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