Miscompilation.cpp revision b15825b0a29e527b361b63a6e41aff5fdb8fdd5a
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" 21using namespace llvm; 22 23namespace { 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 34ReduceMiscompilingPasses::TestResult 35ReduceMiscompilingPasses::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 124namespace { 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. 151static 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 175bool 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. 196static 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. 281static std::vector<Function*> 282DebugAMiscompilation(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 322static 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/// 342bool 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 377