Miscompilation.cpp revision 9c6cfe1bffd37f29a265457b7515839c445b3e6a
1//===- Miscompilation.cpp - Debug program miscompilations -----------------===// 2// 3// This file implements program miscompilation debugging support. 4// 5//===----------------------------------------------------------------------===// 6 7#include "BugDriver.h" 8#include "ListReducer.h" 9#include "llvm/Module.h" 10#include "llvm/Pass.h" 11#include "llvm/Transforms/Utils/Cloning.h" 12#include "llvm/Transforms/Utils/Linker.h" 13#include "Support/FileUtilities.h" 14 15class ReduceMiscompilingPasses : public ListReducer<const PassInfo*> { 16 BugDriver &BD; 17public: 18 ReduceMiscompilingPasses(BugDriver &bd) : BD(bd) {} 19 20 virtual TestResult doTest(std::vector<const PassInfo*> &Prefix, 21 std::vector<const PassInfo*> &Suffix); 22}; 23 24ReduceMiscompilingPasses::TestResult 25ReduceMiscompilingPasses::doTest(std::vector<const PassInfo*> &Prefix, 26 std::vector<const PassInfo*> &Suffix) { 27 // First, run the program with just the Suffix passes. If it is still broken 28 // with JUST the kept passes, discard the prefix passes. 29 std::cout << "Checking to see if '" << getPassesString(Suffix) 30 << "' compile correctly: "; 31 32 std::string BytecodeResult; 33 if (BD.runPasses(Suffix, BytecodeResult, false/*delete*/, true/*quiet*/)) { 34 std::cerr << BD.getToolName() << ": Error running this sequence of passes" 35 << " on the input program!\n"; 36 exit(1); 37 } 38 39 // Check to see if the finished program matches the reference output... 40 if (BD.diffProgram(BytecodeResult, "", true /*delete bytecode*/)) { 41 std::cout << "nope.\n"; 42 return KeepSuffix; // Miscompilation detected! 43 } 44 std::cout << "yup.\n"; // No miscompilation! 45 46 if (Prefix.empty()) return NoFailure; 47 48 // Next, see if the program is broken if we run the "prefix" passes first, 49 // then separately run the "kept" passes. 50 std::cout << "Checking to see if '" << getPassesString(Prefix) 51 << "' compile correctly: "; 52 53 // If it is not broken with the kept passes, it's possible that the prefix 54 // passes must be run before the kept passes to break it. If the program 55 // WORKS after the prefix passes, but then fails if running the prefix AND 56 // kept passes, we can update our bytecode file to include the result of the 57 // prefix passes, then discard the prefix passes. 58 // 59 if (BD.runPasses(Prefix, BytecodeResult, false/*delete*/, true/*quiet*/)) { 60 std::cerr << ": Error running this sequence of passes" 61 << " on the input program!\n"; 62 BD.setPassesToRun(Prefix); 63 BD.EmitProgressBytecode("pass-error", false); 64 exit(1); 65 } 66 67 // If the prefix maintains the predicate by itself, only keep the prefix! 68 if (BD.diffProgram(BytecodeResult)) { 69 std::cout << "nope.\n"; 70 removeFile(BytecodeResult); 71 return KeepPrefix; 72 } 73 std::cout << "yup.\n"; // No miscompilation! 74 75 // Ok, so now we know that the prefix passes work, try running the suffix 76 // passes on the result of the prefix passes. 77 // 78 Module *PrefixOutput = BD.ParseInputFile(BytecodeResult); 79 if (PrefixOutput == 0) { 80 std::cerr << BD.getToolName() << ": Error reading bytecode file '" 81 << BytecodeResult << "'!\n"; 82 exit(1); 83 } 84 removeFile(BytecodeResult); // No longer need the file on disk 85 86 std::cout << "Checking to see if '" << getPassesString(Suffix) 87 << "' passes compile correctly after the '" 88 << getPassesString(Prefix) << "' passes: "; 89 90 Module *OriginalInput = BD.Program; 91 BD.Program = PrefixOutput; 92 if (BD.runPasses(Suffix, BytecodeResult, false/*delete*/, true/*quiet*/)) { 93 std::cerr << ": Error running this sequence of passes" 94 << " on the input program!\n"; 95 BD.setPassesToRun(Prefix); 96 BD.EmitProgressBytecode("pass-error", false); 97 exit(1); 98 } 99 100 // Run the result... 101 if (BD.diffProgram(BytecodeResult, "", true/*delete bytecode*/)) { 102 std::cout << "nope.\n"; 103 delete OriginalInput; // We pruned down the original input... 104 return KeepSuffix; 105 } 106 107 // Otherwise, we must not be running the bad pass anymore. 108 std::cout << "yup.\n"; // No miscompilation! 109 BD.Program = OriginalInput; // Restore original program 110 delete PrefixOutput; // Free experiment 111 return NoFailure; 112} 113 114class ReduceMiscompilingFunctions : public ListReducer<Function*> { 115 BugDriver &BD; 116public: 117 ReduceMiscompilingFunctions(BugDriver &bd) : BD(bd) {} 118 119 virtual TestResult doTest(std::vector<Function*> &Prefix, 120 std::vector<Function*> &Suffix) { 121 if (!Suffix.empty() && TestFuncs(Suffix, false)) 122 return KeepSuffix; 123 if (!Prefix.empty() && TestFuncs(Prefix, false)) 124 return KeepPrefix; 125 return NoFailure; 126 } 127 128 bool TestFuncs(const std::vector<Function*> &Prefix, bool EmitBytecode); 129}; 130 131bool ReduceMiscompilingFunctions::TestFuncs(const std::vector<Function*> &Funcs, 132 bool EmitBytecode) { 133 // Test to see if the function is misoptimized if we ONLY run it on the 134 // functions listed in Funcs. 135 if (!EmitBytecode) { 136 std::cout << "Checking to see if the program is misoptimized when these " 137 << "functions are run\nthrough the passes: "; 138 BD.PrintFunctionList(Funcs); 139 std::cout << "\n"; 140 } else { 141 std::cout <<"Outputting reduced bytecode files which expose the problem:\n"; 142 } 143 144 // First step: clone the module for the two halves of the program we want. 145 Module *ToOptimize = CloneModule(BD.Program); 146 147 // Second step: Make sure functions & globals are all external so that linkage 148 // between the two modules will work. 149 for (Module::iterator I = ToOptimize->begin(), E = ToOptimize->end();I!=E;++I) 150 I->setLinkage(GlobalValue::ExternalLinkage); 151 for (Module::giterator I = ToOptimize->gbegin(), E = ToOptimize->gend(); 152 I != E; ++I) 153 I->setLinkage(GlobalValue::ExternalLinkage); 154 155 // Third step: make a clone of the externalized program for the non-optimized 156 // part. 157 Module *ToNotOptimize = CloneModule(ToOptimize); 158 159 // Fourth step: Remove the test functions from the ToNotOptimize module, and 160 // all of the global variables. 161 for (unsigned i = 0, e = Funcs.size(); i != e; ++i) { 162 Function *TNOF = ToNotOptimize->getFunction(Funcs[i]->getName(), 163 Funcs[i]->getFunctionType()); 164 assert(TNOF && "Function doesn't exist in module!"); 165 DeleteFunctionBody(TNOF); // Function is now external in this module! 166 } 167 for (Module::giterator I = ToNotOptimize->gbegin(), E = ToNotOptimize->gend(); 168 I != E; ++I) 169 I->setInitializer(0); // Delete the initializer to make it external 170 171 if (EmitBytecode) { 172 std::cout << " Non-optimized portion: "; 173 std::swap(BD.Program, ToNotOptimize); 174 BD.EmitProgressBytecode("tonotoptimize", true); 175 std::swap(BD.Program, ToNotOptimize); 176 } 177 178 // Fifth step: Remove all functions from the ToOptimize module EXCEPT for the 179 // ones specified in Funcs. We know which ones these are because they are 180 // non-external in ToOptimize, but external in ToNotOptimize. 181 // 182 for (Module::iterator I = ToOptimize->begin(), E = ToOptimize->end();I!=E;++I) 183 if (!I->isExternal()) { 184 Function *TNOF = ToNotOptimize->getFunction(I->getName(), 185 I->getFunctionType()); 186 assert(TNOF && "Function doesn't exist in ToNotOptimize module??"); 187 if (!TNOF->isExternal()) 188 DeleteFunctionBody(I); 189 } 190 191 if (EmitBytecode) { 192 std::cout << " Portion that is input to optimizer: "; 193 std::swap(BD.Program, ToOptimize); 194 BD.EmitProgressBytecode("tooptimize"); 195 std::swap(BD.Program, ToOptimize); 196 } 197 198 // Sixth step: Run the optimization passes on ToOptimize, producing a 199 // transformed version of the functions being tested. 200 Module *OldProgram = BD.Program; 201 BD.Program = ToOptimize; 202 203 if (!EmitBytecode) 204 std::cout << " Optimizing functions being tested: "; 205 std::string BytecodeResult; 206 if (BD.runPasses(BD.PassesToRun, BytecodeResult, false/*delete*/, 207 true/*quiet*/)) { 208 std::cerr << BD.getToolName() << ": Error running this sequence of passes" 209 << " on the input program!\n"; 210 exit(1); 211 } 212 213 if (!EmitBytecode) 214 std::cout << "done.\n"; 215 216 delete BD.Program; // Delete the old "ToOptimize" module 217 BD.Program = BD.ParseInputFile(BytecodeResult); 218 219 if (EmitBytecode) { 220 std::cout << " 'tooptimize' after being optimized: "; 221 BD.EmitProgressBytecode("optimized", true); 222 } 223 224 if (BD.Program == 0) { 225 std::cerr << BD.getToolName() << ": Error reading bytecode file '" 226 << BytecodeResult << "'!\n"; 227 exit(1); 228 } 229 removeFile(BytecodeResult); // No longer need the file on disk 230 231 // Seventh step: Link the optimized part of the program back to the 232 // unoptimized part of the program. 233 // 234 if (LinkModules(BD.Program, ToNotOptimize, &BytecodeResult)) { 235 std::cerr << BD.getToolName() << ": Error linking modules together:" 236 << BytecodeResult << "\n"; 237 exit(1); 238 } 239 delete ToNotOptimize; // We are done with this module... 240 241 if (EmitBytecode) { 242 std::cout << " Program as tested: "; 243 BD.EmitProgressBytecode("linked", true); 244 delete BD.Program; 245 BD.Program = OldProgram; 246 return false; // We don't need to actually execute the program here. 247 } 248 249 std::cout << " Checking to see if the merged program executes correctly: "; 250 251 // Eighth step: Execute the program. If it does not match the expected 252 // output, then 'Funcs' are being misoptimized! 253 bool Broken = BD.diffProgram(); 254 255 delete BD.Program; // Delete the hacked up program 256 BD.Program = OldProgram; // Restore the original 257 258 std::cout << (Broken ? "nope.\n" : "yup.\n"); 259 return Broken; 260} 261 262 263/// debugMiscompilation - This method is used when the passes selected are not 264/// crashing, but the generated output is semantically different from the 265/// input. 266/// 267bool BugDriver::debugMiscompilation() { 268 // Make sure something was miscompiled... 269 if (!ReduceMiscompilingPasses(*this).reduceList(PassesToRun)) { 270 std::cerr << "*** Optimized program matches reference output! No problem " 271 << "detected...\nbugpoint can't help you with your problem!\n"; 272 return false; 273 } 274 275 std::cout << "\n*** Found miscompiling pass" 276 << (PassesToRun.size() == 1 ? "" : "es") << ": " 277 << getPassesString(PassesToRun) << "\n"; 278 EmitProgressBytecode("passinput"); 279 280 // Okay, now that we have reduced the list of passes which are causing the 281 // failure, see if we can pin down which functions are being 282 // miscompiled... first build a list of all of the non-external functions in 283 // the program. 284 std::vector<Function*> MiscompiledFunctions; 285 for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) 286 if (!I->isExternal()) 287 MiscompiledFunctions.push_back(I); 288 289 // Do the reduction... 290 ReduceMiscompilingFunctions(*this).reduceList(MiscompiledFunctions); 291 292 std::cout << "\n*** The following functions are being miscompiled: "; 293 PrintFunctionList(MiscompiledFunctions); 294 std::cout << "\n"; 295 296 // Output a bunch of bytecode files for the user... 297 ReduceMiscompilingFunctions(*this).TestFuncs(MiscompiledFunctions, true); 298 299 return false; 300} 301