CrashDebugger.cpp revision 6520785dcd22012535934098942d57c07c7631c2
1afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner//===- CrashDebugger.cpp - Debug compilation crashes ----------------------===// 2afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner// 3afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner// This file defines the bugpoint internals that narrow down compilation crashes 4afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner// 5afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner//===----------------------------------------------------------------------===// 6afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 7afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "BugDriver.h" 8218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner#include "SystemUtils.h" 9afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "llvm/Module.h" 10afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "llvm/Bytecode/Writer.h" 11afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "llvm/Pass.h" 12afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include <fstream> 13afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 14afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// debugCrash - This method is called when some pass crashes on input. It 15afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// attempts to prune down the testcase to something reasonable, and figure 16afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// out exactly which pass is crashing. 17afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// 18afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattnerbool BugDriver::debugCrash() { 19afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::cout << "\n*** Debugging optimizer crash!\n"; 20afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 21afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Determine which pass causes the optimizer to crash... using binary search 22afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner unsigned LastToPass = 0, LastToCrash = PassesToRun.size(); 23afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner while (LastToPass != LastToCrash) { 24afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner unsigned Mid = (LastToCrash+LastToPass+1) / 2; 25afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::vector<const PassInfo*> P(PassesToRun.begin(), 26afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner PassesToRun.begin()+Mid); 27afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::cout << "Checking to see if the first " << Mid << " passes crash: "; 28afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 29afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner if (runPasses(P)) 30afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner LastToCrash = Mid-1; 31afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner else 32afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner LastToPass = Mid; 33afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner } 34afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 35afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Make sure something crashed. :) 36afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner if (LastToCrash >= PassesToRun.size()) { 37afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::cerr << "ERROR: No passes crashed!\n"; 38afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner return true; 39afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner } 40afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 41afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Calculate which pass it is that crashes... 42afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner const PassInfo *CrashingPass = PassesToRun[LastToCrash]; 43afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 44afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::cout << "\n*** Found crashing pass '-" << CrashingPass->getPassArgument() 45afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner << "': " << CrashingPass->getPassName() << "\n"; 46afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 47afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Compile the program with just the passes that don't crash. 48218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner if (LastToPass != 0) { // Don't bother doing this if the first pass crashes... 49afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::vector<const PassInfo*> P(PassesToRun.begin(), 50afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner PassesToRun.begin()+LastToPass); 51afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::string Filename; 52afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::cout << "Running passes that don't crash to get input for pass: "; 53afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner if (runPasses(P, Filename)) { 54afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::cerr << "ERROR: Running the first " << LastToPass 55afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner << " passes crashed this time!\n"; 56afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner return true; 57afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner } 58afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 59afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Assuming everything was successful, we now have a valid bytecode file in 60afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // OutputName. Use it for "Program" Instead. 61afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner delete Program; 62afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner Program = ParseInputFile(Filename); 63afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 64afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Delete the file now. 65afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner removeFile(Filename); 66afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner } 67afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 68afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner return debugPassCrash(CrashingPass); 69afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner} 70afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 71afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// CountFunctions - return the number of non-external functions defined in the 72afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// module. 73afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattnerstatic unsigned CountFunctions(Module *M) { 74afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner unsigned N = 0; 75afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 76afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner if (!I->isExternal()) 77afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner ++N; 78afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner return N; 79afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner} 80afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 81afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// debugPassCrash - This method is called when the specified pass crashes on 82afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// Program as input. It tries to reduce the testcase to something that still 83afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// crashes, but it smaller. 84afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// 85afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattnerbool BugDriver::debugPassCrash(const PassInfo *Pass) { 86afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner EmitProgressBytecode(Pass, "passinput"); 87afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 88afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner if (CountFunctions(Program) > 1) { 89afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Attempt to reduce the input program down to a single function that still 90218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner // crashes. Do this by removing everything except for that one function... 91afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // 92afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::cout << "\n*** Attempting to reduce the testcase to one function\n"; 93afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 94afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) 95afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner if (!I->isExternal()) { 96afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Extract one function from the module... 97afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner Module *M = extractFunctionFromModule(I); 98afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 99afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Make the function the current program... 100afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::swap(Program, M); 101afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 102afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Find out if the pass still crashes on this pass... 103afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::cout << "Checking function '" << I->getName() << "': "; 104afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner if (runPass(Pass)) { 105afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // Yup, it does, we delete the old module, and continue trying to 106afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // reduce the testcase... 107afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner delete M; 108afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 109afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner EmitProgressBytecode(Pass, "reduced-"+I->getName()); 110afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner break; 111afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner } 112afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 113afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner // This pass didn't crash on this function, try the next one. 114afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner delete Program; 115afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner Program = M; 116afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner } 117afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 1186520785dcd22012535934098942d57c07c7631c2Chris Lattner if (CountFunctions(Program) > 1) { 1196520785dcd22012535934098942d57c07c7631c2Chris Lattner std::cout << "\n*** Couldn't reduce testcase to one function.\n" 1206520785dcd22012535934098942d57c07c7631c2Chris Lattner << " Attempting to remove individual functions.\n"; 1216520785dcd22012535934098942d57c07c7631c2Chris Lattner std::cout << "XXX Individual function removal unimplemented!\n"; 1226520785dcd22012535934098942d57c07c7631c2Chris Lattner } 123218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner } 124218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner 1256520785dcd22012535934098942d57c07c7631c2Chris Lattner // FIXME: This should attempt to delete entire basic blocks at a time to speed 1266520785dcd22012535934098942d57c07c7631c2Chris Lattner // up convergence... 1276520785dcd22012535934098942d57c07c7631c2Chris Lattner 1286520785dcd22012535934098942d57c07c7631c2Chris Lattner unsigned Simplification = 4; 1296520785dcd22012535934098942d57c07c7631c2Chris Lattner do { 1306520785dcd22012535934098942d57c07c7631c2Chris Lattner --Simplification; 1316520785dcd22012535934098942d57c07c7631c2Chris Lattner std::cout << "\n*** Attempting to reduce testcase by deleting instruc" 1326520785dcd22012535934098942d57c07c7631c2Chris Lattner << "tions: Simplification Level #" << Simplification << "\n"; 1336520785dcd22012535934098942d57c07c7631c2Chris Lattner 1346520785dcd22012535934098942d57c07c7631c2Chris Lattner // Now that we have deleted the functions that are unneccesary for the 1356520785dcd22012535934098942d57c07c7631c2Chris Lattner // program, try to remove instructions that are not neccesary to cause the 1366520785dcd22012535934098942d57c07c7631c2Chris Lattner // crash. To do this, we loop through all of the instructions in the 1376520785dcd22012535934098942d57c07c7631c2Chris Lattner // remaining functions, deleting them (replacing any values produced with 1386520785dcd22012535934098942d57c07c7631c2Chris Lattner // nulls), and then running ADCE and SimplifyCFG. If the transformed input 1396520785dcd22012535934098942d57c07c7631c2Chris Lattner // still triggers failure, keep deleting until we cannot trigger failure 1406520785dcd22012535934098942d57c07c7631c2Chris Lattner // anymore. 1416520785dcd22012535934098942d57c07c7631c2Chris Lattner // 1426520785dcd22012535934098942d57c07c7631c2Chris Lattner TryAgain: 1436520785dcd22012535934098942d57c07c7631c2Chris Lattner 1446520785dcd22012535934098942d57c07c7631c2Chris Lattner // Loop over all of the (non-terminator) instructions remaining in the 1456520785dcd22012535934098942d57c07c7631c2Chris Lattner // function, attempting to delete them. 1466520785dcd22012535934098942d57c07c7631c2Chris Lattner for (Module::iterator FI = Program->begin(), E = Program->end(); 1476520785dcd22012535934098942d57c07c7631c2Chris Lattner FI != E; ++FI) 1486520785dcd22012535934098942d57c07c7631c2Chris Lattner if (!FI->isExternal()) { 1496520785dcd22012535934098942d57c07c7631c2Chris Lattner for (Function::iterator BI = FI->begin(), E = FI->end(); BI != E; ++BI) 1506520785dcd22012535934098942d57c07c7631c2Chris Lattner for (BasicBlock::iterator I = BI->begin(), E = --BI->end(); 1516520785dcd22012535934098942d57c07c7631c2Chris Lattner I != E; ++I) { 1526520785dcd22012535934098942d57c07c7631c2Chris Lattner Module *M = deleteInstructionFromProgram(I, Simplification); 1536520785dcd22012535934098942d57c07c7631c2Chris Lattner 1546520785dcd22012535934098942d57c07c7631c2Chris Lattner // Make the function the current program... 1556520785dcd22012535934098942d57c07c7631c2Chris Lattner std::swap(Program, M); 1566520785dcd22012535934098942d57c07c7631c2Chris Lattner 1576520785dcd22012535934098942d57c07c7631c2Chris Lattner // Find out if the pass still crashes on this pass... 1586520785dcd22012535934098942d57c07c7631c2Chris Lattner std::cout << "Checking instruction '" << I->getName() << "': "; 1596520785dcd22012535934098942d57c07c7631c2Chris Lattner if (runPass(Pass)) { 1606520785dcd22012535934098942d57c07c7631c2Chris Lattner // Yup, it does, we delete the old module, and continue trying to 1616520785dcd22012535934098942d57c07c7631c2Chris Lattner // reduce the testcase... 1626520785dcd22012535934098942d57c07c7631c2Chris Lattner EmitProgressBytecode(Pass, "reduced-" + I->getName()); 1636520785dcd22012535934098942d57c07c7631c2Chris Lattner delete M; 1646520785dcd22012535934098942d57c07c7631c2Chris Lattner goto TryAgain; // I wish I had a multi-level break here! 1656520785dcd22012535934098942d57c07c7631c2Chris Lattner } 1666520785dcd22012535934098942d57c07c7631c2Chris Lattner 1676520785dcd22012535934098942d57c07c7631c2Chris Lattner // This pass didn't crash without this instruction, try the next 1686520785dcd22012535934098942d57c07c7631c2Chris Lattner // one. 1696520785dcd22012535934098942d57c07c7631c2Chris Lattner delete Program; 1706520785dcd22012535934098942d57c07c7631c2Chris Lattner Program = M; 1716520785dcd22012535934098942d57c07c7631c2Chris Lattner } 1726520785dcd22012535934098942d57c07c7631c2Chris Lattner } 1736520785dcd22012535934098942d57c07c7631c2Chris Lattner } while (Simplification); 174218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner 175afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner return false; 176afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner} 177