New files for miscompilation detection

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5120 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 567 insertions, 0 deletions

diff --git a/tools/bugpoint/ExecutionDriver.cpp b/tools/bugpoint/ExecutionDriver.cpp
new file mode 100644
index 0000000..913fee8
--- /dev/null
+++ b/tools/bugpoint/ExecutionDriver.cpp
@@ -0,0 +1,191 @@
+//===- ExecutionDriver.cpp - Allow execution of LLVM program --------------===//
+//
+// This file contains code used to execute the program utilizing one of the
+// various ways of running LLVM bytecode.
+//
+//===----------------------------------------------------------------------===//
+
+/*
+BUGPOINT NOTES:
+
+1. Bugpoint should not leave any files behind if the program works properly
+2. There should be an option to specify the program name, which specifies a
+   unique string to put into output files.  This allows operation in the
+   SingleSource directory f.e.  Default to the first input filename.
+*/
+
+#include "BugDriver.h"
+#include "SystemUtils.h"
+#include "Support/CommandLine.h"
+#include <fstream>
+
+namespace {
+  // OutputType - Allow the user to specify the way code should be run, to test
+  // for miscompilation.
+  //
+  enum OutputType {
+    RunLLI, RunJIT, RunLLC, RunCBE
+  };
+  cl::opt<OutputType>
+  InterpreterSel(cl::desc("Specify how LLVM code should be executed:"),
+		 cl::values(clEnumValN(RunLLI, "run-lli", "Execute with LLI"),
+			    clEnumValN(RunJIT, "run-jit", "Execute with JIT"),
+			    clEnumValN(RunLLC, "run-llc", "Compile with LLC"),
+			    clEnumValN(RunCBE, "run-cbe", "Compile with CBE"),
+			    0));
+}
+
+/// AbstractInterpreter Class - Subclasses of this class are used to execute
+/// LLVM bytecode in a variety of ways.  This abstract interface hides this
+/// complexity behind a simple interface.
+///
+struct AbstractInterpreter {
+
+  virtual ~AbstractInterpreter() {}
+
+  /// ExecuteProgram - Run the specified bytecode file, emitting output to the
+  /// specified filename.  This returns the exit code of the program.
+  ///
+  virtual int ExecuteProgram(const std::string &Bytecode,
+			     const std::string &OutputFile) = 0;
+
+};
+
+
+//===----------------------------------------------------------------------===//
+// LLI Implementation of AbstractIntepreter interface
+//
+class LLI : public AbstractInterpreter {
+  std::string LLIPath;          // The path to the LLI executable
+public:
+  LLI(const std::string &Path) : LLIPath(Path) { }
+
+  // LLI create method - Try to find the LLI executable
+  static LLI *create(BugDriver *BD, std::string &Message) {
+    std::string LLIPath = FindExecutable("lli", BD->getToolName());
+    if (!LLIPath.empty()) {
+      Message = "Found lli: " + LLIPath + "\n";
+      return new LLI(LLIPath);
+    }
+
+    Message = "Cannot find 'lli' in bugpoint executable directory or PATH!\n";
+    return 0;
+  }
+  virtual int ExecuteProgram(const std::string &Bytecode,
+			     const std::string &OutputFile);
+};
+
+int LLI::ExecuteProgram(const std::string &Bytecode,
+			const std::string &OutputFile) {
+  const char *Args[] = {
+    "-abort-on-exception",
+    "-quiet",
+    Bytecode.c_str(),
+    0
+  };
+  
+  return RunProgramWithTimeout(LLIPath, Args,
+			       "/dev/null", OutputFile, OutputFile);
+}
+
+
+//===----------------------------------------------------------------------===//
+// 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: ";
+
+  // FIXME: This should default to searching for the best interpreter to use on
+  // this platform, which would be JIT, then LLC, then CBE, then LLI.
+
+  // Create an instance of the AbstractInterpreter interface as specified on the
+  // command line
+  std::string Message;
+  if (InterpreterSel == RunLLI) {
+    Interpreter = LLI::create(this, Message);
+  } else {
+    Message = " Sorry, only LLI is supported right now!";
+  }
+
+  std::cout << Message;
+
+  // If there was an error creating the selected interpreter, quit with error.
+  return Interpreter == 0;
+}
+
+
+/// 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 BytecodeFile) {
+  assert(Interpreter && "Interpreter should have been created already!");
+  bool CreatedBytecode = false;
+  if (BytecodeFile.empty()) {
+    // Emit the program to a bytecode file...
+    BytecodeFile = getUniqueFilename("bugpoint-test-program.bc");
+
+    if (writeProgramToFile(BytecodeFile, Program)) {
+      std::cerr << ToolName << ": Error emitting bytecode to file '"
+		<< BytecodeFile << "'!\n";
+      exit(1);
+    }
+    CreatedBytecode = true;
+  }
+
+  if (OutputFile.empty()) OutputFile = "bugpoint-execution-output";
+  
+  // Check to see if this is a valid output filename...
+  OutputFile = getUniqueFilename(OutputFile);
+
+  // Actually execute the program!
+  int RetVal = Interpreter->ExecuteProgram(BytecodeFile, OutputFile);
+
+  // Remove the temporary bytecode file.
+  if (CreatedBytecode)
+    removeFile(BytecodeFile);
+
+  // Return the filename we captured the output to.
+  return OutputFile;
+}
+
+/// 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.
+///
+bool BugDriver::diffProgram(const std::string &ReferenceOutputFile,
+			    const std::string &BytecodeFile) {
+  // Execute the program, generating an output file...
+  std::string Output = executeProgram("", BytecodeFile);
+
+  std::ifstream ReferenceFile(ReferenceOutputFile.c_str());
+  if (!ReferenceFile) {
+    std::cerr << "Couldn't open reference output file '"
+	      << ReferenceOutputFile << "'\n";
+    exit(1);
+  }
+
+  std::ifstream OutputFile(Output.c_str());
+  if (!OutputFile) {
+    std::cerr << "Couldn't open output file: " << Output << "'!\n";
+    exit(1);
+  }
+
+  bool FilesDifferent = false;
+
+  // Compare the two files...
+  int C1, C2;
+  do {
+    C1 = ReferenceFile.get();
+    C2 = OutputFile.get();
+    if (C1 != C2) { FilesDifferent = true; break; }
+  } while (C1 != EOF);
+
+  removeFile(Output);
+  return FilesDifferent;
+}
diff --git a/tools/bugpoint/Miscompilation.cpp b/tools/bugpoint/Miscompilation.cpp
new file mode 100644
index 0000000..3cccffe
--- /dev/null
+++ b/tools/bugpoint/Miscompilation.cpp
@@ -0,0 +1,141 @@
+//===- Miscompilation.cpp - Debug program miscompilations -----------------===//
+//
+// This file implements program miscompilation debugging support.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BugDriver.h"
+#include "SystemUtils.h"
+#include "llvm/Pass.h"
+#include "llvm/Module.h"
+#include "Support/CommandLine.h"
+
+// Anonymous namespace to define command line options for miscompilation
+// 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<std::string> 
+  Output("output", cl::desc("Specify a reference program output "
+			    "(for miscompilation detection)"));
+}
+
+/// 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() {
+  std::cout << "*** Debugging miscompilation!\n";
+
+  // Set up the execution environment, selecting a method to run LLVM bytecode.
+  if (initializeExecutionEnvironment()) return true;
+
+  // 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 whatever produced the input code.
+  //
+  bool CreatedOutput = false;
+  if (Output.empty()) {
+    std::cout << "Generating reference output from raw program...";
+    Output = executeProgram("bugpoint.reference.out");
+    CreatedOutput = true;
+    std::cout << " done!\n";
+  } else if (diffProgram(Output)) {
+    std::cout << "\n*** Input program does not match reference diff!\n"
+	      << "    Must be problem with input source!\n";
+    return false;  // Problem found
+  }
+
+  // Figure out which transformation is the first to miscompile the input
+  // program.  We do a binary search here in case there are a large number of
+  // passes involved.
+  //
+  unsigned LastGood = 0, LastBad = PassesToRun.size();
+  while (LastGood != LastBad) {
+    unsigned Mid = (LastBad+LastGood+1) / 2;
+    std::vector<const PassInfo*> P(PassesToRun.begin(),
+                                   PassesToRun.begin()+Mid);
+    std::cout << "Checking to see if the first " << Mid << " passes are ok: ";
+
+    std::string BytecodeResult;
+    if (runPasses(P, BytecodeResult, false, true)) {
+      std::cerr << ToolName << ": Error running this sequence of passes"
+		<< " on the input program!\n";
+      exit(1);
+    }
+
+    // Check to see if the finished program matches the reference output...
+    if (diffProgram(Output, BytecodeResult)) {
+      std::cout << "nope.\n";
+      LastBad = Mid-1;    // Miscompilation detected!
+    } else {
+      std::cout << "yup.\n";
+      LastGood = Mid;     // No miscompilation!
+    }
+
+    // We are now done with the optimized output... so remove it.
+    removeFile(BytecodeResult);
+  }
+
+  // Make sure something was miscompiled...
+  if (LastBad >= PassesToRun.size()) {
+    std::cerr << "*** Optimized program matches reference output!  No problem "
+	      << "detected...\nbugpoint can't help you with your problem!\n";
+    return false;
+  }
+
+  // Calculate which pass it is that miscompiles...
+  const PassInfo *ThePass = PassesToRun[LastBad];
+  
+  std::cout << "\n*** Found miscompiling pass '-" << ThePass->getPassArgument()
+            << "': " << ThePass->getPassName() << "\n";
+  
+  if (LastGood != 0) {
+    std::vector<const PassInfo*> P(PassesToRun.begin(), 
+                                   PassesToRun.begin()+LastGood);
+    std::string Filename;
+    std::cout << "Running good passes to get input for pass:";
+    if (runPasses(P, Filename, false, true)) {
+      std::cerr << "ERROR: Running the first " << LastGood
+                << " passes crashed!\n";
+      return true;
+    }
+    std::cout << " done!\n";
+    
+    // Assuming everything was successful, we now have a valid bytecode file in
+    // OutputName.  Use it for "Program" Instead.
+    delete Program;
+    Program = ParseInputFile(Filename);
+    
+    // Delete the file now.
+    removeFile(Filename);
+  }
+
+  bool Result = debugPassMiscompilation(ThePass, Output);
+
+  if (CreatedOutput) removeFile(Output);
+  return Result;
+}
+
+/// 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 BugDriver::debugPassMiscompilation(const PassInfo *Pass,
+                                        const std::string &ReferenceOutput) {
+  EmitProgressBytecode(Pass, "passinput");
+
+  // Loop over all of the functions in the program, attempting to find one that
+  // is being miscompiled.  We do this by extracting the function into a module,
+  // running the "bad" optimization on that module, then linking it back into
+  // the program.  If the program fails the diff, the function got misoptimized.
+  //
+
+
+  return false;
+}
diff --git a/tools/bugpoint/SystemUtils.cpp b/tools/bugpoint/SystemUtils.cpp
new file mode 100644
index 0000000..5483f80
--- /dev/null
+++ b/tools/bugpoint/SystemUtils.cpp
@@ -0,0 +1,189 @@
+//===- SystemUtils.h - Utilities to do low-level system stuff --*- C++ -*--===//
+//
+// This file contains functions used to do a variety of low-level, often
+// system-specific, tasks.
+//
+//===----------------------------------------------------------------------===//
+
+#include "SystemUtils.h"
+#include <algorithm>
+#include <fstream>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <sys/wait.h>
+#include <unistd.h>
+#include <errno.h>
+
+/// removeFile - Delete the specified file
+///
+void removeFile(const std::string &Filename) {
+  unlink(Filename.c_str());
+}
+
+/// getUniqueFilename - Return a filename with the specified prefix.  If the
+/// file does not exist yet, return it, otherwise add a suffix to make it
+/// unique.
+///
+std::string getUniqueFilename(const std::string &FilenameBase) {
+  if (!std::ifstream(FilenameBase.c_str()))
+    return FilenameBase;    // Couldn't open the file? Use it!
+
+  // Create a pattern for mkstemp...
+  char *FNBuffer = (char*)alloca(FilenameBase.size()+8);
+  strcpy(FNBuffer, FilenameBase.c_str());
+  strcpy(FNBuffer+FilenameBase.size(), "-XXXXXX");
+
+  // Agree on a temporary file name to use....
+  int TempFD;
+  if ((TempFD = mkstemp(FNBuffer)) == -1) {
+    std::cerr << "bugpoint: ERROR: Cannot create temporary file in the current "
+	      << " directory!\n";
+    exit(1);
+  }
+
+  // We don't need to hold the temp file descriptor... we will trust that noone
+  // will overwrite/delete the file while we are working on it...
+  close(TempFD);
+  return FNBuffer;
+}
+
+/// isExecutableFile - This function returns true if the filename specified
+/// exists and is executable.
+///
+bool isExecutableFile(const std::string &ExeFileName) {
+  struct stat Buf;
+  if (stat(ExeFileName.c_str(), &Buf))
+    return false;  // Must not be executable!
+
+  if (!(Buf.st_mode & S_IFREG))
+    return false;                    // Not a regular file?
+
+  if (Buf.st_uid == getuid())        // Owner of file?
+    return Buf.st_mode & S_IXUSR;
+  else if (Buf.st_gid == getgid())   // In group of file?
+    return Buf.st_mode & S_IXGRP;
+  else                               // Unrelated to file?
+    return Buf.st_mode & S_IXOTH;
+}
+
+
+// FindExecutable - Find a named executable, giving the argv[0] of bugpoint.
+// This assumes the executable is in the same directory as bugpoint itself.
+// If the executable cannot be found, return an empty string.
+//
+std::string FindExecutable(const std::string &ExeName,
+			   const std::string &BugPointPath) {
+  // First check the directory that bugpoint is in.  We can do this if
+  // BugPointPath contains at least one / character, indicating that it is a
+  // relative path to bugpoint itself.
+  //
+  std::string Result = BugPointPath;
+  while (!Result.empty() && Result[Result.size()-1] != '/')
+    Result.erase(Result.size()-1, 1);
+
+  if (!Result.empty()) {
+    Result += ExeName;
+    if (isExecutableFile(Result)) return Result; // Found it?
+  }
+
+  // Okay, if the path to bugpoint didn't tell us anything, try using the PATH
+  // environment variable.
+  const char *PathStr = getenv("PATH");
+  if (PathStr == 0) return "";
+
+  // Now we have a colon seperated list of directories to search... try them...
+  unsigned PathLen = strlen(PathStr);
+  while (PathLen) {
+    // Find the first colon...
+    const char *Colon = std::find(PathStr, PathStr+PathLen, ':');
+    
+    // Check to see if this first directory contains the executable...
+    std::string FilePath = std::string(PathStr, Colon) + '/' + ExeName;
+    if (isExecutableFile(FilePath))
+      return FilePath;                    // Found the executable!
+   
+    // Nope it wasn't in this directory, check the next range!
+    PathLen -= Colon-PathStr;
+    PathStr = Colon;
+    while (*PathStr == ':') {   // Advance past colons
+      PathStr++;
+      PathLen--;
+    }
+  }
+
+  // If we fell out, we ran out of directories in PATH to search, return failure
+  return "";
+}
+
+static void RedirectFD(const std::string &File, int FD) {
+  if (File.empty()) return;  // Noop
+
+  // Open the file
+  int InFD = open(File.c_str(), FD == 0 ? O_RDONLY : O_WRONLY|O_CREAT, 0666);
+  if (InFD == -1) {
+    std::cerr << "Error opening file '" << File << "' for "
+	      << (FD == 0 ? "input" : "output") << "!\n";
+    exit(1);
+  }
+
+  dup2(InFD, FD);   // Install it as the requested FD
+  close(InFD);      // Close the original FD
+}
+
+/// RunProgramWithTimeout - This function executes the specified program, with
+/// the specified null-terminated argument array, with the stdin/out/err fd's
+/// redirected, with a timeout specified on the commandline.  This terminates
+/// the calling program if there is an error executing the specified program.
+/// It returns the return value of the program, or -1 if a timeout is detected.
+///
+int RunProgramWithTimeout(const std::string &ProgramPath, const char **Args,
+			  const std::string &StdInFile,
+			  const std::string &StdOutFile,
+			  const std::string &StdErrFile) {
+
+  // FIXME: install sigalarm handler here for timeout...
+
+  int Child = fork();
+  switch (Child) {
+  case -1:
+    std::cerr << "ERROR forking!\n";
+    exit(1);
+  case 0:               // Child
+    RedirectFD(StdInFile, 0);      // Redirect file descriptors...
+    RedirectFD(StdOutFile, 1);
+    RedirectFD(StdErrFile, 2);
+
+    execv(ProgramPath.c_str(), (char *const *)Args);
+    std::cerr << "Error executing program '" << ProgramPath;
+    for (; *Args; ++Args)
+      std::cerr << " " << *Args;
+    exit(1);
+
+  default: break;
+  }
+
+  // Make sure all output has been written while waiting
+  std::cout << std::flush;
+
+  int Status;
+  if (wait(&Status) != Child) {
+    if (errno == EINTR) {
+      static bool FirstTimeout = true;
+      if (FirstTimeout) {
+	std::cout <<
+ "*** 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;
+      }
+      return -1;   // Timeout detected
+    }
+
+    std::cerr << "Error waiting for child process!\n";
+    exit(1);
+  }
+  return Status;
+}
diff --git a/tools/bugpoint/SystemUtils.h b/tools/bugpoint/SystemUtils.h
new file mode 100644
index 0000000..2d5dadc
--- /dev/null
+++ b/tools/bugpoint/SystemUtils.h
@@ -0,0 +1,46 @@
+//===- SystemUtils.h - Utilities to do low-level system stuff --*- C++ -*--===//
+//
+// This file contains functions used to do a variety of low-level, often
+// system-specific, tasks.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SYSTEMUTILS_H
+#define SYSTEMUTILS_H
+
+#include <string>
+
+/// isExecutableFile - This function returns true if the filename specified
+/// exists and is executable.
+///
+bool isExecutableFile(const std::string &ExeFileName);
+
+// FindExecutable - Find a named executable, giving the argv[0] of bugpoint.
+// This assumes the executable is in the same directory as bugpoint itself.
+// If the executable cannot be found, return an empty string.
+//
+std::string FindExecutable(const std::string &ExeName,
+			   const std::string &BugPointPath);
+
+/// removeFile - Delete the specified file
+///
+void removeFile(const std::string &Filename);
+
+/// getUniqueFilename - Return a filename with the specified prefix.  If the
+/// file does not exist yet, return it, otherwise add a suffix to make it
+/// unique.
+///
+std::string getUniqueFilename(const std::string &FilenameBase);
+
+/// RunProgramWithTimeout - This function executes the specified program, with
+/// the specified null-terminated argument array, with the stdin/out/err fd's
+/// redirected, with a timeout specified on the commandline.  This terminates
+/// the calling program if there is an error executing the specified program.
+/// It returns the return value of the program, or -1 if a timeout is detected.
+///
+int RunProgramWithTimeout(const std::string &ProgramPath, const char **Args,
+			  const std::string &StdInFile = "",
+			  const std::string &StdOutFile = "",
+			  const std::string &StdErrFile = "");
+
+#endif