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