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