xref: /openbsd-src/gnu/llvm/llvm/tools/bugpoint/CrashDebugger.cpp (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
109467b48Spatrick //===- CrashDebugger.cpp - Debug compilation crashes ----------------------===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick //
909467b48Spatrick // This file defines the bugpoint internals that narrow down compilation crashes
1009467b48Spatrick //
1109467b48Spatrick //===----------------------------------------------------------------------===//
1209467b48Spatrick 
1309467b48Spatrick #include "BugDriver.h"
1409467b48Spatrick #include "ListReducer.h"
1509467b48Spatrick #include "ToolRunner.h"
1609467b48Spatrick #include "llvm/ADT/SmallPtrSet.h"
1709467b48Spatrick #include "llvm/ADT/StringSet.h"
1809467b48Spatrick #include "llvm/Analysis/TargetTransformInfo.h"
1909467b48Spatrick #include "llvm/IR/CFG.h"
2009467b48Spatrick #include "llvm/IR/Constants.h"
2109467b48Spatrick #include "llvm/IR/DebugInfo.h"
2209467b48Spatrick #include "llvm/IR/DerivedTypes.h"
2309467b48Spatrick #include "llvm/IR/InstIterator.h"
2409467b48Spatrick #include "llvm/IR/Instructions.h"
2509467b48Spatrick #include "llvm/IR/LegacyPassManager.h"
2609467b48Spatrick #include "llvm/IR/Module.h"
2709467b48Spatrick #include "llvm/IR/ValueSymbolTable.h"
2809467b48Spatrick #include "llvm/IR/Verifier.h"
2909467b48Spatrick #include "llvm/Pass.h"
3009467b48Spatrick #include "llvm/Support/CommandLine.h"
3109467b48Spatrick #include "llvm/Support/FileUtilities.h"
3209467b48Spatrick #include "llvm/Transforms/Scalar.h"
3309467b48Spatrick #include "llvm/Transforms/Utils/BasicBlockUtils.h"
3409467b48Spatrick #include "llvm/Transforms/Utils/Cloning.h"
3509467b48Spatrick #include "llvm/Transforms/Utils/Local.h"
3609467b48Spatrick #include <set>
3709467b48Spatrick using namespace llvm;
3809467b48Spatrick 
3909467b48Spatrick namespace {
4009467b48Spatrick cl::opt<bool> KeepMain("keep-main",
4109467b48Spatrick                        cl::desc("Force function reduction to keep main"),
4209467b48Spatrick                        cl::init(false));
4309467b48Spatrick cl::opt<bool> NoGlobalRM("disable-global-remove",
4409467b48Spatrick                          cl::desc("Do not remove global variables"),
4509467b48Spatrick                          cl::init(false));
4609467b48Spatrick 
4709467b48Spatrick cl::opt<bool> NoAttributeRM("disable-attribute-remove",
4809467b48Spatrick                          cl::desc("Do not remove function attributes"),
4909467b48Spatrick                          cl::init(false));
5009467b48Spatrick 
5109467b48Spatrick cl::opt<bool> ReplaceFuncsWithNull(
5209467b48Spatrick     "replace-funcs-with-null",
5309467b48Spatrick     cl::desc("When stubbing functions, replace all uses will null"),
5409467b48Spatrick     cl::init(false));
5509467b48Spatrick cl::opt<bool> DontReducePassList("disable-pass-list-reduction",
5609467b48Spatrick                                  cl::desc("Skip pass list reduction steps"),
5709467b48Spatrick                                  cl::init(false));
5809467b48Spatrick 
5909467b48Spatrick cl::opt<bool> NoNamedMDRM("disable-namedmd-remove",
6009467b48Spatrick                           cl::desc("Do not remove global named metadata"),
6109467b48Spatrick                           cl::init(false));
6209467b48Spatrick cl::opt<bool> NoStripDebugInfo("disable-strip-debuginfo",
6309467b48Spatrick                                cl::desc("Do not strip debug info metadata"),
6409467b48Spatrick                                cl::init(false));
6509467b48Spatrick cl::opt<bool> NoStripDebugTypeInfo("disable-strip-debug-types",
6609467b48Spatrick                                cl::desc("Do not strip debug type info metadata"),
6709467b48Spatrick                                cl::init(false));
6809467b48Spatrick cl::opt<bool> VerboseErrors("verbose-errors",
6909467b48Spatrick                             cl::desc("Print the output of crashing program"),
7009467b48Spatrick                             cl::init(false));
7109467b48Spatrick }
7209467b48Spatrick 
7309467b48Spatrick namespace llvm {
7409467b48Spatrick class ReducePassList : public ListReducer<std::string> {
7509467b48Spatrick   BugDriver &BD;
7609467b48Spatrick 
7709467b48Spatrick public:
ReducePassList(BugDriver & bd)7809467b48Spatrick   ReducePassList(BugDriver &bd) : BD(bd) {}
7909467b48Spatrick 
8009467b48Spatrick   // Return true iff running the "removed" passes succeeds, and running the
8109467b48Spatrick   // "Kept" passes fail when run on the output of the "removed" passes.  If we
8209467b48Spatrick   // return true, we update the current module of bugpoint.
8309467b48Spatrick   Expected<TestResult> doTest(std::vector<std::string> &Removed,
8409467b48Spatrick                               std::vector<std::string> &Kept) override;
8509467b48Spatrick };
8609467b48Spatrick }
8709467b48Spatrick 
8809467b48Spatrick Expected<ReducePassList::TestResult>
doTest(std::vector<std::string> & Prefix,std::vector<std::string> & Suffix)8909467b48Spatrick ReducePassList::doTest(std::vector<std::string> &Prefix,
9009467b48Spatrick                        std::vector<std::string> &Suffix) {
9109467b48Spatrick   std::string PrefixOutput;
9209467b48Spatrick   std::unique_ptr<Module> OrigProgram;
9309467b48Spatrick   if (!Prefix.empty()) {
9409467b48Spatrick     outs() << "Checking to see if these passes crash: "
9509467b48Spatrick            << getPassesString(Prefix) << ": ";
9609467b48Spatrick     if (BD.runPasses(BD.getProgram(), Prefix, PrefixOutput))
9709467b48Spatrick       return KeepPrefix;
9809467b48Spatrick 
9909467b48Spatrick     OrigProgram = std::move(BD.Program);
10009467b48Spatrick 
10109467b48Spatrick     BD.Program = parseInputFile(PrefixOutput, BD.getContext());
10209467b48Spatrick     if (BD.Program == nullptr) {
10309467b48Spatrick       errs() << BD.getToolName() << ": Error reading bitcode file '"
10409467b48Spatrick              << PrefixOutput << "'!\n";
10509467b48Spatrick       exit(1);
10609467b48Spatrick     }
10709467b48Spatrick     sys::fs::remove(PrefixOutput);
10809467b48Spatrick   }
10909467b48Spatrick 
11009467b48Spatrick   outs() << "Checking to see if these passes crash: " << getPassesString(Suffix)
11109467b48Spatrick          << ": ";
11209467b48Spatrick 
11309467b48Spatrick   if (BD.runPasses(BD.getProgram(), Suffix))
11409467b48Spatrick     return KeepSuffix; // The suffix crashes alone...
11509467b48Spatrick 
11609467b48Spatrick   // Nothing failed, restore state...
11709467b48Spatrick   if (OrigProgram)
11809467b48Spatrick     BD.Program = std::move(OrigProgram);
11909467b48Spatrick   return NoFailure;
12009467b48Spatrick }
12109467b48Spatrick 
12209467b48Spatrick using BugTester = bool (*)(const BugDriver &, Module *);
12309467b48Spatrick 
12409467b48Spatrick namespace {
12509467b48Spatrick /// ReduceCrashingGlobalInitializers - This works by removing global variable
12609467b48Spatrick /// initializers and seeing if the program still crashes. If it does, then we
12709467b48Spatrick /// keep that program and try again.
12809467b48Spatrick class ReduceCrashingGlobalInitializers : public ListReducer<GlobalVariable *> {
12909467b48Spatrick   BugDriver &BD;
13009467b48Spatrick   BugTester TestFn;
13109467b48Spatrick 
13209467b48Spatrick public:
ReduceCrashingGlobalInitializers(BugDriver & bd,BugTester testFn)13309467b48Spatrick   ReduceCrashingGlobalInitializers(BugDriver &bd, BugTester testFn)
13409467b48Spatrick       : BD(bd), TestFn(testFn) {}
13509467b48Spatrick 
doTest(std::vector<GlobalVariable * > & Prefix,std::vector<GlobalVariable * > & Kept)13609467b48Spatrick   Expected<TestResult> doTest(std::vector<GlobalVariable *> &Prefix,
13709467b48Spatrick                               std::vector<GlobalVariable *> &Kept) override {
13809467b48Spatrick     if (!Kept.empty() && TestGlobalVariables(Kept))
13909467b48Spatrick       return KeepSuffix;
14009467b48Spatrick     if (!Prefix.empty() && TestGlobalVariables(Prefix))
14109467b48Spatrick       return KeepPrefix;
14209467b48Spatrick     return NoFailure;
14309467b48Spatrick   }
14409467b48Spatrick 
14509467b48Spatrick   bool TestGlobalVariables(std::vector<GlobalVariable *> &GVs);
14609467b48Spatrick };
14709467b48Spatrick }
14809467b48Spatrick 
TestGlobalVariables(std::vector<GlobalVariable * > & GVs)14909467b48Spatrick bool ReduceCrashingGlobalInitializers::TestGlobalVariables(
15009467b48Spatrick     std::vector<GlobalVariable *> &GVs) {
15109467b48Spatrick   // Clone the program to try hacking it apart...
15209467b48Spatrick   ValueToValueMapTy VMap;
15309467b48Spatrick   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
15409467b48Spatrick 
15509467b48Spatrick   // Convert list to set for fast lookup...
15609467b48Spatrick   std::set<GlobalVariable *> GVSet;
15709467b48Spatrick 
15809467b48Spatrick   for (unsigned i = 0, e = GVs.size(); i != e; ++i) {
15909467b48Spatrick     GlobalVariable *CMGV = cast<GlobalVariable>(VMap[GVs[i]]);
16009467b48Spatrick     assert(CMGV && "Global Variable not in module?!");
16109467b48Spatrick     GVSet.insert(CMGV);
16209467b48Spatrick   }
16309467b48Spatrick 
16409467b48Spatrick   outs() << "Checking for crash with only these global variables: ";
16509467b48Spatrick   PrintGlobalVariableList(GVs);
16609467b48Spatrick   outs() << ": ";
16709467b48Spatrick 
16809467b48Spatrick   // Loop over and delete any global variables which we aren't supposed to be
16909467b48Spatrick   // playing with...
17009467b48Spatrick   for (GlobalVariable &I : M->globals())
17109467b48Spatrick     if (I.hasInitializer() && !GVSet.count(&I)) {
17209467b48Spatrick       DeleteGlobalInitializer(&I);
17309467b48Spatrick       I.setLinkage(GlobalValue::ExternalLinkage);
17409467b48Spatrick       I.setComdat(nullptr);
17509467b48Spatrick     }
17609467b48Spatrick 
17709467b48Spatrick   // Try running the hacked up program...
17809467b48Spatrick   if (TestFn(BD, M.get())) {
17909467b48Spatrick     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
18009467b48Spatrick 
18109467b48Spatrick     // Make sure to use global variable pointers that point into the now-current
18209467b48Spatrick     // module.
18309467b48Spatrick     GVs.assign(GVSet.begin(), GVSet.end());
18409467b48Spatrick     return true;
18509467b48Spatrick   }
18609467b48Spatrick 
18709467b48Spatrick   return false;
18809467b48Spatrick }
18909467b48Spatrick 
19009467b48Spatrick namespace {
19109467b48Spatrick /// ReduceCrashingFunctions reducer - This works by removing functions and
19209467b48Spatrick /// seeing if the program still crashes. If it does, then keep the newer,
19309467b48Spatrick /// smaller program.
19409467b48Spatrick ///
19509467b48Spatrick class ReduceCrashingFunctions : public ListReducer<Function *> {
19609467b48Spatrick   BugDriver &BD;
19709467b48Spatrick   BugTester TestFn;
19809467b48Spatrick 
19909467b48Spatrick public:
ReduceCrashingFunctions(BugDriver & bd,BugTester testFn)20009467b48Spatrick   ReduceCrashingFunctions(BugDriver &bd, BugTester testFn)
20109467b48Spatrick       : BD(bd), TestFn(testFn) {}
20209467b48Spatrick 
doTest(std::vector<Function * > & Prefix,std::vector<Function * > & Kept)20309467b48Spatrick   Expected<TestResult> doTest(std::vector<Function *> &Prefix,
20409467b48Spatrick                               std::vector<Function *> &Kept) override {
20509467b48Spatrick     if (!Kept.empty() && TestFuncs(Kept))
20609467b48Spatrick       return KeepSuffix;
20709467b48Spatrick     if (!Prefix.empty() && TestFuncs(Prefix))
20809467b48Spatrick       return KeepPrefix;
20909467b48Spatrick     return NoFailure;
21009467b48Spatrick   }
21109467b48Spatrick 
21209467b48Spatrick   bool TestFuncs(std::vector<Function *> &Prefix);
21309467b48Spatrick };
21409467b48Spatrick }
21509467b48Spatrick 
RemoveFunctionReferences(Module * M,const char * Name)21609467b48Spatrick static void RemoveFunctionReferences(Module *M, const char *Name) {
21709467b48Spatrick   auto *UsedVar = M->getGlobalVariable(Name, true);
21809467b48Spatrick   if (!UsedVar || !UsedVar->hasInitializer())
21909467b48Spatrick     return;
22009467b48Spatrick   if (isa<ConstantAggregateZero>(UsedVar->getInitializer())) {
22109467b48Spatrick     assert(UsedVar->use_empty());
22209467b48Spatrick     UsedVar->eraseFromParent();
22309467b48Spatrick     return;
22409467b48Spatrick   }
22509467b48Spatrick   auto *OldUsedVal = cast<ConstantArray>(UsedVar->getInitializer());
22609467b48Spatrick   std::vector<Constant *> Used;
22709467b48Spatrick   for (Value *V : OldUsedVal->operand_values()) {
22809467b48Spatrick     Constant *Op = cast<Constant>(V->stripPointerCasts());
22909467b48Spatrick     if (!Op->isNullValue()) {
23009467b48Spatrick       Used.push_back(cast<Constant>(V));
23109467b48Spatrick     }
23209467b48Spatrick   }
23309467b48Spatrick   auto *NewValElemTy = OldUsedVal->getType()->getElementType();
23409467b48Spatrick   auto *NewValTy = ArrayType::get(NewValElemTy, Used.size());
23509467b48Spatrick   auto *NewUsedVal = ConstantArray::get(NewValTy, Used);
23609467b48Spatrick   UsedVar->mutateType(NewUsedVal->getType()->getPointerTo());
23709467b48Spatrick   UsedVar->setInitializer(NewUsedVal);
23809467b48Spatrick }
23909467b48Spatrick 
TestFuncs(std::vector<Function * > & Funcs)24009467b48Spatrick bool ReduceCrashingFunctions::TestFuncs(std::vector<Function *> &Funcs) {
24109467b48Spatrick   // If main isn't present, claim there is no problem.
24209467b48Spatrick   if (KeepMain && !is_contained(Funcs, BD.getProgram().getFunction("main")))
24309467b48Spatrick     return false;
24409467b48Spatrick 
24509467b48Spatrick   // Clone the program to try hacking it apart...
24609467b48Spatrick   ValueToValueMapTy VMap;
24709467b48Spatrick   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
24809467b48Spatrick 
24909467b48Spatrick   // Convert list to set for fast lookup...
25009467b48Spatrick   std::set<Function *> Functions;
25109467b48Spatrick   for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
25209467b48Spatrick     Function *CMF = cast<Function>(VMap[Funcs[i]]);
25309467b48Spatrick     assert(CMF && "Function not in module?!");
25409467b48Spatrick     assert(CMF->getFunctionType() == Funcs[i]->getFunctionType() && "wrong ty");
25509467b48Spatrick     assert(CMF->getName() == Funcs[i]->getName() && "wrong name");
25609467b48Spatrick     Functions.insert(CMF);
25709467b48Spatrick   }
25809467b48Spatrick 
25909467b48Spatrick   outs() << "Checking for crash with only these functions: ";
26009467b48Spatrick   PrintFunctionList(Funcs);
26109467b48Spatrick   outs() << ": ";
26209467b48Spatrick   if (!ReplaceFuncsWithNull) {
26309467b48Spatrick     // Loop over and delete any functions which we aren't supposed to be playing
26409467b48Spatrick     // with...
26509467b48Spatrick     for (Function &I : *M)
26609467b48Spatrick       if (!I.isDeclaration() && !Functions.count(&I))
26709467b48Spatrick         DeleteFunctionBody(&I);
26809467b48Spatrick   } else {
26909467b48Spatrick     std::vector<GlobalValue *> ToRemove;
27009467b48Spatrick     // First, remove aliases to functions we're about to purge.
27109467b48Spatrick     for (GlobalAlias &Alias : M->aliases()) {
272*d415bd75Srobert       GlobalObject *Root = Alias.getAliaseeObject();
273*d415bd75Srobert       auto *F = dyn_cast<Function>(Root);
27409467b48Spatrick       if (F) {
27509467b48Spatrick         if (Functions.count(F))
27609467b48Spatrick           // We're keeping this function.
27709467b48Spatrick           continue;
27809467b48Spatrick       } else if (Root->isNullValue()) {
27909467b48Spatrick         // This referenced a globalalias that we've already replaced,
28009467b48Spatrick         // so we still need to replace this alias.
281*d415bd75Srobert       } else {
28209467b48Spatrick         // Not a function, therefore not something we mess with.
28309467b48Spatrick         continue;
28409467b48Spatrick       }
28509467b48Spatrick 
28609467b48Spatrick       PointerType *Ty = cast<PointerType>(Alias.getType());
28709467b48Spatrick       Constant *Replacement = ConstantPointerNull::get(Ty);
28809467b48Spatrick       Alias.replaceAllUsesWith(Replacement);
28909467b48Spatrick       ToRemove.push_back(&Alias);
29009467b48Spatrick     }
29109467b48Spatrick 
29209467b48Spatrick     for (Function &I : *M) {
29309467b48Spatrick       if (!I.isDeclaration() && !Functions.count(&I)) {
29409467b48Spatrick         PointerType *Ty = cast<PointerType>(I.getType());
29509467b48Spatrick         Constant *Replacement = ConstantPointerNull::get(Ty);
29609467b48Spatrick         I.replaceAllUsesWith(Replacement);
29709467b48Spatrick         ToRemove.push_back(&I);
29809467b48Spatrick       }
29909467b48Spatrick     }
30009467b48Spatrick 
30109467b48Spatrick     for (auto *F : ToRemove) {
30209467b48Spatrick       F->eraseFromParent();
30309467b48Spatrick     }
30409467b48Spatrick 
30509467b48Spatrick     // Finally, remove any null members from any global intrinsic.
30609467b48Spatrick     RemoveFunctionReferences(M.get(), "llvm.used");
30709467b48Spatrick     RemoveFunctionReferences(M.get(), "llvm.compiler.used");
30809467b48Spatrick   }
30909467b48Spatrick   // Try running the hacked up program...
31009467b48Spatrick   if (TestFn(BD, M.get())) {
31109467b48Spatrick     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
31209467b48Spatrick 
31309467b48Spatrick     // Make sure to use function pointers that point into the now-current
31409467b48Spatrick     // module.
31509467b48Spatrick     Funcs.assign(Functions.begin(), Functions.end());
31609467b48Spatrick     return true;
31709467b48Spatrick   }
31809467b48Spatrick   return false;
31909467b48Spatrick }
32009467b48Spatrick 
32109467b48Spatrick namespace {
32209467b48Spatrick /// ReduceCrashingFunctionAttributes reducer - This works by removing
32309467b48Spatrick /// attributes on a particular function and seeing if the program still crashes.
32409467b48Spatrick /// If it does, then keep the newer, smaller program.
32509467b48Spatrick ///
32609467b48Spatrick class ReduceCrashingFunctionAttributes : public ListReducer<Attribute> {
32709467b48Spatrick   BugDriver &BD;
32809467b48Spatrick   std::string FnName;
32909467b48Spatrick   BugTester TestFn;
33009467b48Spatrick 
33109467b48Spatrick public:
ReduceCrashingFunctionAttributes(BugDriver & bd,const std::string & FnName,BugTester testFn)33209467b48Spatrick   ReduceCrashingFunctionAttributes(BugDriver &bd, const std::string &FnName,
33309467b48Spatrick                                    BugTester testFn)
33409467b48Spatrick       : BD(bd), FnName(FnName), TestFn(testFn) {}
33509467b48Spatrick 
doTest(std::vector<Attribute> & Prefix,std::vector<Attribute> & Kept)33609467b48Spatrick   Expected<TestResult> doTest(std::vector<Attribute> &Prefix,
33709467b48Spatrick                               std::vector<Attribute> &Kept) override {
33809467b48Spatrick     if (!Kept.empty() && TestFuncAttrs(Kept))
33909467b48Spatrick       return KeepSuffix;
34009467b48Spatrick     if (!Prefix.empty() && TestFuncAttrs(Prefix))
34109467b48Spatrick       return KeepPrefix;
34209467b48Spatrick     return NoFailure;
34309467b48Spatrick   }
34409467b48Spatrick 
34509467b48Spatrick   bool TestFuncAttrs(std::vector<Attribute> &Attrs);
34609467b48Spatrick };
34709467b48Spatrick }
34809467b48Spatrick 
TestFuncAttrs(std::vector<Attribute> & Attrs)34909467b48Spatrick bool ReduceCrashingFunctionAttributes::TestFuncAttrs(
35009467b48Spatrick     std::vector<Attribute> &Attrs) {
35109467b48Spatrick   // Clone the program to try hacking it apart...
35209467b48Spatrick   std::unique_ptr<Module> M = CloneModule(BD.getProgram());
35309467b48Spatrick   Function *F = M->getFunction(FnName);
35409467b48Spatrick 
35509467b48Spatrick   // Build up an AttributeList from the attributes we've been given by the
35609467b48Spatrick   // reducer.
357*d415bd75Srobert   AttrBuilder AB(M->getContext());
35809467b48Spatrick   for (auto A : Attrs)
35909467b48Spatrick     AB.addAttribute(A);
36009467b48Spatrick   AttributeList NewAttrs;
361*d415bd75Srobert   NewAttrs = NewAttrs.addFnAttributes(BD.getContext(), AB);
36209467b48Spatrick 
36309467b48Spatrick   // Set this new list of attributes on the function.
36409467b48Spatrick   F->setAttributes(NewAttrs);
36509467b48Spatrick 
36609467b48Spatrick   // If the attribute list includes "optnone" we need to make sure it also
36709467b48Spatrick   // includes "noinline" otherwise we will get a verifier failure.
36809467b48Spatrick   if (F->hasFnAttribute(Attribute::OptimizeNone))
36909467b48Spatrick     F->addFnAttr(Attribute::NoInline);
37009467b48Spatrick 
37109467b48Spatrick   // Try running on the hacked up program...
37209467b48Spatrick   if (TestFn(BD, M.get())) {
37309467b48Spatrick     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
37409467b48Spatrick 
37509467b48Spatrick     // Pass along the set of attributes that caused the crash.
37609467b48Spatrick     Attrs.clear();
377*d415bd75Srobert     for (Attribute A : NewAttrs.getFnAttrs()) {
37809467b48Spatrick       Attrs.push_back(A);
37909467b48Spatrick     }
38009467b48Spatrick     return true;
38109467b48Spatrick   }
38209467b48Spatrick   return false;
38309467b48Spatrick }
38409467b48Spatrick 
38509467b48Spatrick namespace {
38609467b48Spatrick /// Simplify the CFG without completely destroying it.
38709467b48Spatrick /// This is not well defined, but basically comes down to "try to eliminate
38809467b48Spatrick /// unreachable blocks and constant fold terminators without deciding that
38909467b48Spatrick /// certain undefined behavior cuts off the program at the legs".
simpleSimplifyCfg(Function & F,SmallVectorImpl<BasicBlock * > & BBs)39009467b48Spatrick void simpleSimplifyCfg(Function &F, SmallVectorImpl<BasicBlock *> &BBs) {
39109467b48Spatrick   if (F.empty())
39209467b48Spatrick     return;
39309467b48Spatrick 
39409467b48Spatrick   for (auto *BB : BBs) {
39509467b48Spatrick     ConstantFoldTerminator(BB);
39609467b48Spatrick     MergeBlockIntoPredecessor(BB);
39709467b48Spatrick   }
39809467b48Spatrick 
39909467b48Spatrick   // Remove unreachable blocks
40009467b48Spatrick   // removeUnreachableBlocks can't be used here, it will turn various
40109467b48Spatrick   // undefined behavior into unreachables, but bugpoint was the thing that
40209467b48Spatrick   // generated the undefined behavior, and we don't want it to kill the entire
40309467b48Spatrick   // program.
40409467b48Spatrick   SmallPtrSet<BasicBlock *, 16> Visited;
40509467b48Spatrick   for (auto *BB : depth_first(&F.getEntryBlock()))
40609467b48Spatrick     Visited.insert(BB);
40709467b48Spatrick 
40809467b48Spatrick   SmallVector<BasicBlock *, 16> Unreachable;
40909467b48Spatrick   for (auto &BB : F)
41009467b48Spatrick     if (!Visited.count(&BB))
41109467b48Spatrick       Unreachable.push_back(&BB);
41209467b48Spatrick 
41309467b48Spatrick   // The dead BB's may be in a dead cycle or otherwise have references to each
41409467b48Spatrick   // other.  Because of this, we have to drop all references first, then delete
41509467b48Spatrick   // them all at once.
41609467b48Spatrick   for (auto *BB : Unreachable) {
41709467b48Spatrick     for (BasicBlock *Successor : successors(&*BB))
41809467b48Spatrick       if (Visited.count(Successor))
41909467b48Spatrick         Successor->removePredecessor(&*BB);
42009467b48Spatrick     BB->dropAllReferences();
42109467b48Spatrick   }
42209467b48Spatrick   for (auto *BB : Unreachable)
42309467b48Spatrick     BB->eraseFromParent();
42409467b48Spatrick }
42509467b48Spatrick /// ReduceCrashingBlocks reducer - This works by setting the terminators of
42609467b48Spatrick /// all terminators except the specified basic blocks to a 'ret' instruction,
42773471bf0Spatrick /// then running the simplifycfg pass.  This has the effect of chopping up
42809467b48Spatrick /// the CFG really fast which can reduce large functions quickly.
42909467b48Spatrick ///
43009467b48Spatrick class ReduceCrashingBlocks : public ListReducer<const BasicBlock *> {
43109467b48Spatrick   BugDriver &BD;
43209467b48Spatrick   BugTester TestFn;
43309467b48Spatrick 
43409467b48Spatrick public:
ReduceCrashingBlocks(BugDriver & BD,BugTester testFn)43509467b48Spatrick   ReduceCrashingBlocks(BugDriver &BD, BugTester testFn)
43609467b48Spatrick       : BD(BD), TestFn(testFn) {}
43709467b48Spatrick 
doTest(std::vector<const BasicBlock * > & Prefix,std::vector<const BasicBlock * > & Kept)43809467b48Spatrick   Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
43909467b48Spatrick                               std::vector<const BasicBlock *> &Kept) override {
44009467b48Spatrick     if (!Kept.empty() && TestBlocks(Kept))
44109467b48Spatrick       return KeepSuffix;
44209467b48Spatrick     if (!Prefix.empty() && TestBlocks(Prefix))
44309467b48Spatrick       return KeepPrefix;
44409467b48Spatrick     return NoFailure;
44509467b48Spatrick   }
44609467b48Spatrick 
44709467b48Spatrick   bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
44809467b48Spatrick };
44909467b48Spatrick }
45009467b48Spatrick 
TestBlocks(std::vector<const BasicBlock * > & BBs)45109467b48Spatrick bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock *> &BBs) {
45209467b48Spatrick   // Clone the program to try hacking it apart...
45309467b48Spatrick   ValueToValueMapTy VMap;
45409467b48Spatrick   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
45509467b48Spatrick 
45609467b48Spatrick   // Convert list to set for fast lookup...
45709467b48Spatrick   SmallPtrSet<BasicBlock *, 8> Blocks;
45809467b48Spatrick   for (unsigned i = 0, e = BBs.size(); i != e; ++i)
45909467b48Spatrick     Blocks.insert(cast<BasicBlock>(VMap[BBs[i]]));
46009467b48Spatrick 
46109467b48Spatrick   outs() << "Checking for crash with only these blocks:";
46209467b48Spatrick   unsigned NumPrint = Blocks.size();
46309467b48Spatrick   if (NumPrint > 10)
46409467b48Spatrick     NumPrint = 10;
46509467b48Spatrick   for (unsigned i = 0, e = NumPrint; i != e; ++i)
46609467b48Spatrick     outs() << " " << BBs[i]->getName();
46709467b48Spatrick   if (NumPrint < Blocks.size())
46809467b48Spatrick     outs() << "... <" << Blocks.size() << " total>";
46909467b48Spatrick   outs() << ": ";
47009467b48Spatrick 
47109467b48Spatrick   // Loop over and delete any hack up any blocks that are not listed...
47209467b48Spatrick   for (Function &F : M->functions()) {
47309467b48Spatrick     for (BasicBlock &BB : F) {
47409467b48Spatrick       if (!Blocks.count(&BB) && BB.getTerminator()->getNumSuccessors()) {
47509467b48Spatrick         // Loop over all of the successors of this block, deleting any PHI nodes
47609467b48Spatrick         // that might include it.
47709467b48Spatrick         for (BasicBlock *Succ : successors(&BB))
47809467b48Spatrick           Succ->removePredecessor(&BB);
47909467b48Spatrick 
48009467b48Spatrick         Instruction *BBTerm = BB.getTerminator();
48109467b48Spatrick         if (BBTerm->isEHPad() || BBTerm->getType()->isTokenTy())
48209467b48Spatrick           continue;
48309467b48Spatrick         if (!BBTerm->getType()->isVoidTy())
48409467b48Spatrick           BBTerm->replaceAllUsesWith(Constant::getNullValue(BBTerm->getType()));
48509467b48Spatrick 
48609467b48Spatrick         // Replace the old terminator instruction.
487*d415bd75Srobert         BB.back().eraseFromParent();
48809467b48Spatrick         new UnreachableInst(BB.getContext(), &BB);
48909467b48Spatrick       }
49009467b48Spatrick     }
49109467b48Spatrick   }
49209467b48Spatrick 
49309467b48Spatrick   // The CFG Simplifier pass may delete one of the basic blocks we are
49409467b48Spatrick   // interested in.  If it does we need to take the block out of the list.  Make
49509467b48Spatrick   // a "persistent mapping" by turning basic blocks into <function, name> pairs.
49609467b48Spatrick   // This won't work well if blocks are unnamed, but that is just the risk we
49709467b48Spatrick   // have to take. FIXME: Can we just name the blocks?
49809467b48Spatrick   std::vector<std::pair<std::string, std::string>> BlockInfo;
49909467b48Spatrick 
50009467b48Spatrick   for (BasicBlock *BB : Blocks)
501097a140dSpatrick     BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
502097a140dSpatrick                            std::string(BB->getName()));
50309467b48Spatrick 
50409467b48Spatrick   SmallVector<BasicBlock *, 16> ToProcess;
50509467b48Spatrick   for (auto &F : *M) {
50609467b48Spatrick     for (auto &BB : F)
50709467b48Spatrick       if (!Blocks.count(&BB))
50809467b48Spatrick         ToProcess.push_back(&BB);
50909467b48Spatrick     simpleSimplifyCfg(F, ToProcess);
51009467b48Spatrick     ToProcess.clear();
51109467b48Spatrick   }
51209467b48Spatrick   // Verify we didn't break anything
51309467b48Spatrick   std::vector<std::string> Passes;
51409467b48Spatrick   Passes.push_back("verify");
51509467b48Spatrick   std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
51609467b48Spatrick   if (!New) {
51709467b48Spatrick     errs() << "verify failed!\n";
51809467b48Spatrick     exit(1);
51909467b48Spatrick   }
52009467b48Spatrick   M = std::move(New);
52109467b48Spatrick 
52209467b48Spatrick   // Try running on the hacked up program...
52309467b48Spatrick   if (TestFn(BD, M.get())) {
52409467b48Spatrick     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
52509467b48Spatrick 
52609467b48Spatrick     // Make sure to use basic block pointers that point into the now-current
52709467b48Spatrick     // module, and that they don't include any deleted blocks.
52809467b48Spatrick     BBs.clear();
52909467b48Spatrick     const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
53009467b48Spatrick     for (const auto &BI : BlockInfo) {
53109467b48Spatrick       Function *F = cast<Function>(GST.lookup(BI.first));
53209467b48Spatrick       Value *V = F->getValueSymbolTable()->lookup(BI.second);
53309467b48Spatrick       if (V && V->getType() == Type::getLabelTy(V->getContext()))
53409467b48Spatrick         BBs.push_back(cast<BasicBlock>(V));
53509467b48Spatrick     }
53609467b48Spatrick     return true;
53709467b48Spatrick   }
53809467b48Spatrick   // It didn't crash, try something else.
53909467b48Spatrick   return false;
54009467b48Spatrick }
54109467b48Spatrick 
54209467b48Spatrick namespace {
54309467b48Spatrick /// ReduceCrashingConditionals reducer - This works by changing
54409467b48Spatrick /// conditional branches to unconditional ones, then simplifying the CFG
54509467b48Spatrick /// This has the effect of chopping up the CFG really fast which can reduce
54609467b48Spatrick /// large functions quickly.
54709467b48Spatrick ///
54809467b48Spatrick class ReduceCrashingConditionals : public ListReducer<const BasicBlock *> {
54909467b48Spatrick   BugDriver &BD;
55009467b48Spatrick   BugTester TestFn;
55109467b48Spatrick   bool Direction;
55209467b48Spatrick 
55309467b48Spatrick public:
ReduceCrashingConditionals(BugDriver & bd,BugTester testFn,bool Direction)55409467b48Spatrick   ReduceCrashingConditionals(BugDriver &bd, BugTester testFn, bool Direction)
55509467b48Spatrick       : BD(bd), TestFn(testFn), Direction(Direction) {}
55609467b48Spatrick 
doTest(std::vector<const BasicBlock * > & Prefix,std::vector<const BasicBlock * > & Kept)55709467b48Spatrick   Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
55809467b48Spatrick                               std::vector<const BasicBlock *> &Kept) override {
55909467b48Spatrick     if (!Kept.empty() && TestBlocks(Kept))
56009467b48Spatrick       return KeepSuffix;
56109467b48Spatrick     if (!Prefix.empty() && TestBlocks(Prefix))
56209467b48Spatrick       return KeepPrefix;
56309467b48Spatrick     return NoFailure;
56409467b48Spatrick   }
56509467b48Spatrick 
56609467b48Spatrick   bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
56709467b48Spatrick };
56809467b48Spatrick }
56909467b48Spatrick 
TestBlocks(std::vector<const BasicBlock * > & BBs)57009467b48Spatrick bool ReduceCrashingConditionals::TestBlocks(
57109467b48Spatrick     std::vector<const BasicBlock *> &BBs) {
57209467b48Spatrick   // Clone the program to try hacking it apart...
57309467b48Spatrick   ValueToValueMapTy VMap;
57409467b48Spatrick   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
57509467b48Spatrick 
57609467b48Spatrick   // Convert list to set for fast lookup...
57709467b48Spatrick   SmallPtrSet<const BasicBlock *, 8> Blocks;
57809467b48Spatrick   for (const auto *BB : BBs)
57909467b48Spatrick     Blocks.insert(cast<BasicBlock>(VMap[BB]));
58009467b48Spatrick 
58109467b48Spatrick   outs() << "Checking for crash with changing conditionals to always jump to "
58209467b48Spatrick          << (Direction ? "true" : "false") << ":";
58309467b48Spatrick   unsigned NumPrint = Blocks.size();
58409467b48Spatrick   if (NumPrint > 10)
58509467b48Spatrick     NumPrint = 10;
58609467b48Spatrick   for (unsigned i = 0, e = NumPrint; i != e; ++i)
58709467b48Spatrick     outs() << " " << BBs[i]->getName();
58809467b48Spatrick   if (NumPrint < Blocks.size())
58909467b48Spatrick     outs() << "... <" << Blocks.size() << " total>";
59009467b48Spatrick   outs() << ": ";
59109467b48Spatrick 
59209467b48Spatrick   // Loop over and delete any hack up any blocks that are not listed...
59309467b48Spatrick   for (auto &F : *M)
59409467b48Spatrick     for (auto &BB : F)
59509467b48Spatrick       if (!Blocks.count(&BB)) {
59609467b48Spatrick         auto *BR = dyn_cast<BranchInst>(BB.getTerminator());
59709467b48Spatrick         if (!BR || !BR->isConditional())
59809467b48Spatrick           continue;
59909467b48Spatrick         if (Direction)
60009467b48Spatrick           BR->setCondition(ConstantInt::getTrue(BR->getContext()));
60109467b48Spatrick         else
60209467b48Spatrick           BR->setCondition(ConstantInt::getFalse(BR->getContext()));
60309467b48Spatrick       }
60409467b48Spatrick 
60509467b48Spatrick   // The following may destroy some blocks, so we save them first
60609467b48Spatrick   std::vector<std::pair<std::string, std::string>> BlockInfo;
60709467b48Spatrick 
60809467b48Spatrick   for (const BasicBlock *BB : Blocks)
609097a140dSpatrick     BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
610097a140dSpatrick                            std::string(BB->getName()));
61109467b48Spatrick 
61209467b48Spatrick   SmallVector<BasicBlock *, 16> ToProcess;
61309467b48Spatrick   for (auto &F : *M) {
61409467b48Spatrick     for (auto &BB : F)
61509467b48Spatrick       if (!Blocks.count(&BB))
61609467b48Spatrick         ToProcess.push_back(&BB);
61709467b48Spatrick     simpleSimplifyCfg(F, ToProcess);
61809467b48Spatrick     ToProcess.clear();
61909467b48Spatrick   }
62009467b48Spatrick   // Verify we didn't break anything
62109467b48Spatrick   std::vector<std::string> Passes;
62209467b48Spatrick   Passes.push_back("verify");
62309467b48Spatrick   std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
62409467b48Spatrick   if (!New) {
62509467b48Spatrick     errs() << "verify failed!\n";
62609467b48Spatrick     exit(1);
62709467b48Spatrick   }
62809467b48Spatrick   M = std::move(New);
62909467b48Spatrick 
63009467b48Spatrick   // Try running on the hacked up program...
63109467b48Spatrick   if (TestFn(BD, M.get())) {
63209467b48Spatrick     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
63309467b48Spatrick 
63409467b48Spatrick     // Make sure to use basic block pointers that point into the now-current
63509467b48Spatrick     // module, and that they don't include any deleted blocks.
63609467b48Spatrick     BBs.clear();
63709467b48Spatrick     const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
63809467b48Spatrick     for (auto &BI : BlockInfo) {
63909467b48Spatrick       auto *F = cast<Function>(GST.lookup(BI.first));
64009467b48Spatrick       Value *V = F->getValueSymbolTable()->lookup(BI.second);
64109467b48Spatrick       if (V && V->getType() == Type::getLabelTy(V->getContext()))
64209467b48Spatrick         BBs.push_back(cast<BasicBlock>(V));
64309467b48Spatrick     }
64409467b48Spatrick     return true;
64509467b48Spatrick   }
64609467b48Spatrick   // It didn't crash, try something else.
64709467b48Spatrick   return false;
64809467b48Spatrick }
64909467b48Spatrick 
65009467b48Spatrick namespace {
65109467b48Spatrick /// SimplifyCFG reducer - This works by calling SimplifyCFG on each basic block
65209467b48Spatrick /// in the program.
65309467b48Spatrick 
65409467b48Spatrick class ReduceSimplifyCFG : public ListReducer<const BasicBlock *> {
65509467b48Spatrick   BugDriver &BD;
65609467b48Spatrick   BugTester TestFn;
65709467b48Spatrick   TargetTransformInfo TTI;
65809467b48Spatrick 
65909467b48Spatrick public:
ReduceSimplifyCFG(BugDriver & bd,BugTester testFn)66009467b48Spatrick   ReduceSimplifyCFG(BugDriver &bd, BugTester testFn)
66109467b48Spatrick       : BD(bd), TestFn(testFn), TTI(bd.getProgram().getDataLayout()) {}
66209467b48Spatrick 
doTest(std::vector<const BasicBlock * > & Prefix,std::vector<const BasicBlock * > & Kept)66309467b48Spatrick   Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
66409467b48Spatrick                               std::vector<const BasicBlock *> &Kept) override {
66509467b48Spatrick     if (!Kept.empty() && TestBlocks(Kept))
66609467b48Spatrick       return KeepSuffix;
66709467b48Spatrick     if (!Prefix.empty() && TestBlocks(Prefix))
66809467b48Spatrick       return KeepPrefix;
66909467b48Spatrick     return NoFailure;
67009467b48Spatrick   }
67109467b48Spatrick 
67209467b48Spatrick   bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
67309467b48Spatrick };
67409467b48Spatrick }
67509467b48Spatrick 
TestBlocks(std::vector<const BasicBlock * > & BBs)67609467b48Spatrick bool ReduceSimplifyCFG::TestBlocks(std::vector<const BasicBlock *> &BBs) {
67709467b48Spatrick   // Clone the program to try hacking it apart...
67809467b48Spatrick   ValueToValueMapTy VMap;
67909467b48Spatrick   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
68009467b48Spatrick 
68109467b48Spatrick   // Convert list to set for fast lookup...
68209467b48Spatrick   SmallPtrSet<const BasicBlock *, 8> Blocks;
68309467b48Spatrick   for (const auto *BB : BBs)
68409467b48Spatrick     Blocks.insert(cast<BasicBlock>(VMap[BB]));
68509467b48Spatrick 
68609467b48Spatrick   outs() << "Checking for crash with CFG simplifying:";
68709467b48Spatrick   unsigned NumPrint = Blocks.size();
68809467b48Spatrick   if (NumPrint > 10)
68909467b48Spatrick     NumPrint = 10;
69009467b48Spatrick   for (unsigned i = 0, e = NumPrint; i != e; ++i)
69109467b48Spatrick     outs() << " " << BBs[i]->getName();
69209467b48Spatrick   if (NumPrint < Blocks.size())
69309467b48Spatrick     outs() << "... <" << Blocks.size() << " total>";
69409467b48Spatrick   outs() << ": ";
69509467b48Spatrick 
69609467b48Spatrick   // The following may destroy some blocks, so we save them first
69709467b48Spatrick   std::vector<std::pair<std::string, std::string>> BlockInfo;
69809467b48Spatrick 
69909467b48Spatrick   for (const BasicBlock *BB : Blocks)
700097a140dSpatrick     BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
701097a140dSpatrick                            std::string(BB->getName()));
70209467b48Spatrick 
70309467b48Spatrick   // Loop over and delete any hack up any blocks that are not listed...
70409467b48Spatrick   for (auto &F : *M)
70509467b48Spatrick     // Loop over all of the basic blocks and remove them if they are unneeded.
70609467b48Spatrick     for (Function::iterator BBIt = F.begin(); BBIt != F.end();) {
70709467b48Spatrick       if (!Blocks.count(&*BBIt)) {
70809467b48Spatrick         ++BBIt;
70909467b48Spatrick         continue;
71009467b48Spatrick       }
71109467b48Spatrick       simplifyCFG(&*BBIt++, TTI);
71209467b48Spatrick     }
71309467b48Spatrick   // Verify we didn't break anything
71409467b48Spatrick   std::vector<std::string> Passes;
71509467b48Spatrick   Passes.push_back("verify");
71609467b48Spatrick   std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
71709467b48Spatrick   if (!New) {
71809467b48Spatrick     errs() << "verify failed!\n";
71909467b48Spatrick     exit(1);
72009467b48Spatrick   }
72109467b48Spatrick   M = std::move(New);
72209467b48Spatrick 
72309467b48Spatrick   // Try running on the hacked up program...
72409467b48Spatrick   if (TestFn(BD, M.get())) {
72509467b48Spatrick     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
72609467b48Spatrick 
72709467b48Spatrick     // Make sure to use basic block pointers that point into the now-current
72809467b48Spatrick     // module, and that they don't include any deleted blocks.
72909467b48Spatrick     BBs.clear();
73009467b48Spatrick     const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
73109467b48Spatrick     for (auto &BI : BlockInfo) {
73209467b48Spatrick       auto *F = cast<Function>(GST.lookup(BI.first));
73309467b48Spatrick       Value *V = F->getValueSymbolTable()->lookup(BI.second);
73409467b48Spatrick       if (V && V->getType() == Type::getLabelTy(V->getContext()))
73509467b48Spatrick         BBs.push_back(cast<BasicBlock>(V));
73609467b48Spatrick     }
73709467b48Spatrick     return true;
73809467b48Spatrick   }
73909467b48Spatrick   // It didn't crash, try something else.
74009467b48Spatrick   return false;
74109467b48Spatrick }
74209467b48Spatrick 
74309467b48Spatrick namespace {
74409467b48Spatrick /// ReduceCrashingInstructions reducer - This works by removing the specified
74509467b48Spatrick /// non-terminator instructions and replacing them with undef.
74609467b48Spatrick ///
74709467b48Spatrick class ReduceCrashingInstructions : public ListReducer<const Instruction *> {
74809467b48Spatrick   BugDriver &BD;
74909467b48Spatrick   BugTester TestFn;
75009467b48Spatrick 
75109467b48Spatrick public:
ReduceCrashingInstructions(BugDriver & bd,BugTester testFn)75209467b48Spatrick   ReduceCrashingInstructions(BugDriver &bd, BugTester testFn)
75309467b48Spatrick       : BD(bd), TestFn(testFn) {}
75409467b48Spatrick 
doTest(std::vector<const Instruction * > & Prefix,std::vector<const Instruction * > & Kept)75509467b48Spatrick   Expected<TestResult> doTest(std::vector<const Instruction *> &Prefix,
75609467b48Spatrick                               std::vector<const Instruction *> &Kept) override {
75709467b48Spatrick     if (!Kept.empty() && TestInsts(Kept))
75809467b48Spatrick       return KeepSuffix;
75909467b48Spatrick     if (!Prefix.empty() && TestInsts(Prefix))
76009467b48Spatrick       return KeepPrefix;
76109467b48Spatrick     return NoFailure;
76209467b48Spatrick   }
76309467b48Spatrick 
76409467b48Spatrick   bool TestInsts(std::vector<const Instruction *> &Prefix);
76509467b48Spatrick };
76609467b48Spatrick }
76709467b48Spatrick 
TestInsts(std::vector<const Instruction * > & Insts)76809467b48Spatrick bool ReduceCrashingInstructions::TestInsts(
76909467b48Spatrick     std::vector<const Instruction *> &Insts) {
77009467b48Spatrick   // Clone the program to try hacking it apart...
77109467b48Spatrick   ValueToValueMapTy VMap;
77209467b48Spatrick   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
77309467b48Spatrick 
77409467b48Spatrick   // Convert list to set for fast lookup...
77509467b48Spatrick   SmallPtrSet<Instruction *, 32> Instructions;
77609467b48Spatrick   for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
77709467b48Spatrick     assert(!Insts[i]->isTerminator());
77809467b48Spatrick     Instructions.insert(cast<Instruction>(VMap[Insts[i]]));
77909467b48Spatrick   }
78009467b48Spatrick 
78109467b48Spatrick   outs() << "Checking for crash with only " << Instructions.size();
78209467b48Spatrick   if (Instructions.size() == 1)
78309467b48Spatrick     outs() << " instruction: ";
78409467b48Spatrick   else
78509467b48Spatrick     outs() << " instructions: ";
78609467b48Spatrick 
78709467b48Spatrick   for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI)
78809467b48Spatrick     for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI)
789*d415bd75Srobert       for (Instruction &Inst : llvm::make_early_inc_range(*FI)) {
790*d415bd75Srobert         if (!Instructions.count(&Inst) && !Inst.isTerminator() &&
791*d415bd75Srobert             !Inst.isEHPad() && !Inst.getType()->isTokenTy() &&
792*d415bd75Srobert             !Inst.isSwiftError()) {
793*d415bd75Srobert           if (!Inst.getType()->isVoidTy())
794*d415bd75Srobert             Inst.replaceAllUsesWith(PoisonValue::get(Inst.getType()));
795*d415bd75Srobert           Inst.eraseFromParent();
79609467b48Spatrick         }
79709467b48Spatrick       }
79809467b48Spatrick 
79909467b48Spatrick   // Verify that this is still valid.
80009467b48Spatrick   legacy::PassManager Passes;
80109467b48Spatrick   Passes.add(createVerifierPass(/*FatalErrors=*/false));
80209467b48Spatrick   Passes.run(*M);
80309467b48Spatrick 
80409467b48Spatrick   // Try running on the hacked up program...
80509467b48Spatrick   if (TestFn(BD, M.get())) {
80609467b48Spatrick     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
80709467b48Spatrick 
80809467b48Spatrick     // Make sure to use instruction pointers that point into the now-current
80909467b48Spatrick     // module, and that they don't include any deleted blocks.
81009467b48Spatrick     Insts.clear();
81109467b48Spatrick     for (Instruction *Inst : Instructions)
81209467b48Spatrick       Insts.push_back(Inst);
81309467b48Spatrick     return true;
81409467b48Spatrick   }
81509467b48Spatrick   // It didn't crash, try something else.
81609467b48Spatrick   return false;
81709467b48Spatrick }
81809467b48Spatrick 
81909467b48Spatrick namespace {
82009467b48Spatrick /// ReduceCrashingMetadata reducer - This works by removing all metadata from
82109467b48Spatrick /// the specified instructions.
82209467b48Spatrick ///
82309467b48Spatrick class ReduceCrashingMetadata : public ListReducer<Instruction *> {
82409467b48Spatrick   BugDriver &BD;
82509467b48Spatrick   BugTester TestFn;
82609467b48Spatrick 
82709467b48Spatrick public:
ReduceCrashingMetadata(BugDriver & bd,BugTester testFn)82809467b48Spatrick   ReduceCrashingMetadata(BugDriver &bd, BugTester testFn)
82909467b48Spatrick       : BD(bd), TestFn(testFn) {}
83009467b48Spatrick 
doTest(std::vector<Instruction * > & Prefix,std::vector<Instruction * > & Kept)83109467b48Spatrick   Expected<TestResult> doTest(std::vector<Instruction *> &Prefix,
83209467b48Spatrick                               std::vector<Instruction *> &Kept) override {
83309467b48Spatrick     if (!Kept.empty() && TestInsts(Kept))
83409467b48Spatrick       return KeepSuffix;
83509467b48Spatrick     if (!Prefix.empty() && TestInsts(Prefix))
83609467b48Spatrick       return KeepPrefix;
83709467b48Spatrick     return NoFailure;
83809467b48Spatrick   }
83909467b48Spatrick 
84009467b48Spatrick   bool TestInsts(std::vector<Instruction *> &Prefix);
84109467b48Spatrick };
84209467b48Spatrick } // namespace
84309467b48Spatrick 
TestInsts(std::vector<Instruction * > & Insts)84409467b48Spatrick bool ReduceCrashingMetadata::TestInsts(std::vector<Instruction *> &Insts) {
84509467b48Spatrick   // Clone the program to try hacking it apart...
84609467b48Spatrick   ValueToValueMapTy VMap;
84709467b48Spatrick   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
84809467b48Spatrick 
84909467b48Spatrick   // Convert list to set for fast lookup...
85009467b48Spatrick   SmallPtrSet<Instruction *, 32> Instructions;
85109467b48Spatrick   for (Instruction *I : Insts)
85209467b48Spatrick     Instructions.insert(cast<Instruction>(VMap[I]));
85309467b48Spatrick 
85409467b48Spatrick   outs() << "Checking for crash with metadata retained from "
85509467b48Spatrick          << Instructions.size();
85609467b48Spatrick   if (Instructions.size() == 1)
85709467b48Spatrick     outs() << " instruction: ";
85809467b48Spatrick   else
85909467b48Spatrick     outs() << " instructions: ";
86009467b48Spatrick 
86109467b48Spatrick   // Try to drop instruction metadata from all instructions, except the ones
86209467b48Spatrick   // selected in Instructions.
86309467b48Spatrick   for (Function &F : *M)
86409467b48Spatrick     for (Instruction &Inst : instructions(F)) {
865097a140dSpatrick       if (!Instructions.count(&Inst)) {
86609467b48Spatrick         Inst.dropUnknownNonDebugMetadata();
86709467b48Spatrick         Inst.setDebugLoc({});
86809467b48Spatrick       }
86909467b48Spatrick     }
87009467b48Spatrick 
87109467b48Spatrick   // Verify that this is still valid.
87209467b48Spatrick   legacy::PassManager Passes;
87309467b48Spatrick   Passes.add(createVerifierPass(/*FatalErrors=*/false));
87409467b48Spatrick   Passes.run(*M);
87509467b48Spatrick 
87609467b48Spatrick   // Try running on the hacked up program...
87709467b48Spatrick   if (TestFn(BD, M.get())) {
87809467b48Spatrick     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
87909467b48Spatrick 
88009467b48Spatrick     // Make sure to use instruction pointers that point into the now-current
88109467b48Spatrick     // module, and that they don't include any deleted blocks.
88209467b48Spatrick     Insts.clear();
88309467b48Spatrick     for (Instruction *I : Instructions)
88409467b48Spatrick       Insts.push_back(I);
88509467b48Spatrick     return true;
88609467b48Spatrick   }
88709467b48Spatrick   // It didn't crash, try something else.
88809467b48Spatrick   return false;
88909467b48Spatrick }
89009467b48Spatrick 
89109467b48Spatrick namespace {
89209467b48Spatrick // Reduce the list of Named Metadata nodes. We keep this as a list of
89309467b48Spatrick // names to avoid having to convert back and forth every time.
89409467b48Spatrick class ReduceCrashingNamedMD : public ListReducer<std::string> {
89509467b48Spatrick   BugDriver &BD;
89609467b48Spatrick   BugTester TestFn;
89709467b48Spatrick 
89809467b48Spatrick public:
ReduceCrashingNamedMD(BugDriver & bd,BugTester testFn)89909467b48Spatrick   ReduceCrashingNamedMD(BugDriver &bd, BugTester testFn)
90009467b48Spatrick       : BD(bd), TestFn(testFn) {}
90109467b48Spatrick 
doTest(std::vector<std::string> & Prefix,std::vector<std::string> & Kept)90209467b48Spatrick   Expected<TestResult> doTest(std::vector<std::string> &Prefix,
90309467b48Spatrick                               std::vector<std::string> &Kept) override {
90409467b48Spatrick     if (!Kept.empty() && TestNamedMDs(Kept))
90509467b48Spatrick       return KeepSuffix;
90609467b48Spatrick     if (!Prefix.empty() && TestNamedMDs(Prefix))
90709467b48Spatrick       return KeepPrefix;
90809467b48Spatrick     return NoFailure;
90909467b48Spatrick   }
91009467b48Spatrick 
91109467b48Spatrick   bool TestNamedMDs(std::vector<std::string> &NamedMDs);
91209467b48Spatrick };
91309467b48Spatrick }
91409467b48Spatrick 
TestNamedMDs(std::vector<std::string> & NamedMDs)91509467b48Spatrick bool ReduceCrashingNamedMD::TestNamedMDs(std::vector<std::string> &NamedMDs) {
91609467b48Spatrick 
91709467b48Spatrick   ValueToValueMapTy VMap;
91809467b48Spatrick   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
91909467b48Spatrick 
92009467b48Spatrick   outs() << "Checking for crash with only these named metadata nodes:";
92109467b48Spatrick   unsigned NumPrint = std::min<size_t>(NamedMDs.size(), 10);
92209467b48Spatrick   for (unsigned i = 0, e = NumPrint; i != e; ++i)
92309467b48Spatrick     outs() << " " << NamedMDs[i];
92409467b48Spatrick   if (NumPrint < NamedMDs.size())
92509467b48Spatrick     outs() << "... <" << NamedMDs.size() << " total>";
92609467b48Spatrick   outs() << ": ";
92709467b48Spatrick 
92809467b48Spatrick   // Make a StringMap for faster lookup
92909467b48Spatrick   StringSet<> Names;
93009467b48Spatrick   for (const std::string &Name : NamedMDs)
93109467b48Spatrick     Names.insert(Name);
93209467b48Spatrick 
93309467b48Spatrick   // First collect all the metadata to delete in a vector, then
93409467b48Spatrick   // delete them all at once to avoid invalidating the iterator
93509467b48Spatrick   std::vector<NamedMDNode *> ToDelete;
93609467b48Spatrick   ToDelete.reserve(M->named_metadata_size() - Names.size());
93709467b48Spatrick   for (auto &NamedMD : M->named_metadata())
93809467b48Spatrick     // Always keep a nonempty llvm.dbg.cu because the Verifier would complain.
93909467b48Spatrick     if (!Names.count(NamedMD.getName()) &&
94009467b48Spatrick         (!(NamedMD.getName() == "llvm.dbg.cu" && NamedMD.getNumOperands() > 0)))
94109467b48Spatrick       ToDelete.push_back(&NamedMD);
94209467b48Spatrick 
94309467b48Spatrick   for (auto *NamedMD : ToDelete)
94409467b48Spatrick     NamedMD->eraseFromParent();
94509467b48Spatrick 
94609467b48Spatrick   // Verify that this is still valid.
94709467b48Spatrick   legacy::PassManager Passes;
94809467b48Spatrick   Passes.add(createVerifierPass(/*FatalErrors=*/false));
94909467b48Spatrick   Passes.run(*M);
95009467b48Spatrick 
95109467b48Spatrick   // Try running on the hacked up program...
95209467b48Spatrick   if (TestFn(BD, M.get())) {
95309467b48Spatrick     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
95409467b48Spatrick     return true;
95509467b48Spatrick   }
95609467b48Spatrick   return false;
95709467b48Spatrick }
95809467b48Spatrick 
95909467b48Spatrick namespace {
96009467b48Spatrick // Reduce the list of operands to named metadata nodes
96109467b48Spatrick class ReduceCrashingNamedMDOps : public ListReducer<const MDNode *> {
96209467b48Spatrick   BugDriver &BD;
96309467b48Spatrick   BugTester TestFn;
96409467b48Spatrick 
96509467b48Spatrick public:
ReduceCrashingNamedMDOps(BugDriver & bd,BugTester testFn)96609467b48Spatrick   ReduceCrashingNamedMDOps(BugDriver &bd, BugTester testFn)
96709467b48Spatrick       : BD(bd), TestFn(testFn) {}
96809467b48Spatrick 
doTest(std::vector<const MDNode * > & Prefix,std::vector<const MDNode * > & Kept)96909467b48Spatrick   Expected<TestResult> doTest(std::vector<const MDNode *> &Prefix,
97009467b48Spatrick                               std::vector<const MDNode *> &Kept) override {
97109467b48Spatrick     if (!Kept.empty() && TestNamedMDOps(Kept))
97209467b48Spatrick       return KeepSuffix;
97309467b48Spatrick     if (!Prefix.empty() && TestNamedMDOps(Prefix))
97409467b48Spatrick       return KeepPrefix;
97509467b48Spatrick     return NoFailure;
97609467b48Spatrick   }
97709467b48Spatrick 
97809467b48Spatrick   bool TestNamedMDOps(std::vector<const MDNode *> &NamedMDOps);
97909467b48Spatrick };
98009467b48Spatrick }
98109467b48Spatrick 
TestNamedMDOps(std::vector<const MDNode * > & NamedMDOps)98209467b48Spatrick bool ReduceCrashingNamedMDOps::TestNamedMDOps(
98309467b48Spatrick     std::vector<const MDNode *> &NamedMDOps) {
98409467b48Spatrick   // Convert list to set for fast lookup...
98509467b48Spatrick   SmallPtrSet<const MDNode *, 32> OldMDNodeOps;
98609467b48Spatrick   for (unsigned i = 0, e = NamedMDOps.size(); i != e; ++i) {
98709467b48Spatrick     OldMDNodeOps.insert(NamedMDOps[i]);
98809467b48Spatrick   }
98909467b48Spatrick 
99009467b48Spatrick   outs() << "Checking for crash with only " << OldMDNodeOps.size();
99109467b48Spatrick   if (OldMDNodeOps.size() == 1)
99209467b48Spatrick     outs() << " named metadata operand: ";
99309467b48Spatrick   else
99409467b48Spatrick     outs() << " named metadata operands: ";
99509467b48Spatrick 
99609467b48Spatrick   ValueToValueMapTy VMap;
99709467b48Spatrick   std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
99809467b48Spatrick 
99909467b48Spatrick   // This is a little wasteful. In the future it might be good if we could have
100009467b48Spatrick   // these dropped during cloning.
100109467b48Spatrick   for (auto &NamedMD : BD.getProgram().named_metadata()) {
100209467b48Spatrick     // Drop the old one and create a new one
100309467b48Spatrick     M->eraseNamedMetadata(M->getNamedMetadata(NamedMD.getName()));
100409467b48Spatrick     NamedMDNode *NewNamedMDNode =
100509467b48Spatrick         M->getOrInsertNamedMetadata(NamedMD.getName());
100609467b48Spatrick     for (MDNode *op : NamedMD.operands())
100709467b48Spatrick       if (OldMDNodeOps.count(op))
100809467b48Spatrick         NewNamedMDNode->addOperand(cast<MDNode>(MapMetadata(op, VMap)));
100909467b48Spatrick   }
101009467b48Spatrick 
101109467b48Spatrick   // Verify that this is still valid.
101209467b48Spatrick   legacy::PassManager Passes;
101309467b48Spatrick   Passes.add(createVerifierPass(/*FatalErrors=*/false));
101409467b48Spatrick   Passes.run(*M);
101509467b48Spatrick 
101609467b48Spatrick   // Try running on the hacked up program...
101709467b48Spatrick   if (TestFn(BD, M.get())) {
101809467b48Spatrick     // Make sure to use instruction pointers that point into the now-current
101909467b48Spatrick     // module, and that they don't include any deleted blocks.
102009467b48Spatrick     NamedMDOps.clear();
102109467b48Spatrick     for (const MDNode *Node : OldMDNodeOps)
102209467b48Spatrick       NamedMDOps.push_back(cast<MDNode>(*VMap.getMappedMD(Node)));
102309467b48Spatrick 
102409467b48Spatrick     BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
102509467b48Spatrick     return true;
102609467b48Spatrick   }
102709467b48Spatrick   // It didn't crash, try something else.
102809467b48Spatrick   return false;
102909467b48Spatrick }
103009467b48Spatrick 
103109467b48Spatrick /// Attempt to eliminate as many global initializers as possible.
ReduceGlobalInitializers(BugDriver & BD,BugTester TestFn)103209467b48Spatrick static Error ReduceGlobalInitializers(BugDriver &BD, BugTester TestFn) {
103309467b48Spatrick   Module &OrigM = BD.getProgram();
103409467b48Spatrick   if (OrigM.global_empty())
103509467b48Spatrick     return Error::success();
103609467b48Spatrick 
103709467b48Spatrick   // Now try to reduce the number of global variable initializers in the
103809467b48Spatrick   // module to something small.
103909467b48Spatrick   std::unique_ptr<Module> M = CloneModule(OrigM);
104009467b48Spatrick   bool DeletedInit = false;
104109467b48Spatrick 
104209467b48Spatrick   for (GlobalVariable &GV : M->globals()) {
104309467b48Spatrick     if (GV.hasInitializer()) {
104409467b48Spatrick       DeleteGlobalInitializer(&GV);
104509467b48Spatrick       GV.setLinkage(GlobalValue::ExternalLinkage);
104609467b48Spatrick       GV.setComdat(nullptr);
104709467b48Spatrick       DeletedInit = true;
104809467b48Spatrick     }
104909467b48Spatrick   }
105009467b48Spatrick 
105109467b48Spatrick   if (!DeletedInit)
105209467b48Spatrick     return Error::success();
105309467b48Spatrick 
105409467b48Spatrick   // See if the program still causes a crash...
105509467b48Spatrick   outs() << "\nChecking to see if we can delete global inits: ";
105609467b48Spatrick 
105709467b48Spatrick   if (TestFn(BD, M.get())) { // Still crashes?
105809467b48Spatrick     BD.setNewProgram(std::move(M));
105909467b48Spatrick     outs() << "\n*** Able to remove all global initializers!\n";
106009467b48Spatrick     return Error::success();
106109467b48Spatrick   }
106209467b48Spatrick 
106309467b48Spatrick   // No longer crashes.
106409467b48Spatrick   outs() << "  - Removing all global inits hides problem!\n";
106509467b48Spatrick 
106609467b48Spatrick   std::vector<GlobalVariable *> GVs;
106709467b48Spatrick   for (GlobalVariable &GV : OrigM.globals())
106809467b48Spatrick     if (GV.hasInitializer())
106909467b48Spatrick       GVs.push_back(&GV);
107009467b48Spatrick 
107109467b48Spatrick   if (GVs.size() > 1 && !BugpointIsInterrupted) {
107209467b48Spatrick     outs() << "\n*** Attempting to reduce the number of global initializers "
107309467b48Spatrick            << "in the testcase\n";
107409467b48Spatrick 
107509467b48Spatrick     unsigned OldSize = GVs.size();
107609467b48Spatrick     Expected<bool> Result =
107709467b48Spatrick         ReduceCrashingGlobalInitializers(BD, TestFn).reduceList(GVs);
107809467b48Spatrick     if (Error E = Result.takeError())
107909467b48Spatrick       return E;
108009467b48Spatrick 
108109467b48Spatrick     if (GVs.size() < OldSize)
108209467b48Spatrick       BD.EmitProgressBitcode(BD.getProgram(), "reduced-global-variables");
108309467b48Spatrick   }
108409467b48Spatrick   return Error::success();
108509467b48Spatrick }
108609467b48Spatrick 
ReduceInsts(BugDriver & BD,BugTester TestFn)108709467b48Spatrick static Error ReduceInsts(BugDriver &BD, BugTester TestFn) {
108809467b48Spatrick   // Attempt to delete instructions using bisection. This should help out nasty
108909467b48Spatrick   // cases with large basic blocks where the problem is at one end.
109009467b48Spatrick   if (!BugpointIsInterrupted) {
109109467b48Spatrick     std::vector<const Instruction *> Insts;
109209467b48Spatrick     for (const Function &F : BD.getProgram())
109309467b48Spatrick       for (const BasicBlock &BB : F)
109409467b48Spatrick         for (const Instruction &I : BB)
109509467b48Spatrick           if (!I.isTerminator())
109609467b48Spatrick             Insts.push_back(&I);
109709467b48Spatrick 
109809467b48Spatrick     Expected<bool> Result =
109909467b48Spatrick         ReduceCrashingInstructions(BD, TestFn).reduceList(Insts);
110009467b48Spatrick     if (Error E = Result.takeError())
110109467b48Spatrick       return E;
110209467b48Spatrick   }
110309467b48Spatrick 
110409467b48Spatrick   unsigned Simplification = 2;
110509467b48Spatrick   do {
110609467b48Spatrick     if (BugpointIsInterrupted)
110709467b48Spatrick       // TODO: Should we distinguish this with an "interrupted error"?
110809467b48Spatrick       return Error::success();
110909467b48Spatrick     --Simplification;
111009467b48Spatrick     outs() << "\n*** Attempting to reduce testcase by deleting instruc"
111109467b48Spatrick            << "tions: Simplification Level #" << Simplification << '\n';
111209467b48Spatrick 
111309467b48Spatrick     // Now that we have deleted the functions that are unnecessary for the
111409467b48Spatrick     // program, try to remove instructions that are not necessary to cause the
111509467b48Spatrick     // crash.  To do this, we loop through all of the instructions in the
111609467b48Spatrick     // remaining functions, deleting them (replacing any values produced with
111709467b48Spatrick     // nulls), and then running ADCE and SimplifyCFG.  If the transformed input
111809467b48Spatrick     // still triggers failure, keep deleting until we cannot trigger failure
111909467b48Spatrick     // anymore.
112009467b48Spatrick     //
112109467b48Spatrick     unsigned InstructionsToSkipBeforeDeleting = 0;
112209467b48Spatrick   TryAgain:
112309467b48Spatrick 
112409467b48Spatrick     // Loop over all of the (non-terminator) instructions remaining in the
112509467b48Spatrick     // function, attempting to delete them.
112609467b48Spatrick     unsigned CurInstructionNum = 0;
112709467b48Spatrick     for (Module::const_iterator FI = BD.getProgram().begin(),
112809467b48Spatrick                                 E = BD.getProgram().end();
112909467b48Spatrick          FI != E; ++FI)
113009467b48Spatrick       if (!FI->isDeclaration())
113109467b48Spatrick         for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E;
113209467b48Spatrick              ++BI)
113309467b48Spatrick           for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end();
113409467b48Spatrick                I != E; ++I, ++CurInstructionNum) {
113509467b48Spatrick             if (InstructionsToSkipBeforeDeleting) {
113609467b48Spatrick               --InstructionsToSkipBeforeDeleting;
113709467b48Spatrick             } else {
113809467b48Spatrick               if (BugpointIsInterrupted)
113909467b48Spatrick                 // TODO: Should this be some kind of interrupted error?
114009467b48Spatrick                 return Error::success();
114109467b48Spatrick 
114209467b48Spatrick               if (I->isEHPad() || I->getType()->isTokenTy() ||
114309467b48Spatrick                   I->isSwiftError())
114409467b48Spatrick                 continue;
114509467b48Spatrick 
114609467b48Spatrick               outs() << "Checking instruction: " << *I;
114709467b48Spatrick               std::unique_ptr<Module> M =
114809467b48Spatrick                   BD.deleteInstructionFromProgram(&*I, Simplification);
114909467b48Spatrick 
115009467b48Spatrick               // Find out if the pass still crashes on this pass...
115109467b48Spatrick               if (TestFn(BD, M.get())) {
115209467b48Spatrick                 // Yup, it does, we delete the old module, and continue trying
115309467b48Spatrick                 // to reduce the testcase...
115409467b48Spatrick                 BD.setNewProgram(std::move(M));
115509467b48Spatrick                 InstructionsToSkipBeforeDeleting = CurInstructionNum;
115609467b48Spatrick                 goto TryAgain; // I wish I had a multi-level break here!
115709467b48Spatrick               }
115809467b48Spatrick             }
115909467b48Spatrick           }
116009467b48Spatrick 
116109467b48Spatrick     if (InstructionsToSkipBeforeDeleting) {
116209467b48Spatrick       InstructionsToSkipBeforeDeleting = 0;
116309467b48Spatrick       goto TryAgain;
116409467b48Spatrick     }
116509467b48Spatrick 
116609467b48Spatrick   } while (Simplification);
116709467b48Spatrick 
116809467b48Spatrick   // Attempt to drop metadata from instructions that does not contribute to the
116909467b48Spatrick   // crash.
117009467b48Spatrick   if (!BugpointIsInterrupted) {
117109467b48Spatrick     std::vector<Instruction *> Insts;
117209467b48Spatrick     for (Function &F : BD.getProgram())
117309467b48Spatrick       for (Instruction &I : instructions(F))
117409467b48Spatrick         Insts.push_back(&I);
117509467b48Spatrick 
117609467b48Spatrick     Expected<bool> Result =
117709467b48Spatrick         ReduceCrashingMetadata(BD, TestFn).reduceList(Insts);
117809467b48Spatrick     if (Error E = Result.takeError())
117909467b48Spatrick       return E;
118009467b48Spatrick   }
118109467b48Spatrick 
118209467b48Spatrick   BD.EmitProgressBitcode(BD.getProgram(), "reduced-instructions");
118309467b48Spatrick   return Error::success();
118409467b48Spatrick }
118509467b48Spatrick 
118609467b48Spatrick /// DebugACrash - Given a predicate that determines whether a component crashes
118709467b48Spatrick /// on a program, try to destructively reduce the program while still keeping
118809467b48Spatrick /// the predicate true.
DebugACrash(BugDriver & BD,BugTester TestFn)118909467b48Spatrick static Error DebugACrash(BugDriver &BD, BugTester TestFn) {
119009467b48Spatrick   // See if we can get away with nuking some of the global variable initializers
119109467b48Spatrick   // in the program...
119209467b48Spatrick   if (!NoGlobalRM)
119309467b48Spatrick     if (Error E = ReduceGlobalInitializers(BD, TestFn))
119409467b48Spatrick       return E;
119509467b48Spatrick 
119609467b48Spatrick   // Now try to reduce the number of functions in the module to something small.
119709467b48Spatrick   std::vector<Function *> Functions;
119809467b48Spatrick   for (Function &F : BD.getProgram())
119909467b48Spatrick     if (!F.isDeclaration())
120009467b48Spatrick       Functions.push_back(&F);
120109467b48Spatrick 
120209467b48Spatrick   if (Functions.size() > 1 && !BugpointIsInterrupted) {
120309467b48Spatrick     outs() << "\n*** Attempting to reduce the number of functions "
120409467b48Spatrick               "in the testcase\n";
120509467b48Spatrick 
120609467b48Spatrick     unsigned OldSize = Functions.size();
120709467b48Spatrick     Expected<bool> Result =
120809467b48Spatrick         ReduceCrashingFunctions(BD, TestFn).reduceList(Functions);
120909467b48Spatrick     if (Error E = Result.takeError())
121009467b48Spatrick       return E;
121109467b48Spatrick 
121209467b48Spatrick     if (Functions.size() < OldSize)
121309467b48Spatrick       BD.EmitProgressBitcode(BD.getProgram(), "reduced-function");
121409467b48Spatrick   }
121509467b48Spatrick 
121609467b48Spatrick   if (!NoAttributeRM) {
121709467b48Spatrick     // For each remaining function, try to reduce that function's attributes.
121809467b48Spatrick     std::vector<std::string> FunctionNames;
121909467b48Spatrick     for (Function &F : BD.getProgram())
1220097a140dSpatrick       FunctionNames.push_back(std::string(F.getName()));
122109467b48Spatrick 
122209467b48Spatrick     if (!FunctionNames.empty() && !BugpointIsInterrupted) {
122309467b48Spatrick       outs() << "\n*** Attempting to reduce the number of function attributes"
122409467b48Spatrick                 " in the testcase\n";
122509467b48Spatrick 
122609467b48Spatrick       unsigned OldSize = 0;
122709467b48Spatrick       unsigned NewSize = 0;
122809467b48Spatrick       for (std::string &Name : FunctionNames) {
122909467b48Spatrick         Function *Fn = BD.getProgram().getFunction(Name);
123073471bf0Spatrick         assert(Fn && "Could not find function?");
123109467b48Spatrick 
123209467b48Spatrick         std::vector<Attribute> Attrs;
1233*d415bd75Srobert         for (Attribute A : Fn->getAttributes().getFnAttrs())
123409467b48Spatrick           Attrs.push_back(A);
123509467b48Spatrick 
123609467b48Spatrick         OldSize += Attrs.size();
123709467b48Spatrick         Expected<bool> Result =
123809467b48Spatrick           ReduceCrashingFunctionAttributes(BD, Name, TestFn).reduceList(Attrs);
123909467b48Spatrick         if (Error E = Result.takeError())
124009467b48Spatrick           return E;
124109467b48Spatrick 
124209467b48Spatrick         NewSize += Attrs.size();
124309467b48Spatrick       }
124409467b48Spatrick 
124509467b48Spatrick       if (OldSize < NewSize)
124609467b48Spatrick         BD.EmitProgressBitcode(BD.getProgram(), "reduced-function-attributes");
124709467b48Spatrick     }
124809467b48Spatrick   }
124909467b48Spatrick 
125009467b48Spatrick   // Attempt to change conditional branches into unconditional branches to
125109467b48Spatrick   // eliminate blocks.
125209467b48Spatrick   if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
125309467b48Spatrick     std::vector<const BasicBlock *> Blocks;
125409467b48Spatrick     for (Function &F : BD.getProgram())
125509467b48Spatrick       for (BasicBlock &BB : F)
125609467b48Spatrick         Blocks.push_back(&BB);
125709467b48Spatrick     unsigned OldSize = Blocks.size();
125809467b48Spatrick     Expected<bool> Result =
125909467b48Spatrick         ReduceCrashingConditionals(BD, TestFn, true).reduceList(Blocks);
126009467b48Spatrick     if (Error E = Result.takeError())
126109467b48Spatrick       return E;
126209467b48Spatrick     Result = ReduceCrashingConditionals(BD, TestFn, false).reduceList(Blocks);
126309467b48Spatrick     if (Error E = Result.takeError())
126409467b48Spatrick       return E;
126509467b48Spatrick     if (Blocks.size() < OldSize)
126609467b48Spatrick       BD.EmitProgressBitcode(BD.getProgram(), "reduced-conditionals");
126709467b48Spatrick   }
126809467b48Spatrick 
126909467b48Spatrick   // Attempt to delete entire basic blocks at a time to speed up
127009467b48Spatrick   // convergence... this actually works by setting the terminator of the blocks
127109467b48Spatrick   // to a return instruction then running simplifycfg, which can potentially
127209467b48Spatrick   // shrinks the code dramatically quickly
127309467b48Spatrick   //
127409467b48Spatrick   if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
127509467b48Spatrick     std::vector<const BasicBlock *> Blocks;
127609467b48Spatrick     for (Function &F : BD.getProgram())
127709467b48Spatrick       for (BasicBlock &BB : F)
127809467b48Spatrick         Blocks.push_back(&BB);
127909467b48Spatrick     unsigned OldSize = Blocks.size();
128009467b48Spatrick     Expected<bool> Result = ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks);
128109467b48Spatrick     if (Error E = Result.takeError())
128209467b48Spatrick       return E;
128309467b48Spatrick     if (Blocks.size() < OldSize)
128409467b48Spatrick       BD.EmitProgressBitcode(BD.getProgram(), "reduced-blocks");
128509467b48Spatrick   }
128609467b48Spatrick 
128709467b48Spatrick   if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
128809467b48Spatrick     std::vector<const BasicBlock *> Blocks;
128909467b48Spatrick     for (Function &F : BD.getProgram())
129009467b48Spatrick       for (BasicBlock &BB : F)
129109467b48Spatrick         Blocks.push_back(&BB);
129209467b48Spatrick     unsigned OldSize = Blocks.size();
129309467b48Spatrick     Expected<bool> Result = ReduceSimplifyCFG(BD, TestFn).reduceList(Blocks);
129409467b48Spatrick     if (Error E = Result.takeError())
129509467b48Spatrick       return E;
129609467b48Spatrick     if (Blocks.size() < OldSize)
129709467b48Spatrick       BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplifycfg");
129809467b48Spatrick   }
129909467b48Spatrick 
130009467b48Spatrick   // Attempt to delete instructions using bisection. This should help out nasty
130109467b48Spatrick   // cases with large basic blocks where the problem is at one end.
130209467b48Spatrick   if (!BugpointIsInterrupted)
130309467b48Spatrick     if (Error E = ReduceInsts(BD, TestFn))
130409467b48Spatrick       return E;
130509467b48Spatrick 
130609467b48Spatrick   // Attempt to strip debug info metadata.
130709467b48Spatrick   auto stripMetadata = [&](std::function<bool(Module &)> strip) {
130809467b48Spatrick     std::unique_ptr<Module> M = CloneModule(BD.getProgram());
130909467b48Spatrick     strip(*M);
131009467b48Spatrick     if (TestFn(BD, M.get()))
131109467b48Spatrick       BD.setNewProgram(std::move(M));
131209467b48Spatrick   };
131309467b48Spatrick   if (!NoStripDebugInfo && !BugpointIsInterrupted) {
131409467b48Spatrick     outs() << "\n*** Attempting to strip the debug info: ";
131509467b48Spatrick     stripMetadata(StripDebugInfo);
131609467b48Spatrick   }
131709467b48Spatrick   if (!NoStripDebugTypeInfo && !BugpointIsInterrupted) {
131809467b48Spatrick     outs() << "\n*** Attempting to strip the debug type info: ";
131909467b48Spatrick     stripMetadata(stripNonLineTableDebugInfo);
132009467b48Spatrick   }
132109467b48Spatrick 
132209467b48Spatrick   if (!NoNamedMDRM) {
132309467b48Spatrick     if (!BugpointIsInterrupted) {
132409467b48Spatrick       // Try to reduce the amount of global metadata (particularly debug info),
132509467b48Spatrick       // by dropping global named metadata that anchors them
132609467b48Spatrick       outs() << "\n*** Attempting to remove named metadata: ";
132709467b48Spatrick       std::vector<std::string> NamedMDNames;
132809467b48Spatrick       for (auto &NamedMD : BD.getProgram().named_metadata())
132909467b48Spatrick         NamedMDNames.push_back(NamedMD.getName().str());
133009467b48Spatrick       Expected<bool> Result =
133109467b48Spatrick           ReduceCrashingNamedMD(BD, TestFn).reduceList(NamedMDNames);
133209467b48Spatrick       if (Error E = Result.takeError())
133309467b48Spatrick         return E;
133409467b48Spatrick     }
133509467b48Spatrick 
133609467b48Spatrick     if (!BugpointIsInterrupted) {
133709467b48Spatrick       // Now that we quickly dropped all the named metadata that doesn't
133809467b48Spatrick       // contribute to the crash, bisect the operands of the remaining ones
133909467b48Spatrick       std::vector<const MDNode *> NamedMDOps;
134009467b48Spatrick       for (auto &NamedMD : BD.getProgram().named_metadata())
1341*d415bd75Srobert         for (auto *op : NamedMD.operands())
134209467b48Spatrick           NamedMDOps.push_back(op);
134309467b48Spatrick       Expected<bool> Result =
134409467b48Spatrick           ReduceCrashingNamedMDOps(BD, TestFn).reduceList(NamedMDOps);
134509467b48Spatrick       if (Error E = Result.takeError())
134609467b48Spatrick         return E;
134709467b48Spatrick     }
134809467b48Spatrick     BD.EmitProgressBitcode(BD.getProgram(), "reduced-named-md");
134909467b48Spatrick   }
135009467b48Spatrick 
135109467b48Spatrick   // Try to clean up the testcase by running funcresolve and globaldce...
135209467b48Spatrick   if (!BugpointIsInterrupted) {
135309467b48Spatrick     outs() << "\n*** Attempting to perform final cleanups: ";
135409467b48Spatrick     std::unique_ptr<Module> M = CloneModule(BD.getProgram());
135509467b48Spatrick     M = BD.performFinalCleanups(std::move(M), true);
135609467b48Spatrick 
135709467b48Spatrick     // Find out if the pass still crashes on the cleaned up program...
135809467b48Spatrick     if (M && TestFn(BD, M.get()))
135909467b48Spatrick       BD.setNewProgram(
136009467b48Spatrick           std::move(M)); // Yup, it does, keep the reduced version...
136109467b48Spatrick   }
136209467b48Spatrick 
136309467b48Spatrick   BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplified");
136409467b48Spatrick 
136509467b48Spatrick   return Error::success();
136609467b48Spatrick }
136709467b48Spatrick 
TestForOptimizerCrash(const BugDriver & BD,Module * M)136809467b48Spatrick static bool TestForOptimizerCrash(const BugDriver &BD, Module *M) {
136909467b48Spatrick   return BD.runPasses(*M, BD.getPassesToRun());
137009467b48Spatrick }
137109467b48Spatrick 
137209467b48Spatrick /// debugOptimizerCrash - This method is called when some pass crashes on input.
137309467b48Spatrick /// It attempts to prune down the testcase to something reasonable, and figure
137409467b48Spatrick /// out exactly which pass is crashing.
137509467b48Spatrick ///
debugOptimizerCrash(const std::string & ID)137609467b48Spatrick Error BugDriver::debugOptimizerCrash(const std::string &ID) {
137709467b48Spatrick   outs() << "\n*** Debugging optimizer crash!\n";
137809467b48Spatrick 
137909467b48Spatrick   // Reduce the list of passes which causes the optimizer to crash...
138009467b48Spatrick   if (!BugpointIsInterrupted && !DontReducePassList) {
138109467b48Spatrick     Expected<bool> Result = ReducePassList(*this).reduceList(PassesToRun);
138209467b48Spatrick     if (Error E = Result.takeError())
138309467b48Spatrick       return E;
138409467b48Spatrick   }
138509467b48Spatrick 
138609467b48Spatrick   outs() << "\n*** Found crashing pass"
138709467b48Spatrick          << (PassesToRun.size() == 1 ? ": " : "es: ")
138809467b48Spatrick          << getPassesString(PassesToRun) << '\n';
138909467b48Spatrick 
139009467b48Spatrick   EmitProgressBitcode(*Program, ID);
139109467b48Spatrick 
139209467b48Spatrick   auto Res = DebugACrash(*this, TestForOptimizerCrash);
139309467b48Spatrick   if (Res || DontReducePassList)
139409467b48Spatrick     return Res;
139509467b48Spatrick   // Try to reduce the pass list again. This covers additional cases
139609467b48Spatrick   // we failed to reduce earlier, because of more complex pass dependencies
139709467b48Spatrick   // triggering the crash.
139809467b48Spatrick   auto SecondRes = ReducePassList(*this).reduceList(PassesToRun);
139909467b48Spatrick   if (Error E = SecondRes.takeError())
140009467b48Spatrick     return E;
140109467b48Spatrick   outs() << "\n*** Found crashing pass"
140209467b48Spatrick          << (PassesToRun.size() == 1 ? ": " : "es: ")
140309467b48Spatrick          << getPassesString(PassesToRun) << '\n';
140409467b48Spatrick 
140509467b48Spatrick   EmitProgressBitcode(getProgram(), "reduced-simplified");
140609467b48Spatrick   return Res;
140709467b48Spatrick }
140809467b48Spatrick 
TestForCodeGenCrash(const BugDriver & BD,Module * M)140909467b48Spatrick static bool TestForCodeGenCrash(const BugDriver &BD, Module *M) {
141009467b48Spatrick   if (Error E = BD.compileProgram(*M)) {
141109467b48Spatrick     if (VerboseErrors)
141209467b48Spatrick       errs() << toString(std::move(E)) << "\n";
141309467b48Spatrick     else {
141409467b48Spatrick       consumeError(std::move(E));
141509467b48Spatrick       errs() << "<crash>\n";
141609467b48Spatrick     }
141709467b48Spatrick     return true; // Tool is still crashing.
141809467b48Spatrick   }
141909467b48Spatrick   errs() << '\n';
142009467b48Spatrick   return false;
142109467b48Spatrick }
142209467b48Spatrick 
142309467b48Spatrick /// debugCodeGeneratorCrash - This method is called when the code generator
142409467b48Spatrick /// crashes on an input.  It attempts to reduce the input as much as possible
142509467b48Spatrick /// while still causing the code generator to crash.
debugCodeGeneratorCrash()142609467b48Spatrick Error BugDriver::debugCodeGeneratorCrash() {
142709467b48Spatrick   errs() << "*** Debugging code generator crash!\n";
142809467b48Spatrick 
142909467b48Spatrick   return DebugACrash(*this, TestForCodeGenCrash);
143009467b48Spatrick }
1431