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