1 //===- CrashDebugger.cpp - Debug compilation crashes ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the bugpoint internals that narrow down compilation crashes
12 //===----------------------------------------------------------------------===//
14 #include "BugDriver.h"
15 #include "ListReducer.h"
16 #include "ToolRunner.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/StringSet.h"
19 #include "llvm/Analysis/TargetTransformInfo.h"
20 #include "llvm/IR/CFG.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/DebugInfo.h"
23 #include "llvm/IR/DerivedTypes.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/LegacyPassManager.h"
26 #include "llvm/IR/Module.h"
27 #include "llvm/IR/ValueSymbolTable.h"
28 #include "llvm/IR/Verifier.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/CommandLine.h"
31 #include "llvm/Support/FileUtilities.h"
32 #include "llvm/Transforms/Scalar.h"
33 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
34 #include "llvm/Transforms/Utils/Cloning.h"
35 #include "llvm/Transforms/Utils/Local.h"
40 cl::opt<bool> KeepMain("keep-main",
41 cl::desc("Force function reduction to keep main"),
43 cl::opt<bool> NoGlobalRM("disable-global-remove",
44 cl::desc("Do not remove global variables"),
47 cl::opt<bool> ReplaceFuncsWithNull(
48 "replace-funcs-with-null",
49 cl::desc("When stubbing functions, replace all uses will null"),
51 cl::opt<bool> DontReducePassList("disable-pass-list-reduction",
52 cl::desc("Skip pass list reduction steps"),
55 cl::opt<bool> NoNamedMDRM("disable-namedmd-remove",
56 cl::desc("Do not remove global named metadata"),
58 cl::opt<bool> NoStripDebugInfo("disable-strip-debuginfo",
59 cl::desc("Do not strip debug info metadata"),
61 cl::opt<bool> NoStripDebugTypeInfo("disable-strip-debug-types",
62 cl::desc("Do not strip debug type info metadata"),
64 cl::opt<bool> VerboseErrors("verbose-errors",
65 cl::desc("Print the output of crashing program"),
70 class ReducePassList : public ListReducer<std::string> {
74 ReducePassList(BugDriver &bd) : BD(bd) {}
76 // Return true iff running the "removed" passes succeeds, and running the
77 // "Kept" passes fail when run on the output of the "removed" passes. If we
78 // return true, we update the current module of bugpoint.
79 Expected<TestResult> doTest(std::vector<std::string> &Removed,
80 std::vector<std::string> &Kept) override;
84 Expected<ReducePassList::TestResult>
85 ReducePassList::doTest(std::vector<std::string> &Prefix,
86 std::vector<std::string> &Suffix) {
87 std::string PrefixOutput;
88 Module *OrigProgram = nullptr;
89 if (!Prefix.empty()) {
90 outs() << "Checking to see if these passes crash: "
91 << getPassesString(Prefix) << ": ";
92 if (BD.runPasses(BD.getProgram(), Prefix, PrefixOutput))
95 OrigProgram = BD.Program;
97 BD.Program = parseInputFile(PrefixOutput, BD.getContext()).release();
98 if (BD.Program == nullptr) {
99 errs() << BD.getToolName() << ": Error reading bitcode file '"
100 << PrefixOutput << "'!\n";
103 sys::fs::remove(PrefixOutput);
106 outs() << "Checking to see if these passes crash: " << getPassesString(Suffix)
109 if (BD.runPasses(BD.getProgram(), Suffix)) {
110 delete OrigProgram; // The suffix crashes alone...
114 // Nothing failed, restore state...
117 BD.Program = OrigProgram;
123 /// ReduceCrashingGlobalVariables - This works by removing the global
124 /// variable's initializer and seeing if the program still crashes. If it
125 /// does, then we keep that program and try again.
127 class ReduceCrashingGlobalVariables : public ListReducer<GlobalVariable *> {
129 bool (*TestFn)(const BugDriver &, Module *);
132 ReduceCrashingGlobalVariables(BugDriver &bd,
133 bool (*testFn)(const BugDriver &, Module *))
134 : BD(bd), TestFn(testFn) {}
136 Expected<TestResult> doTest(std::vector<GlobalVariable *> &Prefix,
137 std::vector<GlobalVariable *> &Kept) override {
138 if (!Kept.empty() && TestGlobalVariables(Kept))
140 if (!Prefix.empty() && TestGlobalVariables(Prefix))
145 bool TestGlobalVariables(std::vector<GlobalVariable *> &GVs);
149 bool ReduceCrashingGlobalVariables::TestGlobalVariables(
150 std::vector<GlobalVariable *> &GVs) {
151 // Clone the program to try hacking it apart...
152 ValueToValueMapTy VMap;
153 Module *M = CloneModule(BD.getProgram(), VMap).release();
155 // Convert list to set for fast lookup...
156 std::set<GlobalVariable *> GVSet;
158 for (unsigned i = 0, e = GVs.size(); i != e; ++i) {
159 GlobalVariable *CMGV = cast<GlobalVariable>(VMap[GVs[i]]);
160 assert(CMGV && "Global Variable not in module?!");
164 outs() << "Checking for crash with only these global variables: ";
165 PrintGlobalVariableList(GVs);
168 // Loop over and delete any global variables which we aren't supposed to be
170 for (GlobalVariable &I : M->globals())
171 if (I.hasInitializer() && !GVSet.count(&I)) {
172 DeleteGlobalInitializer(&I);
173 I.setLinkage(GlobalValue::ExternalLinkage);
174 I.setComdat(nullptr);
177 // Try running the hacked up program...
179 BD.setNewProgram(M); // It crashed, keep the trimmed version...
181 // Make sure to use global variable pointers that point into the now-current
183 GVs.assign(GVSet.begin(), GVSet.end());
192 /// ReduceCrashingFunctions reducer - This works by removing functions and
193 /// seeing if the program still crashes. If it does, then keep the newer,
196 class ReduceCrashingFunctions : public ListReducer<Function *> {
198 bool (*TestFn)(const BugDriver &, Module *);
201 ReduceCrashingFunctions(BugDriver &bd,
202 bool (*testFn)(const BugDriver &, Module *))
203 : BD(bd), TestFn(testFn) {}
205 Expected<TestResult> doTest(std::vector<Function *> &Prefix,
206 std::vector<Function *> &Kept) override {
207 if (!Kept.empty() && TestFuncs(Kept))
209 if (!Prefix.empty() && TestFuncs(Prefix))
214 bool TestFuncs(std::vector<Function *> &Prefix);
218 static void RemoveFunctionReferences(Module *M, const char *Name) {
219 auto *UsedVar = M->getGlobalVariable(Name, true);
220 if (!UsedVar || !UsedVar->hasInitializer())
222 if (isa<ConstantAggregateZero>(UsedVar->getInitializer())) {
223 assert(UsedVar->use_empty());
224 UsedVar->eraseFromParent();
227 auto *OldUsedVal = cast<ConstantArray>(UsedVar->getInitializer());
228 std::vector<Constant *> Used;
229 for (Value *V : OldUsedVal->operand_values()) {
230 Constant *Op = cast<Constant>(V->stripPointerCasts());
231 if (!Op->isNullValue()) {
232 Used.push_back(cast<Constant>(V));
235 auto *NewValElemTy = OldUsedVal->getType()->getElementType();
236 auto *NewValTy = ArrayType::get(NewValElemTy, Used.size());
237 auto *NewUsedVal = ConstantArray::get(NewValTy, Used);
238 UsedVar->mutateType(NewUsedVal->getType()->getPointerTo());
239 UsedVar->setInitializer(NewUsedVal);
242 bool ReduceCrashingFunctions::TestFuncs(std::vector<Function *> &Funcs) {
243 // If main isn't present, claim there is no problem.
244 if (KeepMain && !is_contained(Funcs, BD.getProgram()->getFunction("main")))
247 // Clone the program to try hacking it apart...
248 ValueToValueMapTy VMap;
249 Module *M = CloneModule(BD.getProgram(), VMap).release();
251 // Convert list to set for fast lookup...
252 std::set<Function *> Functions;
253 for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
254 Function *CMF = cast<Function>(VMap[Funcs[i]]);
255 assert(CMF && "Function not in module?!");
256 assert(CMF->getFunctionType() == Funcs[i]->getFunctionType() && "wrong ty");
257 assert(CMF->getName() == Funcs[i]->getName() && "wrong name");
258 Functions.insert(CMF);
261 outs() << "Checking for crash with only these functions: ";
262 PrintFunctionList(Funcs);
264 if (!ReplaceFuncsWithNull) {
265 // Loop over and delete any functions which we aren't supposed to be playing
267 for (Function &I : *M)
268 if (!I.isDeclaration() && !Functions.count(&I))
269 DeleteFunctionBody(&I);
271 std::vector<GlobalValue *> ToRemove;
272 // First, remove aliases to functions we're about to purge.
273 for (GlobalAlias &Alias : M->aliases()) {
274 GlobalObject *Root = Alias.getBaseObject();
275 Function *F = dyn_cast_or_null<Function>(Root);
277 if (Functions.count(F))
278 // We're keeping this function.
280 } else if (Root->isNullValue()) {
281 // This referenced a globalalias that we've already replaced,
282 // so we still need to replace this alias.
284 // Not a function, therefore not something we mess with.
288 PointerType *Ty = cast<PointerType>(Alias.getType());
289 Constant *Replacement = ConstantPointerNull::get(Ty);
290 Alias.replaceAllUsesWith(Replacement);
291 ToRemove.push_back(&Alias);
294 for (Function &I : *M) {
295 if (!I.isDeclaration() && !Functions.count(&I)) {
296 PointerType *Ty = cast<PointerType>(I.getType());
297 Constant *Replacement = ConstantPointerNull::get(Ty);
298 I.replaceAllUsesWith(Replacement);
299 ToRemove.push_back(&I);
303 for (auto *F : ToRemove) {
304 F->eraseFromParent();
307 // Finally, remove any null members from any global intrinsic.
308 RemoveFunctionReferences(M, "llvm.used");
309 RemoveFunctionReferences(M, "llvm.compiler.used");
311 // Try running the hacked up program...
313 BD.setNewProgram(M); // It crashed, keep the trimmed version...
315 // Make sure to use function pointers that point into the now-current
317 Funcs.assign(Functions.begin(), Functions.end());
325 /// Simplify the CFG without completely destroying it.
326 /// This is not well defined, but basically comes down to "try to eliminate
327 /// unreachable blocks and constant fold terminators without deciding that
328 /// certain undefined behavior cuts off the program at the legs".
329 void simpleSimplifyCfg(Function &F, SmallVectorImpl<BasicBlock *> &BBs) {
333 for (auto *BB : BBs) {
334 ConstantFoldTerminator(BB);
335 MergeBlockIntoPredecessor(BB);
338 // Remove unreachable blocks
339 // removeUnreachableBlocks can't be used here, it will turn various
340 // undefined behavior into unreachables, but bugpoint was the thing that
341 // generated the undefined behavior, and we don't want it to kill the entire
343 SmallPtrSet<BasicBlock *, 16> Visited;
344 for (auto *BB : depth_first(&F.getEntryBlock()))
347 SmallVector<BasicBlock *, 16> Unreachable;
349 if (!Visited.count(&BB))
350 Unreachable.push_back(&BB);
352 // The dead BB's may be in a dead cycle or otherwise have references to each
353 // other. Because of this, we have to drop all references first, then delete
355 for (auto *BB : Unreachable) {
356 for (BasicBlock *Successor : successors(&*BB))
357 if (Visited.count(Successor))
358 Successor->removePredecessor(&*BB);
359 BB->dropAllReferences();
361 for (auto *BB : Unreachable)
362 BB->eraseFromParent();
364 /// ReduceCrashingBlocks reducer - This works by setting the terminators of
365 /// all terminators except the specified basic blocks to a 'ret' instruction,
366 /// then running the simplify-cfg pass. This has the effect of chopping up
367 /// the CFG really fast which can reduce large functions quickly.
369 class ReduceCrashingBlocks : public ListReducer<const BasicBlock *> {
371 bool (*TestFn)(const BugDriver &, Module *);
374 ReduceCrashingBlocks(BugDriver &BD,
375 bool (*testFn)(const BugDriver &, Module *))
376 : BD(BD), TestFn(testFn) {}
378 Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
379 std::vector<const BasicBlock *> &Kept) override {
380 if (!Kept.empty() && TestBlocks(Kept))
382 if (!Prefix.empty() && TestBlocks(Prefix))
387 bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
391 bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock *> &BBs) {
392 // Clone the program to try hacking it apart...
393 ValueToValueMapTy VMap;
394 Module *M = CloneModule(BD.getProgram(), VMap).release();
396 // Convert list to set for fast lookup...
397 SmallPtrSet<BasicBlock *, 8> Blocks;
398 for (unsigned i = 0, e = BBs.size(); i != e; ++i)
399 Blocks.insert(cast<BasicBlock>(VMap[BBs[i]]));
401 outs() << "Checking for crash with only these blocks:";
402 unsigned NumPrint = Blocks.size();
405 for (unsigned i = 0, e = NumPrint; i != e; ++i)
406 outs() << " " << BBs[i]->getName();
407 if (NumPrint < Blocks.size())
408 outs() << "... <" << Blocks.size() << " total>";
411 // Loop over and delete any hack up any blocks that are not listed...
412 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
413 for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB)
414 if (!Blocks.count(&*BB) && BB->getTerminator()->getNumSuccessors()) {
415 // Loop over all of the successors of this block, deleting any PHI nodes
416 // that might include it.
417 for (succ_iterator SI = succ_begin(&*BB), E = succ_end(&*BB); SI != E;
419 (*SI)->removePredecessor(&*BB);
421 TerminatorInst *BBTerm = BB->getTerminator();
422 if (BBTerm->isEHPad() || BBTerm->getType()->isTokenTy())
424 if (!BBTerm->getType()->isVoidTy())
425 BBTerm->replaceAllUsesWith(Constant::getNullValue(BBTerm->getType()));
427 // Replace the old terminator instruction.
428 BB->getInstList().pop_back();
429 new UnreachableInst(BB->getContext(), &*BB);
432 // The CFG Simplifier pass may delete one of the basic blocks we are
433 // interested in. If it does we need to take the block out of the list. Make
434 // a "persistent mapping" by turning basic blocks into <function, name> pairs.
435 // This won't work well if blocks are unnamed, but that is just the risk we
437 std::vector<std::pair<std::string, std::string>> BlockInfo;
439 for (BasicBlock *BB : Blocks)
440 BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName());
442 SmallVector<BasicBlock *, 16> ToProcess;
445 if (!Blocks.count(&BB))
446 ToProcess.push_back(&BB);
447 simpleSimplifyCfg(F, ToProcess);
450 // Verify we didn't break anything
451 std::vector<std::string> Passes;
452 Passes.push_back("verify");
453 std::unique_ptr<Module> New = BD.runPassesOn(M, Passes);
456 errs() << "verify failed!\n";
461 // Try running on the hacked up program...
463 BD.setNewProgram(M); // It crashed, keep the trimmed version...
465 // Make sure to use basic block pointers that point into the now-current
466 // module, and that they don't include any deleted blocks.
468 const ValueSymbolTable &GST = M->getValueSymbolTable();
469 for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {
470 Function *F = cast<Function>(GST.lookup(BlockInfo[i].first));
471 Value *V = F->getValueSymbolTable()->lookup(BlockInfo[i].second);
472 if (V && V->getType() == Type::getLabelTy(V->getContext()))
473 BBs.push_back(cast<BasicBlock>(V));
477 delete M; // It didn't crash, try something else.
482 /// ReduceCrashingConditionals reducer - This works by changing
483 /// conditional branches to unconditional ones, then simplifying the CFG
484 /// This has the effect of chopping up the CFG really fast which can reduce
485 /// large functions quickly.
487 class ReduceCrashingConditionals : public ListReducer<const BasicBlock *> {
489 bool (*TestFn)(const BugDriver &, Module *);
493 ReduceCrashingConditionals(BugDriver &bd,
494 bool (*testFn)(const BugDriver &, Module *),
496 : BD(bd), TestFn(testFn), Direction(Direction) {}
498 Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
499 std::vector<const BasicBlock *> &Kept) override {
500 if (!Kept.empty() && TestBlocks(Kept))
502 if (!Prefix.empty() && TestBlocks(Prefix))
507 bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
511 bool ReduceCrashingConditionals::TestBlocks(
512 std::vector<const BasicBlock *> &BBs) {
513 // Clone the program to try hacking it apart...
514 ValueToValueMapTy VMap;
515 Module *M = CloneModule(BD.getProgram(), VMap).release();
517 // Convert list to set for fast lookup...
518 SmallPtrSet<const BasicBlock *, 8> Blocks;
519 for (const auto *BB : BBs)
520 Blocks.insert(cast<BasicBlock>(VMap[BB]));
522 outs() << "Checking for crash with changing conditionals to always jump to "
523 << (Direction ? "true" : "false") << ":";
524 unsigned NumPrint = Blocks.size();
527 for (unsigned i = 0, e = NumPrint; i != e; ++i)
528 outs() << " " << BBs[i]->getName();
529 if (NumPrint < Blocks.size())
530 outs() << "... <" << Blocks.size() << " total>";
533 // Loop over and delete any hack up any blocks that are not listed...
536 if (!Blocks.count(&BB)) {
537 auto *BR = dyn_cast<BranchInst>(BB.getTerminator());
538 if (!BR || !BR->isConditional())
541 BR->setCondition(ConstantInt::getTrue(BR->getContext()));
543 BR->setCondition(ConstantInt::getFalse(BR->getContext()));
546 // The following may destroy some blocks, so we save them first
547 std::vector<std::pair<std::string, std::string>> BlockInfo;
549 for (const BasicBlock *BB : Blocks)
550 BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName());
552 SmallVector<BasicBlock *, 16> ToProcess;
555 if (!Blocks.count(&BB))
556 ToProcess.push_back(&BB);
557 simpleSimplifyCfg(F, ToProcess);
560 // Verify we didn't break anything
561 std::vector<std::string> Passes;
562 Passes.push_back("verify");
563 std::unique_ptr<Module> New = BD.runPassesOn(M, Passes);
566 errs() << "verify failed!\n";
571 // Try running on the hacked up program...
573 BD.setNewProgram(M); // It crashed, keep the trimmed version...
575 // Make sure to use basic block pointers that point into the now-current
576 // module, and that they don't include any deleted blocks.
578 const ValueSymbolTable &GST = M->getValueSymbolTable();
579 for (auto &BI : BlockInfo) {
580 auto *F = cast<Function>(GST.lookup(BI.first));
581 Value *V = F->getValueSymbolTable()->lookup(BI.second);
582 if (V && V->getType() == Type::getLabelTy(V->getContext()))
583 BBs.push_back(cast<BasicBlock>(V));
587 delete M; // It didn't crash, try something else.
592 /// SimplifyCFG reducer - This works by calling SimplifyCFG on each basic block
595 class ReduceSimplifyCFG : public ListReducer<const BasicBlock *> {
597 bool (*TestFn)(const BugDriver &, Module *);
598 TargetTransformInfo TTI;
601 ReduceSimplifyCFG(BugDriver &bd, bool (*testFn)(const BugDriver &, Module *))
602 : BD(bd), TestFn(testFn), TTI(bd.getProgram()->getDataLayout()) {}
604 Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
605 std::vector<const BasicBlock *> &Kept) override {
606 if (!Kept.empty() && TestBlocks(Kept))
608 if (!Prefix.empty() && TestBlocks(Prefix))
613 bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
617 bool ReduceSimplifyCFG::TestBlocks(std::vector<const BasicBlock *> &BBs) {
618 // Clone the program to try hacking it apart...
619 ValueToValueMapTy VMap;
620 Module *M = CloneModule(BD.getProgram(), VMap).release();
622 // Convert list to set for fast lookup...
623 SmallPtrSet<const BasicBlock *, 8> Blocks;
624 for (const auto *BB : BBs)
625 Blocks.insert(cast<BasicBlock>(VMap[BB]));
627 outs() << "Checking for crash with CFG simplifying:";
628 unsigned NumPrint = Blocks.size();
631 for (unsigned i = 0, e = NumPrint; i != e; ++i)
632 outs() << " " << BBs[i]->getName();
633 if (NumPrint < Blocks.size())
634 outs() << "... <" << Blocks.size() << " total>";
637 // The following may destroy some blocks, so we save them first
638 std::vector<std::pair<std::string, std::string>> BlockInfo;
640 for (const BasicBlock *BB : Blocks)
641 BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName());
643 // Loop over and delete any hack up any blocks that are not listed...
645 // Loop over all of the basic blocks and remove them if they are unneeded.
646 for (Function::iterator BBIt = F.begin(); BBIt != F.end();) {
647 if (!Blocks.count(&*BBIt)) {
651 SimplifyCFG(&*BBIt++, TTI, 1);
653 // Verify we didn't break anything
654 std::vector<std::string> Passes;
655 Passes.push_back("verify");
656 std::unique_ptr<Module> New = BD.runPassesOn(M, Passes);
659 errs() << "verify failed!\n";
664 // Try running on the hacked up program...
666 BD.setNewProgram(M); // It crashed, keep the trimmed version...
668 // Make sure to use basic block pointers that point into the now-current
669 // module, and that they don't include any deleted blocks.
671 const ValueSymbolTable &GST = M->getValueSymbolTable();
672 for (auto &BI : BlockInfo) {
673 auto *F = cast<Function>(GST.lookup(BI.first));
674 Value *V = F->getValueSymbolTable()->lookup(BI.second);
675 if (V && V->getType() == Type::getLabelTy(V->getContext()))
676 BBs.push_back(cast<BasicBlock>(V));
680 delete M; // It didn't crash, try something else.
685 /// ReduceCrashingInstructions reducer - This works by removing the specified
686 /// non-terminator instructions and replacing them with undef.
688 class ReduceCrashingInstructions : public ListReducer<const Instruction *> {
690 bool (*TestFn)(const BugDriver &, Module *);
693 ReduceCrashingInstructions(BugDriver &bd,
694 bool (*testFn)(const BugDriver &, Module *))
695 : BD(bd), TestFn(testFn) {}
697 Expected<TestResult> doTest(std::vector<const Instruction *> &Prefix,
698 std::vector<const Instruction *> &Kept) override {
699 if (!Kept.empty() && TestInsts(Kept))
701 if (!Prefix.empty() && TestInsts(Prefix))
706 bool TestInsts(std::vector<const Instruction *> &Prefix);
710 bool ReduceCrashingInstructions::TestInsts(
711 std::vector<const Instruction *> &Insts) {
712 // Clone the program to try hacking it apart...
713 ValueToValueMapTy VMap;
714 Module *M = CloneModule(BD.getProgram(), VMap).release();
716 // Convert list to set for fast lookup...
717 SmallPtrSet<Instruction *, 32> Instructions;
718 for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
719 assert(!isa<TerminatorInst>(Insts[i]));
720 Instructions.insert(cast<Instruction>(VMap[Insts[i]]));
723 outs() << "Checking for crash with only " << Instructions.size();
724 if (Instructions.size() == 1)
725 outs() << " instruction: ";
727 outs() << " instructions: ";
729 for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI)
730 for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI)
731 for (BasicBlock::iterator I = FI->begin(), E = FI->end(); I != E;) {
732 Instruction *Inst = &*I++;
733 if (!Instructions.count(Inst) && !isa<TerminatorInst>(Inst) &&
734 !Inst->isEHPad() && !Inst->getType()->isTokenTy() &&
735 !Inst->isSwiftError()) {
736 if (!Inst->getType()->isVoidTy())
737 Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
738 Inst->eraseFromParent();
742 // Verify that this is still valid.
743 legacy::PassManager Passes;
744 Passes.add(createVerifierPass(/*FatalErrors=*/false));
747 // Try running on the hacked up program...
749 BD.setNewProgram(M); // It crashed, keep the trimmed version...
751 // Make sure to use instruction pointers that point into the now-current
752 // module, and that they don't include any deleted blocks.
754 for (Instruction *Inst : Instructions)
755 Insts.push_back(Inst);
758 delete M; // It didn't crash, try something else.
763 // Reduce the list of Named Metadata nodes. We keep this as a list of
764 // names to avoid having to convert back and forth every time.
765 class ReduceCrashingNamedMD : public ListReducer<std::string> {
767 bool (*TestFn)(const BugDriver &, Module *);
770 ReduceCrashingNamedMD(BugDriver &bd,
771 bool (*testFn)(const BugDriver &, Module *))
772 : BD(bd), TestFn(testFn) {}
774 Expected<TestResult> doTest(std::vector<std::string> &Prefix,
775 std::vector<std::string> &Kept) override {
776 if (!Kept.empty() && TestNamedMDs(Kept))
778 if (!Prefix.empty() && TestNamedMDs(Prefix))
783 bool TestNamedMDs(std::vector<std::string> &NamedMDs);
787 bool ReduceCrashingNamedMD::TestNamedMDs(std::vector<std::string> &NamedMDs) {
789 ValueToValueMapTy VMap;
790 Module *M = CloneModule(BD.getProgram(), VMap).release();
792 outs() << "Checking for crash with only these named metadata nodes:";
793 unsigned NumPrint = std::min<size_t>(NamedMDs.size(), 10);
794 for (unsigned i = 0, e = NumPrint; i != e; ++i)
795 outs() << " " << NamedMDs[i];
796 if (NumPrint < NamedMDs.size())
797 outs() << "... <" << NamedMDs.size() << " total>";
800 // Make a StringMap for faster lookup
802 for (const std::string &Name : NamedMDs)
805 // First collect all the metadata to delete in a vector, then
806 // delete them all at once to avoid invalidating the iterator
807 std::vector<NamedMDNode *> ToDelete;
808 ToDelete.reserve(M->named_metadata_size() - Names.size());
809 for (auto &NamedMD : M->named_metadata())
810 // Always keep a nonempty llvm.dbg.cu because the Verifier would complain.
811 if (!Names.count(NamedMD.getName()) &&
812 (!(NamedMD.getName() == "llvm.dbg.cu" && NamedMD.getNumOperands() > 0)))
813 ToDelete.push_back(&NamedMD);
815 for (auto *NamedMD : ToDelete)
816 NamedMD->eraseFromParent();
818 // Verify that this is still valid.
819 legacy::PassManager Passes;
820 Passes.add(createVerifierPass(/*FatalErrors=*/false));
823 // Try running on the hacked up program...
825 BD.setNewProgram(M); // It crashed, keep the trimmed version...
828 delete M; // It didn't crash, try something else.
833 // Reduce the list of operands to named metadata nodes
834 class ReduceCrashingNamedMDOps : public ListReducer<const MDNode *> {
836 bool (*TestFn)(const BugDriver &, Module *);
839 ReduceCrashingNamedMDOps(BugDriver &bd,
840 bool (*testFn)(const BugDriver &, Module *))
841 : BD(bd), TestFn(testFn) {}
843 Expected<TestResult> doTest(std::vector<const MDNode *> &Prefix,
844 std::vector<const MDNode *> &Kept) override {
845 if (!Kept.empty() && TestNamedMDOps(Kept))
847 if (!Prefix.empty() && TestNamedMDOps(Prefix))
852 bool TestNamedMDOps(std::vector<const MDNode *> &NamedMDOps);
856 bool ReduceCrashingNamedMDOps::TestNamedMDOps(
857 std::vector<const MDNode *> &NamedMDOps) {
858 // Convert list to set for fast lookup...
859 SmallPtrSet<const MDNode *, 32> OldMDNodeOps;
860 for (unsigned i = 0, e = NamedMDOps.size(); i != e; ++i) {
861 OldMDNodeOps.insert(NamedMDOps[i]);
864 outs() << "Checking for crash with only " << OldMDNodeOps.size();
865 if (OldMDNodeOps.size() == 1)
866 outs() << " named metadata operand: ";
868 outs() << " named metadata operands: ";
870 ValueToValueMapTy VMap;
871 Module *M = CloneModule(BD.getProgram(), VMap).release();
873 // This is a little wasteful. In the future it might be good if we could have
874 // these dropped during cloning.
875 for (auto &NamedMD : BD.getProgram()->named_metadata()) {
876 // Drop the old one and create a new one
877 M->eraseNamedMetadata(M->getNamedMetadata(NamedMD.getName()));
878 NamedMDNode *NewNamedMDNode =
879 M->getOrInsertNamedMetadata(NamedMD.getName());
880 for (MDNode *op : NamedMD.operands())
881 if (OldMDNodeOps.count(op))
882 NewNamedMDNode->addOperand(cast<MDNode>(MapMetadata(op, VMap)));
885 // Verify that this is still valid.
886 legacy::PassManager Passes;
887 Passes.add(createVerifierPass(/*FatalErrors=*/false));
890 // Try running on the hacked up program...
892 // Make sure to use instruction pointers that point into the now-current
893 // module, and that they don't include any deleted blocks.
895 for (const MDNode *Node : OldMDNodeOps)
896 NamedMDOps.push_back(cast<MDNode>(*VMap.getMappedMD(Node)));
898 BD.setNewProgram(M); // It crashed, keep the trimmed version...
901 delete M; // It didn't crash, try something else.
905 static Error ReduceGlobalInitializers(BugDriver &BD,
906 bool (*TestFn)(const BugDriver &,
908 if (BD.getProgram()->global_begin() != BD.getProgram()->global_end()) {
909 // Now try to reduce the number of global variable initializers in the
910 // module to something small.
911 Module *M = CloneModule(BD.getProgram()).release();
912 bool DeletedInit = false;
914 for (Module::global_iterator I = M->global_begin(), E = M->global_end();
916 if (I->hasInitializer()) {
917 DeleteGlobalInitializer(&*I);
918 I->setLinkage(GlobalValue::ExternalLinkage);
919 I->setComdat(nullptr);
924 delete M; // No change made...
926 // See if the program still causes a crash...
927 outs() << "\nChecking to see if we can delete global inits: ";
929 if (TestFn(BD, M)) { // Still crashes?
931 outs() << "\n*** Able to remove all global initializers!\n";
932 } else { // No longer crashes?
933 outs() << " - Removing all global inits hides problem!\n";
936 std::vector<GlobalVariable *> GVs;
938 for (Module::global_iterator I = BD.getProgram()->global_begin(),
939 E = BD.getProgram()->global_end();
941 if (I->hasInitializer())
944 if (GVs.size() > 1 && !BugpointIsInterrupted) {
945 outs() << "\n*** Attempting to reduce the number of global "
946 << "variables in the testcase\n";
948 unsigned OldSize = GVs.size();
949 Expected<bool> Result =
950 ReduceCrashingGlobalVariables(BD, TestFn).reduceList(GVs);
951 if (Error E = Result.takeError())
954 if (GVs.size() < OldSize)
955 BD.EmitProgressBitcode(BD.getProgram(), "reduced-global-variables");
960 return Error::success();
963 static Error ReduceInsts(BugDriver &BD,
964 bool (*TestFn)(const BugDriver &, Module *)) {
965 // Attempt to delete instructions using bisection. This should help out nasty
966 // cases with large basic blocks where the problem is at one end.
967 if (!BugpointIsInterrupted) {
968 std::vector<const Instruction *> Insts;
969 for (const Function &F : *BD.getProgram())
970 for (const BasicBlock &BB : F)
971 for (const Instruction &I : BB)
972 if (!isa<TerminatorInst>(&I))
975 Expected<bool> Result =
976 ReduceCrashingInstructions(BD, TestFn).reduceList(Insts);
977 if (Error E = Result.takeError())
981 unsigned Simplification = 2;
983 if (BugpointIsInterrupted)
984 // TODO: Should we distinguish this with an "interrupted error"?
985 return Error::success();
987 outs() << "\n*** Attempting to reduce testcase by deleting instruc"
988 << "tions: Simplification Level #" << Simplification << '\n';
990 // Now that we have deleted the functions that are unnecessary for the
991 // program, try to remove instructions that are not necessary to cause the
992 // crash. To do this, we loop through all of the instructions in the
993 // remaining functions, deleting them (replacing any values produced with
994 // nulls), and then running ADCE and SimplifyCFG. If the transformed input
995 // still triggers failure, keep deleting until we cannot trigger failure
998 unsigned InstructionsToSkipBeforeDeleting = 0;
1001 // Loop over all of the (non-terminator) instructions remaining in the
1002 // function, attempting to delete them.
1003 unsigned CurInstructionNum = 0;
1004 for (Module::const_iterator FI = BD.getProgram()->begin(),
1005 E = BD.getProgram()->end();
1007 if (!FI->isDeclaration())
1008 for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E;
1010 for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end();
1011 I != E; ++I, ++CurInstructionNum) {
1012 if (InstructionsToSkipBeforeDeleting) {
1013 --InstructionsToSkipBeforeDeleting;
1015 if (BugpointIsInterrupted)
1016 // TODO: Should this be some kind of interrupted error?
1017 return Error::success();
1019 if (I->isEHPad() || I->getType()->isTokenTy() ||
1023 outs() << "Checking instruction: " << *I;
1024 std::unique_ptr<Module> M =
1025 BD.deleteInstructionFromProgram(&*I, Simplification);
1027 // Find out if the pass still crashes on this pass...
1028 if (TestFn(BD, M.get())) {
1029 // Yup, it does, we delete the old module, and continue trying
1030 // to reduce the testcase...
1031 BD.setNewProgram(M.release());
1032 InstructionsToSkipBeforeDeleting = CurInstructionNum;
1033 goto TryAgain; // I wish I had a multi-level break here!
1038 if (InstructionsToSkipBeforeDeleting) {
1039 InstructionsToSkipBeforeDeleting = 0;
1043 } while (Simplification);
1044 BD.EmitProgressBitcode(BD.getProgram(), "reduced-instructions");
1045 return Error::success();
1048 /// DebugACrash - Given a predicate that determines whether a component crashes
1049 /// on a program, try to destructively reduce the program while still keeping
1050 /// the predicate true.
1051 static Error DebugACrash(BugDriver &BD,
1052 bool (*TestFn)(const BugDriver &, Module *)) {
1053 // See if we can get away with nuking some of the global variable initializers
1054 // in the program...
1056 if (Error E = ReduceGlobalInitializers(BD, TestFn))
1059 // Now try to reduce the number of functions in the module to something small.
1060 std::vector<Function *> Functions;
1061 for (Function &F : *BD.getProgram())
1062 if (!F.isDeclaration())
1063 Functions.push_back(&F);
1065 if (Functions.size() > 1 && !BugpointIsInterrupted) {
1066 outs() << "\n*** Attempting to reduce the number of functions "
1067 "in the testcase\n";
1069 unsigned OldSize = Functions.size();
1070 Expected<bool> Result =
1071 ReduceCrashingFunctions(BD, TestFn).reduceList(Functions);
1072 if (Error E = Result.takeError())
1075 if (Functions.size() < OldSize)
1076 BD.EmitProgressBitcode(BD.getProgram(), "reduced-function");
1079 // Attempt to change conditional branches into unconditional branches to
1080 // eliminate blocks.
1081 if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1082 std::vector<const BasicBlock *> Blocks;
1083 for (Function &F : *BD.getProgram())
1084 for (BasicBlock &BB : F)
1085 Blocks.push_back(&BB);
1086 unsigned OldSize = Blocks.size();
1087 Expected<bool> Result =
1088 ReduceCrashingConditionals(BD, TestFn, true).reduceList(Blocks);
1089 if (Error E = Result.takeError())
1091 Result = ReduceCrashingConditionals(BD, TestFn, false).reduceList(Blocks);
1092 if (Error E = Result.takeError())
1094 if (Blocks.size() < OldSize)
1095 BD.EmitProgressBitcode(BD.getProgram(), "reduced-conditionals");
1098 // Attempt to delete entire basic blocks at a time to speed up
1099 // convergence... this actually works by setting the terminator of the blocks
1100 // to a return instruction then running simplifycfg, which can potentially
1101 // shrinks the code dramatically quickly
1103 if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1104 std::vector<const BasicBlock *> Blocks;
1105 for (Function &F : *BD.getProgram())
1106 for (BasicBlock &BB : F)
1107 Blocks.push_back(&BB);
1108 unsigned OldSize = Blocks.size();
1109 Expected<bool> Result = ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks);
1110 if (Error E = Result.takeError())
1112 if (Blocks.size() < OldSize)
1113 BD.EmitProgressBitcode(BD.getProgram(), "reduced-blocks");
1116 if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1117 std::vector<const BasicBlock *> Blocks;
1118 for (Function &F : *BD.getProgram())
1119 for (BasicBlock &BB : F)
1120 Blocks.push_back(&BB);
1121 unsigned OldSize = Blocks.size();
1122 Expected<bool> Result = ReduceSimplifyCFG(BD, TestFn).reduceList(Blocks);
1123 if (Error E = Result.takeError())
1125 if (Blocks.size() < OldSize)
1126 BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplifycfg");
1129 // Attempt to delete instructions using bisection. This should help out nasty
1130 // cases with large basic blocks where the problem is at one end.
1131 if (!BugpointIsInterrupted)
1132 if (Error E = ReduceInsts(BD, TestFn))
1135 // Attempt to strip debug info metadata.
1136 auto stripMetadata = [&](std::function<bool(Module &)> strip) {
1137 std::unique_ptr<Module> M = CloneModule(BD.getProgram());
1139 if (TestFn(BD, M.get()))
1140 BD.setNewProgram(M.release());
1142 if (!NoStripDebugInfo && !BugpointIsInterrupted) {
1143 outs() << "\n*** Attempting to strip the debug info: ";
1144 stripMetadata(StripDebugInfo);
1146 if (!NoStripDebugTypeInfo && !BugpointIsInterrupted) {
1147 outs() << "\n*** Attempting to strip the debug type info: ";
1148 stripMetadata(stripNonLineTableDebugInfo);
1152 if (!BugpointIsInterrupted) {
1153 // Try to reduce the amount of global metadata (particularly debug info),
1154 // by dropping global named metadata that anchors them
1155 outs() << "\n*** Attempting to remove named metadata: ";
1156 std::vector<std::string> NamedMDNames;
1157 for (auto &NamedMD : BD.getProgram()->named_metadata())
1158 NamedMDNames.push_back(NamedMD.getName().str());
1159 Expected<bool> Result =
1160 ReduceCrashingNamedMD(BD, TestFn).reduceList(NamedMDNames);
1161 if (Error E = Result.takeError())
1165 if (!BugpointIsInterrupted) {
1166 // Now that we quickly dropped all the named metadata that doesn't
1167 // contribute to the crash, bisect the operands of the remaining ones
1168 std::vector<const MDNode *> NamedMDOps;
1169 for (auto &NamedMD : BD.getProgram()->named_metadata())
1170 for (auto op : NamedMD.operands())
1171 NamedMDOps.push_back(op);
1172 Expected<bool> Result =
1173 ReduceCrashingNamedMDOps(BD, TestFn).reduceList(NamedMDOps);
1174 if (Error E = Result.takeError())
1177 BD.EmitProgressBitcode(BD.getProgram(), "reduced-named-md");
1180 // Try to clean up the testcase by running funcresolve and globaldce...
1181 if (!BugpointIsInterrupted) {
1182 outs() << "\n*** Attempting to perform final cleanups: ";
1183 Module *M = CloneModule(BD.getProgram()).release();
1184 M = BD.performFinalCleanups(M, true).release();
1186 // Find out if the pass still crashes on the cleaned up program...
1187 if (TestFn(BD, M)) {
1188 BD.setNewProgram(M); // Yup, it does, keep the reduced version...
1194 BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplified");
1196 return Error::success();
1199 static bool TestForOptimizerCrash(const BugDriver &BD, Module *M) {
1200 return BD.runPasses(M, BD.getPassesToRun());
1203 /// debugOptimizerCrash - This method is called when some pass crashes on input.
1204 /// It attempts to prune down the testcase to something reasonable, and figure
1205 /// out exactly which pass is crashing.
1207 Error BugDriver::debugOptimizerCrash(const std::string &ID) {
1208 outs() << "\n*** Debugging optimizer crash!\n";
1210 // Reduce the list of passes which causes the optimizer to crash...
1211 if (!BugpointIsInterrupted && !DontReducePassList) {
1212 Expected<bool> Result = ReducePassList(*this).reduceList(PassesToRun);
1213 if (Error E = Result.takeError())
1217 outs() << "\n*** Found crashing pass"
1218 << (PassesToRun.size() == 1 ? ": " : "es: ")
1219 << getPassesString(PassesToRun) << '\n';
1221 EmitProgressBitcode(Program, ID);
1223 return DebugACrash(*this, TestForOptimizerCrash);
1226 static bool TestForCodeGenCrash(const BugDriver &BD, Module *M) {
1227 if (Error E = BD.compileProgram(M)) {
1229 errs() << toString(std::move(E)) << "\n";
1231 consumeError(std::move(E));
1232 errs() << "<crash>\n";
1234 return true; // Tool is still crashing.
1240 /// debugCodeGeneratorCrash - This method is called when the code generator
1241 /// crashes on an input. It attempts to reduce the input as much as possible
1242 /// while still causing the code generator to crash.
1243 Error BugDriver::debugCodeGeneratorCrash() {
1244 errs() << "*** Debugging code generator crash!\n";
1246 return DebugACrash(*this, TestForCodeGenCrash);