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