CrashDebugger.cpp revision 73b96bd52d9361d5c947e4fb660a46e498f7b407
1afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner//===- CrashDebugger.cpp - Debug compilation crashes ----------------------===// 27c0e022c5c4be4b11e199a53f73bbdd84e34aa80John Criswell// 37c0e022c5c4be4b11e199a53f73bbdd84e34aa80John Criswell// The LLVM Compiler Infrastructure 47c0e022c5c4be4b11e199a53f73bbdd84e34aa80John Criswell// 57c0e022c5c4be4b11e199a53f73bbdd84e34aa80John Criswell// This file was developed by the LLVM research group and is distributed under 67c0e022c5c4be4b11e199a53f73bbdd84e34aa80John Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 77c0e022c5c4be4b11e199a53f73bbdd84e34aa80John Criswell// 87c0e022c5c4be4b11e199a53f73bbdd84e34aa80John Criswell//===----------------------------------------------------------------------===// 9afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner// 10afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner// This file defines the bugpoint internals that narrow down compilation crashes 11afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner// 12afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner//===----------------------------------------------------------------------===// 13afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 14afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "BugDriver.h" 15aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner#include "ListReducer.h" 16286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/Constant.h" 17286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/iTerminators.h" 18e49603d79d220a795bd50684c8b1f503ee40f97fMisha Brukman#include "llvm/Module.h" 19e49603d79d220a795bd50684c8b1f503ee40f97fMisha Brukman#include "llvm/Pass.h" 20e49603d79d220a795bd50684c8b1f503ee40f97fMisha Brukman#include "llvm/PassManager.h" 21286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/SymbolTable.h" 22e49603d79d220a795bd50684c8b1f503ee40f97fMisha Brukman#include "llvm/Type.h" 23286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/Analysis/Verifier.h" 24e49603d79d220a795bd50684c8b1f503ee40f97fMisha Brukman#include "llvm/Bytecode/Writer.h" 25e49603d79d220a795bd50684c8b1f503ee40f97fMisha Brukman#include "llvm/Support/CFG.h" 26286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner#include "llvm/Transforms/Scalar.h" 27aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner#include "llvm/Transforms/Utils/Cloning.h" 283d9cafa003a114bf9974bc80d5b69b0ed1d29290Misha Brukman#include "Support/FileUtilities.h" 29afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include <fstream> 30aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner#include <set> 31afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 32640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattnerclass DebugCrashes : public ListReducer<const PassInfo*> { 33640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner BugDriver &BD; 34640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattnerpublic: 35640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner DebugCrashes(BugDriver &bd) : BD(bd) {} 36640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner 37640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner // doTest - Return true iff running the "removed" passes succeeds, and running 38640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner // the "Kept" passes fail when run on the output of the "removed" passes. If 39640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner // we return true, we update the current module of bugpoint. 40640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner // 41aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner virtual TestResult doTest(std::vector<const PassInfo*> &Removed, 42aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::vector<const PassInfo*> &Kept); 43aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner}; 44aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 45aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris LattnerDebugCrashes::TestResult 46aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris LattnerDebugCrashes::doTest(std::vector<const PassInfo*> &Prefix, 47aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::vector<const PassInfo*> &Suffix) { 48aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::string PrefixOutput; 49b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner Module *OrigProgram = 0; 50aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (!Prefix.empty()) { 51aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << "Checking to see if these passes crash: " 52aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner << getPassesString(Prefix) << ": "; 53aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (BD.runPasses(Prefix, PrefixOutput)) 54aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return KeepPrefix; 55b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner 56b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner OrigProgram = BD.Program; 57b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner 58b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner BD.Program = BD.ParseInputFile(PrefixOutput); 59b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner if (BD.Program == 0) { 60b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner std::cerr << BD.getToolName() << ": Error reading bytecode file '" 61b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner << PrefixOutput << "'!\n"; 62b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner exit(1); 63b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner } 64b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner removeFile(PrefixOutput); 65aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner } 66aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 67aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << "Checking to see if these passes crash: " 68aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner << getPassesString(Suffix) << ": "; 69b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner 70aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (BD.runPasses(Suffix)) { 71aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner delete OrigProgram; // The suffix crashes alone... 72aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return KeepSuffix; 73aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner } 74aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 75aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Nothing failed, restore state... 76b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner if (OrigProgram) { 77b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner delete BD.Program; 78b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner BD.Program = OrigProgram; 79b417c795d2a8832b5edac321dc0d19eca7e3f2f5Chris Lattner } 80aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return NoFailure; 81aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner} 82aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 83aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattnerclass ReduceCrashingFunctions : public ListReducer<Function*> { 84aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner BugDriver &BD; 85aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattnerpublic: 86aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner ReduceCrashingFunctions(BugDriver &bd) : BD(bd) {} 87aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 88aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner virtual TestResult doTest(std::vector<Function*> &Prefix, 89aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::vector<Function*> &Kept) { 90a493ae300b01bae69b66d961b5d67be5d64e129aMisha Brukman if (!Kept.empty() && TestFuncs(Kept)) 91aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return KeepSuffix; 92aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (!Prefix.empty() && TestFuncs(Prefix)) 93aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return KeepPrefix; 94aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return NoFailure; 95640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner } 96aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 97aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner bool TestFuncs(std::vector<Function*> &Prefix); 98640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner}; 99aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 100aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattnerbool ReduceCrashingFunctions::TestFuncs(std::vector<Function*> &Funcs) { 101cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Clone the program to try hacking it apart... 102aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner Module *M = CloneModule(BD.Program); 103aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 104aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Convert list to set for fast lookup... 105aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::set<Function*> Functions; 106aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner for (unsigned i = 0, e = Funcs.size(); i != e; ++i) { 107aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner Function *CMF = M->getFunction(Funcs[i]->getName(), 108aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner Funcs[i]->getFunctionType()); 109aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner assert(CMF && "Function not in module?!"); 110f607b79bc78fcbfd8cda01d2d5dbda6cd8253a40Chris Lattner Functions.insert(CMF); 111aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner } 112aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 113aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << "Checking for crash with only these functions:"; 11473b96bd52d9361d5c947e4fb660a46e498f7b407Chris Lattner unsigned NumPrint = Funcs.size(); 11573b96bd52d9361d5c947e4fb660a46e498f7b407Chris Lattner if (NumPrint > 10) NumPrint = 10; 11673b96bd52d9361d5c947e4fb660a46e498f7b407Chris Lattner for (unsigned i = 0; i != NumPrint; ++i) 117aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << " " << Funcs[i]->getName(); 11873b96bd52d9361d5c947e4fb660a46e498f7b407Chris Lattner if (NumPrint < Funcs.size()) 11973b96bd52d9361d5c947e4fb660a46e498f7b407Chris Lattner std::cout << "... <" << Funcs.size() << " total>"; 120aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << ": "; 121aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 122aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Loop over and delete any functions which we aren't supposed to be playing 123aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // with... 124aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 125f607b79bc78fcbfd8cda01d2d5dbda6cd8253a40Chris Lattner if (!I->isExternal() && !Functions.count(I)) 126aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner DeleteFunctionBody(I); 127aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 128aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Try running the hacked up program... 129aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::swap(BD.Program, M); 130aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (BD.runPasses(BD.PassesToRun)) { 131aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner delete M; // It crashed, keep the trimmed version... 132aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 133aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Make sure to use function pointers that point into the now-current 134aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // module. 135aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner Funcs.assign(Functions.begin(), Functions.end()); 136aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return true; 137aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner } 138aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner delete BD.Program; // It didn't crash, revert... 139aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner BD.Program = M; 140aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner return false; 141aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner} 142aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 143640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner 144286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner/// ReduceCrashingBlocks reducer - This works by setting the terminators of all 145286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner/// terminators except the specified basic blocks to a 'ret' instruction, then 146286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner/// running the simplify-cfg pass. This has the effect of chopping up the CFG 147286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner/// really fast which can reduce large functions quickly. 148286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner/// 149286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattnerclass ReduceCrashingBlocks : public ListReducer<BasicBlock*> { 150286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BugDriver &BD; 151286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattnerpublic: 152286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner ReduceCrashingBlocks(BugDriver &bd) : BD(bd) {} 153286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 154286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner virtual TestResult doTest(std::vector<BasicBlock*> &Prefix, 155286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::vector<BasicBlock*> &Kept) { 1565cfff2545d5c731bb236d6e5c355bcb59d7abda7John Criswell if (!Kept.empty() && TestBlocks(Kept)) 157286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner return KeepSuffix; 158286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner if (!Prefix.empty() && TestBlocks(Prefix)) 159286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner return KeepPrefix; 160286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner return NoFailure; 161286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner } 162286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 163286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner bool TestBlocks(std::vector<BasicBlock*> &Prefix); 164286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner}; 165286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 166286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattnerbool ReduceCrashingBlocks::TestBlocks(std::vector<BasicBlock*> &BBs) { 167cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Clone the program to try hacking it apart... 168286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Module *M = CloneModule(BD.Program); 169286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 170286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Convert list to set for fast lookup... 171286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::set<BasicBlock*> Blocks; 172286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (unsigned i = 0, e = BBs.size(); i != e; ++i) { 173286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Convert the basic block from the original module to the new module... 174286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Function *F = BBs[i]->getParent(); 175286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Function *CMF = M->getFunction(F->getName(), F->getFunctionType()); 176286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner assert(CMF && "Function not in module?!"); 177286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 178286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Get the mapped basic block... 179286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Function::iterator CBI = CMF->begin(); 180286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::advance(CBI, std::distance(F->begin(), Function::iterator(BBs[i]))); 181286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Blocks.insert(CBI); 182286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner } 183286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 184286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::cout << "Checking for crash with only these blocks:"; 18573b96bd52d9361d5c947e4fb660a46e498f7b407Chris Lattner unsigned NumPrint = Blocks.size(); 18673b96bd52d9361d5c947e4fb660a46e498f7b407Chris Lattner if (NumPrint > 10) NumPrint = 10; 18773b96bd52d9361d5c947e4fb660a46e498f7b407Chris Lattner for (unsigned i = 0, e = NumPrint; i != e; ++i) 188286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::cout << " " << BBs[i]->getName(); 18973b96bd52d9361d5c947e4fb660a46e498f7b407Chris Lattner if (NumPrint < Blocks.size()) 19073b96bd52d9361d5c947e4fb660a46e498f7b407Chris Lattner std::cout << "... <" << Blocks.size() << " total>"; 191286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::cout << ": "; 192286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 193286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Loop over and delete any hack up any blocks that are not listed... 194286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 195286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB) 196286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner if (!Blocks.count(BB) && !isa<ReturnInst>(BB->getTerminator())) { 197286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Loop over all of the successors of this block, deleting any PHI nodes 198286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // that might include it. 199286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 200286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner (*SI)->removePredecessor(BB); 201286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 202286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Delete the old terminator instruction... 203286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BB->getInstList().pop_back(); 204286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 205286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Add a new return instruction of the appropriate type... 206286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner const Type *RetTy = BB->getParent()->getReturnType(); 207286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner ReturnInst *RI = new ReturnInst(RetTy == Type::VoidTy ? 0 : 208286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Constant::getNullValue(RetTy)); 209286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BB->getInstList().push_back(RI); 210286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner } 211286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 212286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // The CFG Simplifier pass may delete one of the basic blocks we are 213286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // interested in. If it does we need to take the block out of the list. Make 214286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // a "persistent mapping" by turning basic blocks into <function, name> pairs. 215286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // This won't work well if blocks are unnamed, but that is just the risk we 216286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // have to take. 217286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::vector<std::pair<Function*, std::string> > BlockInfo; 218286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 219286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (std::set<BasicBlock*>::iterator I = Blocks.begin(), E = Blocks.end(); 220286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner I != E; ++I) 221286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BlockInfo.push_back(std::make_pair((*I)->getParent(), (*I)->getName())); 222286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 223286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Now run the CFG simplify pass on the function... 224286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner PassManager Passes; 225286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Passes.add(createCFGSimplificationPass()); 226286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Passes.add(createVerifierPass()); 227286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner Passes.run(*M); 228286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 229286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Try running on the hacked up program... 230286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner std::swap(BD.Program, M); 231286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner if (BD.runPasses(BD.PassesToRun)) { 232286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner delete M; // It crashed, keep the trimmed version... 233286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 234286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Make sure to use basic block pointers that point into the now-current 235286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // module, and that they don't include any deleted blocks. 236286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BBs.clear(); 237286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { 238286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner SymbolTable &ST = BlockInfo[i].first->getSymbolTable(); 239286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner SymbolTable::iterator I = ST.find(Type::LabelTy); 240286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner if (I != ST.end() && I->second.count(BlockInfo[i].second)) 241286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BBs.push_back(cast<BasicBlock>(I->second[BlockInfo[i].second])); 242286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner } 243286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner return true; 244286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner } 245286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner delete BD.Program; // It didn't crash, revert... 246286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner BD.Program = M; 247286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner return false; 248286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner} 249286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner 250afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// debugCrash - This method is called when some pass crashes on input. It 251afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// attempts to prune down the testcase to something reasonable, and figure 252afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// out exactly which pass is crashing. 253afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// 254afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattnerbool BugDriver::debugCrash() { 255aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner bool AnyReduction = false; 256afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner std::cout << "\n*** Debugging optimizer crash!\n"; 257afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 258640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner // Reduce the list of passes which causes the optimizer to crash... 259aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner unsigned OldSize = PassesToRun.size(); 260640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner DebugCrashes(*this).reduceList(PassesToRun); 261afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 262aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << "\n*** Found crashing pass" 263aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner << (PassesToRun.size() == 1 ? ": " : "es: ") 264aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner << getPassesString(PassesToRun) << "\n"; 265640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner 266aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner EmitProgressBytecode("passinput"); 2675f73e38548c57636ad0ef8c719d040e166761962Chris Lattner 2685f73e38548c57636ad0ef8c719d040e166761962Chris Lattner // See if we can get away with nuking all of the global variable initializers 2695f73e38548c57636ad0ef8c719d040e166761962Chris Lattner // in the program... 2705f73e38548c57636ad0ef8c719d040e166761962Chris Lattner if (Program->gbegin() != Program->gend()) { 2715f73e38548c57636ad0ef8c719d040e166761962Chris Lattner Module *M = CloneModule(Program); 2725f73e38548c57636ad0ef8c719d040e166761962Chris Lattner bool DeletedInit = false; 2735f73e38548c57636ad0ef8c719d040e166761962Chris Lattner for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I) 2745f73e38548c57636ad0ef8c719d040e166761962Chris Lattner if (I->hasInitializer()) { 2755f73e38548c57636ad0ef8c719d040e166761962Chris Lattner I->setInitializer(0); 2765f73e38548c57636ad0ef8c719d040e166761962Chris Lattner I->setLinkage(GlobalValue::ExternalLinkage); 2775f73e38548c57636ad0ef8c719d040e166761962Chris Lattner DeletedInit = true; 2785f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } 2795f73e38548c57636ad0ef8c719d040e166761962Chris Lattner 2805f73e38548c57636ad0ef8c719d040e166761962Chris Lattner if (!DeletedInit) { 2815f73e38548c57636ad0ef8c719d040e166761962Chris Lattner delete M; // No change made... 2825f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } else { 2835f73e38548c57636ad0ef8c719d040e166761962Chris Lattner // See if the program still causes a crash... 2845f73e38548c57636ad0ef8c719d040e166761962Chris Lattner std::cout << "\nChecking to see if we can delete global inits: "; 2855f73e38548c57636ad0ef8c719d040e166761962Chris Lattner std::swap(Program, M); 2865f73e38548c57636ad0ef8c719d040e166761962Chris Lattner if (runPasses(PassesToRun)) { // Still crashes? 2875f73e38548c57636ad0ef8c719d040e166761962Chris Lattner AnyReduction = true; 2885f73e38548c57636ad0ef8c719d040e166761962Chris Lattner delete M; 2895f73e38548c57636ad0ef8c719d040e166761962Chris Lattner std::cout << "\n*** Able to remove all global initializers!\n"; 2905f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } else { // No longer crashes? 2915f73e38548c57636ad0ef8c719d040e166761962Chris Lattner delete Program; // Restore program. 2925f73e38548c57636ad0ef8c719d040e166761962Chris Lattner Program = M; 2935f73e38548c57636ad0ef8c719d040e166761962Chris Lattner std::cout << " - Removing all global inits hides problem!\n"; 2945f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } 2955f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } 2965f73e38548c57636ad0ef8c719d040e166761962Chris Lattner } 297aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner 298aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // Now try to reduce the number of functions in the module to something small. 299aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::vector<Function*> Functions; 300aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) 301afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner if (!I->isExternal()) 302aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner Functions.push_back(I); 303afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 304aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (Functions.size() > 1) { 305aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner std::cout << "\n*** Attempting to reduce the number of functions " 306aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner "in the testcase\n"; 307afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 308aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner OldSize = Functions.size(); 309aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner ReduceCrashingFunctions(*this).reduceList(Functions); 310afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 311aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (Functions.size() < OldSize) { 312aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner EmitProgressBytecode("reduced-function"); 313aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner AnyReduction = true; 3146520785dcd22012535934098942d57c07c7631c2Chris Lattner } 315218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner } 316218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner 317286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // Attempt to delete entire basic blocks at a time to speed up 318286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // convergence... this actually works by setting the terminator of the blocks 319286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // to a return instruction then running simplifycfg, which can potentially 320286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // shrinks the code dramatically quickly 321286921e8d21d4f0655905ed278d0e140829c7d1fChris Lattner // 32247ae4a1cee5eec5767a11403c0fac7c91ec45461Chris Lattner if (!DisableSimplifyCFG) { 32347ae4a1cee5eec5767a11403c0fac7c91ec45461Chris Lattner std::vector<BasicBlock*> Blocks; 32447ae4a1cee5eec5767a11403c0fac7c91ec45461Chris Lattner for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) 32547ae4a1cee5eec5767a11403c0fac7c91ec45461Chris Lattner for (Function::iterator FI = I->begin(), E = I->end(); FI != E; ++FI) 32647ae4a1cee5eec5767a11403c0fac7c91ec45461Chris Lattner Blocks.push_back(FI); 32747ae4a1cee5eec5767a11403c0fac7c91ec45461Chris Lattner ReduceCrashingBlocks(*this).reduceList(Blocks); 32847ae4a1cee5eec5767a11403c0fac7c91ec45461Chris Lattner } 3296520785dcd22012535934098942d57c07c7631c2Chris Lattner 330aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // FIXME: This should use the list reducer to converge faster by deleting 331aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner // larger chunks of instructions at a time! 3326520785dcd22012535934098942d57c07c7631c2Chris Lattner unsigned Simplification = 4; 3336520785dcd22012535934098942d57c07c7631c2Chris Lattner do { 3346520785dcd22012535934098942d57c07c7631c2Chris Lattner --Simplification; 3356520785dcd22012535934098942d57c07c7631c2Chris Lattner std::cout << "\n*** Attempting to reduce testcase by deleting instruc" 3366520785dcd22012535934098942d57c07c7631c2Chris Lattner << "tions: Simplification Level #" << Simplification << "\n"; 3376520785dcd22012535934098942d57c07c7631c2Chris Lattner 3385560c9d49ccae132cabf1155f18aa0480dce3edaMisha Brukman // Now that we have deleted the functions that are unnecessary for the 3395560c9d49ccae132cabf1155f18aa0480dce3edaMisha Brukman // program, try to remove instructions that are not necessary to cause the 3406520785dcd22012535934098942d57c07c7631c2Chris Lattner // crash. To do this, we loop through all of the instructions in the 3416520785dcd22012535934098942d57c07c7631c2Chris Lattner // remaining functions, deleting them (replacing any values produced with 3426520785dcd22012535934098942d57c07c7631c2Chris Lattner // nulls), and then running ADCE and SimplifyCFG. If the transformed input 3436520785dcd22012535934098942d57c07c7631c2Chris Lattner // still triggers failure, keep deleting until we cannot trigger failure 3446520785dcd22012535934098942d57c07c7631c2Chris Lattner // anymore. 3456520785dcd22012535934098942d57c07c7631c2Chris Lattner // 3466520785dcd22012535934098942d57c07c7631c2Chris Lattner TryAgain: 3476520785dcd22012535934098942d57c07c7631c2Chris Lattner 3486520785dcd22012535934098942d57c07c7631c2Chris Lattner // Loop over all of the (non-terminator) instructions remaining in the 3496520785dcd22012535934098942d57c07c7631c2Chris Lattner // function, attempting to delete them. 3506520785dcd22012535934098942d57c07c7631c2Chris Lattner for (Module::iterator FI = Program->begin(), E = Program->end(); 3516520785dcd22012535934098942d57c07c7631c2Chris Lattner FI != E; ++FI) 3526520785dcd22012535934098942d57c07c7631c2Chris Lattner if (!FI->isExternal()) { 3536520785dcd22012535934098942d57c07c7631c2Chris Lattner for (Function::iterator BI = FI->begin(), E = FI->end(); BI != E; ++BI) 3546520785dcd22012535934098942d57c07c7631c2Chris Lattner for (BasicBlock::iterator I = BI->begin(), E = --BI->end(); 3556520785dcd22012535934098942d57c07c7631c2Chris Lattner I != E; ++I) { 3566520785dcd22012535934098942d57c07c7631c2Chris Lattner Module *M = deleteInstructionFromProgram(I, Simplification); 3576520785dcd22012535934098942d57c07c7631c2Chris Lattner 3586520785dcd22012535934098942d57c07c7631c2Chris Lattner // Make the function the current program... 3596520785dcd22012535934098942d57c07c7631c2Chris Lattner std::swap(Program, M); 3606520785dcd22012535934098942d57c07c7631c2Chris Lattner 3616520785dcd22012535934098942d57c07c7631c2Chris Lattner // Find out if the pass still crashes on this pass... 3626520785dcd22012535934098942d57c07c7631c2Chris Lattner std::cout << "Checking instruction '" << I->getName() << "': "; 363aae33f9137e4a64394d8f9fe66611ae53a0ef4e8Chris Lattner if (runPasses(PassesToRun)) { 3646520785dcd22012535934098942d57c07c7631c2Chris Lattner // Yup, it does, we delete the old module, and continue trying to 3656520785dcd22012535934098942d57c07c7631c2Chris Lattner // reduce the testcase... 3666520785dcd22012535934098942d57c07c7631c2Chris Lattner delete M; 367f607b79bc78fcbfd8cda01d2d5dbda6cd8253a40Chris Lattner AnyReduction = true; 3686520785dcd22012535934098942d57c07c7631c2Chris Lattner goto TryAgain; // I wish I had a multi-level break here! 3696520785dcd22012535934098942d57c07c7631c2Chris Lattner } 3706520785dcd22012535934098942d57c07c7631c2Chris Lattner 3716520785dcd22012535934098942d57c07c7631c2Chris Lattner // This pass didn't crash without this instruction, try the next 3726520785dcd22012535934098942d57c07c7631c2Chris Lattner // one. 3736520785dcd22012535934098942d57c07c7631c2Chris Lattner delete Program; 3746520785dcd22012535934098942d57c07c7631c2Chris Lattner Program = M; 3756520785dcd22012535934098942d57c07c7631c2Chris Lattner } 3766520785dcd22012535934098942d57c07c7631c2Chris Lattner } 3776520785dcd22012535934098942d57c07c7631c2Chris Lattner } while (Simplification); 378ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner 379ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner // Try to clean up the testcase by running funcresolve and globaldce... 380898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner std::cout << "\n*** Attempting to perform final cleanups: "; 381898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner Module *M = performFinalCleanups(); 382898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner std::swap(Program, M); 383ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner 384898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner // Find out if the pass still crashes on the cleaned up program... 385898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner if (runPasses(PassesToRun)) { 386898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner // Yup, it does, keep the reduced version... 387898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner delete M; 388898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner AnyReduction = true; 389898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner } else { 390898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner delete Program; // Otherwise, restore the original module... 391898e0e42e3c09e9f2098bf9a83720b5a33b52fc7Chris Lattner Program = M; 392ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner } 393ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner 394f607b79bc78fcbfd8cda01d2d5dbda6cd8253a40Chris Lattner if (AnyReduction) 395640f22e66d90439857a97a83896ee68c4f7128c9Chris Lattner EmitProgressBytecode("reduced-simplified"); 396ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner 397afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner return false; 398afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner} 399