Miscompilation.cpp revision ca7409664273fed4b473127295af3af0836b3077
1//===- Miscompilation.cpp - Debug program miscompilations -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements optimizer and code generation miscompilation debugging 11// support. 12// 13//===----------------------------------------------------------------------===// 14 15#include "BugDriver.h" 16#include "ListReducer.h" 17#include "ToolRunner.h" 18#include "llvm/Constants.h" 19#include "llvm/DerivedTypes.h" 20#include "llvm/Instructions.h" 21#include "llvm/Linker.h" 22#include "llvm/Module.h" 23#include "llvm/Pass.h" 24#include "llvm/Analysis/Verifier.h" 25#include "llvm/Support/Mangler.h" 26#include "llvm/Transforms/Utils/Cloning.h" 27#include "llvm/Support/CommandLine.h" 28#include "llvm/Support/FileUtilities.h" 29#include "llvm/Config/config.h" // for HAVE_LINK_R 30using namespace llvm; 31 32namespace llvm { 33 extern cl::list<std::string> InputArgv; 34} 35 36namespace { 37 static llvm::cl::opt<bool> 38 DisableLoopExtraction("disable-loop-extraction", 39 cl::desc("Don't extract loops when searching for miscompilations"), 40 cl::init(false)); 41 static llvm::cl::opt<bool> 42 DisableBlockExtraction("disable-block-extraction", 43 cl::desc("Don't extract blocks when searching for miscompilations"), 44 cl::init(false)); 45 46 class ReduceMiscompilingPasses : public ListReducer<const PassInfo*> { 47 BugDriver &BD; 48 public: 49 ReduceMiscompilingPasses(BugDriver &bd) : BD(bd) {} 50 51 virtual TestResult doTest(std::vector<const PassInfo*> &Prefix, 52 std::vector<const PassInfo*> &Suffix); 53 }; 54} 55 56/// TestResult - After passes have been split into a test group and a control 57/// group, see if they still break the program. 58/// 59ReduceMiscompilingPasses::TestResult 60ReduceMiscompilingPasses::doTest(std::vector<const PassInfo*> &Prefix, 61 std::vector<const PassInfo*> &Suffix) { 62 // First, run the program with just the Suffix passes. If it is still broken 63 // with JUST the kept passes, discard the prefix passes. 64 outs() << "Checking to see if '" << getPassesString(Suffix) 65 << "' compiles correctly: "; 66 67 std::string BitcodeResult; 68 if (BD.runPasses(Suffix, BitcodeResult, false/*delete*/, true/*quiet*/)) { 69 errs() << " Error running this sequence of passes" 70 << " on the input program!\n"; 71 BD.setPassesToRun(Suffix); 72 BD.EmitProgressBitcode("pass-error", false); 73 exit(BD.debugOptimizerCrash()); 74 } 75 76 // Check to see if the finished program matches the reference output... 77 if (BD.diffProgram(BitcodeResult, "", true /*delete bitcode*/)) { 78 outs() << " nope.\n"; 79 if (Suffix.empty()) { 80 errs() << BD.getToolName() << ": I'm confused: the test fails when " 81 << "no passes are run, nondeterministic program?\n"; 82 exit(1); 83 } 84 return KeepSuffix; // Miscompilation detected! 85 } 86 outs() << " yup.\n"; // No miscompilation! 87 88 if (Prefix.empty()) return NoFailure; 89 90 // Next, see if the program is broken if we run the "prefix" passes first, 91 // then separately run the "kept" passes. 92 outs() << "Checking to see if '" << getPassesString(Prefix) 93 << "' compiles correctly: "; 94 95 // If it is not broken with the kept passes, it's possible that the prefix 96 // passes must be run before the kept passes to break it. If the program 97 // WORKS after the prefix passes, but then fails if running the prefix AND 98 // kept passes, we can update our bitcode file to include the result of the 99 // prefix passes, then discard the prefix passes. 100 // 101 if (BD.runPasses(Prefix, BitcodeResult, false/*delete*/, true/*quiet*/)) { 102 errs() << " Error running this sequence of passes" 103 << " on the input program!\n"; 104 BD.setPassesToRun(Prefix); 105 BD.EmitProgressBitcode("pass-error", false); 106 exit(BD.debugOptimizerCrash()); 107 } 108 109 // If the prefix maintains the predicate by itself, only keep the prefix! 110 if (BD.diffProgram(BitcodeResult)) { 111 outs() << " nope.\n"; 112 sys::Path(BitcodeResult).eraseFromDisk(); 113 return KeepPrefix; 114 } 115 outs() << " yup.\n"; // No miscompilation! 116 117 // Ok, so now we know that the prefix passes work, try running the suffix 118 // passes on the result of the prefix passes. 119 // 120 Module *PrefixOutput = ParseInputFile(BitcodeResult, BD.getContext()); 121 if (PrefixOutput == 0) { 122 errs() << BD.getToolName() << ": Error reading bitcode file '" 123 << BitcodeResult << "'!\n"; 124 exit(1); 125 } 126 sys::Path(BitcodeResult).eraseFromDisk(); // No longer need the file on disk 127 128 // Don't check if there are no passes in the suffix. 129 if (Suffix.empty()) 130 return NoFailure; 131 132 outs() << "Checking to see if '" << getPassesString(Suffix) 133 << "' passes compile correctly after the '" 134 << getPassesString(Prefix) << "' passes: "; 135 136 Module *OriginalInput = BD.swapProgramIn(PrefixOutput); 137 if (BD.runPasses(Suffix, BitcodeResult, false/*delete*/, true/*quiet*/)) { 138 errs() << " Error running this sequence of passes" 139 << " on the input program!\n"; 140 BD.setPassesToRun(Suffix); 141 BD.EmitProgressBitcode("pass-error", false); 142 exit(BD.debugOptimizerCrash()); 143 } 144 145 // Run the result... 146 if (BD.diffProgram(BitcodeResult, "", true/*delete bitcode*/)) { 147 outs() << " nope.\n"; 148 delete OriginalInput; // We pruned down the original input... 149 return KeepSuffix; 150 } 151 152 // Otherwise, we must not be running the bad pass anymore. 153 outs() << " yup.\n"; // No miscompilation! 154 delete BD.swapProgramIn(OriginalInput); // Restore orig program & free test 155 return NoFailure; 156} 157 158namespace { 159 class ReduceMiscompilingFunctions : public ListReducer<Function*> { 160 BugDriver &BD; 161 bool (*TestFn)(BugDriver &, Module *, Module *); 162 public: 163 ReduceMiscompilingFunctions(BugDriver &bd, 164 bool (*F)(BugDriver &, Module *, Module *)) 165 : BD(bd), TestFn(F) {} 166 167 virtual TestResult doTest(std::vector<Function*> &Prefix, 168 std::vector<Function*> &Suffix) { 169 if (!Suffix.empty() && TestFuncs(Suffix)) 170 return KeepSuffix; 171 if (!Prefix.empty() && TestFuncs(Prefix)) 172 return KeepPrefix; 173 return NoFailure; 174 } 175 176 bool TestFuncs(const std::vector<Function*> &Prefix); 177 }; 178} 179 180/// TestMergedProgram - Given two modules, link them together and run the 181/// program, checking to see if the program matches the diff. If the diff 182/// matches, return false, otherwise return true. If the DeleteInputs argument 183/// is set to true then this function deletes both input modules before it 184/// returns. 185/// 186static bool TestMergedProgram(BugDriver &BD, Module *M1, Module *M2, 187 bool DeleteInputs) { 188 // Link the two portions of the program back to together. 189 std::string ErrorMsg; 190 if (!DeleteInputs) { 191 M1 = CloneModule(M1); 192 M2 = CloneModule(M2); 193 } 194 if (Linker::LinkModules(M1, M2, &ErrorMsg)) { 195 errs() << BD.getToolName() << ": Error linking modules together:" 196 << ErrorMsg << '\n'; 197 exit(1); 198 } 199 delete M2; // We are done with this module. 200 201 Module *OldProgram = BD.swapProgramIn(M1); 202 203 // Execute the program. If it does not match the expected output, we must 204 // return true. 205 bool Broken = BD.diffProgram(); 206 207 // Delete the linked module & restore the original 208 BD.swapProgramIn(OldProgram); 209 delete M1; 210 return Broken; 211} 212 213/// TestFuncs - split functions in a Module into two groups: those that are 214/// under consideration for miscompilation vs. those that are not, and test 215/// accordingly. Each group of functions becomes a separate Module. 216/// 217bool ReduceMiscompilingFunctions::TestFuncs(const std::vector<Function*>&Funcs){ 218 // Test to see if the function is misoptimized if we ONLY run it on the 219 // functions listed in Funcs. 220 outs() << "Checking to see if the program is misoptimized when " 221 << (Funcs.size()==1 ? "this function is" : "these functions are") 222 << " run through the pass" 223 << (BD.getPassesToRun().size() == 1 ? "" : "es") << ":"; 224 PrintFunctionList(Funcs); 225 outs() << '\n'; 226 227 // Split the module into the two halves of the program we want. 228 DenseMap<const Value*, Value*> ValueMap; 229 Module *ToNotOptimize = CloneModule(BD.getProgram(), ValueMap); 230 Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, Funcs, 231 ValueMap); 232 233 // Run the predicate, note that the predicate will delete both input modules. 234 return TestFn(BD, ToOptimize, ToNotOptimize); 235} 236 237/// DisambiguateGlobalSymbols - Mangle symbols to guarantee uniqueness by 238/// modifying predominantly internal symbols rather than external ones. 239/// 240static void DisambiguateGlobalSymbols(Module *M) { 241 // Try not to cause collisions by minimizing chances of renaming an 242 // already-external symbol, so take in external globals and functions as-is. 243 // The code should work correctly without disambiguation (assuming the same 244 // mangler is used by the two code generators), but having symbols with the 245 // same name causes warnings to be emitted by the code generator. 246 Mangler Mang(*M); 247 // Agree with the CBE on symbol naming 248 Mang.markCharUnacceptable('.'); 249 for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 250 I != E; ++I) { 251 // Don't mangle asm names. 252 if (!I->hasName() || I->getName()[0] != 1) 253 I->setName(Mang.getMangledName(I)); 254 } 255 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) { 256 // Don't mangle asm names or intrinsics. 257 if ((!I->hasName() || I->getName()[0] != 1) && 258 I->getIntrinsicID() == 0) 259 I->setName(Mang.getMangledName(I)); 260 } 261} 262 263/// ExtractLoops - Given a reduced list of functions that still exposed the bug, 264/// check to see if we can extract the loops in the region without obscuring the 265/// bug. If so, it reduces the amount of code identified. 266/// 267static bool ExtractLoops(BugDriver &BD, 268 bool (*TestFn)(BugDriver &, Module *, Module *), 269 std::vector<Function*> &MiscompiledFunctions) { 270 bool MadeChange = false; 271 while (1) { 272 if (BugpointIsInterrupted) return MadeChange; 273 274 DenseMap<const Value*, Value*> ValueMap; 275 Module *ToNotOptimize = CloneModule(BD.getProgram(), ValueMap); 276 Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, 277 MiscompiledFunctions, 278 ValueMap); 279 Module *ToOptimizeLoopExtracted = BD.ExtractLoop(ToOptimize); 280 if (!ToOptimizeLoopExtracted) { 281 // If the loop extractor crashed or if there were no extractible loops, 282 // then this chapter of our odyssey is over with. 283 delete ToNotOptimize; 284 delete ToOptimize; 285 return MadeChange; 286 } 287 288 errs() << "Extracted a loop from the breaking portion of the program.\n"; 289 290 // Bugpoint is intentionally not very trusting of LLVM transformations. In 291 // particular, we're not going to assume that the loop extractor works, so 292 // we're going to test the newly loop extracted program to make sure nothing 293 // has broken. If something broke, then we'll inform the user and stop 294 // extraction. 295 AbstractInterpreter *AI = BD.switchToSafeInterpreter(); 296 if (TestMergedProgram(BD, ToOptimizeLoopExtracted, ToNotOptimize, false)) { 297 BD.switchToInterpreter(AI); 298 299 // Merged program doesn't work anymore! 300 errs() << " *** ERROR: Loop extraction broke the program. :(" 301 << " Please report a bug!\n"; 302 errs() << " Continuing on with un-loop-extracted version.\n"; 303 304 BD.writeProgramToFile("bugpoint-loop-extract-fail-tno.bc", ToNotOptimize); 305 BD.writeProgramToFile("bugpoint-loop-extract-fail-to.bc", ToOptimize); 306 BD.writeProgramToFile("bugpoint-loop-extract-fail-to-le.bc", 307 ToOptimizeLoopExtracted); 308 309 errs() << "Please submit the bugpoint-loop-extract-fail-*.bc files.\n"; 310 delete ToOptimize; 311 delete ToNotOptimize; 312 delete ToOptimizeLoopExtracted; 313 return MadeChange; 314 } 315 delete ToOptimize; 316 BD.switchToInterpreter(AI); 317 318 outs() << " Testing after loop extraction:\n"; 319 // Clone modules, the tester function will free them. 320 Module *TOLEBackup = CloneModule(ToOptimizeLoopExtracted); 321 Module *TNOBackup = CloneModule(ToNotOptimize); 322 if (!TestFn(BD, ToOptimizeLoopExtracted, ToNotOptimize)) { 323 outs() << "*** Loop extraction masked the problem. Undoing.\n"; 324 // If the program is not still broken, then loop extraction did something 325 // that masked the error. Stop loop extraction now. 326 delete TOLEBackup; 327 delete TNOBackup; 328 return MadeChange; 329 } 330 ToOptimizeLoopExtracted = TOLEBackup; 331 ToNotOptimize = TNOBackup; 332 333 outs() << "*** Loop extraction successful!\n"; 334 335 std::vector<std::pair<std::string, const FunctionType*> > MisCompFunctions; 336 for (Module::iterator I = ToOptimizeLoopExtracted->begin(), 337 E = ToOptimizeLoopExtracted->end(); I != E; ++I) 338 if (!I->isDeclaration()) 339 MisCompFunctions.push_back(std::make_pair(I->getName(), 340 I->getFunctionType())); 341 342 // Okay, great! Now we know that we extracted a loop and that loop 343 // extraction both didn't break the program, and didn't mask the problem. 344 // Replace the current program with the loop extracted version, and try to 345 // extract another loop. 346 std::string ErrorMsg; 347 if (Linker::LinkModules(ToNotOptimize, ToOptimizeLoopExtracted, &ErrorMsg)){ 348 errs() << BD.getToolName() << ": Error linking modules together:" 349 << ErrorMsg << '\n'; 350 exit(1); 351 } 352 delete ToOptimizeLoopExtracted; 353 354 // All of the Function*'s in the MiscompiledFunctions list are in the old 355 // module. Update this list to include all of the functions in the 356 // optimized and loop extracted module. 357 MiscompiledFunctions.clear(); 358 for (unsigned i = 0, e = MisCompFunctions.size(); i != e; ++i) { 359 Function *NewF = ToNotOptimize->getFunction(MisCompFunctions[i].first); 360 361 assert(NewF && "Function not found??"); 362 assert(NewF->getFunctionType() == MisCompFunctions[i].second && 363 "found wrong function type?"); 364 MiscompiledFunctions.push_back(NewF); 365 } 366 367 BD.setNewProgram(ToNotOptimize); 368 MadeChange = true; 369 } 370} 371 372namespace { 373 class ReduceMiscompiledBlocks : public ListReducer<BasicBlock*> { 374 BugDriver &BD; 375 bool (*TestFn)(BugDriver &, Module *, Module *); 376 std::vector<Function*> FunctionsBeingTested; 377 public: 378 ReduceMiscompiledBlocks(BugDriver &bd, 379 bool (*F)(BugDriver &, Module *, Module *), 380 const std::vector<Function*> &Fns) 381 : BD(bd), TestFn(F), FunctionsBeingTested(Fns) {} 382 383 virtual TestResult doTest(std::vector<BasicBlock*> &Prefix, 384 std::vector<BasicBlock*> &Suffix) { 385 if (!Suffix.empty() && TestFuncs(Suffix)) 386 return KeepSuffix; 387 if (TestFuncs(Prefix)) 388 return KeepPrefix; 389 return NoFailure; 390 } 391 392 bool TestFuncs(const std::vector<BasicBlock*> &Prefix); 393 }; 394} 395 396/// TestFuncs - Extract all blocks for the miscompiled functions except for the 397/// specified blocks. If the problem still exists, return true. 398/// 399bool ReduceMiscompiledBlocks::TestFuncs(const std::vector<BasicBlock*> &BBs) { 400 // Test to see if the function is misoptimized if we ONLY run it on the 401 // functions listed in Funcs. 402 outs() << "Checking to see if the program is misoptimized when all "; 403 if (!BBs.empty()) { 404 outs() << "but these " << BBs.size() << " blocks are extracted: "; 405 for (unsigned i = 0, e = BBs.size() < 10 ? BBs.size() : 10; i != e; ++i) 406 outs() << BBs[i]->getName() << " "; 407 if (BBs.size() > 10) outs() << "..."; 408 } else { 409 outs() << "blocks are extracted."; 410 } 411 outs() << '\n'; 412 413 // Split the module into the two halves of the program we want. 414 DenseMap<const Value*, Value*> ValueMap; 415 Module *ToNotOptimize = CloneModule(BD.getProgram(), ValueMap); 416 Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, 417 FunctionsBeingTested, 418 ValueMap); 419 420 // Try the extraction. If it doesn't work, then the block extractor crashed 421 // or something, in which case bugpoint can't chase down this possibility. 422 if (Module *New = BD.ExtractMappedBlocksFromModule(BBs, ToOptimize)) { 423 delete ToOptimize; 424 // Run the predicate, not that the predicate will delete both input modules. 425 return TestFn(BD, New, ToNotOptimize); 426 } 427 delete ToOptimize; 428 delete ToNotOptimize; 429 return false; 430} 431 432 433/// ExtractBlocks - Given a reduced list of functions that still expose the bug, 434/// extract as many basic blocks from the region as possible without obscuring 435/// the bug. 436/// 437static bool ExtractBlocks(BugDriver &BD, 438 bool (*TestFn)(BugDriver &, Module *, Module *), 439 std::vector<Function*> &MiscompiledFunctions) { 440 if (BugpointIsInterrupted) return false; 441 442 std::vector<BasicBlock*> Blocks; 443 for (unsigned i = 0, e = MiscompiledFunctions.size(); i != e; ++i) 444 for (Function::iterator I = MiscompiledFunctions[i]->begin(), 445 E = MiscompiledFunctions[i]->end(); I != E; ++I) 446 Blocks.push_back(I); 447 448 // Use the list reducer to identify blocks that can be extracted without 449 // obscuring the bug. The Blocks list will end up containing blocks that must 450 // be retained from the original program. 451 unsigned OldSize = Blocks.size(); 452 453 // Check to see if all blocks are extractible first. 454 if (ReduceMiscompiledBlocks(BD, TestFn, 455 MiscompiledFunctions).TestFuncs(std::vector<BasicBlock*>())) { 456 Blocks.clear(); 457 } else { 458 ReduceMiscompiledBlocks(BD, TestFn,MiscompiledFunctions).reduceList(Blocks); 459 if (Blocks.size() == OldSize) 460 return false; 461 } 462 463 DenseMap<const Value*, Value*> ValueMap; 464 Module *ProgClone = CloneModule(BD.getProgram(), ValueMap); 465 Module *ToExtract = SplitFunctionsOutOfModule(ProgClone, 466 MiscompiledFunctions, 467 ValueMap); 468 Module *Extracted = BD.ExtractMappedBlocksFromModule(Blocks, ToExtract); 469 if (Extracted == 0) { 470 // Weird, extraction should have worked. 471 errs() << "Nondeterministic problem extracting blocks??\n"; 472 delete ProgClone; 473 delete ToExtract; 474 return false; 475 } 476 477 // Otherwise, block extraction succeeded. Link the two program fragments back 478 // together. 479 delete ToExtract; 480 481 std::vector<std::pair<std::string, const FunctionType*> > MisCompFunctions; 482 for (Module::iterator I = Extracted->begin(), E = Extracted->end(); 483 I != E; ++I) 484 if (!I->isDeclaration()) 485 MisCompFunctions.push_back(std::make_pair(I->getName(), 486 I->getFunctionType())); 487 488 std::string ErrorMsg; 489 if (Linker::LinkModules(ProgClone, Extracted, &ErrorMsg)) { 490 errs() << BD.getToolName() << ": Error linking modules together:" 491 << ErrorMsg << '\n'; 492 exit(1); 493 } 494 delete Extracted; 495 496 // Set the new program and delete the old one. 497 BD.setNewProgram(ProgClone); 498 499 // Update the list of miscompiled functions. 500 MiscompiledFunctions.clear(); 501 502 for (unsigned i = 0, e = MisCompFunctions.size(); i != e; ++i) { 503 Function *NewF = ProgClone->getFunction(MisCompFunctions[i].first); 504 assert(NewF && "Function not found??"); 505 assert(NewF->getFunctionType() == MisCompFunctions[i].second && 506 "Function has wrong type??"); 507 MiscompiledFunctions.push_back(NewF); 508 } 509 510 return true; 511} 512 513 514/// DebugAMiscompilation - This is a generic driver to narrow down 515/// miscompilations, either in an optimization or a code generator. 516/// 517static std::vector<Function*> 518DebugAMiscompilation(BugDriver &BD, 519 bool (*TestFn)(BugDriver &, Module *, Module *)) { 520 // Okay, now that we have reduced the list of passes which are causing the 521 // failure, see if we can pin down which functions are being 522 // miscompiled... first build a list of all of the non-external functions in 523 // the program. 524 std::vector<Function*> MiscompiledFunctions; 525 Module *Prog = BD.getProgram(); 526 for (Module::iterator I = Prog->begin(), E = Prog->end(); I != E; ++I) 527 if (!I->isDeclaration()) 528 MiscompiledFunctions.push_back(I); 529 530 // Do the reduction... 531 if (!BugpointIsInterrupted) 532 ReduceMiscompilingFunctions(BD, TestFn).reduceList(MiscompiledFunctions); 533 534 outs() << "\n*** The following function" 535 << (MiscompiledFunctions.size() == 1 ? " is" : "s are") 536 << " being miscompiled: "; 537 PrintFunctionList(MiscompiledFunctions); 538 outs() << '\n'; 539 540 // See if we can rip any loops out of the miscompiled functions and still 541 // trigger the problem. 542 543 if (!BugpointIsInterrupted && !DisableLoopExtraction && 544 ExtractLoops(BD, TestFn, MiscompiledFunctions)) { 545 // Okay, we extracted some loops and the problem still appears. See if we 546 // can eliminate some of the created functions from being candidates. 547 548 // Loop extraction can introduce functions with the same name (foo_code). 549 // Make sure to disambiguate the symbols so that when the program is split 550 // apart that we can link it back together again. 551 DisambiguateGlobalSymbols(BD.getProgram()); 552 553 // Do the reduction... 554 if (!BugpointIsInterrupted) 555 ReduceMiscompilingFunctions(BD, TestFn).reduceList(MiscompiledFunctions); 556 557 outs() << "\n*** The following function" 558 << (MiscompiledFunctions.size() == 1 ? " is" : "s are") 559 << " being miscompiled: "; 560 PrintFunctionList(MiscompiledFunctions); 561 outs() << '\n'; 562 } 563 564 if (!BugpointIsInterrupted && !DisableBlockExtraction && 565 ExtractBlocks(BD, TestFn, MiscompiledFunctions)) { 566 // Okay, we extracted some blocks and the problem still appears. See if we 567 // can eliminate some of the created functions from being candidates. 568 569 // Block extraction can introduce functions with the same name (foo_code). 570 // Make sure to disambiguate the symbols so that when the program is split 571 // apart that we can link it back together again. 572 DisambiguateGlobalSymbols(BD.getProgram()); 573 574 // Do the reduction... 575 ReduceMiscompilingFunctions(BD, TestFn).reduceList(MiscompiledFunctions); 576 577 outs() << "\n*** The following function" 578 << (MiscompiledFunctions.size() == 1 ? " is" : "s are") 579 << " being miscompiled: "; 580 PrintFunctionList(MiscompiledFunctions); 581 outs() << '\n'; 582 } 583 584 return MiscompiledFunctions; 585} 586 587/// TestOptimizer - This is the predicate function used to check to see if the 588/// "Test" portion of the program is misoptimized. If so, return true. In any 589/// case, both module arguments are deleted. 590/// 591static bool TestOptimizer(BugDriver &BD, Module *Test, Module *Safe) { 592 // Run the optimization passes on ToOptimize, producing a transformed version 593 // of the functions being tested. 594 outs() << " Optimizing functions being tested: "; 595 Module *Optimized = BD.runPassesOn(Test, BD.getPassesToRun(), 596 /*AutoDebugCrashes*/true); 597 outs() << "done.\n"; 598 delete Test; 599 600 outs() << " Checking to see if the merged program executes correctly: "; 601 bool Broken = TestMergedProgram(BD, Optimized, Safe, true); 602 outs() << (Broken ? " nope.\n" : " yup.\n"); 603 return Broken; 604} 605 606 607/// debugMiscompilation - This method is used when the passes selected are not 608/// crashing, but the generated output is semantically different from the 609/// input. 610/// 611bool BugDriver::debugMiscompilation() { 612 // Make sure something was miscompiled... 613 if (!BugpointIsInterrupted) 614 if (!ReduceMiscompilingPasses(*this).reduceList(PassesToRun)) { 615 errs() << "*** Optimized program matches reference output! No problem" 616 << " detected...\nbugpoint can't help you with your problem!\n"; 617 return false; 618 } 619 620 outs() << "\n*** Found miscompiling pass" 621 << (getPassesToRun().size() == 1 ? "" : "es") << ": " 622 << getPassesString(getPassesToRun()) << '\n'; 623 EmitProgressBitcode("passinput"); 624 625 std::vector<Function*> MiscompiledFunctions = 626 DebugAMiscompilation(*this, TestOptimizer); 627 628 // Output a bunch of bitcode files for the user... 629 outs() << "Outputting reduced bitcode files which expose the problem:\n"; 630 DenseMap<const Value*, Value*> ValueMap; 631 Module *ToNotOptimize = CloneModule(getProgram(), ValueMap); 632 Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, 633 MiscompiledFunctions, 634 ValueMap); 635 636 outs() << " Non-optimized portion: "; 637 ToNotOptimize = swapProgramIn(ToNotOptimize); 638 EmitProgressBitcode("tonotoptimize", true); 639 setNewProgram(ToNotOptimize); // Delete hacked module. 640 641 outs() << " Portion that is input to optimizer: "; 642 ToOptimize = swapProgramIn(ToOptimize); 643 EmitProgressBitcode("tooptimize"); 644 setNewProgram(ToOptimize); // Delete hacked module. 645 646 return false; 647} 648 649/// CleanupAndPrepareModules - Get the specified modules ready for code 650/// generator testing. 651/// 652static void CleanupAndPrepareModules(BugDriver &BD, Module *&Test, 653 Module *Safe) { 654 // Clean up the modules, removing extra cruft that we don't need anymore... 655 Test = BD.performFinalCleanups(Test); 656 657 // If we are executing the JIT, we have several nasty issues to take care of. 658 if (!BD.isExecutingJIT()) return; 659 660 // First, if the main function is in the Safe module, we must add a stub to 661 // the Test module to call into it. Thus, we create a new function `main' 662 // which just calls the old one. 663 if (Function *oldMain = Safe->getFunction("main")) 664 if (!oldMain->isDeclaration()) { 665 // Rename it 666 oldMain->setName("llvm_bugpoint_old_main"); 667 // Create a NEW `main' function with same type in the test module. 668 Function *newMain = Function::Create(oldMain->getFunctionType(), 669 GlobalValue::ExternalLinkage, 670 "main", Test); 671 // Create an `oldmain' prototype in the test module, which will 672 // corresponds to the real main function in the same module. 673 Function *oldMainProto = Function::Create(oldMain->getFunctionType(), 674 GlobalValue::ExternalLinkage, 675 oldMain->getName(), Test); 676 // Set up and remember the argument list for the main function. 677 std::vector<Value*> args; 678 for (Function::arg_iterator 679 I = newMain->arg_begin(), E = newMain->arg_end(), 680 OI = oldMain->arg_begin(); I != E; ++I, ++OI) { 681 I->setName(OI->getName()); // Copy argument names from oldMain 682 args.push_back(I); 683 } 684 685 // Call the old main function and return its result 686 BasicBlock *BB = BasicBlock::Create(Safe->getContext(), "entry", newMain); 687 CallInst *call = CallInst::Create(oldMainProto, args.begin(), args.end(), 688 "", BB); 689 690 // If the type of old function wasn't void, return value of call 691 ReturnInst::Create(Safe->getContext(), call, BB); 692 } 693 694 // The second nasty issue we must deal with in the JIT is that the Safe 695 // module cannot directly reference any functions defined in the test 696 // module. Instead, we use a JIT API call to dynamically resolve the 697 // symbol. 698 699 // Add the resolver to the Safe module. 700 // Prototype: void *getPointerToNamedFunction(const char* Name) 701 Constant *resolverFunc = 702 Safe->getOrInsertFunction("getPointerToNamedFunction", 703 PointerType::getUnqual(Type::getInt8Ty(Safe->getContext())), 704 PointerType::getUnqual(Type::getInt8Ty(Safe->getContext())), 705 (Type *)0); 706 707 // Use the function we just added to get addresses of functions we need. 708 for (Module::iterator F = Safe->begin(), E = Safe->end(); F != E; ++F) { 709 if (F->isDeclaration() && !F->use_empty() && &*F != resolverFunc && 710 !F->isIntrinsic() /* ignore intrinsics */) { 711 Function *TestFn = Test->getFunction(F->getName()); 712 713 // Don't forward functions which are external in the test module too. 714 if (TestFn && !TestFn->isDeclaration()) { 715 // 1. Add a string constant with its name to the global file 716 Constant *InitArray = ConstantArray::get(F->getContext(), F->getName()); 717 GlobalVariable *funcName = 718 new GlobalVariable(*Safe, InitArray->getType(), true /*isConstant*/, 719 GlobalValue::InternalLinkage, InitArray, 720 F->getName() + "_name"); 721 722 // 2. Use `GetElementPtr *funcName, 0, 0' to convert the string to an 723 // sbyte* so it matches the signature of the resolver function. 724 725 // GetElementPtr *funcName, ulong 0, ulong 0 726 std::vector<Constant*> GEPargs(2, 727 Constant::getNullValue(Type::getInt32Ty(F->getContext()))); 728 Value *GEP = 729 ConstantExpr::getGetElementPtr(funcName, &GEPargs[0], 2); 730 std::vector<Value*> ResolverArgs; 731 ResolverArgs.push_back(GEP); 732 733 // Rewrite uses of F in global initializers, etc. to uses of a wrapper 734 // function that dynamically resolves the calls to F via our JIT API 735 if (!F->use_empty()) { 736 // Create a new global to hold the cached function pointer. 737 Constant *NullPtr = ConstantPointerNull::get(F->getType()); 738 GlobalVariable *Cache = 739 new GlobalVariable(*F->getParent(), F->getType(), 740 false, GlobalValue::InternalLinkage, 741 NullPtr,F->getName()+".fpcache"); 742 743 // Construct a new stub function that will re-route calls to F 744 const FunctionType *FuncTy = F->getFunctionType(); 745 Function *FuncWrapper = Function::Create(FuncTy, 746 GlobalValue::InternalLinkage, 747 F->getName() + "_wrapper", 748 F->getParent()); 749 BasicBlock *EntryBB = BasicBlock::Create(F->getContext(), 750 "entry", FuncWrapper); 751 BasicBlock *DoCallBB = BasicBlock::Create(F->getContext(), 752 "usecache", FuncWrapper); 753 BasicBlock *LookupBB = BasicBlock::Create(F->getContext(), 754 "lookupfp", FuncWrapper); 755 756 // Check to see if we already looked up the value. 757 Value *CachedVal = new LoadInst(Cache, "fpcache", EntryBB); 758 Value *IsNull = new ICmpInst(*EntryBB, ICmpInst::ICMP_EQ, CachedVal, 759 NullPtr, "isNull"); 760 BranchInst::Create(LookupBB, DoCallBB, IsNull, EntryBB); 761 762 // Resolve the call to function F via the JIT API: 763 // 764 // call resolver(GetElementPtr...) 765 CallInst *Resolver = 766 CallInst::Create(resolverFunc, ResolverArgs.begin(), 767 ResolverArgs.end(), "resolver", LookupBB); 768 769 // Cast the result from the resolver to correctly-typed function. 770 CastInst *CastedResolver = 771 new BitCastInst(Resolver, 772 PointerType::getUnqual(F->getFunctionType()), 773 "resolverCast", LookupBB); 774 775 // Save the value in our cache. 776 new StoreInst(CastedResolver, Cache, LookupBB); 777 BranchInst::Create(DoCallBB, LookupBB); 778 779 PHINode *FuncPtr = PHINode::Create(NullPtr->getType(), 780 "fp", DoCallBB); 781 FuncPtr->addIncoming(CastedResolver, LookupBB); 782 FuncPtr->addIncoming(CachedVal, EntryBB); 783 784 // Save the argument list. 785 std::vector<Value*> Args; 786 for (Function::arg_iterator i = FuncWrapper->arg_begin(), 787 e = FuncWrapper->arg_end(); i != e; ++i) 788 Args.push_back(i); 789 790 // Pass on the arguments to the real function, return its result 791 if (F->getReturnType() == Type::getVoidTy(F->getContext())) { 792 CallInst::Create(FuncPtr, Args.begin(), Args.end(), "", DoCallBB); 793 ReturnInst::Create(F->getContext(), DoCallBB); 794 } else { 795 CallInst *Call = CallInst::Create(FuncPtr, Args.begin(), Args.end(), 796 "retval", DoCallBB); 797 ReturnInst::Create(F->getContext(),Call, DoCallBB); 798 } 799 800 // Use the wrapper function instead of the old function 801 F->replaceAllUsesWith(FuncWrapper); 802 } 803 } 804 } 805 } 806 807 if (verifyModule(*Test) || verifyModule(*Safe)) { 808 errs() << "Bugpoint has a bug, which corrupted a module!!\n"; 809 abort(); 810 } 811} 812 813 814 815/// TestCodeGenerator - This is the predicate function used to check to see if 816/// the "Test" portion of the program is miscompiled by the code generator under 817/// test. If so, return true. In any case, both module arguments are deleted. 818/// 819static bool TestCodeGenerator(BugDriver &BD, Module *Test, Module *Safe) { 820 CleanupAndPrepareModules(BD, Test, Safe); 821 822 sys::Path TestModuleBC("bugpoint.test.bc"); 823 std::string ErrMsg; 824 if (TestModuleBC.makeUnique(true, &ErrMsg)) { 825 errs() << BD.getToolName() << "Error making unique filename: " 826 << ErrMsg << "\n"; 827 exit(1); 828 } 829 if (BD.writeProgramToFile(TestModuleBC.toString(), Test)) { 830 errs() << "Error writing bitcode to `" << TestModuleBC << "'\nExiting."; 831 exit(1); 832 } 833 delete Test; 834 835 // Make the shared library 836 sys::Path SafeModuleBC("bugpoint.safe.bc"); 837 if (SafeModuleBC.makeUnique(true, &ErrMsg)) { 838 errs() << BD.getToolName() << "Error making unique filename: " 839 << ErrMsg << "\n"; 840 exit(1); 841 } 842 843 if (BD.writeProgramToFile(SafeModuleBC.toString(), Safe)) { 844 errs() << "Error writing bitcode to `" << SafeModuleBC << "'\nExiting."; 845 exit(1); 846 } 847 std::string SharedObject = BD.compileSharedObject(SafeModuleBC.toString()); 848 delete Safe; 849 850 // Run the code generator on the `Test' code, loading the shared library. 851 // The function returns whether or not the new output differs from reference. 852 int Result = BD.diffProgram(TestModuleBC.toString(), SharedObject, false); 853 854 if (Result) 855 errs() << ": still failing!\n"; 856 else 857 errs() << ": didn't fail.\n"; 858 TestModuleBC.eraseFromDisk(); 859 SafeModuleBC.eraseFromDisk(); 860 sys::Path(SharedObject).eraseFromDisk(); 861 862 return Result; 863} 864 865 866/// debugCodeGenerator - debug errors in LLC, LLI, or CBE. 867/// 868bool BugDriver::debugCodeGenerator() { 869 if ((void*)SafeInterpreter == (void*)Interpreter) { 870 std::string Result = executeProgramSafely("bugpoint.safe.out"); 871 outs() << "\n*** The \"safe\" i.e. 'known good' backend cannot match " 872 << "the reference diff. This may be due to a\n front-end " 873 << "bug or a bug in the original program, but this can also " 874 << "happen if bugpoint isn't running the program with the " 875 << "right flags or input.\n I left the result of executing " 876 << "the program with the \"safe\" backend in this file for " 877 << "you: '" 878 << Result << "'.\n"; 879 return true; 880 } 881 882 DisambiguateGlobalSymbols(Program); 883 884 std::vector<Function*> Funcs = DebugAMiscompilation(*this, TestCodeGenerator); 885 886 // Split the module into the two halves of the program we want. 887 DenseMap<const Value*, Value*> ValueMap; 888 Module *ToNotCodeGen = CloneModule(getProgram(), ValueMap); 889 Module *ToCodeGen = SplitFunctionsOutOfModule(ToNotCodeGen, Funcs, ValueMap); 890 891 // Condition the modules 892 CleanupAndPrepareModules(*this, ToCodeGen, ToNotCodeGen); 893 894 sys::Path TestModuleBC("bugpoint.test.bc"); 895 std::string ErrMsg; 896 if (TestModuleBC.makeUnique(true, &ErrMsg)) { 897 errs() << getToolName() << "Error making unique filename: " 898 << ErrMsg << "\n"; 899 exit(1); 900 } 901 902 if (writeProgramToFile(TestModuleBC.toString(), ToCodeGen)) { 903 errs() << "Error writing bitcode to `" << TestModuleBC << "'\nExiting."; 904 exit(1); 905 } 906 delete ToCodeGen; 907 908 // Make the shared library 909 sys::Path SafeModuleBC("bugpoint.safe.bc"); 910 if (SafeModuleBC.makeUnique(true, &ErrMsg)) { 911 errs() << getToolName() << "Error making unique filename: " 912 << ErrMsg << "\n"; 913 exit(1); 914 } 915 916 if (writeProgramToFile(SafeModuleBC.toString(), ToNotCodeGen)) { 917 errs() << "Error writing bitcode to `" << SafeModuleBC << "'\nExiting."; 918 exit(1); 919 } 920 std::string SharedObject = compileSharedObject(SafeModuleBC.toString()); 921 delete ToNotCodeGen; 922 923 outs() << "You can reproduce the problem with the command line: \n"; 924 if (isExecutingJIT()) { 925 outs() << " lli -load " << SharedObject << " " << TestModuleBC; 926 } else { 927 outs() << " llc -f " << TestModuleBC << " -o " << TestModuleBC<< ".s\n"; 928 outs() << " gcc " << SharedObject << " " << TestModuleBC 929 << ".s -o " << TestModuleBC << ".exe"; 930#if defined (HAVE_LINK_R) 931 outs() << " -Wl,-R."; 932#endif 933 outs() << "\n"; 934 outs() << " " << TestModuleBC << ".exe"; 935 } 936 for (unsigned i=0, e = InputArgv.size(); i != e; ++i) 937 outs() << " " << InputArgv[i]; 938 outs() << '\n'; 939 outs() << "The shared object was created with:\n llc -march=c " 940 << SafeModuleBC << " -o temporary.c\n" 941 << " gcc -xc temporary.c -O2 -o " << SharedObject; 942 if (TargetTriple.getArch() == Triple::sparc) 943 outs() << " -G"; // Compile a shared library, `-G' for Sparc 944 else 945 outs() << " -fPIC -shared"; // `-shared' for Linux/X86, maybe others 946 947 outs() << " -fno-strict-aliasing\n"; 948 949 return false; 950} 951