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   unsigned NumPrint = Funcs.size();
 115   if (NumPrint > 10) NumPrint = 10;
 116   for (unsigned i = 0; i != NumPrint; ++i)
 117     std::cout << " " << Funcs[i]->getName();
 118   if (NumPrint < Funcs.size())
 119     std::cout << "... <" << Funcs.size() << " total>";
 120   std::cout << ": ";
 121
 122   // Loop over and delete any functions which we aren't supposed to be playing
 123   // with...
 124   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
 125     if (!I->isExternal() && !Functions.count(I))
 126       DeleteFunctionBody(I);
 127
 128   // Try running the hacked up program...
 129   std::swap(BD.Program, M);
 130   if (BD.runPasses(BD.PassesToRun)) {
 131     delete M;         // It crashed, keep the trimmed version...
 132
 133     // Make sure to use function pointers that point into the now-current
 134     // module.
 135     Funcs.assign(Functions.begin(), Functions.end());
 136     return true;
 137   }
 138   delete BD.Program;  // It didn't crash, revert...
 139   BD.Program = M;
 140   return false;
 141 }
 142
 143
 144 /// ReduceCrashingBlocks reducer - This works by setting the terminators of all
 145 /// terminators except the specified basic blocks to a 'ret' instruction, then
 146 /// running the simplify-cfg pass.  This has the effect of chopping up the CFG
 147 /// really fast which can reduce large functions quickly.
 148 ///
 149 class ReduceCrashingBlocks : public ListReducer<BasicBlock*> {
 150   BugDriver &BD;
 151 public:
 152   ReduceCrashingBlocks(BugDriver &bd) : BD(bd) {}
 153
 154   virtual TestResult doTest(std::vector<BasicBlock*> &Prefix,
 155                             std::vector<BasicBlock*> &Kept) {
 156     if (!Kept.empty() && TestBlocks(Kept))
 157       return KeepSuffix;
 158     if (!Prefix.empty() && TestBlocks(Prefix))
 159       return KeepPrefix;
 160     return NoFailure;
 161   }
 162
 163   bool TestBlocks(std::vector<BasicBlock*> &Prefix);
 164 };
 165
 166 bool ReduceCrashingBlocks::TestBlocks(std::vector<BasicBlock*> &BBs) {
 167   // Clone the program to try hacking it apart...
 168   Module *M = CloneModule(BD.Program);
 169
 170   // Convert list to set for fast lookup...
 171   std::set<BasicBlock*> Blocks;
 172   for (unsigned i = 0, e = BBs.size(); i != e; ++i) {
 173     // Convert the basic block from the original module to the new module...
 174     Function *F = BBs[i]->getParent();
 175     Function *CMF = M->getFunction(F->getName(), F->getFunctionType());
 176     assert(CMF && "Function not in module?!");
 177
 178     // Get the mapped basic block...
 179     Function::iterator CBI = CMF->begin();
 180     std::advance(CBI, std::distance(F->begin(), Function::iterator(BBs[i])));
 181     Blocks.insert(CBI);
 182   }
 183
 184   std::cout << "Checking for crash with only these blocks:";
 185   unsigned NumPrint = Blocks.size();
 186   if (NumPrint > 10) NumPrint = 10;
 187   for (unsigned i = 0, e = NumPrint; i != e; ++i)
 188     std::cout << " " << BBs[i]->getName();
 189   if (NumPrint < Blocks.size())
 190     std::cout << "... <" << Blocks.size() << " total>";
 191   std::cout << ": ";
 192
 193   // Loop over and delete any hack up any blocks that are not listed...
 194   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
 195     for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB)
 196       if (!Blocks.count(BB) && !isa<ReturnInst>(BB->getTerminator())) {
 197         // Loop over all of the successors of this block, deleting any PHI nodes
 198         // that might include it.
 199         for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
 200           (*SI)->removePredecessor(BB);
 201
 202         // Delete the old terminator instruction...
 203         BB->getInstList().pop_back();
 204
 205         // Add a new return instruction of the appropriate type...
 206         const Type *RetTy = BB->getParent()->getReturnType();
 207         ReturnInst *RI = new ReturnInst(RetTy == Type::VoidTy ? 0 :
 208                                         Constant::getNullValue(RetTy));
 209         BB->getInstList().push_back(RI);
 210       }
 211
 212   // The CFG Simplifier pass may delete one of the basic blocks we are
 213   // interested in.  If it does we need to take the block out of the list.  Make
 214   // a "persistent mapping" by turning basic blocks into <function, name> pairs.
 215   // This won't work well if blocks are unnamed, but that is just the risk we
 216   // have to take.
 217   std::vector<std::pair<Function*, std::string> > BlockInfo;
 218
 219   for (std::set<BasicBlock*>::iterator I = Blocks.begin(), E = Blocks.end();
 220        I != E; ++I)
 221     BlockInfo.push_back(std::make_pair((*I)->getParent(), (*I)->getName()));
 222
 223   // Now run the CFG simplify pass on the function...
 224   PassManager Passes;
 225   Passes.add(createCFGSimplificationPass());
 226   Passes.add(createVerifierPass());
 227   Passes.run(*M);
 228
 229   // Try running on the hacked up program...
 230   std::swap(BD.Program, M);
 231   if (BD.runPasses(BD.PassesToRun)) {
 232     delete M;         // It crashed, keep the trimmed version...
 233
 234     // Make sure to use basic block pointers that point into the now-current
 235     // module, and that they don't include any deleted blocks.
 236     BBs.clear();
 237     for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {
 238       SymbolTable &ST = BlockInfo[i].first->getSymbolTable();
 239       SymbolTable::iterator I = ST.find(Type::LabelTy);
 240       if (I != ST.end() && I->second.count(BlockInfo[i].second))
 241         BBs.push_back(cast<BasicBlock>(I->second[BlockInfo[i].second]));
 242     }
 243     return true;
 244   }
 245   delete BD.Program;  // It didn't crash, revert...
 246   BD.Program = M;
 247   return false;
 248 }
 249
 250 /// debugCrash - This method is called when some pass crashes on input.  It
 251 /// attempts to prune down the testcase to something reasonable, and figure
 252 /// out exactly which pass is crashing.
 253 ///
 254 bool BugDriver::debugCrash() {
 255   bool AnyReduction = false;
 256   std::cout << "\n*** Debugging optimizer crash!\n";
 257
 258   // Reduce the list of passes which causes the optimizer to crash...
 259   unsigned OldSize = PassesToRun.size();
 260   DebugCrashes(*this).reduceList(PassesToRun);
 261
 262   std::cout << "\n*** Found crashing pass"
 263             << (PassesToRun.size() == 1 ? ": " : "es: ")
 264             << getPassesString(PassesToRun) << "\n";
 265
 266   EmitProgressBytecode("passinput");
 267
 268   // See if we can get away with nuking all of the global variable initializers
 269   // in the program...
 270   if (Program->gbegin() != Program->gend()) {
 271     Module *M = CloneModule(Program);
 272     bool DeletedInit = false;
 273     for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I)
 274       if (I->hasInitializer()) {
 275         I->setInitializer(0);
 276         I->setLinkage(GlobalValue::ExternalLinkage);
 277         DeletedInit = true;
 278       }
 279
 280     if (!DeletedInit) {
 281       delete M;  // No change made...
 282     } else {
 283       // See if the program still causes a crash...
 284       std::cout << "\nChecking to see if we can delete global inits: ";
 285       std::swap(Program, M);
 286       if (runPasses(PassesToRun)) {  // Still crashes?
 287         AnyReduction = true;
 288         delete M;
 289         std::cout << "\n*** Able to remove all global initializers!\n";
 290       } else {                       // No longer crashes?
 291         delete Program;              // Restore program.
 292         Program = M;
 293         std::cout << "  - Removing all global inits hides problem!\n";
 294       }
 295     }
 296   }
 297
 298   // Now try to reduce the number of functions in the module to something small.
 299   std::vector<Function*> Functions;
 300   for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
 301     if (!I->isExternal())
 302       Functions.push_back(I);
 303
 304   if (Functions.size() > 1) {
 305     std::cout << "\n*** Attempting to reduce the number of functions "
 306       "in the testcase\n";
 307
 308     OldSize = Functions.size();
 309     ReduceCrashingFunctions(*this).reduceList(Functions);
 310
 311     if (Functions.size() < OldSize) {
 312       EmitProgressBytecode("reduced-function");
 313       AnyReduction = true;
 314     }
 315   }
 316
 317   // Attempt to delete entire basic blocks at a time to speed up
 318   // convergence... this actually works by setting the terminator of the blocks
 319   // to a return instruction then running simplifycfg, which can potentially
 320   // shrinks the code dramatically quickly
 321   //
 322   if (!DisableSimplifyCFG) {
 323     std::vector<BasicBlock*> Blocks;
 324     for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
 325       for (Function::iterator FI = I->begin(), E = I->end(); FI != E; ++FI)
 326         Blocks.push_back(FI);
 327     ReduceCrashingBlocks(*this).reduceList(Blocks);
 328   }
 329
 330   // FIXME: This should use the list reducer to converge faster by deleting
 331   // larger chunks of instructions at a time!
 332   unsigned Simplification = 4;
 333   do {
 334     --Simplification;
 335     std::cout << "\n*** Attempting to reduce testcase by deleting instruc"
 336               << "tions: Simplification Level #" << Simplification << "\n";
 337
 338     // Now that we have deleted the functions that are unnecessary for the
 339     // program, try to remove instructions that are not necessary to cause the
 340     // crash.  To do this, we loop through all of the instructions in the
 341     // remaining functions, deleting them (replacing any values produced with
 342     // nulls), and then running ADCE and SimplifyCFG.  If the transformed input
 343     // still triggers failure, keep deleting until we cannot trigger failure
 344     // anymore.
 345     //
 346   TryAgain:
 347
 348     // Loop over all of the (non-terminator) instructions remaining in the
 349     // function, attempting to delete them.
 350     for (Module::iterator FI = Program->begin(), E = Program->end();
 351          FI != E; ++FI)
 352       if (!FI->isExternal()) {
 353         for (Function::iterator BI = FI->begin(), E = FI->end(); BI != E; ++BI)
 354           for (BasicBlock::iterator I = BI->begin(), E = --BI->end();
 355                I != E; ++I) {
 356             Module *M = deleteInstructionFromProgram(I, Simplification);
 357
 358             // Make the function the current program...
 359             std::swap(Program, M);
 360
 361             // Find out if the pass still crashes on this pass...
 362             std::cout << "Checking instruction '" << I->getName() << "': ";
 363             if (runPasses(PassesToRun)) {
 364               // Yup, it does, we delete the old module, and continue trying to
 365               // reduce the testcase...
 366               delete M;
 367               AnyReduction = true;
 368               goto TryAgain;  // I wish I had a multi-level break here!
 369             }
 370
 371             // This pass didn't crash without this instruction, try the next
 372             // one.
 373             delete Program;
 374             Program = M;
 375           }
 376       }
 377   } while (Simplification);
 378
 379   // Try to clean up the testcase by running funcresolve and globaldce...
 380   std::cout << "\n*** Attempting to perform final cleanups: ";
 381   Module *M = CloneModule(Program);
 382   M = performFinalCleanups(M, true);
 383   std::swap(Program, M);
 384
 385   // Find out if the pass still crashes on the cleaned up program...
 386   if (runPasses(PassesToRun)) {
 387     // Yup, it does, keep the reduced version...
 388     delete M;
 389     AnyReduction = true;
 390   } else {
 391     delete Program;   // Otherwise, restore the original module...
 392     Program = M;
 393   }
 394
 395   if (AnyReduction)
 396     EmitProgressBytecode("reduced-simplified");
 397
 398   return false;
 399 }