CrashDebugger.cpp revision 6520785dcd22012535934098942d57c07c7631c2
1afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner//===- CrashDebugger.cpp - Debug compilation crashes ----------------------===//
2afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner//
3afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner// This file defines the bugpoint internals that narrow down compilation crashes
4afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner//
5afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner//===----------------------------------------------------------------------===//
6afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
7afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "BugDriver.h"
8218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner#include "SystemUtils.h"
9afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "llvm/Module.h"
10afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "llvm/Bytecode/Writer.h"
11afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "llvm/Pass.h"
12afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include <fstream>
13afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
14afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// debugCrash - This method is called when some pass crashes on input.  It
15afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// attempts to prune down the testcase to something reasonable, and figure
16afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// out exactly which pass is crashing.
17afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner///
18afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattnerbool BugDriver::debugCrash() {
19afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  std::cout << "\n*** Debugging optimizer crash!\n";
20afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
21afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  // Determine which pass causes the optimizer to crash... using binary search
22afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  unsigned LastToPass = 0, LastToCrash = PassesToRun.size();
23afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  while (LastToPass != LastToCrash) {
24afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    unsigned Mid = (LastToCrash+LastToPass+1) / 2;
25afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    std::vector<const PassInfo*> P(PassesToRun.begin(),
26afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner                                   PassesToRun.begin()+Mid);
27afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    std::cout << "Checking to see if the first " << Mid << " passes crash: ";
28afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
29afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    if (runPasses(P))
30afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner      LastToCrash = Mid-1;
31afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    else
32afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner      LastToPass = Mid;
33afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  }
34afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
35afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  // Make sure something crashed.  :)
36afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  if (LastToCrash >= PassesToRun.size()) {
37afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    std::cerr << "ERROR: No passes crashed!\n";
38afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    return true;
39afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  }
40afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
41afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  // Calculate which pass it is that crashes...
42afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  const PassInfo *CrashingPass = PassesToRun[LastToCrash];
43afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
44afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  std::cout << "\n*** Found crashing pass '-" << CrashingPass->getPassArgument()
45afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner            << "': " << CrashingPass->getPassName() << "\n";
46afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
47afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  // Compile the program with just the passes that don't crash.
48218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner  if (LastToPass != 0) { // Don't bother doing this if the first pass crashes...
49afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    std::vector<const PassInfo*> P(PassesToRun.begin(),
50afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner                                   PassesToRun.begin()+LastToPass);
51afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    std::string Filename;
52afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    std::cout << "Running passes that don't crash to get input for pass: ";
53afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    if (runPasses(P, Filename)) {
54afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner      std::cerr << "ERROR: Running the first " << LastToPass
55afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner                << " passes crashed this time!\n";
56afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner      return true;
57afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    }
58afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
59afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    // Assuming everything was successful, we now have a valid bytecode file in
60afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    // OutputName.  Use it for "Program" Instead.
61afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    delete Program;
62afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    Program = ParseInputFile(Filename);
63afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
64afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    // Delete the file now.
65afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    removeFile(Filename);
66afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  }
67afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
68afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  return debugPassCrash(CrashingPass);
69afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner}
70afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
71afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// CountFunctions - return the number of non-external functions defined in the
72afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// module.
73afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattnerstatic unsigned CountFunctions(Module *M) {
74afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  unsigned N = 0;
75afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
76afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    if (!I->isExternal())
77afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner      ++N;
78afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  return N;
79afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner}
80afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
81afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// debugPassCrash - This method is called when the specified pass crashes on
82afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// Program as input.  It tries to reduce the testcase to something that still
83afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner/// crashes, but it smaller.
84afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner///
85afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattnerbool BugDriver::debugPassCrash(const PassInfo *Pass) {
86afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  EmitProgressBytecode(Pass, "passinput");
87afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
88afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  if (CountFunctions(Program) > 1) {
89afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    // Attempt to reduce the input program down to a single function that still
90218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner    // crashes.  Do this by removing everything except for that one function...
91afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    //
92afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    std::cout << "\n*** Attempting to reduce the testcase to one function\n";
93afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
94afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner    for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
95afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner      if (!I->isExternal()) {
96afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        // Extract one function from the module...
97afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        Module *M = extractFunctionFromModule(I);
98afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
99afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        // Make the function the current program...
100afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        std::swap(Program, M);
101afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
102afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        // Find out if the pass still crashes on this pass...
103afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        std::cout << "Checking function '" << I->getName() << "': ";
104afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        if (runPass(Pass)) {
105afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner          // Yup, it does, we delete the old module, and continue trying to
106afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner          // reduce the testcase...
107afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner          delete M;
108afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
109afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner          EmitProgressBytecode(Pass, "reduced-"+I->getName());
110afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner          break;
111afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        }
112afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
113afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        // This pass didn't crash on this function, try the next one.
114afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        delete Program;
115afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner        Program = M;
116afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner      }
117afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner
1186520785dcd22012535934098942d57c07c7631c2Chris Lattner    if (CountFunctions(Program) > 1) {
1196520785dcd22012535934098942d57c07c7631c2Chris Lattner      std::cout << "\n*** Couldn't reduce testcase to one function.\n"
1206520785dcd22012535934098942d57c07c7631c2Chris Lattner                << "    Attempting to remove individual functions.\n";
1216520785dcd22012535934098942d57c07c7631c2Chris Lattner      std::cout << "XXX Individual function removal unimplemented!\n";
1226520785dcd22012535934098942d57c07c7631c2Chris Lattner    }
123218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner  }
124218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner
1256520785dcd22012535934098942d57c07c7631c2Chris Lattner  // FIXME: This should attempt to delete entire basic blocks at a time to speed
1266520785dcd22012535934098942d57c07c7631c2Chris Lattner  // up convergence...
1276520785dcd22012535934098942d57c07c7631c2Chris Lattner
1286520785dcd22012535934098942d57c07c7631c2Chris Lattner  unsigned Simplification = 4;
1296520785dcd22012535934098942d57c07c7631c2Chris Lattner  do {
1306520785dcd22012535934098942d57c07c7631c2Chris Lattner    --Simplification;
1316520785dcd22012535934098942d57c07c7631c2Chris Lattner    std::cout << "\n*** Attempting to reduce testcase by deleting instruc"
1326520785dcd22012535934098942d57c07c7631c2Chris Lattner              << "tions: Simplification Level #" << Simplification << "\n";
1336520785dcd22012535934098942d57c07c7631c2Chris Lattner
1346520785dcd22012535934098942d57c07c7631c2Chris Lattner    // Now that we have deleted the functions that are unneccesary for the
1356520785dcd22012535934098942d57c07c7631c2Chris Lattner    // program, try to remove instructions that are not neccesary to cause the
1366520785dcd22012535934098942d57c07c7631c2Chris Lattner    // crash.  To do this, we loop through all of the instructions in the
1376520785dcd22012535934098942d57c07c7631c2Chris Lattner    // remaining functions, deleting them (replacing any values produced with
1386520785dcd22012535934098942d57c07c7631c2Chris Lattner    // nulls), and then running ADCE and SimplifyCFG.  If the transformed input
1396520785dcd22012535934098942d57c07c7631c2Chris Lattner    // still triggers failure, keep deleting until we cannot trigger failure
1406520785dcd22012535934098942d57c07c7631c2Chris Lattner    // anymore.
1416520785dcd22012535934098942d57c07c7631c2Chris Lattner    //
1426520785dcd22012535934098942d57c07c7631c2Chris Lattner  TryAgain:
1436520785dcd22012535934098942d57c07c7631c2Chris Lattner
1446520785dcd22012535934098942d57c07c7631c2Chris Lattner    // Loop over all of the (non-terminator) instructions remaining in the
1456520785dcd22012535934098942d57c07c7631c2Chris Lattner    // function, attempting to delete them.
1466520785dcd22012535934098942d57c07c7631c2Chris Lattner    for (Module::iterator FI = Program->begin(), E = Program->end();
1476520785dcd22012535934098942d57c07c7631c2Chris Lattner         FI != E; ++FI)
1486520785dcd22012535934098942d57c07c7631c2Chris Lattner      if (!FI->isExternal()) {
1496520785dcd22012535934098942d57c07c7631c2Chris Lattner        for (Function::iterator BI = FI->begin(), E = FI->end(); BI != E; ++BI)
1506520785dcd22012535934098942d57c07c7631c2Chris Lattner          for (BasicBlock::iterator I = BI->begin(), E = --BI->end();
1516520785dcd22012535934098942d57c07c7631c2Chris Lattner               I != E; ++I) {
1526520785dcd22012535934098942d57c07c7631c2Chris Lattner            Module *M = deleteInstructionFromProgram(I, Simplification);
1536520785dcd22012535934098942d57c07c7631c2Chris Lattner
1546520785dcd22012535934098942d57c07c7631c2Chris Lattner            // Make the function the current program...
1556520785dcd22012535934098942d57c07c7631c2Chris Lattner            std::swap(Program, M);
1566520785dcd22012535934098942d57c07c7631c2Chris Lattner
1576520785dcd22012535934098942d57c07c7631c2Chris Lattner            // Find out if the pass still crashes on this pass...
1586520785dcd22012535934098942d57c07c7631c2Chris Lattner            std::cout << "Checking instruction '" << I->getName() << "': ";
1596520785dcd22012535934098942d57c07c7631c2Chris Lattner            if (runPass(Pass)) {
1606520785dcd22012535934098942d57c07c7631c2Chris Lattner              // Yup, it does, we delete the old module, and continue trying to
1616520785dcd22012535934098942d57c07c7631c2Chris Lattner              // reduce the testcase...
1626520785dcd22012535934098942d57c07c7631c2Chris Lattner              EmitProgressBytecode(Pass, "reduced-" + I->getName());
1636520785dcd22012535934098942d57c07c7631c2Chris Lattner              delete M;
1646520785dcd22012535934098942d57c07c7631c2Chris Lattner              goto TryAgain;  // I wish I had a multi-level break here!
1656520785dcd22012535934098942d57c07c7631c2Chris Lattner            }
1666520785dcd22012535934098942d57c07c7631c2Chris Lattner
1676520785dcd22012535934098942d57c07c7631c2Chris Lattner            // This pass didn't crash without this instruction, try the next
1686520785dcd22012535934098942d57c07c7631c2Chris Lattner            // one.
1696520785dcd22012535934098942d57c07c7631c2Chris Lattner            delete Program;
1706520785dcd22012535934098942d57c07c7631c2Chris Lattner            Program = M;
1716520785dcd22012535934098942d57c07c7631c2Chris Lattner          }
1726520785dcd22012535934098942d57c07c7631c2Chris Lattner      }
1736520785dcd22012535934098942d57c07c7631c2Chris Lattner  } while (Simplification);
174218e26ef3583cc3270f5f2a2b9cb1025e5b05ebeChris Lattner
175afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner  return false;
176afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner}
177