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.  If the DeleteInputs argument
 146 /// is set to true then this function deletes both input modules before it
 147 /// returns.
 148 static bool TestMergedProgram(BugDriver &BD, Module *M1, Module *M2,
 149                               bool DeleteInputs) {
 150   // Link the two portions of the program back to together.
 151   std::string ErrorMsg;
 152   if (!DeleteInputs) M1 = CloneModule(M1);
 153   if (LinkModules(M1, M2, &ErrorMsg)) {
 154     std::cerr << BD.getToolName() << ": Error linking modules together:"
 155               << ErrorMsg << "\n";
 156     exit(1);
 157   }
 158   if (DeleteInputs) delete M2;  // We are done with this module...
 159
 160   Module *OldProgram = BD.swapProgramIn(M1);
 161
 162   // Execute the program.  If it does not match the expected output, we must
 163   // return true.
 164   bool Broken = BD.diffProgram();
 165
 166   // Delete the linked module & restore the original
 167   BD.swapProgramIn(OldProgram);
 168   delete M1;
 169   return Broken;
 170 }
 171
 172 bool ReduceMiscompilingFunctions::TestFuncs(const std::vector<Function*>&Funcs){
 173   // Test to see if the function is misoptimized if we ONLY run it on the
 174   // functions listed in Funcs.
 175   std::cout << "Checking to see if the program is misoptimized when "
 176             << (Funcs.size()==1 ? "this function is" : "these functions are")
 177             << " run through the pass"
 178             << (BD.getPassesToRun().size() == 1 ? "" : "es") << ":";
 179   PrintFunctionList(Funcs);
 180   std::cout << "\n";
 181
 182   // Split the module into the two halves of the program we want.
 183   Module *ToNotOptimize = CloneModule(BD.getProgram());
 184   Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, Funcs);
 185
 186   // Run the optimization passes on ToOptimize, producing a transformed version
 187   // of the functions being tested.
 188   std::cout << "  Optimizing functions being tested: ";
 189   Module *Optimized = BD.runPassesOn(ToOptimize, BD.getPassesToRun(),
 190                                      /*AutoDebugCrashes*/true);
 191   std::cout << "done.\n";
 192   delete ToOptimize;
 193
 194
 195   std::cout << "  Checking to see if the merged program executes correctly: ";
 196   bool Broken = TestMergedProgram(BD, Optimized, ToNotOptimize, true);
 197   std::cout << (Broken ? " nope.\n" : " yup.\n");
 198   return Broken;
 199 }
 200
 201 /// ExtractLoops - Given a reduced list of functions that still exposed the bug,
 202 /// check to see if we can extract the loops in the region without obscuring the
 203 /// bug.  If so, it reduces the amount of code identified.
 204 static bool ExtractLoops(BugDriver &BD,
 205                          std::vector<Function*> &MiscompiledFunctions) {
 206   bool MadeChange = false;
 207   while (1) {
 208     Module *ToNotOptimize = CloneModule(BD.getProgram());
 209     Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize,
 210                                                    MiscompiledFunctions);
 211     Module *ToOptimizeLoopExtracted = BD.ExtractLoop(ToOptimize);
 212     if (!ToOptimizeLoopExtracted) {
 213       // If the loop extractor crashed or if there were no extractible loops,
 214       // then this chapter of our odyssey is over with.
 215       delete ToNotOptimize;
 216       delete ToOptimize;
 217       return MadeChange;
 218     }
 219
 220     std::cerr << "Extracted a loop from the breaking portion of the program.\n";
 221     delete ToOptimize;
 222
 223     // Bugpoint is intentionally not very trusting of LLVM transformations.  In
 224     // particular, we're not going to assume that the loop extractor works, so
 225     // we're going to test the newly loop extracted program to make sure nothing
 226     // has broken.  If something broke, then we'll inform the user and stop
 227     // extraction.
 228     if (TestMergedProgram(BD, ToOptimizeLoopExtracted, ToNotOptimize, false)) {
 229       // Merged program doesn't work anymore!
 230       std::cerr << "  *** ERROR: Loop extraction broke the program. :("
 231                 << " Please report a bug!\n";
 232       std::cerr << "      Continuing on with un-loop-extracted version.\n";
 233       delete ToNotOptimize;
 234       delete ToOptimizeLoopExtracted;
 235       return MadeChange;
 236     }
 237
 238     // Okay, the loop extractor didn't break the program.  Run the series of
 239     // optimizations on the loop extracted portion and see if THEY still break
 240     // the program.  If so, it was safe to extract these loops!
 241     std::cout << "  Running optimizations on loop extracted portion: ";
 242     Module *Optimized = BD.runPassesOn(ToOptimizeLoopExtracted,
 243                                        BD.getPassesToRun(),
 244                                        /*AutoDebugCrashes*/true);
 245     std::cout << "done.\n";
 246
 247     std::cout << "  Checking to see if the merged program executes correctly: ";
 248     bool Broken = TestMergedProgram(BD, Optimized, ToNotOptimize, false);
 249     delete Optimized;
 250     if (!Broken) {
 251       std::cout << "yup: loop extraction masked the problem.  Undoing.\n";
 252       // If the program is not still broken, then loop extraction did something
 253       // that masked the error.  Stop loop extraction now.
 254       delete ToNotOptimize;
 255       delete ToOptimizeLoopExtracted;
 256       return MadeChange;
 257     }
 258     std::cout << "nope: loop extraction successful!\n";
 259
 260     // Okay, great!  Now we know that we extracted a loop and that loop
 261     // extraction both didn't break the program, and didn't mask the problem.
 262     // Replace the current program with the loop extracted version, and try to
 263     // extract another loop.
 264     std::string ErrorMsg;
 265     if (LinkModules(ToNotOptimize, ToOptimizeLoopExtracted, &ErrorMsg)) {
 266       std::cerr << BD.getToolName() << ": Error linking modules together:"
 267                 << ErrorMsg << "\n";
 268       exit(1);
 269     }
 270
 271     // All of the Function*'s in the MiscompiledFunctions list are in the old
 272     // module.  Update this list to include all of the functions in the
 273     // optimized and loop extracted module.
 274     MiscompiledFunctions.clear();
 275     for (Module::iterator I = ToOptimizeLoopExtracted->begin(),
 276            E = ToOptimizeLoopExtracted->end(); I != E; ++I) {
 277       if (!I->isExternal()) {
 278         Function *OldF = I;
 279         Function *NewF =
 280           ToNotOptimize->getFunction(OldF->getName(), OldF->getFunctionType());
 281         assert(NewF && "Function not found??");
 282         MiscompiledFunctions.push_back(NewF);
 283       }
 284     }
 285     delete ToOptimizeLoopExtracted;
 286
 287     BD.setNewProgram(ToNotOptimize);
 288     MadeChange = true;
 289   }
 290 }
 291
 292 /// debugMiscompilation - This method is used when the passes selected are not
 293 /// crashing, but the generated output is semantically different from the
 294 /// input.
 295 ///
 296 bool BugDriver::debugMiscompilation() {
 297   // Make sure something was miscompiled...
 298   if (!ReduceMiscompilingPasses(*this).reduceList(PassesToRun)) {
 299     std::cerr << "*** Optimized program matches reference output!  No problem "
 300               << "detected...\nbugpoint can't help you with your problem!\n";
 301     return false;
 302   }
 303
 304   std::cout << "\n*** Found miscompiling pass"
 305             << (getPassesToRun().size() == 1 ? "" : "es") << ": "
 306             << getPassesString(getPassesToRun()) << "\n";
 307   EmitProgressBytecode("passinput");
 308
 309   // Okay, now that we have reduced the list of passes which are causing the
 310   // failure, see if we can pin down which functions are being
 311   // miscompiled... first build a list of all of the non-external functions in
 312   // the program.
 313   std::vector<Function*> MiscompiledFunctions;
 314   for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
 315     if (!I->isExternal())
 316       MiscompiledFunctions.push_back(I);
 317
 318   // Do the reduction...
 319   ReduceMiscompilingFunctions(*this).reduceList(MiscompiledFunctions);
 320
 321   std::cout << "\n*** The following function"
 322             << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
 323             << " being miscompiled: ";
 324   PrintFunctionList(MiscompiledFunctions);
 325   std::cout << "\n";
 326
 327   // See if we can rip any loops out of the miscompiled functions and still
 328   // trigger the problem.
 329   if (ExtractLoops(*this, MiscompiledFunctions)) {
 330     // Okay, we extracted some loops and the problem still appears.  See if we
 331     // can eliminate some of the created functions from being candidates.
 332
 333     // Do the reduction...
 334     ReduceMiscompilingFunctions(*this).reduceList(MiscompiledFunctions);
 335
 336     std::cout << "\n*** The following function"
 337               << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
 338               << " being miscompiled: ";
 339     PrintFunctionList(MiscompiledFunctions);
 340     std::cout << "\n";
 341   }
 342
 343   // Output a bunch of bytecode files for the user...
 344   std::cout << "Outputting reduced bytecode files which expose the problem:\n";
 345   Module *ToNotOptimize = CloneModule(getProgram());
 346   Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize,
 347                                                  MiscompiledFunctions);
 348
 349   std::cout << "  Non-optimized portion: ";
 350   std::swap(Program, ToNotOptimize);
 351   EmitProgressBytecode("tonotoptimize", true);
 352   setNewProgram(ToNotOptimize);   // Delete hacked module.
 353
 354   std::cout << "  Portion that is input to optimizer: ";
 355   std::swap(Program, ToOptimize);
 356   EmitProgressBytecode("tooptimize");
 357   setNewProgram(ToOptimize);      // Delete hacked module.
 358
 359   return false;
 360 }
 361