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