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