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