From 3277b69d734b9c90b44ebde4ede005717e2c3b2e Mon Sep 17 00:00:00 2001 From: ed Date: Tue, 2 Jun 2009 17:52:33 +0000 Subject: Import LLVM, at r72732. --- tools/bugpoint/BugDriver.cpp | 241 ++++++++++ tools/bugpoint/BugDriver.h | 322 +++++++++++++ tools/bugpoint/CMakeLists.txt | 16 + tools/bugpoint/CrashDebugger.cpp | 648 ++++++++++++++++++++++++++ tools/bugpoint/ExecutionDriver.cpp | 473 +++++++++++++++++++ tools/bugpoint/ExtractFunction.cpp | 375 +++++++++++++++ tools/bugpoint/FindBugs.cpp | 112 +++++ tools/bugpoint/ListReducer.h | 189 ++++++++ tools/bugpoint/Makefile | 17 + tools/bugpoint/Miscompilation.cpp | 932 +++++++++++++++++++++++++++++++++++++ tools/bugpoint/OptimizerDriver.cpp | 266 +++++++++++ tools/bugpoint/TestPasses.cpp | 75 +++ tools/bugpoint/ToolRunner.cpp | 748 +++++++++++++++++++++++++++++ tools/bugpoint/ToolRunner.h | 230 +++++++++ tools/bugpoint/bugpoint.cpp | 104 +++++ 15 files changed, 4748 insertions(+) create mode 100644 tools/bugpoint/BugDriver.cpp create mode 100644 tools/bugpoint/BugDriver.h create mode 100644 tools/bugpoint/CMakeLists.txt create mode 100644 tools/bugpoint/CrashDebugger.cpp create mode 100644 tools/bugpoint/ExecutionDriver.cpp create mode 100644 tools/bugpoint/ExtractFunction.cpp create mode 100644 tools/bugpoint/FindBugs.cpp create mode 100644 tools/bugpoint/ListReducer.h create mode 100644 tools/bugpoint/Makefile create mode 100644 tools/bugpoint/Miscompilation.cpp create mode 100644 tools/bugpoint/OptimizerDriver.cpp create mode 100644 tools/bugpoint/TestPasses.cpp create mode 100644 tools/bugpoint/ToolRunner.cpp create mode 100644 tools/bugpoint/ToolRunner.h create mode 100644 tools/bugpoint/bugpoint.cpp (limited to 'tools/bugpoint') diff --git a/tools/bugpoint/BugDriver.cpp b/tools/bugpoint/BugDriver.cpp new file mode 100644 index 0000000..d050b59 --- /dev/null +++ b/tools/bugpoint/BugDriver.cpp @@ -0,0 +1,241 @@ +//===- BugDriver.cpp - Top-Level BugPoint class implementation ------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This class contains all of the shared state and information that is used by +// the BugPoint tool to track down errors in optimizations. This class is the +// main driver class that invokes all sub-functionality. +// +//===----------------------------------------------------------------------===// + +#include "BugDriver.h" +#include "ToolRunner.h" +#include "llvm/Linker.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Assembly/Parser.h" +#include "llvm/Bitcode/ReaderWriter.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/FileUtilities.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/raw_ostream.h" +#include +#include +using namespace llvm; + +// Anonymous namespace to define command line options for debugging. +// +namespace { + // Output - The user can specify a file containing the expected output of the + // program. If this filename is set, it is used as the reference diff source, + // otherwise the raw input run through an interpreter is used as the reference + // source. + // + cl::opt + OutputFile("output", cl::desc("Specify a reference program output " + "(for miscompilation detection)")); +} + +/// setNewProgram - If we reduce or update the program somehow, call this method +/// to update bugdriver with it. This deletes the old module and sets the +/// specified one as the current program. +void BugDriver::setNewProgram(Module *M) { + delete Program; + Program = M; +} + + +/// getPassesString - Turn a list of passes into a string which indicates the +/// command line options that must be passed to add the passes. +/// +std::string llvm::getPassesString(const std::vector &Passes) { + std::string Result; + for (unsigned i = 0, e = Passes.size(); i != e; ++i) { + if (i) Result += " "; + Result += "-"; + Result += Passes[i]->getPassArgument(); + } + return Result; +} + +BugDriver::BugDriver(const char *toolname, bool as_child, bool find_bugs, + unsigned timeout, unsigned memlimit) + : ToolName(toolname), ReferenceOutputFile(OutputFile), + Program(0), Interpreter(0), SafeInterpreter(0), gcc(0), + run_as_child(as_child), + run_find_bugs(find_bugs), Timeout(timeout), MemoryLimit(memlimit) {} + + +/// ParseInputFile - Given a bitcode or assembly input filename, parse and +/// return it, or return null if not possible. +/// +Module *llvm::ParseInputFile(const std::string &Filename) { + std::auto_ptr Buffer(MemoryBuffer::getFileOrSTDIN(Filename)); + Module *Result = 0; + if (Buffer.get()) + Result = ParseBitcodeFile(Buffer.get()); + + ParseError Err; + if (!Result && !(Result = ParseAssemblyFile(Filename, Err))) { + Err.PrintError("bugpoint", errs()); + Result = 0; + } + + return Result; +} + +// This method takes the specified list of LLVM input files, attempts to load +// them, either as assembly or bitcode, then link them together. It returns +// true on failure (if, for example, an input bitcode file could not be +// parsed), and false on success. +// +bool BugDriver::addSources(const std::vector &Filenames) { + assert(Program == 0 && "Cannot call addSources multiple times!"); + assert(!Filenames.empty() && "Must specify at least on input filename!"); + + try { + // Load the first input file. + Program = ParseInputFile(Filenames[0]); + if (Program == 0) return true; + + if (!run_as_child) + std::cout << "Read input file : '" << Filenames[0] << "'\n"; + + for (unsigned i = 1, e = Filenames.size(); i != e; ++i) { + std::auto_ptr M(ParseInputFile(Filenames[i])); + if (M.get() == 0) return true; + + if (!run_as_child) + std::cout << "Linking in input file: '" << Filenames[i] << "'\n"; + std::string ErrorMessage; + if (Linker::LinkModules(Program, M.get(), &ErrorMessage)) { + std::cerr << ToolName << ": error linking in '" << Filenames[i] << "': " + << ErrorMessage << '\n'; + return true; + } + } + } catch (const std::string &Error) { + std::cerr << ToolName << ": error reading input '" << Error << "'\n"; + return true; + } + + if (!run_as_child) + std::cout << "*** All input ok\n"; + + // All input files read successfully! + return false; +} + + + +/// run - The top level method that is invoked after all of the instance +/// variables are set up from command line arguments. +/// +bool BugDriver::run() { + // The first thing to do is determine if we're running as a child. If we are, + // then what to do is very narrow. This form of invocation is only called + // from the runPasses method to actually run those passes in a child process. + if (run_as_child) { + // Execute the passes + return runPassesAsChild(PassesToRun); + } + + if (run_find_bugs) { + // Rearrange the passes and apply them to the program. Repeat this process + // until the user kills the program or we find a bug. + return runManyPasses(PassesToRun); + } + + // If we're not running as a child, the first thing that we must do is + // determine what the problem is. Does the optimization series crash the + // compiler, or does it produce illegal code? We make the top-level + // decision by trying to run all of the passes on the the input program, + // which should generate a bitcode file. If it does generate a bitcode + // file, then we know the compiler didn't crash, so try to diagnose a + // miscompilation. + if (!PassesToRun.empty()) { + std::cout << "Running selected passes on program to test for crash: "; + if (runPasses(PassesToRun)) + return debugOptimizerCrash(); + } + + // Set up the execution environment, selecting a method to run LLVM bitcode. + if (initializeExecutionEnvironment()) return true; + + // Test to see if we have a code generator crash. + std::cout << "Running the code generator to test for a crash: "; + try { + compileProgram(Program); + std::cout << '\n'; + } catch (ToolExecutionError &TEE) { + std::cout << TEE.what(); + return debugCodeGeneratorCrash(); + } + + + // Run the raw input to see where we are coming from. If a reference output + // was specified, make sure that the raw output matches it. If not, it's a + // problem in the front-end or the code generator. + // + bool CreatedOutput = false; + if (ReferenceOutputFile.empty()) { + std::cout << "Generating reference output from raw program: "; + if(!createReferenceFile(Program)){ + return debugCodeGeneratorCrash(); + } + CreatedOutput = true; + } + + // Make sure the reference output file gets deleted on exit from this + // function, if appropriate. + sys::Path ROF(ReferenceOutputFile); + FileRemover RemoverInstance(ROF, CreatedOutput); + + // Diff the output of the raw program against the reference output. If it + // matches, then we assume there is a miscompilation bug and try to + // diagnose it. + std::cout << "*** Checking the code generator...\n"; + try { + if (!diffProgram()) { + std::cout << "\n*** Debugging miscompilation!\n"; + return debugMiscompilation(); + } + } catch (ToolExecutionError &TEE) { + std::cerr << TEE.what(); + return debugCodeGeneratorCrash(); + } + + std::cout << "\n*** Input program does not match reference diff!\n"; + std::cout << "Debugging code generator problem!\n"; + try { + return debugCodeGenerator(); + } catch (ToolExecutionError &TEE) { + std::cerr << TEE.what(); + return debugCodeGeneratorCrash(); + } +} + +void llvm::PrintFunctionList(const std::vector &Funcs) { + unsigned NumPrint = Funcs.size(); + if (NumPrint > 10) NumPrint = 10; + for (unsigned i = 0; i != NumPrint; ++i) + std::cout << " " << Funcs[i]->getName(); + if (NumPrint < Funcs.size()) + std::cout << "... <" << Funcs.size() << " total>"; + std::cout << std::flush; +} + +void llvm::PrintGlobalVariableList(const std::vector &GVs) { + unsigned NumPrint = GVs.size(); + if (NumPrint > 10) NumPrint = 10; + for (unsigned i = 0; i != NumPrint; ++i) + std::cout << " " << GVs[i]->getName(); + if (NumPrint < GVs.size()) + std::cout << "... <" << GVs.size() << " total>"; + std::cout << std::flush; +} diff --git a/tools/bugpoint/BugDriver.h b/tools/bugpoint/BugDriver.h new file mode 100644 index 0000000..96e9fb9 --- /dev/null +++ b/tools/bugpoint/BugDriver.h @@ -0,0 +1,322 @@ +//===- BugDriver.h - Top-Level BugPoint class -------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This class contains all of the shared state and information that is used by +// the BugPoint tool to track down errors in optimizations. This class is the +// main driver class that invokes all sub-functionality. +// +//===----------------------------------------------------------------------===// + +#ifndef BUGDRIVER_H +#define BUGDRIVER_H + +#include "llvm/ADT/DenseMap.h" +#include +#include + +namespace llvm { + +class Value; +class PassInfo; +class Module; +class GlobalVariable; +class Function; +class BasicBlock; +class AbstractInterpreter; +class Instruction; + +class DebugCrashes; + +class GCC; + +extern bool DisableSimplifyCFG; + +/// BugpointIsInterrupted - Set to true when the user presses ctrl-c. +/// +extern bool BugpointIsInterrupted; + +class BugDriver { + const std::string ToolName; // Name of bugpoint + std::string ReferenceOutputFile; // Name of `good' output file + Module *Program; // The raw program, linked together + std::vector PassesToRun; + AbstractInterpreter *Interpreter; // How to run the program + AbstractInterpreter *SafeInterpreter; // To generate reference output, etc. + GCC *gcc; + bool run_as_child; + bool run_find_bugs; + unsigned Timeout; + unsigned MemoryLimit; + + // FIXME: sort out public/private distinctions... + friend class ReducePassList; + friend class ReduceMisCodegenFunctions; + +public: + BugDriver(const char *toolname, bool as_child, bool find_bugs, + unsigned timeout, unsigned memlimit); + + const std::string &getToolName() const { return ToolName; } + + // Set up methods... these methods are used to copy information about the + // command line arguments into instance variables of BugDriver. + // + bool addSources(const std::vector &FileNames); + template + void addPasses(It I, It E) { PassesToRun.insert(PassesToRun.end(), I, E); } + void setPassesToRun(const std::vector &PTR) { + PassesToRun = PTR; + } + const std::vector &getPassesToRun() const { + return PassesToRun; + } + + /// run - The top level method that is invoked after all of the instance + /// variables are set up from command line arguments. The \p as_child argument + /// indicates whether the driver is to run in parent mode or child mode. + /// + bool run(); + + /// debugOptimizerCrash - This method is called when some optimizer pass + /// crashes on input. It attempts to prune down the testcase to something + /// reasonable, and figure out exactly which pass is crashing. + /// + bool debugOptimizerCrash(const std::string &ID = "passes"); + + /// debugCodeGeneratorCrash - This method is called when the code generator + /// crashes on an input. It attempts to reduce the input as much as possible + /// while still causing the code generator to crash. + bool debugCodeGeneratorCrash(); + + /// debugMiscompilation - This method is used when the passes selected are not + /// crashing, but the generated output is semantically different from the + /// input. + bool debugMiscompilation(); + + /// debugPassMiscompilation - This method is called when the specified pass + /// miscompiles Program as input. It tries to reduce the testcase to + /// something that smaller that still miscompiles the program. + /// ReferenceOutput contains the filename of the file containing the output we + /// are to match. + /// + bool debugPassMiscompilation(const PassInfo *ThePass, + const std::string &ReferenceOutput); + + /// compileSharedObject - This method creates a SharedObject from a given + /// BitcodeFile for debugging a code generator. + /// + std::string compileSharedObject(const std::string &BitcodeFile); + + /// debugCodeGenerator - This method narrows down a module to a function or + /// set of functions, using the CBE as a ``safe'' code generator for other + /// functions that are not under consideration. + bool debugCodeGenerator(); + + /// isExecutingJIT - Returns true if bugpoint is currently testing the JIT + /// + bool isExecutingJIT(); + + /// runPasses - Run all of the passes in the "PassesToRun" list, discard the + /// output, and return true if any of the passes crashed. + bool runPasses(Module *M = 0) { + if (M == 0) M = Program; + std::swap(M, Program); + bool Result = runPasses(PassesToRun); + std::swap(M, Program); + return Result; + } + + Module *getProgram() const { return Program; } + + /// swapProgramIn - Set the current module to the specified module, returning + /// the old one. + Module *swapProgramIn(Module *M) { + Module *OldProgram = Program; + Program = M; + return OldProgram; + } + + AbstractInterpreter *switchToSafeInterpreter() { + AbstractInterpreter *Old = Interpreter; + Interpreter = (AbstractInterpreter*)SafeInterpreter; + return Old; + } + + void switchToInterpreter(AbstractInterpreter *AI) { + Interpreter = AI; + } + + /// setNewProgram - If we reduce or update the program somehow, call this + /// method to update bugdriver with it. This deletes the old module and sets + /// the specified one as the current program. + void setNewProgram(Module *M); + + /// compileProgram - Try to compile the specified module, throwing an + /// exception if an error occurs, or returning normally if not. This is used + /// for code generation crash testing. + /// + void compileProgram(Module *M); + + /// executeProgram - This method runs "Program", capturing the output of the + /// program to a file, returning the filename of the file. A recommended + /// filename may be optionally specified. If there is a problem with the code + /// generator (e.g., llc crashes), this will throw an exception. + /// + std::string executeProgram(std::string RequestedOutputFilename = "", + std::string Bitcode = "", + const std::string &SharedObjects = "", + AbstractInterpreter *AI = 0, + bool *ProgramExitedNonzero = 0); + + /// executeProgramSafely - Used to create reference output with the "safe" + /// backend, if reference output is not provided. If there is a problem with + /// the code generator (e.g., llc crashes), this will throw an exception. + /// + std::string executeProgramSafely(std::string OutputFile = ""); + + /// createReferenceFile - calls compileProgram and then records the output + /// into ReferenceOutputFile. Returns true if reference file created, false + /// otherwise. Note: initializeExecutionEnvironment should be called BEFORE + /// this function. + /// + bool createReferenceFile(Module *M, const std::string &Filename + = "bugpoint.reference.out"); + + /// diffProgram - This method executes the specified module and diffs the + /// output against the file specified by ReferenceOutputFile. If the output + /// is different, true is returned. If there is a problem with the code + /// generator (e.g., llc crashes), this will throw an exception. + /// + bool diffProgram(const std::string &BitcodeFile = "", + const std::string &SharedObj = "", + bool RemoveBitcode = false); + + /// EmitProgressBitcode - This function is used to output the current Program + /// to a file named "bugpoint-ID.bc". + /// + void EmitProgressBitcode(const std::string &ID, bool NoFlyer = false); + + /// deleteInstructionFromProgram - This method clones the current Program and + /// deletes the specified instruction from the cloned module. It then runs a + /// series of cleanup passes (ADCE and SimplifyCFG) to eliminate any code + /// which depends on the value. The modified module is then returned. + /// + Module *deleteInstructionFromProgram(const Instruction *I, unsigned Simp) + const; + + /// performFinalCleanups - This method clones the current Program and performs + /// a series of cleanups intended to get rid of extra cruft on the module. If + /// the MayModifySemantics argument is true, then the cleanups is allowed to + /// modify how the code behaves. + /// + Module *performFinalCleanups(Module *M, bool MayModifySemantics = false); + + /// ExtractLoop - Given a module, extract up to one loop from it into a new + /// function. This returns null if there are no extractable loops in the + /// program or if the loop extractor crashes. + Module *ExtractLoop(Module *M); + + /// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks + /// into their own functions. The only detail is that M is actually a module + /// cloned from the one the BBs are in, so some mapping needs to be performed. + /// If this operation fails for some reason (ie the implementation is buggy), + /// this function should return null, otherwise it returns a new Module. + Module *ExtractMappedBlocksFromModule(const std::vector &BBs, + Module *M); + + /// runPassesOn - Carefully run the specified set of pass on the specified + /// module, returning the transformed module on success, or a null pointer on + /// failure. If AutoDebugCrashes is set to true, then bugpoint will + /// automatically attempt to track down a crashing pass if one exists, and + /// this method will never return null. + Module *runPassesOn(Module *M, const std::vector &Passes, + bool AutoDebugCrashes = false, unsigned NumExtraArgs = 0, + const char * const *ExtraArgs = NULL); + + /// runPasses - Run the specified passes on Program, outputting a bitcode + /// file and writting the filename into OutputFile if successful. If the + /// optimizations fail for some reason (optimizer crashes), return true, + /// otherwise return false. If DeleteOutput is set to true, the bitcode is + /// deleted on success, and the filename string is undefined. This prints to + /// cout a single line message indicating whether compilation was successful + /// or failed, unless Quiet is set. ExtraArgs specifies additional arguments + /// to pass to the child bugpoint instance. + /// + bool runPasses(const std::vector &PassesToRun, + std::string &OutputFilename, bool DeleteOutput = false, + bool Quiet = false, unsigned NumExtraArgs = 0, + const char * const *ExtraArgs = NULL) const; + + /// runManyPasses - Take the specified pass list and create different + /// combinations of passes to compile the program with. Compile the program with + /// each set and mark test to see if it compiled correctly. If the passes + /// compiled correctly output nothing and rearrange the passes into a new order. + /// If the passes did not compile correctly, output the command required to + /// recreate the failure. This returns true if a compiler error is found. + /// + bool runManyPasses(const std::vector &AllPasses); + + /// writeProgramToFile - This writes the current "Program" to the named + /// bitcode file. If an error occurs, true is returned. + /// + bool writeProgramToFile(const std::string &Filename, Module *M = 0) const; + +private: + /// runPasses - Just like the method above, but this just returns true or + /// false indicating whether or not the optimizer crashed on the specified + /// input (true = crashed). + /// + bool runPasses(const std::vector &PassesToRun, + bool DeleteOutput = true) const { + std::string Filename; + return runPasses(PassesToRun, Filename, DeleteOutput); + } + + /// runAsChild - The actual "runPasses" guts that runs in a child process. + int runPassesAsChild(const std::vector &PassesToRun); + + /// initializeExecutionEnvironment - This method is used to set up the + /// environment for executing LLVM programs. + /// + bool initializeExecutionEnvironment(); +}; + +/// ParseInputFile - Given a bitcode or assembly input filename, parse and +/// return it, or return null if not possible. +/// +Module *ParseInputFile(const std::string &InputFilename); + + +/// getPassesString - Turn a list of passes into a string which indicates the +/// command line options that must be passed to add the passes. +/// +std::string getPassesString(const std::vector &Passes); + +/// PrintFunctionList - prints out list of problematic functions +/// +void PrintFunctionList(const std::vector &Funcs); + +/// PrintGlobalVariableList - prints out list of problematic global variables +/// +void PrintGlobalVariableList(const std::vector &GVs); + +// DeleteFunctionBody - "Remove" the function by deleting all of it's basic +// blocks, making it external. +// +void DeleteFunctionBody(Function *F); + +/// SplitFunctionsOutOfModule - Given a module and a list of functions in the +/// module, split the functions OUT of the specified module, and place them in +/// the new module. +Module *SplitFunctionsOutOfModule(Module *M, const std::vector &F, + DenseMap &ValueMap); + +} // End llvm namespace + +#endif diff --git a/tools/bugpoint/CMakeLists.txt b/tools/bugpoint/CMakeLists.txt new file mode 100644 index 0000000..90f24ba --- /dev/null +++ b/tools/bugpoint/CMakeLists.txt @@ -0,0 +1,16 @@ +set(LLVM_LINK_COMPONENTS asmparser instrumentation scalaropts ipo + linker bitreader bitwriter) +set(LLVM_REQUIRES_EH 1) + +add_llvm_tool(bugpoint + BugDriver.cpp + CrashDebugger.cpp + ExecutionDriver.cpp + ExtractFunction.cpp + FindBugs.cpp + Miscompilation.cpp + OptimizerDriver.cpp + TestPasses.cpp + ToolRunner.cpp + bugpoint.cpp + ) diff --git a/tools/bugpoint/CrashDebugger.cpp b/tools/bugpoint/CrashDebugger.cpp new file mode 100644 index 0000000..7daf57c --- /dev/null +++ b/tools/bugpoint/CrashDebugger.cpp @@ -0,0 +1,648 @@ +//===- CrashDebugger.cpp - Debug compilation crashes ----------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the bugpoint internals that narrow down compilation crashes +// +//===----------------------------------------------------------------------===// + +#include "BugDriver.h" +#include "ToolRunner.h" +#include "ListReducer.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/Instructions.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/PassManager.h" +#include "llvm/ValueSymbolTable.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/Verifier.h" +#include "llvm/Support/CFG.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Support/FileUtilities.h" +#include "llvm/Support/CommandLine.h" +#include +#include +using namespace llvm; + +namespace { + cl::opt + KeepMain("keep-main", + cl::desc("Force function reduction to keep main"), + cl::init(false)); + cl::opt + NoGlobalRM ("disable-global-remove", + cl::desc("Do not remove global variables"), + cl::init(false)); +} + +namespace llvm { + class ReducePassList : public ListReducer { + BugDriver &BD; + public: + ReducePassList(BugDriver &bd) : BD(bd) {} + + // doTest - Return true iff running the "removed" passes succeeds, and + // running the "Kept" passes fail when run on the output of the "removed" + // passes. If we return true, we update the current module of bugpoint. + // + virtual TestResult doTest(std::vector &Removed, + std::vector &Kept); + }; +} + +ReducePassList::TestResult +ReducePassList::doTest(std::vector &Prefix, + std::vector &Suffix) { + sys::Path PrefixOutput; + Module *OrigProgram = 0; + if (!Prefix.empty()) { + std::cout << "Checking to see if these passes crash: " + << getPassesString(Prefix) << ": "; + std::string PfxOutput; + if (BD.runPasses(Prefix, PfxOutput)) + return KeepPrefix; + + PrefixOutput.set(PfxOutput); + OrigProgram = BD.Program; + + BD.Program = ParseInputFile(PrefixOutput.toString()); + if (BD.Program == 0) { + std::cerr << BD.getToolName() << ": Error reading bitcode file '" + << PrefixOutput << "'!\n"; + exit(1); + } + PrefixOutput.eraseFromDisk(); + } + + std::cout << "Checking to see if these passes crash: " + << getPassesString(Suffix) << ": "; + + if (BD.runPasses(Suffix)) { + delete OrigProgram; // The suffix crashes alone... + return KeepSuffix; + } + + // Nothing failed, restore state... + if (OrigProgram) { + delete BD.Program; + BD.Program = OrigProgram; + } + return NoFailure; +} + +namespace { + /// ReduceCrashingGlobalVariables - This works by removing the global + /// variable's initializer and seeing if the program still crashes. If it + /// does, then we keep that program and try again. + /// + class ReduceCrashingGlobalVariables : public ListReducer { + BugDriver &BD; + bool (*TestFn)(BugDriver &, Module *); + public: + ReduceCrashingGlobalVariables(BugDriver &bd, + bool (*testFn)(BugDriver&, Module*)) + : BD(bd), TestFn(testFn) {} + + virtual TestResult doTest(std::vector& Prefix, + std::vector& Kept) { + if (!Kept.empty() && TestGlobalVariables(Kept)) + return KeepSuffix; + + if (!Prefix.empty() && TestGlobalVariables(Prefix)) + return KeepPrefix; + + return NoFailure; + } + + bool TestGlobalVariables(std::vector& GVs); + }; +} + +bool +ReduceCrashingGlobalVariables::TestGlobalVariables( + std::vector& GVs) { + // Clone the program to try hacking it apart... + DenseMap ValueMap; + Module *M = CloneModule(BD.getProgram(), ValueMap); + + // Convert list to set for fast lookup... + std::set GVSet; + + for (unsigned i = 0, e = GVs.size(); i != e; ++i) { + GlobalVariable* CMGV = cast(ValueMap[GVs[i]]); + assert(CMGV && "Global Variable not in module?!"); + GVSet.insert(CMGV); + } + + std::cout << "Checking for crash with only these global variables: "; + PrintGlobalVariableList(GVs); + std::cout << ": "; + + // Loop over and delete any global variables which we aren't supposed to be + // playing with... + for (Module::global_iterator I = M->global_begin(), E = M->global_end(); + I != E; ++I) + if (I->hasInitializer() && !GVSet.count(I)) { + I->setInitializer(0); + I->setLinkage(GlobalValue::ExternalLinkage); + } + + // Try running the hacked up program... + if (TestFn(BD, M)) { + BD.setNewProgram(M); // It crashed, keep the trimmed version... + + // Make sure to use global variable pointers that point into the now-current + // module. + GVs.assign(GVSet.begin(), GVSet.end()); + return true; + } + + delete M; + return false; +} + +namespace llvm { + /// ReduceCrashingFunctions reducer - This works by removing functions and + /// seeing if the program still crashes. If it does, then keep the newer, + /// smaller program. + /// + class ReduceCrashingFunctions : public ListReducer { + BugDriver &BD; + bool (*TestFn)(BugDriver &, Module *); + public: + ReduceCrashingFunctions(BugDriver &bd, + bool (*testFn)(BugDriver &, Module *)) + : BD(bd), TestFn(testFn) {} + + virtual TestResult doTest(std::vector &Prefix, + std::vector &Kept) { + if (!Kept.empty() && TestFuncs(Kept)) + return KeepSuffix; + if (!Prefix.empty() && TestFuncs(Prefix)) + return KeepPrefix; + return NoFailure; + } + + bool TestFuncs(std::vector &Prefix); + }; +} + +bool ReduceCrashingFunctions::TestFuncs(std::vector &Funcs) { + + //if main isn't present, claim there is no problem + if (KeepMain && find(Funcs.begin(), Funcs.end(), + BD.getProgram()->getFunction("main")) == Funcs.end()) + return false; + + // Clone the program to try hacking it apart... + DenseMap ValueMap; + Module *M = CloneModule(BD.getProgram(), ValueMap); + + // Convert list to set for fast lookup... + std::set Functions; + for (unsigned i = 0, e = Funcs.size(); i != e; ++i) { + Function *CMF = cast(ValueMap[Funcs[i]]); + assert(CMF && "Function not in module?!"); + assert(CMF->getFunctionType() == Funcs[i]->getFunctionType() && "wrong ty"); + assert(CMF->getName() == Funcs[i]->getName() && "wrong name"); + Functions.insert(CMF); + } + + std::cout << "Checking for crash with only these functions: "; + PrintFunctionList(Funcs); + std::cout << ": "; + + // Loop over and delete any functions which we aren't supposed to be playing + // with... + for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) + if (!I->isDeclaration() && !Functions.count(I)) + DeleteFunctionBody(I); + + // Try running the hacked up program... + if (TestFn(BD, M)) { + BD.setNewProgram(M); // It crashed, keep the trimmed version... + + // Make sure to use function pointers that point into the now-current + // module. + Funcs.assign(Functions.begin(), Functions.end()); + return true; + } + delete M; + return false; +} + + +namespace { + /// ReduceCrashingBlocks reducer - This works by setting the terminators of + /// all terminators except the specified basic blocks to a 'ret' instruction, + /// then running the simplify-cfg pass. This has the effect of chopping up + /// the CFG really fast which can reduce large functions quickly. + /// + class ReduceCrashingBlocks : public ListReducer { + BugDriver &BD; + bool (*TestFn)(BugDriver &, Module *); + public: + ReduceCrashingBlocks(BugDriver &bd, bool (*testFn)(BugDriver &, Module *)) + : BD(bd), TestFn(testFn) {} + + virtual TestResult doTest(std::vector &Prefix, + std::vector &Kept) { + if (!Kept.empty() && TestBlocks(Kept)) + return KeepSuffix; + if (!Prefix.empty() && TestBlocks(Prefix)) + return KeepPrefix; + return NoFailure; + } + + bool TestBlocks(std::vector &Prefix); + }; +} + +bool ReduceCrashingBlocks::TestBlocks(std::vector &BBs) { + // Clone the program to try hacking it apart... + DenseMap ValueMap; + Module *M = CloneModule(BD.getProgram(), ValueMap); + + // Convert list to set for fast lookup... + SmallPtrSet Blocks; + for (unsigned i = 0, e = BBs.size(); i != e; ++i) + Blocks.insert(cast(ValueMap[BBs[i]])); + + std::cout << "Checking for crash with only these blocks:"; + unsigned NumPrint = Blocks.size(); + if (NumPrint > 10) NumPrint = 10; + for (unsigned i = 0, e = NumPrint; i != e; ++i) + std::cout << " " << BBs[i]->getName(); + if (NumPrint < Blocks.size()) + std::cout << "... <" << Blocks.size() << " total>"; + std::cout << ": "; + + // Loop over and delete any hack up any blocks that are not listed... + for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) + for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB) + if (!Blocks.count(BB) && BB->getTerminator()->getNumSuccessors()) { + // Loop over all of the successors of this block, deleting any PHI nodes + // that might include it. + for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) + (*SI)->removePredecessor(BB); + + TerminatorInst *BBTerm = BB->getTerminator(); + + if (isa(BBTerm->getType())) + BBTerm->replaceAllUsesWith(UndefValue::get(BBTerm->getType())); + else if (BB->getTerminator()->getType() != Type::VoidTy) + BBTerm->replaceAllUsesWith(Constant::getNullValue(BBTerm->getType())); + + // Replace the old terminator instruction. + BB->getInstList().pop_back(); + new UnreachableInst(BB); + } + + // The CFG Simplifier pass may delete one of the basic blocks we are + // interested in. If it does we need to take the block out of the list. Make + // a "persistent mapping" by turning basic blocks into pairs. + // This won't work well if blocks are unnamed, but that is just the risk we + // have to take. + std::vector > BlockInfo; + + for (SmallPtrSet::iterator I = Blocks.begin(), + E = Blocks.end(); I != E; ++I) + BlockInfo.push_back(std::make_pair((*I)->getParent(), (*I)->getName())); + + // Now run the CFG simplify pass on the function... + PassManager Passes; + Passes.add(createCFGSimplificationPass()); + Passes.add(createVerifierPass()); + Passes.run(*M); + + // Try running on the hacked up program... + if (TestFn(BD, M)) { + BD.setNewProgram(M); // It crashed, keep the trimmed version... + + // Make sure to use basic block pointers that point into the now-current + // module, and that they don't include any deleted blocks. + BBs.clear(); + for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { + ValueSymbolTable &ST = BlockInfo[i].first->getValueSymbolTable(); + Value* V = ST.lookup(BlockInfo[i].second); + if (V && V->getType() == Type::LabelTy) + BBs.push_back(cast(V)); + } + return true; + } + delete M; // It didn't crash, try something else. + return false; +} + +namespace { + /// ReduceCrashingInstructions reducer - This works by removing the specified + /// non-terminator instructions and replacing them with undef. + /// + class ReduceCrashingInstructions : public ListReducer { + BugDriver &BD; + bool (*TestFn)(BugDriver &, Module *); + public: + ReduceCrashingInstructions(BugDriver &bd, bool (*testFn)(BugDriver &, + Module *)) + : BD(bd), TestFn(testFn) {} + + virtual TestResult doTest(std::vector &Prefix, + std::vector &Kept) { + if (!Kept.empty() && TestInsts(Kept)) + return KeepSuffix; + if (!Prefix.empty() && TestInsts(Prefix)) + return KeepPrefix; + return NoFailure; + } + + bool TestInsts(std::vector &Prefix); + }; +} + +bool ReduceCrashingInstructions::TestInsts(std::vector + &Insts) { + // Clone the program to try hacking it apart... + DenseMap ValueMap; + Module *M = CloneModule(BD.getProgram(), ValueMap); + + // Convert list to set for fast lookup... + SmallPtrSet Instructions; + for (unsigned i = 0, e = Insts.size(); i != e; ++i) { + assert(!isa(Insts[i])); + Instructions.insert(cast(ValueMap[Insts[i]])); + } + + std::cout << "Checking for crash with only " << Instructions.size(); + if (Instructions.size() == 1) + std::cout << " instruction: "; + else + std::cout << " instructions: "; + + for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) + for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI) + for (BasicBlock::iterator I = FI->begin(), E = FI->end(); I != E;) { + Instruction *Inst = I++; + if (!Instructions.count(Inst) && !isa(Inst)) { + if (Inst->getType() != Type::VoidTy) + Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); + Inst->eraseFromParent(); + } + } + + // Verify that this is still valid. + PassManager Passes; + Passes.add(createVerifierPass()); + Passes.run(*M); + + // Try running on the hacked up program... + if (TestFn(BD, M)) { + BD.setNewProgram(M); // It crashed, keep the trimmed version... + + // Make sure to use instruction pointers that point into the now-current + // module, and that they don't include any deleted blocks. + Insts.clear(); + for (SmallPtrSet::const_iterator I = Instructions.begin(), + E = Instructions.end(); I != E; ++I) + Insts.push_back(*I); + return true; + } + delete M; // It didn't crash, try something else. + return false; +} + +/// DebugACrash - Given a predicate that determines whether a component crashes +/// on a program, try to destructively reduce the program while still keeping +/// the predicate true. +static bool DebugACrash(BugDriver &BD, bool (*TestFn)(BugDriver &, Module *)) { + // See if we can get away with nuking some of the global variable initializers + // in the program... + if (!NoGlobalRM && + BD.getProgram()->global_begin() != BD.getProgram()->global_end()) { + // Now try to reduce the number of global variable initializers in the + // module to something small. + Module *M = CloneModule(BD.getProgram()); + bool DeletedInit = false; + + for (Module::global_iterator I = M->global_begin(), E = M->global_end(); + I != E; ++I) + if (I->hasInitializer()) { + I->setInitializer(0); + I->setLinkage(GlobalValue::ExternalLinkage); + DeletedInit = true; + } + + if (!DeletedInit) { + delete M; // No change made... + } else { + // See if the program still causes a crash... + std::cout << "\nChecking to see if we can delete global inits: "; + + if (TestFn(BD, M)) { // Still crashes? + BD.setNewProgram(M); + std::cout << "\n*** Able to remove all global initializers!\n"; + } else { // No longer crashes? + std::cout << " - Removing all global inits hides problem!\n"; + delete M; + + std::vector GVs; + + for (Module::global_iterator I = BD.getProgram()->global_begin(), + E = BD.getProgram()->global_end(); I != E; ++I) + if (I->hasInitializer()) + GVs.push_back(I); + + if (GVs.size() > 1 && !BugpointIsInterrupted) { + std::cout << "\n*** Attempting to reduce the number of global " + << "variables in the testcase\n"; + + unsigned OldSize = GVs.size(); + ReduceCrashingGlobalVariables(BD, TestFn).reduceList(GVs); + + if (GVs.size() < OldSize) + BD.EmitProgressBitcode("reduced-global-variables"); + } + } + } + } + + // Now try to reduce the number of functions in the module to something small. + std::vector Functions; + for (Module::iterator I = BD.getProgram()->begin(), + E = BD.getProgram()->end(); I != E; ++I) + if (!I->isDeclaration()) + Functions.push_back(I); + + if (Functions.size() > 1 && !BugpointIsInterrupted) { + std::cout << "\n*** Attempting to reduce the number of functions " + "in the testcase\n"; + + unsigned OldSize = Functions.size(); + ReduceCrashingFunctions(BD, TestFn).reduceList(Functions); + + if (Functions.size() < OldSize) + BD.EmitProgressBitcode("reduced-function"); + } + + // Attempt to delete entire basic blocks at a time to speed up + // convergence... this actually works by setting the terminator of the blocks + // to a return instruction then running simplifycfg, which can potentially + // shrinks the code dramatically quickly + // + if (!DisableSimplifyCFG && !BugpointIsInterrupted) { + std::vector Blocks; + for (Module::const_iterator I = BD.getProgram()->begin(), + E = BD.getProgram()->end(); I != E; ++I) + for (Function::const_iterator FI = I->begin(), E = I->end(); FI !=E; ++FI) + Blocks.push_back(FI); + unsigned OldSize = Blocks.size(); + ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks); + if (Blocks.size() < OldSize) + BD.EmitProgressBitcode("reduced-blocks"); + } + + // Attempt to delete instructions using bisection. This should help out nasty + // cases with large basic blocks where the problem is at one end. + if (!BugpointIsInterrupted) { + std::vector Insts; + for (Module::const_iterator MI = BD.getProgram()->begin(), + ME = BD.getProgram()->end(); MI != ME; ++MI) + for (Function::const_iterator FI = MI->begin(), FE = MI->end(); FI != FE; + ++FI) + for (BasicBlock::const_iterator I = FI->begin(), E = FI->end(); + I != E; ++I) + if (!isa(I)) + Insts.push_back(I); + + ReduceCrashingInstructions(BD, TestFn).reduceList(Insts); + } + + // FIXME: This should use the list reducer to converge faster by deleting + // larger chunks of instructions at a time! + unsigned Simplification = 2; + do { + if (BugpointIsInterrupted) break; + --Simplification; + std::cout << "\n*** Attempting to reduce testcase by deleting instruc" + << "tions: Simplification Level #" << Simplification << '\n'; + + // Now that we have deleted the functions that are unnecessary for the + // program, try to remove instructions that are not necessary to cause the + // crash. To do this, we loop through all of the instructions in the + // remaining functions, deleting them (replacing any values produced with + // nulls), and then running ADCE and SimplifyCFG. If the transformed input + // still triggers failure, keep deleting until we cannot trigger failure + // anymore. + // + unsigned InstructionsToSkipBeforeDeleting = 0; + TryAgain: + + // Loop over all of the (non-terminator) instructions remaining in the + // function, attempting to delete them. + unsigned CurInstructionNum = 0; + for (Module::const_iterator FI = BD.getProgram()->begin(), + E = BD.getProgram()->end(); FI != E; ++FI) + if (!FI->isDeclaration()) + for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E; + ++BI) + for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end(); + I != E; ++I, ++CurInstructionNum) + if (InstructionsToSkipBeforeDeleting) { + --InstructionsToSkipBeforeDeleting; + } else { + if (BugpointIsInterrupted) goto ExitLoops; + + std::cout << "Checking instruction: " << *I; + Module *M = BD.deleteInstructionFromProgram(I, Simplification); + + // Find out if the pass still crashes on this pass... + if (TestFn(BD, M)) { + // Yup, it does, we delete the old module, and continue trying + // to reduce the testcase... + BD.setNewProgram(M); + InstructionsToSkipBeforeDeleting = CurInstructionNum; + goto TryAgain; // I wish I had a multi-level break here! + } + + // This pass didn't crash without this instruction, try the next + // one. + delete M; + } + + if (InstructionsToSkipBeforeDeleting) { + InstructionsToSkipBeforeDeleting = 0; + goto TryAgain; + } + + } while (Simplification); +ExitLoops: + + // Try to clean up the testcase by running funcresolve and globaldce... + if (!BugpointIsInterrupted) { + std::cout << "\n*** Attempting to perform final cleanups: "; + Module *M = CloneModule(BD.getProgram()); + M = BD.performFinalCleanups(M, true); + + // Find out if the pass still crashes on the cleaned up program... + if (TestFn(BD, M)) { + BD.setNewProgram(M); // Yup, it does, keep the reduced version... + } else { + delete M; + } + } + + BD.EmitProgressBitcode("reduced-simplified"); + + return false; +} + +static bool TestForOptimizerCrash(BugDriver &BD, Module *M) { + return BD.runPasses(M); +} + +/// debugOptimizerCrash - This method is called when some pass crashes on input. +/// It attempts to prune down the testcase to something reasonable, and figure +/// out exactly which pass is crashing. +/// +bool BugDriver::debugOptimizerCrash(const std::string &ID) { + std::cout << "\n*** Debugging optimizer crash!\n"; + + // Reduce the list of passes which causes the optimizer to crash... + if (!BugpointIsInterrupted) + ReducePassList(*this).reduceList(PassesToRun); + + std::cout << "\n*** Found crashing pass" + << (PassesToRun.size() == 1 ? ": " : "es: ") + << getPassesString(PassesToRun) << '\n'; + + EmitProgressBitcode(ID); + + return DebugACrash(*this, TestForOptimizerCrash); +} + +static bool TestForCodeGenCrash(BugDriver &BD, Module *M) { + try { + BD.compileProgram(M); + std::cerr << '\n'; + return false; + } catch (ToolExecutionError &) { + std::cerr << "\n"; + return true; // Tool is still crashing. + } +} + +/// debugCodeGeneratorCrash - This method is called when the code generator +/// crashes on an input. It attempts to reduce the input as much as possible +/// while still causing the code generator to crash. +bool BugDriver::debugCodeGeneratorCrash() { + std::cerr << "*** Debugging code generator crash!\n"; + + return DebugACrash(*this, TestForCodeGenCrash); +} diff --git a/tools/bugpoint/ExecutionDriver.cpp b/tools/bugpoint/ExecutionDriver.cpp new file mode 100644 index 0000000..640fe28 --- /dev/null +++ b/tools/bugpoint/ExecutionDriver.cpp @@ -0,0 +1,473 @@ +//===- ExecutionDriver.cpp - Allow execution of LLVM program --------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains code used to execute the program utilizing one of the +// various ways of running LLVM bitcode. +// +//===----------------------------------------------------------------------===// + +#include "BugDriver.h" +#include "ToolRunner.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FileUtilities.h" +#include "llvm/Support/SystemUtils.h" +#include +#include + +using namespace llvm; + +namespace { + // OutputType - Allow the user to specify the way code should be run, to test + // for miscompilation. + // + enum OutputType { + AutoPick, RunLLI, RunJIT, RunLLC, RunCBE, CBE_bug, LLC_Safe, Custom + }; + + cl::opt + AbsTolerance("abs-tolerance", cl::desc("Absolute error tolerated"), + cl::init(0.0)); + cl::opt + RelTolerance("rel-tolerance", cl::desc("Relative error tolerated"), + cl::init(0.0)); + + cl::opt + InterpreterSel(cl::desc("Specify the \"test\" i.e. suspect back-end:"), + cl::values(clEnumValN(AutoPick, "auto", "Use best guess"), + clEnumValN(RunLLI, "run-int", + "Execute with the interpreter"), + clEnumValN(RunJIT, "run-jit", "Execute with JIT"), + clEnumValN(RunLLC, "run-llc", "Compile with LLC"), + clEnumValN(RunCBE, "run-cbe", "Compile with CBE"), + clEnumValN(CBE_bug,"cbe-bug", "Find CBE bugs"), + clEnumValN(LLC_Safe, "llc-safe", "Use LLC for all"), + clEnumValN(Custom, "run-custom", + "Use -exec-command to define a command to execute " + "the bitcode. Useful for cross-compilation."), + clEnumValEnd), + cl::init(AutoPick)); + + cl::opt + SafeInterpreterSel(cl::desc("Specify \"safe\" i.e. known-good backend:"), + cl::values(clEnumValN(AutoPick, "safe-auto", "Use best guess"), + clEnumValN(RunLLC, "safe-run-llc", "Compile with LLC"), + clEnumValN(RunCBE, "safe-run-cbe", "Compile with CBE"), + clEnumValN(Custom, "safe-run-custom", + "Use -exec-command to define a command to execute " + "the bitcode. Useful for cross-compilation."), + clEnumValEnd), + cl::init(AutoPick)); + + cl::opt + SafeInterpreterPath("safe-path", + cl::desc("Specify the path to the \"safe\" backend program"), + cl::init("")); + + cl::opt + AppendProgramExitCode("append-exit-code", + cl::desc("Append the exit code to the output so it gets diff'd too"), + cl::init(false)); + + cl::opt + InputFile("input", cl::init("/dev/null"), + cl::desc("Filename to pipe in as stdin (default: /dev/null)")); + + cl::list + AdditionalSOs("additional-so", + cl::desc("Additional shared objects to load " + "into executing programs")); + + cl::list + AdditionalLinkerArgs("Xlinker", + cl::desc("Additional arguments to pass to the linker")); + + cl::opt + CustomExecCommand("exec-command", cl::init("simulate"), + cl::desc("Command to execute the bitcode (use with -run-custom) " + "(default: simulate)")); +} + +namespace llvm { + // Anything specified after the --args option are taken as arguments to the + // program being debugged. + cl::list + InputArgv("args", cl::Positional, cl::desc("..."), + cl::ZeroOrMore, cl::PositionalEatsArgs); +} + +namespace { + cl::list + ToolArgv("tool-args", cl::Positional, cl::desc("..."), + cl::ZeroOrMore, cl::PositionalEatsArgs); + + cl::list + SafeToolArgv("safe-tool-args", cl::Positional, + cl::desc("..."), + cl::ZeroOrMore, cl::PositionalEatsArgs); + + cl::list + GCCToolArgv("gcc-tool-args", cl::Positional, + cl::desc("..."), + cl::ZeroOrMore, cl::PositionalEatsArgs); +} + +//===----------------------------------------------------------------------===// +// BugDriver method implementation +// + +/// initializeExecutionEnvironment - This method is used to set up the +/// environment for executing LLVM programs. +/// +bool BugDriver::initializeExecutionEnvironment() { + std::cout << "Initializing execution environment: "; + + // Create an instance of the AbstractInterpreter interface as specified on + // the command line + SafeInterpreter = 0; + std::string Message; + + switch (InterpreterSel) { + case AutoPick: + InterpreterSel = RunCBE; + Interpreter = + AbstractInterpreter::createCBE(getToolName(), Message, &ToolArgv, + &GCCToolArgv); + if (!Interpreter) { + InterpreterSel = RunJIT; + Interpreter = AbstractInterpreter::createJIT(getToolName(), Message, + &ToolArgv); + } + if (!Interpreter) { + InterpreterSel = RunLLC; + Interpreter = AbstractInterpreter::createLLC(getToolName(), Message, + &ToolArgv, &GCCToolArgv); + } + if (!Interpreter) { + InterpreterSel = RunLLI; + Interpreter = AbstractInterpreter::createLLI(getToolName(), Message, + &ToolArgv); + } + if (!Interpreter) { + InterpreterSel = AutoPick; + Message = "Sorry, I can't automatically select an interpreter!\n"; + } + break; + case RunLLI: + Interpreter = AbstractInterpreter::createLLI(getToolName(), Message, + &ToolArgv); + break; + case RunLLC: + case LLC_Safe: + Interpreter = AbstractInterpreter::createLLC(getToolName(), Message, + &ToolArgv, &GCCToolArgv); + break; + case RunJIT: + Interpreter = AbstractInterpreter::createJIT(getToolName(), Message, + &ToolArgv); + break; + case RunCBE: + case CBE_bug: + Interpreter = AbstractInterpreter::createCBE(getToolName(), Message, + &ToolArgv, &GCCToolArgv); + break; + case Custom: + Interpreter = AbstractInterpreter::createCustom(getToolName(), Message, + CustomExecCommand); + break; + default: + Message = "Sorry, this back-end is not supported by bugpoint right now!\n"; + break; + } + if (!Interpreter) + std::cerr << Message; + else // Display informational messages on stdout instead of stderr + std::cout << Message; + + std::string Path = SafeInterpreterPath; + if (Path.empty()) + Path = getToolName(); + std::vector SafeToolArgs = SafeToolArgv; + switch (SafeInterpreterSel) { + case AutoPick: + // In "cbe-bug" mode, default to using LLC as the "safe" backend. + if (!SafeInterpreter && + InterpreterSel == CBE_bug) { + SafeInterpreterSel = RunLLC; + SafeToolArgs.push_back("--relocation-model=pic"); + SafeInterpreter = AbstractInterpreter::createLLC(Path, Message, + &SafeToolArgs, + &GCCToolArgv); + } + + // In "llc-safe" mode, default to using LLC as the "safe" backend. + if (!SafeInterpreter && + InterpreterSel == LLC_Safe) { + SafeInterpreterSel = RunLLC; + SafeToolArgs.push_back("--relocation-model=pic"); + SafeInterpreter = AbstractInterpreter::createLLC(Path, Message, + &SafeToolArgs, + &GCCToolArgv); + } + + // Pick a backend that's different from the test backend. The JIT and + // LLC backends share a lot of code, so prefer to use the CBE as the + // safe back-end when testing them. + if (!SafeInterpreter && + InterpreterSel != RunCBE) { + SafeInterpreterSel = RunCBE; + SafeInterpreter = AbstractInterpreter::createCBE(Path, Message, + &SafeToolArgs, + &GCCToolArgv); + } + if (!SafeInterpreter && + InterpreterSel != RunLLC && + InterpreterSel != RunJIT) { + SafeInterpreterSel = RunLLC; + SafeToolArgs.push_back("--relocation-model=pic"); + SafeInterpreter = AbstractInterpreter::createLLC(Path, Message, + &SafeToolArgs, + &GCCToolArgv); + } + if (!SafeInterpreter) { + SafeInterpreterSel = AutoPick; + Message = "Sorry, I can't automatically select an interpreter!\n"; + } + break; + case RunLLC: + SafeToolArgs.push_back("--relocation-model=pic"); + SafeInterpreter = AbstractInterpreter::createLLC(Path, Message, + &SafeToolArgs, + &GCCToolArgv); + break; + case RunCBE: + SafeInterpreter = AbstractInterpreter::createCBE(Path, Message, + &SafeToolArgs, + &GCCToolArgv); + break; + case Custom: + SafeInterpreter = AbstractInterpreter::createCustom(Path, Message, + CustomExecCommand); + break; + default: + Message = "Sorry, this back-end is not supported by bugpoint as the " + "\"safe\" backend right now!\n"; + break; + } + if (!SafeInterpreter) { std::cout << Message << "\nExiting.\n"; exit(1); } + + gcc = GCC::create(getToolName(), Message, &GCCToolArgv); + if (!gcc) { std::cout << Message << "\nExiting.\n"; exit(1); } + + // If there was an error creating the selected interpreter, quit with error. + return Interpreter == 0; +} + +/// compileProgram - Try to compile the specified module, throwing an exception +/// if an error occurs, or returning normally if not. This is used for code +/// generation crash testing. +/// +void BugDriver::compileProgram(Module *M) { + // Emit the program to a bitcode file... + sys::Path BitcodeFile ("bugpoint-test-program.bc"); + std::string ErrMsg; + if (BitcodeFile.makeUnique(true,&ErrMsg)) { + std::cerr << ToolName << ": Error making unique filename: " << ErrMsg + << "\n"; + exit(1); + } + if (writeProgramToFile(BitcodeFile.toString(), M)) { + std::cerr << ToolName << ": Error emitting bitcode to file '" + << BitcodeFile << "'!\n"; + exit(1); + } + + // Remove the temporary bitcode file when we are done. + FileRemover BitcodeFileRemover(BitcodeFile); + + // Actually compile the program! + Interpreter->compileProgram(BitcodeFile.toString()); +} + + +/// executeProgram - This method runs "Program", capturing the output of the +/// program to a file, returning the filename of the file. A recommended +/// filename may be optionally specified. +/// +std::string BugDriver::executeProgram(std::string OutputFile, + std::string BitcodeFile, + const std::string &SharedObj, + AbstractInterpreter *AI, + bool *ProgramExitedNonzero) { + if (AI == 0) AI = Interpreter; + assert(AI && "Interpreter should have been created already!"); + bool CreatedBitcode = false; + std::string ErrMsg; + if (BitcodeFile.empty()) { + // Emit the program to a bitcode file... + sys::Path uniqueFilename("bugpoint-test-program.bc"); + if (uniqueFilename.makeUnique(true, &ErrMsg)) { + std::cerr << ToolName << ": Error making unique filename: " + << ErrMsg << "!\n"; + exit(1); + } + BitcodeFile = uniqueFilename.toString(); + + if (writeProgramToFile(BitcodeFile, Program)) { + std::cerr << ToolName << ": Error emitting bitcode to file '" + << BitcodeFile << "'!\n"; + exit(1); + } + CreatedBitcode = true; + } + + // Remove the temporary bitcode file when we are done. + sys::Path BitcodePath (BitcodeFile); + FileRemover BitcodeFileRemover(BitcodePath, CreatedBitcode); + + if (OutputFile.empty()) OutputFile = "bugpoint-execution-output"; + + // Check to see if this is a valid output filename... + sys::Path uniqueFile(OutputFile); + if (uniqueFile.makeUnique(true, &ErrMsg)) { + std::cerr << ToolName << ": Error making unique filename: " + << ErrMsg << "\n"; + exit(1); + } + OutputFile = uniqueFile.toString(); + + // Figure out which shared objects to run, if any. + std::vector SharedObjs(AdditionalSOs); + if (!SharedObj.empty()) + SharedObjs.push_back(SharedObj); + + int RetVal = AI->ExecuteProgram(BitcodeFile, InputArgv, InputFile, + OutputFile, AdditionalLinkerArgs, SharedObjs, + Timeout, MemoryLimit); + + if (RetVal == -1) { + std::cerr << ""; + static bool FirstTimeout = true; + if (FirstTimeout) { + std::cout << "\n" + "*** Program execution timed out! This mechanism is designed to handle\n" + " programs stuck in infinite loops gracefully. The -timeout option\n" + " can be used to change the timeout threshold or disable it completely\n" + " (with -timeout=0). This message is only displayed once.\n"; + FirstTimeout = false; + } + } + + if (AppendProgramExitCode) { + std::ofstream outFile(OutputFile.c_str(), std::ios_base::app); + outFile << "exit " << RetVal << '\n'; + outFile.close(); + } + + if (ProgramExitedNonzero != 0) + *ProgramExitedNonzero = (RetVal != 0); + + // Return the filename we captured the output to. + return OutputFile; +} + +/// executeProgramSafely - Used to create reference output with the "safe" +/// backend, if reference output is not provided. +/// +std::string BugDriver::executeProgramSafely(std::string OutputFile) { + bool ProgramExitedNonzero; + std::string outFN = executeProgram(OutputFile, "", "", SafeInterpreter, + &ProgramExitedNonzero); + return outFN; +} + +std::string BugDriver::compileSharedObject(const std::string &BitcodeFile) { + assert(Interpreter && "Interpreter should have been created already!"); + sys::Path OutputFile; + + // Using the known-good backend. + GCC::FileType FT = SafeInterpreter->OutputCode(BitcodeFile, OutputFile); + + std::string SharedObjectFile; + if (gcc->MakeSharedObject(OutputFile.toString(), FT, + SharedObjectFile, AdditionalLinkerArgs)) + exit(1); + + // Remove the intermediate C file + OutputFile.eraseFromDisk(); + + return "./" + SharedObjectFile; +} + +/// createReferenceFile - calls compileProgram and then records the output +/// into ReferenceOutputFile. Returns true if reference file created, false +/// otherwise. Note: initializeExecutionEnvironment should be called BEFORE +/// this function. +/// +bool BugDriver::createReferenceFile(Module *M, const std::string &Filename) { + try { + compileProgram(Program); + } catch (ToolExecutionError &) { + return false; + } + try { + ReferenceOutputFile = executeProgramSafely(Filename); + std::cout << "\nReference output is: " << ReferenceOutputFile << "\n\n"; + } catch (ToolExecutionError &TEE) { + std::cerr << TEE.what(); + if (Interpreter != SafeInterpreter) { + std::cerr << "*** There is a bug running the \"safe\" backend. Either" + << " debug it (for example with the -run-cbe bugpoint option," + << " if CBE is being used as the \"safe\" backend), or fix the" + << " error some other way.\n"; + } + return false; + } + return true; +} + +/// diffProgram - This method executes the specified module and diffs the +/// output against the file specified by ReferenceOutputFile. If the output +/// is different, true is returned. If there is a problem with the code +/// generator (e.g., llc crashes), this will throw an exception. +/// +bool BugDriver::diffProgram(const std::string &BitcodeFile, + const std::string &SharedObject, + bool RemoveBitcode) { + bool ProgramExitedNonzero; + + // Execute the program, generating an output file... + sys::Path Output(executeProgram("", BitcodeFile, SharedObject, 0, + &ProgramExitedNonzero)); + + std::string Error; + bool FilesDifferent = false; + if (int Diff = DiffFilesWithTolerance(sys::Path(ReferenceOutputFile), + sys::Path(Output.toString()), + AbsTolerance, RelTolerance, &Error)) { + if (Diff == 2) { + std::cerr << "While diffing output: " << Error << '\n'; + exit(1); + } + FilesDifferent = true; + } + + // Remove the generated output. + Output.eraseFromDisk(); + + // Remove the bitcode file if we are supposed to. + if (RemoveBitcode) + sys::Path(BitcodeFile).eraseFromDisk(); + return FilesDifferent; +} + +bool BugDriver::isExecutingJIT() { + return InterpreterSel == RunJIT; +} + diff --git a/tools/bugpoint/ExtractFunction.cpp b/tools/bugpoint/ExtractFunction.cpp new file mode 100644 index 0000000..e4affbb --- /dev/null +++ b/tools/bugpoint/ExtractFunction.cpp @@ -0,0 +1,375 @@ +//===- ExtractFunction.cpp - Extract a function from Program --------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements several methods that are used to extract functions, +// loops, or portions of a module from the rest of the module. +// +//===----------------------------------------------------------------------===// + +#include "BugDriver.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/Module.h" +#include "llvm/PassManager.h" +#include "llvm/Pass.h" +#include "llvm/Analysis/Verifier.h" +#include "llvm/Transforms/IPO.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Transforms/Utils/FunctionUtils.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FileUtilities.h" +#include "llvm/System/Path.h" +#include "llvm/System/Signals.h" +#include +#include +#include +using namespace llvm; + +namespace llvm { + bool DisableSimplifyCFG = false; +} // End llvm namespace + +namespace { + cl::opt + NoDCE ("disable-dce", + cl::desc("Do not use the -dce pass to reduce testcases")); + cl::opt + NoSCFG("disable-simplifycfg", cl::location(DisableSimplifyCFG), + cl::desc("Do not use the -simplifycfg pass to reduce testcases")); +} + +/// deleteInstructionFromProgram - This method clones the current Program and +/// deletes the specified instruction from the cloned module. It then runs a +/// series of cleanup passes (ADCE and SimplifyCFG) to eliminate any code which +/// depends on the value. The modified module is then returned. +/// +Module *BugDriver::deleteInstructionFromProgram(const Instruction *I, + unsigned Simplification) const { + Module *Result = CloneModule(Program); + + const BasicBlock *PBB = I->getParent(); + const Function *PF = PBB->getParent(); + + Module::iterator RFI = Result->begin(); // Get iterator to corresponding fn + std::advance(RFI, std::distance(PF->getParent()->begin(), + Module::const_iterator(PF))); + + Function::iterator RBI = RFI->begin(); // Get iterator to corresponding BB + std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB))); + + BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst + std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I))); + Instruction *TheInst = RI; // Got the corresponding instruction! + + // If this instruction produces a value, replace any users with null values + if (isa(TheInst->getType())) + TheInst->replaceAllUsesWith(UndefValue::get(TheInst->getType())); + else if (TheInst->getType() != Type::VoidTy) + TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType())); + + // Remove the instruction from the program. + TheInst->getParent()->getInstList().erase(TheInst); + + + //writeProgramToFile("current.bc", Result); + + // Spiff up the output a little bit. + PassManager Passes; + // Make sure that the appropriate target data is always used... + Passes.add(new TargetData(Result)); + + /// FIXME: If this used runPasses() like the methods below, we could get rid + /// of the -disable-* options! + if (Simplification > 1 && !NoDCE) + Passes.add(createDeadCodeEliminationPass()); + if (Simplification && !DisableSimplifyCFG) + Passes.add(createCFGSimplificationPass()); // Delete dead control flow + + Passes.add(createVerifierPass()); + Passes.run(*Result); + return Result; +} + +static const PassInfo *getPI(Pass *P) { + const PassInfo *PI = P->getPassInfo(); + delete P; + return PI; +} + +/// performFinalCleanups - This method clones the current Program and performs +/// a series of cleanups intended to get rid of extra cruft on the module +/// before handing it to the user. +/// +Module *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) { + // Make all functions external, so GlobalDCE doesn't delete them... + for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) + I->setLinkage(GlobalValue::ExternalLinkage); + + std::vector CleanupPasses; + CleanupPasses.push_back(getPI(createGlobalDCEPass())); + CleanupPasses.push_back(getPI(createDeadTypeEliminationPass())); + + if (MayModifySemantics) + CleanupPasses.push_back(getPI(createDeadArgHackingPass())); + else + CleanupPasses.push_back(getPI(createDeadArgEliminationPass())); + + Module *New = runPassesOn(M, CleanupPasses); + if (New == 0) { + std::cerr << "Final cleanups failed. Sorry. :( Please report a bug!\n"; + return M; + } + delete M; + return New; +} + + +/// ExtractLoop - Given a module, extract up to one loop from it into a new +/// function. This returns null if there are no extractable loops in the +/// program or if the loop extractor crashes. +Module *BugDriver::ExtractLoop(Module *M) { + std::vector LoopExtractPasses; + LoopExtractPasses.push_back(getPI(createSingleLoopExtractorPass())); + + Module *NewM = runPassesOn(M, LoopExtractPasses); + if (NewM == 0) { + Module *Old = swapProgramIn(M); + std::cout << "*** Loop extraction failed: "; + EmitProgressBitcode("loopextraction", true); + std::cout << "*** Sorry. :( Please report a bug!\n"; + swapProgramIn(Old); + return 0; + } + + // Check to see if we created any new functions. If not, no loops were + // extracted and we should return null. Limit the number of loops we extract + // to avoid taking forever. + static unsigned NumExtracted = 32; + if (M->size() == NewM->size() || --NumExtracted == 0) { + delete NewM; + return 0; + } else { + assert(M->size() < NewM->size() && "Loop extract removed functions?"); + Module::iterator MI = NewM->begin(); + for (unsigned i = 0, e = M->size(); i != e; ++i) + ++MI; + } + + return NewM; +} + + +// DeleteFunctionBody - "Remove" the function by deleting all of its basic +// blocks, making it external. +// +void llvm::DeleteFunctionBody(Function *F) { + // delete the body of the function... + F->deleteBody(); + assert(F->isDeclaration() && "This didn't make the function external!"); +} + +/// GetTorInit - Given a list of entries for static ctors/dtors, return them +/// as a constant array. +static Constant *GetTorInit(std::vector > &TorList) { + assert(!TorList.empty() && "Don't create empty tor list!"); + std::vector ArrayElts; + for (unsigned i = 0, e = TorList.size(); i != e; ++i) { + std::vector Elts; + Elts.push_back(ConstantInt::get(Type::Int32Ty, TorList[i].second)); + Elts.push_back(TorList[i].first); + ArrayElts.push_back(ConstantStruct::get(Elts)); + } + return ConstantArray::get(ArrayType::get(ArrayElts[0]->getType(), + ArrayElts.size()), + ArrayElts); +} + +/// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and +/// M1 has all of the global variables. If M2 contains any functions that are +/// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and +/// prune appropriate entries out of M1s list. +static void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2, + DenseMap ValueMap) { + GlobalVariable *GV = M1->getNamedGlobal(GlobalName); + if (!GV || GV->isDeclaration() || GV->hasLocalLinkage() || + !GV->use_empty()) return; + + std::vector > M1Tors, M2Tors; + ConstantArray *InitList = dyn_cast(GV->getInitializer()); + if (!InitList) return; + + for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) { + if (ConstantStruct *CS = dyn_cast(InitList->getOperand(i))){ + if (CS->getNumOperands() != 2) return; // Not array of 2-element structs. + + if (CS->getOperand(1)->isNullValue()) + break; // Found a null terminator, stop here. + + ConstantInt *CI = dyn_cast(CS->getOperand(0)); + int Priority = CI ? CI->getSExtValue() : 0; + + Constant *FP = CS->getOperand(1); + if (ConstantExpr *CE = dyn_cast(FP)) + if (CE->isCast()) + FP = CE->getOperand(0); + if (Function *F = dyn_cast(FP)) { + if (!F->isDeclaration()) + M1Tors.push_back(std::make_pair(F, Priority)); + else { + // Map to M2's version of the function. + F = cast(ValueMap[F]); + M2Tors.push_back(std::make_pair(F, Priority)); + } + } + } + } + + GV->eraseFromParent(); + if (!M1Tors.empty()) { + Constant *M1Init = GetTorInit(M1Tors); + new GlobalVariable(M1Init->getType(), false, GlobalValue::AppendingLinkage, + M1Init, GlobalName, M1); + } + + GV = M2->getNamedGlobal(GlobalName); + assert(GV && "Not a clone of M1?"); + assert(GV->use_empty() && "llvm.ctors shouldn't have uses!"); + + GV->eraseFromParent(); + if (!M2Tors.empty()) { + Constant *M2Init = GetTorInit(M2Tors); + new GlobalVariable(M2Init->getType(), false, GlobalValue::AppendingLinkage, + M2Init, GlobalName, M2); + } +} + + +/// SplitFunctionsOutOfModule - Given a module and a list of functions in the +/// module, split the functions OUT of the specified module, and place them in +/// the new module. +Module * +llvm::SplitFunctionsOutOfModule(Module *M, + const std::vector &F, + DenseMap &ValueMap) { + // Make sure functions & globals are all external so that linkage + // between the two modules will work. + for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) + I->setLinkage(GlobalValue::ExternalLinkage); + for (Module::global_iterator I = M->global_begin(), E = M->global_end(); + I != E; ++I) { + if (I->hasName() && *I->getNameStart() == '\01') + I->setName(I->getNameStart()+1, I->getNameLen()-1); + I->setLinkage(GlobalValue::ExternalLinkage); + } + + DenseMap NewValueMap; + Module *New = CloneModule(M, NewValueMap); + + // Make sure global initializers exist only in the safe module (CBE->.so) + for (Module::global_iterator I = New->global_begin(), E = New->global_end(); + I != E; ++I) + I->setInitializer(0); // Delete the initializer to make it external + + // Remove the Test functions from the Safe module + std::set TestFunctions; + for (unsigned i = 0, e = F.size(); i != e; ++i) { + Function *TNOF = cast(ValueMap[F[i]]); + DEBUG(std::cerr << "Removing function "); + DEBUG(WriteAsOperand(std::cerr, TNOF, false)); + DEBUG(std::cerr << "\n"); + TestFunctions.insert(cast(NewValueMap[TNOF])); + DeleteFunctionBody(TNOF); // Function is now external in this module! + } + + + // Remove the Safe functions from the Test module + for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I) + if (!TestFunctions.count(I)) + DeleteFunctionBody(I); + + + // Make sure that there is a global ctor/dtor array in both halves of the + // module if they both have static ctor/dtor functions. + SplitStaticCtorDtor("llvm.global_ctors", M, New, NewValueMap); + SplitStaticCtorDtor("llvm.global_dtors", M, New, NewValueMap); + + return New; +} + +//===----------------------------------------------------------------------===// +// Basic Block Extraction Code +//===----------------------------------------------------------------------===// + +/// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks +/// into their own functions. The only detail is that M is actually a module +/// cloned from the one the BBs are in, so some mapping needs to be performed. +/// If this operation fails for some reason (ie the implementation is buggy), +/// this function should return null, otherwise it returns a new Module. +Module *BugDriver::ExtractMappedBlocksFromModule(const + std::vector &BBs, + Module *M) { + char *ExtraArg = NULL; + + sys::Path uniqueFilename("bugpoint-extractblocks"); + std::string ErrMsg; + if (uniqueFilename.createTemporaryFileOnDisk(true, &ErrMsg)) { + std::cout << "*** Basic Block extraction failed!\n"; + std::cerr << "Error creating temporary file: " << ErrMsg << "\n"; + M = swapProgramIn(M); + EmitProgressBitcode("basicblockextractfail", true); + swapProgramIn(M); + return 0; + } + sys::RemoveFileOnSignal(uniqueFilename); + + std::ofstream BlocksToNotExtractFile(uniqueFilename.c_str()); + if (!BlocksToNotExtractFile) { + std::cout << "*** Basic Block extraction failed!\n"; + std::cerr << "Error writing list of blocks to not extract: " << ErrMsg + << "\n"; + M = swapProgramIn(M); + EmitProgressBitcode("basicblockextractfail", true); + swapProgramIn(M); + return 0; + } + for (std::vector::const_iterator I = BBs.begin(), E = BBs.end(); + I != E; ++I) { + BasicBlock *BB = *I; + // If the BB doesn't have a name, give it one so we have something to key + // off of. + if (!BB->hasName()) BB->setName("tmpbb"); + BlocksToNotExtractFile << BB->getParent()->getName() << " " + << BB->getName() << "\n"; + } + BlocksToNotExtractFile.close(); + + const char *uniqueFN = uniqueFilename.c_str(); + ExtraArg = (char*)malloc(23 + strlen(uniqueFN)); + strcat(strcpy(ExtraArg, "--extract-blocks-file="), uniqueFN); + + std::vector PI; + std::vector EmptyBBs; // This parameter is ignored. + PI.push_back(getPI(createBlockExtractorPass(EmptyBBs))); + Module *Ret = runPassesOn(M, PI, false, 1, &ExtraArg); + + if (uniqueFilename.exists()) + uniqueFilename.eraseFromDisk(); // Free disk space + free(ExtraArg); + + if (Ret == 0) { + std::cout << "*** Basic Block extraction failed, please report a bug!\n"; + M = swapProgramIn(M); + EmitProgressBitcode("basicblockextractfail", true); + swapProgramIn(M); + } + return Ret; +} diff --git a/tools/bugpoint/FindBugs.cpp b/tools/bugpoint/FindBugs.cpp new file mode 100644 index 0000000..e42cce4 --- /dev/null +++ b/tools/bugpoint/FindBugs.cpp @@ -0,0 +1,112 @@ +//===-- FindBugs.cpp - Run Many Different Optimizations -------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines an interface that allows bugpoint to choose different +// combinations of optimizations to run on the selected input. Bugpoint will +// run these optimizations and record the success/failure of each. This way +// we can hopefully spot bugs in the optimizations. +// +//===----------------------------------------------------------------------===// + +#include "BugDriver.h" +#include "ToolRunner.h" +#include "llvm/Pass.h" +#include +#include +#include +using namespace llvm; + +/// runManyPasses - Take the specified pass list and create different +/// combinations of passes to compile the program with. Compile the program with +/// each set and mark test to see if it compiled correctly. If the passes +/// compiled correctly output nothing and rearrange the passes into a new order. +/// If the passes did not compile correctly, output the command required to +/// recreate the failure. This returns true if a compiler error is found. +/// +bool BugDriver::runManyPasses(const std::vector &AllPasses) { + setPassesToRun(AllPasses); + std::cout << "Starting bug finding procedure...\n\n"; + + // Creating a reference output if necessary + if (initializeExecutionEnvironment()) return false; + + std::cout << "\n"; + if (ReferenceOutputFile.empty()) { + std::cout << "Generating reference output from raw program: \n"; + if (!createReferenceFile(Program)) + return false; + } + + srand(time(NULL)); + + unsigned num = 1; + while(1) { + // + // Step 1: Randomize the order of the optimizer passes. + // + std::random_shuffle(PassesToRun.begin(), PassesToRun.end()); + + // + // Step 2: Run optimizer passes on the program and check for success. + // + std::cout << "Running selected passes on program to test for crash: "; + for(int i = 0, e = PassesToRun.size(); i != e; i++) { + std::cout << "-" << PassesToRun[i]->getPassArgument( )<< " "; + } + + std::string Filename; + if(runPasses(PassesToRun, Filename, false)) { + std::cout << "\n"; + std::cout << "Optimizer passes caused failure!\n\n"; + debugOptimizerCrash(); + return true; + } else { + std::cout << "Combination " << num << " optimized successfully!\n"; + } + + // + // Step 3: Compile the optimized code. + // + std::cout << "Running the code generator to test for a crash: "; + try { + compileProgram(Program); + std::cout << '\n'; + } catch (ToolExecutionError &TEE) { + std::cout << "\n*** compileProgram threw an exception: "; + std::cout << TEE.what(); + return debugCodeGeneratorCrash(); + } + + // + // Step 4: Run the program and compare its output to the reference + // output (created above). + // + std::cout << "*** Checking if passes caused miscompliation:\n"; + try { + if (diffProgram(Filename, "", false)) { + std::cout << "\n*** diffProgram returned true!\n"; + debugMiscompilation(); + return true; + } else { + std::cout << "\n*** diff'd output matches!\n"; + } + } catch (ToolExecutionError &TEE) { + std::cerr << TEE.what(); + debugCodeGeneratorCrash(); + return true; + } + + sys::Path(Filename).eraseFromDisk(); + + std::cout << "\n\n"; + num++; + } //end while + + // Unreachable. +} diff --git a/tools/bugpoint/ListReducer.h b/tools/bugpoint/ListReducer.h new file mode 100644 index 0000000..de3f389 --- /dev/null +++ b/tools/bugpoint/ListReducer.h @@ -0,0 +1,189 @@ +//===- ListReducer.h - Trim down list while retaining property --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This class is to be used as a base class for operations that want to zero in +// on a subset of the input which still causes the bug we are tracking. +// +//===----------------------------------------------------------------------===// + +#ifndef BUGPOINT_LIST_REDUCER_H +#define BUGPOINT_LIST_REDUCER_H + +#include +#include +#include +#include + +namespace llvm { + + extern bool BugpointIsInterrupted; + +template +struct ListReducer { + enum TestResult { + NoFailure, // No failure of the predicate was detected + KeepSuffix, // The suffix alone satisfies the predicate + KeepPrefix // The prefix alone satisfies the predicate + }; + + virtual ~ListReducer() {} + + // doTest - This virtual function should be overriden by subclasses to + // implement the test desired. The testcase is only required to test to see + // if the Kept list still satisfies the property, but if it is going to check + // the prefix anyway, it can. + // + virtual TestResult doTest(std::vector &Prefix, + std::vector &Kept) = 0; + + // reduceList - This function attempts to reduce the length of the specified + // list while still maintaining the "test" property. This is the core of the + // "work" that bugpoint does. + // + bool reduceList(std::vector &TheList) { + std::vector empty; + std::srand(0x6e5ea738); // Seed the random number generator + switch (doTest(TheList, empty)) { + case KeepPrefix: + if (TheList.size() == 1) // we are done, it's the base case and it fails + return true; + else + break; // there's definitely an error, but we need to narrow it down + + case KeepSuffix: + // cannot be reached! + std::cerr << "bugpoint ListReducer internal error: selected empty set.\n"; + abort(); + + case NoFailure: + return false; // there is no failure with the full set of passes/funcs! + } + + // Maximal number of allowed splitting iterations, + // before the elements are randomly shuffled. + const unsigned MaxIterationsWithoutProgress = 3; + bool ShufflingEnabled = true; + +Backjump: + unsigned MidTop = TheList.size(); + unsigned MaxIterations = MaxIterationsWithoutProgress; + unsigned NumOfIterationsWithoutProgress = 0; + while (MidTop > 1) { // Binary split reduction loop + // Halt if the user presses ctrl-c. + if (BugpointIsInterrupted) { + std::cerr << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; + return true; + } + + // If the loop doesn't make satisfying progress, try shuffling. + // The purpose of shuffling is to avoid the heavy tails of the + // distribution (improving the speed of convergence). + if (ShufflingEnabled && + NumOfIterationsWithoutProgress > MaxIterations) { + std::vector ShuffledList(TheList); + std::random_shuffle(ShuffledList.begin(), ShuffledList.end()); + std::cerr << "\n\n*** Testing shuffled set...\n\n"; + // Check that random shuffle doesn't loose the bug + if (doTest(ShuffledList, empty) == KeepPrefix) { + // If the bug is still here, use the shuffled list. + TheList.swap(ShuffledList); + MidTop = TheList.size(); + // Must increase the shuffling treshold to avoid the small + // probability of inifinite looping without making progress. + MaxIterations += 2; + std::cerr << "\n\n*** Shuffling does not hide the bug...\n\n"; + } else { + ShufflingEnabled = false; // Disable shuffling further on + std::cerr << "\n\n*** Shuffling hides the bug...\n\n"; + } + NumOfIterationsWithoutProgress = 0; + } + + unsigned Mid = MidTop / 2; + std::vector Prefix(TheList.begin(), TheList.begin()+Mid); + std::vector Suffix(TheList.begin()+Mid, TheList.end()); + + switch (doTest(Prefix, Suffix)) { + case KeepSuffix: + // The property still holds. We can just drop the prefix elements, and + // shorten the list to the "kept" elements. + TheList.swap(Suffix); + MidTop = TheList.size(); + // Reset progress treshold and progress counter + MaxIterations = MaxIterationsWithoutProgress; + NumOfIterationsWithoutProgress = 0; + break; + case KeepPrefix: + // The predicate still holds, shorten the list to the prefix elements. + TheList.swap(Prefix); + MidTop = TheList.size(); + // Reset progress treshold and progress counter + MaxIterations = MaxIterationsWithoutProgress; + NumOfIterationsWithoutProgress = 0; + break; + case NoFailure: + // Otherwise the property doesn't hold. Some of the elements we removed + // must be necessary to maintain the property. + MidTop = Mid; + NumOfIterationsWithoutProgress++; + break; + } + } + + // Probability of backjumping from the trimming loop back to the binary + // split reduction loop. + const int BackjumpProbability = 10; + + // Okay, we trimmed as much off the top and the bottom of the list as we + // could. If there is more than two elements in the list, try deleting + // interior elements and testing that. + // + if (TheList.size() > 2) { + bool Changed = true; + std::vector EmptyList; + while (Changed) { // Trimming loop. + Changed = false; + + // If the binary split reduction loop made an unfortunate sequence of + // splits, the trimming loop might be left off with a huge number of + // remaining elements (large search space). Backjumping out of that + // search space and attempting a different split can significantly + // improve the convergence speed. + if (std::rand() % 100 < BackjumpProbability) + goto Backjump; + + for (unsigned i = 1; i < TheList.size()-1; ++i) { // Check interior elts + if (BugpointIsInterrupted) { + std::cerr << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; + return true; + } + + std::vector TestList(TheList); + TestList.erase(TestList.begin()+i); + + if (doTest(EmptyList, TestList) == KeepSuffix) { + // We can trim down the list! + TheList.swap(TestList); + --i; // Don't skip an element of the list + Changed = true; + } + } + // This can take a long time if left uncontrolled. For now, don't + // iterate. + break; + } + } + + return true; // there are some failure and we've narrowed them down + } +}; + +} // End llvm namespace + +#endif diff --git a/tools/bugpoint/Makefile b/tools/bugpoint/Makefile new file mode 100644 index 0000000..b821b6c --- /dev/null +++ b/tools/bugpoint/Makefile @@ -0,0 +1,17 @@ +##===- tools/bugpoint/Makefile -----------------------------*- Makefile -*-===## +# +# The LLVM Compiler Infrastructure +# +# This file is distributed under the University of Illinois Open Source +# License. See LICENSE.TXT for details. +# +##===----------------------------------------------------------------------===## +LEVEL = ../.. + +TOOLNAME = bugpoint + +LINK_COMPONENTS := asmparser instrumentation scalaropts ipo \ + linker bitreader bitwriter +REQUIRES_EH := 1 + +include $(LEVEL)/Makefile.common diff --git a/tools/bugpoint/Miscompilation.cpp b/tools/bugpoint/Miscompilation.cpp new file mode 100644 index 0000000..7e8ff78 --- /dev/null +++ b/tools/bugpoint/Miscompilation.cpp @@ -0,0 +1,932 @@ +//===- Miscompilation.cpp - Debug program miscompilations -----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements optimizer and code generation miscompilation debugging +// support. +// +//===----------------------------------------------------------------------===// + +#include "BugDriver.h" +#include "ListReducer.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/Instructions.h" +#include "llvm/Linker.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Analysis/Verifier.h" +#include "llvm/Support/Mangler.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/FileUtilities.h" +#include "llvm/Config/config.h" // for HAVE_LINK_R +using namespace llvm; + +namespace llvm { + extern cl::list InputArgv; +} + +namespace { + static llvm::cl::opt + DisableLoopExtraction("disable-loop-extraction", + cl::desc("Don't extract loops when searching for miscompilations"), + cl::init(false)); + + class ReduceMiscompilingPasses : public ListReducer { + BugDriver &BD; + public: + ReduceMiscompilingPasses(BugDriver &bd) : BD(bd) {} + + virtual TestResult doTest(std::vector &Prefix, + std::vector &Suffix); + }; +} + +/// TestResult - After passes have been split into a test group and a control +/// group, see if they still break the program. +/// +ReduceMiscompilingPasses::TestResult +ReduceMiscompilingPasses::doTest(std::vector &Prefix, + std::vector &Suffix) { + // First, run the program with just the Suffix passes. If it is still broken + // with JUST the kept passes, discard the prefix passes. + std::cout << "Checking to see if '" << getPassesString(Suffix) + << "' compile correctly: "; + + std::string BitcodeResult; + if (BD.runPasses(Suffix, BitcodeResult, false/*delete*/, true/*quiet*/)) { + std::cerr << " Error running this sequence of passes" + << " on the input program!\n"; + BD.setPassesToRun(Suffix); + BD.EmitProgressBitcode("pass-error", false); + exit(BD.debugOptimizerCrash()); + } + + // Check to see if the finished program matches the reference output... + if (BD.diffProgram(BitcodeResult, "", true /*delete bitcode*/)) { + std::cout << " nope.\n"; + if (Suffix.empty()) { + std::cerr << BD.getToolName() << ": I'm confused: the test fails when " + << "no passes are run, nondeterministic program?\n"; + exit(1); + } + return KeepSuffix; // Miscompilation detected! + } + std::cout << " yup.\n"; // No miscompilation! + + if (Prefix.empty()) return NoFailure; + + // Next, see if the program is broken if we run the "prefix" passes first, + // then separately run the "kept" passes. + std::cout << "Checking to see if '" << getPassesString(Prefix) + << "' compile correctly: "; + + // If it is not broken with the kept passes, it's possible that the prefix + // passes must be run before the kept passes to break it. If the program + // WORKS after the prefix passes, but then fails if running the prefix AND + // kept passes, we can update our bitcode file to include the result of the + // prefix passes, then discard the prefix passes. + // + if (BD.runPasses(Prefix, BitcodeResult, false/*delete*/, true/*quiet*/)) { + std::cerr << " Error running this sequence of passes" + << " on the input program!\n"; + BD.setPassesToRun(Prefix); + BD.EmitProgressBitcode("pass-error", false); + exit(BD.debugOptimizerCrash()); + } + + // If the prefix maintains the predicate by itself, only keep the prefix! + if (BD.diffProgram(BitcodeResult)) { + std::cout << " nope.\n"; + sys::Path(BitcodeResult).eraseFromDisk(); + return KeepPrefix; + } + std::cout << " yup.\n"; // No miscompilation! + + // Ok, so now we know that the prefix passes work, try running the suffix + // passes on the result of the prefix passes. + // + Module *PrefixOutput = ParseInputFile(BitcodeResult); + if (PrefixOutput == 0) { + std::cerr << BD.getToolName() << ": Error reading bitcode file '" + << BitcodeResult << "'!\n"; + exit(1); + } + sys::Path(BitcodeResult).eraseFromDisk(); // No longer need the file on disk + + // Don't check if there are no passes in the suffix. + if (Suffix.empty()) + return NoFailure; + + std::cout << "Checking to see if '" << getPassesString(Suffix) + << "' passes compile correctly after the '" + << getPassesString(Prefix) << "' passes: "; + + Module *OriginalInput = BD.swapProgramIn(PrefixOutput); + if (BD.runPasses(Suffix, BitcodeResult, false/*delete*/, true/*quiet*/)) { + std::cerr << " Error running this sequence of passes" + << " on the input program!\n"; + BD.setPassesToRun(Suffix); + BD.EmitProgressBitcode("pass-error", false); + exit(BD.debugOptimizerCrash()); + } + + // Run the result... + if (BD.diffProgram(BitcodeResult, "", true/*delete bitcode*/)) { + std::cout << " nope.\n"; + delete OriginalInput; // We pruned down the original input... + return KeepSuffix; + } + + // Otherwise, we must not be running the bad pass anymore. + std::cout << " yup.\n"; // No miscompilation! + delete BD.swapProgramIn(OriginalInput); // Restore orig program & free test + return NoFailure; +} + +namespace { + class ReduceMiscompilingFunctions : public ListReducer { + BugDriver &BD; + bool (*TestFn)(BugDriver &, Module *, Module *); + public: + ReduceMiscompilingFunctions(BugDriver &bd, + bool (*F)(BugDriver &, Module *, Module *)) + : BD(bd), TestFn(F) {} + + virtual TestResult doTest(std::vector &Prefix, + std::vector &Suffix) { + if (!Suffix.empty() && TestFuncs(Suffix)) + return KeepSuffix; + if (!Prefix.empty() && TestFuncs(Prefix)) + return KeepPrefix; + return NoFailure; + } + + bool TestFuncs(const std::vector &Prefix); + }; +} + +/// 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); + M2 = CloneModule(M2); + } + if (Linker::LinkModules(M1, M2, &ErrorMsg)) { + std::cerr << BD.getToolName() << ": Error linking modules together:" + << ErrorMsg << '\n'; + exit(1); + } + delete M2; // We are done with this module. + + Module *OldProgram = BD.swapProgramIn(M1); + + // Execute the program. If it does not match the expected output, we must + // return true. + bool Broken = BD.diffProgram(); + + // Delete the linked module & restore the original + BD.swapProgramIn(OldProgram); + delete M1; + return Broken; +} + +/// TestFuncs - split functions in a Module into two groups: those that are +/// under consideration for miscompilation vs. those that are not, and test +/// accordingly. Each group of functions becomes a separate Module. +/// +bool ReduceMiscompilingFunctions::TestFuncs(const std::vector&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'; + + // Split the module into the two halves of the program we want. + DenseMap ValueMap; + Module *ToNotOptimize = CloneModule(BD.getProgram(), ValueMap); + Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, Funcs, + ValueMap); + + // Run the predicate, note that the predicate will delete both input modules. + return TestFn(BD, ToOptimize, ToNotOptimize); +} + +/// DisambiguateGlobalSymbols - Mangle symbols to guarantee uniqueness by +/// modifying predominantly internal symbols rather than external ones. +/// +static void DisambiguateGlobalSymbols(Module *M) { + // Try not to cause collisions by minimizing chances of renaming an + // already-external symbol, so take in external globals and functions as-is. + // The code should work correctly without disambiguation (assuming the same + // mangler is used by the two code generators), but having symbols with the + // same name causes warnings to be emitted by the code generator. + Mangler Mang(*M); + // Agree with the CBE on symbol naming + Mang.markCharUnacceptable('.'); + Mang.setPreserveAsmNames(true); + for (Module::global_iterator I = M->global_begin(), E = M->global_end(); + I != E; ++I) + I->setName(Mang.getValueName(I)); + for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) + I->setName(Mang.getValueName(I)); +} + +/// 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, + bool (*TestFn)(BugDriver &, Module *, Module *), + std::vector &MiscompiledFunctions) { + bool MadeChange = false; + while (1) { + if (BugpointIsInterrupted) return MadeChange; + + DenseMap ValueMap; + Module *ToNotOptimize = CloneModule(BD.getProgram(), ValueMap); + Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, + MiscompiledFunctions, + ValueMap); + 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; + } + + std::cerr << "Extracted a loop from the breaking portion of the program.\n"; + + // 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. + AbstractInterpreter *AI = BD.switchToSafeInterpreter(); + if (TestMergedProgram(BD, ToOptimizeLoopExtracted, ToNotOptimize, false)) { + BD.switchToInterpreter(AI); + + // 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"; + + BD.writeProgramToFile("bugpoint-loop-extract-fail-tno.bc", ToNotOptimize); + BD.writeProgramToFile("bugpoint-loop-extract-fail-to.bc", ToOptimize); + BD.writeProgramToFile("bugpoint-loop-extract-fail-to-le.bc", + ToOptimizeLoopExtracted); + + std::cerr << "Please submit the bugpoint-loop-extract-fail-*.bc files.\n"; + delete ToOptimize; + delete ToNotOptimize; + delete ToOptimizeLoopExtracted; + return MadeChange; + } + delete ToOptimize; + BD.switchToInterpreter(AI); + + std::cout << " Testing after loop extraction:\n"; + // Clone modules, the tester function will free them. + Module *TOLEBackup = CloneModule(ToOptimizeLoopExtracted); + Module *TNOBackup = CloneModule(ToNotOptimize); + if (!TestFn(BD, ToOptimizeLoopExtracted, ToNotOptimize)) { + std::cout << "*** 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 TOLEBackup; + delete TNOBackup; + return MadeChange; + } + ToOptimizeLoopExtracted = TOLEBackup; + ToNotOptimize = TNOBackup; + + std::cout << "*** Loop extraction successful!\n"; + + std::vector > MisCompFunctions; + for (Module::iterator I = ToOptimizeLoopExtracted->begin(), + E = ToOptimizeLoopExtracted->end(); I != E; ++I) + if (!I->isDeclaration()) + MisCompFunctions.push_back(std::make_pair(I->getName(), + I->getFunctionType())); + + // 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 (Linker::LinkModules(ToNotOptimize, ToOptimizeLoopExtracted, &ErrorMsg)){ + std::cerr << BD.getToolName() << ": Error linking modules together:" + << ErrorMsg << '\n'; + exit(1); + } + delete ToOptimizeLoopExtracted; + + // 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 (unsigned i = 0, e = MisCompFunctions.size(); i != e; ++i) { + Function *NewF = ToNotOptimize->getFunction(MisCompFunctions[i].first); + + assert(NewF && "Function not found??"); + assert(NewF->getFunctionType() == MisCompFunctions[i].second && + "found wrong function type?"); + MiscompiledFunctions.push_back(NewF); + } + + BD.setNewProgram(ToNotOptimize); + MadeChange = true; + } +} + +namespace { + class ReduceMiscompiledBlocks : public ListReducer { + BugDriver &BD; + bool (*TestFn)(BugDriver &, Module *, Module *); + std::vector FunctionsBeingTested; + public: + ReduceMiscompiledBlocks(BugDriver &bd, + bool (*F)(BugDriver &, Module *, Module *), + const std::vector &Fns) + : BD(bd), TestFn(F), FunctionsBeingTested(Fns) {} + + virtual TestResult doTest(std::vector &Prefix, + std::vector &Suffix) { + if (!Suffix.empty() && TestFuncs(Suffix)) + return KeepSuffix; + if (TestFuncs(Prefix)) + return KeepPrefix; + return NoFailure; + } + + bool TestFuncs(const std::vector &Prefix); + }; +} + +/// TestFuncs - Extract all blocks for the miscompiled functions except for the +/// specified blocks. If the problem still exists, return true. +/// +bool ReduceMiscompiledBlocks::TestFuncs(const std::vector &BBs) { + // 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 all "; + if (!BBs.empty()) { + std::cout << "but these " << BBs.size() << " blocks are extracted: "; + for (unsigned i = 0, e = BBs.size() < 10 ? BBs.size() : 10; i != e; ++i) + std::cout << BBs[i]->getName() << " "; + if (BBs.size() > 10) std::cout << "..."; + } else { + std::cout << "blocks are extracted."; + } + std::cout << '\n'; + + // Split the module into the two halves of the program we want. + DenseMap ValueMap; + Module *ToNotOptimize = CloneModule(BD.getProgram(), ValueMap); + Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, + FunctionsBeingTested, + ValueMap); + + // Try the extraction. If it doesn't work, then the block extractor crashed + // or something, in which case bugpoint can't chase down this possibility. + if (Module *New = BD.ExtractMappedBlocksFromModule(BBs, ToOptimize)) { + delete ToOptimize; + // Run the predicate, not that the predicate will delete both input modules. + return TestFn(BD, New, ToNotOptimize); + } + delete ToOptimize; + delete ToNotOptimize; + return false; +} + + +/// ExtractBlocks - Given a reduced list of functions that still expose the bug, +/// extract as many basic blocks from the region as possible without obscuring +/// the bug. +/// +static bool ExtractBlocks(BugDriver &BD, + bool (*TestFn)(BugDriver &, Module *, Module *), + std::vector &MiscompiledFunctions) { + if (BugpointIsInterrupted) return false; + + std::vector Blocks; + for (unsigned i = 0, e = MiscompiledFunctions.size(); i != e; ++i) + for (Function::iterator I = MiscompiledFunctions[i]->begin(), + E = MiscompiledFunctions[i]->end(); I != E; ++I) + Blocks.push_back(I); + + // Use the list reducer to identify blocks that can be extracted without + // obscuring the bug. The Blocks list will end up containing blocks that must + // be retained from the original program. + unsigned OldSize = Blocks.size(); + + // Check to see if all blocks are extractible first. + if (ReduceMiscompiledBlocks(BD, TestFn, + MiscompiledFunctions).TestFuncs(std::vector())) { + Blocks.clear(); + } else { + ReduceMiscompiledBlocks(BD, TestFn,MiscompiledFunctions).reduceList(Blocks); + if (Blocks.size() == OldSize) + return false; + } + + DenseMap ValueMap; + Module *ProgClone = CloneModule(BD.getProgram(), ValueMap); + Module *ToExtract = SplitFunctionsOutOfModule(ProgClone, + MiscompiledFunctions, + ValueMap); + Module *Extracted = BD.ExtractMappedBlocksFromModule(Blocks, ToExtract); + if (Extracted == 0) { + // Weird, extraction should have worked. + std::cerr << "Nondeterministic problem extracting blocks??\n"; + delete ProgClone; + delete ToExtract; + return false; + } + + // Otherwise, block extraction succeeded. Link the two program fragments back + // together. + delete ToExtract; + + std::vector > MisCompFunctions; + for (Module::iterator I = Extracted->begin(), E = Extracted->end(); + I != E; ++I) + if (!I->isDeclaration()) + MisCompFunctions.push_back(std::make_pair(I->getName(), + I->getFunctionType())); + + std::string ErrorMsg; + if (Linker::LinkModules(ProgClone, Extracted, &ErrorMsg)) { + std::cerr << BD.getToolName() << ": Error linking modules together:" + << ErrorMsg << '\n'; + exit(1); + } + delete Extracted; + + // Set the new program and delete the old one. + BD.setNewProgram(ProgClone); + + // Update the list of miscompiled functions. + MiscompiledFunctions.clear(); + + for (unsigned i = 0, e = MisCompFunctions.size(); i != e; ++i) { + Function *NewF = ProgClone->getFunction(MisCompFunctions[i].first); + assert(NewF && "Function not found??"); + assert(NewF->getFunctionType() == MisCompFunctions[i].second && + "Function has wrong type??"); + MiscompiledFunctions.push_back(NewF); + } + + return true; +} + + +/// DebugAMiscompilation - This is a generic driver to narrow down +/// miscompilations, either in an optimization or a code generator. +/// +static std::vector +DebugAMiscompilation(BugDriver &BD, + bool (*TestFn)(BugDriver &, Module *, Module *)) { + // Okay, now that we have reduced the list of passes which are causing the + // failure, see if we can pin down which functions are being + // miscompiled... first build a list of all of the non-external functions in + // the program. + std::vector MiscompiledFunctions; + Module *Prog = BD.getProgram(); + for (Module::iterator I = Prog->begin(), E = Prog->end(); I != E; ++I) + if (!I->isDeclaration()) + MiscompiledFunctions.push_back(I); + + // Do the reduction... + if (!BugpointIsInterrupted) + ReduceMiscompilingFunctions(BD, TestFn).reduceList(MiscompiledFunctions); + + 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 (!BugpointIsInterrupted && !DisableLoopExtraction && + ExtractLoops(BD, TestFn, MiscompiledFunctions)) { + // Okay, we extracted some loops and the problem still appears. See if we + // can eliminate some of the created functions from being candidates. + + // Loop extraction can introduce functions with the same name (foo_code). + // Make sure to disambiguate the symbols so that when the program is split + // apart that we can link it back together again. + DisambiguateGlobalSymbols(BD.getProgram()); + + // Do the reduction... + if (!BugpointIsInterrupted) + ReduceMiscompilingFunctions(BD, TestFn).reduceList(MiscompiledFunctions); + + std::cout << "\n*** The following function" + << (MiscompiledFunctions.size() == 1 ? " is" : "s are") + << " being miscompiled: "; + PrintFunctionList(MiscompiledFunctions); + std::cout << '\n'; + } + + if (!BugpointIsInterrupted && + ExtractBlocks(BD, TestFn, MiscompiledFunctions)) { + // Okay, we extracted some blocks and the problem still appears. See if we + // can eliminate some of the created functions from being candidates. + + // Block extraction can introduce functions with the same name (foo_code). + // Make sure to disambiguate the symbols so that when the program is split + // apart that we can link it back together again. + DisambiguateGlobalSymbols(BD.getProgram()); + + // Do the reduction... + ReduceMiscompilingFunctions(BD, TestFn).reduceList(MiscompiledFunctions); + + std::cout << "\n*** The following function" + << (MiscompiledFunctions.size() == 1 ? " is" : "s are") + << " being miscompiled: "; + PrintFunctionList(MiscompiledFunctions); + std::cout << '\n'; + } + + return MiscompiledFunctions; +} + +/// TestOptimizer - This is the predicate function used to check to see if the +/// "Test" portion of the program is misoptimized. If so, return true. In any +/// case, both module arguments are deleted. +/// +static bool TestOptimizer(BugDriver &BD, Module *Test, Module *Safe) { + // 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(Test, BD.getPassesToRun(), + /*AutoDebugCrashes*/true); + std::cout << "done.\n"; + delete Test; + + std::cout << " Checking to see if the merged program executes correctly: "; + bool Broken = TestMergedProgram(BD, Optimized, Safe, true); + std::cout << (Broken ? " nope.\n" : " yup.\n"); + return Broken; +} + + +/// 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() { + // Make sure something was miscompiled... + if (!BugpointIsInterrupted) + if (!ReduceMiscompilingPasses(*this).reduceList(PassesToRun)) { + std::cerr << "*** Optimized program matches reference output! No problem" + << " detected...\nbugpoint can't help you with your problem!\n"; + return false; + } + + std::cout << "\n*** Found miscompiling pass" + << (getPassesToRun().size() == 1 ? "" : "es") << ": " + << getPassesString(getPassesToRun()) << '\n'; + EmitProgressBitcode("passinput"); + + std::vector MiscompiledFunctions = + DebugAMiscompilation(*this, TestOptimizer); + + // Output a bunch of bitcode files for the user... + std::cout << "Outputting reduced bitcode files which expose the problem:\n"; + DenseMap ValueMap; + Module *ToNotOptimize = CloneModule(getProgram(), ValueMap); + Module *ToOptimize = SplitFunctionsOutOfModule(ToNotOptimize, + MiscompiledFunctions, + ValueMap); + + std::cout << " Non-optimized portion: "; + ToNotOptimize = swapProgramIn(ToNotOptimize); + EmitProgressBitcode("tonotoptimize", true); + setNewProgram(ToNotOptimize); // Delete hacked module. + + std::cout << " Portion that is input to optimizer: "; + ToOptimize = swapProgramIn(ToOptimize); + EmitProgressBitcode("tooptimize"); + setNewProgram(ToOptimize); // Delete hacked module. + + return false; +} + +/// CleanupAndPrepareModules - Get the specified modules ready for code +/// generator testing. +/// +static void CleanupAndPrepareModules(BugDriver &BD, Module *&Test, + Module *Safe) { + // Clean up the modules, removing extra cruft that we don't need anymore... + Test = BD.performFinalCleanups(Test); + + // If we are executing the JIT, we have several nasty issues to take care of. + if (!BD.isExecutingJIT()) return; + + // First, if the main function is in the Safe module, we must add a stub to + // the Test module to call into it. Thus, we create a new function `main' + // which just calls the old one. + if (Function *oldMain = Safe->getFunction("main")) + if (!oldMain->isDeclaration()) { + // Rename it + oldMain->setName("llvm_bugpoint_old_main"); + // Create a NEW `main' function with same type in the test module. + Function *newMain = Function::Create(oldMain->getFunctionType(), + GlobalValue::ExternalLinkage, + "main", Test); + // Create an `oldmain' prototype in the test module, which will + // corresponds to the real main function in the same module. + Function *oldMainProto = Function::Create(oldMain->getFunctionType(), + GlobalValue::ExternalLinkage, + oldMain->getName(), Test); + // Set up and remember the argument list for the main function. + std::vector args; + for (Function::arg_iterator + I = newMain->arg_begin(), E = newMain->arg_end(), + OI = oldMain->arg_begin(); I != E; ++I, ++OI) { + I->setName(OI->getName()); // Copy argument names from oldMain + args.push_back(I); + } + + // Call the old main function and return its result + BasicBlock *BB = BasicBlock::Create("entry", newMain); + CallInst *call = CallInst::Create(oldMainProto, args.begin(), args.end(), + "", BB); + + // If the type of old function wasn't void, return value of call + ReturnInst::Create(call, BB); + } + + // The second nasty issue we must deal with in the JIT is that the Safe + // module cannot directly reference any functions defined in the test + // module. Instead, we use a JIT API call to dynamically resolve the + // symbol. + + // Add the resolver to the Safe module. + // Prototype: void *getPointerToNamedFunction(const char* Name) + Constant *resolverFunc = + Safe->getOrInsertFunction("getPointerToNamedFunction", + PointerType::getUnqual(Type::Int8Ty), + PointerType::getUnqual(Type::Int8Ty), (Type *)0); + + // Use the function we just added to get addresses of functions we need. + for (Module::iterator F = Safe->begin(), E = Safe->end(); F != E; ++F) { + if (F->isDeclaration() && !F->use_empty() && &*F != resolverFunc && + !F->isIntrinsic() /* ignore intrinsics */) { + Function *TestFn = Test->getFunction(F->getName()); + + // Don't forward functions which are external in the test module too. + if (TestFn && !TestFn->isDeclaration()) { + // 1. Add a string constant with its name to the global file + Constant *InitArray = ConstantArray::get(F->getName()); + GlobalVariable *funcName = + new GlobalVariable(InitArray->getType(), true /*isConstant*/, + GlobalValue::InternalLinkage, InitArray, + F->getName() + "_name", Safe); + + // 2. Use `GetElementPtr *funcName, 0, 0' to convert the string to an + // sbyte* so it matches the signature of the resolver function. + + // GetElementPtr *funcName, ulong 0, ulong 0 + std::vector GEPargs(2,Constant::getNullValue(Type::Int32Ty)); + Value *GEP = ConstantExpr::getGetElementPtr(funcName, &GEPargs[0], 2); + std::vector ResolverArgs; + ResolverArgs.push_back(GEP); + + // Rewrite uses of F in global initializers, etc. to uses of a wrapper + // function that dynamically resolves the calls to F via our JIT API + if (!F->use_empty()) { + // Create a new global to hold the cached function pointer. + Constant *NullPtr = ConstantPointerNull::get(F->getType()); + GlobalVariable *Cache = + new GlobalVariable(F->getType(), false,GlobalValue::InternalLinkage, + NullPtr,F->getName()+".fpcache", F->getParent()); + + // Construct a new stub function that will re-route calls to F + const FunctionType *FuncTy = F->getFunctionType(); + Function *FuncWrapper = Function::Create(FuncTy, + GlobalValue::InternalLinkage, + F->getName() + "_wrapper", + F->getParent()); + BasicBlock *EntryBB = BasicBlock::Create("entry", FuncWrapper); + BasicBlock *DoCallBB = BasicBlock::Create("usecache", FuncWrapper); + BasicBlock *LookupBB = BasicBlock::Create("lookupfp", FuncWrapper); + + // Check to see if we already looked up the value. + Value *CachedVal = new LoadInst(Cache, "fpcache", EntryBB); + Value *IsNull = new ICmpInst(ICmpInst::ICMP_EQ, CachedVal, + NullPtr, "isNull", EntryBB); + BranchInst::Create(LookupBB, DoCallBB, IsNull, EntryBB); + + // Resolve the call to function F via the JIT API: + // + // call resolver(GetElementPtr...) + CallInst *Resolver = + CallInst::Create(resolverFunc, ResolverArgs.begin(), + ResolverArgs.end(), "resolver", LookupBB); + + // Cast the result from the resolver to correctly-typed function. + CastInst *CastedResolver = + new BitCastInst(Resolver, + PointerType::getUnqual(F->getFunctionType()), + "resolverCast", LookupBB); + + // Save the value in our cache. + new StoreInst(CastedResolver, Cache, LookupBB); + BranchInst::Create(DoCallBB, LookupBB); + + PHINode *FuncPtr = PHINode::Create(NullPtr->getType(), + "fp", DoCallBB); + FuncPtr->addIncoming(CastedResolver, LookupBB); + FuncPtr->addIncoming(CachedVal, EntryBB); + + // Save the argument list. + std::vector Args; + for (Function::arg_iterator i = FuncWrapper->arg_begin(), + e = FuncWrapper->arg_end(); i != e; ++i) + Args.push_back(i); + + // Pass on the arguments to the real function, return its result + if (F->getReturnType() == Type::VoidTy) { + CallInst::Create(FuncPtr, Args.begin(), Args.end(), "", DoCallBB); + ReturnInst::Create(DoCallBB); + } else { + CallInst *Call = CallInst::Create(FuncPtr, Args.begin(), Args.end(), + "retval", DoCallBB); + ReturnInst::Create(Call, DoCallBB); + } + + // Use the wrapper function instead of the old function + F->replaceAllUsesWith(FuncWrapper); + } + } + } + } + + if (verifyModule(*Test) || verifyModule(*Safe)) { + std::cerr << "Bugpoint has a bug, which corrupted a module!!\n"; + abort(); + } +} + + + +/// TestCodeGenerator - This is the predicate function used to check to see if +/// the "Test" portion of the program is miscompiled by the code generator under +/// test. If so, return true. In any case, both module arguments are deleted. +/// +static bool TestCodeGenerator(BugDriver &BD, Module *Test, Module *Safe) { + CleanupAndPrepareModules(BD, Test, Safe); + + sys::Path TestModuleBC("bugpoint.test.bc"); + std::string ErrMsg; + if (TestModuleBC.makeUnique(true, &ErrMsg)) { + std::cerr << BD.getToolName() << "Error making unique filename: " + << ErrMsg << "\n"; + exit(1); + } + if (BD.writeProgramToFile(TestModuleBC.toString(), Test)) { + std::cerr << "Error writing bitcode to `" << TestModuleBC << "'\nExiting."; + exit(1); + } + delete Test; + + // Make the shared library + sys::Path SafeModuleBC("bugpoint.safe.bc"); + if (SafeModuleBC.makeUnique(true, &ErrMsg)) { + std::cerr << BD.getToolName() << "Error making unique filename: " + << ErrMsg << "\n"; + exit(1); + } + + if (BD.writeProgramToFile(SafeModuleBC.toString(), Safe)) { + std::cerr << "Error writing bitcode to `" << SafeModuleBC << "'\nExiting."; + exit(1); + } + std::string SharedObject = BD.compileSharedObject(SafeModuleBC.toString()); + delete Safe; + + // Run the code generator on the `Test' code, loading the shared library. + // The function returns whether or not the new output differs from reference. + int Result = BD.diffProgram(TestModuleBC.toString(), SharedObject, false); + + if (Result) + std::cerr << ": still failing!\n"; + else + std::cerr << ": didn't fail.\n"; + TestModuleBC.eraseFromDisk(); + SafeModuleBC.eraseFromDisk(); + sys::Path(SharedObject).eraseFromDisk(); + + return Result; +} + + +/// debugCodeGenerator - debug errors in LLC, LLI, or CBE. +/// +bool BugDriver::debugCodeGenerator() { + if ((void*)SafeInterpreter == (void*)Interpreter) { + std::string Result = executeProgramSafely("bugpoint.safe.out"); + std::cout << "\n*** The \"safe\" i.e. 'known good' backend cannot match " + << "the reference diff. This may be due to a\n front-end " + << "bug or a bug in the original program, but this can also " + << "happen if bugpoint isn't running the program with the " + << "right flags or input.\n I left the result of executing " + << "the program with the \"safe\" backend in this file for " + << "you: '" + << Result << "'.\n"; + return true; + } + + DisambiguateGlobalSymbols(Program); + + std::vector Funcs = DebugAMiscompilation(*this, TestCodeGenerator); + + // Split the module into the two halves of the program we want. + DenseMap ValueMap; + Module *ToNotCodeGen = CloneModule(getProgram(), ValueMap); + Module *ToCodeGen = SplitFunctionsOutOfModule(ToNotCodeGen, Funcs, ValueMap); + + // Condition the modules + CleanupAndPrepareModules(*this, ToCodeGen, ToNotCodeGen); + + sys::Path TestModuleBC("bugpoint.test.bc"); + std::string ErrMsg; + if (TestModuleBC.makeUnique(true, &ErrMsg)) { + std::cerr << getToolName() << "Error making unique filename: " + << ErrMsg << "\n"; + exit(1); + } + + if (writeProgramToFile(TestModuleBC.toString(), ToCodeGen)) { + std::cerr << "Error writing bitcode to `" << TestModuleBC << "'\nExiting."; + exit(1); + } + delete ToCodeGen; + + // Make the shared library + sys::Path SafeModuleBC("bugpoint.safe.bc"); + if (SafeModuleBC.makeUnique(true, &ErrMsg)) { + std::cerr << getToolName() << "Error making unique filename: " + << ErrMsg << "\n"; + exit(1); + } + + if (writeProgramToFile(SafeModuleBC.toString(), ToNotCodeGen)) { + std::cerr << "Error writing bitcode to `" << SafeModuleBC << "'\nExiting."; + exit(1); + } + std::string SharedObject = compileSharedObject(SafeModuleBC.toString()); + delete ToNotCodeGen; + + std::cout << "You can reproduce the problem with the command line: \n"; + if (isExecutingJIT()) { + std::cout << " lli -load " << SharedObject << " " << TestModuleBC; + } else { + std::cout << " llc -f " << TestModuleBC << " -o " << TestModuleBC<< ".s\n"; + std::cout << " gcc " << SharedObject << " " << TestModuleBC + << ".s -o " << TestModuleBC << ".exe"; +#if defined (HAVE_LINK_R) + std::cout << " -Wl,-R."; +#endif + std::cout << "\n"; + std::cout << " " << TestModuleBC << ".exe"; + } + for (unsigned i=0, e = InputArgv.size(); i != e; ++i) + std::cout << " " << InputArgv[i]; + std::cout << '\n'; + std::cout << "The shared object was created with:\n llc -march=c " + << SafeModuleBC << " -o temporary.c\n" + << " gcc -xc temporary.c -O2 -o " << SharedObject +#if defined(sparc) || defined(__sparc__) || defined(__sparcv9) + << " -G" // Compile a shared library, `-G' for Sparc +#else + << " -fPIC -shared" // `-shared' for Linux/X86, maybe others +#endif + << " -fno-strict-aliasing\n"; + + return false; +} diff --git a/tools/bugpoint/OptimizerDriver.cpp b/tools/bugpoint/OptimizerDriver.cpp new file mode 100644 index 0000000..3ded5e8 --- /dev/null +++ b/tools/bugpoint/OptimizerDriver.cpp @@ -0,0 +1,266 @@ +//===- OptimizerDriver.cpp - Allow BugPoint to run passes safely ----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines an interface that allows bugpoint to run various passes +// without the threat of a buggy pass corrupting bugpoint (of course, bugpoint +// may have its own bugs, but that's another story...). It achieves this by +// forking a copy of itself and having the child process do the optimizations. +// If this client dies, we can always fork a new one. :) +// +//===----------------------------------------------------------------------===// + +// Note: as a short term hack, the old Unix-specific code and platform- +// independent code co-exist via conditional compilation until it is verified +// that the new code works correctly on Unix. + +#include "BugDriver.h" +#include "llvm/Module.h" +#include "llvm/PassManager.h" +#include "llvm/Analysis/Verifier.h" +#include "llvm/Bitcode/ReaderWriter.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Support/FileUtilities.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Streams.h" +#include "llvm/System/Path.h" +#include "llvm/System/Program.h" +#include "llvm/Config/alloca.h" + +#define DONT_GET_PLUGIN_LOADER_OPTION +#include "llvm/Support/PluginLoader.h" + +#include +using namespace llvm; + + +namespace { + // ChildOutput - This option captures the name of the child output file that + // is set up by the parent bugpoint process + cl::opt ChildOutput("child-output", cl::ReallyHidden); + cl::opt UseValgrind("enable-valgrind", + cl::desc("Run optimizations through valgrind")); +} + +/// writeProgramToFile - This writes the current "Program" to the named bitcode +/// file. If an error occurs, true is returned. +/// +bool BugDriver::writeProgramToFile(const std::string &Filename, + Module *M) const { + std::ios::openmode io_mode = std::ios::out | std::ios::trunc | + std::ios::binary; + std::ofstream Out(Filename.c_str(), io_mode); + if (!Out.good()) return true; + + WriteBitcodeToFile(M ? M : Program, Out); + return false; +} + + +/// EmitProgressBitcode - This function is used to output the current Program +/// to a file named "bugpoint-ID.bc". +/// +void BugDriver::EmitProgressBitcode(const std::string &ID, bool NoFlyer) { + // Output the input to the current pass to a bitcode file, emit a message + // telling the user how to reproduce it: opt -foo blah.bc + // + std::string Filename = "bugpoint-" + ID + ".bc"; + if (writeProgramToFile(Filename)) { + cerr << "Error opening file '" << Filename << "' for writing!\n"; + return; + } + + cout << "Emitted bitcode to '" << Filename << "'\n"; + if (NoFlyer || PassesToRun.empty()) return; + cout << "\n*** You can reproduce the problem with: "; + cout << "opt " << Filename << " "; + cout << getPassesString(PassesToRun) << "\n"; +} + +int BugDriver::runPassesAsChild(const std::vector &Passes) { + + std::ios::openmode io_mode = std::ios::out | std::ios::trunc | + std::ios::binary; + std::ofstream OutFile(ChildOutput.c_str(), io_mode); + if (!OutFile.good()) { + cerr << "Error opening bitcode file: " << ChildOutput << "\n"; + return 1; + } + + PassManager PM; + // Make sure that the appropriate target data is always used... + PM.add(new TargetData(Program)); + + for (unsigned i = 0, e = Passes.size(); i != e; ++i) { + if (Passes[i]->getNormalCtor()) + PM.add(Passes[i]->getNormalCtor()()); + else + cerr << "Cannot create pass yet: " << Passes[i]->getPassName() << "\n"; + } + // Check that the module is well formed on completion of optimization + PM.add(createVerifierPass()); + + // Write bitcode out to disk as the last step... + PM.add(CreateBitcodeWriterPass(OutFile)); + + // Run all queued passes. + PM.run(*Program); + + return 0; +} + +cl::opt SilencePasses("silence-passes", cl::desc("Suppress output of running passes (both stdout and stderr)")); + +/// runPasses - Run the specified passes on Program, outputting a bitcode file +/// and writing the filename into OutputFile if successful. If the +/// optimizations fail for some reason (optimizer crashes), return true, +/// otherwise return false. If DeleteOutput is set to true, the bitcode is +/// deleted on success, and the filename string is undefined. This prints to +/// cout a single line message indicating whether compilation was successful or +/// failed. +/// +bool BugDriver::runPasses(const std::vector &Passes, + std::string &OutputFilename, bool DeleteOutput, + bool Quiet, unsigned NumExtraArgs, + const char * const *ExtraArgs) const { + // setup the output file name + cout << std::flush; + sys::Path uniqueFilename("bugpoint-output.bc"); + std::string ErrMsg; + if (uniqueFilename.makeUnique(true, &ErrMsg)) { + cerr << getToolName() << ": Error making unique filename: " + << ErrMsg << "\n"; + return(1); + } + OutputFilename = uniqueFilename.toString(); + + // set up the input file name + sys::Path inputFilename("bugpoint-input.bc"); + if (inputFilename.makeUnique(true, &ErrMsg)) { + cerr << getToolName() << ": Error making unique filename: " + << ErrMsg << "\n"; + return(1); + } + std::ios::openmode io_mode = std::ios::out | std::ios::trunc | + std::ios::binary; + std::ofstream InFile(inputFilename.c_str(), io_mode); + if (!InFile.good()) { + cerr << "Error opening bitcode file: " << inputFilename << "\n"; + return(1); + } + WriteBitcodeToFile(Program, InFile); + InFile.close(); + + // setup the child process' arguments + const char** args = (const char**) + alloca(sizeof(const char*) * + (Passes.size()+13+2*PluginLoader::getNumPlugins()+NumExtraArgs)); + int n = 0; + sys::Path tool = sys::Program::FindProgramByName(ToolName); + if (UseValgrind) { + args[n++] = "valgrind"; + args[n++] = "--error-exitcode=1"; + args[n++] = "-q"; + args[n++] = tool.c_str(); + } else + args[n++] = ToolName.c_str(); + + args[n++] = "-as-child"; + args[n++] = "-child-output"; + args[n++] = OutputFilename.c_str(); + std::vector pass_args; + for (unsigned i = 0, e = PluginLoader::getNumPlugins(); i != e; ++i) { + pass_args.push_back( std::string("-load")); + pass_args.push_back( PluginLoader::getPlugin(i)); + } + for (std::vector::const_iterator I = Passes.begin(), + E = Passes.end(); I != E; ++I ) + pass_args.push_back( std::string("-") + (*I)->getPassArgument() ); + for (std::vector::const_iterator I = pass_args.begin(), + E = pass_args.end(); I != E; ++I ) + args[n++] = I->c_str(); + args[n++] = inputFilename.c_str(); + for (unsigned i = 0; i < NumExtraArgs; ++i) + args[n++] = *ExtraArgs; + args[n++] = 0; + + sys::Path prog; + if (UseValgrind) + prog = sys::Program::FindProgramByName("valgrind"); + else + prog = tool; + + // Redirect stdout and stderr to nowhere if SilencePasses is given + sys::Path Nowhere; + const sys::Path *Redirects[3] = {0, &Nowhere, &Nowhere}; + + int result = sys::Program::ExecuteAndWait(prog, args, 0, (SilencePasses ? Redirects : 0), + Timeout, MemoryLimit, &ErrMsg); + + // If we are supposed to delete the bitcode file or if the passes crashed, + // remove it now. This may fail if the file was never created, but that's ok. + if (DeleteOutput || result != 0) + sys::Path(OutputFilename).eraseFromDisk(); + + // Remove the temporary input file as well + inputFilename.eraseFromDisk(); + + if (!Quiet) { + if (result == 0) + cout << "Success!\n"; + else if (result > 0) + cout << "Exited with error code '" << result << "'\n"; + else if (result < 0) { + if (result == -1) + cout << "Execute failed: " << ErrMsg << "\n"; + else + cout << "Crashed with signal #" << abs(result) << "\n"; + } + if (result & 0x01000000) + cout << "Dumped core\n"; + } + + // Was the child successful? + return result != 0; +} + + +/// runPassesOn - Carefully run the specified set of pass on the specified +/// module, returning the transformed module on success, or a null pointer on +/// failure. +Module *BugDriver::runPassesOn(Module *M, + const std::vector &Passes, + bool AutoDebugCrashes, unsigned NumExtraArgs, + const char * const *ExtraArgs) { + Module *OldProgram = swapProgramIn(M); + std::string BitcodeResult; + if (runPasses(Passes, BitcodeResult, false/*delete*/, true/*quiet*/, + NumExtraArgs, ExtraArgs)) { + if (AutoDebugCrashes) { + cerr << " Error running this sequence of passes" + << " on the input program!\n"; + delete OldProgram; + EmitProgressBitcode("pass-error", false); + exit(debugOptimizerCrash()); + } + swapProgramIn(OldProgram); + return 0; + } + + // Restore the current program. + swapProgramIn(OldProgram); + + Module *Ret = ParseInputFile(BitcodeResult); + if (Ret == 0) { + cerr << getToolName() << ": Error reading bitcode file '" + << BitcodeResult << "'!\n"; + exit(1); + } + sys::Path(BitcodeResult).eraseFromDisk(); // No longer need the file on disk + return Ret; +} diff --git a/tools/bugpoint/TestPasses.cpp b/tools/bugpoint/TestPasses.cpp new file mode 100644 index 0000000..900bf63 --- /dev/null +++ b/tools/bugpoint/TestPasses.cpp @@ -0,0 +1,75 @@ +//===- TestPasses.cpp - "buggy" passes used to test bugpoint --------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains "buggy" passes that are used to test bugpoint, to check +// that it is narrowing down testcases correctly. +// +//===----------------------------------------------------------------------===// + +#include "llvm/BasicBlock.h" +#include "llvm/Constant.h" +#include "llvm/Instructions.h" +#include "llvm/Pass.h" +#include "llvm/Type.h" +#include "llvm/Support/InstVisitor.h" + +using namespace llvm; + +namespace { + /// CrashOnCalls - This pass is used to test bugpoint. It intentionally + /// crashes on any call instructions. + class CrashOnCalls : public BasicBlockPass { + public: + static char ID; // Pass ID, replacement for typeid + CrashOnCalls() : BasicBlockPass(&ID) {} + private: + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + } + + bool runOnBasicBlock(BasicBlock &BB) { + for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) + if (isa(*I)) + abort(); + + return false; + } + }; + + char CrashOnCalls::ID = 0; + RegisterPass + X("bugpoint-crashcalls", + "BugPoint Test Pass - Intentionally crash on CallInsts"); +} + +namespace { + /// DeleteCalls - This pass is used to test bugpoint. It intentionally + /// deletes some call instructions, "misoptimizing" the program. + class DeleteCalls : public BasicBlockPass { + public: + static char ID; // Pass ID, replacement for typeid + DeleteCalls() : BasicBlockPass(&ID) {} + private: + bool runOnBasicBlock(BasicBlock &BB) { + for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) + if (CallInst *CI = dyn_cast(I)) { + if (!CI->use_empty()) + CI->replaceAllUsesWith(Constant::getNullValue(CI->getType())); + CI->getParent()->getInstList().erase(CI); + break; + } + return false; + } + }; + + char DeleteCalls::ID = 0; + RegisterPass + Y("bugpoint-deletecalls", + "BugPoint Test Pass - Intentionally 'misoptimize' CallInsts"); +} diff --git a/tools/bugpoint/ToolRunner.cpp b/tools/bugpoint/ToolRunner.cpp new file mode 100644 index 0000000..978e60b --- /dev/null +++ b/tools/bugpoint/ToolRunner.cpp @@ -0,0 +1,748 @@ +//===-- ToolRunner.cpp ----------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the interfaces described in the ToolRunner.h file. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "toolrunner" +#include "ToolRunner.h" +#include "llvm/Config/config.h" // for HAVE_LINK_R +#include "llvm/System/Program.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FileUtilities.h" +#include +#include +#include +using namespace llvm; + +namespace { + cl::opt + RemoteClient("remote-client", + cl::desc("Remote execution client (rsh/ssh)")); + + cl::opt + RemoteHost("remote-host", + cl::desc("Remote execution (rsh/ssh) host")); + + cl::opt + RemoteUser("remote-user", + cl::desc("Remote execution (rsh/ssh) user id")); + + cl::opt + RemoteExtra("remote-extra-options", + cl::desc("Remote execution (rsh/ssh) extra options")); +} + +ToolExecutionError::~ToolExecutionError() throw() { } + +/// RunProgramWithTimeout - This function provides an alternate interface to the +/// sys::Program::ExecuteAndWait interface. +/// @see sys:Program::ExecuteAndWait +static int RunProgramWithTimeout(const sys::Path &ProgramPath, + const char **Args, + const sys::Path &StdInFile, + const sys::Path &StdOutFile, + const sys::Path &StdErrFile, + unsigned NumSeconds = 0, + unsigned MemoryLimit = 0) { + const sys::Path* redirects[3]; + redirects[0] = &StdInFile; + redirects[1] = &StdOutFile; + redirects[2] = &StdErrFile; + + if (0) { + std::cerr << "RUN:"; + for (unsigned i = 0; Args[i]; ++i) + std::cerr << " " << Args[i]; + std::cerr << "\n"; + } + + return + sys::Program::ExecuteAndWait(ProgramPath, Args, 0, redirects, + NumSeconds, MemoryLimit); +} + + + +static void ProcessFailure(sys::Path ProgPath, const char** Args) { + std::ostringstream OS; + OS << "\nError running tool:\n "; + for (const char **Arg = Args; *Arg; ++Arg) + OS << " " << *Arg; + OS << "\n"; + + // Rerun the compiler, capturing any error messages to print them. + sys::Path ErrorFilename("bugpoint.program_error_messages"); + std::string ErrMsg; + if (ErrorFilename.makeUnique(true, &ErrMsg)) { + std::cerr << "Error making unique filename: " << ErrMsg << "\n"; + exit(1); + } + RunProgramWithTimeout(ProgPath, Args, sys::Path(""), ErrorFilename, + ErrorFilename); // FIXME: check return code ? + + // Print out the error messages generated by GCC if possible... + std::ifstream ErrorFile(ErrorFilename.c_str()); + if (ErrorFile) { + std::copy(std::istreambuf_iterator(ErrorFile), + std::istreambuf_iterator(), + std::ostreambuf_iterator(OS)); + ErrorFile.close(); + } + + ErrorFilename.eraseFromDisk(); + throw ToolExecutionError(OS.str()); +} + +//===---------------------------------------------------------------------===// +// LLI Implementation of AbstractIntepreter interface +// +namespace { + class LLI : public AbstractInterpreter { + std::string LLIPath; // The path to the LLI executable + std::vector ToolArgs; // Args to pass to LLI + public: + LLI(const std::string &Path, const std::vector *Args) + : LLIPath(Path) { + ToolArgs.clear (); + if (Args) { ToolArgs = *Args; } + } + + virtual int ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &GCCArgs, + const std::vector &SharedLibs = + std::vector(), + unsigned Timeout = 0, + unsigned MemoryLimit = 0); + }; +} + +int LLI::ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &GCCArgs, + const std::vector &SharedLibs, + unsigned Timeout, + unsigned MemoryLimit) { + if (!SharedLibs.empty()) + throw ToolExecutionError("LLI currently does not support " + "loading shared libraries."); + + std::vector LLIArgs; + LLIArgs.push_back(LLIPath.c_str()); + LLIArgs.push_back("-force-interpreter=true"); + + // Add any extra LLI args. + for (unsigned i = 0, e = ToolArgs.size(); i != e; ++i) + LLIArgs.push_back(ToolArgs[i].c_str()); + + LLIArgs.push_back(Bitcode.c_str()); + // Add optional parameters to the running program from Argv + for (unsigned i=0, e = Args.size(); i != e; ++i) + LLIArgs.push_back(Args[i].c_str()); + LLIArgs.push_back(0); + + std::cout << "" << std::flush; + DEBUG(std::cerr << "\nAbout to run:\t"; + for (unsigned i=0, e = LLIArgs.size()-1; i != e; ++i) + std::cerr << " " << LLIArgs[i]; + std::cerr << "\n"; + ); + return RunProgramWithTimeout(sys::Path(LLIPath), &LLIArgs[0], + sys::Path(InputFile), sys::Path(OutputFile), sys::Path(OutputFile), + Timeout, MemoryLimit); +} + +// LLI create method - Try to find the LLI executable +AbstractInterpreter *AbstractInterpreter::createLLI(const std::string &ProgPath, + std::string &Message, + const std::vector *ToolArgs) { + std::string LLIPath = FindExecutable("lli", ProgPath).toString(); + if (!LLIPath.empty()) { + Message = "Found lli: " + LLIPath + "\n"; + return new LLI(LLIPath, ToolArgs); + } + + Message = "Cannot find `lli' in executable directory or PATH!\n"; + return 0; +} + +//===---------------------------------------------------------------------===// +// Custom execution command implementation of AbstractIntepreter interface +// +// Allows using a custom command for executing the bitcode, thus allows, +// for example, to invoke a cross compiler for code generation followed by +// a simulator that executes the generated binary. +namespace { + class CustomExecutor : public AbstractInterpreter { + std::string ExecutionCommand; + std::vector ExecutorArgs; + public: + CustomExecutor( + const std::string &ExecutionCmd, std::vector ExecArgs) : + ExecutionCommand(ExecutionCmd), ExecutorArgs(ExecArgs) {} + + virtual int ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &GCCArgs, + const std::vector &SharedLibs = + std::vector(), + unsigned Timeout = 0, + unsigned MemoryLimit = 0); + }; +} + +int CustomExecutor::ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &GCCArgs, + const std::vector &SharedLibs, + unsigned Timeout, + unsigned MemoryLimit) { + + std::vector ProgramArgs; + ProgramArgs.push_back(ExecutionCommand.c_str()); + + for (std::size_t i = 0; i < ExecutorArgs.size(); ++i) + ProgramArgs.push_back(ExecutorArgs.at(i).c_str()); + ProgramArgs.push_back(Bitcode.c_str()); + ProgramArgs.push_back(0); + + // Add optional parameters to the running program from Argv + for (unsigned i=0, e = Args.size(); i != e; ++i) + ProgramArgs.push_back(Args[i].c_str()); + + return RunProgramWithTimeout( + sys::Path(ExecutionCommand), + &ProgramArgs[0], sys::Path(InputFile), sys::Path(OutputFile), + sys::Path(OutputFile), Timeout, MemoryLimit); +} + +// Custom execution environment create method, takes the execution command +// as arguments +AbstractInterpreter *AbstractInterpreter::createCustom( + const std::string &ProgramPath, + std::string &Message, + const std::string &ExecCommandLine) { + + std::string Command = ""; + std::vector Args; + std::string delimiters = " "; + + // Tokenize the ExecCommandLine to the command and the args to allow + // defining a full command line as the command instead of just the + // executed program. We cannot just pass the whole string after the command + // as a single argument because then program sees only a single + // command line argument (with spaces in it: "foo bar" instead + // of "foo" and "bar"). + + // code borrowed from: + // http://oopweb.com/CPP/Documents/CPPHOWTO/Volume/C++Programming-HOWTO-7.html + std::string::size_type lastPos = + ExecCommandLine.find_first_not_of(delimiters, 0); + std::string::size_type pos = + ExecCommandLine.find_first_of(delimiters, lastPos); + + while (std::string::npos != pos || std::string::npos != lastPos) { + std::string token = ExecCommandLine.substr(lastPos, pos - lastPos); + if (Command == "") + Command = token; + else + Args.push_back(token); + // Skip delimiters. Note the "not_of" + lastPos = ExecCommandLine.find_first_not_of(delimiters, pos); + // Find next "non-delimiter" + pos = ExecCommandLine.find_first_of(delimiters, lastPos); + } + + std::string CmdPath = FindExecutable(Command, ProgramPath).toString(); + if (CmdPath.empty()) { + Message = + std::string("Cannot find '") + Command + + "' in executable directory or PATH!\n"; + return 0; + } + + Message = "Found command in: " + CmdPath + "\n"; + + return new CustomExecutor(CmdPath, Args); +} + +//===----------------------------------------------------------------------===// +// LLC Implementation of AbstractIntepreter interface +// +GCC::FileType LLC::OutputCode(const std::string &Bitcode, + sys::Path &OutputAsmFile) { + sys::Path uniqueFile(Bitcode+".llc.s"); + std::string ErrMsg; + if (uniqueFile.makeUnique(true, &ErrMsg)) { + std::cerr << "Error making unique filename: " << ErrMsg << "\n"; + exit(1); + } + OutputAsmFile = uniqueFile; + std::vector LLCArgs; + LLCArgs.push_back (LLCPath.c_str()); + + // Add any extra LLC args. + for (unsigned i = 0, e = ToolArgs.size(); i != e; ++i) + LLCArgs.push_back(ToolArgs[i].c_str()); + + LLCArgs.push_back ("-o"); + LLCArgs.push_back (OutputAsmFile.c_str()); // Output to the Asm file + LLCArgs.push_back ("-f"); // Overwrite as necessary... + LLCArgs.push_back (Bitcode.c_str()); // This is the input bitcode + LLCArgs.push_back (0); + + std::cout << "" << std::flush; + DEBUG(std::cerr << "\nAbout to run:\t"; + for (unsigned i=0, e = LLCArgs.size()-1; i != e; ++i) + std::cerr << " " << LLCArgs[i]; + std::cerr << "\n"; + ); + if (RunProgramWithTimeout(sys::Path(LLCPath), &LLCArgs[0], + sys::Path(), sys::Path(), sys::Path())) + ProcessFailure(sys::Path(LLCPath), &LLCArgs[0]); + + return GCC::AsmFile; +} + +void LLC::compileProgram(const std::string &Bitcode) { + sys::Path OutputAsmFile; + OutputCode(Bitcode, OutputAsmFile); + OutputAsmFile.eraseFromDisk(); +} + +int LLC::ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &ArgsForGCC, + const std::vector &SharedLibs, + unsigned Timeout, + unsigned MemoryLimit) { + + sys::Path OutputAsmFile; + OutputCode(Bitcode, OutputAsmFile); + FileRemover OutFileRemover(OutputAsmFile); + + std::vector GCCArgs(ArgsForGCC); + GCCArgs.insert(GCCArgs.end(), SharedLibs.begin(), SharedLibs.end()); + GCCArgs.insert(GCCArgs.end(), gccArgs.begin(), gccArgs.end()); + + // Assuming LLC worked, compile the result with GCC and run it. + return gcc->ExecuteProgram(OutputAsmFile.toString(), Args, GCC::AsmFile, + InputFile, OutputFile, GCCArgs, + Timeout, MemoryLimit); +} + +/// createLLC - Try to find the LLC executable +/// +LLC *AbstractInterpreter::createLLC(const std::string &ProgramPath, + std::string &Message, + const std::vector *Args, + const std::vector *GCCArgs) { + std::string LLCPath = FindExecutable("llc", ProgramPath).toString(); + if (LLCPath.empty()) { + Message = "Cannot find `llc' in executable directory or PATH!\n"; + return 0; + } + + Message = "Found llc: " + LLCPath + "\n"; + GCC *gcc = GCC::create(ProgramPath, Message, GCCArgs); + if (!gcc) { + std::cerr << Message << "\n"; + exit(1); + } + return new LLC(LLCPath, gcc, Args, GCCArgs); +} + +//===---------------------------------------------------------------------===// +// JIT Implementation of AbstractIntepreter interface +// +namespace { + class JIT : public AbstractInterpreter { + std::string LLIPath; // The path to the LLI executable + std::vector ToolArgs; // Args to pass to LLI + public: + JIT(const std::string &Path, const std::vector *Args) + : LLIPath(Path) { + ToolArgs.clear (); + if (Args) { ToolArgs = *Args; } + } + + virtual int ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &GCCArgs = + std::vector(), + const std::vector &SharedLibs = + std::vector(), + unsigned Timeout =0, + unsigned MemoryLimit =0); + }; +} + +int JIT::ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &GCCArgs, + const std::vector &SharedLibs, + unsigned Timeout, + unsigned MemoryLimit) { + // Construct a vector of parameters, incorporating those from the command-line + std::vector JITArgs; + JITArgs.push_back(LLIPath.c_str()); + JITArgs.push_back("-force-interpreter=false"); + + // Add any extra LLI args. + for (unsigned i = 0, e = ToolArgs.size(); i != e; ++i) + JITArgs.push_back(ToolArgs[i].c_str()); + + for (unsigned i = 0, e = SharedLibs.size(); i != e; ++i) { + JITArgs.push_back("-load"); + JITArgs.push_back(SharedLibs[i].c_str()); + } + JITArgs.push_back(Bitcode.c_str()); + // Add optional parameters to the running program from Argv + for (unsigned i=0, e = Args.size(); i != e; ++i) + JITArgs.push_back(Args[i].c_str()); + JITArgs.push_back(0); + + std::cout << "" << std::flush; + DEBUG(std::cerr << "\nAbout to run:\t"; + for (unsigned i=0, e = JITArgs.size()-1; i != e; ++i) + std::cerr << " " << JITArgs[i]; + std::cerr << "\n"; + ); + DEBUG(std::cerr << "\nSending output to " << OutputFile << "\n"); + return RunProgramWithTimeout(sys::Path(LLIPath), &JITArgs[0], + sys::Path(InputFile), sys::Path(OutputFile), sys::Path(OutputFile), + Timeout, MemoryLimit); +} + +/// createJIT - Try to find the LLI executable +/// +AbstractInterpreter *AbstractInterpreter::createJIT(const std::string &ProgPath, + std::string &Message, const std::vector *Args) { + std::string LLIPath = FindExecutable("lli", ProgPath).toString(); + if (!LLIPath.empty()) { + Message = "Found lli: " + LLIPath + "\n"; + return new JIT(LLIPath, Args); + } + + Message = "Cannot find `lli' in executable directory or PATH!\n"; + return 0; +} + +GCC::FileType CBE::OutputCode(const std::string &Bitcode, + sys::Path &OutputCFile) { + sys::Path uniqueFile(Bitcode+".cbe.c"); + std::string ErrMsg; + if (uniqueFile.makeUnique(true, &ErrMsg)) { + std::cerr << "Error making unique filename: " << ErrMsg << "\n"; + exit(1); + } + OutputCFile = uniqueFile; + std::vector LLCArgs; + LLCArgs.push_back (LLCPath.c_str()); + + // Add any extra LLC args. + for (unsigned i = 0, e = ToolArgs.size(); i != e; ++i) + LLCArgs.push_back(ToolArgs[i].c_str()); + + LLCArgs.push_back ("-o"); + LLCArgs.push_back (OutputCFile.c_str()); // Output to the C file + LLCArgs.push_back ("-march=c"); // Output C language + LLCArgs.push_back ("-f"); // Overwrite as necessary... + LLCArgs.push_back (Bitcode.c_str()); // This is the input bitcode + LLCArgs.push_back (0); + + std::cout << "" << std::flush; + DEBUG(std::cerr << "\nAbout to run:\t"; + for (unsigned i=0, e = LLCArgs.size()-1; i != e; ++i) + std::cerr << " " << LLCArgs[i]; + std::cerr << "\n"; + ); + if (RunProgramWithTimeout(LLCPath, &LLCArgs[0], sys::Path(), sys::Path(), + sys::Path())) + ProcessFailure(LLCPath, &LLCArgs[0]); + return GCC::CFile; +} + +void CBE::compileProgram(const std::string &Bitcode) { + sys::Path OutputCFile; + OutputCode(Bitcode, OutputCFile); + OutputCFile.eraseFromDisk(); +} + +int CBE::ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &ArgsForGCC, + const std::vector &SharedLibs, + unsigned Timeout, + unsigned MemoryLimit) { + sys::Path OutputCFile; + OutputCode(Bitcode, OutputCFile); + + FileRemover CFileRemove(OutputCFile); + + std::vector GCCArgs(ArgsForGCC); + GCCArgs.insert(GCCArgs.end(), SharedLibs.begin(), SharedLibs.end()); + + return gcc->ExecuteProgram(OutputCFile.toString(), Args, GCC::CFile, + InputFile, OutputFile, GCCArgs, + Timeout, MemoryLimit); +} + +/// createCBE - Try to find the 'llc' executable +/// +CBE *AbstractInterpreter::createCBE(const std::string &ProgramPath, + std::string &Message, + const std::vector *Args, + const std::vector *GCCArgs) { + sys::Path LLCPath = FindExecutable("llc", ProgramPath); + if (LLCPath.isEmpty()) { + Message = + "Cannot find `llc' in executable directory or PATH!\n"; + return 0; + } + + Message = "Found llc: " + LLCPath.toString() + "\n"; + GCC *gcc = GCC::create(ProgramPath, Message, GCCArgs); + if (!gcc) { + std::cerr << Message << "\n"; + exit(1); + } + return new CBE(LLCPath, gcc, Args); +} + +//===---------------------------------------------------------------------===// +// GCC abstraction +// +int GCC::ExecuteProgram(const std::string &ProgramFile, + const std::vector &Args, + FileType fileType, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &ArgsForGCC, + unsigned Timeout, + unsigned MemoryLimit) { + std::vector GCCArgs; + + GCCArgs.push_back(GCCPath.c_str()); + + for (std::vector::const_iterator + I = gccArgs.begin(), E = gccArgs.end(); I != E; ++I) + GCCArgs.push_back(I->c_str()); + + // Specify -x explicitly in case the extension is wonky + GCCArgs.push_back("-x"); + if (fileType == CFile) { + GCCArgs.push_back("c"); + GCCArgs.push_back("-fno-strict-aliasing"); + } else { + GCCArgs.push_back("assembler"); +#ifdef __APPLE__ + GCCArgs.push_back("-force_cpusubtype_ALL"); +#endif + } + GCCArgs.push_back(ProgramFile.c_str()); // Specify the input filename... + GCCArgs.push_back("-x"); + GCCArgs.push_back("none"); + GCCArgs.push_back("-o"); + sys::Path OutputBinary (ProgramFile+".gcc.exe"); + std::string ErrMsg; + if (OutputBinary.makeUnique(true, &ErrMsg)) { + std::cerr << "Error making unique filename: " << ErrMsg << "\n"; + exit(1); + } + GCCArgs.push_back(OutputBinary.c_str()); // Output to the right file... + + // Add any arguments intended for GCC. We locate them here because this is + // most likely -L and -l options that need to come before other libraries but + // after the source. Other options won't be sensitive to placement on the + // command line, so this should be safe. + for (unsigned i = 0, e = ArgsForGCC.size(); i != e; ++i) + GCCArgs.push_back(ArgsForGCC[i].c_str()); + + GCCArgs.push_back("-lm"); // Hard-code the math library... + GCCArgs.push_back("-O2"); // Optimize the program a bit... +#if defined (HAVE_LINK_R) + GCCArgs.push_back("-Wl,-R."); // Search this dir for .so files +#endif +#ifdef __sparc__ + GCCArgs.push_back("-mcpu=v9"); +#endif + GCCArgs.push_back(0); // NULL terminator + + std::cout << "" << std::flush; + DEBUG(std::cerr << "\nAbout to run:\t"; + for (unsigned i=0, e = GCCArgs.size()-1; i != e; ++i) + std::cerr << " " << GCCArgs[i]; + std::cerr << "\n"; + ); + if (RunProgramWithTimeout(GCCPath, &GCCArgs[0], sys::Path(), sys::Path(), + sys::Path())) { + ProcessFailure(GCCPath, &GCCArgs[0]); + exit(1); + } + + std::vector ProgramArgs; + + if (RemoteClientPath.isEmpty()) + ProgramArgs.push_back(OutputBinary.c_str()); + else { + ProgramArgs.push_back(RemoteClientPath.c_str()); + ProgramArgs.push_back(RemoteHost.c_str()); + ProgramArgs.push_back("-l"); + ProgramArgs.push_back(RemoteUser.c_str()); + if (!RemoteExtra.empty()) { + ProgramArgs.push_back(RemoteExtra.c_str()); + } + + char* env_pwd = getenv("PWD"); + std::string Exec = "cd "; + Exec += env_pwd; + Exec += "; ./"; + Exec += OutputBinary.c_str(); + ProgramArgs.push_back(Exec.c_str()); + } + + // Add optional parameters to the running program from Argv + for (unsigned i=0, e = Args.size(); i != e; ++i) + ProgramArgs.push_back(Args[i].c_str()); + ProgramArgs.push_back(0); // NULL terminator + + // Now that we have a binary, run it! + std::cout << "" << std::flush; + DEBUG(std::cerr << "\nAbout to run:\t"; + for (unsigned i=0, e = ProgramArgs.size()-1; i != e; ++i) + std::cerr << " " << ProgramArgs[i]; + std::cerr << "\n"; + ); + + FileRemover OutputBinaryRemover(OutputBinary); + + if (RemoteClientPath.isEmpty()) + return RunProgramWithTimeout(OutputBinary, &ProgramArgs[0], + sys::Path(InputFile), sys::Path(OutputFile), sys::Path(OutputFile), + Timeout, MemoryLimit); + else + return RunProgramWithTimeout(sys::Path(RemoteClientPath), &ProgramArgs[0], + sys::Path(InputFile), sys::Path(OutputFile), sys::Path(OutputFile), + Timeout, MemoryLimit); +} + +int GCC::MakeSharedObject(const std::string &InputFile, FileType fileType, + std::string &OutputFile, + const std::vector &ArgsForGCC) { + sys::Path uniqueFilename(InputFile+LTDL_SHLIB_EXT); + std::string ErrMsg; + if (uniqueFilename.makeUnique(true, &ErrMsg)) { + std::cerr << "Error making unique filename: " << ErrMsg << "\n"; + exit(1); + } + OutputFile = uniqueFilename.toString(); + + std::vector GCCArgs; + + GCCArgs.push_back(GCCPath.c_str()); + + for (std::vector::const_iterator + I = gccArgs.begin(), E = gccArgs.end(); I != E; ++I) + GCCArgs.push_back(I->c_str()); + + // Compile the C/asm file into a shared object + GCCArgs.push_back("-x"); + GCCArgs.push_back(fileType == AsmFile ? "assembler" : "c"); + GCCArgs.push_back("-fno-strict-aliasing"); + GCCArgs.push_back(InputFile.c_str()); // Specify the input filename. + GCCArgs.push_back("-x"); + GCCArgs.push_back("none"); +#if defined(sparc) || defined(__sparc__) || defined(__sparcv9) + GCCArgs.push_back("-G"); // Compile a shared library, `-G' for Sparc +#elif defined(__APPLE__) + // link all source files into a single module in data segment, rather than + // generating blocks. dynamic_lookup requires that you set + // MACOSX_DEPLOYMENT_TARGET=10.3 in your env. FIXME: it would be better for + // bugpoint to just pass that in the environment of GCC. + GCCArgs.push_back("-single_module"); + GCCArgs.push_back("-dynamiclib"); // `-dynamiclib' for MacOS X/PowerPC + GCCArgs.push_back("-undefined"); + GCCArgs.push_back("dynamic_lookup"); +#else + GCCArgs.push_back("-shared"); // `-shared' for Linux/X86, maybe others +#endif + +#if defined(__ia64__) || defined(__alpha__) || defined(__amd64__) + GCCArgs.push_back("-fPIC"); // Requires shared objs to contain PIC +#endif +#ifdef __sparc__ + GCCArgs.push_back("-mcpu=v9"); +#endif + GCCArgs.push_back("-o"); + GCCArgs.push_back(OutputFile.c_str()); // Output to the right filename. + GCCArgs.push_back("-O2"); // Optimize the program a bit. + + + + // Add any arguments intended for GCC. We locate them here because this is + // most likely -L and -l options that need to come before other libraries but + // after the source. Other options won't be sensitive to placement on the + // command line, so this should be safe. + for (unsigned i = 0, e = ArgsForGCC.size(); i != e; ++i) + GCCArgs.push_back(ArgsForGCC[i].c_str()); + GCCArgs.push_back(0); // NULL terminator + + + + std::cout << "" << std::flush; + DEBUG(std::cerr << "\nAbout to run:\t"; + for (unsigned i=0, e = GCCArgs.size()-1; i != e; ++i) + std::cerr << " " << GCCArgs[i]; + std::cerr << "\n"; + ); + if (RunProgramWithTimeout(GCCPath, &GCCArgs[0], sys::Path(), sys::Path(), + sys::Path())) { + ProcessFailure(GCCPath, &GCCArgs[0]); + return 1; + } + return 0; +} + +/// create - Try to find the `gcc' executable +/// +GCC *GCC::create(const std::string &ProgramPath, std::string &Message, + const std::vector *Args) { + sys::Path GCCPath = FindExecutable("gcc", ProgramPath); + if (GCCPath.isEmpty()) { + Message = "Cannot find `gcc' in executable directory or PATH!\n"; + return 0; + } + + sys::Path RemoteClientPath; + if (!RemoteClient.empty()) + RemoteClientPath = FindExecutable(RemoteClient.c_str(), ProgramPath); + + Message = "Found gcc: " + GCCPath.toString() + "\n"; + return new GCC(GCCPath, RemoteClientPath, Args); +} diff --git a/tools/bugpoint/ToolRunner.h b/tools/bugpoint/ToolRunner.h new file mode 100644 index 0000000..721f66c --- /dev/null +++ b/tools/bugpoint/ToolRunner.h @@ -0,0 +1,230 @@ +//===-- tools/bugpoint/ToolRunner.h -----------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file exposes an abstraction around a platform C compiler, used to +// compile C and assembly code. It also exposes an "AbstractIntepreter" +// interface, which is used to execute code using one of the LLVM execution +// engines. +// +//===----------------------------------------------------------------------===// + +#ifndef BUGPOINT_TOOLRUNNER_H +#define BUGPOINT_TOOLRUNNER_H + +#include "llvm/Support/SystemUtils.h" +#include +#include + +namespace llvm { + +class CBE; +class LLC; + +/// ToolExecutionError - An instance of this class is thrown by the +/// AbstractInterpreter instances if there is an error running a tool (e.g., LLC +/// crashes) which prevents execution of the program. +/// +class ToolExecutionError : std::exception { + std::string Message; +public: + explicit ToolExecutionError(const std::string &M) : Message(M) {} + virtual ~ToolExecutionError() throw(); + virtual const char* what() const throw() { return Message.c_str(); } +}; + + +//===---------------------------------------------------------------------===// +// GCC abstraction +// +class GCC { + sys::Path GCCPath; // The path to the gcc executable. + sys::Path RemoteClientPath; // The path to the rsh / ssh executable. + std::vector gccArgs; // GCC-specific arguments. + GCC(const sys::Path &gccPath, const sys::Path &RemotePath, + const std::vector *GCCArgs) + : GCCPath(gccPath), RemoteClientPath(RemotePath) { + if (GCCArgs) gccArgs = *GCCArgs; + } +public: + enum FileType { AsmFile, CFile }; + + static GCC *create(const std::string &ProgramPath, std::string &Message, + const std::vector *Args); + + /// ExecuteProgram - Execute the program specified by "ProgramFile" (which is + /// either a .s file, or a .c file, specified by FileType), with the specified + /// arguments. Standard input is specified with InputFile, and standard + /// Output is captured to the specified OutputFile location. The SharedLibs + /// option specifies optional native shared objects that can be loaded into + /// the program for execution. + /// + int ExecuteProgram(const std::string &ProgramFile, + const std::vector &Args, + FileType fileType, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &GCCArgs = + std::vector(), + unsigned Timeout = 0, + unsigned MemoryLimit = 0); + + /// MakeSharedObject - This compiles the specified file (which is either a .c + /// file or a .s file) into a shared object. + /// + int MakeSharedObject(const std::string &InputFile, FileType fileType, + std::string &OutputFile, + const std::vector &ArgsForGCC); +}; + + +//===---------------------------------------------------------------------===// +/// AbstractInterpreter Class - Subclasses of this class are used to execute +/// LLVM bitcode in a variety of ways. This abstract interface hides this +/// complexity behind a simple interface. +/// +class AbstractInterpreter { +public: + static CBE *createCBE(const std::string &ProgramPath, std::string &Message, + const std::vector *Args = 0, + const std::vector *GCCArgs = 0); + static LLC *createLLC(const std::string &ProgramPath, std::string &Message, + const std::vector *Args = 0, + const std::vector *GCCArgs = 0); + + static AbstractInterpreter* createLLI(const std::string &ProgramPath, + std::string &Message, + const std::vector *Args=0); + + static AbstractInterpreter* createJIT(const std::string &ProgramPath, + std::string &Message, + const std::vector *Args=0); + + static AbstractInterpreter* createCustom(const std::string &ProgramPath, + std::string &Message, + const std::string &ExecCommandLine); + + + virtual ~AbstractInterpreter() {} + + /// compileProgram - Compile the specified program from bitcode to executable + /// code. This does not produce any output, it is only used when debugging + /// the code generator. If the code generator fails, an exception should be + /// thrown, otherwise, this function will just return. + virtual void compileProgram(const std::string &Bitcode) {} + + /// OutputCode - Compile the specified program from bitcode to code + /// understood by the GCC driver (either C or asm). If the code generator + /// fails, an exception should be thrown, otherwise, this function returns the + /// type of code emitted. + virtual GCC::FileType OutputCode(const std::string &Bitcode, + sys::Path &OutFile) { + throw std::string("OutputCode not supported by this AbstractInterpreter!"); + } + + /// ExecuteProgram - Run the specified bitcode file, emitting output to the + /// specified filename. This returns the exit code of the program. + /// + virtual int ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &GCCArgs = + std::vector(), + const std::vector &SharedLibs = + std::vector(), + unsigned Timeout = 0, + unsigned MemoryLimit = 0) = 0; +}; + +//===---------------------------------------------------------------------===// +// CBE Implementation of AbstractIntepreter interface +// +class CBE : public AbstractInterpreter { + sys::Path LLCPath; // The path to the `llc' executable. + std::vector ToolArgs; // Extra args to pass to LLC. + GCC *gcc; +public: + CBE(const sys::Path &llcPath, GCC *Gcc, + const std::vector *Args) + : LLCPath(llcPath), gcc(Gcc) { + ToolArgs.clear (); + if (Args) ToolArgs = *Args; + } + ~CBE() { delete gcc; } + + /// compileProgram - Compile the specified program from bitcode to executable + /// code. This does not produce any output, it is only used when debugging + /// the code generator. If the code generator fails, an exception should be + /// thrown, otherwise, this function will just return. + virtual void compileProgram(const std::string &Bitcode); + + virtual int ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &GCCArgs = + std::vector(), + const std::vector &SharedLibs = + std::vector(), + unsigned Timeout = 0, + unsigned MemoryLimit = 0); + + /// OutputCode - Compile the specified program from bitcode to code + /// understood by the GCC driver (either C or asm). If the code generator + /// fails, an exception should be thrown, otherwise, this function returns the + /// type of code emitted. + virtual GCC::FileType OutputCode(const std::string &Bitcode, + sys::Path &OutFile); +}; + + +//===---------------------------------------------------------------------===// +// LLC Implementation of AbstractIntepreter interface +// +class LLC : public AbstractInterpreter { + std::string LLCPath; // The path to the LLC executable. + std::vector ToolArgs; // Extra args to pass to LLC. + std::vector gccArgs; // Extra args to pass to GCC. + GCC *gcc; +public: + LLC(const std::string &llcPath, GCC *Gcc, + const std::vector *Args, + const std::vector *GCCArgs) + : LLCPath(llcPath), gcc(Gcc) { + ToolArgs.clear(); + if (Args) ToolArgs = *Args; + if (GCCArgs) gccArgs = *GCCArgs; + } + ~LLC() { delete gcc; } + + /// compileProgram - Compile the specified program from bitcode to executable + /// code. This does not produce any output, it is only used when debugging + /// the code generator. If the code generator fails, an exception should be + /// thrown, otherwise, this function will just return. + virtual void compileProgram(const std::string &Bitcode); + + virtual int ExecuteProgram(const std::string &Bitcode, + const std::vector &Args, + const std::string &InputFile, + const std::string &OutputFile, + const std::vector &GCCArgs = + std::vector(), + const std::vector &SharedLibs = + std::vector(), + unsigned Timeout = 0, + unsigned MemoryLimit = 0); + + virtual GCC::FileType OutputCode(const std::string &Bitcode, + sys::Path &OutFile); + +}; + +} // End llvm namespace + +#endif diff --git a/tools/bugpoint/bugpoint.cpp b/tools/bugpoint/bugpoint.cpp new file mode 100644 index 0000000..20f0e99 --- /dev/null +++ b/tools/bugpoint/bugpoint.cpp @@ -0,0 +1,104 @@ +//===- bugpoint.cpp - The LLVM Bugpoint utility ---------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This program is an automated compiler debugger tool. It is used to narrow +// down miscompilations and crash problems to a specific pass in the compiler, +// and the specific Module or Function input that is causing the problem. +// +//===----------------------------------------------------------------------===// + +#include "BugDriver.h" +#include "ToolRunner.h" +#include "llvm/LinkAllPasses.h" +#include "llvm/Support/PassNameParser.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/ManagedStatic.h" +#include "llvm/Support/PluginLoader.h" +#include "llvm/Support/PrettyStackTrace.h" +#include "llvm/System/Process.h" +#include "llvm/System/Signals.h" +#include "llvm/LinkAllVMCore.h" +#include +using namespace llvm; + +// AsChild - Specifies that this invocation of bugpoint is being generated +// from a parent process. It is not intended to be used by users so the +// option is hidden. +static cl::opt +AsChild("as-child", cl::desc("Run bugpoint as child process"), + cl::ReallyHidden); + +static cl::opt +FindBugs("find-bugs", cl::desc("Run many different optimization sequences " + "on program to find bugs"), cl::init(false)); + +static cl::list +InputFilenames(cl::Positional, cl::OneOrMore, + cl::desc("")); + +static cl::opt +TimeoutValue("timeout", cl::init(300), cl::value_desc("seconds"), + cl::desc("Number of seconds program is allowed to run before it " + "is killed (default is 300s), 0 disables timeout")); + +static cl::opt +MemoryLimit("mlimit", cl::init(100), cl::value_desc("MBytes"), + cl::desc("Maximum amount of memory to use. 0 disables check.")); + +// The AnalysesList is automatically populated with registered Passes by the +// PassNameParser. +// +static cl::list +PassList(cl::desc("Passes available:"), cl::ZeroOrMore); + +/// BugpointIsInterrupted - Set to true when the user presses ctrl-c. +bool llvm::BugpointIsInterrupted = false; + +static void BugpointInterruptFunction() { + BugpointIsInterrupted = true; +} + +int main(int argc, char **argv) { + llvm::sys::PrintStackTraceOnErrorSignal(); + llvm::PrettyStackTraceProgram X(argc, argv); + llvm_shutdown_obj Y; // Call llvm_shutdown() on exit. + cl::ParseCommandLineOptions(argc, argv, + "LLVM automatic testcase reducer. See\nhttp://" + "llvm.org/cmds/bugpoint.html" + " for more information.\n"); + sys::SetInterruptFunction(BugpointInterruptFunction); + + BugDriver D(argv[0], AsChild, FindBugs, TimeoutValue, MemoryLimit); + if (D.addSources(InputFilenames)) return 1; + D.addPasses(PassList.begin(), PassList.end()); + + // Bugpoint has the ability of generating a plethora of core files, so to + // avoid filling up the disk, we prevent it + sys::Process::PreventCoreFiles(); + + try { + return D.run(); + } catch (ToolExecutionError &TEE) { + std::cerr << "Tool execution error: " << TEE.what() << '\n'; + } catch (const std::string& msg) { + std::cerr << argv[0] << ": " << msg << "\n"; + } catch (const std::bad_alloc &e) { + std::cerr << "Oh no, a bugpoint process ran out of memory!\n" + "To increase the allocation limits for bugpoint child\n" + "processes, use the -mlimit option.\n"; + } catch (const std::exception &e) { + std::cerr << "Whoops, a std::exception leaked out of bugpoint: " + << e.what() << "\n" + << "This is a bug in bugpoint!\n"; + } catch (...) { + std::cerr << "Whoops, an exception leaked out of bugpoint. " + << "This is a bug in bugpoint!\n"; + } + return 1; +} -- cgit v1.1