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