Add framework for iterative compilation to clang

[Radovan.Obradovic]

Summary

This patch adds command line option for iterative compilation, as well
as the code that invokes clang iteratively.
Communication between multiple runs is done over temporary files.

[Radovan.Obradovic]

This patch needs to be applied along with the patch for llvm.
See http://reviews.llvm.org/D4723 for more details.

[Radovan.Obradovic]

This is the new version of the patch which adds support for the iterative compilation to clang.

[petarj]

Ping.

[Radovan.Obradovic]

The patch is updated to be consistent with the patch for IC for LLVM.

[petarj]

This patch can now be abandoned, as an updated version is available at http://reviews.llvm.org/D12200 .

include/clang/Driver/Compilation.h

 //===--- Compilation.h - Compilation Task Data Structure --------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_DRIVER_COMPILATION_H
 #define LLVM_CLANG_DRIVER_COMPILATION_H
 
 #include "clang/Driver/Job.h"
 #include "clang/Driver/Util.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Analysis/DecisionTree.h"
 
 namespace llvm {
 namespace opt {
   class DerivedArgList;
   class InputArgList;
 }
 }
 
class Compilation {
 
   /// Result files which are generated correctly on failure, and which should
   /// only be removed if we crash.
   ArgStringMap FailureResultFiles;
 
   /// Redirection for stdout, stderr, etc.
   const StringRef **Redirects;
 
+  llvm::ModuleDecisionTrees *moduleDecisionTrees;
+
   /// Whether we're compiling for diagnostic purposes.
   bool ForDiagnostics;
 
 public:
   Compilation(const Driver &D, const ToolChain &DefaultToolChain,
               llvm::opt::InputArgList *Args,
               llvm::opt::DerivedArgList *TranslatedArgs);
   ~Compilation();
public:
 
   const ArgStringMap &getFailureResultFiles() const {
     return FailureResultFiles;
   }
 
   /// Returns the sysroot path.
   StringRef getSysRoot() const;
 
+  llvm::ModuleDecisionTrees *getModuleDecisionTrees() const { return moduleDecisionTrees; }
+
+  void setModuleDecisionTrees(llvm::ModuleDecisionTrees *x) { moduleDecisionTrees = x; }
+
   /// getArgsForToolChain - Return the derived argument list for the
   /// tool chain \p TC (or the default tool chain, if TC is not specified).
   ///
   /// \param BoundArch - The bound architecture name, or 0.
   const llvm::opt::DerivedArgList &getArgsForToolChain(const ToolChain *TC,
                                                        const char *BoundArch);
 
   /// addTempFile - Add a file to remove on exit, and returns its

include/clang/Driver/Driver.h

 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Driver/Phases.h"
 #include "clang/Driver/Types.h"
 #include "clang/Driver/Util.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
+#include "llvm/Analysis/DecisionTree.h"
 #include "llvm/Support/Path.h" // FIXME: Kill when CompilationInfo
 #include <memory>
                               // lands.
 #include <list>
 #include <set>
 #include <string>
 
 namespace llvm {
public:
   /// Set CC_LOG_DIAGNOSTICS mode, which causes the frontend to log diagnostics
   /// to CCLogDiagnosticsFilename or to stderr, in a stable machine readable
   /// format.
   unsigned CCLogDiagnostics : 1;
 
   /// Whether the driver is generating diagnostics for debugging purposes.
   unsigned CCGenDiagnostics : 1;
 
+  /// Module decision trees for iterative compilation.
+  llvm::ModuleDecisionTrees *moduleDecisionTrees;
+
 private:
   /// Name to use when invoking gcc/g++.
   std::string CCCGenericGCCName;
 
   /// Whether to check that input files exist when constructing compilation
   /// jobs.
   unsigned CheckInputsExist : 1;
 
public:
   Driver(StringRef _ClangExecutable,
          StringRef _DefaultTargetTriple,
          DiagnosticsEngine &_Diags);
   ~Driver();
 
   /// @name Accessors
   /// @{
 
+  llvm::ModuleDecisionTrees *getModuleDecisionTrees() const { return moduleDecisionTrees; }
+  void setModuleDecisionTrees(llvm::ModuleDecisionTrees *x) { moduleDecisionTrees = x; }
+
   /// Name to use when invoking gcc/g++.
   const std::string &getCCCGenericGCCName() const { return CCCGenericGCCName; }
 
   const llvm::opt::OptTable &getOpts() const { return *Opts; }
 
   const DiagnosticsEngine &getDiags() const { return Diags; }
 
   bool getCheckInputsExist() const { return CheckInputsExist; }

include/clang/Driver/Options.td

 def feliminate_unused_debug_symbols : Flag<["-"], "feliminate-unused-debug-symbols">, Group<f_Group>;
 def femit_all_decls : Flag<["-"], "femit-all-decls">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Emit all declarations, even if unused">;
 def femulated_tls : Flag<["-"], "femulated-tls">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Use emutls functions to access thread_local variables">;
 def fno_emulated_tls : Flag<["-"], "fno-emulated-tls">, Group<f_Group>;
 def fencoding_EQ : Joined<["-"], "fencoding=">, Group<f_Group>;
 def ferror_limit_EQ : Joined<["-"], "ferror-limit=">, Group<f_Group>, Flags<[CoreOption]>;
+def fiterative_comp_EQ : Joined<["-"], "fiterative-comp=">, Group<f_Group>,
+  HelpText<"Number of iterations for iterative compilation">;
 def fexceptions : Flag<["-"], "fexceptions">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Enable support for exception handling">;
 def fexcess_precision_EQ : Joined<["-"], "fexcess-precision=">,
     Group<clang_ignored_gcc_optimization_f_Group>;
 def : Flag<["-"], "fexpensive-optimizations">, Group<clang_ignored_gcc_optimization_f_Group>;
 def : Flag<["-"], "fno-expensive-optimizations">, Group<clang_ignored_gcc_optimization_f_Group>;
 def fextdirs_EQ : Joined<["-"], "fextdirs=">, Group<f_Group>;
 def : Flag<["-"], "fdefer-pop">, Group<clang_ignored_gcc_optimization_f_Group>;

lib/CodeGen/BackendUtil.cpp

 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/ObjCARC.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/SymbolRewriter.h"
+#include "llvm/Analysis/Passes.h"
 #include <memory>
 using namespace clang;
 using namespace llvm;
 
 namespace {
 
 class EmitAssemblyHelper {
   DiagnosticsEngine &Diags;
static void addMemorySanitizerPass(const PassManagerBuilder &Builder,
   PM.add(createMemorySanitizerPass(CGOpts.SanitizeMemoryTrackOrigins));
 
   // MemorySanitizer inserts complex instrumentation that mostly follows
   // the logic of the original code, but operates on "shadow" values.
   // It can benefit from re-running some general purpose optimization passes.
   if (Builder.OptLevel > 0) {
     PM.add(createEarlyCSEPass());
     PM.add(createReassociatePass());
+    PM.add(createICSetCurrentFuncPass());
     PM.add(createLICMPass());
     PM.add(createGVNPass());
     PM.add(createInstructionCombiningPass());
     PM.add(createDeadStoreEliminationPass());
   }
 }
 
 static void addThreadSanitizerPass(const PassManagerBuilder &Builder,

lib/Driver/Driver.cpp

Driver::Driver(StringRef ClangExecutable, StringRef DefaultTargetTriple,
     : Opts(createDriverOptTable()), Diags(Diags), Mode(GCCMode),
       SaveTemps(SaveTempsNone), ClangExecutable(ClangExecutable),
       SysRoot(DEFAULT_SYSROOT), UseStdLib(true),
       DefaultTargetTriple(DefaultTargetTriple),
       DriverTitle("clang LLVM compiler"), CCPrintOptionsFilename(nullptr),
       CCPrintHeadersFilename(nullptr), CCLogDiagnosticsFilename(nullptr),
       CCCPrintBindings(false), CCPrintHeaders(false), CCLogDiagnostics(false),
       CCGenDiagnostics(false), CCCGenericGCCName(""), CheckInputsExist(true),
-      CCCUsePCH(true), SuppressMissingInputWarning(false) {
+      CCCUsePCH(true), SuppressMissingInputWarning(false),
+      moduleDecisionTrees(0) {
 
   Name = llvm::sys::path::filename(ClangExecutable);
   Dir = llvm::sys::path::parent_path(ClangExecutable);
 
   // Compute the path to the resource directory.
   StringRef ClangResourceDir(CLANG_RESOURCE_DIR);
   SmallString<128> P(Dir);
   if (ClangResourceDir != "") {
Compilation *Driver::BuildCompilation(ArrayRef<const char *> ArgList) {
 
   // Owned by the host.
   const ToolChain &TC =
       getToolChain(*UArgs, computeTargetTriple(DefaultTargetTriple, *UArgs));
 
   // The compilation takes ownership of Args.
   Compilation *C = new Compilation(*this, TC, UArgs.release(), TranslatedArgs);
 
+  C->setModuleDecisionTrees(moduleDecisionTrees);
+
   if (!HandleImmediateArgs(*C))
     return C;
 
   // Construct the list of inputs.
   InputList Inputs;
   BuildInputs(C->getDefaultToolChain(), *TranslatedArgs, Inputs);
 
   // Construct the list of abstract actions to perform for this compilation. On

lib/Driver/Tools.cpp

 #include "llvm/Support/Compression.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Analysis/DecisionTree.h"
+#include <sstream>
 
 #ifdef LLVM_ON_UNIX
 #include <unistd.h> // For getuid().
 #endif
 
 using namespace clang::driver;
 using namespace clang::driver::tools;
 using namespace clang;
if (Arg *A = Args.getLastArg(options::OPT_ftabstop_EQ)) {
     CmdArgs.push_back(A->getValue());
   }
 
   CmdArgs.push_back("-ferror-limit");
   if (Arg *A = Args.getLastArg(options::OPT_ferror_limit_EQ))
     CmdArgs.push_back(A->getValue());
   else
     CmdArgs.push_back("19");
+  if (Arg *A = Args.getLastArg(options::OPT_fiterative_comp_EQ)) {
+    std::string Val = A->getValue();
+    int IterNo;
+    std::stringstream Convert(Val);
+    Convert >> IterNo;
+    if (IterNo > 1) {
+      CmdArgs.push_back("-mllvm");
+      CmdArgs.push_back("-fiterative-comp");
+      llvm::ModuleDecisionTrees *ModDecisionTrees =
+        C.getModuleDecisionTrees();
+      CmdArgs.push_back("-mllvm");
+      std::string &OptIF = ModDecisionTrees->getICInputFileOpt();
+      OptIF = "-fic-input-file=" + ModDecisionTrees->getICInputFile();
+      CmdArgs.push_back(OptIF.c_str());
+      CmdArgs.push_back("-mllvm");
+      std::string &OptIF2 = ModDecisionTrees->getICInputFile2Opt();
+      OptIF2 = "-fic-input2-file=" + ModDecisionTrees->getICInputFile2();
+      CmdArgs.push_back(OptIF2.c_str());
+      CmdArgs.push_back("-mllvm");
+      std::string &OptRF = ModDecisionTrees->getICResultsFileOpt();
+      OptRF = "-fic-results-file=" + ModDecisionTrees->getICResultsFile();
+      CmdArgs.push_back(OptRF.c_str());
+      CmdArgs.push_back("-mllvm");
+      std::string &OptRF2 = ModDecisionTrees->getICResultsFile2Opt();
+      OptRF2 = "-fic-results2-file=" + ModDecisionTrees->getICResultsFile2();
+      CmdArgs.push_back(OptRF2.c_str());
+    }
+  }
 
   if (Arg *A = Args.getLastArg(options::OPT_fmacro_backtrace_limit_EQ)) {
     CmdArgs.push_back("-fmacro-backtrace-limit");
     CmdArgs.push_back(A->getValue());
   }
 
   if (Arg *A = Args.getLastArg(options::OPT_ftemplate_backtrace_limit_EQ)) {
     CmdArgs.push_back("-ftemplate-backtrace-limit");

tools/driver/driver.cpp

 #include "llvm/Support/Signals.h"
 #include "llvm/Support/StringSaver.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <memory>
 #include <system_error>
+#include "llvm/Analysis/DecisionTree.h"
+#include "llvm/Support/Program.h"
+#include <string>
+#include <sstream>
 using namespace clang;
 using namespace clang::driver;
 using namespace llvm::opt;
 
 std::string GetExecutablePath(const char *Argv0, bool CanonicalPrefixes) {
   if (!CanonicalPrefixes)
     return Argv0;
 
int main(int argc_, const char **argv_) {
   if (!DiagOpts->DiagnosticSerializationFile.empty()) {
     auto SerializedConsumer =
         clang::serialized_diags::create(DiagOpts->DiagnosticSerializationFile,
                                         &*DiagOpts, /*MergeChildRecords=*/true);
     Diags.setClient(new ChainedDiagnosticConsumer(
         Diags.takeClient(), std::move(SerializedConsumer)));
   }
 
+  // Get number of iterations for iterative compilation.
+  int ICNumberOfIterations = 0;
+  std::string ICInputFile;
+  std::string ICInputFile2;
+  std::string ICResultsFile;
+  std::string ICResultsFile2;
+
+  std::unique_ptr<OptTable> CCopts(createDriverOptTable());
+  unsigned MissingArgIndex, MissingArgCount;
+  ArrayRef<const char*> argv_ref(argv);
+  InputArgList Args = CCopts->ParseArgs(argv_ref.slice(1),
+                                        MissingArgIndex, MissingArgCount);
+  if (Args.getLastArg(options::OPT_fiterative_comp_EQ)) {
+    std::string Val = Args.getLastArgValue(options::OPT_fiterative_comp_EQ, "1");
+    std::stringstream Convert(Val);
+    Convert >> ICNumberOfIterations;
+   }
+  if (!ICNumberOfIterations)
+    ICNumberOfIterations = 1; // Default value is 1.
+
+  llvm::ModuleDecisionTrees moduleDecisionTrees;
+
+  int CurrentIteration = 0;
+  int Res = 0;
+
+  llvm::FnNameAndPhase::ICPhase CurrICPhase = llvm::FnNameAndPhase::ModulePhase;
+
+  for (; CurrentIteration < ICNumberOfIterations; CurrentIteration++) {
+
   ProcessWarningOptions(Diags, *DiagOpts, /*ReportDiags=*/false);
 
   Driver TheDriver(Path, llvm::sys::getDefaultTargetTriple(), Diags);
   SetInstallDir(argv, TheDriver);
 
   llvm::InitializeAllTargets();
   insertArgsFromProgramName(ProgName, DS, argv, SavedStrings);
 
   SetBackdoorDriverOutputsFromEnvVars(TheDriver);
 
+  std::stringstream filename;
+
+  if (ICNumberOfIterations > 1) {
+    std::string ErrMsg;
+    SmallString<128> InputPath;
+    filename << "ic-input-" << CurrentIteration;
+    if (llvm::sys::fs::createTemporaryFile(filename.str(), ".json", InputPath)) {
+      llvm::errs() << "Error creating temporary file: " << ErrMsg << "\n";
+      ICNumberOfIterations = 1;
+    }
+    ICInputFile = InputPath.c_str();
+
+    SmallString<128> InputPath2;
+
+    filename.str("");
+    filename << "ic-input2-" << CurrentIteration;
+    if (llvm::sys::fs::createTemporaryFile(filename.str(), ".json", InputPath2)) {
+      llvm::errs() << "Error creating temporary file: " << ErrMsg << "\n";
+      ICNumberOfIterations = 1;
+    }
+    ICInputFile2 = InputPath2.c_str();
+
+    SmallString<128> ResPath;
+    filename.str("");
+    filename << "ic-results-" << CurrentIteration;
+    if (llvm::sys::fs::createTemporaryFile(filename.str(), ".json", ResPath)) {
+      llvm::errs() << "Error creating temporary file: " << ErrMsg << "\n";
+      ICNumberOfIterations = 1;
+    }
+    ICResultsFile = ResPath.c_str();
+
+    SmallString<128> ResPath2;
+    filename.str("");
+    filename << "ic-results2-" << CurrentIteration;
+    if (llvm::sys::fs::createTemporaryFile(filename.str(), ".json", ResPath2)) {
+      llvm::errs() << "Error creating temporary file: " << ErrMsg << "\n";
+      ICNumberOfIterations = 1;
+    }
+    ICResultsFile2 = ResPath2.c_str();
+
+    moduleDecisionTrees.getICInputFile() = ICInputFile;
+    moduleDecisionTrees.getICInputFile2() = ICInputFile2;
+    moduleDecisionTrees.getICResultsFile() = ICResultsFile;
+    moduleDecisionTrees.getICResultsFile2() = ICResultsFile2;
+    TheDriver.setModuleDecisionTrees(&moduleDecisionTrees);
+
+    std::map<llvm::FnNameAndPhase, llvm::BitVector> paths;
+    std::map<llvm::FnNameAndPhase, llvm::BitVector> paths1;
+    std::map<llvm::FnNameAndPhase, llvm::BitVector> paths2;
+    moduleDecisionTrees.getPaths(paths);
+    moduleDecisionTrees.startNewIteration();
+    moduleDecisionTrees.splitPaths(paths, paths1, paths2);
+    std::string pathsStr =
+      llvm::ModuleDecisionTrees::generateMdtPathsString(paths1);
+    llvm::DecisionTree::writeToFile(ICInputFile, pathsStr);
+    std::string pathsStr2 =
+      llvm::ModuleDecisionTrees::generateMdtPathsString(paths2);
+    llvm::DecisionTree::writeToFile(ICInputFile2, pathsStr2);
+  }
+
   std::unique_ptr<Compilation> C(TheDriver.BuildCompilation(argv));
   int Res = 0;
   SmallVector<std::pair<int, const Command *>, 4> FailingCommands;
   if (C.get())
     Res = TheDriver.ExecuteCompilation(*C, FailingCommands);
 
+  if (ICNumberOfIterations > 1) {
+    std::string ResultsStrJson = llvm::DecisionTree::readFromFile(ICResultsFile);
+    std::vector<llvm::MdtResults> ResultsJson;
+    std::string ErrorMsg;
+    if (!llvm::ModuleDecisionTrees::parseMdtResults(ResultsJson,
+      ResultsStrJson, ErrorMsg)) {
+      llvm::errs() << "ITERATIVE COMPILATION ERROR:" << ErrorMsg << "\n";
+      return 1;
+    }
+
+    std::string ResultsStr2Json = llvm::DecisionTree::readFromFile(ICResultsFile2);
+    std::vector<llvm::MdtResults> Results2Json;
+    if (!llvm::ModuleDecisionTrees::parseMdtResults(Results2Json,
+      ResultsStr2Json, ErrorMsg)) {
+      llvm::errs() << "ITERATIVE COMPILATION ERROR:" << ErrorMsg << "\n";
+      return 1;
+    }
+
+    llvm::sys::fs::remove(ICInputFile);
+    llvm::sys::fs::remove(ICInputFile2);
+    llvm::sys::fs::remove(ICResultsFile);
+    llvm::sys::fs::remove(ICResultsFile2);
+
+    std::vector<llvm::MdtResults> MergerdResults;
+    llvm::ModuleDecisionTrees::mergeMdtResults(MergerdResults,
+      ResultsJson, Results2Json);
+
+    std::string mergedResultsStr = llvm::ModuleDecisionTrees::generateMdtResultsString(
+                                            MergerdResults);
+
+    // Calculate the new decision three paths.
+    if (CurrICPhase == llvm::FnNameAndPhase::ModulePhase) {
+      int TotalFittness =
+        llvm::ModuleDecisionTrees::calculateTotalFitness(MergerdResults);
+      std::string ModuleNameId = "module-id";
+
+      llvm::MdtResults *ModuleResults = 0;
+      for (unsigned i = 0; i < MergerdResults.size(); i++) {
+        llvm::MdtResults &res = MergerdResults[i];
+        if (res.FunctionNameAndPhase.getName() == ModuleNameId)
+          ModuleResults = &res;
+      }
+
+      llvm::DecisionTree &dt =
+        moduleDecisionTrees.getDecisionTree(
+          llvm::FnNameAndPhase(ModuleNameId,
+                               llvm::FnNameAndPhase::ModulePhase));
+
+      if (ModuleResults)
+        dt.applyResults(*ModuleResults);
+
+      dt.setFunctionFitness(TotalFittness);
+      dt.updateBestFunctionFitness(CurrentIteration);
+
+
+      bool FinalIteration = false;
+      if (CurrentIteration >= ICNumberOfIterations - 2)
+        FinalIteration = true;
+      bool finished = dt.selectPath(FinalIteration);
+      if (finished && CurrentIteration < (ICNumberOfIterations - 2))
+        CurrentIteration = ICNumberOfIterations - 2;
+
+      dt.dumpToJSON(CurrentIteration);
+    }
+  }
+
   // Force a crash to test the diagnostics.
   if (::getenv("FORCE_CLANG_DIAGNOSTICS_CRASH")) {
     Diags.Report(diag::err_drv_force_crash) << "FORCE_CLANG_DIAGNOSTICS_CRASH";
 
     // Pretend that every command failed.
     FailingCommands.clear();
     for (const auto &J : C->getJobs())
       if (const Command *C = dyn_cast<Command>(&J))
#endif
     }
   }
 
   Diags.getClient()->finish();
 
   // If any timers were active but haven't been destroyed yet, print their
   // results now.  This happens in -disable-free mode.
   llvm::TimerGroup::printAll(llvm::errs());
-
+  } // iterative compiler
   llvm::llvm_shutdown();
 
 #ifdef LLVM_ON_WIN32
   // Exit status should not be negative on Win32, unless abnormal termination.
   // Once abnormal termiation was caught, negative status should not be
   // propagated.
   if (Res < 0)
     Res = 1;
 #endif
 
   // If we have multiple failing commands, we return the result of the first
   // failing command.
   return Res;
 }