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