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