Miscompilation.cpp revision d3a533d94dae1e57194001af08763eb3ba199c8f
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 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. 148static 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 if (DeleteInputs) delete M1; 169 return Broken; 170} 171 172bool 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. 204static 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 delete ToOptimizeLoopExtracted; 271 272 // All of the Function*'s in the MiscompiledFunctions list are in the old 273 // module. Make sure to update them to point to the corresponding functions 274 // in the new module. 275 for (unsigned i = 0, e = MiscompiledFunctions.size(); i != e; ++i) { 276 Function *OldF = MiscompiledFunctions[i]; 277 Function *NewF = 278 ToNotOptimize->getFunction(OldF->getName(), OldF->getFunctionType()); 279 MiscompiledFunctions[i] = NewF; 280 } 281 282 BD.setNewProgram(ToNotOptimize); 283 MadeChange = true; 284 } 285} 286 287/// debugMiscompilation - This method is used when the passes selected are not 288/// crashing, but the generated output is semantically different from the 289/// input. 290/// 291bool BugDriver::debugMiscompilation() { 292 // Make sure something was miscompiled... 293 if (!ReduceMiscompilingPasses(*this).reduceList(PassesToRun)) { 294 std::cerr << "*** Optimized program matches reference output! No problem " 295 << "detected...\nbugpoint can't help you with your problem!\n"; 296 return false; 297 } 298 299 std::cout << "\n*** Found miscompiling pass" 300 << (getPassesToRun().size() == 1 ? "" : "es") << ": " 301 << getPassesString(getPassesToRun()) << "\n"; 302 EmitProgressBytecode("passinput"); 303 304 // Okay, now that we have reduced the list of passes which are causing the 305 // failure, see if we can pin down which functions are being 306 // miscompiled... first build a list of all of the non-external functions in 307 // the program. 308 std::vector<Function*> MiscompiledFunctions; 309 for (Module::iterator I = Program->begin(), E = Program->end(); I != E; ++I) 310 if (!I->isExternal()) 311 MiscompiledFunctions.push_back(I); 312 313 // Do the reduction... 314 ReduceMiscompilingFunctions(*this).reduceList(MiscompiledFunctions); 315 316 std::cout << "\n*** The following function" 317 << (MiscompiledFunctions.size() == 1 ? " is" : "s are") 318 << " being miscompiled: "; 319 PrintFunctionList(MiscompiledFunctions); 320 std::cout << "\n"; 321 322 // See if we can rip any loops out of the miscompiled functions and still 323 // trigger the problem. 324 if (ExtractLoops(*this, MiscompiledFunctions)) { 325 // Okay, we extracted some loops and the problem still appears. See if we 326 // can eliminate some of the created functions from being candidates. 327 328 // Do the reduction... 329 ReduceMiscompilingFunctions(*this).reduceList(MiscompiledFunctions); 330 331 std::cout << "\n*** The following function" 332 << (MiscompiledFunctions.size() == 1 ? " is" : "s are") 333 << " being miscompiled: "; 334 PrintFunctionList(MiscompiledFunctions); 335 std::cout << "\n"; 336 } 337 338 // Output a bunch of bytecode files for the user... 339 std::cout << "Outputting reduced bytecode files which expose the problem:\n"; 340 Module *ToNotOptimize = CloneModule(getProgram()); 341 Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, 342 MiscompiledFunctions); 343 344 std::cout << " Non-optimized portion: "; 345 std::swap(Program, ToNotOptimize); 346 EmitProgressBytecode("tonotoptimize", true); 347 setNewProgram(ToNotOptimize); // Delete hacked module. 348 349 std::cout << " Portion that is input to optimizer: "; 350 std::swap(Program, ToOptimize); 351 EmitProgressBytecode("tooptimize"); 352 setNewProgram(ToOptimize); // Delete hacked module. 353 354 return false; 355} 356 357