1 //===- CrashDebugger.cpp - Debug compilation crashes ----------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the bugpoint internals that narrow down compilation crashes
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "BugDriver.h"
15 #include "ListReducer.h"
16 #include "ToolRunner.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/StringSet.h"
19 #include "llvm/IR/CFG.h"
20 #include "llvm/IR/Constants.h"
21 #include "llvm/IR/DerivedTypes.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/LegacyPassManager.h"
24 #include "llvm/IR/Module.h"
25 #include "llvm/IR/ValueSymbolTable.h"
26 #include "llvm/IR/Verifier.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Support/CommandLine.h"
29 #include "llvm/Support/FileUtilities.h"
30 #include "llvm/Transforms/Scalar.h"
31 #include "llvm/Transforms/Utils/Cloning.h"
32 #include <set>
33 using namespace llvm;
34 
35 namespace {
36   cl::opt<bool>
37   KeepMain("keep-main",
38            cl::desc("Force function reduction to keep main"),
39            cl::init(false));
40   cl::opt<bool>
41   NoGlobalRM ("disable-global-remove",
42          cl::desc("Do not remove global variables"),
43          cl::init(false));
44 
45   cl::opt<bool>
46   ReplaceFuncsWithNull("replace-funcs-with-null",
47          cl::desc("When stubbing functions, replace all uses will null"),
48          cl::init(false));
49   cl::opt<bool>
50   DontReducePassList("disable-pass-list-reduction",
51                      cl::desc("Skip pass list reduction steps"),
52                      cl::init(false));
53 
54   cl::opt<bool> NoNamedMDRM("disable-namedmd-remove",
55                             cl::desc("Do not remove global named metadata"),
56                             cl::init(false));
57 }
58 
59 namespace llvm {
60   class ReducePassList : public ListReducer<std::string> {
61     BugDriver &BD;
62   public:
ReducePassList(BugDriver & bd)63     ReducePassList(BugDriver &bd) : BD(bd) {}
64 
65     // doTest - Return true iff running the "removed" passes succeeds, and
66     // running the "Kept" passes fail when run on the output of the "removed"
67     // passes.  If we return true, we update the current module of bugpoint.
68     //
69     TestResult doTest(std::vector<std::string> &Removed,
70                       std::vector<std::string> &Kept,
71                       std::string &Error) override;
72   };
73 }
74 
75 ReducePassList::TestResult
doTest(std::vector<std::string> & Prefix,std::vector<std::string> & Suffix,std::string & Error)76 ReducePassList::doTest(std::vector<std::string> &Prefix,
77                        std::vector<std::string> &Suffix,
78                        std::string &Error) {
79   std::string PrefixOutput;
80   Module *OrigProgram = nullptr;
81   if (!Prefix.empty()) {
82     outs() << "Checking to see if these passes crash: "
83            << getPassesString(Prefix) << ": ";
84     if (BD.runPasses(BD.getProgram(), Prefix, PrefixOutput))
85       return KeepPrefix;
86 
87     OrigProgram = BD.Program;
88 
89     BD.Program = parseInputFile(PrefixOutput, BD.getContext()).release();
90     if (BD.Program == nullptr) {
91       errs() << BD.getToolName() << ": Error reading bitcode file '"
92              << PrefixOutput << "'!\n";
93       exit(1);
94     }
95     sys::fs::remove(PrefixOutput);
96   }
97 
98   outs() << "Checking to see if these passes crash: "
99          << getPassesString(Suffix) << ": ";
100 
101   if (BD.runPasses(BD.getProgram(), Suffix)) {
102     delete OrigProgram;            // The suffix crashes alone...
103     return KeepSuffix;
104   }
105 
106   // Nothing failed, restore state...
107   if (OrigProgram) {
108     delete BD.Program;
109     BD.Program = OrigProgram;
110   }
111   return NoFailure;
112 }
113 
114 namespace {
115   /// ReduceCrashingGlobalVariables - This works by removing the global
116   /// variable's initializer and seeing if the program still crashes. If it
117   /// does, then we keep that program and try again.
118   ///
119   class ReduceCrashingGlobalVariables : public ListReducer<GlobalVariable*> {
120     BugDriver &BD;
121     bool (*TestFn)(const BugDriver &, Module *);
122   public:
ReduceCrashingGlobalVariables(BugDriver & bd,bool (* testFn)(const BugDriver &,Module *))123     ReduceCrashingGlobalVariables(BugDriver &bd,
124                                   bool (*testFn)(const BugDriver &, Module *))
125       : BD(bd), TestFn(testFn) {}
126 
doTest(std::vector<GlobalVariable * > & Prefix,std::vector<GlobalVariable * > & Kept,std::string & Error)127     TestResult doTest(std::vector<GlobalVariable*> &Prefix,
128                       std::vector<GlobalVariable*> &Kept,
129                       std::string &Error) override {
130       if (!Kept.empty() && TestGlobalVariables(Kept))
131         return KeepSuffix;
132       if (!Prefix.empty() && TestGlobalVariables(Prefix))
133         return KeepPrefix;
134       return NoFailure;
135     }
136 
137     bool TestGlobalVariables(std::vector<GlobalVariable*> &GVs);
138   };
139 }
140 
141 bool
TestGlobalVariables(std::vector<GlobalVariable * > & GVs)142 ReduceCrashingGlobalVariables::TestGlobalVariables(
143                               std::vector<GlobalVariable*> &GVs) {
144   // Clone the program to try hacking it apart...
145   ValueToValueMapTy VMap;
146   Module *M = CloneModule(BD.getProgram(), VMap).release();
147 
148   // Convert list to set for fast lookup...
149   std::set<GlobalVariable*> GVSet;
150 
151   for (unsigned i = 0, e = GVs.size(); i != e; ++i) {
152     GlobalVariable* CMGV = cast<GlobalVariable>(VMap[GVs[i]]);
153     assert(CMGV && "Global Variable not in module?!");
154     GVSet.insert(CMGV);
155   }
156 
157   outs() << "Checking for crash with only these global variables: ";
158   PrintGlobalVariableList(GVs);
159   outs() << ": ";
160 
161   // Loop over and delete any global variables which we aren't supposed to be
162   // playing with...
163   for (GlobalVariable &I : M->globals())
164     if (I.hasInitializer() && !GVSet.count(&I)) {
165       DeleteGlobalInitializer(&I);
166       I.setLinkage(GlobalValue::ExternalLinkage);
167     }
168 
169   // Try running the hacked up program...
170   if (TestFn(BD, M)) {
171     BD.setNewProgram(M);        // It crashed, keep the trimmed version...
172 
173     // Make sure to use global variable pointers that point into the now-current
174     // module.
175     GVs.assign(GVSet.begin(), GVSet.end());
176     return true;
177   }
178 
179   delete M;
180   return false;
181 }
182 
183 namespace {
184   /// ReduceCrashingFunctions reducer - This works by removing functions and
185   /// seeing if the program still crashes. If it does, then keep the newer,
186   /// smaller program.
187   ///
188   class ReduceCrashingFunctions : public ListReducer<Function*> {
189     BugDriver &BD;
190     bool (*TestFn)(const BugDriver &, Module *);
191   public:
ReduceCrashingFunctions(BugDriver & bd,bool (* testFn)(const BugDriver &,Module *))192     ReduceCrashingFunctions(BugDriver &bd,
193                             bool (*testFn)(const BugDriver &, Module *))
194       : BD(bd), TestFn(testFn) {}
195 
doTest(std::vector<Function * > & Prefix,std::vector<Function * > & Kept,std::string & Error)196     TestResult doTest(std::vector<Function*> &Prefix,
197                       std::vector<Function*> &Kept,
198                       std::string &Error) override {
199       if (!Kept.empty() && TestFuncs(Kept))
200         return KeepSuffix;
201       if (!Prefix.empty() && TestFuncs(Prefix))
202         return KeepPrefix;
203       return NoFailure;
204     }
205 
206     bool TestFuncs(std::vector<Function*> &Prefix);
207   };
208 }
209 
RemoveFunctionReferences(Module * M,const char * Name)210 static void RemoveFunctionReferences(Module *M, const char* Name) {
211   auto *UsedVar = M->getGlobalVariable(Name, true);
212   if (!UsedVar || !UsedVar->hasInitializer()) return;
213   if (isa<ConstantAggregateZero>(UsedVar->getInitializer())) {
214     assert(UsedVar->use_empty());
215     UsedVar->eraseFromParent();
216     return;
217   }
218   auto *OldUsedVal = cast<ConstantArray>(UsedVar->getInitializer());
219   std::vector<Constant*> Used;
220   for(Value *V : OldUsedVal->operand_values()) {
221     Constant *Op = cast<Constant>(V->stripPointerCasts());
222     if(!Op->isNullValue()) {
223       Used.push_back(cast<Constant>(V));
224     }
225   }
226   auto *NewValElemTy = OldUsedVal->getType()->getElementType();
227   auto *NewValTy = ArrayType::get(NewValElemTy, Used.size());
228   auto *NewUsedVal = ConstantArray::get(NewValTy, Used);
229   UsedVar->mutateType(NewUsedVal->getType()->getPointerTo());
230   UsedVar->setInitializer(NewUsedVal);
231 }
232 
TestFuncs(std::vector<Function * > & Funcs)233 bool ReduceCrashingFunctions::TestFuncs(std::vector<Function*> &Funcs) {
234   // If main isn't present, claim there is no problem.
235   if (KeepMain && std::find(Funcs.begin(), Funcs.end(),
236                             BD.getProgram()->getFunction("main")) ==
237                       Funcs.end())
238     return false;
239 
240   // Clone the program to try hacking it apart...
241   ValueToValueMapTy VMap;
242   Module *M = CloneModule(BD.getProgram(), VMap).release();
243 
244   // Convert list to set for fast lookup...
245   std::set<Function*> Functions;
246   for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
247     Function *CMF = cast<Function>(VMap[Funcs[i]]);
248     assert(CMF && "Function not in module?!");
249     assert(CMF->getFunctionType() == Funcs[i]->getFunctionType() && "wrong ty");
250     assert(CMF->getName() == Funcs[i]->getName() && "wrong name");
251     Functions.insert(CMF);
252   }
253 
254   outs() << "Checking for crash with only these functions: ";
255   PrintFunctionList(Funcs);
256   outs() << ": ";
257   if (!ReplaceFuncsWithNull) {
258     // Loop over and delete any functions which we aren't supposed to be playing
259     // with...
260     for (Function &I : *M)
261       if (!I.isDeclaration() && !Functions.count(&I))
262         DeleteFunctionBody(&I);
263   } else {
264     std::vector<GlobalValue*> ToRemove;
265     // First, remove aliases to functions we're about to purge.
266     for (GlobalAlias &Alias : M->aliases()) {
267       Constant *Root = Alias.getAliasee()->stripPointerCasts();
268       Function *F = dyn_cast<Function>(Root);
269       if (F) {
270         if (Functions.count(F))
271           // We're keeping this function.
272           continue;
273       } else if (Root->isNullValue()) {
274         // This referenced a globalalias that we've already replaced,
275         // so we still need to replace this alias.
276       } else if (!F) {
277         // Not a function, therefore not something we mess with.
278         continue;
279       }
280 
281       PointerType *Ty = cast<PointerType>(Alias.getType());
282       Constant *Replacement = ConstantPointerNull::get(Ty);
283       Alias.replaceAllUsesWith(Replacement);
284       ToRemove.push_back(&Alias);
285     }
286 
287     for (Function &I : *M) {
288       if (!I.isDeclaration() && !Functions.count(&I)) {
289         PointerType *Ty = cast<PointerType>(I.getType());
290         Constant *Replacement = ConstantPointerNull::get(Ty);
291         I.replaceAllUsesWith(Replacement);
292         ToRemove.push_back(&I);
293       }
294     }
295 
296     for (auto *F : ToRemove) {
297       F->eraseFromParent();
298     }
299 
300     // Finally, remove any null members from any global intrinsic.
301     RemoveFunctionReferences(M, "llvm.used");
302     RemoveFunctionReferences(M, "llvm.compiler.used");
303   }
304   // Try running the hacked up program...
305   if (TestFn(BD, M)) {
306     BD.setNewProgram(M);        // It crashed, keep the trimmed version...
307 
308     // Make sure to use function pointers that point into the now-current
309     // module.
310     Funcs.assign(Functions.begin(), Functions.end());
311     return true;
312   }
313   delete M;
314   return false;
315 }
316 
317 
318 namespace {
319   /// ReduceCrashingBlocks reducer - This works by setting the terminators of
320   /// all terminators except the specified basic blocks to a 'ret' instruction,
321   /// then running the simplify-cfg pass.  This has the effect of chopping up
322   /// the CFG really fast which can reduce large functions quickly.
323   ///
324   class ReduceCrashingBlocks : public ListReducer<const BasicBlock*> {
325     BugDriver &BD;
326     bool (*TestFn)(const BugDriver &, Module *);
327   public:
ReduceCrashingBlocks(BugDriver & bd,bool (* testFn)(const BugDriver &,Module *))328     ReduceCrashingBlocks(BugDriver &bd,
329                          bool (*testFn)(const BugDriver &, Module *))
330       : BD(bd), TestFn(testFn) {}
331 
doTest(std::vector<const BasicBlock * > & Prefix,std::vector<const BasicBlock * > & Kept,std::string & Error)332     TestResult doTest(std::vector<const BasicBlock*> &Prefix,
333                       std::vector<const BasicBlock*> &Kept,
334                       std::string &Error) override {
335       if (!Kept.empty() && TestBlocks(Kept))
336         return KeepSuffix;
337       if (!Prefix.empty() && TestBlocks(Prefix))
338         return KeepPrefix;
339       return NoFailure;
340     }
341 
342     bool TestBlocks(std::vector<const BasicBlock*> &Prefix);
343   };
344 }
345 
TestBlocks(std::vector<const BasicBlock * > & BBs)346 bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock*> &BBs) {
347   // Clone the program to try hacking it apart...
348   ValueToValueMapTy VMap;
349   Module *M = CloneModule(BD.getProgram(), VMap).release();
350 
351   // Convert list to set for fast lookup...
352   SmallPtrSet<BasicBlock*, 8> Blocks;
353   for (unsigned i = 0, e = BBs.size(); i != e; ++i)
354     Blocks.insert(cast<BasicBlock>(VMap[BBs[i]]));
355 
356   outs() << "Checking for crash with only these blocks:";
357   unsigned NumPrint = Blocks.size();
358   if (NumPrint > 10) NumPrint = 10;
359   for (unsigned i = 0, e = NumPrint; i != e; ++i)
360     outs() << " " << BBs[i]->getName();
361   if (NumPrint < Blocks.size())
362     outs() << "... <" << Blocks.size() << " total>";
363   outs() << ": ";
364 
365   // Loop over and delete any hack up any blocks that are not listed...
366   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
367     for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB)
368       if (!Blocks.count(&*BB) && BB->getTerminator()->getNumSuccessors()) {
369         // Loop over all of the successors of this block, deleting any PHI nodes
370         // that might include it.
371         for (succ_iterator SI = succ_begin(&*BB), E = succ_end(&*BB); SI != E;
372              ++SI)
373           (*SI)->removePredecessor(&*BB);
374 
375         TerminatorInst *BBTerm = BB->getTerminator();
376         if (BBTerm->isEHPad())
377           continue;
378         if (!BBTerm->getType()->isVoidTy() && !BBTerm->getType()->isTokenTy())
379           BBTerm->replaceAllUsesWith(Constant::getNullValue(BBTerm->getType()));
380 
381         // Replace the old terminator instruction.
382         BB->getInstList().pop_back();
383         new UnreachableInst(BB->getContext(), &*BB);
384       }
385 
386   // The CFG Simplifier pass may delete one of the basic blocks we are
387   // interested in.  If it does we need to take the block out of the list.  Make
388   // a "persistent mapping" by turning basic blocks into <function, name> pairs.
389   // This won't work well if blocks are unnamed, but that is just the risk we
390   // have to take.
391   std::vector<std::pair<std::string, std::string> > BlockInfo;
392 
393   for (BasicBlock *BB : Blocks)
394     BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName());
395 
396   // Now run the CFG simplify pass on the function...
397   std::vector<std::string> Passes;
398   Passes.push_back("simplifycfg");
399   Passes.push_back("verify");
400   std::unique_ptr<Module> New = BD.runPassesOn(M, Passes);
401   delete M;
402   if (!New) {
403     errs() << "simplifycfg failed!\n";
404     exit(1);
405   }
406   M = New.release();
407 
408   // Try running on the hacked up program...
409   if (TestFn(BD, M)) {
410     BD.setNewProgram(M);      // It crashed, keep the trimmed version...
411 
412     // Make sure to use basic block pointers that point into the now-current
413     // module, and that they don't include any deleted blocks.
414     BBs.clear();
415     const ValueSymbolTable &GST = M->getValueSymbolTable();
416     for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {
417       Function *F = cast<Function>(GST.lookup(BlockInfo[i].first));
418       ValueSymbolTable &ST = F->getValueSymbolTable();
419       Value* V = ST.lookup(BlockInfo[i].second);
420       if (V && V->getType() == Type::getLabelTy(V->getContext()))
421         BBs.push_back(cast<BasicBlock>(V));
422     }
423     return true;
424   }
425   delete M;  // It didn't crash, try something else.
426   return false;
427 }
428 
429 namespace {
430   /// ReduceCrashingInstructions reducer - This works by removing the specified
431   /// non-terminator instructions and replacing them with undef.
432   ///
433   class ReduceCrashingInstructions : public ListReducer<const Instruction*> {
434     BugDriver &BD;
435     bool (*TestFn)(const BugDriver &, Module *);
436   public:
ReduceCrashingInstructions(BugDriver & bd,bool (* testFn)(const BugDriver &,Module *))437     ReduceCrashingInstructions(BugDriver &bd,
438                                bool (*testFn)(const BugDriver &, Module *))
439       : BD(bd), TestFn(testFn) {}
440 
doTest(std::vector<const Instruction * > & Prefix,std::vector<const Instruction * > & Kept,std::string & Error)441     TestResult doTest(std::vector<const Instruction*> &Prefix,
442                       std::vector<const Instruction*> &Kept,
443                       std::string &Error) override {
444       if (!Kept.empty() && TestInsts(Kept))
445         return KeepSuffix;
446       if (!Prefix.empty() && TestInsts(Prefix))
447         return KeepPrefix;
448       return NoFailure;
449     }
450 
451     bool TestInsts(std::vector<const Instruction*> &Prefix);
452   };
453 }
454 
TestInsts(std::vector<const Instruction * > & Insts)455 bool ReduceCrashingInstructions::TestInsts(std::vector<const Instruction*>
456                                            &Insts) {
457   // Clone the program to try hacking it apart...
458   ValueToValueMapTy VMap;
459   Module *M = CloneModule(BD.getProgram(), VMap).release();
460 
461   // Convert list to set for fast lookup...
462   SmallPtrSet<Instruction*, 64> Instructions;
463   for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
464     assert(!isa<TerminatorInst>(Insts[i]));
465     Instructions.insert(cast<Instruction>(VMap[Insts[i]]));
466   }
467 
468   outs() << "Checking for crash with only " << Instructions.size();
469   if (Instructions.size() == 1)
470     outs() << " instruction: ";
471   else
472     outs() << " instructions: ";
473 
474   for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI)
475     for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI)
476       for (BasicBlock::iterator I = FI->begin(), E = FI->end(); I != E;) {
477         Instruction *Inst = &*I++;
478         if (!Instructions.count(Inst) && !isa<TerminatorInst>(Inst) &&
479             !Inst->isEHPad()) {
480           if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy())
481             Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
482           Inst->eraseFromParent();
483         }
484       }
485 
486   // Verify that this is still valid.
487   legacy::PassManager Passes;
488   Passes.add(createVerifierPass());
489   Passes.run(*M);
490 
491   // Try running on the hacked up program...
492   if (TestFn(BD, M)) {
493     BD.setNewProgram(M);      // It crashed, keep the trimmed version...
494 
495     // Make sure to use instruction pointers that point into the now-current
496     // module, and that they don't include any deleted blocks.
497     Insts.clear();
498     for (Instruction *Inst : Instructions)
499       Insts.push_back(Inst);
500     return true;
501   }
502   delete M;  // It didn't crash, try something else.
503   return false;
504 }
505 
506 namespace {
507 // Reduce the list of Named Metadata nodes. We keep this as a list of
508 // names to avoid having to convert back and forth every time.
509 class ReduceCrashingNamedMD : public ListReducer<std::string> {
510   BugDriver &BD;
511   bool (*TestFn)(const BugDriver &, Module *);
512 
513 public:
ReduceCrashingNamedMD(BugDriver & bd,bool (* testFn)(const BugDriver &,Module *))514   ReduceCrashingNamedMD(BugDriver &bd,
515                         bool (*testFn)(const BugDriver &, Module *))
516       : BD(bd), TestFn(testFn) {}
517 
doTest(std::vector<std::string> & Prefix,std::vector<std::string> & Kept,std::string & Error)518   TestResult doTest(std::vector<std::string> &Prefix,
519                     std::vector<std::string> &Kept,
520                     std::string &Error) override {
521     if (!Kept.empty() && TestNamedMDs(Kept))
522       return KeepSuffix;
523     if (!Prefix.empty() && TestNamedMDs(Prefix))
524       return KeepPrefix;
525     return NoFailure;
526   }
527 
528   bool TestNamedMDs(std::vector<std::string> &NamedMDs);
529 };
530 }
531 
TestNamedMDs(std::vector<std::string> & NamedMDs)532 bool ReduceCrashingNamedMD::TestNamedMDs(std::vector<std::string> &NamedMDs) {
533 
534   ValueToValueMapTy VMap;
535   Module *M = CloneModule(BD.getProgram(), VMap).release();
536 
537   outs() << "Checking for crash with only these named metadata nodes:";
538   unsigned NumPrint = std::min<size_t>(NamedMDs.size(), 10);
539   for (unsigned i = 0, e = NumPrint; i != e; ++i)
540     outs() << " " << NamedMDs[i];
541   if (NumPrint < NamedMDs.size())
542     outs() << "... <" << NamedMDs.size() << " total>";
543   outs() << ": ";
544 
545   // Make a StringMap for faster lookup
546   StringSet<> Names;
547   for (const std::string &Name : NamedMDs)
548     Names.insert(Name);
549 
550   // First collect all the metadata to delete in a vector, then
551   // delete them all at once to avoid invalidating the iterator
552   std::vector<NamedMDNode *> ToDelete;
553   ToDelete.reserve(M->named_metadata_size() - Names.size());
554   for (auto &NamedMD : M->named_metadata())
555     if (!Names.count(NamedMD.getName()))
556       ToDelete.push_back(&NamedMD);
557 
558   for (auto *NamedMD : ToDelete)
559     NamedMD->eraseFromParent();
560 
561   // Verify that this is still valid.
562   legacy::PassManager Passes;
563   Passes.add(createVerifierPass());
564   Passes.run(*M);
565 
566   // Try running on the hacked up program...
567   if (TestFn(BD, M)) {
568     BD.setNewProgram(M); // It crashed, keep the trimmed version...
569     return true;
570   }
571   delete M; // It didn't crash, try something else.
572   return false;
573 }
574 
575 namespace {
576 // Reduce the list of operands to named metadata nodes
577 class ReduceCrashingNamedMDOps : public ListReducer<const MDNode *> {
578   BugDriver &BD;
579   bool (*TestFn)(const BugDriver &, Module *);
580 
581 public:
ReduceCrashingNamedMDOps(BugDriver & bd,bool (* testFn)(const BugDriver &,Module *))582   ReduceCrashingNamedMDOps(BugDriver &bd,
583                            bool (*testFn)(const BugDriver &, Module *))
584       : BD(bd), TestFn(testFn) {}
585 
doTest(std::vector<const MDNode * > & Prefix,std::vector<const MDNode * > & Kept,std::string & Error)586   TestResult doTest(std::vector<const MDNode *> &Prefix,
587                     std::vector<const MDNode *> &Kept,
588                     std::string &Error) override {
589     if (!Kept.empty() && TestNamedMDOps(Kept))
590       return KeepSuffix;
591     if (!Prefix.empty() && TestNamedMDOps(Prefix))
592       return KeepPrefix;
593     return NoFailure;
594   }
595 
596   bool TestNamedMDOps(std::vector<const MDNode *> &NamedMDOps);
597 };
598 }
599 
TestNamedMDOps(std::vector<const MDNode * > & NamedMDOps)600 bool ReduceCrashingNamedMDOps::TestNamedMDOps(
601     std::vector<const MDNode *> &NamedMDOps) {
602   // Convert list to set for fast lookup...
603   SmallPtrSet<const MDNode *, 64> OldMDNodeOps;
604   for (unsigned i = 0, e = NamedMDOps.size(); i != e; ++i) {
605     OldMDNodeOps.insert(NamedMDOps[i]);
606   }
607 
608   outs() << "Checking for crash with only " << OldMDNodeOps.size();
609   if (OldMDNodeOps.size() == 1)
610     outs() << " named metadata operand: ";
611   else
612     outs() << " named metadata operands: ";
613 
614   ValueToValueMapTy VMap;
615   Module *M = CloneModule(BD.getProgram(), VMap).release();
616 
617   // This is a little wasteful. In the future it might be good if we could have
618   // these dropped during cloning.
619   for (auto &NamedMD : BD.getProgram()->named_metadata()) {
620     // Drop the old one and create a new one
621     M->eraseNamedMetadata(M->getNamedMetadata(NamedMD.getName()));
622     NamedMDNode *NewNamedMDNode =
623         M->getOrInsertNamedMetadata(NamedMD.getName());
624     for (MDNode *op : NamedMD.operands())
625       if (OldMDNodeOps.count(op))
626         NewNamedMDNode->addOperand(cast<MDNode>(MapMetadata(op, VMap)));
627   }
628 
629   // Verify that this is still valid.
630   legacy::PassManager Passes;
631   Passes.add(createVerifierPass());
632   Passes.run(*M);
633 
634   // Try running on the hacked up program...
635   if (TestFn(BD, M)) {
636     // Make sure to use instruction pointers that point into the now-current
637     // module, and that they don't include any deleted blocks.
638     NamedMDOps.clear();
639     for (const MDNode *Node : OldMDNodeOps)
640       NamedMDOps.push_back(cast<MDNode>(VMap.MD()[Node].get()));
641 
642     BD.setNewProgram(M); // It crashed, keep the trimmed version...
643     return true;
644   }
645   delete M; // It didn't crash, try something else.
646   return false;
647 }
648 
649 /// DebugACrash - Given a predicate that determines whether a component crashes
650 /// on a program, try to destructively reduce the program while still keeping
651 /// the predicate true.
DebugACrash(BugDriver & BD,bool (* TestFn)(const BugDriver &,Module *),std::string & Error)652 static bool DebugACrash(BugDriver &BD,
653                         bool (*TestFn)(const BugDriver &, Module *),
654                         std::string &Error) {
655   // See if we can get away with nuking some of the global variable initializers
656   // in the program...
657   if (!NoGlobalRM &&
658       BD.getProgram()->global_begin() != BD.getProgram()->global_end()) {
659     // Now try to reduce the number of global variable initializers in the
660     // module to something small.
661     Module *M = CloneModule(BD.getProgram()).release();
662     bool DeletedInit = false;
663 
664     for (Module::global_iterator I = M->global_begin(), E = M->global_end();
665          I != E; ++I)
666       if (I->hasInitializer()) {
667         DeleteGlobalInitializer(&*I);
668         I->setLinkage(GlobalValue::ExternalLinkage);
669         DeletedInit = true;
670       }
671 
672     if (!DeletedInit) {
673       delete M;  // No change made...
674     } else {
675       // See if the program still causes a crash...
676       outs() << "\nChecking to see if we can delete global inits: ";
677 
678       if (TestFn(BD, M)) {      // Still crashes?
679         BD.setNewProgram(M);
680         outs() << "\n*** Able to remove all global initializers!\n";
681       } else {                  // No longer crashes?
682         outs() << "  - Removing all global inits hides problem!\n";
683         delete M;
684 
685         std::vector<GlobalVariable*> GVs;
686 
687         for (Module::global_iterator I = BD.getProgram()->global_begin(),
688                E = BD.getProgram()->global_end(); I != E; ++I)
689           if (I->hasInitializer())
690             GVs.push_back(&*I);
691 
692         if (GVs.size() > 1 && !BugpointIsInterrupted) {
693           outs() << "\n*** Attempting to reduce the number of global "
694                     << "variables in the testcase\n";
695 
696           unsigned OldSize = GVs.size();
697           ReduceCrashingGlobalVariables(BD, TestFn).reduceList(GVs, Error);
698           if (!Error.empty())
699             return true;
700 
701           if (GVs.size() < OldSize)
702             BD.EmitProgressBitcode(BD.getProgram(), "reduced-global-variables");
703         }
704       }
705     }
706   }
707 
708   // Now try to reduce the number of functions in the module to something small.
709   std::vector<Function*> Functions;
710   for (Function &F : *BD.getProgram())
711     if (!F.isDeclaration())
712       Functions.push_back(&F);
713 
714   if (Functions.size() > 1 && !BugpointIsInterrupted) {
715     outs() << "\n*** Attempting to reduce the number of functions "
716       "in the testcase\n";
717 
718     unsigned OldSize = Functions.size();
719     ReduceCrashingFunctions(BD, TestFn).reduceList(Functions, Error);
720 
721     if (Functions.size() < OldSize)
722       BD.EmitProgressBitcode(BD.getProgram(), "reduced-function");
723   }
724 
725   // Attempt to delete entire basic blocks at a time to speed up
726   // convergence... this actually works by setting the terminator of the blocks
727   // to a return instruction then running simplifycfg, which can potentially
728   // shrinks the code dramatically quickly
729   //
730   if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
731     std::vector<const BasicBlock*> Blocks;
732     for (Function &F : *BD.getProgram())
733       for (BasicBlock &BB : F)
734         Blocks.push_back(&BB);
735     unsigned OldSize = Blocks.size();
736     ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks, Error);
737     if (Blocks.size() < OldSize)
738       BD.EmitProgressBitcode(BD.getProgram(), "reduced-blocks");
739   }
740 
741   // Attempt to delete instructions using bisection. This should help out nasty
742   // cases with large basic blocks where the problem is at one end.
743   if (!BugpointIsInterrupted) {
744     std::vector<const Instruction*> Insts;
745     for (const Function &F : *BD.getProgram())
746       for (const BasicBlock &BB : F)
747         for (const Instruction &I : BB)
748           if (!isa<TerminatorInst>(&I))
749             Insts.push_back(&I);
750 
751     ReduceCrashingInstructions(BD, TestFn).reduceList(Insts, Error);
752   }
753 
754   // FIXME: This should use the list reducer to converge faster by deleting
755   // larger chunks of instructions at a time!
756   unsigned Simplification = 2;
757   do {
758     if (BugpointIsInterrupted) break;
759     --Simplification;
760     outs() << "\n*** Attempting to reduce testcase by deleting instruc"
761            << "tions: Simplification Level #" << Simplification << '\n';
762 
763     // Now that we have deleted the functions that are unnecessary for the
764     // program, try to remove instructions that are not necessary to cause the
765     // crash.  To do this, we loop through all of the instructions in the
766     // remaining functions, deleting them (replacing any values produced with
767     // nulls), and then running ADCE and SimplifyCFG.  If the transformed input
768     // still triggers failure, keep deleting until we cannot trigger failure
769     // anymore.
770     //
771     unsigned InstructionsToSkipBeforeDeleting = 0;
772   TryAgain:
773 
774     // Loop over all of the (non-terminator) instructions remaining in the
775     // function, attempting to delete them.
776     unsigned CurInstructionNum = 0;
777     for (Module::const_iterator FI = BD.getProgram()->begin(),
778            E = BD.getProgram()->end(); FI != E; ++FI)
779       if (!FI->isDeclaration())
780         for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E;
781              ++BI)
782           for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end();
783                I != E; ++I, ++CurInstructionNum) {
784             if (InstructionsToSkipBeforeDeleting) {
785               --InstructionsToSkipBeforeDeleting;
786             } else {
787               if (BugpointIsInterrupted) goto ExitLoops;
788 
789               if (I->isEHPad() || I->getType()->isTokenTy())
790                 continue;
791 
792               outs() << "Checking instruction: " << *I;
793               std::unique_ptr<Module> M =
794                   BD.deleteInstructionFromProgram(&*I, Simplification);
795 
796               // Find out if the pass still crashes on this pass...
797               if (TestFn(BD, M.get())) {
798                 // Yup, it does, we delete the old module, and continue trying
799                 // to reduce the testcase...
800                 BD.setNewProgram(M.release());
801                 InstructionsToSkipBeforeDeleting = CurInstructionNum;
802                 goto TryAgain;  // I wish I had a multi-level break here!
803               }
804             }
805           }
806 
807     if (InstructionsToSkipBeforeDeleting) {
808       InstructionsToSkipBeforeDeleting = 0;
809       goto TryAgain;
810     }
811 
812   } while (Simplification);
813 
814   if (!NoNamedMDRM) {
815     BD.EmitProgressBitcode(BD.getProgram(), "reduced-instructions");
816 
817     if (!BugpointIsInterrupted) {
818       // Try to reduce the amount of global metadata (particularly debug info),
819       // by dropping global named metadata that anchors them
820       outs() << "\n*** Attempting to remove named metadata: ";
821       std::vector<std::string> NamedMDNames;
822       for (auto &NamedMD : BD.getProgram()->named_metadata())
823         NamedMDNames.push_back(NamedMD.getName().str());
824       ReduceCrashingNamedMD(BD, TestFn).reduceList(NamedMDNames, Error);
825     }
826 
827     if (!BugpointIsInterrupted) {
828       // Now that we quickly dropped all the named metadata that doesn't
829       // contribute to the crash, bisect the operands of the remaining ones
830       std::vector<const MDNode *> NamedMDOps;
831       for (auto &NamedMD : BD.getProgram()->named_metadata())
832         for (auto op : NamedMD.operands())
833           NamedMDOps.push_back(op);
834       ReduceCrashingNamedMDOps(BD, TestFn).reduceList(NamedMDOps, Error);
835     }
836   }
837 
838 ExitLoops:
839 
840   // Try to clean up the testcase by running funcresolve and globaldce...
841   if (!BugpointIsInterrupted) {
842     outs() << "\n*** Attempting to perform final cleanups: ";
843     Module *M = CloneModule(BD.getProgram()).release();
844     M = BD.performFinalCleanups(M, true).release();
845 
846     // Find out if the pass still crashes on the cleaned up program...
847     if (TestFn(BD, M)) {
848       BD.setNewProgram(M);     // Yup, it does, keep the reduced version...
849     } else {
850       delete M;
851     }
852   }
853 
854   BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplified");
855 
856   return false;
857 }
858 
TestForOptimizerCrash(const BugDriver & BD,Module * M)859 static bool TestForOptimizerCrash(const BugDriver &BD, Module *M) {
860   return BD.runPasses(M);
861 }
862 
863 /// debugOptimizerCrash - This method is called when some pass crashes on input.
864 /// It attempts to prune down the testcase to something reasonable, and figure
865 /// out exactly which pass is crashing.
866 ///
debugOptimizerCrash(const std::string & ID)867 bool BugDriver::debugOptimizerCrash(const std::string &ID) {
868   outs() << "\n*** Debugging optimizer crash!\n";
869 
870   std::string Error;
871   // Reduce the list of passes which causes the optimizer to crash...
872   if (!BugpointIsInterrupted && !DontReducePassList)
873     ReducePassList(*this).reduceList(PassesToRun, Error);
874   assert(Error.empty());
875 
876   outs() << "\n*** Found crashing pass"
877          << (PassesToRun.size() == 1 ? ": " : "es: ")
878          << getPassesString(PassesToRun) << '\n';
879 
880   EmitProgressBitcode(Program, ID);
881 
882   bool Success = DebugACrash(*this, TestForOptimizerCrash, Error);
883   assert(Error.empty());
884   return Success;
885 }
886 
TestForCodeGenCrash(const BugDriver & BD,Module * M)887 static bool TestForCodeGenCrash(const BugDriver &BD, Module *M) {
888   std::string Error;
889   BD.compileProgram(M, &Error);
890   if (!Error.empty()) {
891     errs() << "<crash>\n";
892     return true;  // Tool is still crashing.
893   }
894   errs() << '\n';
895   return false;
896 }
897 
898 /// debugCodeGeneratorCrash - This method is called when the code generator
899 /// crashes on an input.  It attempts to reduce the input as much as possible
900 /// while still causing the code generator to crash.
debugCodeGeneratorCrash(std::string & Error)901 bool BugDriver::debugCodeGeneratorCrash(std::string &Error) {
902   errs() << "*** Debugging code generator crash!\n";
903 
904   return DebugACrash(*this, TestForCodeGenCrash, Error);
905 }
906