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