llvm/tools/bugpoint/CrashDebugger.cpp

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