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