//===- Miscompilation.cpp - Debug program miscompilations -----------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
//
// This file implements program miscompilation debugging support.
//
//===----------------------------------------------------------------------===//
#include "BugDriver.h"
-#include "SystemUtils.h"
#include "ListReducer.h"
-#include "llvm/Pass.h"
#include "llvm/Module.h"
+#include "llvm/Pass.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Linker.h"
-
-class ReduceMiscompilingPasses : public ListReducer<const PassInfo*> {
- BugDriver &BD;
-public:
- ReduceMiscompilingPasses(BugDriver &bd) : BD(bd) {}
-
- virtual TestResult doTest(std::vector<const PassInfo*> &Prefix,
- std::vector<const PassInfo*> &Suffix);
-};
+#include "Support/FileUtilities.h"
+using namespace llvm;
+
+namespace {
+ class ReduceMiscompilingPasses : public ListReducer<const PassInfo*> {
+ BugDriver &BD;
+ public:
+ ReduceMiscompilingPasses(BugDriver &bd) : BD(bd) {}
+
+ virtual TestResult doTest(std::vector<const PassInfo*> &Prefix,
+ std::vector<const PassInfo*> &Suffix);
+ };
+}
ReduceMiscompilingPasses::TestResult
ReduceMiscompilingPasses::doTest(std::vector<const PassInfo*> &Prefix,
std::string BytecodeResult;
if (BD.runPasses(Suffix, BytecodeResult, false/*delete*/, true/*quiet*/)) {
- std::cerr << BD.getToolName() << ": Error running this sequence of passes"
+ std::cerr << " Error running this sequence of passes"
<< " on the input program!\n";
- exit(1);
+ BD.setPassesToRun(Suffix);
+ BD.EmitProgressBytecode("pass-error", false);
+ exit(BD.debugOptimizerCrash());
}
// Check to see if the finished program matches the reference output...
// prefix passes, then discard the prefix passes.
//
if (BD.runPasses(Prefix, BytecodeResult, false/*delete*/, true/*quiet*/)) {
- std::cerr << BD.getToolName() << ": Error running this sequence of passes"
+ std::cerr << " Error running this sequence of passes"
<< " on the input program!\n";
- exit(1);
+ BD.setPassesToRun(Prefix);
+ BD.EmitProgressBytecode("pass-error", false);
+ exit(BD.debugOptimizerCrash());
}
// If the prefix maintains the predicate by itself, only keep the prefix!
// Ok, so now we know that the prefix passes work, try running the suffix
// passes on the result of the prefix passes.
//
- Module *PrefixOutput = BD.ParseInputFile(BytecodeResult);
+ Module *PrefixOutput = ParseInputFile(BytecodeResult);
if (PrefixOutput == 0) {
std::cerr << BD.getToolName() << ": Error reading bytecode file '"
<< BytecodeResult << "'!\n";
<< "' passes compile correctly after the '"
<< getPassesString(Prefix) << "' passes: ";
- Module *OriginalInput = BD.Program;
- BD.Program = PrefixOutput;
+ Module *OriginalInput = BD.swapProgramIn(PrefixOutput);
if (BD.runPasses(Suffix, BytecodeResult, false/*delete*/, true/*quiet*/)) {
- std::cerr << BD.getToolName() << ": Error running this sequence of passes"
+ std::cerr << " Error running this sequence of passes"
<< " on the input program!\n";
- exit(1);
+ BD.setPassesToRun(Suffix);
+ BD.EmitProgressBytecode("pass-error", false);
+ exit(BD.debugOptimizerCrash());
}
// Run the result...
// Otherwise, we must not be running the bad pass anymore.
std::cout << "yup.\n"; // No miscompilation!
- BD.Program = OriginalInput; // Restore original program
- delete PrefixOutput; // Free experiment
+ delete BD.swapProgramIn(OriginalInput); // Restore orig program & free test
return NoFailure;
}
-class ReduceMiscompilingFunctions : public ListReducer<Function*> {
- BugDriver &BD;
-public:
- ReduceMiscompilingFunctions(BugDriver &bd) : BD(bd) {}
-
- virtual TestResult doTest(std::vector<Function*> &Prefix,
- std::vector<Function*> &Suffix) {
- if (!Suffix.empty() && TestFuncs(Suffix, false))
- return KeepSuffix;
- if (!Prefix.empty() && TestFuncs(Prefix, false))
- return KeepPrefix;
- return NoFailure;
- }
-
- bool TestFuncs(const std::vector<Function*> &Prefix, bool EmitBytecode);
-};
-
-bool ReduceMiscompilingFunctions::TestFuncs(const std::vector<Function*> &Funcs,
- bool EmitBytecode) {
- // Test to see if the function is misoptimized if we ONLY run it on the
- // functions listed in Funcs.
- if (!EmitBytecode) {
- std::cout << "Checking to see if the program is misoptimized when these "
- << "functions are run\nthrough the passes: ";
- BD.PrintFunctionList(Funcs);
- std::cout << "\n";
- } else {
- std::cout <<"Outputting reduced bytecode files which expose the problem:\n";
- }
-
- // First step: clone the module for the two halves of the program we want.
- Module *ToOptimize = CloneModule(BD.Program);
-
- // Second step: Make sure functions & globals are all external so that linkage
- // between the two modules will work.
- for (Module::iterator I = ToOptimize->begin(), E = ToOptimize->end();I!=E;++I)
- I->setLinkage(GlobalValue::ExternalLinkage);
- for (Module::giterator I = ToOptimize->gbegin(), E = ToOptimize->gend();
- I != E; ++I)
- I->setLinkage(GlobalValue::ExternalLinkage);
-
- // Third step: make a clone of the externalized program for the non-optimized
- // part.
- Module *ToNotOptimize = CloneModule(ToOptimize);
-
- // Fourth step: Remove the test functions from the ToNotOptimize module, and
- // all of the global variables.
- for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
- Function *TNOF = ToNotOptimize->getFunction(Funcs[i]->getName(),
- Funcs[i]->getFunctionType());
- assert(TNOF && "Function doesn't exist in module!");
- DeleteFunctionBody(TNOF); // Function is now external in this module!
- }
- for (Module::giterator I = ToNotOptimize->gbegin(), E = ToNotOptimize->gend();
- I != E; ++I)
- I->setInitializer(0); // Delete the initializer to make it external
-
- if (EmitBytecode) {
- std::cout << " Non-optimized portion: ";
- std::swap(BD.Program, ToNotOptimize);
- BD.EmitProgressBytecode("tonotoptimize", true);
- std::swap(BD.Program, ToNotOptimize);
- }
-
- // Fifth step: Remove all functions from the ToOptimize module EXCEPT for the
- // ones specified in Funcs. We know which ones these are because they are
- // non-external in ToOptimize, but external in ToNotOptimize.
- //
- for (Module::iterator I = ToOptimize->begin(), E = ToOptimize->end();I!=E;++I)
- if (!I->isExternal()) {
- Function *TNOF = ToNotOptimize->getFunction(I->getName(),
- I->getFunctionType());
- assert(TNOF && "Function doesn't exist in ToNotOptimize module??");
- if (!TNOF->isExternal())
- DeleteFunctionBody(I);
+namespace {
+ class ReduceMiscompilingFunctions : public ListReducer<Function*> {
+ BugDriver &BD;
+ public:
+ ReduceMiscompilingFunctions(BugDriver &bd) : BD(bd) {}
+
+ virtual TestResult doTest(std::vector<Function*> &Prefix,
+ std::vector<Function*> &Suffix) {
+ if (!Suffix.empty() && TestFuncs(Suffix))
+ return KeepSuffix;
+ if (!Prefix.empty() && TestFuncs(Prefix))
+ return KeepPrefix;
+ return NoFailure;
}
+
+ bool TestFuncs(const std::vector<Function*> &Prefix);
+ };
+}
- if (EmitBytecode) {
- std::cout << " Portion that is input to optimizer: ";
- std::swap(BD.Program, ToOptimize);
- BD.EmitProgressBytecode("tooptimize");
- std::swap(BD.Program, ToOptimize);
+/// TestMergedProgram - Given two modules, link them together and run the
+/// program, checking to see if the program matches the diff. If the diff
+/// matches, return false, otherwise return true. If the DeleteInputs argument
+/// is set to true then this function deletes both input modules before it
+/// returns.
+static bool TestMergedProgram(BugDriver &BD, Module *M1, Module *M2,
+ bool DeleteInputs) {
+ // Link the two portions of the program back to together.
+ std::string ErrorMsg;
+ if (!DeleteInputs) M1 = CloneModule(M1);
+ if (LinkModules(M1, M2, &ErrorMsg)) {
+ std::cerr << BD.getToolName() << ": Error linking modules together:"
+ << ErrorMsg << "\n";
+ exit(1);
}
+ if (DeleteInputs) delete M2; // We are done with this module...
- // Sixth step: Run the optimization passes on ToOptimize, producing a
- // transformed version of the functions being tested.
- Module *OldProgram = BD.Program;
- BD.Program = ToOptimize;
+ Module *OldProgram = BD.swapProgramIn(M1);
- if (!EmitBytecode)
- std::cout << " Optimizing functions being tested: ";
- std::string BytecodeResult;
- if (BD.runPasses(BD.PassesToRun, BytecodeResult, false/*delete*/,
- true/*quiet*/)) {
- std::cerr << BD.getToolName() << ": Error running this sequence of passes"
- << " on the input program!\n";
- exit(1);
- }
+ // Execute the program. If it does not match the expected output, we must
+ // return true.
+ bool Broken = BD.diffProgram();
- if (!EmitBytecode)
- std::cout << "done.\n";
+ // Delete the linked module & restore the original
+ BD.swapProgramIn(OldProgram);
+ delete M1;
+ return Broken;
+}
- delete BD.Program; // Delete the old "ToOptimize" module
- BD.Program = BD.ParseInputFile(BytecodeResult);
+bool ReduceMiscompilingFunctions::TestFuncs(const std::vector<Function*>&Funcs){
+ // Test to see if the function is misoptimized if we ONLY run it on the
+ // functions listed in Funcs.
+ std::cout << "Checking to see if the program is misoptimized when "
+ << (Funcs.size()==1 ? "this function is" : "these functions are")
+ << " run through the pass"
+ << (BD.getPassesToRun().size() == 1 ? "" : "es") << ":";
+ PrintFunctionList(Funcs);
+ std::cout << "\n";
- if (EmitBytecode) {
- std::cout << " 'tooptimize' after being optimized: ";
- BD.EmitProgressBytecode("optimized", true);
- }
+ // Split the module into the two halves of the program we want.
+ Module *ToNotOptimize = CloneModule(BD.getProgram());
+ Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, Funcs);
- if (BD.Program == 0) {
- std::cerr << BD.getToolName() << ": Error reading bytecode file '"
- << BytecodeResult << "'!\n";
- exit(1);
- }
- removeFile(BytecodeResult); // No longer need the file on disk
+ // Run the optimization passes on ToOptimize, producing a transformed version
+ // of the functions being tested.
+ std::cout << " Optimizing functions being tested: ";
+ Module *Optimized = BD.runPassesOn(ToOptimize, BD.getPassesToRun(),
+ /*AutoDebugCrashes*/true);
+ std::cout << "done.\n";
+ delete ToOptimize;
- // Seventh step: Link the optimized part of the program back to the
- // unoptimized part of the program.
- //
- if (LinkModules(BD.Program, ToNotOptimize, &BytecodeResult)) {
- std::cerr << BD.getToolName() << ": Error linking modules together:"
- << BytecodeResult << "\n";
- exit(1);
- }
- delete ToNotOptimize; // We are done with this module...
-
- if (EmitBytecode) {
- std::cout << " Program as tested: ";
- BD.EmitProgressBytecode("linked", true);
- delete BD.Program;
- BD.Program = OldProgram;
- return false; // We don't need to actually execute the program here.
- }
std::cout << " Checking to see if the merged program executes correctly: ";
+ bool Broken = TestMergedProgram(BD, Optimized, ToNotOptimize, true);
+ std::cout << (Broken ? " nope.\n" : " yup.\n");
+ return Broken;
+}
- // Eighth step: Execute the program. If it does not match the expected
- // output, then 'Funcs' are being misoptimized!
- bool Broken = BD.diffProgram();
+/// ExtractLoops - Given a reduced list of functions that still exposed the bug,
+/// check to see if we can extract the loops in the region without obscuring the
+/// bug. If so, it reduces the amount of code identified.
+static bool ExtractLoops(BugDriver &BD,
+ std::vector<Function*> &MiscompiledFunctions) {
+ bool MadeChange = false;
+ while (1) {
+ Module *ToNotOptimize = CloneModule(BD.getProgram());
+ Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize,
+ MiscompiledFunctions);
+ Module *ToOptimizeLoopExtracted = BD.ExtractLoop(ToOptimize);
+ if (!ToOptimizeLoopExtracted) {
+ // If the loop extractor crashed or if there were no extractible loops,
+ // then this chapter of our odyssey is over with.
+ delete ToNotOptimize;
+ delete ToOptimize;
+ return MadeChange;
+ }
- delete BD.Program; // Delete the hacked up program
- BD.Program = OldProgram; // Restore the original
+ std::cerr << "Extracted a loop from the breaking portion of the program.\n";
+ delete ToOptimize;
+
+ // Bugpoint is intentionally not very trusting of LLVM transformations. In
+ // particular, we're not going to assume that the loop extractor works, so
+ // we're going to test the newly loop extracted program to make sure nothing
+ // has broken. If something broke, then we'll inform the user and stop
+ // extraction.
+ if (TestMergedProgram(BD, ToOptimizeLoopExtracted, ToNotOptimize, false)) {
+ // Merged program doesn't work anymore!
+ std::cerr << " *** ERROR: Loop extraction broke the program. :("
+ << " Please report a bug!\n";
+ std::cerr << " Continuing on with un-loop-extracted version.\n";
+ delete ToNotOptimize;
+ delete ToOptimizeLoopExtracted;
+ return MadeChange;
+ }
+
+ // Okay, the loop extractor didn't break the program. Run the series of
+ // optimizations on the loop extracted portion and see if THEY still break
+ // the program. If so, it was safe to extract these loops!
+ std::cout << " Running optimizations on loop extracted portion: ";
+ Module *Optimized = BD.runPassesOn(ToOptimizeLoopExtracted,
+ BD.getPassesToRun(),
+ /*AutoDebugCrashes*/true);
+ std::cout << "done.\n";
- std::cout << (Broken ? "nope.\n" : "yup.\n");
- return Broken;
-}
+ std::cout << " Checking to see if the merged program executes correctly: ";
+ bool Broken = TestMergedProgram(BD, Optimized, ToNotOptimize, false);
+ delete Optimized;
+ if (!Broken) {
+ std::cout << "yup: loop extraction masked the problem. Undoing.\n";
+ // If the program is not still broken, then loop extraction did something
+ // that masked the error. Stop loop extraction now.
+ delete ToNotOptimize;
+ delete ToOptimizeLoopExtracted;
+ return MadeChange;
+ }
+ std::cout << "nope: loop extraction successful!\n";
+
+ // Okay, great! Now we know that we extracted a loop and that loop
+ // extraction both didn't break the program, and didn't mask the problem.
+ // Replace the current program with the loop extracted version, and try to
+ // extract another loop.
+ std::string ErrorMsg;
+ if (LinkModules(ToNotOptimize, ToOptimizeLoopExtracted, &ErrorMsg)) {
+ std::cerr << BD.getToolName() << ": Error linking modules together:"
+ << ErrorMsg << "\n";
+ exit(1);
+ }
+ // All of the Function*'s in the MiscompiledFunctions list are in the old
+ // module. Update this list to include all of the functions in the
+ // optimized and loop extracted module.
+ MiscompiledFunctions.clear();
+ for (Module::iterator I = ToOptimizeLoopExtracted->begin(),
+ E = ToOptimizeLoopExtracted->end(); I != E; ++I) {
+ if (!I->isExternal()) {
+ Function *NewF = ToNotOptimize->getFunction(I->getName(),
+ I->getFunctionType());
+ assert(NewF && "Function not found??");
+ MiscompiledFunctions.push_back(NewF);
+ }
+ }
+ delete ToOptimizeLoopExtracted;
+
+ BD.setNewProgram(ToNotOptimize);
+ MadeChange = true;
+ }
+}
/// debugMiscompilation - This method is used when the passes selected are not
/// crashing, but the generated output is semantically different from the
/// input.
///
bool BugDriver::debugMiscompilation() {
-
- if (diffProgram()) {
- std::cout << "\n*** Input program does not match reference diff!\n"
- << " Must be problem with input source!\n";
- return false; // Problem found
- }
-
// Make sure something was miscompiled...
if (!ReduceMiscompilingPasses(*this).reduceList(PassesToRun)) {
std::cerr << "*** Optimized program matches reference output! No problem "
}
std::cout << "\n*** Found miscompiling pass"
- << (PassesToRun.size() == 1 ? "" : "es") << ": "
- << getPassesString(PassesToRun) << "\n";
+ << (getPassesToRun().size() == 1 ? "" : "es") << ": "
+ << getPassesString(getPassesToRun()) << "\n";
EmitProgressBytecode("passinput");
// Okay, now that we have reduced the list of passes which are causing the
// Do the reduction...
ReduceMiscompilingFunctions(*this).reduceList(MiscompiledFunctions);
- std::cout << "\n*** The following functions are being miscompiled: ";
+ std::cout << "\n*** The following function"
+ << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
+ << " being miscompiled: ";
PrintFunctionList(MiscompiledFunctions);
std::cout << "\n";
+ // See if we can rip any loops out of the miscompiled functions and still
+ // trigger the problem.
+ if (ExtractLoops(*this, MiscompiledFunctions)) {
+ // Okay, we extracted some loops and the problem still appears. See if we
+ // can eliminate some of the created functions from being candidates.
+
+ // Do the reduction...
+ ReduceMiscompilingFunctions(*this).reduceList(MiscompiledFunctions);
+
+ std::cout << "\n*** The following function"
+ << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
+ << " being miscompiled: ";
+ PrintFunctionList(MiscompiledFunctions);
+ std::cout << "\n";
+ }
+
// Output a bunch of bytecode files for the user...
- ReduceMiscompilingFunctions(*this).TestFuncs(MiscompiledFunctions, true);
+ std::cout << "Outputting reduced bytecode files which expose the problem:\n";
+ Module *ToNotOptimize = CloneModule(getProgram());
+ Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize,
+ MiscompiledFunctions);
+
+ std::cout << " Non-optimized portion: ";
+ std::swap(Program, ToNotOptimize);
+ EmitProgressBytecode("tonotoptimize", true);
+ setNewProgram(ToNotOptimize); // Delete hacked module.
+
+ std::cout << " Portion that is input to optimizer: ";
+ std::swap(Program, ToOptimize);
+ EmitProgressBytecode("tooptimize");
+ setNewProgram(ToOptimize); // Delete hacked module.
return false;
}
+
projects / oota-llvm.git / blobdiff