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/Transforms/Utils/Cloning.h"
  12 #include "llvm/Bytecode/Writer.h"
  13 #include "llvm/Pass.h"
  14 #include <fstream>
  15 #include <set>
  16
  17 class DebugCrashes : public ListReducer<const PassInfo*> {
  18   BugDriver &BD;
  19 public:
  20   DebugCrashes(BugDriver &bd) : BD(bd) {}
  21
  22   // doTest - Return true iff running the "removed" passes succeeds, and running
  23   // the "Kept" passes fail when run on the output of the "removed" passes.  If
  24   // we return true, we update the current module of bugpoint.
  25   //
  26   virtual TestResult doTest(std::vector<const PassInfo*> &Removed,
  27                             std::vector<const PassInfo*> &Kept);
  28 };
  29
  30 DebugCrashes::TestResult
  31 DebugCrashes::doTest(std::vector<const PassInfo*> &Prefix,
  32                      std::vector<const PassInfo*> &Suffix) {
  33   std::string PrefixOutput;
  34   if (!Prefix.empty()) {
  35     std::cout << "Checking to see if these passes crash: "
  36               << getPassesString(Prefix) << ": ";
  37     if (BD.runPasses(Prefix, PrefixOutput))
  38       return KeepPrefix;
  39   }
  40
  41   std::cout << "Checking to see if these passes crash: "
  42             << getPassesString(Suffix) << ": ";
  43   Module *OrigProgram = BD.Program;
  44   BD.Program = BD.ParseInputFile(PrefixOutput);
  45   if (BD.Program == 0) {
  46     std::cerr << BD.getToolName() << ": Error reading bytecode file '"
  47               << PrefixOutput << "'!\n";
  48     exit(1);
  49   }
  50   removeFile(PrefixOutput);
  51
  52   if (BD.runPasses(Suffix)) {
  53     delete OrigProgram;            // The suffix crashes alone...
  54     return KeepSuffix;
  55   }
  56
  57   // Nothing failed, restore state...
  58   delete BD.Program;
  59   BD.Program = OrigProgram;
  60   return NoFailure;
  61 }
  62
  63 class ReduceCrashingFunctions : public ListReducer<Function*> {
  64   BugDriver &BD;
  65 public:
  66   ReduceCrashingFunctions(BugDriver &bd) : BD(bd) {}
  67
  68   virtual TestResult doTest(std::vector<Function*> &Prefix,
  69                             std::vector<Function*> &Kept) {
  70     if (TestFuncs(Kept))
  71       return KeepSuffix;
  72     if (!Prefix.empty() && TestFuncs(Prefix))
  73       return KeepPrefix;
  74     return NoFailure;
  75   }
  76
  77   bool TestFuncs(std::vector<Function*> &Prefix);
  78 };
  79
  80 bool ReduceCrashingFunctions::TestFuncs(std::vector<Function*> &Funcs) {
  81   // Clone the program to try hacking it appart...
  82   Module *M = CloneModule(BD.Program);
  83
  84   // Convert list to set for fast lookup...
  85   std::set<Function*> Functions;
  86   for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
  87     Function *CMF = M->getFunction(Funcs[i]->getName(),
  88                                    Funcs[i]->getFunctionType());
  89     assert(CMF && "Function not in module?!");
  90     Functions.insert(CMF);
  91   }
  92
  93   std::cout << "Checking for crash with only these functions:";
  94   for (unsigned i = 0, e = Funcs.size(); i != e; ++i)
  95     std::cout << " " << Funcs[i]->getName();
  96   std::cout << ": ";
  97
  98   // Loop over and delete any functions which we aren't supposed to be playing
  99   // with...
 100   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
 101     if (I->isExternal() && !Functions.count(I))
 102       DeleteFunctionBody(I);
 103
 104   // Try running the hacked up program...
 105   std::swap(BD.Program, M);
 106   if (BD.runPasses(BD.PassesToRun)) {
 107     delete M;         // It crashed, keep the trimmed version...
 108
 109     // Make sure to use function pointers that point into the now-current
 110     // module.
 111     Funcs.assign(Functions.begin(), Functions.end());
 112     return true;
 113   }
 114   delete BD.Program;  // It didn't crash, revert...
 115   BD.Program = M;
 116   return false;
 117 }
 118
 119
 120 /// debugCrash - This method is called when some pass crashes on input.  It
 121 /// attempts to prune down the testcase to something reasonable, and figure
 122 /// out exactly which pass is crashing.
 123 ///
 124 bool BugDriver::debugCrash() {
 125   bool AnyReduction = false;
 126   std::cout << "\n*** Debugging optimizer crash!\n";
 127
 128   // Reduce the list of passes which causes the optimizer to crash...
 129   unsigned OldSize = PassesToRun.size();
 130   DebugCrashes(*this).reduceList(PassesToRun);
 131
 132   if (PassesToRun.size() == OldSize) { // Make sure something crashed.  :)
 133     std::cerr << "ERROR: No passes crashed!\n";
 134     return true;
 135   }
 136
 137   std::cout << "\n*** Found crashing pass"
 138             << (PassesToRun.size() == 1 ? ": " : "es: ")
 139             << getPassesString(PassesToRun) << "\n";
 140
 141   EmitProgressBytecode("passinput");
 142
 143   // Now try to reduce the number of functions in the module to something small.
 144   std::vector<Function*> Functions;
 145   for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
 146     if (!I->isExternal())
 147       Functions.push_back(I);
 148
 149   if (Functions.size() > 1) {
 150     std::cout << "\n*** Attempting to reduce the number of functions "
 151       "in the testcase\n";
 152
 153     OldSize = Functions.size();
 154     ReduceCrashingFunctions(*this).reduceList(Functions);
 155
 156     if (Functions.size() < OldSize) {
 157       EmitProgressBytecode("reduced-function");
 158       AnyReduction = true;
 159     }
 160   }
 161
 162   // FIXME: This should attempt to delete entire basic blocks at a time to speed
 163   // up convergence...
 164
 165   // FIXME: This should use the list reducer to converge faster by deleting
 166   // larger chunks of instructions at a time!
 167   bool Reduced = false;
 168   unsigned Simplification = 4;
 169   do {
 170     --Simplification;
 171     std::cout << "\n*** Attempting to reduce testcase by deleting instruc"
 172               << "tions: Simplification Level #" << Simplification << "\n";
 173
 174     // Now that we have deleted the functions that are unneccesary for the
 175     // program, try to remove instructions that are not neccesary to cause the
 176     // crash.  To do this, we loop through all of the instructions in the
 177     // remaining functions, deleting them (replacing any values produced with
 178     // nulls), and then running ADCE and SimplifyCFG.  If the transformed input
 179     // still triggers failure, keep deleting until we cannot trigger failure
 180     // anymore.
 181     //
 182   TryAgain:
 183
 184     // Loop over all of the (non-terminator) instructions remaining in the
 185     // function, attempting to delete them.
 186     for (Module::iterator FI = Program->begin(), E = Program->end();
 187          FI != E; ++FI)
 188       if (!FI->isExternal()) {
 189         for (Function::iterator BI = FI->begin(), E = FI->end(); BI != E; ++BI)
 190           for (BasicBlock::iterator I = BI->begin(), E = --BI->end();
 191                I != E; ++I) {
 192             Module *M = deleteInstructionFromProgram(I, Simplification);
 193
 194             // Make the function the current program...
 195             std::swap(Program, M);
 196
 197             // Find out if the pass still crashes on this pass...
 198             std::cout << "Checking instruction '" << I->getName() << "': ";
 199             if (runPasses(PassesToRun)) {
 200               // Yup, it does, we delete the old module, and continue trying to
 201               // reduce the testcase...
 202               delete M;
 203               Reduced = AnyReduction = true;
 204               goto TryAgain;  // I wish I had a multi-level break here!
 205             }
 206
 207             // This pass didn't crash without this instruction, try the next
 208             // one.
 209             delete Program;
 210             Program = M;
 211           }
 212       }
 213   } while (Simplification);
 214
 215   // Try to clean up the testcase by running funcresolve and globaldce...
 216   if (AnyReduction) {
 217     std::cout << "\n*** Attempting to perform final cleanups: ";
 218     Module *M = performFinalCleanups();
 219     std::swap(Program, M);
 220
 221     // Find out if the pass still crashes on the cleaned up program...
 222     if (runPasses(PassesToRun)) {
 223       // Yup, it does, keep the reduced version...
 224       delete M;
 225       Reduced = AnyReduction = true;
 226     } else {
 227       delete Program;   // Otherwise, restore the original module...
 228       Program = M;
 229     }
 230   }
 231
 232   if (Reduced) {
 233     EmitProgressBytecode("reduced-simplified");
 234     Reduced = false;
 235   }
 236
 237   return false;
 238 }