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   std::cout << "\n*** Found crashing pass"
 133             << (PassesToRun.size() == 1 ? ": " : "es: ")
 134             << getPassesString(PassesToRun) << "\n";
 135
 136   EmitProgressBytecode("passinput");
 137
 138   // Now try to reduce the number of functions in the module to something small.
 139   std::vector<Function*> Functions;
 140   for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
 141     if (!I->isExternal())
 142       Functions.push_back(I);
 143
 144   if (Functions.size() > 1) {
 145     std::cout << "\n*** Attempting to reduce the number of functions "
 146       "in the testcase\n";
 147
 148     OldSize = Functions.size();
 149     ReduceCrashingFunctions(*this).reduceList(Functions);
 150
 151     if (Functions.size() < OldSize) {
 152       EmitProgressBytecode("reduced-function");
 153       AnyReduction = true;
 154     }
 155   }
 156
 157   // FIXME: This should attempt to delete entire basic blocks at a time to speed
 158   // up convergence...
 159
 160   // FIXME: This should use the list reducer to converge faster by deleting
 161   // larger chunks of instructions at a time!
 162   unsigned Simplification = 4;
 163   do {
 164     --Simplification;
 165     std::cout << "\n*** Attempting to reduce testcase by deleting instruc"
 166               << "tions: Simplification Level #" << Simplification << "\n";
 167
 168     // Now that we have deleted the functions that are unneccesary for the
 169     // program, try to remove instructions that are not neccesary to cause the
 170     // crash.  To do this, we loop through all of the instructions in the
 171     // remaining functions, deleting them (replacing any values produced with
 172     // nulls), and then running ADCE and SimplifyCFG.  If the transformed input
 173     // still triggers failure, keep deleting until we cannot trigger failure
 174     // anymore.
 175     //
 176   TryAgain:
 177
 178     // Loop over all of the (non-terminator) instructions remaining in the
 179     // function, attempting to delete them.
 180     for (Module::iterator FI = Program->begin(), E = Program->end();
 181          FI != E; ++FI)
 182       if (!FI->isExternal()) {
 183         for (Function::iterator BI = FI->begin(), E = FI->end(); BI != E; ++BI)
 184           for (BasicBlock::iterator I = BI->begin(), E = --BI->end();
 185                I != E; ++I) {
 186             Module *M = deleteInstructionFromProgram(I, Simplification);
 187
 188             // Make the function the current program...
 189             std::swap(Program, M);
 190
 191             // Find out if the pass still crashes on this pass...
 192             std::cout << "Checking instruction '" << I->getName() << "': ";
 193             if (runPasses(PassesToRun)) {
 194               // Yup, it does, we delete the old module, and continue trying to
 195               // reduce the testcase...
 196               delete M;
 197               AnyReduction = true;
 198               goto TryAgain;  // I wish I had a multi-level break here!
 199             }
 200
 201             // This pass didn't crash without this instruction, try the next
 202             // one.
 203             delete Program;
 204             Program = M;
 205           }
 206       }
 207   } while (Simplification);
 208
 209   // Try to clean up the testcase by running funcresolve and globaldce...
 210   if (AnyReduction) {
 211     std::cout << "\n*** Attempting to perform final cleanups: ";
 212     Module *M = performFinalCleanups();
 213     std::swap(Program, M);
 214
 215     // Find out if the pass still crashes on the cleaned up program...
 216     if (runPasses(PassesToRun)) {
 217       // Yup, it does, keep the reduced version...
 218       delete M;
 219       AnyReduction = true;
 220     } else {
 221       delete Program;   // Otherwise, restore the original module...
 222       Program = M;
 223     }
 224   }
 225
 226   if (AnyReduction)
 227     EmitProgressBytecode("reduced-simplified");
 228
 229   return false;
 230 }