X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=tools%2Fbugpoint%2FCrashDebugger.cpp;h=ecb17342cb71210fb17b0ab224af8fc504fc0f25;hb=fa76183e8e28985dfd17b1d6291c939dab4cbe1d;hp=daf3915a5ebc83d978df1e53319ff44ef6e7e455;hpb=6520785dcd22012535934098942d57c07c7631c2;p=oota-llvm.git diff --git a/tools/bugpoint/CrashDebugger.cpp b/tools/bugpoint/CrashDebugger.cpp index daf3915a5eb..ecb17342cb7 100644 --- a/tools/bugpoint/CrashDebugger.cpp +++ b/tools/bugpoint/CrashDebugger.cpp @@ -1,138 +1,352 @@ //===- CrashDebugger.cpp - Debug compilation crashes ----------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// // // This file defines the bugpoint internals that narrow down compilation crashes // //===----------------------------------------------------------------------===// #include "BugDriver.h" -#include "SystemUtils.h" +#include "ListReducer.h" +#include "llvm/Constant.h" +#include "llvm/iTerminators.h" #include "llvm/Module.h" -#include "llvm/Bytecode/Writer.h" #include "llvm/Pass.h" +#include "llvm/PassManager.h" +#include "llvm/SymbolTable.h" +#include "llvm/Type.h" +#include "llvm/Analysis/Verifier.h" +#include "llvm/Bytecode/Writer.h" +#include "llvm/Support/CFG.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "Support/FileUtilities.h" #include +#include +using namespace llvm; -/// debugCrash - This method is called when some pass crashes on input. It -/// attempts to prune down the testcase to something reasonable, and figure -/// out exactly which pass is crashing. -/// -bool BugDriver::debugCrash() { - std::cout << "\n*** Debugging optimizer crash!\n"; +namespace llvm { + class DebugCrashes : public ListReducer { + BugDriver &BD; + public: + DebugCrashes(BugDriver &bd) : BD(bd) {} + + // doTest - Return true iff running the "removed" passes succeeds, and + // running the "Kept" passes fail when run on the output of the "removed" + // passes. If we return true, we update the current module of bugpoint. + // + virtual TestResult doTest(std::vector &Removed, + std::vector &Kept); + }; +} - // Determine which pass causes the optimizer to crash... using binary search - unsigned LastToPass = 0, LastToCrash = PassesToRun.size(); - while (LastToPass != LastToCrash) { - unsigned Mid = (LastToCrash+LastToPass+1) / 2; - std::vector P(PassesToRun.begin(), - PassesToRun.begin()+Mid); - std::cout << "Checking to see if the first " << Mid << " passes crash: "; - - if (runPasses(P)) - LastToCrash = Mid-1; - else - LastToPass = Mid; - } +DebugCrashes::TestResult +DebugCrashes::doTest(std::vector &Prefix, + std::vector &Suffix) { + std::string PrefixOutput; + Module *OrigProgram = 0; + if (!Prefix.empty()) { + std::cout << "Checking to see if these passes crash: " + << getPassesString(Prefix) << ": "; + if (BD.runPasses(Prefix, PrefixOutput)) + return KeepPrefix; - // Make sure something crashed. :) - if (LastToCrash >= PassesToRun.size()) { - std::cerr << "ERROR: No passes crashed!\n"; - return true; + OrigProgram = BD.Program; + + BD.Program = BD.ParseInputFile(PrefixOutput); + if (BD.Program == 0) { + std::cerr << BD.getToolName() << ": Error reading bytecode file '" + << PrefixOutput << "'!\n"; + exit(1); + } + removeFile(PrefixOutput); } - // Calculate which pass it is that crashes... - const PassInfo *CrashingPass = PassesToRun[LastToCrash]; + std::cout << "Checking to see if these passes crash: " + << getPassesString(Suffix) << ": "; - std::cout << "\n*** Found crashing pass '-" << CrashingPass->getPassArgument() - << "': " << CrashingPass->getPassName() << "\n"; - - // Compile the program with just the passes that don't crash. - if (LastToPass != 0) { // Don't bother doing this if the first pass crashes... - std::vector P(PassesToRun.begin(), - PassesToRun.begin()+LastToPass); - std::string Filename; - std::cout << "Running passes that don't crash to get input for pass: "; - if (runPasses(P, Filename)) { - std::cerr << "ERROR: Running the first " << LastToPass - << " passes crashed this time!\n"; - return true; + if (BD.runPasses(Suffix)) { + delete OrigProgram; // The suffix crashes alone... + return KeepSuffix; + } + + // Nothing failed, restore state... + if (OrigProgram) { + delete BD.Program; + BD.Program = OrigProgram; + } + return NoFailure; +} + +namespace llvm { + class ReduceCrashingFunctions : public ListReducer { + BugDriver &BD; + public: + ReduceCrashingFunctions(BugDriver &bd) : BD(bd) {} + + virtual TestResult doTest(std::vector &Prefix, + std::vector &Kept) { + if (!Kept.empty() && TestFuncs(Kept)) + return KeepSuffix; + if (!Prefix.empty() && TestFuncs(Prefix)) + return KeepPrefix; + return NoFailure; } + + bool TestFuncs(std::vector &Prefix); + }; +} - // Assuming everything was successful, we now have a valid bytecode file in - // OutputName. Use it for "Program" Instead. - delete Program; - Program = ParseInputFile(Filename); +bool ReduceCrashingFunctions::TestFuncs(std::vector &Funcs) { + // Clone the program to try hacking it apart... + Module *M = CloneModule(BD.Program); + + // Convert list to set for fast lookup... + std::set Functions; + for (unsigned i = 0, e = Funcs.size(); i != e; ++i) { + Function *CMF = M->getFunction(Funcs[i]->getName(), + Funcs[i]->getFunctionType()); + assert(CMF && "Function not in module?!"); + Functions.insert(CMF); + } - // Delete the file now. - removeFile(Filename); + std::cout << "Checking for crash with only these functions:"; + unsigned NumPrint = Funcs.size(); + if (NumPrint > 10) NumPrint = 10; + for (unsigned i = 0; i != NumPrint; ++i) + std::cout << " " << Funcs[i]->getName(); + if (NumPrint < Funcs.size()) + std::cout << "... <" << Funcs.size() << " total>"; + std::cout << ": "; + + // Loop over and delete any functions which we aren't supposed to be playing + // with... + for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) + if (!I->isExternal() && !Functions.count(I)) + DeleteFunctionBody(I); + + // Try running the hacked up program... + std::swap(BD.Program, M); + if (BD.runPasses(BD.PassesToRun)) { + delete M; // It crashed, keep the trimmed version... + + // Make sure to use function pointers that point into the now-current + // module. + Funcs.assign(Functions.begin(), Functions.end()); + return true; } + delete BD.Program; // It didn't crash, revert... + BD.Program = M; + return false; +} + - return debugPassCrash(CrashingPass); +namespace llvm { + /// ReduceCrashingBlocks reducer - This works by setting the terminators of + /// all terminators except the specified basic blocks to a 'ret' instruction, + /// then running the simplify-cfg pass. This has the effect of chopping up + /// the CFG really fast which can reduce large functions quickly. + /// + class ReduceCrashingBlocks : public ListReducer { + BugDriver &BD; + public: + ReduceCrashingBlocks(BugDriver &bd) : BD(bd) {} + + virtual TestResult doTest(std::vector &Prefix, + std::vector &Kept) { + if (!Kept.empty() && TestBlocks(Kept)) + return KeepSuffix; + if (!Prefix.empty() && TestBlocks(Prefix)) + return KeepPrefix; + return NoFailure; + } + + bool TestBlocks(std::vector &Prefix); + }; } -/// CountFunctions - return the number of non-external functions defined in the -/// module. -static unsigned CountFunctions(Module *M) { - unsigned N = 0; +bool ReduceCrashingBlocks::TestBlocks(std::vector &BBs) { + // Clone the program to try hacking it apart... + Module *M = CloneModule(BD.Program); + + // Convert list to set for fast lookup... + std::set Blocks; + for (unsigned i = 0, e = BBs.size(); i != e; ++i) { + // Convert the basic block from the original module to the new module... + Function *F = BBs[i]->getParent(); + Function *CMF = M->getFunction(F->getName(), F->getFunctionType()); + assert(CMF && "Function not in module?!"); + + // Get the mapped basic block... + Function::iterator CBI = CMF->begin(); + std::advance(CBI, std::distance(F->begin(), Function::iterator(BBs[i]))); + Blocks.insert(CBI); + } + + std::cout << "Checking for crash with only these blocks:"; + unsigned NumPrint = Blocks.size(); + if (NumPrint > 10) NumPrint = 10; + for (unsigned i = 0, e = NumPrint; i != e; ++i) + std::cout << " " << BBs[i]->getName(); + if (NumPrint < Blocks.size()) + std::cout << "... <" << Blocks.size() << " total>"; + std::cout << ": "; + + // Loop over and delete any hack up any blocks that are not listed... for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) - if (!I->isExternal()) - ++N; - return N; + for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB) + if (!Blocks.count(BB) && BB->getTerminator()->getNumSuccessors()) { + // Loop over all of the successors of this block, deleting any PHI nodes + // that might include it. + for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) + (*SI)->removePredecessor(BB); + + if (BB->getTerminator()->getType() != Type::VoidTy) + BB->getTerminator()->replaceAllUsesWith( + Constant::getNullValue(BB->getTerminator()->getType())); + + // Delete the old terminator instruction... + BB->getInstList().pop_back(); + + // Add a new return instruction of the appropriate type... + const Type *RetTy = BB->getParent()->getReturnType(); + new ReturnInst(RetTy == Type::VoidTy ? 0 : + Constant::getNullValue(RetTy), BB); + } + + // The CFG Simplifier pass may delete one of the basic blocks we are + // interested in. If it does we need to take the block out of the list. Make + // a "persistent mapping" by turning basic blocks into pairs. + // This won't work well if blocks are unnamed, but that is just the risk we + // have to take. + std::vector > BlockInfo; + + for (std::set::iterator I = Blocks.begin(), E = Blocks.end(); + I != E; ++I) + BlockInfo.push_back(std::make_pair((*I)->getParent(), (*I)->getName())); + + // Now run the CFG simplify pass on the function... + PassManager Passes; + Passes.add(createCFGSimplificationPass()); + Passes.add(createVerifierPass()); + Passes.run(*M); + + // Try running on the hacked up program... + std::swap(BD.Program, M); + if (BD.runPasses(BD.PassesToRun)) { + delete M; // It crashed, keep the trimmed version... + + // Make sure to use basic block pointers that point into the now-current + // module, and that they don't include any deleted blocks. + BBs.clear(); + for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { + SymbolTable &ST = BlockInfo[i].first->getSymbolTable(); + SymbolTable::iterator I = ST.find(Type::LabelTy); + if (I != ST.end() && I->second.count(BlockInfo[i].second)) + BBs.push_back(cast(I->second[BlockInfo[i].second])); + } + return true; + } + delete BD.Program; // It didn't crash, revert... + BD.Program = M; + return false; } -/// debugPassCrash - This method is called when the specified pass crashes on -/// Program as input. It tries to reduce the testcase to something that still -/// crashes, but it smaller. +/// debugCrash - This method is called when some pass crashes on input. It +/// attempts to prune down the testcase to something reasonable, and figure +/// out exactly which pass is crashing. /// -bool BugDriver::debugPassCrash(const PassInfo *Pass) { - EmitProgressBytecode(Pass, "passinput"); +bool BugDriver::debugCrash() { + bool AnyReduction = false; + std::cout << "\n*** Debugging optimizer crash!\n"; - if (CountFunctions(Program) > 1) { - // Attempt to reduce the input program down to a single function that still - // crashes. Do this by removing everything except for that one function... - // - std::cout << "\n*** Attempting to reduce the testcase to one function\n"; + // Reduce the list of passes which causes the optimizer to crash... + unsigned OldSize = PassesToRun.size(); + DebugCrashes(*this).reduceList(PassesToRun); - for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) - if (!I->isExternal()) { - // Extract one function from the module... - Module *M = extractFunctionFromModule(I); + std::cout << "\n*** Found crashing pass" + << (PassesToRun.size() == 1 ? ": " : "es: ") + << getPassesString(PassesToRun) << "\n"; - // Make the function the current program... - std::swap(Program, M); - - // Find out if the pass still crashes on this pass... - std::cout << "Checking function '" << I->getName() << "': "; - if (runPass(Pass)) { - // Yup, it does, we delete the old module, and continue trying to - // reduce the testcase... - delete M; - - EmitProgressBytecode(Pass, "reduced-"+I->getName()); - break; - } - - // This pass didn't crash on this function, try the next one. - delete Program; + EmitProgressBytecode("passinput"); + + // See if we can get away with nuking all of the global variable initializers + // in the program... + if (Program->gbegin() != Program->gend()) { + Module *M = CloneModule(Program); + bool DeletedInit = false; + for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I) + if (I->hasInitializer()) { + I->setInitializer(0); + I->setLinkage(GlobalValue::ExternalLinkage); + DeletedInit = true; + } + + if (!DeletedInit) { + delete M; // No change made... + } else { + // See if the program still causes a crash... + std::cout << "\nChecking to see if we can delete global inits: "; + std::swap(Program, M); + if (runPasses(PassesToRun)) { // Still crashes? + AnyReduction = true; + delete M; + std::cout << "\n*** Able to remove all global initializers!\n"; + } else { // No longer crashes? + delete Program; // Restore program. Program = M; + std::cout << " - Removing all global inits hides problem!\n"; } + } + } + + // Now try to reduce the number of functions in the module to something small. + std::vector Functions; + for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) + if (!I->isExternal()) + Functions.push_back(I); + + if (Functions.size() > 1) { + std::cout << "\n*** Attempting to reduce the number of functions " + "in the testcase\n"; - if (CountFunctions(Program) > 1) { - std::cout << "\n*** Couldn't reduce testcase to one function.\n" - << " Attempting to remove individual functions.\n"; - std::cout << "XXX Individual function removal unimplemented!\n"; + OldSize = Functions.size(); + ReduceCrashingFunctions(*this).reduceList(Functions); + + if (Functions.size() < OldSize) { + EmitProgressBytecode("reduced-function"); + AnyReduction = true; } } - // FIXME: This should attempt to delete entire basic blocks at a time to speed - // up convergence... + // Attempt to delete entire basic blocks at a time to speed up + // convergence... this actually works by setting the terminator of the blocks + // to a return instruction then running simplifycfg, which can potentially + // shrinks the code dramatically quickly + // + if (!DisableSimplifyCFG) { + std::vector Blocks; + for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) + for (Function::iterator FI = I->begin(), E = I->end(); FI != E; ++FI) + Blocks.push_back(FI); + ReduceCrashingBlocks(*this).reduceList(Blocks); + } + // FIXME: This should use the list reducer to converge faster by deleting + // larger chunks of instructions at a time! unsigned Simplification = 4; do { --Simplification; std::cout << "\n*** Attempting to reduce testcase by deleting instruc" << "tions: Simplification Level #" << Simplification << "\n"; - // Now that we have deleted the functions that are unneccesary for the - // program, try to remove instructions that are not neccesary to cause the + // Now that we have deleted the functions that are unnecessary for the + // program, try to remove instructions that are not necessary to cause the // crash. To do this, we loop through all of the instructions in the // remaining functions, deleting them (replacing any values produced with // nulls), and then running ADCE and SimplifyCFG. If the transformed input @@ -156,11 +370,11 @@ bool BugDriver::debugPassCrash(const PassInfo *Pass) { // Find out if the pass still crashes on this pass... std::cout << "Checking instruction '" << I->getName() << "': "; - if (runPass(Pass)) { + if (runPasses(PassesToRun)) { // Yup, it does, we delete the old module, and continue trying to // reduce the testcase... - EmitProgressBytecode(Pass, "reduced-" + I->getName()); delete M; + AnyReduction = true; goto TryAgain; // I wish I had a multi-level break here! } @@ -171,6 +385,26 @@ bool BugDriver::debugPassCrash(const PassInfo *Pass) { } } } while (Simplification); - + + // Try to clean up the testcase by running funcresolve and globaldce... + std::cout << "\n*** Attempting to perform final cleanups: "; + Module *M = CloneModule(Program); + M = performFinalCleanups(M, true); + std::swap(Program, M); + + // Find out if the pass still crashes on the cleaned up program... + if (runPasses(PassesToRun)) { + // Yup, it does, keep the reduced version... + delete M; + AnyReduction = true; + } else { + delete Program; // Otherwise, restore the original module... + Program = M; + } + + if (AnyReduction) + EmitProgressBytecode("reduced-simplified"); + return false; } +