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 simplifycfg 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(std::string(BB->getParent()->getName()),
503 std::string(BB->getName()));
504
505 SmallVector<BasicBlock *, 16> ToProcess;
506 for (auto &F : *M) {
507 for (auto &BB : F)
508 if (!Blocks.count(&BB))
509 ToProcess.push_back(&BB);
510 simpleSimplifyCfg(F, ToProcess);
511 ToProcess.clear();
512 }
513 // Verify we didn't break anything
514 std::vector<std::string> Passes;
515 Passes.push_back("verify");
516 std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
517 if (!New) {
518 errs() << "verify failed!\n";
519 exit(1);
520 }
521 M = std::move(New);
522
523 // Try running on the hacked up program...
524 if (TestFn(BD, M.get())) {
525 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
526
527 // Make sure to use basic block pointers that point into the now-current
528 // module, and that they don't include any deleted blocks.
529 BBs.clear();
530 const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
531 for (const auto &BI : BlockInfo) {
532 Function *F = cast<Function>(GST.lookup(BI.first));
533 Value *V = F->getValueSymbolTable()->lookup(BI.second);
534 if (V && V->getType() == Type::getLabelTy(V->getContext()))
535 BBs.push_back(cast<BasicBlock>(V));
536 }
537 return true;
538 }
539 // It didn't crash, try something else.
540 return false;
541 }
542
543 namespace {
544 /// ReduceCrashingConditionals reducer - This works by changing
545 /// conditional branches to unconditional ones, then simplifying the CFG
546 /// This has the effect of chopping up the CFG really fast which can reduce
547 /// large functions quickly.
548 ///
549 class ReduceCrashingConditionals : public ListReducer<const BasicBlock *> {
550 BugDriver &BD;
551 BugTester TestFn;
552 bool Direction;
553
554 public:
ReduceCrashingConditionals(BugDriver & bd,BugTester testFn,bool Direction)555 ReduceCrashingConditionals(BugDriver &bd, BugTester testFn, bool Direction)
556 : BD(bd), TestFn(testFn), Direction(Direction) {}
557
doTest(std::vector<const BasicBlock * > & Prefix,std::vector<const BasicBlock * > & Kept)558 Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
559 std::vector<const BasicBlock *> &Kept) override {
560 if (!Kept.empty() && TestBlocks(Kept))
561 return KeepSuffix;
562 if (!Prefix.empty() && TestBlocks(Prefix))
563 return KeepPrefix;
564 return NoFailure;
565 }
566
567 bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
568 };
569 }
570
TestBlocks(std::vector<const BasicBlock * > & BBs)571 bool ReduceCrashingConditionals::TestBlocks(
572 std::vector<const BasicBlock *> &BBs) {
573 // Clone the program to try hacking it apart...
574 ValueToValueMapTy VMap;
575 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
576
577 // Convert list to set for fast lookup...
578 SmallPtrSet<const BasicBlock *, 8> Blocks;
579 for (const auto *BB : BBs)
580 Blocks.insert(cast<BasicBlock>(VMap[BB]));
581
582 outs() << "Checking for crash with changing conditionals to always jump to "
583 << (Direction ? "true" : "false") << ":";
584 unsigned NumPrint = Blocks.size();
585 if (NumPrint > 10)
586 NumPrint = 10;
587 for (unsigned i = 0, e = NumPrint; i != e; ++i)
588 outs() << " " << BBs[i]->getName();
589 if (NumPrint < Blocks.size())
590 outs() << "... <" << Blocks.size() << " total>";
591 outs() << ": ";
592
593 // Loop over and delete any hack up any blocks that are not listed...
594 for (auto &F : *M)
595 for (auto &BB : F)
596 if (!Blocks.count(&BB)) {
597 auto *BR = dyn_cast<BranchInst>(BB.getTerminator());
598 if (!BR || !BR->isConditional())
599 continue;
600 if (Direction)
601 BR->setCondition(ConstantInt::getTrue(BR->getContext()));
602 else
603 BR->setCondition(ConstantInt::getFalse(BR->getContext()));
604 }
605
606 // The following may destroy some blocks, so we save them first
607 std::vector<std::pair<std::string, std::string>> BlockInfo;
608
609 for (const BasicBlock *BB : Blocks)
610 BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
611 std::string(BB->getName()));
612
613 SmallVector<BasicBlock *, 16> ToProcess;
614 for (auto &F : *M) {
615 for (auto &BB : F)
616 if (!Blocks.count(&BB))
617 ToProcess.push_back(&BB);
618 simpleSimplifyCfg(F, ToProcess);
619 ToProcess.clear();
620 }
621 // Verify we didn't break anything
622 std::vector<std::string> Passes;
623 Passes.push_back("verify");
624 std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
625 if (!New) {
626 errs() << "verify failed!\n";
627 exit(1);
628 }
629 M = std::move(New);
630
631 // Try running on the hacked up program...
632 if (TestFn(BD, M.get())) {
633 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
634
635 // Make sure to use basic block pointers that point into the now-current
636 // module, and that they don't include any deleted blocks.
637 BBs.clear();
638 const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
639 for (auto &BI : BlockInfo) {
640 auto *F = cast<Function>(GST.lookup(BI.first));
641 Value *V = F->getValueSymbolTable()->lookup(BI.second);
642 if (V && V->getType() == Type::getLabelTy(V->getContext()))
643 BBs.push_back(cast<BasicBlock>(V));
644 }
645 return true;
646 }
647 // It didn't crash, try something else.
648 return false;
649 }
650
651 namespace {
652 /// SimplifyCFG reducer - This works by calling SimplifyCFG on each basic block
653 /// in the program.
654
655 class ReduceSimplifyCFG : public ListReducer<const BasicBlock *> {
656 BugDriver &BD;
657 BugTester TestFn;
658 TargetTransformInfo TTI;
659
660 public:
ReduceSimplifyCFG(BugDriver & bd,BugTester testFn)661 ReduceSimplifyCFG(BugDriver &bd, BugTester testFn)
662 : BD(bd), TestFn(testFn), TTI(bd.getProgram().getDataLayout()) {}
663
doTest(std::vector<const BasicBlock * > & Prefix,std::vector<const BasicBlock * > & Kept)664 Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
665 std::vector<const BasicBlock *> &Kept) override {
666 if (!Kept.empty() && TestBlocks(Kept))
667 return KeepSuffix;
668 if (!Prefix.empty() && TestBlocks(Prefix))
669 return KeepPrefix;
670 return NoFailure;
671 }
672
673 bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
674 };
675 }
676
TestBlocks(std::vector<const BasicBlock * > & BBs)677 bool ReduceSimplifyCFG::TestBlocks(std::vector<const BasicBlock *> &BBs) {
678 // Clone the program to try hacking it apart...
679 ValueToValueMapTy VMap;
680 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
681
682 // Convert list to set for fast lookup...
683 SmallPtrSet<const BasicBlock *, 8> Blocks;
684 for (const auto *BB : BBs)
685 Blocks.insert(cast<BasicBlock>(VMap[BB]));
686
687 outs() << "Checking for crash with CFG simplifying:";
688 unsigned NumPrint = Blocks.size();
689 if (NumPrint > 10)
690 NumPrint = 10;
691 for (unsigned i = 0, e = NumPrint; i != e; ++i)
692 outs() << " " << BBs[i]->getName();
693 if (NumPrint < Blocks.size())
694 outs() << "... <" << Blocks.size() << " total>";
695 outs() << ": ";
696
697 // The following may destroy some blocks, so we save them first
698 std::vector<std::pair<std::string, std::string>> BlockInfo;
699
700 for (const BasicBlock *BB : Blocks)
701 BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
702 std::string(BB->getName()));
703
704 // Loop over and delete any hack up any blocks that are not listed...
705 for (auto &F : *M)
706 // Loop over all of the basic blocks and remove them if they are unneeded.
707 for (Function::iterator BBIt = F.begin(); BBIt != F.end();) {
708 if (!Blocks.count(&*BBIt)) {
709 ++BBIt;
710 continue;
711 }
712 simplifyCFG(&*BBIt++, TTI);
713 }
714 // Verify we didn't break anything
715 std::vector<std::string> Passes;
716 Passes.push_back("verify");
717 std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
718 if (!New) {
719 errs() << "verify failed!\n";
720 exit(1);
721 }
722 M = std::move(New);
723
724 // Try running on the hacked up program...
725 if (TestFn(BD, M.get())) {
726 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
727
728 // Make sure to use basic block pointers that point into the now-current
729 // module, and that they don't include any deleted blocks.
730 BBs.clear();
731 const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
732 for (auto &BI : BlockInfo) {
733 auto *F = cast<Function>(GST.lookup(BI.first));
734 Value *V = F->getValueSymbolTable()->lookup(BI.second);
735 if (V && V->getType() == Type::getLabelTy(V->getContext()))
736 BBs.push_back(cast<BasicBlock>(V));
737 }
738 return true;
739 }
740 // It didn't crash, try something else.
741 return false;
742 }
743
744 namespace {
745 /// ReduceCrashingInstructions reducer - This works by removing the specified
746 /// non-terminator instructions and replacing them with undef.
747 ///
748 class ReduceCrashingInstructions : public ListReducer<const Instruction *> {
749 BugDriver &BD;
750 BugTester TestFn;
751
752 public:
ReduceCrashingInstructions(BugDriver & bd,BugTester testFn)753 ReduceCrashingInstructions(BugDriver &bd, BugTester testFn)
754 : BD(bd), TestFn(testFn) {}
755
doTest(std::vector<const Instruction * > & Prefix,std::vector<const Instruction * > & Kept)756 Expected<TestResult> doTest(std::vector<const Instruction *> &Prefix,
757 std::vector<const Instruction *> &Kept) override {
758 if (!Kept.empty() && TestInsts(Kept))
759 return KeepSuffix;
760 if (!Prefix.empty() && TestInsts(Prefix))
761 return KeepPrefix;
762 return NoFailure;
763 }
764
765 bool TestInsts(std::vector<const Instruction *> &Prefix);
766 };
767 }
768
TestInsts(std::vector<const Instruction * > & Insts)769 bool ReduceCrashingInstructions::TestInsts(
770 std::vector<const Instruction *> &Insts) {
771 // Clone the program to try hacking it apart...
772 ValueToValueMapTy VMap;
773 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
774
775 // Convert list to set for fast lookup...
776 SmallPtrSet<Instruction *, 32> Instructions;
777 for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
778 assert(!Insts[i]->isTerminator());
779 Instructions.insert(cast<Instruction>(VMap[Insts[i]]));
780 }
781
782 outs() << "Checking for crash with only " << Instructions.size();
783 if (Instructions.size() == 1)
784 outs() << " instruction: ";
785 else
786 outs() << " instructions: ";
787
788 for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI)
789 for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI)
790 for (BasicBlock::iterator I = FI->begin(), E = FI->end(); I != E;) {
791 Instruction *Inst = &*I++;
792 if (!Instructions.count(Inst) && !Inst->isTerminator() &&
793 !Inst->isEHPad() && !Inst->getType()->isTokenTy() &&
794 !Inst->isSwiftError()) {
795 if (!Inst->getType()->isVoidTy())
796 Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
797 Inst->eraseFromParent();
798 }
799 }
800
801 // Verify that this is still valid.
802 legacy::PassManager Passes;
803 Passes.add(createVerifierPass(/*FatalErrors=*/false));
804 Passes.run(*M);
805
806 // Try running on the hacked up program...
807 if (TestFn(BD, M.get())) {
808 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
809
810 // Make sure to use instruction pointers that point into the now-current
811 // module, and that they don't include any deleted blocks.
812 Insts.clear();
813 for (Instruction *Inst : Instructions)
814 Insts.push_back(Inst);
815 return true;
816 }
817 // It didn't crash, try something else.
818 return false;
819 }
820
821 namespace {
822 /// ReduceCrashingMetadata reducer - This works by removing all metadata from
823 /// the specified instructions.
824 ///
825 class ReduceCrashingMetadata : public ListReducer<Instruction *> {
826 BugDriver &BD;
827 BugTester TestFn;
828
829 public:
ReduceCrashingMetadata(BugDriver & bd,BugTester testFn)830 ReduceCrashingMetadata(BugDriver &bd, BugTester testFn)
831 : BD(bd), TestFn(testFn) {}
832
doTest(std::vector<Instruction * > & Prefix,std::vector<Instruction * > & Kept)833 Expected<TestResult> doTest(std::vector<Instruction *> &Prefix,
834 std::vector<Instruction *> &Kept) override {
835 if (!Kept.empty() && TestInsts(Kept))
836 return KeepSuffix;
837 if (!Prefix.empty() && TestInsts(Prefix))
838 return KeepPrefix;
839 return NoFailure;
840 }
841
842 bool TestInsts(std::vector<Instruction *> &Prefix);
843 };
844 } // namespace
845
TestInsts(std::vector<Instruction * > & Insts)846 bool ReduceCrashingMetadata::TestInsts(std::vector<Instruction *> &Insts) {
847 // Clone the program to try hacking it apart...
848 ValueToValueMapTy VMap;
849 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
850
851 // Convert list to set for fast lookup...
852 SmallPtrSet<Instruction *, 32> Instructions;
853 for (Instruction *I : Insts)
854 Instructions.insert(cast<Instruction>(VMap[I]));
855
856 outs() << "Checking for crash with metadata retained from "
857 << Instructions.size();
858 if (Instructions.size() == 1)
859 outs() << " instruction: ";
860 else
861 outs() << " instructions: ";
862
863 // Try to drop instruction metadata from all instructions, except the ones
864 // selected in Instructions.
865 for (Function &F : *M)
866 for (Instruction &Inst : instructions(F)) {
867 if (!Instructions.count(&Inst)) {
868 Inst.dropUnknownNonDebugMetadata();
869 Inst.setDebugLoc({});
870 }
871 }
872
873 // Verify that this is still valid.
874 legacy::PassManager Passes;
875 Passes.add(createVerifierPass(/*FatalErrors=*/false));
876 Passes.run(*M);
877
878 // Try running on the hacked up program...
879 if (TestFn(BD, M.get())) {
880 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
881
882 // Make sure to use instruction pointers that point into the now-current
883 // module, and that they don't include any deleted blocks.
884 Insts.clear();
885 for (Instruction *I : Instructions)
886 Insts.push_back(I);
887 return true;
888 }
889 // It didn't crash, try something else.
890 return false;
891 }
892
893 namespace {
894 // Reduce the list of Named Metadata nodes. We keep this as a list of
895 // names to avoid having to convert back and forth every time.
896 class ReduceCrashingNamedMD : public ListReducer<std::string> {
897 BugDriver &BD;
898 BugTester TestFn;
899
900 public:
ReduceCrashingNamedMD(BugDriver & bd,BugTester testFn)901 ReduceCrashingNamedMD(BugDriver &bd, BugTester testFn)
902 : BD(bd), TestFn(testFn) {}
903
doTest(std::vector<std::string> & Prefix,std::vector<std::string> & Kept)904 Expected<TestResult> doTest(std::vector<std::string> &Prefix,
905 std::vector<std::string> &Kept) override {
906 if (!Kept.empty() && TestNamedMDs(Kept))
907 return KeepSuffix;
908 if (!Prefix.empty() && TestNamedMDs(Prefix))
909 return KeepPrefix;
910 return NoFailure;
911 }
912
913 bool TestNamedMDs(std::vector<std::string> &NamedMDs);
914 };
915 }
916
TestNamedMDs(std::vector<std::string> & NamedMDs)917 bool ReduceCrashingNamedMD::TestNamedMDs(std::vector<std::string> &NamedMDs) {
918
919 ValueToValueMapTy VMap;
920 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
921
922 outs() << "Checking for crash with only these named metadata nodes:";
923 unsigned NumPrint = std::min<size_t>(NamedMDs.size(), 10);
924 for (unsigned i = 0, e = NumPrint; i != e; ++i)
925 outs() << " " << NamedMDs[i];
926 if (NumPrint < NamedMDs.size())
927 outs() << "... <" << NamedMDs.size() << " total>";
928 outs() << ": ";
929
930 // Make a StringMap for faster lookup
931 StringSet<> Names;
932 for (const std::string &Name : NamedMDs)
933 Names.insert(Name);
934
935 // First collect all the metadata to delete in a vector, then
936 // delete them all at once to avoid invalidating the iterator
937 std::vector<NamedMDNode *> ToDelete;
938 ToDelete.reserve(M->named_metadata_size() - Names.size());
939 for (auto &NamedMD : M->named_metadata())
940 // Always keep a nonempty llvm.dbg.cu because the Verifier would complain.
941 if (!Names.count(NamedMD.getName()) &&
942 (!(NamedMD.getName() == "llvm.dbg.cu" && NamedMD.getNumOperands() > 0)))
943 ToDelete.push_back(&NamedMD);
944
945 for (auto *NamedMD : ToDelete)
946 NamedMD->eraseFromParent();
947
948 // Verify that this is still valid.
949 legacy::PassManager Passes;
950 Passes.add(createVerifierPass(/*FatalErrors=*/false));
951 Passes.run(*M);
952
953 // Try running on the hacked up program...
954 if (TestFn(BD, M.get())) {
955 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
956 return true;
957 }
958 return false;
959 }
960
961 namespace {
962 // Reduce the list of operands to named metadata nodes
963 class ReduceCrashingNamedMDOps : public ListReducer<const MDNode *> {
964 BugDriver &BD;
965 BugTester TestFn;
966
967 public:
ReduceCrashingNamedMDOps(BugDriver & bd,BugTester testFn)968 ReduceCrashingNamedMDOps(BugDriver &bd, BugTester testFn)
969 : BD(bd), TestFn(testFn) {}
970
doTest(std::vector<const MDNode * > & Prefix,std::vector<const MDNode * > & Kept)971 Expected<TestResult> doTest(std::vector<const MDNode *> &Prefix,
972 std::vector<const MDNode *> &Kept) override {
973 if (!Kept.empty() && TestNamedMDOps(Kept))
974 return KeepSuffix;
975 if (!Prefix.empty() && TestNamedMDOps(Prefix))
976 return KeepPrefix;
977 return NoFailure;
978 }
979
980 bool TestNamedMDOps(std::vector<const MDNode *> &NamedMDOps);
981 };
982 }
983
TestNamedMDOps(std::vector<const MDNode * > & NamedMDOps)984 bool ReduceCrashingNamedMDOps::TestNamedMDOps(
985 std::vector<const MDNode *> &NamedMDOps) {
986 // Convert list to set for fast lookup...
987 SmallPtrSet<const MDNode *, 32> OldMDNodeOps;
988 for (unsigned i = 0, e = NamedMDOps.size(); i != e; ++i) {
989 OldMDNodeOps.insert(NamedMDOps[i]);
990 }
991
992 outs() << "Checking for crash with only " << OldMDNodeOps.size();
993 if (OldMDNodeOps.size() == 1)
994 outs() << " named metadata operand: ";
995 else
996 outs() << " named metadata operands: ";
997
998 ValueToValueMapTy VMap;
999 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
1000
1001 // This is a little wasteful. In the future it might be good if we could have
1002 // these dropped during cloning.
1003 for (auto &NamedMD : BD.getProgram().named_metadata()) {
1004 // Drop the old one and create a new one
1005 M->eraseNamedMetadata(M->getNamedMetadata(NamedMD.getName()));
1006 NamedMDNode *NewNamedMDNode =
1007 M->getOrInsertNamedMetadata(NamedMD.getName());
1008 for (MDNode *op : NamedMD.operands())
1009 if (OldMDNodeOps.count(op))
1010 NewNamedMDNode->addOperand(cast<MDNode>(MapMetadata(op, VMap)));
1011 }
1012
1013 // Verify that this is still valid.
1014 legacy::PassManager Passes;
1015 Passes.add(createVerifierPass(/*FatalErrors=*/false));
1016 Passes.run(*M);
1017
1018 // Try running on the hacked up program...
1019 if (TestFn(BD, M.get())) {
1020 // Make sure to use instruction pointers that point into the now-current
1021 // module, and that they don't include any deleted blocks.
1022 NamedMDOps.clear();
1023 for (const MDNode *Node : OldMDNodeOps)
1024 NamedMDOps.push_back(cast<MDNode>(*VMap.getMappedMD(Node)));
1025
1026 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
1027 return true;
1028 }
1029 // It didn't crash, try something else.
1030 return false;
1031 }
1032
1033 /// Attempt to eliminate as many global initializers as possible.
ReduceGlobalInitializers(BugDriver & BD,BugTester TestFn)1034 static Error ReduceGlobalInitializers(BugDriver &BD, BugTester TestFn) {
1035 Module &OrigM = BD.getProgram();
1036 if (OrigM.global_empty())
1037 return Error::success();
1038
1039 // Now try to reduce the number of global variable initializers in the
1040 // module to something small.
1041 std::unique_ptr<Module> M = CloneModule(OrigM);
1042 bool DeletedInit = false;
1043
1044 for (GlobalVariable &GV : M->globals()) {
1045 if (GV.hasInitializer()) {
1046 DeleteGlobalInitializer(&GV);
1047 GV.setLinkage(GlobalValue::ExternalLinkage);
1048 GV.setComdat(nullptr);
1049 DeletedInit = true;
1050 }
1051 }
1052
1053 if (!DeletedInit)
1054 return Error::success();
1055
1056 // See if the program still causes a crash...
1057 outs() << "\nChecking to see if we can delete global inits: ";
1058
1059 if (TestFn(BD, M.get())) { // Still crashes?
1060 BD.setNewProgram(std::move(M));
1061 outs() << "\n*** Able to remove all global initializers!\n";
1062 return Error::success();
1063 }
1064
1065 // No longer crashes.
1066 outs() << " - Removing all global inits hides problem!\n";
1067
1068 std::vector<GlobalVariable *> GVs;
1069 for (GlobalVariable &GV : OrigM.globals())
1070 if (GV.hasInitializer())
1071 GVs.push_back(&GV);
1072
1073 if (GVs.size() > 1 && !BugpointIsInterrupted) {
1074 outs() << "\n*** Attempting to reduce the number of global initializers "
1075 << "in the testcase\n";
1076
1077 unsigned OldSize = GVs.size();
1078 Expected<bool> Result =
1079 ReduceCrashingGlobalInitializers(BD, TestFn).reduceList(GVs);
1080 if (Error E = Result.takeError())
1081 return E;
1082
1083 if (GVs.size() < OldSize)
1084 BD.EmitProgressBitcode(BD.getProgram(), "reduced-global-variables");
1085 }
1086 return Error::success();
1087 }
1088
ReduceInsts(BugDriver & BD,BugTester TestFn)1089 static Error ReduceInsts(BugDriver &BD, BugTester TestFn) {
1090 // Attempt to delete instructions using bisection. This should help out nasty
1091 // cases with large basic blocks where the problem is at one end.
1092 if (!BugpointIsInterrupted) {
1093 std::vector<const Instruction *> Insts;
1094 for (const Function &F : BD.getProgram())
1095 for (const BasicBlock &BB : F)
1096 for (const Instruction &I : BB)
1097 if (!I.isTerminator())
1098 Insts.push_back(&I);
1099
1100 Expected<bool> Result =
1101 ReduceCrashingInstructions(BD, TestFn).reduceList(Insts);
1102 if (Error E = Result.takeError())
1103 return E;
1104 }
1105
1106 unsigned Simplification = 2;
1107 do {
1108 if (BugpointIsInterrupted)
1109 // TODO: Should we distinguish this with an "interrupted error"?
1110 return Error::success();
1111 --Simplification;
1112 outs() << "\n*** Attempting to reduce testcase by deleting instruc"
1113 << "tions: Simplification Level #" << Simplification << '\n';
1114
1115 // Now that we have deleted the functions that are unnecessary for the
1116 // program, try to remove instructions that are not necessary to cause the
1117 // crash. To do this, we loop through all of the instructions in the
1118 // remaining functions, deleting them (replacing any values produced with
1119 // nulls), and then running ADCE and SimplifyCFG. If the transformed input
1120 // still triggers failure, keep deleting until we cannot trigger failure
1121 // anymore.
1122 //
1123 unsigned InstructionsToSkipBeforeDeleting = 0;
1124 TryAgain:
1125
1126 // Loop over all of the (non-terminator) instructions remaining in the
1127 // function, attempting to delete them.
1128 unsigned CurInstructionNum = 0;
1129 for (Module::const_iterator FI = BD.getProgram().begin(),
1130 E = BD.getProgram().end();
1131 FI != E; ++FI)
1132 if (!FI->isDeclaration())
1133 for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E;
1134 ++BI)
1135 for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end();
1136 I != E; ++I, ++CurInstructionNum) {
1137 if (InstructionsToSkipBeforeDeleting) {
1138 --InstructionsToSkipBeforeDeleting;
1139 } else {
1140 if (BugpointIsInterrupted)
1141 // TODO: Should this be some kind of interrupted error?
1142 return Error::success();
1143
1144 if (I->isEHPad() || I->getType()->isTokenTy() ||
1145 I->isSwiftError())
1146 continue;
1147
1148 outs() << "Checking instruction: " << *I;
1149 std::unique_ptr<Module> M =
1150 BD.deleteInstructionFromProgram(&*I, Simplification);
1151
1152 // Find out if the pass still crashes on this pass...
1153 if (TestFn(BD, M.get())) {
1154 // Yup, it does, we delete the old module, and continue trying
1155 // to reduce the testcase...
1156 BD.setNewProgram(std::move(M));
1157 InstructionsToSkipBeforeDeleting = CurInstructionNum;
1158 goto TryAgain; // I wish I had a multi-level break here!
1159 }
1160 }
1161 }
1162
1163 if (InstructionsToSkipBeforeDeleting) {
1164 InstructionsToSkipBeforeDeleting = 0;
1165 goto TryAgain;
1166 }
1167
1168 } while (Simplification);
1169
1170 // Attempt to drop metadata from instructions that does not contribute to the
1171 // crash.
1172 if (!BugpointIsInterrupted) {
1173 std::vector<Instruction *> Insts;
1174 for (Function &F : BD.getProgram())
1175 for (Instruction &I : instructions(F))
1176 Insts.push_back(&I);
1177
1178 Expected<bool> Result =
1179 ReduceCrashingMetadata(BD, TestFn).reduceList(Insts);
1180 if (Error E = Result.takeError())
1181 return E;
1182 }
1183
1184 BD.EmitProgressBitcode(BD.getProgram(), "reduced-instructions");
1185 return Error::success();
1186 }
1187
1188 /// DebugACrash - Given a predicate that determines whether a component crashes
1189 /// on a program, try to destructively reduce the program while still keeping
1190 /// the predicate true.
DebugACrash(BugDriver & BD,BugTester TestFn)1191 static Error DebugACrash(BugDriver &BD, BugTester TestFn) {
1192 // See if we can get away with nuking some of the global variable initializers
1193 // in the program...
1194 if (!NoGlobalRM)
1195 if (Error E = ReduceGlobalInitializers(BD, TestFn))
1196 return E;
1197
1198 // Now try to reduce the number of functions in the module to something small.
1199 std::vector<Function *> Functions;
1200 for (Function &F : BD.getProgram())
1201 if (!F.isDeclaration())
1202 Functions.push_back(&F);
1203
1204 if (Functions.size() > 1 && !BugpointIsInterrupted) {
1205 outs() << "\n*** Attempting to reduce the number of functions "
1206 "in the testcase\n";
1207
1208 unsigned OldSize = Functions.size();
1209 Expected<bool> Result =
1210 ReduceCrashingFunctions(BD, TestFn).reduceList(Functions);
1211 if (Error E = Result.takeError())
1212 return E;
1213
1214 if (Functions.size() < OldSize)
1215 BD.EmitProgressBitcode(BD.getProgram(), "reduced-function");
1216 }
1217
1218 if (!NoAttributeRM) {
1219 // For each remaining function, try to reduce that function's attributes.
1220 std::vector<std::string> FunctionNames;
1221 for (Function &F : BD.getProgram())
1222 FunctionNames.push_back(std::string(F.getName()));
1223
1224 if (!FunctionNames.empty() && !BugpointIsInterrupted) {
1225 outs() << "\n*** Attempting to reduce the number of function attributes"
1226 " in the testcase\n";
1227
1228 unsigned OldSize = 0;
1229 unsigned NewSize = 0;
1230 for (std::string &Name : FunctionNames) {
1231 Function *Fn = BD.getProgram().getFunction(Name);
1232 assert(Fn && "Could not find function?");
1233
1234 std::vector<Attribute> Attrs;
1235 for (Attribute A : Fn->getAttributes().getFnAttributes())
1236 Attrs.push_back(A);
1237
1238 OldSize += Attrs.size();
1239 Expected<bool> Result =
1240 ReduceCrashingFunctionAttributes(BD, Name, TestFn).reduceList(Attrs);
1241 if (Error E = Result.takeError())
1242 return E;
1243
1244 NewSize += Attrs.size();
1245 }
1246
1247 if (OldSize < NewSize)
1248 BD.EmitProgressBitcode(BD.getProgram(), "reduced-function-attributes");
1249 }
1250 }
1251
1252 // Attempt to change conditional branches into unconditional branches to
1253 // eliminate blocks.
1254 if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1255 std::vector<const BasicBlock *> Blocks;
1256 for (Function &F : BD.getProgram())
1257 for (BasicBlock &BB : F)
1258 Blocks.push_back(&BB);
1259 unsigned OldSize = Blocks.size();
1260 Expected<bool> Result =
1261 ReduceCrashingConditionals(BD, TestFn, true).reduceList(Blocks);
1262 if (Error E = Result.takeError())
1263 return E;
1264 Result = ReduceCrashingConditionals(BD, TestFn, false).reduceList(Blocks);
1265 if (Error E = Result.takeError())
1266 return E;
1267 if (Blocks.size() < OldSize)
1268 BD.EmitProgressBitcode(BD.getProgram(), "reduced-conditionals");
1269 }
1270
1271 // Attempt to delete entire basic blocks at a time to speed up
1272 // convergence... this actually works by setting the terminator of the blocks
1273 // to a return instruction then running simplifycfg, which can potentially
1274 // shrinks the code dramatically quickly
1275 //
1276 if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1277 std::vector<const BasicBlock *> Blocks;
1278 for (Function &F : BD.getProgram())
1279 for (BasicBlock &BB : F)
1280 Blocks.push_back(&BB);
1281 unsigned OldSize = Blocks.size();
1282 Expected<bool> Result = ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks);
1283 if (Error E = Result.takeError())
1284 return E;
1285 if (Blocks.size() < OldSize)
1286 BD.EmitProgressBitcode(BD.getProgram(), "reduced-blocks");
1287 }
1288
1289 if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1290 std::vector<const BasicBlock *> Blocks;
1291 for (Function &F : BD.getProgram())
1292 for (BasicBlock &BB : F)
1293 Blocks.push_back(&BB);
1294 unsigned OldSize = Blocks.size();
1295 Expected<bool> Result = ReduceSimplifyCFG(BD, TestFn).reduceList(Blocks);
1296 if (Error E = Result.takeError())
1297 return E;
1298 if (Blocks.size() < OldSize)
1299 BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplifycfg");
1300 }
1301
1302 // Attempt to delete instructions using bisection. This should help out nasty
1303 // cases with large basic blocks where the problem is at one end.
1304 if (!BugpointIsInterrupted)
1305 if (Error E = ReduceInsts(BD, TestFn))
1306 return E;
1307
1308 // Attempt to strip debug info metadata.
1309 auto stripMetadata = [&](std::function<bool(Module &)> strip) {
1310 std::unique_ptr<Module> M = CloneModule(BD.getProgram());
1311 strip(*M);
1312 if (TestFn(BD, M.get()))
1313 BD.setNewProgram(std::move(M));
1314 };
1315 if (!NoStripDebugInfo && !BugpointIsInterrupted) {
1316 outs() << "\n*** Attempting to strip the debug info: ";
1317 stripMetadata(StripDebugInfo);
1318 }
1319 if (!NoStripDebugTypeInfo && !BugpointIsInterrupted) {
1320 outs() << "\n*** Attempting to strip the debug type info: ";
1321 stripMetadata(stripNonLineTableDebugInfo);
1322 }
1323
1324 if (!NoNamedMDRM) {
1325 if (!BugpointIsInterrupted) {
1326 // Try to reduce the amount of global metadata (particularly debug info),
1327 // by dropping global named metadata that anchors them
1328 outs() << "\n*** Attempting to remove named metadata: ";
1329 std::vector<std::string> NamedMDNames;
1330 for (auto &NamedMD : BD.getProgram().named_metadata())
1331 NamedMDNames.push_back(NamedMD.getName().str());
1332 Expected<bool> Result =
1333 ReduceCrashingNamedMD(BD, TestFn).reduceList(NamedMDNames);
1334 if (Error E = Result.takeError())
1335 return E;
1336 }
1337
1338 if (!BugpointIsInterrupted) {
1339 // Now that we quickly dropped all the named metadata that doesn't
1340 // contribute to the crash, bisect the operands of the remaining ones
1341 std::vector<const MDNode *> NamedMDOps;
1342 for (auto &NamedMD : BD.getProgram().named_metadata())
1343 for (auto op : NamedMD.operands())
1344 NamedMDOps.push_back(op);
1345 Expected<bool> Result =
1346 ReduceCrashingNamedMDOps(BD, TestFn).reduceList(NamedMDOps);
1347 if (Error E = Result.takeError())
1348 return E;
1349 }
1350 BD.EmitProgressBitcode(BD.getProgram(), "reduced-named-md");
1351 }
1352
1353 // Try to clean up the testcase by running funcresolve and globaldce...
1354 if (!BugpointIsInterrupted) {
1355 outs() << "\n*** Attempting to perform final cleanups: ";
1356 std::unique_ptr<Module> M = CloneModule(BD.getProgram());
1357 M = BD.performFinalCleanups(std::move(M), true);
1358
1359 // Find out if the pass still crashes on the cleaned up program...
1360 if (M && TestFn(BD, M.get()))
1361 BD.setNewProgram(
1362 std::move(M)); // Yup, it does, keep the reduced version...
1363 }
1364
1365 BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplified");
1366
1367 return Error::success();
1368 }
1369
TestForOptimizerCrash(const BugDriver & BD,Module * M)1370 static bool TestForOptimizerCrash(const BugDriver &BD, Module *M) {
1371 return BD.runPasses(*M, BD.getPassesToRun());
1372 }
1373
1374 /// debugOptimizerCrash - This method is called when some pass crashes on input.
1375 /// It attempts to prune down the testcase to something reasonable, and figure
1376 /// out exactly which pass is crashing.
1377 ///
debugOptimizerCrash(const std::string & ID)1378 Error BugDriver::debugOptimizerCrash(const std::string &ID) {
1379 outs() << "\n*** Debugging optimizer crash!\n";
1380
1381 // Reduce the list of passes which causes the optimizer to crash...
1382 if (!BugpointIsInterrupted && !DontReducePassList) {
1383 Expected<bool> Result = ReducePassList(*this).reduceList(PassesToRun);
1384 if (Error E = Result.takeError())
1385 return E;
1386 }
1387
1388 outs() << "\n*** Found crashing pass"
1389 << (PassesToRun.size() == 1 ? ": " : "es: ")
1390 << getPassesString(PassesToRun) << '\n';
1391
1392 EmitProgressBitcode(*Program, ID);
1393
1394 auto Res = DebugACrash(*this, TestForOptimizerCrash);
1395 if (Res || DontReducePassList)
1396 return Res;
1397 // Try to reduce the pass list again. This covers additional cases
1398 // we failed to reduce earlier, because of more complex pass dependencies
1399 // triggering the crash.
1400 auto SecondRes = ReducePassList(*this).reduceList(PassesToRun);
1401 if (Error E = SecondRes.takeError())
1402 return E;
1403 outs() << "\n*** Found crashing pass"
1404 << (PassesToRun.size() == 1 ? ": " : "es: ")
1405 << getPassesString(PassesToRun) << '\n';
1406
1407 EmitProgressBitcode(getProgram(), "reduced-simplified");
1408 return Res;
1409 }
1410
TestForCodeGenCrash(const BugDriver & BD,Module * M)1411 static bool TestForCodeGenCrash(const BugDriver &BD, Module *M) {
1412 if (Error E = BD.compileProgram(*M)) {
1413 if (VerboseErrors)
1414 errs() << toString(std::move(E)) << "\n";
1415 else {
1416 consumeError(std::move(E));
1417 errs() << "<crash>\n";
1418 }
1419 return true; // Tool is still crashing.
1420 }
1421 errs() << '\n';
1422 return false;
1423 }
1424
1425 /// debugCodeGeneratorCrash - This method is called when the code generator
1426 /// crashes on an input. It attempts to reduce the input as much as possible
1427 /// while still causing the code generator to crash.
debugCodeGeneratorCrash()1428 Error BugDriver::debugCodeGeneratorCrash() {
1429 errs() << "*** Debugging code generator crash!\n";
1430
1431 return DebugACrash(*this, TestForCodeGenCrash);
1432 }
1433