CrashDebugger.cpp revision b417c795d2a8832b5edac321dc0d19eca7e3f2f5
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" 9aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner#include "ListReducer.h" 10afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "llvm/Module.h" 11286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/PassManager.h" 12286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/Pass.h" 13286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/Constant.h" 14286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/iTerminators.h" 15286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/Type.h" 16286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/SymbolTable.h" 17286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/Support/CFG.h" 18286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/Analysis/Verifier.h" 19286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/Transforms/Scalar.h" 20aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner#include "llvm/Transforms/Utils/Cloning.h" 21afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "llvm/Bytecode/Writer.h" 22afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include <fstream> 23aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner#include <set> 24afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 25640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattnerclass DebugCrashes : public ListReducer<const PassInfo*> { 26640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner BugDriver &BD; 27640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattnerpublic: 28640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner DebugCrashes(BugDriver &bd) : BD(bd) {} 29640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner 30640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner // doTest - Return true iff running the "removed" passes succeeds, and running 31640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner // the "Kept" passes fail when run on the output of the "removed" passes. If 32640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner // we return true, we update the current module of bugpoint. 33640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner // 34aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner virtual TestResult doTest(std::vector<const PassInfo*> &Removed, 35aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::vector<const PassInfo*> &Kept); 36aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner}; 37aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 38aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris LattnerDebugCrashes::TestResult 39aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris LattnerDebugCrashes::doTest(std::vector<const PassInfo*> &Prefix, 40aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::vector<const PassInfo*> &Suffix) { 41aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::string PrefixOutput; 42b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner Module *OrigProgram = 0; 43aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (!Prefix.empty()) { 44aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << "Checking to see if these passes crash: " 45aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner << getPassesString(Prefix) << ": "; 46aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (BD.runPasses(Prefix, PrefixOutput)) 47aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return KeepPrefix; 48b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner 49b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner OrigProgram = BD.Program; 50b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner 51b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner BD.Program = BD.ParseInputFile(PrefixOutput); 52b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner if (BD.Program == 0) { 53b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner std::cerr << BD.getToolName() << ": Error reading bytecode file '" 54b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner << PrefixOutput << "'!\n"; 55b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner exit(1); 56b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner } 57b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner removeFile(PrefixOutput); 58aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner } 59aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 60aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << "Checking to see if these passes crash: " 61aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner << getPassesString(Suffix) << ": "; 62b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner 63aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (BD.runPasses(Suffix)) { 64aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner delete OrigProgram; // The suffix crashes alone... 65aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return KeepSuffix; 66aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner } 67aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 68aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Nothing failed, restore state... 69b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner if (OrigProgram) { 70b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner delete BD.Program; 71b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner BD.Program = OrigProgram; 72b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner } 73aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return NoFailure; 74aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner} 75aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 76aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattnerclass ReduceCrashingFunctions : public ListReducer<Function*> { 77aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner BugDriver &BD; 78aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattnerpublic: 79aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner ReduceCrashingFunctions(BugDriver &bd) : BD(bd) {} 80aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 81aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner virtual TestResult doTest(std::vector<Function*> &Prefix, 82aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::vector<Function*> &Kept) { 83aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (TestFuncs(Kept)) 84aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return KeepSuffix; 85aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (!Prefix.empty() && TestFuncs(Prefix)) 86aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return KeepPrefix; 87aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return NoFailure; 88640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner } 89aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 90aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner bool TestFuncs(std::vector<Function*> &Prefix); 91640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner}; 92aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 93aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattnerbool ReduceCrashingFunctions::TestFuncs(std::vector<Function*> &Funcs) { 94aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Clone the program to try hacking it appart... 95aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner Module *M = CloneModule(BD.Program); 96aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 97aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Convert list to set for fast lookup... 98aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::set<Function*> Functions; 99aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner for (unsigned i = 0, e = Funcs.size(); i != e; ++i) { 100aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner Function *CMF = M->getFunction(Funcs[i]->getName(), 101aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner Funcs[i]->getFunctionType()); 102aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner assert(CMF && "Function not in module?!"); 103f607b79bc78fcbfd8cda01d2d5dbda6cd8253a40Chris Lattner Functions.insert(CMF); 104aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner } 105aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 106aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << "Checking for crash with only these functions:"; 107aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner for (unsigned i = 0, e = Funcs.size(); i != e; ++i) 108aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << " " << Funcs[i]->getName(); 109aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << ": "; 110aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 111aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Loop over and delete any functions which we aren't supposed to be playing 112aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // with... 113aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 114f607b79bc78fcbfd8cda01d2d5dbda6cd8253a40Chris Lattner if (!I->isExternal() && !Functions.count(I)) 115aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner DeleteFunctionBody(I); 116aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 117aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Try running the hacked up program... 118aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::swap(BD.Program, M); 119aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (BD.runPasses(BD.PassesToRun)) { 120aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner delete M; // It crashed, keep the trimmed version... 121aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 122aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Make sure to use function pointers that point into the now-current 123aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // module. 124aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner Funcs.assign(Functions.begin(), Functions.end()); 125aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return true; 126aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner } 127aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner delete BD.Program; // It didn't crash, revert... 128aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner BD.Program = M; 129aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return false; 130aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner} 131aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 132640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner 133286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner/// ReduceCrashingBlocks reducer - This works by setting the terminators of all 134286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner/// terminators except the specified basic blocks to a 'ret' instruction, then 135286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner/// running the simplify-cfg pass. This has the effect of chopping up the CFG 136286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner/// really fast which can reduce large functions quickly. 137286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner/// 138286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattnerclass ReduceCrashingBlocks : public ListReducer<BasicBlock*> { 139286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BugDriver &BD; 140286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattnerpublic: 141286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner ReduceCrashingBlocks(BugDriver &bd) : BD(bd) {} 142286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 143286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner virtual TestResult doTest(std::vector<BasicBlock*> &Prefix, 144286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::vector<BasicBlock*> &Kept) { 145286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner if (TestBlocks(Kept)) 146286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner return KeepSuffix; 147286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner if (!Prefix.empty() && TestBlocks(Prefix)) 148286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner return KeepPrefix; 149286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner return NoFailure; 150286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner } 151286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 152286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner bool TestBlocks(std::vector<BasicBlock*> &Prefix); 153286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner}; 154286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 155286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattnerbool ReduceCrashingBlocks::TestBlocks(std::vector<BasicBlock*> &BBs) { 156286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Clone the program to try hacking it appart... 157286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Module *M = CloneModule(BD.Program); 158286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 159286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Convert list to set for fast lookup... 160286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::set<BasicBlock*> Blocks; 161286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (unsigned i = 0, e = BBs.size(); i != e; ++i) { 162286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Convert the basic block from the original module to the new module... 163286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Function *F = BBs[i]->getParent(); 164286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Function *CMF = M->getFunction(F->getName(), F->getFunctionType()); 165286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner assert(CMF && "Function not in module?!"); 166286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 167286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Get the mapped basic block... 168286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Function::iterator CBI = CMF->begin(); 169286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::advance(CBI, std::distance(F->begin(), Function::iterator(BBs[i]))); 170286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Blocks.insert(CBI); 171286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner } 172286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 173286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::cout << "Checking for crash with only these blocks:"; 174286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (unsigned i = 0, e = Blocks.size(); i != e; ++i) 175286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::cout << " " << BBs[i]->getName(); 176286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::cout << ": "; 177286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 178286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Loop over and delete any hack up any blocks that are not listed... 179286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 180286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB) 181286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner if (!Blocks.count(BB) && !isa<ReturnInst>(BB->getTerminator())) { 182286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Loop over all of the successors of this block, deleting any PHI nodes 183286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // that might include it. 184286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 185286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner (*SI)->removePredecessor(BB); 186286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 187286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Delete the old terminator instruction... 188286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BB->getInstList().pop_back(); 189286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 190286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Add a new return instruction of the appropriate type... 191286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner const Type *RetTy = BB->getParent()->getReturnType(); 192286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner ReturnInst *RI = new ReturnInst(RetTy == Type::VoidTy ? 0 : 193286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Constant::getNullValue(RetTy)); 194286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BB->getInstList().push_back(RI); 195286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner } 196286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 197286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // The CFG Simplifier pass may delete one of the basic blocks we are 198286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // interested in. If it does we need to take the block out of the list. Make 199286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // a "persistent mapping" by turning basic blocks into <function, name> pairs. 200286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // This won't work well if blocks are unnamed, but that is just the risk we 201286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // have to take. 202286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::vector<std::pair<Function*, std::string> > BlockInfo; 203286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 204286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (std::set<BasicBlock*>::iterator I = Blocks.begin(), E = Blocks.end(); 205286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner I != E; ++I) 206286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BlockInfo.push_back(std::make_pair((*I)->getParent(), (*I)->getName())); 207286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 208286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Now run the CFG simplify pass on the function... 209286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner PassManager Passes; 210286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Passes.add(createCFGSimplificationPass()); 211286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Passes.add(createVerifierPass()); 212286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Passes.run(*M); 213286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 214286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Try running on the hacked up program... 215286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::swap(BD.Program, M); 216286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner if (BD.runPasses(BD.PassesToRun)) { 217286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner delete M; // It crashed, keep the trimmed version... 218286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 219286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Make sure to use basic block pointers that point into the now-current 220286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // module, and that they don't include any deleted blocks. 221286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BBs.clear(); 222286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { 223286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner SymbolTable &ST = BlockInfo[i].first->getSymbolTable(); 224286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner SymbolTable::iterator I = ST.find(Type::LabelTy); 225286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner if (I != ST.end() && I->second.count(BlockInfo[i].second)) 226286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BBs.push_back(cast<BasicBlock>(I->second[BlockInfo[i].second])); 227286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner } 228286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner return true; 229286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner } 230286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner delete BD.Program; // It didn't crash, revert... 231286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BD.Program = M; 232286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner return false; 233286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner} 234286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 235afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// debugCrash - This method is called when some pass crashes on input. It 236afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// attempts to prune down the testcase to something reasonable, and figure 237afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// out exactly which pass is crashing. 238afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// 239afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattnerbool BugDriver::debugCrash() { 240aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner bool AnyReduction = false; 241afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::cout << "\n*** Debugging optimizer crash!\n"; 242afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 243640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner // Reduce the list of passes which causes the optimizer to crash... 244aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner unsigned OldSize = PassesToRun.size(); 245640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner DebugCrashes(*this).reduceList(PassesToRun); 246afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 247aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << "\n*** Found crashing pass" 248aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner << (PassesToRun.size() == 1 ? ": " : "es: ") 249aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner << getPassesString(PassesToRun) << "\n"; 250640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner 251aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner EmitProgressBytecode("passinput"); 2525f73e38548c57636ad0ef8c719d040e166761962Chris Lattner 2535f73e38548c57636ad0ef8c719d040e166761962Chris Lattner // See if we can get away with nuking all of the global variable initializers 2545f73e38548c57636ad0ef8c719d040e166761962Chris Lattner // in the program... 2555f73e38548c57636ad0ef8c719d040e166761962Chris Lattner if (Program->gbegin() != Program->gend()) { 2565f73e38548c57636ad0ef8c719d040e166761962Chris Lattner Module *M = CloneModule(Program); 2575f73e38548c57636ad0ef8c719d040e166761962Chris Lattner bool DeletedInit = false; 2585f73e38548c57636ad0ef8c719d040e166761962Chris Lattner for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I) 2595f73e38548c57636ad0ef8c719d040e166761962Chris Lattner if (I->hasInitializer()) { 2605f73e38548c57636ad0ef8c719d040e166761962Chris Lattner I->setInitializer(0); 2615f73e38548c57636ad0ef8c719d040e166761962Chris Lattner I->setLinkage(GlobalValue::ExternalLinkage); 2625f73e38548c57636ad0ef8c719d040e166761962Chris Lattner DeletedInit = true; 2635f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } 2645f73e38548c57636ad0ef8c719d040e166761962Chris Lattner 2655f73e38548c57636ad0ef8c719d040e166761962Chris Lattner if (!DeletedInit) { 2665f73e38548c57636ad0ef8c719d040e166761962Chris Lattner delete M; // No change made... 2675f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } else { 2685f73e38548c57636ad0ef8c719d040e166761962Chris Lattner // See if the program still causes a crash... 2695f73e38548c57636ad0ef8c719d040e166761962Chris Lattner std::cout << "\nChecking to see if we can delete global inits: "; 2705f73e38548c57636ad0ef8c719d040e166761962Chris Lattner std::swap(Program, M); 2715f73e38548c57636ad0ef8c719d040e166761962Chris Lattner if (runPasses(PassesToRun)) { // Still crashes? 2725f73e38548c57636ad0ef8c719d040e166761962Chris Lattner AnyReduction = true; 2735f73e38548c57636ad0ef8c719d040e166761962Chris Lattner delete M; 2745f73e38548c57636ad0ef8c719d040e166761962Chris Lattner std::cout << "\n*** Able to remove all global initializers!\n"; 2755f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } else { // No longer crashes? 2765f73e38548c57636ad0ef8c719d040e166761962Chris Lattner delete Program; // Restore program. 2775f73e38548c57636ad0ef8c719d040e166761962Chris Lattner Program = M; 2785f73e38548c57636ad0ef8c719d040e166761962Chris Lattner std::cout << " - Removing all global inits hides problem!\n"; 2795f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } 2805f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } 2815f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } 282aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 283aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Now try to reduce the number of functions in the module to something small. 284aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::vector<Function*> Functions; 285aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) 286afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner if (!I->isExternal()) 287aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner Functions.push_back(I); 288afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 289aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (Functions.size() > 1) { 290aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << "\n*** Attempting to reduce the number of functions " 291aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner "in the testcase\n"; 292afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 293aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner OldSize = Functions.size(); 294aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner ReduceCrashingFunctions(*this).reduceList(Functions); 295afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 296aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (Functions.size() < OldSize) { 297aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner EmitProgressBytecode("reduced-function"); 298aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner AnyReduction = true; 2996520785dcd22012535934098942d57c07c7631c2Chris Lattner } 300218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner } 301218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner 302286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Attempt to delete entire basic blocks at a time to speed up 303286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // convergence... this actually works by setting the terminator of the blocks 304286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // to a return instruction then running simplifycfg, which can potentially 305286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // shrinks the code dramatically quickly 306286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // 307286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::vector<BasicBlock*> Blocks; 308286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) 309286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (Function::iterator FI = I->begin(), E = I->end(); FI != E; ++FI) 310286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Blocks.push_back(FI); 311286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner ReduceCrashingBlocks(*this).reduceList(Blocks); 3126520785dcd22012535934098942d57c07c7631c2Chris Lattner 313aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // FIXME: This should use the list reducer to converge faster by deleting 314aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // larger chunks of instructions at a time! 3156520785dcd22012535934098942d57c07c7631c2Chris Lattner unsigned Simplification = 4; 3166520785dcd22012535934098942d57c07c7631c2Chris Lattner do { 3176520785dcd22012535934098942d57c07c7631c2Chris Lattner --Simplification; 3186520785dcd22012535934098942d57c07c7631c2Chris Lattner std::cout << "\n*** Attempting to reduce testcase by deleting instruc" 3196520785dcd22012535934098942d57c07c7631c2Chris Lattner << "tions: Simplification Level #" << Simplification << "\n"; 3206520785dcd22012535934098942d57c07c7631c2Chris Lattner 3216520785dcd22012535934098942d57c07c7631c2Chris Lattner // Now that we have deleted the functions that are unneccesary for the 3226520785dcd22012535934098942d57c07c7631c2Chris Lattner // program, try to remove instructions that are not neccesary to cause the 3236520785dcd22012535934098942d57c07c7631c2Chris Lattner // crash. To do this, we loop through all of the instructions in the 3246520785dcd22012535934098942d57c07c7631c2Chris Lattner // remaining functions, deleting them (replacing any values produced with 3256520785dcd22012535934098942d57c07c7631c2Chris Lattner // nulls), and then running ADCE and SimplifyCFG. If the transformed input 3266520785dcd22012535934098942d57c07c7631c2Chris Lattner // still triggers failure, keep deleting until we cannot trigger failure 3276520785dcd22012535934098942d57c07c7631c2Chris Lattner // anymore. 3286520785dcd22012535934098942d57c07c7631c2Chris Lattner // 3296520785dcd22012535934098942d57c07c7631c2Chris Lattner TryAgain: 3306520785dcd22012535934098942d57c07c7631c2Chris Lattner 3316520785dcd22012535934098942d57c07c7631c2Chris Lattner // Loop over all of the (non-terminator) instructions remaining in the 3326520785dcd22012535934098942d57c07c7631c2Chris Lattner // function, attempting to delete them. 3336520785dcd22012535934098942d57c07c7631c2Chris Lattner for (Module::iterator FI = Program->begin(), E = Program->end(); 3346520785dcd22012535934098942d57c07c7631c2Chris Lattner FI != E; ++FI) 3356520785dcd22012535934098942d57c07c7631c2Chris Lattner if (!FI->isExternal()) { 3366520785dcd22012535934098942d57c07c7631c2Chris Lattner for (Function::iterator BI = FI->begin(), E = FI->end(); BI != E; ++BI) 3376520785dcd22012535934098942d57c07c7631c2Chris Lattner for (BasicBlock::iterator I = BI->begin(), E = --BI->end(); 3386520785dcd22012535934098942d57c07c7631c2Chris Lattner I != E; ++I) { 3396520785dcd22012535934098942d57c07c7631c2Chris Lattner Module *M = deleteInstructionFromProgram(I, Simplification); 3406520785dcd22012535934098942d57c07c7631c2Chris Lattner 3416520785dcd22012535934098942d57c07c7631c2Chris Lattner // Make the function the current program... 3426520785dcd22012535934098942d57c07c7631c2Chris Lattner std::swap(Program, M); 3436520785dcd22012535934098942d57c07c7631c2Chris Lattner 3446520785dcd22012535934098942d57c07c7631c2Chris Lattner // Find out if the pass still crashes on this pass... 3456520785dcd22012535934098942d57c07c7631c2Chris Lattner std::cout << "Checking instruction '" << I->getName() << "': "; 346aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (runPasses(PassesToRun)) { 3476520785dcd22012535934098942d57c07c7631c2Chris Lattner // Yup, it does, we delete the old module, and continue trying to 3486520785dcd22012535934098942d57c07c7631c2Chris Lattner // reduce the testcase... 3496520785dcd22012535934098942d57c07c7631c2Chris Lattner delete M; 350f607b79bc78fcbfd8cda01d2d5dbda6cd8253a40Chris Lattner AnyReduction = true; 3516520785dcd22012535934098942d57c07c7631c2Chris Lattner goto TryAgain; // I wish I had a multi-level break here! 3526520785dcd22012535934098942d57c07c7631c2Chris Lattner } 3536520785dcd22012535934098942d57c07c7631c2Chris Lattner 3546520785dcd22012535934098942d57c07c7631c2Chris Lattner // This pass didn't crash without this instruction, try the next 3556520785dcd22012535934098942d57c07c7631c2Chris Lattner // one. 3566520785dcd22012535934098942d57c07c7631c2Chris Lattner delete Program; 3576520785dcd22012535934098942d57c07c7631c2Chris Lattner Program = M; 3586520785dcd22012535934098942d57c07c7631c2Chris Lattner } 3596520785dcd22012535934098942d57c07c7631c2Chris Lattner } 3606520785dcd22012535934098942d57c07c7631c2Chris Lattner } while (Simplification); 361ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner 362ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner // Try to clean up the testcase by running funcresolve and globaldce... 363ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner if (AnyReduction) { 364ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner std::cout << "\n*** Attempting to perform final cleanups: "; 365ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner Module *M = performFinalCleanups(); 366ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner std::swap(Program, M); 367ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner 368ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner // Find out if the pass still crashes on the cleaned up program... 369aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (runPasses(PassesToRun)) { 370ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner // Yup, it does, keep the reduced version... 371ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner delete M; 372f607b79bc78fcbfd8cda01d2d5dbda6cd8253a40Chris Lattner AnyReduction = true; 373ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner } else { 374ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner delete Program; // Otherwise, restore the original module... 375ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner Program = M; 376ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner } 377ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner } 378ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner 379f607b79bc78fcbfd8cda01d2d5dbda6cd8253a40Chris Lattner if (AnyReduction) 380640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner EmitProgressBytecode("reduced-simplified"); 381ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner 382afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner return false; 383afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner} 384