tools/bugpoint/CrashDebugger.cpp

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