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 using namespace llvm;
  22
  23 namespace {
  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
  34 ReduceMiscompilingPasses::TestResult
  35 ReduceMiscompilingPasses::doTest(std::vector<const PassInfo*> &Prefix,
  36                                  std::vector<const PassInfo*> &Suffix) {
  37   // First, run the program with just the Suffix passes.  If it is still broken
  38   // with JUST the kept passes, discard the prefix passes.
  39   std::cout << "Checking to see if '" << getPassesString(Suffix)
  40             << "' compile correctly: ";
  41
  42   std::string BytecodeResult;
  43   if (BD.runPasses(Suffix, BytecodeResult, false/*delete*/, true/*quiet*/)) {
  44     std::cerr << " Error running this sequence of passes"
  45               << " on the input program!\n";
  46     BD.setPassesToRun(Suffix);
  47     BD.EmitProgressBytecode("pass-error",  false);
  48     exit(BD.debugOptimizerCrash());
  49   }
  50
  51   // Check to see if the finished program matches the reference output...
  52   if (BD.diffProgram(BytecodeResult, "", true /*delete bytecode*/)) {
  53     std::cout << "nope.\n";
  54     return KeepSuffix;        // Miscompilation detected!
  55   }
  56   std::cout << "yup.\n";      // No miscompilation!
  57
  58   if (Prefix.empty()) return NoFailure;
  59
  60   // Next, see if the program is broken if we run the "prefix" passes first,
  61   // then separately run the "kept" passes.
  62   std::cout << "Checking to see if '" << getPassesString(Prefix)
  63             << "' compile correctly: ";
  64
  65   // If it is not broken with the kept passes, it's possible that the prefix
  66   // passes must be run before the kept passes to break it.  If the program
  67   // WORKS after the prefix passes, but then fails if running the prefix AND
  68   // kept passes, we can update our bytecode file to include the result of the
  69   // prefix passes, then discard the prefix passes.
  70   //
  71   if (BD.runPasses(Prefix, BytecodeResult, false/*delete*/, true/*quiet*/)) {
  72     std::cerr << " Error running this sequence of passes"
  73               << " on the input program!\n";
  74     BD.setPassesToRun(Prefix);
  75     BD.EmitProgressBytecode("pass-error",  false);
  76     exit(BD.debugOptimizerCrash());
  77   }
  78
  79   // If the prefix maintains the predicate by itself, only keep the prefix!
  80   if (BD.diffProgram(BytecodeResult)) {
  81     std::cout << "nope.\n";
  82     removeFile(BytecodeResult);
  83     return KeepPrefix;
  84   }
  85   std::cout << "yup.\n";      // No miscompilation!
  86
  87   // Ok, so now we know that the prefix passes work, try running the suffix
  88   // passes on the result of the prefix passes.
  89   //
  90   Module *PrefixOutput = ParseInputFile(BytecodeResult);
  91   if (PrefixOutput == 0) {
  92     std::cerr << BD.getToolName() << ": Error reading bytecode file '"
  93               << BytecodeResult << "'!\n";
  94     exit(1);
  95   }
  96   removeFile(BytecodeResult);  // No longer need the file on disk
  97
  98   std::cout << "Checking to see if '" << getPassesString(Suffix)
  99             << "' passes compile correctly after the '"
 100             << getPassesString(Prefix) << "' passes: ";
 101
 102   Module *OriginalInput = BD.swapProgramIn(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.debugOptimizerCrash());
 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   delete BD.swapProgramIn(OriginalInput); // Restore orig program & free test
 121   return NoFailure;
 122 }
 123
 124 namespace {
 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))
 133         return KeepSuffix;
 134       if (!Prefix.empty() && TestFuncs(Prefix))
 135         return KeepPrefix;
 136       return NoFailure;
 137     }
 138
 139     bool TestFuncs(const std::vector<Function*> &Prefix);
 140   };
 141 }
 142
 143 /// TestMergedProgram - Given two modules, link them together and run the
 144 /// program, checking to see if the program matches the diff.  If the diff
 145 /// matches, return false, otherwise return true.  In either case, we delete
 146 /// both input modules before we return.
 147 static bool TestMergedProgram(BugDriver &BD, Module *M1, Module *M2) {
 148   // Link the two portions of the program back to together.
 149   std::string ErrorMsg;
 150   if (LinkModules(M1, M2, &ErrorMsg)) {
 151     std::cerr << BD.getToolName() << ": Error linking modules together:"
 152               << ErrorMsg << "\n";
 153     exit(1);
 154   }
 155   delete M2;  // We are done with this module...
 156
 157   Module *OldProgram = BD.swapProgramIn(M1);
 158
 159   // Execute the program.  If it does not match the expected output, we must
 160   // return true.
 161   bool Broken = BD.diffProgram();
 162
 163   // Delete the linked module & restore the original
 164   delete BD.swapProgramIn(OldProgram);
 165   return Broken;
 166 }
 167
 168 bool ReduceMiscompilingFunctions::TestFuncs(const std::vector<Function*>&Funcs){
 169   // Test to see if the function is misoptimized if we ONLY run it on the
 170   // functions listed in Funcs.
 171   std::cout << "Checking to see if the program is misoptimized when "
 172             << (Funcs.size()==1 ? "this function is" : "these functions are")
 173             << " run through the pass"
 174             << (BD.getPassesToRun().size() == 1 ? "" : "es") << ": ";
 175   PrintFunctionList(Funcs);
 176   std::cout << "\n";
 177
 178   // Split the module into the two halves of the program we want.
 179   Module *ToNotOptimize = CloneModule(BD.getProgram());
 180   Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, Funcs);
 181
 182   // Run the optimization passes on ToOptimize, producing a transformed version
 183   // of the functions being tested.
 184   Module *OldProgram = BD.swapProgramIn(ToOptimize);
 185
 186   std::cout << "  Optimizing functions being tested: ";
 187   std::string BytecodeResult;
 188   if (BD.runPasses(BD.getPassesToRun(), BytecodeResult, false/*delete*/,
 189                    true/*quiet*/)) {
 190     std::cerr << " Error running this sequence of passes"
 191               << " on the input program!\n";
 192     BD.EmitProgressBytecode("pass-error",  false);
 193     exit(BD.debugOptimizerCrash());
 194   }
 195
 196   std::cout << "done.\n";
 197
 198   // Delete the old "ToOptimize" module
 199   delete BD.swapProgramIn(OldProgram);
 200   Module *Optimized = ParseInputFile(BytecodeResult);
 201   if (Optimized == 0) {
 202     std::cerr << BD.getToolName() << ": Error reading bytecode file '"
 203               << BytecodeResult << "'!\n";
 204     exit(1);
 205   }
 206   removeFile(BytecodeResult);  // No longer need the file on disk
 207
 208   std::cout << "  Checking to see if the merged program executes correctly: ";
 209   bool Broken = TestMergedProgram(BD, Optimized, ToNotOptimize);
 210   std::cout << (Broken ? " nope.\n" : " yup.\n");
 211   return Broken;
 212 }
 213
 214 /// debugMiscompilation - This method is used when the passes selected are not
 215 /// crashing, but the generated output is semantically different from the
 216 /// input.
 217 ///
 218 bool BugDriver::debugMiscompilation() {
 219   // Make sure something was miscompiled...
 220   if (!ReduceMiscompilingPasses(*this).reduceList(PassesToRun)) {
 221     std::cerr << "*** Optimized program matches reference output!  No problem "
 222               << "detected...\nbugpoint can't help you with your problem!\n";
 223     return false;
 224   }
 225
 226   std::cout << "\n*** Found miscompiling pass"
 227             << (getPassesToRun().size() == 1 ? "" : "es") << ": "
 228             << getPassesString(getPassesToRun()) << "\n";
 229   EmitProgressBytecode("passinput");
 230
 231   // Okay, now that we have reduced the list of passes which are causing the
 232   // failure, see if we can pin down which functions are being
 233   // miscompiled... first build a list of all of the non-external functions in
 234   // the program.
 235   std::vector<Function*> MiscompiledFunctions;
 236   for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
 237     if (!I->isExternal())
 238       MiscompiledFunctions.push_back(I);
 239
 240   // Do the reduction...
 241   ReduceMiscompilingFunctions(*this).reduceList(MiscompiledFunctions);
 242
 243   std::cout << "\n*** The following function"
 244             << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
 245             << " being miscompiled: ";
 246   PrintFunctionList(MiscompiledFunctions);
 247   std::cout << "\n";
 248
 249   // Output a bunch of bytecode files for the user...
 250   std::cout << "Outputting reduced bytecode files which expose the problem:\n";
 251   Module *ToNotOptimize = CloneModule(getProgram());
 252   Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize,
 253                                                  MiscompiledFunctions);
 254
 255   std::cout << "  Non-optimized portion: ";
 256   std::swap(Program, ToNotOptimize);
 257   EmitProgressBytecode("tonotoptimize", true);
 258   setNewProgram(ToNotOptimize);   // Delete hacked module.
 259
 260   std::cout << "  Portion that is input to optimizer: ";
 261   std::swap(Program, ToOptimize);
 262   EmitProgressBytecode("tooptimize");
 263   setNewProgram(ToOptimize);      // Delete hacked module.
 264
 265   return false;
 266 }
 267