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