tools/bugpoint/CrashDebugger.cpp

   1 //===- CrashDebugger.cpp - Debug compilation crashes ----------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines the bugpoint internals that narrow down compilation crashes
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "BugDriver.h"
  14 #include "ListReducer.h"
  15 #include "ToolRunner.h"
  16 #include "llvm/ADT/SmallPtrSet.h"
  17 #include "llvm/ADT/StringSet.h"
  18 #include "llvm/Analysis/TargetTransformInfo.h"
  19 #include "llvm/Transforms/Utils/Local.h"
  20 #include "llvm/IR/CFG.h"
  21 #include "llvm/IR/Constants.h"
  22 #include "llvm/IR/DebugInfo.h"
  23 #include "llvm/IR/DerivedTypes.h"
  24 #include "llvm/IR/Instructions.h"
  25 #include "llvm/IR/LegacyPassManager.h"
  26 #include "llvm/IR/Module.h"
  27 #include "llvm/IR/ValueSymbolTable.h"
  28 #include "llvm/IR/Verifier.h"
  29 #include "llvm/Pass.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/FileUtilities.h"
  32 #include "llvm/Transforms/Scalar.h"
  33 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  34 #include "llvm/Transforms/Utils/Cloning.h"
  35 #include <set>
  36 using namespace llvm;
  37
  38 namespace {
  39 cl::opt<bool> KeepMain("keep-main",
  40                        cl::desc("Force function reduction to keep main"),
  41                        cl::init(false));
  42 cl::opt<bool> NoGlobalRM("disable-global-remove",
  43                          cl::desc("Do not remove global variables"),
  44                          cl::init(false));
  45
  46 cl::opt<bool> ReplaceFuncsWithNull(
  47     "replace-funcs-with-null",
  48     cl::desc("When stubbing functions, replace all uses will null"),
  49     cl::init(false));
  50 cl::opt<bool> DontReducePassList("disable-pass-list-reduction",
  51                                  cl::desc("Skip pass list reduction steps"),
  52                                  cl::init(false));
  53
  54 cl::opt<bool> NoNamedMDRM("disable-namedmd-remove",
  55                           cl::desc("Do not remove global named metadata"),
  56                           cl::init(false));
  57 cl::opt<bool> NoStripDebugInfo("disable-strip-debuginfo",
  58                                cl::desc("Do not strip debug info metadata"),
  59                                cl::init(false));
  60 cl::opt<bool> NoStripDebugTypeInfo("disable-strip-debug-types",
  61                                cl::desc("Do not strip debug type info metadata"),
  62                                cl::init(false));
  63 cl::opt<bool> VerboseErrors("verbose-errors",
  64                             cl::desc("Print the output of crashing program"),
  65                             cl::init(false));
  66 }
  67
  68 namespace llvm {
  69 class ReducePassList : public ListReducer<std::string> {
  70   BugDriver &BD;
  71
  72 public:
  73   ReducePassList(BugDriver &bd) : BD(bd) {}
  74
  75   // Return true iff running the "removed" passes succeeds, and running the
  76   // "Kept" passes fail when run on the output of the "removed" passes.  If we
  77   // return true, we update the current module of bugpoint.
  78   Expected<TestResult> doTest(std::vector<std::string> &Removed,
  79                               std::vector<std::string> &Kept) override;
  80 };
  81 }
  82
  83 Expected<ReducePassList::TestResult>
  84 ReducePassList::doTest(std::vector<std::string> &Prefix,
  85                        std::vector<std::string> &Suffix) {
  86   std::string PrefixOutput;
  87   std::unique_ptr<Module> OrigProgram;
  88   if (!Prefix.empty()) {
  89     outs() << "Checking to see if these passes crash: "
  90            << getPassesString(Prefix) << ": ";
  91     if (BD.runPasses(BD.getProgram(), Prefix, PrefixOutput))
  92       return KeepPrefix;
  93
  94     OrigProgram = std::move(BD.Program);
  95
  96     BD.Program = parseInputFile(PrefixOutput, BD.getContext());
  97     if (BD.Program == nullptr) {
  98       errs() << BD.getToolName() << ": Error reading bitcode file '"
  99              << PrefixOutput << "'!\n";
 100       exit(1);
 101     }
 102     sys::fs::remove(PrefixOutput);
 103   }
 104
 105   outs() << "Checking to see if these passes crash: " << getPassesString(Suffix)
 106          << ": ";
 107
 108   if (BD.runPasses(BD.getProgram(), Suffix))
 109     return KeepSuffix; // The suffix crashes alone...
 110
 111   // Nothing failed, restore state...
 112   if (OrigProgram)
 113     BD.Program = std::move(OrigProgram);
 114   return NoFailure;
 115 }
 116
 117 using BugTester = bool (*)(const BugDriver &, Module *);
 118
 119 namespace {
 120 /// ReduceCrashingGlobalInitializers - This works by removing global variable
 121 /// initializers and seeing if the program still crashes. If it does, then we
 122 /// keep that program and try again.
 123 class ReduceCrashingGlobalInitializers : public ListReducer<GlobalVariable *> {
 124   BugDriver &BD;
 125   BugTester TestFn;
 126
 127 public:
 128   ReduceCrashingGlobalInitializers(BugDriver &bd, BugTester testFn)
 129       : BD(bd), TestFn(testFn) {}
 130
 131   Expected<TestResult> doTest(std::vector<GlobalVariable *> &Prefix,
 132                               std::vector<GlobalVariable *> &Kept) override {
 133     if (!Kept.empty() && TestGlobalVariables(Kept))
 134       return KeepSuffix;
 135     if (!Prefix.empty() && TestGlobalVariables(Prefix))
 136       return KeepPrefix;
 137     return NoFailure;
 138   }
 139
 140   bool TestGlobalVariables(std::vector<GlobalVariable *> &GVs);
 141 };
 142 }
 143
 144 bool ReduceCrashingGlobalInitializers::TestGlobalVariables(
 145     std::vector<GlobalVariable *> &GVs) {
 146   // Clone the program to try hacking it apart...
 147   ValueToValueMapTy VMap;
 148   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
 149
 150   // Convert list to set for fast lookup...
 151   std::set<GlobalVariable *> GVSet;
 152
 153   for (unsigned i = 0, e = GVs.size(); i != e; ++i) {
 154     GlobalVariable *CMGV = cast<GlobalVariable>(VMap[GVs[i]]);
 155     assert(CMGV && "Global Variable not in module?!");
 156     GVSet.insert(CMGV);
 157   }
 158
 159   outs() << "Checking for crash with only these global variables: ";
 160   PrintGlobalVariableList(GVs);
 161   outs() << ": ";
 162
 163   // Loop over and delete any global variables which we aren't supposed to be
 164   // playing with...
 165   for (GlobalVariable &I : M->globals())
 166     if (I.hasInitializer() && !GVSet.count(&I)) {
 167       DeleteGlobalInitializer(&I);
 168       I.setLinkage(GlobalValue::ExternalLinkage);
 169       I.setComdat(nullptr);
 170     }
 171
 172   // Try running the hacked up program...
 173   if (TestFn(BD, M.get())) {
 174     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
 175
 176     // Make sure to use global variable pointers that point into the now-current
 177     // module.
 178     GVs.assign(GVSet.begin(), GVSet.end());
 179     return true;
 180   }
 181
 182   return false;
 183 }
 184
 185 namespace {
 186 /// ReduceCrashingFunctions reducer - This works by removing functions and
 187 /// seeing if the program still crashes. If it does, then keep the newer,
 188 /// smaller program.
 189 ///
 190 class ReduceCrashingFunctions : public ListReducer<Function *> {
 191   BugDriver &BD;
 192   BugTester TestFn;
 193
 194 public:
 195   ReduceCrashingFunctions(BugDriver &bd, BugTester testFn)
 196       : BD(bd), TestFn(testFn) {}
 197
 198   Expected<TestResult> doTest(std::vector<Function *> &Prefix,
 199                               std::vector<Function *> &Kept) override {
 200     if (!Kept.empty() && TestFuncs(Kept))
 201       return KeepSuffix;
 202     if (!Prefix.empty() && TestFuncs(Prefix))
 203       return KeepPrefix;
 204     return NoFailure;
 205   }
 206
 207   bool TestFuncs(std::vector<Function *> &Prefix);
 208 };
 209 }
 210
 211 static void RemoveFunctionReferences(Module *M, const char *Name) {
 212   auto *UsedVar = M->getGlobalVariable(Name, true);
 213   if (!UsedVar || !UsedVar->hasInitializer())
 214     return;
 215   if (isa<ConstantAggregateZero>(UsedVar->getInitializer())) {
 216     assert(UsedVar->use_empty());
 217     UsedVar->eraseFromParent();
 218     return;
 219   }
 220   auto *OldUsedVal = cast<ConstantArray>(UsedVar->getInitializer());
 221   std::vector<Constant *> Used;
 222   for (Value *V : OldUsedVal->operand_values()) {
 223     Constant *Op = cast<Constant>(V->stripPointerCasts());
 224     if (!Op->isNullValue()) {
 225       Used.push_back(cast<Constant>(V));
 226     }
 227   }
 228   auto *NewValElemTy = OldUsedVal->getType()->getElementType();
 229   auto *NewValTy = ArrayType::get(NewValElemTy, Used.size());
 230   auto *NewUsedVal = ConstantArray::get(NewValTy, Used);
 231   UsedVar->mutateType(NewUsedVal->getType()->getPointerTo());
 232   UsedVar->setInitializer(NewUsedVal);
 233 }
 234
 235 bool ReduceCrashingFunctions::TestFuncs(std::vector<Function *> &Funcs) {
 236   // If main isn't present, claim there is no problem.
 237   if (KeepMain && !is_contained(Funcs, BD.getProgram().getFunction("main")))
 238     return false;
 239
 240   // Clone the program to try hacking it apart...
 241   ValueToValueMapTy VMap;
 242   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
 243
 244   // Convert list to set for fast lookup...
 245   std::set<Function *> Functions;
 246   for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
 247     Function *CMF = cast<Function>(VMap[Funcs[i]]);
 248     assert(CMF && "Function not in module?!");
 249     assert(CMF->getFunctionType() == Funcs[i]->getFunctionType() && "wrong ty");
 250     assert(CMF->getName() == Funcs[i]->getName() && "wrong name");
 251     Functions.insert(CMF);
 252   }
 253
 254   outs() << "Checking for crash with only these functions: ";
 255   PrintFunctionList(Funcs);
 256   outs() << ": ";
 257   if (!ReplaceFuncsWithNull) {
 258     // Loop over and delete any functions which we aren't supposed to be playing
 259     // with...
 260     for (Function &I : *M)
 261       if (!I.isDeclaration() && !Functions.count(&I))
 262         DeleteFunctionBody(&I);
 263   } else {
 264     std::vector<GlobalValue *> ToRemove;
 265     // First, remove aliases to functions we're about to purge.
 266     for (GlobalAlias &Alias : M->aliases()) {
 267       GlobalObject *Root = Alias.getBaseObject();
 268       Function *F = dyn_cast_or_null<Function>(Root);
 269       if (F) {
 270         if (Functions.count(F))
 271           // We're keeping this function.
 272           continue;
 273       } else if (Root->isNullValue()) {
 274         // This referenced a globalalias that we've already replaced,
 275         // so we still need to replace this alias.
 276       } else if (!F) {
 277         // Not a function, therefore not something we mess with.
 278         continue;
 279       }
 280
 281       PointerType *Ty = cast<PointerType>(Alias.getType());
 282       Constant *Replacement = ConstantPointerNull::get(Ty);
 283       Alias.replaceAllUsesWith(Replacement);
 284       ToRemove.push_back(&Alias);
 285     }
 286
 287     for (Function &I : *M) {
 288       if (!I.isDeclaration() && !Functions.count(&I)) {
 289         PointerType *Ty = cast<PointerType>(I.getType());
 290         Constant *Replacement = ConstantPointerNull::get(Ty);
 291         I.replaceAllUsesWith(Replacement);
 292         ToRemove.push_back(&I);
 293       }
 294     }
 295
 296     for (auto *F : ToRemove) {
 297       F->eraseFromParent();
 298     }
 299
 300     // Finally, remove any null members from any global intrinsic.
 301     RemoveFunctionReferences(M.get(), "llvm.used");
 302     RemoveFunctionReferences(M.get(), "llvm.compiler.used");
 303   }
 304   // Try running the hacked up program...
 305   if (TestFn(BD, M.get())) {
 306     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
 307
 308     // Make sure to use function pointers that point into the now-current
 309     // module.
 310     Funcs.assign(Functions.begin(), Functions.end());
 311     return true;
 312   }
 313   return false;
 314 }
 315
 316 namespace {
 317 /// ReduceCrashingFunctionAttributes reducer - This works by removing
 318 /// attributes on a particular function and seeing if the program still crashes.
 319 /// If it does, then keep the newer, smaller program.
 320 ///
 321 class ReduceCrashingFunctionAttributes : public ListReducer<Attribute> {
 322   BugDriver &BD;
 323   std::string FnName;
 324   BugTester TestFn;
 325
 326 public:
 327   ReduceCrashingFunctionAttributes(BugDriver &bd, const std::string &FnName,
 328                                    BugTester testFn)
 329       : BD(bd), FnName(FnName), TestFn(testFn) {}
 330
 331   Expected<TestResult> doTest(std::vector<Attribute> &Prefix,
 332                               std::vector<Attribute> &Kept) override {
 333     if (!Kept.empty() && TestFuncAttrs(Kept))
 334       return KeepSuffix;
 335     if (!Prefix.empty() && TestFuncAttrs(Prefix))
 336       return KeepPrefix;
 337     return NoFailure;
 338   }
 339
 340   bool TestFuncAttrs(std::vector<Attribute> &Attrs);
 341 };
 342 }
 343
 344 bool ReduceCrashingFunctionAttributes::TestFuncAttrs(
 345     std::vector<Attribute> &Attrs) {
 346   // Clone the program to try hacking it apart...
 347   std::unique_ptr<Module> M = CloneModule(BD.getProgram());
 348   Function *F = M->getFunction(FnName);
 349
 350   // Build up an AttributeList from the attributes we've been given by the
 351   // reducer.
 352   AttrBuilder AB;
 353   for (auto A : Attrs)
 354     AB.addAttribute(A);
 355   AttributeList NewAttrs;
 356   NewAttrs =
 357       NewAttrs.addAttributes(BD.getContext(), AttributeList::FunctionIndex, AB);
 358
 359   // Set this new list of attributes on the function.
 360   F->setAttributes(NewAttrs);
 361
 362   // Try running on the hacked up program...
 363   if (TestFn(BD, M.get())) {
 364     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
 365
 366     // Pass along the set of attributes that caused the crash.
 367     Attrs.clear();
 368     for (Attribute A : NewAttrs.getFnAttributes()) {
 369       Attrs.push_back(A);
 370     }
 371     return true;
 372   }
 373   return false;
 374 }
 375
 376 namespace {
 377 /// Simplify the CFG without completely destroying it.
 378 /// This is not well defined, but basically comes down to "try to eliminate
 379 /// unreachable blocks and constant fold terminators without deciding that
 380 /// certain undefined behavior cuts off the program at the legs".
 381 void simpleSimplifyCfg(Function &F, SmallVectorImpl<BasicBlock *> &BBs) {
 382   if (F.empty())
 383     return;
 384
 385   for (auto *BB : BBs) {
 386     ConstantFoldTerminator(BB);
 387     MergeBlockIntoPredecessor(BB);
 388   }
 389
 390   // Remove unreachable blocks
 391   // removeUnreachableBlocks can't be used here, it will turn various
 392   // undefined behavior into unreachables, but bugpoint was the thing that
 393   // generated the undefined behavior, and we don't want it to kill the entire
 394   // program.
 395   SmallPtrSet<BasicBlock *, 16> Visited;
 396   for (auto *BB : depth_first(&F.getEntryBlock()))
 397     Visited.insert(BB);
 398
 399   SmallVector<BasicBlock *, 16> Unreachable;
 400   for (auto &BB : F)
 401     if (!Visited.count(&BB))
 402       Unreachable.push_back(&BB);
 403
 404   // The dead BB's may be in a dead cycle or otherwise have references to each
 405   // other.  Because of this, we have to drop all references first, then delete
 406   // them all at once.
 407   for (auto *BB : Unreachable) {
 408     for (BasicBlock *Successor : successors(&*BB))
 409       if (Visited.count(Successor))
 410         Successor->removePredecessor(&*BB);
 411     BB->dropAllReferences();
 412   }
 413   for (auto *BB : Unreachable)
 414     BB->eraseFromParent();
 415 }
 416 /// ReduceCrashingBlocks reducer - This works by setting the terminators of
 417 /// all terminators except the specified basic blocks to a 'ret' instruction,
 418 /// then running the simplify-cfg pass.  This has the effect of chopping up
 419 /// the CFG really fast which can reduce large functions quickly.
 420 ///
 421 class ReduceCrashingBlocks : public ListReducer<const BasicBlock *> {
 422   BugDriver &BD;
 423   BugTester TestFn;
 424
 425 public:
 426   ReduceCrashingBlocks(BugDriver &BD, BugTester testFn)
 427       : BD(BD), TestFn(testFn) {}
 428
 429   Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
 430                               std::vector<const BasicBlock *> &Kept) override {
 431     if (!Kept.empty() && TestBlocks(Kept))
 432       return KeepSuffix;
 433     if (!Prefix.empty() && TestBlocks(Prefix))
 434       return KeepPrefix;
 435     return NoFailure;
 436   }
 437
 438   bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
 439 };
 440 }
 441
 442 bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock *> &BBs) {
 443   // Clone the program to try hacking it apart...
 444   ValueToValueMapTy VMap;
 445   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
 446
 447   // Convert list to set for fast lookup...
 448   SmallPtrSet<BasicBlock *, 8> Blocks;
 449   for (unsigned i = 0, e = BBs.size(); i != e; ++i)
 450     Blocks.insert(cast<BasicBlock>(VMap[BBs[i]]));
 451
 452   outs() << "Checking for crash with only these blocks:";
 453   unsigned NumPrint = Blocks.size();
 454   if (NumPrint > 10)
 455     NumPrint = 10;
 456   for (unsigned i = 0, e = NumPrint; i != e; ++i)
 457     outs() << " " << BBs[i]->getName();
 458   if (NumPrint < Blocks.size())
 459     outs() << "... <" << Blocks.size() << " total>";
 460   outs() << ": ";
 461
 462   // Loop over and delete any hack up any blocks that are not listed...
 463   for (Function &F : M->functions()) {
 464     for (BasicBlock &BB : F) {
 465       if (!Blocks.count(&BB) && BB.getTerminator()->getNumSuccessors()) {
 466         // Loop over all of the successors of this block, deleting any PHI nodes
 467         // that might include it.
 468         for (BasicBlock *Succ : successors(&BB))
 469           Succ->removePredecessor(&BB);
 470
 471         Instruction *BBTerm = BB.getTerminator();
 472         if (BBTerm->isEHPad() || BBTerm->getType()->isTokenTy())
 473           continue;
 474         if (!BBTerm->getType()->isVoidTy())
 475           BBTerm->replaceAllUsesWith(Constant::getNullValue(BBTerm->getType()));
 476
 477         // Replace the old terminator instruction.
 478         BB.getInstList().pop_back();
 479         new UnreachableInst(BB.getContext(), &BB);
 480       }
 481     }
 482   }
 483
 484   // The CFG Simplifier pass may delete one of the basic blocks we are
 485   // interested in.  If it does we need to take the block out of the list.  Make
 486   // a "persistent mapping" by turning basic blocks into <function, name> pairs.
 487   // This won't work well if blocks are unnamed, but that is just the risk we
 488   // have to take. FIXME: Can we just name the blocks?
 489   std::vector<std::pair<std::string, std::string>> BlockInfo;
 490
 491   for (BasicBlock *BB : Blocks)
 492     BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName());
 493
 494   SmallVector<BasicBlock *, 16> ToProcess;
 495   for (auto &F : *M) {
 496     for (auto &BB : F)
 497       if (!Blocks.count(&BB))
 498         ToProcess.push_back(&BB);
 499     simpleSimplifyCfg(F, ToProcess);
 500     ToProcess.clear();
 501   }
 502   // Verify we didn't break anything
 503   std::vector<std::string> Passes;
 504   Passes.push_back("verify");
 505   std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
 506   if (!New) {
 507     errs() << "verify failed!\n";
 508     exit(1);
 509   }
 510   M = std::move(New);
 511
 512   // Try running on the hacked up program...
 513   if (TestFn(BD, M.get())) {
 514     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
 515
 516     // Make sure to use basic block pointers that point into the now-current
 517     // module, and that they don't include any deleted blocks.
 518     BBs.clear();
 519     const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
 520     for (const auto &BI : BlockInfo) {
 521       Function *F = cast<Function>(GST.lookup(BI.first));
 522       Value *V = F->getValueSymbolTable()->lookup(BI.second);
 523       if (V && V->getType() == Type::getLabelTy(V->getContext()))
 524         BBs.push_back(cast<BasicBlock>(V));
 525     }
 526     return true;
 527   }
 528   // It didn't crash, try something else.
 529   return false;
 530 }
 531
 532 namespace {
 533 /// ReduceCrashingConditionals reducer - This works by changing
 534 /// conditional branches to unconditional ones, then simplifying the CFG
 535 /// This has the effect of chopping up the CFG really fast which can reduce
 536 /// large functions quickly.
 537 ///
 538 class ReduceCrashingConditionals : public ListReducer<const BasicBlock *> {
 539   BugDriver &BD;
 540   BugTester TestFn;
 541   bool Direction;
 542
 543 public:
 544   ReduceCrashingConditionals(BugDriver &bd, BugTester testFn, bool Direction)
 545       : BD(bd), TestFn(testFn), Direction(Direction) {}
 546
 547   Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
 548                               std::vector<const BasicBlock *> &Kept) override {
 549     if (!Kept.empty() && TestBlocks(Kept))
 550       return KeepSuffix;
 551     if (!Prefix.empty() && TestBlocks(Prefix))
 552       return KeepPrefix;
 553     return NoFailure;
 554   }
 555
 556   bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
 557 };
 558 }
 559
 560 bool ReduceCrashingConditionals::TestBlocks(
 561     std::vector<const BasicBlock *> &BBs) {
 562   // Clone the program to try hacking it apart...
 563   ValueToValueMapTy VMap;
 564   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
 565
 566   // Convert list to set for fast lookup...
 567   SmallPtrSet<const BasicBlock *, 8> Blocks;
 568   for (const auto *BB : BBs)
 569     Blocks.insert(cast<BasicBlock>(VMap[BB]));
 570
 571   outs() << "Checking for crash with changing conditionals to always jump to "
 572          << (Direction ? "true" : "false") << ":";
 573   unsigned NumPrint = Blocks.size();
 574   if (NumPrint > 10)
 575     NumPrint = 10;
 576   for (unsigned i = 0, e = NumPrint; i != e; ++i)
 577     outs() << " " << BBs[i]->getName();
 578   if (NumPrint < Blocks.size())
 579     outs() << "... <" << Blocks.size() << " total>";
 580   outs() << ": ";
 581
 582   // Loop over and delete any hack up any blocks that are not listed...
 583   for (auto &F : *M)
 584     for (auto &BB : F)
 585       if (!Blocks.count(&BB)) {
 586         auto *BR = dyn_cast<BranchInst>(BB.getTerminator());
 587         if (!BR || !BR->isConditional())
 588           continue;
 589         if (Direction)
 590           BR->setCondition(ConstantInt::getTrue(BR->getContext()));
 591         else
 592           BR->setCondition(ConstantInt::getFalse(BR->getContext()));
 593       }
 594
 595   // The following may destroy some blocks, so we save them first
 596   std::vector<std::pair<std::string, std::string>> BlockInfo;
 597
 598   for (const BasicBlock *BB : Blocks)
 599     BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName());
 600
 601   SmallVector<BasicBlock *, 16> ToProcess;
 602   for (auto &F : *M) {
 603     for (auto &BB : F)
 604       if (!Blocks.count(&BB))
 605         ToProcess.push_back(&BB);
 606     simpleSimplifyCfg(F, ToProcess);
 607     ToProcess.clear();
 608   }
 609   // Verify we didn't break anything
 610   std::vector<std::string> Passes;
 611   Passes.push_back("verify");
 612   std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
 613   if (!New) {
 614     errs() << "verify failed!\n";
 615     exit(1);
 616   }
 617   M = std::move(New);
 618
 619   // Try running on the hacked up program...
 620   if (TestFn(BD, M.get())) {
 621     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
 622
 623     // Make sure to use basic block pointers that point into the now-current
 624     // module, and that they don't include any deleted blocks.
 625     BBs.clear();
 626     const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
 627     for (auto &BI : BlockInfo) {
 628       auto *F = cast<Function>(GST.lookup(BI.first));
 629       Value *V = F->getValueSymbolTable()->lookup(BI.second);
 630       if (V && V->getType() == Type::getLabelTy(V->getContext()))
 631         BBs.push_back(cast<BasicBlock>(V));
 632     }
 633     return true;
 634   }
 635   // It didn't crash, try something else.
 636   return false;
 637 }
 638
 639 namespace {
 640 /// SimplifyCFG reducer - This works by calling SimplifyCFG on each basic block
 641 /// in the program.
 642
 643 class ReduceSimplifyCFG : public ListReducer<const BasicBlock *> {
 644   BugDriver &BD;
 645   BugTester TestFn;
 646   TargetTransformInfo TTI;
 647
 648 public:
 649   ReduceSimplifyCFG(BugDriver &bd, BugTester testFn)
 650       : BD(bd), TestFn(testFn), TTI(bd.getProgram().getDataLayout()) {}
 651
 652   Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
 653                               std::vector<const BasicBlock *> &Kept) override {
 654     if (!Kept.empty() && TestBlocks(Kept))
 655       return KeepSuffix;
 656     if (!Prefix.empty() && TestBlocks(Prefix))
 657       return KeepPrefix;
 658     return NoFailure;
 659   }
 660
 661   bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
 662 };
 663 }
 664
 665 bool ReduceSimplifyCFG::TestBlocks(std::vector<const BasicBlock *> &BBs) {
 666   // Clone the program to try hacking it apart...
 667   ValueToValueMapTy VMap;
 668   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
 669
 670   // Convert list to set for fast lookup...
 671   SmallPtrSet<const BasicBlock *, 8> Blocks;
 672   for (const auto *BB : BBs)
 673     Blocks.insert(cast<BasicBlock>(VMap[BB]));
 674
 675   outs() << "Checking for crash with CFG simplifying:";
 676   unsigned NumPrint = Blocks.size();
 677   if (NumPrint > 10)
 678     NumPrint = 10;
 679   for (unsigned i = 0, e = NumPrint; i != e; ++i)
 680     outs() << " " << BBs[i]->getName();
 681   if (NumPrint < Blocks.size())
 682     outs() << "... <" << Blocks.size() << " total>";
 683   outs() << ": ";
 684
 685   // The following may destroy some blocks, so we save them first
 686   std::vector<std::pair<std::string, std::string>> BlockInfo;
 687
 688   for (const BasicBlock *BB : Blocks)
 689     BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName());
 690
 691   // Loop over and delete any hack up any blocks that are not listed...
 692   for (auto &F : *M)
 693     // Loop over all of the basic blocks and remove them if they are unneeded.
 694     for (Function::iterator BBIt = F.begin(); BBIt != F.end();) {
 695       if (!Blocks.count(&*BBIt)) {
 696         ++BBIt;
 697         continue;
 698       }
 699       simplifyCFG(&*BBIt++, TTI);
 700     }
 701   // Verify we didn't break anything
 702   std::vector<std::string> Passes;
 703   Passes.push_back("verify");
 704   std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
 705   if (!New) {
 706     errs() << "verify failed!\n";
 707     exit(1);
 708   }
 709   M = std::move(New);
 710
 711   // Try running on the hacked up program...
 712   if (TestFn(BD, M.get())) {
 713     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
 714
 715     // Make sure to use basic block pointers that point into the now-current
 716     // module, and that they don't include any deleted blocks.
 717     BBs.clear();
 718     const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
 719     for (auto &BI : BlockInfo) {
 720       auto *F = cast<Function>(GST.lookup(BI.first));
 721       Value *V = F->getValueSymbolTable()->lookup(BI.second);
 722       if (V && V->getType() == Type::getLabelTy(V->getContext()))
 723         BBs.push_back(cast<BasicBlock>(V));
 724     }
 725     return true;
 726   }
 727   // It didn't crash, try something else.
 728   return false;
 729 }
 730
 731 namespace {
 732 /// ReduceCrashingInstructions reducer - This works by removing the specified
 733 /// non-terminator instructions and replacing them with undef.
 734 ///
 735 class ReduceCrashingInstructions : public ListReducer<const Instruction *> {
 736   BugDriver &BD;
 737   BugTester TestFn;
 738
 739 public:
 740   ReduceCrashingInstructions(BugDriver &bd, BugTester testFn)
 741       : BD(bd), TestFn(testFn) {}
 742
 743   Expected<TestResult> doTest(std::vector<const Instruction *> &Prefix,
 744                               std::vector<const Instruction *> &Kept) override {
 745     if (!Kept.empty() && TestInsts(Kept))
 746       return KeepSuffix;
 747     if (!Prefix.empty() && TestInsts(Prefix))
 748       return KeepPrefix;
 749     return NoFailure;
 750   }
 751
 752   bool TestInsts(std::vector<const Instruction *> &Prefix);
 753 };
 754 }
 755
 756 bool ReduceCrashingInstructions::TestInsts(
 757     std::vector<const Instruction *> &Insts) {
 758   // Clone the program to try hacking it apart...
 759   ValueToValueMapTy VMap;
 760   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
 761
 762   // Convert list to set for fast lookup...
 763   SmallPtrSet<Instruction *, 32> Instructions;
 764   for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
 765     assert(!Insts[i]->isTerminator());
 766     Instructions.insert(cast<Instruction>(VMap[Insts[i]]));
 767   }
 768
 769   outs() << "Checking for crash with only " << Instructions.size();
 770   if (Instructions.size() == 1)
 771     outs() << " instruction: ";
 772   else
 773     outs() << " instructions: ";
 774
 775   for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI)
 776     for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI)
 777       for (BasicBlock::iterator I = FI->begin(), E = FI->end(); I != E;) {
 778         Instruction *Inst = &*I++;
 779         if (!Instructions.count(Inst) && !Inst->isTerminator() &&
 780             !Inst->isEHPad() && !Inst->getType()->isTokenTy() &&
 781             !Inst->isSwiftError()) {
 782           if (!Inst->getType()->isVoidTy())
 783             Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
 784           Inst->eraseFromParent();
 785         }
 786       }
 787
 788   // Verify that this is still valid.
 789   legacy::PassManager Passes;
 790   Passes.add(createVerifierPass(/*FatalErrors=*/false));
 791   Passes.run(*M);
 792
 793   // Try running on the hacked up program...
 794   if (TestFn(BD, M.get())) {
 795     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
 796
 797     // Make sure to use instruction pointers that point into the now-current
 798     // module, and that they don't include any deleted blocks.
 799     Insts.clear();
 800     for (Instruction *Inst : Instructions)
 801       Insts.push_back(Inst);
 802     return true;
 803   }
 804   // It didn't crash, try something else.
 805   return false;
 806 }
 807
 808 namespace {
 809 // Reduce the list of Named Metadata nodes. We keep this as a list of
 810 // names to avoid having to convert back and forth every time.
 811 class ReduceCrashingNamedMD : public ListReducer<std::string> {
 812   BugDriver &BD;
 813   BugTester TestFn;
 814
 815 public:
 816   ReduceCrashingNamedMD(BugDriver &bd, BugTester testFn)
 817       : BD(bd), TestFn(testFn) {}
 818
 819   Expected<TestResult> doTest(std::vector<std::string> &Prefix,
 820                               std::vector<std::string> &Kept) override {
 821     if (!Kept.empty() && TestNamedMDs(Kept))
 822       return KeepSuffix;
 823     if (!Prefix.empty() && TestNamedMDs(Prefix))
 824       return KeepPrefix;
 825     return NoFailure;
 826   }
 827
 828   bool TestNamedMDs(std::vector<std::string> &NamedMDs);
 829 };
 830 }
 831
 832 bool ReduceCrashingNamedMD::TestNamedMDs(std::vector<std::string> &NamedMDs) {
 833
 834   ValueToValueMapTy VMap;
 835   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
 836
 837   outs() << "Checking for crash with only these named metadata nodes:";
 838   unsigned NumPrint = std::min<size_t>(NamedMDs.size(), 10);
 839   for (unsigned i = 0, e = NumPrint; i != e; ++i)
 840     outs() << " " << NamedMDs[i];
 841   if (NumPrint < NamedMDs.size())
 842     outs() << "... <" << NamedMDs.size() << " total>";
 843   outs() << ": ";
 844
 845   // Make a StringMap for faster lookup
 846   StringSet<> Names;
 847   for (const std::string &Name : NamedMDs)
 848     Names.insert(Name);
 849
 850   // First collect all the metadata to delete in a vector, then
 851   // delete them all at once to avoid invalidating the iterator
 852   std::vector<NamedMDNode *> ToDelete;
 853   ToDelete.reserve(M->named_metadata_size() - Names.size());
 854   for (auto &NamedMD : M->named_metadata())
 855     // Always keep a nonempty llvm.dbg.cu because the Verifier would complain.
 856     if (!Names.count(NamedMD.getName()) &&
 857         (!(NamedMD.getName() == "llvm.dbg.cu" && NamedMD.getNumOperands() > 0)))
 858       ToDelete.push_back(&NamedMD);
 859
 860   for (auto *NamedMD : ToDelete)
 861     NamedMD->eraseFromParent();
 862
 863   // Verify that this is still valid.
 864   legacy::PassManager Passes;
 865   Passes.add(createVerifierPass(/*FatalErrors=*/false));
 866   Passes.run(*M);
 867
 868   // Try running on the hacked up program...
 869   if (TestFn(BD, M.get())) {
 870     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
 871     return true;
 872   }
 873   return false;
 874 }
 875
 876 namespace {
 877 // Reduce the list of operands to named metadata nodes
 878 class ReduceCrashingNamedMDOps : public ListReducer<const MDNode *> {
 879   BugDriver &BD;
 880   BugTester TestFn;
 881
 882 public:
 883   ReduceCrashingNamedMDOps(BugDriver &bd, BugTester testFn)
 884       : BD(bd), TestFn(testFn) {}
 885
 886   Expected<TestResult> doTest(std::vector<const MDNode *> &Prefix,
 887                               std::vector<const MDNode *> &Kept) override {
 888     if (!Kept.empty() && TestNamedMDOps(Kept))
 889       return KeepSuffix;
 890     if (!Prefix.empty() && TestNamedMDOps(Prefix))
 891       return KeepPrefix;
 892     return NoFailure;
 893   }
 894
 895   bool TestNamedMDOps(std::vector<const MDNode *> &NamedMDOps);
 896 };
 897 }
 898
 899 bool ReduceCrashingNamedMDOps::TestNamedMDOps(
 900     std::vector<const MDNode *> &NamedMDOps) {
 901   // Convert list to set for fast lookup...
 902   SmallPtrSet<const MDNode *, 32> OldMDNodeOps;
 903   for (unsigned i = 0, e = NamedMDOps.size(); i != e; ++i) {
 904     OldMDNodeOps.insert(NamedMDOps[i]);
 905   }
 906
 907   outs() << "Checking for crash with only " << OldMDNodeOps.size();
 908   if (OldMDNodeOps.size() == 1)
 909     outs() << " named metadata operand: ";
 910   else
 911     outs() << " named metadata operands: ";
 912
 913   ValueToValueMapTy VMap;
 914   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
 915
 916   // This is a little wasteful. In the future it might be good if we could have
 917   // these dropped during cloning.
 918   for (auto &NamedMD : BD.getProgram().named_metadata()) {
 919     // Drop the old one and create a new one
 920     M->eraseNamedMetadata(M->getNamedMetadata(NamedMD.getName()));
 921     NamedMDNode *NewNamedMDNode =
 922         M->getOrInsertNamedMetadata(NamedMD.getName());
 923     for (MDNode *op : NamedMD.operands())
 924       if (OldMDNodeOps.count(op))
 925         NewNamedMDNode->addOperand(cast<MDNode>(MapMetadata(op, VMap)));
 926   }
 927
 928   // Verify that this is still valid.
 929   legacy::PassManager Passes;
 930   Passes.add(createVerifierPass(/*FatalErrors=*/false));
 931   Passes.run(*M);
 932
 933   // Try running on the hacked up program...
 934   if (TestFn(BD, M.get())) {
 935     // Make sure to use instruction pointers that point into the now-current
 936     // module, and that they don't include any deleted blocks.
 937     NamedMDOps.clear();
 938     for (const MDNode *Node : OldMDNodeOps)
 939       NamedMDOps.push_back(cast<MDNode>(*VMap.getMappedMD(Node)));
 940
 941     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
 942     return true;
 943   }
 944   // It didn't crash, try something else.
 945   return false;
 946 }
 947
 948 /// Attempt to eliminate as many global initializers as possible.
 949 static Error ReduceGlobalInitializers(BugDriver &BD, BugTester TestFn) {
 950   Module &OrigM = BD.getProgram();
 951   if (OrigM.global_empty())
 952     return Error::success();
 953
 954   // Now try to reduce the number of global variable initializers in the
 955   // module to something small.
 956   std::unique_ptr<Module> M = CloneModule(OrigM);
 957   bool DeletedInit = false;
 958
 959   for (GlobalVariable &GV : M->globals()) {
 960     if (GV.hasInitializer()) {
 961       DeleteGlobalInitializer(&GV);
 962       GV.setLinkage(GlobalValue::ExternalLinkage);
 963       GV.setComdat(nullptr);
 964       DeletedInit = true;
 965     }
 966   }
 967
 968   if (!DeletedInit)
 969     return Error::success();
 970
 971   // See if the program still causes a crash...
 972   outs() << "\nChecking to see if we can delete global inits: ";
 973
 974   if (TestFn(BD, M.get())) { // Still crashes?
 975     BD.setNewProgram(std::move(M));
 976     outs() << "\n*** Able to remove all global initializers!\n";
 977     return Error::success();
 978   }
 979
 980   // No longer crashes.
 981   outs() << "  - Removing all global inits hides problem!\n";
 982
 983   std::vector<GlobalVariable *> GVs;
 984   for (GlobalVariable &GV : OrigM.globals())
 985     if (GV.hasInitializer())
 986       GVs.push_back(&GV);
 987
 988   if (GVs.size() > 1 && !BugpointIsInterrupted) {
 989     outs() << "\n*** Attempting to reduce the number of global initializers "
 990            << "in the testcase\n";
 991
 992     unsigned OldSize = GVs.size();
 993     Expected<bool> Result =
 994         ReduceCrashingGlobalInitializers(BD, TestFn).reduceList(GVs);
 995     if (Error E = Result.takeError())
 996       return E;
 997
 998     if (GVs.size() < OldSize)
 999       BD.EmitProgressBitcode(BD.getProgram(), "reduced-global-variables");
1000   }
1001   return Error::success();
1002 }
1003
1004 static Error ReduceInsts(BugDriver &BD, BugTester TestFn) {
1005   // Attempt to delete instructions using bisection. This should help out nasty
1006   // cases with large basic blocks where the problem is at one end.
1007   if (!BugpointIsInterrupted) {
1008     std::vector<const Instruction *> Insts;
1009     for (const Function &F : BD.getProgram())
1010       for (const BasicBlock &BB : F)
1011         for (const Instruction &I : BB)
1012           if (!I.isTerminator())
1013             Insts.push_back(&I);
1014
1015     Expected<bool> Result =
1016         ReduceCrashingInstructions(BD, TestFn).reduceList(Insts);
1017     if (Error E = Result.takeError())
1018       return E;
1019   }
1020
1021   unsigned Simplification = 2;
1022   do {
1023     if (BugpointIsInterrupted)
1024       // TODO: Should we distinguish this with an "interrupted error"?
1025       return Error::success();
1026     --Simplification;
1027     outs() << "\n*** Attempting to reduce testcase by deleting instruc"
1028            << "tions: Simplification Level #" << Simplification << '\n';
1029
1030     // Now that we have deleted the functions that are unnecessary for the
1031     // program, try to remove instructions that are not necessary to cause the
1032     // crash.  To do this, we loop through all of the instructions in the
1033     // remaining functions, deleting them (replacing any values produced with
1034     // nulls), and then running ADCE and SimplifyCFG.  If the transformed input
1035     // still triggers failure, keep deleting until we cannot trigger failure
1036     // anymore.
1037     //
1038     unsigned InstructionsToSkipBeforeDeleting = 0;
1039   TryAgain:
1040
1041     // Loop over all of the (non-terminator) instructions remaining in the
1042     // function, attempting to delete them.
1043     unsigned CurInstructionNum = 0;
1044     for (Module::const_iterator FI = BD.getProgram().begin(),
1045                                 E = BD.getProgram().end();
1046          FI != E; ++FI)
1047       if (!FI->isDeclaration())
1048         for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E;
1049              ++BI)
1050           for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end();
1051                I != E; ++I, ++CurInstructionNum) {
1052             if (InstructionsToSkipBeforeDeleting) {
1053               --InstructionsToSkipBeforeDeleting;
1054             } else {
1055               if (BugpointIsInterrupted)
1056                 // TODO: Should this be some kind of interrupted error?
1057                 return Error::success();
1058
1059               if (I->isEHPad() || I->getType()->isTokenTy() ||
1060                   I->isSwiftError())
1061                 continue;
1062
1063               outs() << "Checking instruction: " << *I;
1064               std::unique_ptr<Module> M =
1065                   BD.deleteInstructionFromProgram(&*I, Simplification);
1066
1067               // Find out if the pass still crashes on this pass...
1068               if (TestFn(BD, M.get())) {
1069                 // Yup, it does, we delete the old module, and continue trying
1070                 // to reduce the testcase...
1071                 BD.setNewProgram(std::move(M));
1072                 InstructionsToSkipBeforeDeleting = CurInstructionNum;
1073                 goto TryAgain; // I wish I had a multi-level break here!
1074               }
1075             }
1076           }
1077
1078     if (InstructionsToSkipBeforeDeleting) {
1079       InstructionsToSkipBeforeDeleting = 0;
1080       goto TryAgain;
1081     }
1082
1083   } while (Simplification);
1084   BD.EmitProgressBitcode(BD.getProgram(), "reduced-instructions");
1085   return Error::success();
1086 }
1087
1088 /// DebugACrash - Given a predicate that determines whether a component crashes
1089 /// on a program, try to destructively reduce the program while still keeping
1090 /// the predicate true.
1091 static Error DebugACrash(BugDriver &BD, BugTester TestFn) {
1092   // See if we can get away with nuking some of the global variable initializers
1093   // in the program...
1094   if (!NoGlobalRM)
1095     if (Error E = ReduceGlobalInitializers(BD, TestFn))
1096       return E;
1097
1098   // Now try to reduce the number of functions in the module to something small.
1099   std::vector<Function *> Functions;
1100   for (Function &F : BD.getProgram())
1101     if (!F.isDeclaration())
1102       Functions.push_back(&F);
1103
1104   if (Functions.size() > 1 && !BugpointIsInterrupted) {
1105     outs() << "\n*** Attempting to reduce the number of functions "
1106               "in the testcase\n";
1107
1108     unsigned OldSize = Functions.size();
1109     Expected<bool> Result =
1110         ReduceCrashingFunctions(BD, TestFn).reduceList(Functions);
1111     if (Error E = Result.takeError())
1112       return E;
1113
1114     if (Functions.size() < OldSize)
1115       BD.EmitProgressBitcode(BD.getProgram(), "reduced-function");
1116   }
1117
1118   // For each remaining function, try to reduce that function's attributes.
1119   std::vector<std::string> FunctionNames;
1120   for (Function &F : BD.getProgram())
1121     FunctionNames.push_back(F.getName());
1122
1123   if (!FunctionNames.empty() && !BugpointIsInterrupted) {
1124     outs() << "\n*** Attempting to reduce the number of function attributes in "
1125               "the testcase\n";
1126
1127     unsigned OldSize = 0;
1128     unsigned NewSize = 0;
1129     for (std::string &Name : FunctionNames) {
1130       Function *Fn = BD.getProgram().getFunction(Name);
1131       assert(Fn && "Could not find funcion?");
1132
1133       std::vector<Attribute> Attrs;
1134       for (Attribute A : Fn->getAttributes().getFnAttributes())
1135         Attrs.push_back(A);
1136
1137       OldSize += Attrs.size();
1138       Expected<bool> Result =
1139           ReduceCrashingFunctionAttributes(BD, Name, TestFn).reduceList(Attrs);
1140       if (Error E = Result.takeError())
1141         return E;
1142
1143       NewSize += Attrs.size();
1144     }
1145
1146     if (OldSize < NewSize)
1147       BD.EmitProgressBitcode(BD.getProgram(), "reduced-function-attributes");
1148   }
1149
1150   // Attempt to change conditional branches into unconditional branches to
1151   // eliminate blocks.
1152   if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1153     std::vector<const BasicBlock *> Blocks;
1154     for (Function &F : BD.getProgram())
1155       for (BasicBlock &BB : F)
1156         Blocks.push_back(&BB);
1157     unsigned OldSize = Blocks.size();
1158     Expected<bool> Result =
1159         ReduceCrashingConditionals(BD, TestFn, true).reduceList(Blocks);
1160     if (Error E = Result.takeError())
1161       return E;
1162     Result = ReduceCrashingConditionals(BD, TestFn, false).reduceList(Blocks);
1163     if (Error E = Result.takeError())
1164       return E;
1165     if (Blocks.size() < OldSize)
1166       BD.EmitProgressBitcode(BD.getProgram(), "reduced-conditionals");
1167   }
1168
1169   // Attempt to delete entire basic blocks at a time to speed up
1170   // convergence... this actually works by setting the terminator of the blocks
1171   // to a return instruction then running simplifycfg, which can potentially
1172   // shrinks the code dramatically quickly
1173   //
1174   if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1175     std::vector<const BasicBlock *> Blocks;
1176     for (Function &F : BD.getProgram())
1177       for (BasicBlock &BB : F)
1178         Blocks.push_back(&BB);
1179     unsigned OldSize = Blocks.size();
1180     Expected<bool> Result = ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks);
1181     if (Error E = Result.takeError())
1182       return E;
1183     if (Blocks.size() < OldSize)
1184       BD.EmitProgressBitcode(BD.getProgram(), "reduced-blocks");
1185   }
1186
1187   if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1188     std::vector<const BasicBlock *> Blocks;
1189     for (Function &F : BD.getProgram())
1190       for (BasicBlock &BB : F)
1191         Blocks.push_back(&BB);
1192     unsigned OldSize = Blocks.size();
1193     Expected<bool> Result = ReduceSimplifyCFG(BD, TestFn).reduceList(Blocks);
1194     if (Error E = Result.takeError())
1195       return E;
1196     if (Blocks.size() < OldSize)
1197       BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplifycfg");
1198   }
1199
1200   // Attempt to delete instructions using bisection. This should help out nasty
1201   // cases with large basic blocks where the problem is at one end.
1202   if (!BugpointIsInterrupted)
1203     if (Error E = ReduceInsts(BD, TestFn))
1204       return E;
1205
1206   // Attempt to strip debug info metadata.
1207   auto stripMetadata = [&](std::function<bool(Module &)> strip) {
1208     std::unique_ptr<Module> M = CloneModule(BD.getProgram());
1209     strip(*M);
1210     if (TestFn(BD, M.get()))
1211       BD.setNewProgram(std::move(M));
1212   };
1213   if (!NoStripDebugInfo && !BugpointIsInterrupted) {
1214     outs() << "\n*** Attempting to strip the debug info: ";
1215     stripMetadata(StripDebugInfo);
1216   }
1217   if (!NoStripDebugTypeInfo && !BugpointIsInterrupted) {
1218     outs() << "\n*** Attempting to strip the debug type info: ";
1219     stripMetadata(stripNonLineTableDebugInfo);
1220   }
1221
1222   if (!NoNamedMDRM) {
1223     if (!BugpointIsInterrupted) {
1224       // Try to reduce the amount of global metadata (particularly debug info),
1225       // by dropping global named metadata that anchors them
1226       outs() << "\n*** Attempting to remove named metadata: ";
1227       std::vector<std::string> NamedMDNames;
1228       for (auto &NamedMD : BD.getProgram().named_metadata())
1229         NamedMDNames.push_back(NamedMD.getName().str());
1230       Expected<bool> Result =
1231           ReduceCrashingNamedMD(BD, TestFn).reduceList(NamedMDNames);
1232       if (Error E = Result.takeError())
1233         return E;
1234     }
1235
1236     if (!BugpointIsInterrupted) {
1237       // Now that we quickly dropped all the named metadata that doesn't
1238       // contribute to the crash, bisect the operands of the remaining ones
1239       std::vector<const MDNode *> NamedMDOps;
1240       for (auto &NamedMD : BD.getProgram().named_metadata())
1241         for (auto op : NamedMD.operands())
1242           NamedMDOps.push_back(op);
1243       Expected<bool> Result =
1244           ReduceCrashingNamedMDOps(BD, TestFn).reduceList(NamedMDOps);
1245       if (Error E = Result.takeError())
1246         return E;
1247     }
1248     BD.EmitProgressBitcode(BD.getProgram(), "reduced-named-md");
1249   }
1250
1251   // Try to clean up the testcase by running funcresolve and globaldce...
1252   if (!BugpointIsInterrupted) {
1253     outs() << "\n*** Attempting to perform final cleanups: ";
1254     std::unique_ptr<Module> M = CloneModule(BD.getProgram());
1255     M = BD.performFinalCleanups(std::move(M), true);
1256
1257     // Find out if the pass still crashes on the cleaned up program...
1258     if (M && TestFn(BD, M.get()))
1259       BD.setNewProgram(
1260           std::move(M)); // Yup, it does, keep the reduced version...
1261   }
1262
1263   BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplified");
1264
1265   return Error::success();
1266 }
1267
1268 static bool TestForOptimizerCrash(const BugDriver &BD, Module *M) {
1269   return BD.runPasses(*M, BD.getPassesToRun());
1270 }
1271
1272 /// debugOptimizerCrash - This method is called when some pass crashes on input.
1273 /// It attempts to prune down the testcase to something reasonable, and figure
1274 /// out exactly which pass is crashing.
1275 ///
1276 Error BugDriver::debugOptimizerCrash(const std::string &ID) {
1277   outs() << "\n*** Debugging optimizer crash!\n";
1278
1279   // Reduce the list of passes which causes the optimizer to crash...
1280   if (!BugpointIsInterrupted && !DontReducePassList) {
1281     Expected<bool> Result = ReducePassList(*this).reduceList(PassesToRun);
1282     if (Error E = Result.takeError())
1283       return E;
1284   }
1285
1286   outs() << "\n*** Found crashing pass"
1287          << (PassesToRun.size() == 1 ? ": " : "es: ")
1288          << getPassesString(PassesToRun) << '\n';
1289
1290   EmitProgressBitcode(*Program, ID);
1291
1292   return DebugACrash(*this, TestForOptimizerCrash);
1293 }
1294
1295 static bool TestForCodeGenCrash(const BugDriver &BD, Module *M) {
1296   if (Error E = BD.compileProgram(*M)) {
1297     if (VerboseErrors)
1298       errs() << toString(std::move(E)) << "\n";
1299     else {
1300       consumeError(std::move(E));
1301       errs() << "<crash>\n";
1302     }
1303     return true; // Tool is still crashing.
1304   }
1305   errs() << '\n';
1306   return false;
1307 }
1308
1309 /// debugCodeGeneratorCrash - This method is called when the code generator
1310 /// crashes on an input.  It attempts to reduce the input as much as possible
1311 /// while still causing the code generator to crash.
1312 Error BugDriver::debugCodeGeneratorCrash() {
1313   errs() << "*** Debugging code generator crash!\n";
1314
1315   return DebugACrash(*this, TestForCodeGenCrash);
1316 }