tools/bugpoint/CrashDebugger.cpp

   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
  25 class DebugCrashes : public ListReducer<const PassInfo*> {
  26   BugDriver &BD;
  27 public:
  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
  38 DebugCrashes::TestResult
  39 DebugCrashes::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
  76 class ReduceCrashingFunctions : public ListReducer<Function*> {
  77   BugDriver &BD;
  78 public:
  79   ReduceCrashingFunctions(BugDriver &bd) : BD(bd) {}
  80
  81   virtual TestResult doTest(std::vector<Function*> &Prefix,
  82                             std::vector<Function*> &Kept) {
  83     if (!Kept.empty() && 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
  93 bool 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 ///
 138 class ReduceCrashingBlocks : public ListReducer<BasicBlock*> {
 139   BugDriver &BD;
 140 public:
 141   ReduceCrashingBlocks(BugDriver &bd) : BD(bd) {}
 142
 143   virtual TestResult doTest(std::vector<BasicBlock*> &Prefix,
 144                             std::vector<BasicBlock*> &Kept) {
 145     if (!Kept.empty() && 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
 155 bool 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 ///
 239 bool 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 }