tools/bugpoint/Miscompilation.cpp

   1 //===- Miscompilation.cpp - Debug program miscompilations -----------------===//
   2 //
   3 // This file implements program miscompilation debugging support.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "BugDriver.h"
   8 #include "SystemUtils.h"
   9 #include "ListReducer.h"
  10 #include "llvm/Pass.h"
  11 #include "llvm/Module.h"
  12 #include "llvm/Transforms/Utils/Cloning.h"
  13 #include "llvm/Transforms/Utils/Linker.h"
  14 #include "Support/CommandLine.h"
  15
  16 // Anonymous namespace to define command line options for miscompilation
  17 // debugging.
  18 //
  19 namespace {
  20   // Output - The user can specify a file containing the expected output of the
  21   // program.  If this filename is set, it is used as the reference diff source,
  22   // otherwise the raw input run through an interpreter is used as the reference
  23   // source.
  24   //
  25   cl::opt<std::string>
  26   Output("output", cl::desc("Specify a reference program output "
  27                             "(for miscompilation detection)"));
  28 }
  29
  30 class ReduceMiscompilingPasses : public ListReducer<const PassInfo*> {
  31   BugDriver &BD;
  32 public:
  33   ReduceMiscompilingPasses(BugDriver &bd) : BD(bd) {}
  34
  35   virtual TestResult doTest(std::vector<const PassInfo*> &Prefix,
  36                             std::vector<const PassInfo*> &Kept);
  37 };
  38
  39 ReduceMiscompilingPasses::TestResult
  40 ReduceMiscompilingPasses::doTest(std::vector<const PassInfo*> &Prefix,
  41                                  std::vector<const PassInfo*> &Suffix) {
  42   // First, run the program with just the Suffix passes.  If it is still broken
  43   // with JUST the kept passes, discard the prefix passes.
  44   std::cout << "Checking to see if '" << getPassesString(Suffix)
  45             << "' compile correctly: ";
  46
  47   std::string BytecodeResult;
  48   if (BD.runPasses(Suffix, BytecodeResult, false/*delete*/, true/*quiet*/)) {
  49     std::cerr << BD.getToolName() << ": Error running this sequence of passes"
  50               << " on the input program!\n";
  51     exit(1);
  52   }
  53
  54   // Check to see if the finished program matches the reference output...
  55   if (BD.diffProgram(Output, BytecodeResult, true /*delete bytecode*/)) {
  56     std::cout << "nope.\n";
  57     return KeepSuffix;        // Miscompilation detected!
  58   }
  59   std::cout << "yup.\n";      // No miscompilation!
  60
  61   if (Prefix.empty()) return NoFailure;
  62
  63   // Next, see if the program is broken if we run the "prefix" passes first,
  64   // then separately run the "kept" passes.
  65   std::cout << "Checking to see if '" << getPassesString(Prefix)
  66             << "' compile correctly: ";
  67
  68   // If it is not broken with the kept passes, it's possible that the prefix
  69   // passes must be run before the kept passes to break it.  If the program
  70   // WORKS after the prefix passes, but then fails if running the prefix AND
  71   // kept passes, we can update our bytecode file to include the result of the
  72   // prefix passes, then discard the prefix passes.
  73   //
  74   if (BD.runPasses(Prefix, BytecodeResult, false/*delete*/, true/*quiet*/)) {
  75     std::cerr << BD.getToolName() << ": Error running this sequence of passes"
  76               << " on the input program!\n";
  77     exit(1);
  78   }
  79
  80   // If the prefix maintains the predicate by itself, only keep the prefix!
  81   if (BD.diffProgram(Output, BytecodeResult)) {
  82     std::cout << "nope.\n";
  83     removeFile(BytecodeResult);
  84     return KeepPrefix;
  85   }
  86   std::cout << "yup.\n";      // No miscompilation!
  87
  88   // Ok, so now we know that the prefix passes work, try running the suffix
  89   // passes on the result of the prefix passes.
  90   //
  91   Module *PrefixOutput = BD.ParseInputFile(BytecodeResult);
  92   if (PrefixOutput == 0) {
  93     std::cerr << BD.getToolName() << ": Error reading bytecode file '"
  94               << BytecodeResult << "'!\n";
  95     exit(1);
  96   }
  97   removeFile(BytecodeResult);  // No longer need the file on disk
  98
  99   std::cout << "Checking to see if '" << getPassesString(Suffix)
 100             << "' passes compile correctly after the '"
 101             << getPassesString(Prefix) << "' passes: ";
 102
 103   Module *OriginalInput = BD.Program;
 104   BD.Program = PrefixOutput;
 105   if (BD.runPasses(Suffix, BytecodeResult, false/*delete*/, true/*quiet*/)) {
 106     std::cerr << BD.getToolName() << ": Error running this sequence of passes"
 107               << " on the input program!\n";
 108     exit(1);
 109   }
 110
 111   // Run the result...
 112   if (BD.diffProgram(Output, BytecodeResult, true/*delete bytecode*/)) {
 113     std::cout << "nope.\n";
 114     delete OriginalInput;     // We pruned down the original input...
 115     return KeepSuffix;
 116   }
 117
 118   // Otherwise, we must not be running the bad pass anymore.
 119   std::cout << "yup.\n";      // No miscompilation!
 120   BD.Program = OriginalInput; // Restore original program
 121   delete PrefixOutput;        // Free experiment
 122   return NoFailure;
 123 }
 124
 125 static void PrintFunctionList(const std::vector<Function*> &Funcs) {
 126   for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
 127     if (i) std::cout << ", ";
 128     std::cout << Funcs[i]->getName();
 129   }
 130 }
 131
 132
 133 class ReduceMiscompilingFunctions : public ListReducer<Function*> {
 134   BugDriver &BD;
 135 public:
 136   ReduceMiscompilingFunctions(BugDriver &bd) : BD(bd) {}
 137
 138   virtual TestResult doTest(std::vector<Function*> &Prefix,
 139                             std::vector<Function*> &Suffix) {
 140     if (TestFuncs(Suffix, false))
 141       return KeepSuffix;
 142     if (!Prefix.empty() && TestFuncs(Prefix, false))
 143       return KeepPrefix;
 144     return NoFailure;
 145   }
 146
 147   bool TestFuncs(const std::vector<Function*> &Prefix, bool EmitBytecode);
 148 };
 149
 150 bool ReduceMiscompilingFunctions::TestFuncs(const std::vector<Function*> &Funcs,
 151                                             bool EmitBytecode) {
 152   // Test to see if the function is misoptimized if we ONLY run it on the
 153   // functions listed in Funcs.
 154   if (!EmitBytecode) {
 155     std::cout << "Checking to see if the program is misoptimized when these "
 156               << "functions are run\nthrough the passes: ";
 157     PrintFunctionList(Funcs);
 158     std::cout << "\n";
 159   } else {
 160     std::cout <<"Outputting reduced bytecode files which expose the problem:\n";
 161   }
 162
 163   // First step: clone the module for the two halves of the program we want.
 164   Module *ToOptimize = CloneModule(BD.Program);
 165
 166   // Second step: Make sure functions & globals are all external so that linkage
 167   // between the two modules will work.
 168   for (Module::iterator I = ToOptimize->begin(), E = ToOptimize->end();I!=E;++I)
 169     I->setLinkage(GlobalValue::ExternalLinkage);
 170   for (Module::giterator I = ToOptimize->gbegin(), E = ToOptimize->gend();
 171        I != E; ++I)
 172     I->setLinkage(GlobalValue::ExternalLinkage);
 173
 174   // Third step: make a clone of the externalized program for the non-optimized
 175   // part.
 176   Module *ToNotOptimize = CloneModule(ToOptimize);
 177
 178   // Fourth step: Remove the test functions from the ToNotOptimize module, and
 179   // all of the global variables.
 180   for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
 181     Function *TNOF = ToNotOptimize->getFunction(Funcs[i]->getName(),
 182                                                 Funcs[i]->getFunctionType());
 183     assert(TNOF && "Function doesn't exist in module!");
 184     DeleteFunctionBody(TNOF);       // Function is now external in this module!
 185   }
 186   for (Module::giterator I = ToNotOptimize->gbegin(), E = ToNotOptimize->gend();
 187        I != E; ++I)
 188     I->setInitializer(0);  // Delete the initializer to make it external
 189
 190   if (EmitBytecode) {
 191     std::cout << "  Non-optimized portion: ";
 192     std::swap(BD.Program, ToNotOptimize);
 193     BD.EmitProgressBytecode("tonotoptimize", true);
 194     std::swap(BD.Program, ToNotOptimize);
 195   }
 196
 197   // Fifth step: Remove all functions from the ToOptimize module EXCEPT for the
 198   // ones specified in Funcs.  We know which ones these are because they are
 199   // non-external in ToOptimize, but external in ToNotOptimize.
 200   //
 201   for (Module::iterator I = ToOptimize->begin(), E = ToOptimize->end();I!=E;++I)
 202     if (!I->isExternal()) {
 203       Function *TNOF = ToNotOptimize->getFunction(I->getName(),
 204                                                   I->getFunctionType());
 205       assert(TNOF && "Function doesn't exist in ToNotOptimize module??");
 206       if (!TNOF->isExternal())
 207         DeleteFunctionBody(I);
 208     }
 209
 210   if (EmitBytecode) {
 211     std::cout << "  Portion that is input to optimizer: ";
 212     std::swap(BD.Program, ToOptimize);
 213     BD.EmitProgressBytecode("tooptimize");
 214     std::swap(BD.Program, ToOptimize);
 215   }
 216
 217   // Sixth step: Run the optimization passes on ToOptimize, producing a
 218   // transformed version of the functions being tested.
 219   Module *OldProgram = BD.Program;
 220   BD.Program = ToOptimize;
 221
 222   if (!EmitBytecode)
 223     std::cout << "  Optimizing functions being tested: ";
 224   std::string BytecodeResult;
 225   if (BD.runPasses(BD.PassesToRun, BytecodeResult, false/*delete*/,
 226                    true/*quiet*/)) {
 227     std::cerr << BD.getToolName() << ": Error running this sequence of passes"
 228               << " on the input program!\n";
 229     exit(1);
 230   }
 231
 232   if (!EmitBytecode)
 233     std::cout << "done.\n";
 234
 235   delete BD.Program;   // Delete the old "ToOptimize" module
 236   BD.Program = BD.ParseInputFile(BytecodeResult);
 237
 238   if (EmitBytecode) {
 239     std::cout << "  'tooptimize' after being optimized: ";
 240     BD.EmitProgressBytecode("optimized", true);
 241   }
 242
 243   if (BD.Program == 0) {
 244     std::cerr << BD.getToolName() << ": Error reading bytecode file '"
 245               << BytecodeResult << "'!\n";
 246     exit(1);
 247   }
 248   removeFile(BytecodeResult);  // No longer need the file on disk
 249
 250   // Seventh step: Link the optimized part of the program back to the
 251   // unoptimized part of the program.
 252   //
 253   if (LinkModules(BD.Program, ToNotOptimize, &BytecodeResult)) {
 254     std::cerr << BD.getToolName() << ": Error linking modules together:"
 255               << BytecodeResult << "\n";
 256     exit(1);
 257   }
 258   delete ToNotOptimize;  // We are done with this module...
 259
 260   if (EmitBytecode) {
 261     std::cout << "  Program as tested: ";
 262     BD.EmitProgressBytecode("linked", true);
 263     delete BD.Program;
 264     BD.Program = OldProgram;
 265     return false;   // We don't need to actually execute the program here.
 266   }
 267
 268   std::cout << "  Checking to see if the merged program executes correctly: ";
 269
 270   // Eighth step: Execute the program.  If it does not match the expected
 271   // output, then 'Funcs' are being misoptimized!
 272   bool Broken = BD.diffProgram(Output);
 273
 274   delete BD.Program;  // Delete the hacked up program
 275   BD.Program = OldProgram;   // Restore the original
 276
 277   std::cout << (Broken ? "nope.\n" : "yup.\n");
 278   return Broken;
 279 }
 280
 281
 282 /// debugMiscompilation - This method is used when the passes selected are not
 283 /// crashing, but the generated output is semantically different from the
 284 /// input.
 285 ///
 286 bool BugDriver::debugMiscompilation() {
 287   std::cout << "*** Debugging miscompilation!\n";
 288
 289   // Set up the execution environment, selecting a method to run LLVM bytecode.
 290   if (initializeExecutionEnvironment()) return true;
 291
 292   // Run the raw input to see where we are coming from.  If a reference output
 293   // was specified, make sure that the raw output matches it.  If not, it's a
 294   // problem in the front-end or whatever produced the input code.
 295   //
 296   bool CreatedOutput = false;
 297   if (Output.empty()) {
 298     std::cout << "Generating reference output from raw program...";
 299     Output = executeProgram("bugpoint.reference.out");
 300     CreatedOutput = true;
 301     std::cout << " done! Reference output is: " << Output << "\n";
 302   } else if (diffProgram(Output)) {
 303     std::cout << "\n*** Input program does not match reference diff!\n"
 304               << "    Must be problem with input source!\n";
 305     return false;  // Problem found
 306   }
 307
 308   // Figure out which transformations miscompile the input program.
 309   unsigned OldSize = PassesToRun.size();
 310   ReduceMiscompilingPasses(*this).reduceList(PassesToRun);
 311
 312   // Make sure something was miscompiled...
 313   if (PassesToRun.size() == OldSize) {
 314     std::cerr << "*** Optimized program matches reference output!  No problem "
 315               << "detected...\nbugpoint can't help you with your problem!\n";
 316     return false;
 317   }
 318
 319   std::cout << "\n*** Found miscompiling pass"
 320             << (PassesToRun.size() == 1 ? "" : "es") << ": "
 321             << getPassesString(PassesToRun) << "\n";
 322   EmitProgressBytecode("passinput");
 323
 324
 325   // Okay, now that we have reduced the list of passes which are causing the
 326   // failure, see if we can pin down which functions are being
 327   // miscompiled... first build a list of all of the non-external functions in
 328   // the program.
 329   std::vector<Function*> MiscompiledFunctions;
 330   for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
 331     if (!I->isExternal())
 332       MiscompiledFunctions.push_back(I);
 333
 334   // Do the reduction...
 335   ReduceMiscompilingFunctions(*this).reduceList(MiscompiledFunctions);
 336
 337   std::cout << "\n*** The following functions are being miscompiled: ";
 338   PrintFunctionList(MiscompiledFunctions);
 339   std::cout << "\n";
 340
 341   // Output a bunch of bytecode files for the user...
 342   ReduceMiscompilingFunctions(*this).TestFuncs(MiscompiledFunctions, true);
 343
 344   if (CreatedOutput) removeFile(Output);
 345   return false;
 346 }