tools/bugpoint/CrashDebugger.cpp

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