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, false))
 136         return KeepSuffix;
 137       if (!Prefix.empty() && TestFuncs(Prefix, false))
 138         return KeepPrefix;
 139       return NoFailure;
 140     }
 141
 142     bool TestFuncs(const std::vector<Function*> &Prefix, bool EmitBytecode);
 143   };
 144 }
 145
 146 bool ReduceMiscompilingFunctions::TestFuncs(const std::vector<Function*> &Funcs,
 147                                             bool EmitBytecode) {
 148   // Test to see if the function is misoptimized if we ONLY run it on the
 149   // functions listed in Funcs.
 150   if (!EmitBytecode) {
 151     std::cout << "Checking to see if the program is misoptimized when "
 152               << (Funcs.size()==1 ? "this function is" : "these functions are")
 153               << " run through the pass"
 154               << (BD.PassesToRun.size() == 1 ? "" : "es") << ": ";
 155     BD.PrintFunctionList(Funcs);
 156     std::cout << "\n";
 157   } else {
 158     std::cout <<"Outputting reduced bytecode files which expose the problem:\n";
 159   }
 160
 161   // First step: clone the module for the two halves of the program we want.
 162   Module *ToOptimize = CloneModule(BD.Program);
 163
 164   // Second step: Make sure functions & globals are all external so that linkage
 165   // between the two modules will work.
 166   for (Module::iterator I = ToOptimize->begin(), E = ToOptimize->end();I!=E;++I)
 167     I->setLinkage(GlobalValue::ExternalLinkage);
 168   for (Module::giterator I = ToOptimize->gbegin(), E = ToOptimize->gend();
 169        I != E; ++I)
 170     I->setLinkage(GlobalValue::ExternalLinkage);
 171
 172   // Third step: make a clone of the externalized program for the non-optimized
 173   // part.
 174   Module *ToNotOptimize = CloneModule(ToOptimize);
 175
 176   // Fourth step: Remove the test functions from the ToNotOptimize module, and
 177   // all of the global variables.
 178   for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
 179     Function *TNOF = ToNotOptimize->getFunction(Funcs[i]->getName(),
 180                                                 Funcs[i]->getFunctionType());
 181     assert(TNOF && "Function doesn't exist in module!");
 182     DeleteFunctionBody(TNOF);       // Function is now external in this module!
 183   }
 184   for (Module::giterator I = ToNotOptimize->gbegin(), E = ToNotOptimize->gend();
 185        I != E; ++I)
 186     I->setInitializer(0);  // Delete the initializer to make it external
 187
 188   if (EmitBytecode) {
 189     std::cout << "  Non-optimized portion: ";
 190     std::swap(BD.Program, ToNotOptimize);
 191     BD.EmitProgressBytecode("tonotoptimize", true);
 192     std::swap(BD.Program, ToNotOptimize);
 193   }
 194
 195   // Fifth step: Remove all functions from the ToOptimize module EXCEPT for the
 196   // ones specified in Funcs.  We know which ones these are because they are
 197   // non-external in ToOptimize, but external in ToNotOptimize.
 198   //
 199   for (Module::iterator I = ToOptimize->begin(), E = ToOptimize->end();I!=E;++I)
 200     if (!I->isExternal()) {
 201       Function *TNOF = ToNotOptimize->getFunction(I->getName(),
 202                                                   I->getFunctionType());
 203       assert(TNOF && "Function doesn't exist in ToNotOptimize module??");
 204       if (!TNOF->isExternal())
 205         DeleteFunctionBody(I);
 206     }
 207
 208   if (EmitBytecode) {
 209     std::cout << "  Portion that is input to optimizer: ";
 210     std::swap(BD.Program, ToOptimize);
 211     BD.EmitProgressBytecode("tooptimize");
 212     std::swap(BD.Program, ToOptimize);
 213   }
 214
 215   // Sixth step: Run the optimization passes on ToOptimize, producing a
 216   // transformed version of the functions being tested.
 217   Module *OldProgram = BD.Program;
 218   BD.Program = ToOptimize;
 219
 220   if (!EmitBytecode)
 221     std::cout << "  Optimizing functions being tested: ";
 222   std::string BytecodeResult;
 223   if (BD.runPasses(BD.PassesToRun, BytecodeResult, false/*delete*/,
 224                    true/*quiet*/)) {
 225     std::cerr << " Error running this sequence of passes"
 226               << " on the input program!\n";
 227     BD.EmitProgressBytecode("pass-error",  false);
 228     exit(BD.debugOptimizerCrash());
 229   }
 230
 231   if (!EmitBytecode)
 232     std::cout << "done.\n";
 233
 234   delete BD.Program;   // Delete the old "ToOptimize" module
 235   BD.Program = BD.ParseInputFile(BytecodeResult);
 236
 237   if (EmitBytecode) {
 238     std::cout << "  'tooptimize' after being optimized: ";
 239     BD.EmitProgressBytecode("optimized", true);
 240   }
 241
 242   if (BD.Program == 0) {
 243     std::cerr << BD.getToolName() << ": Error reading bytecode file '"
 244               << BytecodeResult << "'!\n";
 245     exit(1);
 246   }
 247   removeFile(BytecodeResult);  // No longer need the file on disk
 248
 249   // Seventh step: Link the optimized part of the program back to the
 250   // unoptimized part of the program.
 251   //
 252   if (LinkModules(BD.Program, ToNotOptimize, &BytecodeResult)) {
 253     std::cerr << BD.getToolName() << ": Error linking modules together:"
 254               << BytecodeResult << "\n";
 255     exit(1);
 256   }
 257   delete ToNotOptimize;  // We are done with this module...
 258
 259   if (EmitBytecode) {
 260     std::cout << "  Program as tested: ";
 261     BD.EmitProgressBytecode("linked", true);
 262     delete BD.Program;
 263     BD.Program = OldProgram;
 264     return false;   // We don't need to actually execute the program here.
 265   }
 266
 267   std::cout << "  Checking to see if the merged program executes correctly: ";
 268
 269   // Eighth step: Execute the program.  If it does not match the expected
 270   // output, then 'Funcs' are being misoptimized!
 271   bool Broken = BD.diffProgram();
 272
 273   delete BD.Program;  // Delete the hacked up program
 274   BD.Program = OldProgram;   // Restore the original
 275
 276   std::cout << (Broken ? " nope.\n" : " yup.\n");
 277   return Broken;
 278 }
 279
 280
 281 /// debugMiscompilation - This method is used when the passes selected are not
 282 /// crashing, but the generated output is semantically different from the
 283 /// input.
 284 ///
 285 bool BugDriver::debugMiscompilation() {
 286   // Make sure something was miscompiled...
 287   if (!ReduceMiscompilingPasses(*this).reduceList(PassesToRun)) {
 288     std::cerr << "*** Optimized program matches reference output!  No problem "
 289               << "detected...\nbugpoint can't help you with your problem!\n";
 290     return false;
 291   }
 292
 293   std::cout << "\n*** Found miscompiling pass"
 294             << (PassesToRun.size() == 1 ? "" : "es") << ": "
 295             << getPassesString(PassesToRun) << "\n";
 296   EmitProgressBytecode("passinput");
 297
 298   // Okay, now that we have reduced the list of passes which are causing the
 299   // failure, see if we can pin down which functions are being
 300   // miscompiled... first build a list of all of the non-external functions in
 301   // the program.
 302   std::vector<Function*> MiscompiledFunctions;
 303   for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I)
 304     if (!I->isExternal())
 305       MiscompiledFunctions.push_back(I);
 306
 307   // Do the reduction...
 308   ReduceMiscompilingFunctions(*this).reduceList(MiscompiledFunctions);
 309
 310   std::cout << "\n*** The following function"
 311             << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
 312             << " being miscompiled: ";
 313   PrintFunctionList(MiscompiledFunctions);
 314   std::cout << "\n";
 315
 316   // Output a bunch of bytecode files for the user...
 317   ReduceMiscompilingFunctions(*this).TestFuncs(MiscompiledFunctions, true);
 318
 319   return false;
 320 }
 321