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