CrashDebugger.cpp revision 898e0e42e3c09e9f2098bf9a83720b5a33b52fc7
1//===- CrashDebugger.cpp - Debug compilation crashes ----------------------===// 2// 3// This file defines the bugpoint internals that narrow down compilation crashes 4// 5//===----------------------------------------------------------------------===// 6 7#include "BugDriver.h" 8#include "SystemUtils.h" 9#include "ListReducer.h" 10#include "llvm/Module.h" 11#include "llvm/PassManager.h" 12#include "llvm/Pass.h" 13#include "llvm/Constant.h" 14#include "llvm/iTerminators.h" 15#include "llvm/Type.h" 16#include "llvm/SymbolTable.h" 17#include "llvm/Support/CFG.h" 18#include "llvm/Analysis/Verifier.h" 19#include "llvm/Transforms/Scalar.h" 20#include "llvm/Transforms/Utils/Cloning.h" 21#include "llvm/Bytecode/Writer.h" 22#include <fstream> 23#include <set> 24 25class DebugCrashes : public ListReducer<const PassInfo*> { 26 BugDriver &BD; 27public: 28 DebugCrashes(BugDriver &bd) : BD(bd) {} 29 30 // doTest - Return true iff running the "removed" passes succeeds, and running 31 // the "Kept" passes fail when run on the output of the "removed" passes. If 32 // we return true, we update the current module of bugpoint. 33 // 34 virtual TestResult doTest(std::vector<const PassInfo*> &Removed, 35 std::vector<const PassInfo*> &Kept); 36}; 37 38DebugCrashes::TestResult 39DebugCrashes::doTest(std::vector<const PassInfo*> &Prefix, 40 std::vector<const PassInfo*> &Suffix) { 41 std::string PrefixOutput; 42 Module *OrigProgram = 0; 43 if (!Prefix.empty()) { 44 std::cout << "Checking to see if these passes crash: " 45 << getPassesString(Prefix) << ": "; 46 if (BD.runPasses(Prefix, PrefixOutput)) 47 return KeepPrefix; 48 49 OrigProgram = BD.Program; 50 51 BD.Program = BD.ParseInputFile(PrefixOutput); 52 if (BD.Program == 0) { 53 std::cerr << BD.getToolName() << ": Error reading bytecode file '" 54 << PrefixOutput << "'!\n"; 55 exit(1); 56 } 57 removeFile(PrefixOutput); 58 } 59 60 std::cout << "Checking to see if these passes crash: " 61 << getPassesString(Suffix) << ": "; 62 63 if (BD.runPasses(Suffix)) { 64 delete OrigProgram; // The suffix crashes alone... 65 return KeepSuffix; 66 } 67 68 // Nothing failed, restore state... 69 if (OrigProgram) { 70 delete BD.Program; 71 BD.Program = OrigProgram; 72 } 73 return NoFailure; 74} 75 76class ReduceCrashingFunctions : public ListReducer<Function*> { 77 BugDriver &BD; 78public: 79 ReduceCrashingFunctions(BugDriver &bd) : BD(bd) {} 80 81 virtual TestResult doTest(std::vector<Function*> &Prefix, 82 std::vector<Function*> &Kept) { 83 if (TestFuncs(Kept)) 84 return KeepSuffix; 85 if (!Prefix.empty() && TestFuncs(Prefix)) 86 return KeepPrefix; 87 return NoFailure; 88 } 89 90 bool TestFuncs(std::vector<Function*> &Prefix); 91}; 92 93bool ReduceCrashingFunctions::TestFuncs(std::vector<Function*> &Funcs) { 94 // Clone the program to try hacking it appart... 95 Module *M = CloneModule(BD.Program); 96 97 // Convert list to set for fast lookup... 98 std::set<Function*> Functions; 99 for (unsigned i = 0, e = Funcs.size(); i != e; ++i) { 100 Function *CMF = M->getFunction(Funcs[i]->getName(), 101 Funcs[i]->getFunctionType()); 102 assert(CMF && "Function not in module?!"); 103 Functions.insert(CMF); 104 } 105 106 std::cout << "Checking for crash with only these functions:"; 107 for (unsigned i = 0, e = Funcs.size(); i != e; ++i) 108 std::cout << " " << Funcs[i]->getName(); 109 std::cout << ": "; 110 111 // Loop over and delete any functions which we aren't supposed to be playing 112 // with... 113 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 114 if (!I->isExternal() && !Functions.count(I)) 115 DeleteFunctionBody(I); 116 117 // Try running the hacked up program... 118 std::swap(BD.Program, M); 119 if (BD.runPasses(BD.PassesToRun)) { 120 delete M; // It crashed, keep the trimmed version... 121 122 // Make sure to use function pointers that point into the now-current 123 // module. 124 Funcs.assign(Functions.begin(), Functions.end()); 125 return true; 126 } 127 delete BD.Program; // It didn't crash, revert... 128 BD.Program = M; 129 return false; 130} 131 132 133/// ReduceCrashingBlocks reducer - This works by setting the terminators of all 134/// terminators except the specified basic blocks to a 'ret' instruction, then 135/// running the simplify-cfg pass. This has the effect of chopping up the CFG 136/// really fast which can reduce large functions quickly. 137/// 138class ReduceCrashingBlocks : public ListReducer<BasicBlock*> { 139 BugDriver &BD; 140public: 141 ReduceCrashingBlocks(BugDriver &bd) : BD(bd) {} 142 143 virtual TestResult doTest(std::vector<BasicBlock*> &Prefix, 144 std::vector<BasicBlock*> &Kept) { 145 if (TestBlocks(Kept)) 146 return KeepSuffix; 147 if (!Prefix.empty() && TestBlocks(Prefix)) 148 return KeepPrefix; 149 return NoFailure; 150 } 151 152 bool TestBlocks(std::vector<BasicBlock*> &Prefix); 153}; 154 155bool ReduceCrashingBlocks::TestBlocks(std::vector<BasicBlock*> &BBs) { 156 // Clone the program to try hacking it appart... 157 Module *M = CloneModule(BD.Program); 158 159 // Convert list to set for fast lookup... 160 std::set<BasicBlock*> Blocks; 161 for (unsigned i = 0, e = BBs.size(); i != e; ++i) { 162 // Convert the basic block from the original module to the new module... 163 Function *F = BBs[i]->getParent(); 164 Function *CMF = M->getFunction(F->getName(), F->getFunctionType()); 165 assert(CMF && "Function not in module?!"); 166 167 // Get the mapped basic block... 168 Function::iterator CBI = CMF->begin(); 169 std::advance(CBI, std::distance(F->begin(), Function::iterator(BBs[i]))); 170 Blocks.insert(CBI); 171 } 172 173 std::cout << "Checking for crash with only these blocks:"; 174 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) 175 std::cout << " " << BBs[i]->getName(); 176 std::cout << ": "; 177 178 // Loop over and delete any hack up any blocks that are not listed... 179 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 180 for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB) 181 if (!Blocks.count(BB) && !isa<ReturnInst>(BB->getTerminator())) { 182 // Loop over all of the successors of this block, deleting any PHI nodes 183 // that might include it. 184 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 185 (*SI)->removePredecessor(BB); 186 187 // Delete the old terminator instruction... 188 BB->getInstList().pop_back(); 189 190 // Add a new return instruction of the appropriate type... 191 const Type *RetTy = BB->getParent()->getReturnType(); 192 ReturnInst *RI = new ReturnInst(RetTy == Type::VoidTy ? 0 : 193 Constant::getNullValue(RetTy)); 194 BB->getInstList().push_back(RI); 195 } 196 197 // The CFG Simplifier pass may delete one of the basic blocks we are 198 // interested in. If it does we need to take the block out of the list. Make 199 // a "persistent mapping" by turning basic blocks into <function, name> pairs. 200 // This won't work well if blocks are unnamed, but that is just the risk we 201 // have to take. 202 std::vector<std::pair<Function*, std::string> > BlockInfo; 203 204 for (std::set<BasicBlock*>::iterator I = Blocks.begin(), E = Blocks.end(); 205 I != E; ++I) 206 BlockInfo.push_back(std::make_pair((*I)->getParent(), (*I)->getName())); 207 208 // Now run the CFG simplify pass on the function... 209 PassManager Passes; 210 Passes.add(createCFGSimplificationPass()); 211 Passes.add(createVerifierPass()); 212 Passes.run(*M); 213 214 // Try running on the hacked up program... 215 std::swap(BD.Program, M); 216 if (BD.runPasses(BD.PassesToRun)) { 217 delete M; // It crashed, keep the trimmed version... 218 219 // Make sure to use basic block pointers that point into the now-current 220 // module, and that they don't include any deleted blocks. 221 BBs.clear(); 222 for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { 223 SymbolTable &ST = BlockInfo[i].first->getSymbolTable(); 224 SymbolTable::iterator I = ST.find(Type::LabelTy); 225 if (I != ST.end() && I->second.count(BlockInfo[i].second)) 226 BBs.push_back(cast<BasicBlock>(I->second[BlockInfo[i].second])); 227 } 228 return true; 229 } 230 delete BD.Program; // It didn't crash, revert... 231 BD.Program = M; 232 return false; 233} 234 235/// debugCrash - This method is called when some pass crashes on input. It 236/// attempts to prune down the testcase to something reasonable, and figure 237/// out exactly which pass is crashing. 238/// 239bool BugDriver::debugCrash() { 240 bool AnyReduction = false; 241 std::cout << "\n*** Debugging optimizer crash!\n"; 242 243 // Reduce the list of passes which causes the optimizer to crash... 244 unsigned OldSize = PassesToRun.size(); 245 DebugCrashes(*this).reduceList(PassesToRun); 246 247 std::cout << "\n*** Found crashing pass" 248 << (PassesToRun.size() == 1 ? ": " : "es: ") 249 << getPassesString(PassesToRun) << "\n"; 250 251 EmitProgressBytecode("passinput"); 252 253 // See if we can get away with nuking all of the global variable initializers 254 // in the program... 255 if (Program->gbegin() != Program->gend()) { 256 Module *M = CloneModule(Program); 257 bool DeletedInit = false; 258 for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I) 259 if (I->hasInitializer()) { 260 I->setInitializer(0); 261 I->setLinkage(GlobalValue::ExternalLinkage); 262 DeletedInit = true; 263 } 264 265 if (!DeletedInit) { 266 delete M; // No change made... 267 } else { 268 // See if the program still causes a crash... 269 std::cout << "\nChecking to see if we can delete global inits: "; 270 std::swap(Program, M); 271 if (runPasses(PassesToRun)) { // Still crashes? 272 AnyReduction = true; 273 delete M; 274 std::cout << "\n*** Able to remove all global initializers!\n"; 275 } else { // No longer crashes? 276 delete Program; // Restore program. 277 Program = M; 278 std::cout << " - Removing all global inits hides problem!\n"; 279 } 280 } 281 } 282 283 // Now try to reduce the number of functions in the module to something small. 284 std::vector<Function*> Functions; 285 for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) 286 if (!I->isExternal()) 287 Functions.push_back(I); 288 289 if (Functions.size() > 1) { 290 std::cout << "\n*** Attempting to reduce the number of functions " 291 "in the testcase\n"; 292 293 OldSize = Functions.size(); 294 ReduceCrashingFunctions(*this).reduceList(Functions); 295 296 if (Functions.size() < OldSize) { 297 EmitProgressBytecode("reduced-function"); 298 AnyReduction = true; 299 } 300 } 301 302 // Attempt to delete entire basic blocks at a time to speed up 303 // convergence... this actually works by setting the terminator of the blocks 304 // to a return instruction then running simplifycfg, which can potentially 305 // shrinks the code dramatically quickly 306 // 307 std::vector<BasicBlock*> Blocks; 308 for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) 309 for (Function::iterator FI = I->begin(), E = I->end(); FI != E; ++FI) 310 Blocks.push_back(FI); 311 ReduceCrashingBlocks(*this).reduceList(Blocks); 312 313 // FIXME: This should use the list reducer to converge faster by deleting 314 // larger chunks of instructions at a time! 315 unsigned Simplification = 4; 316 do { 317 --Simplification; 318 std::cout << "\n*** Attempting to reduce testcase by deleting instruc" 319 << "tions: Simplification Level #" << Simplification << "\n"; 320 321 // Now that we have deleted the functions that are unneccesary for the 322 // program, try to remove instructions that are not neccesary to cause the 323 // crash. To do this, we loop through all of the instructions in the 324 // remaining functions, deleting them (replacing any values produced with 325 // nulls), and then running ADCE and SimplifyCFG. If the transformed input 326 // still triggers failure, keep deleting until we cannot trigger failure 327 // anymore. 328 // 329 TryAgain: 330 331 // Loop over all of the (non-terminator) instructions remaining in the 332 // function, attempting to delete them. 333 for (Module::iterator FI = Program->begin(), E = Program->end(); 334 FI != E; ++FI) 335 if (!FI->isExternal()) { 336 for (Function::iterator BI = FI->begin(), E = FI->end(); BI != E; ++BI) 337 for (BasicBlock::iterator I = BI->begin(), E = --BI->end(); 338 I != E; ++I) { 339 Module *M = deleteInstructionFromProgram(I, Simplification); 340 341 // Make the function the current program... 342 std::swap(Program, M); 343 344 // Find out if the pass still crashes on this pass... 345 std::cout << "Checking instruction '" << I->getName() << "': "; 346 if (runPasses(PassesToRun)) { 347 // Yup, it does, we delete the old module, and continue trying to 348 // reduce the testcase... 349 delete M; 350 AnyReduction = true; 351 goto TryAgain; // I wish I had a multi-level break here! 352 } 353 354 // This pass didn't crash without this instruction, try the next 355 // one. 356 delete Program; 357 Program = M; 358 } 359 } 360 } while (Simplification); 361 362 // Try to clean up the testcase by running funcresolve and globaldce... 363 std::cout << "\n*** Attempting to perform final cleanups: "; 364 Module *M = performFinalCleanups(); 365 std::swap(Program, M); 366 367 // Find out if the pass still crashes on the cleaned up program... 368 if (runPasses(PassesToRun)) { 369 // Yup, it does, keep the reduced version... 370 delete M; 371 AnyReduction = true; 372 } else { 373 delete Program; // Otherwise, restore the original module... 374 Program = M; 375 } 376 377 if (AnyReduction) 378 EmitProgressBytecode("reduced-simplified"); 379 380 return false; 381} 382