tools/bugpoint/Miscompilation.cpp

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