1 //===- CrashDebugger.cpp - Debug compilation crashes ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the bugpoint internals that narrow down compilation crashes
12 //===----------------------------------------------------------------------===//
14 #include "BugDriver.h"
15 #include "ToolRunner.h"
16 #include "ListReducer.h"
17 #include "llvm/Constants.h"
18 #include "llvm/DerivedTypes.h"
19 #include "llvm/Instructions.h"
20 #include "llvm/Module.h"
21 #include "llvm/Pass.h"
22 #include "llvm/PassManager.h"
23 #include "llvm/ValueSymbolTable.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/Analysis/Verifier.h"
26 #include "llvm/Support/CFG.h"
27 #include "llvm/Transforms/Scalar.h"
28 #include "llvm/Transforms/Utils/Cloning.h"
29 #include "llvm/Support/FileUtilities.h"
30 #include "llvm/Support/CommandLine.h"
37 cl::desc("Force function reduction to keep main"),
40 NoGlobalRM ("disable-global-remove",
41 cl::desc("Do not remove global variables"),
46 class ReducePassList
: public ListReducer
<std::string
> {
49 ReducePassList(BugDriver
&bd
) : BD(bd
) {}
51 // doTest - Return true iff running the "removed" passes succeeds, and
52 // running the "Kept" passes fail when run on the output of the "removed"
53 // passes. If we return true, we update the current module of bugpoint.
55 virtual TestResult
doTest(std::vector
<std::string
> &Removed
,
56 std::vector
<std::string
> &Kept
,
61 ReducePassList::TestResult
62 ReducePassList::doTest(std::vector
<std::string
> &Prefix
,
63 std::vector
<std::string
> &Suffix
,
65 sys::Path PrefixOutput
;
66 Module
*OrigProgram
= 0;
67 if (!Prefix
.empty()) {
68 outs() << "Checking to see if these passes crash: "
69 << getPassesString(Prefix
) << ": ";
70 std::string PfxOutput
;
71 if (BD
.runPasses(BD
.getProgram(), Prefix
, PfxOutput
))
74 PrefixOutput
.set(PfxOutput
);
75 OrigProgram
= BD
.Program
;
77 BD
.Program
= ParseInputFile(PrefixOutput
.str(), BD
.getContext());
78 if (BD
.Program
== 0) {
79 errs() << BD
.getToolName() << ": Error reading bitcode file '"
80 << PrefixOutput
.str() << "'!\n";
83 PrefixOutput
.eraseFromDisk();
86 outs() << "Checking to see if these passes crash: "
87 << getPassesString(Suffix
) << ": ";
89 if (BD
.runPasses(BD
.getProgram(), Suffix
)) {
90 delete OrigProgram
; // The suffix crashes alone...
94 // Nothing failed, restore state...
97 BD
.Program
= OrigProgram
;
103 /// ReduceCrashingGlobalVariables - This works by removing the global
104 /// variable's initializer and seeing if the program still crashes. If it
105 /// does, then we keep that program and try again.
107 class ReduceCrashingGlobalVariables
: public ListReducer
<GlobalVariable
*> {
109 bool (*TestFn
)(const BugDriver
&, Module
*);
111 ReduceCrashingGlobalVariables(BugDriver
&bd
,
112 bool (*testFn
)(const BugDriver
&, Module
*))
113 : BD(bd
), TestFn(testFn
) {}
115 virtual TestResult
doTest(std::vector
<GlobalVariable
*> &Prefix
,
116 std::vector
<GlobalVariable
*> &Kept
,
117 std::string
&Error
) {
118 if (!Kept
.empty() && TestGlobalVariables(Kept
))
120 if (!Prefix
.empty() && TestGlobalVariables(Prefix
))
125 bool TestGlobalVariables(std::vector
<GlobalVariable
*> &GVs
);
130 ReduceCrashingGlobalVariables::TestGlobalVariables(
131 std::vector
<GlobalVariable
*> &GVs
) {
132 // Clone the program to try hacking it apart...
133 ValueMap
<const Value
*, Value
*> VMap
;
134 Module
*M
= CloneModule(BD
.getProgram(), VMap
);
136 // Convert list to set for fast lookup...
137 std::set
<GlobalVariable
*> GVSet
;
139 for (unsigned i
= 0, e
= GVs
.size(); i
!= e
; ++i
) {
140 GlobalVariable
* CMGV
= cast
<GlobalVariable
>(VMap
[GVs
[i
]]);
141 assert(CMGV
&& "Global Variable not in module?!");
145 outs() << "Checking for crash with only these global variables: ";
146 PrintGlobalVariableList(GVs
);
149 // Loop over and delete any global variables which we aren't supposed to be
151 for (Module::global_iterator I
= M
->global_begin(), E
= M
->global_end();
153 if (I
->hasInitializer() && !GVSet
.count(I
)) {
154 I
->setInitializer(0);
155 I
->setLinkage(GlobalValue::ExternalLinkage
);
158 // Try running the hacked up program...
160 BD
.setNewProgram(M
); // It crashed, keep the trimmed version...
162 // Make sure to use global variable pointers that point into the now-current
164 GVs
.assign(GVSet
.begin(), GVSet
.end());
173 /// ReduceCrashingFunctions reducer - This works by removing functions and
174 /// seeing if the program still crashes. If it does, then keep the newer,
177 class ReduceCrashingFunctions
: public ListReducer
<Function
*> {
179 bool (*TestFn
)(const BugDriver
&, Module
*);
181 ReduceCrashingFunctions(BugDriver
&bd
,
182 bool (*testFn
)(const BugDriver
&, Module
*))
183 : BD(bd
), TestFn(testFn
) {}
185 virtual TestResult
doTest(std::vector
<Function
*> &Prefix
,
186 std::vector
<Function
*> &Kept
,
187 std::string
&Error
) {
188 if (!Kept
.empty() && TestFuncs(Kept
))
190 if (!Prefix
.empty() && TestFuncs(Prefix
))
195 bool TestFuncs(std::vector
<Function
*> &Prefix
);
199 bool ReduceCrashingFunctions::TestFuncs(std::vector
<Function
*> &Funcs
) {
201 //if main isn't present, claim there is no problem
202 if (KeepMain
&& find(Funcs
.begin(), Funcs
.end(),
203 BD
.getProgram()->getFunction("main")) == Funcs
.end())
206 // Clone the program to try hacking it apart...
207 ValueMap
<const Value
*, Value
*> VMap
;
208 Module
*M
= CloneModule(BD
.getProgram(), VMap
);
210 // Convert list to set for fast lookup...
211 std::set
<Function
*> Functions
;
212 for (unsigned i
= 0, e
= Funcs
.size(); i
!= e
; ++i
) {
213 Function
*CMF
= cast
<Function
>(VMap
[Funcs
[i
]]);
214 assert(CMF
&& "Function not in module?!");
215 assert(CMF
->getFunctionType() == Funcs
[i
]->getFunctionType() && "wrong ty");
216 assert(CMF
->getName() == Funcs
[i
]->getName() && "wrong name");
217 Functions
.insert(CMF
);
220 outs() << "Checking for crash with only these functions: ";
221 PrintFunctionList(Funcs
);
224 // Loop over and delete any functions which we aren't supposed to be playing
226 for (Module::iterator I
= M
->begin(), E
= M
->end(); I
!= E
; ++I
)
227 if (!I
->isDeclaration() && !Functions
.count(I
))
228 DeleteFunctionBody(I
);
230 // Try running the hacked up program...
232 BD
.setNewProgram(M
); // It crashed, keep the trimmed version...
234 // Make sure to use function pointers that point into the now-current
236 Funcs
.assign(Functions
.begin(), Functions
.end());
245 /// ReduceCrashingBlocks reducer - This works by setting the terminators of
246 /// all terminators except the specified basic blocks to a 'ret' instruction,
247 /// then running the simplify-cfg pass. This has the effect of chopping up
248 /// the CFG really fast which can reduce large functions quickly.
250 class ReduceCrashingBlocks
: public ListReducer
<const BasicBlock
*> {
252 bool (*TestFn
)(const BugDriver
&, Module
*);
254 ReduceCrashingBlocks(BugDriver
&bd
,
255 bool (*testFn
)(const BugDriver
&, Module
*))
256 : BD(bd
), TestFn(testFn
) {}
258 virtual TestResult
doTest(std::vector
<const BasicBlock
*> &Prefix
,
259 std::vector
<const BasicBlock
*> &Kept
,
260 std::string
&Error
) {
261 if (!Kept
.empty() && TestBlocks(Kept
))
263 if (!Prefix
.empty() && TestBlocks(Prefix
))
268 bool TestBlocks(std::vector
<const BasicBlock
*> &Prefix
);
272 bool ReduceCrashingBlocks::TestBlocks(std::vector
<const BasicBlock
*> &BBs
) {
273 // Clone the program to try hacking it apart...
274 ValueMap
<const Value
*, Value
*> VMap
;
275 Module
*M
= CloneModule(BD
.getProgram(), VMap
);
277 // Convert list to set for fast lookup...
278 SmallPtrSet
<BasicBlock
*, 8> Blocks
;
279 for (unsigned i
= 0, e
= BBs
.size(); i
!= e
; ++i
)
280 Blocks
.insert(cast
<BasicBlock
>(VMap
[BBs
[i
]]));
282 outs() << "Checking for crash with only these blocks:";
283 unsigned NumPrint
= Blocks
.size();
284 if (NumPrint
> 10) NumPrint
= 10;
285 for (unsigned i
= 0, e
= NumPrint
; i
!= e
; ++i
)
286 outs() << " " << BBs
[i
]->getName();
287 if (NumPrint
< Blocks
.size())
288 outs() << "... <" << Blocks
.size() << " total>";
291 // Loop over and delete any hack up any blocks that are not listed...
292 for (Module::iterator I
= M
->begin(), E
= M
->end(); I
!= E
; ++I
)
293 for (Function::iterator BB
= I
->begin(), E
= I
->end(); BB
!= E
; ++BB
)
294 if (!Blocks
.count(BB
) && BB
->getTerminator()->getNumSuccessors()) {
295 // Loop over all of the successors of this block, deleting any PHI nodes
296 // that might include it.
297 for (succ_iterator SI
= succ_begin(BB
), E
= succ_end(BB
); SI
!= E
; ++SI
)
298 (*SI
)->removePredecessor(BB
);
300 TerminatorInst
*BBTerm
= BB
->getTerminator();
302 if (!BB
->getTerminator()->getType()->isVoidTy())
303 BBTerm
->replaceAllUsesWith(Constant::getNullValue(BBTerm
->getType()));
305 // Replace the old terminator instruction.
306 BB
->getInstList().pop_back();
307 new UnreachableInst(BB
->getContext(), BB
);
310 // The CFG Simplifier pass may delete one of the basic blocks we are
311 // interested in. If it does we need to take the block out of the list. Make
312 // a "persistent mapping" by turning basic blocks into <function, name> pairs.
313 // This won't work well if blocks are unnamed, but that is just the risk we
315 std::vector
<std::pair
<Function
*, std::string
> > BlockInfo
;
317 for (SmallPtrSet
<BasicBlock
*, 8>::iterator I
= Blocks
.begin(),
318 E
= Blocks
.end(); I
!= E
; ++I
)
319 BlockInfo
.push_back(std::make_pair((*I
)->getParent(), (*I
)->getName()));
321 // Now run the CFG simplify pass on the function...
323 Passes
.add(createCFGSimplificationPass());
324 Passes
.add(createVerifierPass());
327 // Try running on the hacked up program...
329 BD
.setNewProgram(M
); // It crashed, keep the trimmed version...
331 // Make sure to use basic block pointers that point into the now-current
332 // module, and that they don't include any deleted blocks.
334 for (unsigned i
= 0, e
= BlockInfo
.size(); i
!= e
; ++i
) {
335 ValueSymbolTable
&ST
= BlockInfo
[i
].first
->getValueSymbolTable();
336 Value
* V
= ST
.lookup(BlockInfo
[i
].second
);
337 if (V
&& V
->getType() == Type::getLabelTy(V
->getContext()))
338 BBs
.push_back(cast
<BasicBlock
>(V
));
342 delete M
; // It didn't crash, try something else.
347 /// ReduceCrashingInstructions reducer - This works by removing the specified
348 /// non-terminator instructions and replacing them with undef.
350 class ReduceCrashingInstructions
: public ListReducer
<const Instruction
*> {
352 bool (*TestFn
)(const BugDriver
&, Module
*);
354 ReduceCrashingInstructions(BugDriver
&bd
,
355 bool (*testFn
)(const BugDriver
&, Module
*))
356 : BD(bd
), TestFn(testFn
) {}
358 virtual TestResult
doTest(std::vector
<const Instruction
*> &Prefix
,
359 std::vector
<const Instruction
*> &Kept
,
360 std::string
&Error
) {
361 if (!Kept
.empty() && TestInsts(Kept
))
363 if (!Prefix
.empty() && TestInsts(Prefix
))
368 bool TestInsts(std::vector
<const Instruction
*> &Prefix
);
372 bool ReduceCrashingInstructions::TestInsts(std::vector
<const Instruction
*>
374 // Clone the program to try hacking it apart...
375 ValueMap
<const Value
*, Value
*> VMap
;
376 Module
*M
= CloneModule(BD
.getProgram(), VMap
);
378 // Convert list to set for fast lookup...
379 SmallPtrSet
<Instruction
*, 64> Instructions
;
380 for (unsigned i
= 0, e
= Insts
.size(); i
!= e
; ++i
) {
381 assert(!isa
<TerminatorInst
>(Insts
[i
]));
382 Instructions
.insert(cast
<Instruction
>(VMap
[Insts
[i
]]));
385 outs() << "Checking for crash with only " << Instructions
.size();
386 if (Instructions
.size() == 1)
387 outs() << " instruction: ";
389 outs() << " instructions: ";
391 for (Module::iterator MI
= M
->begin(), ME
= M
->end(); MI
!= ME
; ++MI
)
392 for (Function::iterator FI
= MI
->begin(), FE
= MI
->end(); FI
!= FE
; ++FI
)
393 for (BasicBlock::iterator I
= FI
->begin(), E
= FI
->end(); I
!= E
;) {
394 Instruction
*Inst
= I
++;
395 if (!Instructions
.count(Inst
) && !isa
<TerminatorInst
>(Inst
)) {
396 if (!Inst
->getType()->isVoidTy())
397 Inst
->replaceAllUsesWith(UndefValue::get(Inst
->getType()));
398 Inst
->eraseFromParent();
402 // Verify that this is still valid.
404 Passes
.add(createVerifierPass());
407 // Try running on the hacked up program...
409 BD
.setNewProgram(M
); // It crashed, keep the trimmed version...
411 // Make sure to use instruction pointers that point into the now-current
412 // module, and that they don't include any deleted blocks.
414 for (SmallPtrSet
<Instruction
*, 64>::const_iterator I
= Instructions
.begin(),
415 E
= Instructions
.end(); I
!= E
; ++I
)
419 delete M
; // It didn't crash, try something else.
423 /// DebugACrash - Given a predicate that determines whether a component crashes
424 /// on a program, try to destructively reduce the program while still keeping
425 /// the predicate true.
426 static bool DebugACrash(BugDriver
&BD
,
427 bool (*TestFn
)(const BugDriver
&, Module
*),
428 std::string
&Error
) {
429 // See if we can get away with nuking some of the global variable initializers
432 BD
.getProgram()->global_begin() != BD
.getProgram()->global_end()) {
433 // Now try to reduce the number of global variable initializers in the
434 // module to something small.
435 Module
*M
= CloneModule(BD
.getProgram());
436 bool DeletedInit
= false;
438 for (Module::global_iterator I
= M
->global_begin(), E
= M
->global_end();
440 if (I
->hasInitializer()) {
441 I
->setInitializer(0);
442 I
->setLinkage(GlobalValue::ExternalLinkage
);
447 delete M
; // No change made...
449 // See if the program still causes a crash...
450 outs() << "\nChecking to see if we can delete global inits: ";
452 if (TestFn(BD
, M
)) { // Still crashes?
454 outs() << "\n*** Able to remove all global initializers!\n";
455 } else { // No longer crashes?
456 outs() << " - Removing all global inits hides problem!\n";
459 std::vector
<GlobalVariable
*> GVs
;
461 for (Module::global_iterator I
= BD
.getProgram()->global_begin(),
462 E
= BD
.getProgram()->global_end(); I
!= E
; ++I
)
463 if (I
->hasInitializer())
466 if (GVs
.size() > 1 && !BugpointIsInterrupted
) {
467 outs() << "\n*** Attempting to reduce the number of global "
468 << "variables in the testcase\n";
470 unsigned OldSize
= GVs
.size();
471 ReduceCrashingGlobalVariables(BD
, TestFn
).reduceList(GVs
, Error
);
475 if (GVs
.size() < OldSize
)
476 BD
.EmitProgressBitcode(BD
.getProgram(), "reduced-global-variables");
482 // Now try to reduce the number of functions in the module to something small.
483 std::vector
<Function
*> Functions
;
484 for (Module::iterator I
= BD
.getProgram()->begin(),
485 E
= BD
.getProgram()->end(); I
!= E
; ++I
)
486 if (!I
->isDeclaration())
487 Functions
.push_back(I
);
489 if (Functions
.size() > 1 && !BugpointIsInterrupted
) {
490 outs() << "\n*** Attempting to reduce the number of functions "
493 unsigned OldSize
= Functions
.size();
494 ReduceCrashingFunctions(BD
, TestFn
).reduceList(Functions
, Error
);
496 if (Functions
.size() < OldSize
)
497 BD
.EmitProgressBitcode(BD
.getProgram(), "reduced-function");
500 // Attempt to delete entire basic blocks at a time to speed up
501 // convergence... this actually works by setting the terminator of the blocks
502 // to a return instruction then running simplifycfg, which can potentially
503 // shrinks the code dramatically quickly
505 if (!DisableSimplifyCFG
&& !BugpointIsInterrupted
) {
506 std::vector
<const BasicBlock
*> Blocks
;
507 for (Module::const_iterator I
= BD
.getProgram()->begin(),
508 E
= BD
.getProgram()->end(); I
!= E
; ++I
)
509 for (Function::const_iterator FI
= I
->begin(), E
= I
->end(); FI
!=E
; ++FI
)
510 Blocks
.push_back(FI
);
511 unsigned OldSize
= Blocks
.size();
512 ReduceCrashingBlocks(BD
, TestFn
).reduceList(Blocks
, Error
);
513 if (Blocks
.size() < OldSize
)
514 BD
.EmitProgressBitcode(BD
.getProgram(), "reduced-blocks");
517 // Attempt to delete instructions using bisection. This should help out nasty
518 // cases with large basic blocks where the problem is at one end.
519 if (!BugpointIsInterrupted
) {
520 std::vector
<const Instruction
*> Insts
;
521 for (Module::const_iterator MI
= BD
.getProgram()->begin(),
522 ME
= BD
.getProgram()->end(); MI
!= ME
; ++MI
)
523 for (Function::const_iterator FI
= MI
->begin(), FE
= MI
->end(); FI
!= FE
;
525 for (BasicBlock::const_iterator I
= FI
->begin(), E
= FI
->end();
527 if (!isa
<TerminatorInst
>(I
))
530 ReduceCrashingInstructions(BD
, TestFn
).reduceList(Insts
, Error
);
533 // FIXME: This should use the list reducer to converge faster by deleting
534 // larger chunks of instructions at a time!
535 unsigned Simplification
= 2;
537 if (BugpointIsInterrupted
) break;
539 outs() << "\n*** Attempting to reduce testcase by deleting instruc"
540 << "tions: Simplification Level #" << Simplification
<< '\n';
542 // Now that we have deleted the functions that are unnecessary for the
543 // program, try to remove instructions that are not necessary to cause the
544 // crash. To do this, we loop through all of the instructions in the
545 // remaining functions, deleting them (replacing any values produced with
546 // nulls), and then running ADCE and SimplifyCFG. If the transformed input
547 // still triggers failure, keep deleting until we cannot trigger failure
550 unsigned InstructionsToSkipBeforeDeleting
= 0;
553 // Loop over all of the (non-terminator) instructions remaining in the
554 // function, attempting to delete them.
555 unsigned CurInstructionNum
= 0;
556 for (Module::const_iterator FI
= BD
.getProgram()->begin(),
557 E
= BD
.getProgram()->end(); FI
!= E
; ++FI
)
558 if (!FI
->isDeclaration())
559 for (Function::const_iterator BI
= FI
->begin(), E
= FI
->end(); BI
!= E
;
561 for (BasicBlock::const_iterator I
= BI
->begin(), E
= --BI
->end();
562 I
!= E
; ++I
, ++CurInstructionNum
)
563 if (InstructionsToSkipBeforeDeleting
) {
564 --InstructionsToSkipBeforeDeleting
;
566 if (BugpointIsInterrupted
) goto ExitLoops
;
568 outs() << "Checking instruction: " << *I
;
569 Module
*M
= BD
.deleteInstructionFromProgram(I
, Simplification
);
571 // Find out if the pass still crashes on this pass...
573 // Yup, it does, we delete the old module, and continue trying
574 // to reduce the testcase...
576 InstructionsToSkipBeforeDeleting
= CurInstructionNum
;
577 goto TryAgain
; // I wish I had a multi-level break here!
580 // This pass didn't crash without this instruction, try the next
585 if (InstructionsToSkipBeforeDeleting
) {
586 InstructionsToSkipBeforeDeleting
= 0;
590 } while (Simplification
);
593 // Try to clean up the testcase by running funcresolve and globaldce...
594 if (!BugpointIsInterrupted
) {
595 outs() << "\n*** Attempting to perform final cleanups: ";
596 Module
*M
= CloneModule(BD
.getProgram());
597 M
= BD
.performFinalCleanups(M
, true);
599 // Find out if the pass still crashes on the cleaned up program...
601 BD
.setNewProgram(M
); // Yup, it does, keep the reduced version...
607 BD
.EmitProgressBitcode(BD
.getProgram(), "reduced-simplified");
612 static bool TestForOptimizerCrash(const BugDriver
&BD
, Module
*M
) {
613 return BD
.runPasses(M
);
616 /// debugOptimizerCrash - This method is called when some pass crashes on input.
617 /// It attempts to prune down the testcase to something reasonable, and figure
618 /// out exactly which pass is crashing.
620 bool BugDriver::debugOptimizerCrash(const std::string
&ID
) {
621 outs() << "\n*** Debugging optimizer crash!\n";
624 // Reduce the list of passes which causes the optimizer to crash...
625 if (!BugpointIsInterrupted
)
626 ReducePassList(*this).reduceList(PassesToRun
, Error
);
627 assert(Error
.empty());
629 outs() << "\n*** Found crashing pass"
630 << (PassesToRun
.size() == 1 ? ": " : "es: ")
631 << getPassesString(PassesToRun
) << '\n';
633 EmitProgressBitcode(Program
, ID
);
635 bool Success
= DebugACrash(*this, TestForOptimizerCrash
, Error
);
636 assert(Error
.empty());
640 static bool TestForCodeGenCrash(const BugDriver
&BD
, Module
*M
) {
642 BD
.compileProgram(M
, &Error
);
643 if (!Error
.empty()) {
644 errs() << "<crash>\n";
645 return true; // Tool is still crashing.
651 /// debugCodeGeneratorCrash - This method is called when the code generator
652 /// crashes on an input. It attempts to reduce the input as much as possible
653 /// while still causing the code generator to crash.
654 bool BugDriver::debugCodeGeneratorCrash(std::string
&Error
) {
655 errs() << "*** Debugging code generator crash!\n";
657 return DebugACrash(*this, TestForCodeGenCrash
, Error
);