Add framework for iterative compilation to llvm

[zoran.jovanovic]

Summary

This patch adds necessary parts to implement iterative compilation in
llvm: decision trees and three passes (ModuleDecisionTreeProxy,
FunctionFitness and ICSetCurrentFunc). Further, inliner, LICM and register allocator
are modified to support the iterative approach.

[zoran.jovanovic]

This is a follow-up work on the iterative compilation framework for clang/llvm.
Initial discussion as well as the introduction to this approach has been presented at:

http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-December/thread.html#68784

Previous patch revisions (same as suggestions to create new revision for this patch) can be found at:

http://reviews.llvm.org/D4723

Here is a short explanation of the forming of the decision tree.

First, some passes need to be modified to call getDecision function.
If this function returns false, a pass should do exactly as the code without modification.
If the return value is true, then the alternative path is taken.

Function getDecison always returns false in the first iteration.
And the compiler should work exactly as if there was no iterrative framework.

Let us assume that getDecision function is called four times in the first iteration of iterative compilation.
After the end of the first iteration, the decision tree will look like this:

o
\
  o
    \
      o
        \
          o
            \
              o

In the second iteration, exactly one decision is changed and the compiler works as in the first iteration until it reaches this particular decision. Then alternative path is taken in this point.
Further, getDecision function returns false until compilation iteration is finished. Let us assume that we took alternative decision at the third decision and that there are three more calls
of getDecision function. Note that different compilation paths may have different number of calls of getDecision function.

o
\
  o
    \
      o
    /   \
   o      o
     \      \
       o      o
         \
           o

Every new iteration adds one new branch to the decision tree.

At the end of each iteration fitness of the generated code is evaluated. In the last iteration, the compiler takes the path with the best fitness.

To augment the selection of a node where alternative decision would be taken, getDecision tree takes one parameter.
This parameter is interpreted as priority and the node with highest priory is selected for next alternative decision.

Machine learning approach

Formed decision tree can be used to train a binary classifier which can be used to facilitate existing heuristics. By collecting nodes where branching of decision tree occurred, we have training examples for the classifier. We could replace existing heuristics with this trained classifier and potentially get better code even without iterative approach.

This may be a good approach for jit compiler but it requires adding this machine learning approach which is planed for the future.

N-ary decisions are not planed for now because every n-ary decision can be replaced with n-1 binary decision. For example if we have to decide for a number from zero to three we can set three yes/no questions:

(number is zero or greater then zero?)
  /                            \
0             (number is one or greater then one?)
                /                      \
               1               (number is 2 or 3?)
                                  /          \
                                 2            3

If some decisions are made relevant by some future decisions this is only some inefficiency of the compilation process but they stay in the decision tree because nodes are never deleted. The nodes represent some decision points in the history, and path from the root of the tree to the leaf has enough information to exactly replay compilation iteration.

This patch includes:

Code refactoring.

Rebase
This version of patch is rebased to current trunk.

Decision points in pre-codegen and in codegen phase
This version introduces support for decision points in both
pre-codegen and codegen phase.

This feature led to a lot changes in code becuse implementation of the
ImmutablePass is such that an ImmutablePass is destroyed between
pre-codegen and codegen phase. The issue is resolved with temporary
JSON files which pass information between those two phases. Also, we
had to merge results from these phases.

We find that such behaviour of ImmutablePass and boundary between
pre-codegen and codegen phases is a bit strange and that there is
space for improvements which would simplify this patch and
implementation of similar features in llvm.

New optimization point - RegAllocGreedy
Decision points in codegen phase enabled us to implement a new
optimization point where iterative compilation can take an alternative
path. In this version of patch iterative compilation can take
alternative paths in register allocation, next to LICM and Inliner
which were present in the old version, too.

Added unit tests for DecissionTree, FileUtils and ModuleDecisionTreeProxies.

Bugfixes
During development we fixed some bugs. Some of them were introduced by
new changes and some were existing even in the old version.

Testing procedure and current status
We are targeting MIPS architecture and current testing procedure looks
like this:

create CSiBE test configuration
preprocess files with gcc
run all tests with -Oz -target mipsel-unknown-linux
-fiterative-comp=n -S

assemble output with MIPS gcc toolchain
measure results with size
Our results show that there are improvements of up to 8.78% in code
size which is promising and we are working on getting such results in
more cases and getting even better results.

Our results also show that making alternative decisions in compilation
path in LICM, Inliner or RegAlloc only (separated) can lead to
improvements in code size up to, respectively, 6%, 5% and 8%. This
results proved our assumption that these optimization points are good
for making decisions to take alternative compilation path is true.

Significant improvements are seen as early as with 10 iterations, but
100 iterations lead to even better results. As expected, improvements
and iteration count are not linearly dependant.

RFC
We would like to see this feature (iterative compilation) merged into
the LLVM/Clang core and we would like to hear what we should change
and improve so this will be possible in the future.

We would also like to hear from you if you find this approach
interesting and get any suggestion where to steer research and
experiments. Any suggestions which passes have potential for taking
alternative path?

Currently, there are few issues that we are working among which the
most interesting are:

Register allocator has higher priority than other optimization
points so we will change implementation in that way that all
optimization points can get a chance to take alternative direction

Our decision whether to take an alternative path or not is based on
a fitness function which can be improved. We will be working on
that, too.

Please, feel free to experiment with this patch and to contact us for
any help and information.

[zoran.jovanovic]

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

[zoran.jovanovic]

*Places for improvement*

Our research identified couple of places where improvements can be made:

• DecisionTreeNodes priorities can be tuned better
• Tree exploration can be made faster

*Implemented solutions*
This patch addresses the first issue.

Original idea is to find spots where heuristic result isn't
confident. Those values should be inspected carefully and normalized
which we can improve. Because of this, our implementation was biased
to explore alternative decisions of only one (RegAllocGreedy)
optimization point.

This problem is for now solved with introducing "round robin" tree
exploration which tries to mask out nodes of already used optimization
until all optimizations are exhausted or there are no available nodes
of unused optimizations. When all optimizations are used / there are
no available nodes to choose, we restart masking process. (An
optimization, or optimization point is considered as used if node of
that optimization was chosen for making alternative decision and
producing an alternative path.)

This solution enabled as to vary position in decision tree where we
make alternative decision which led to significant improvements.

Another improvement in this patch is randomization of node choice. Let
us define best node as a node with lowest function fitness (node is on
path which leads to smallest code size) and with highest priority. The
issue is that there are usually more than one such node in the
decision tree, for every optimization. In previous revisions, only
first best node was considered for making alternative decision. In
this revision, we collect all equivalent best nodes and randomly
choose one of them.

This randomization led to even faster tree exploration and greater
improvements.

*Current results*
We continued with benchmarking LLVM IC framework using CSiBE test. Our
results show that this patch can give results for 10 iterations as
good as old version for 100 iterations! As expected, this version
outperformed old version on 100 iterations.

*Further work*
To make improvements mentioned in the beginning, we will try to split
decision tree in such way that every function has it's own decision
tree. That way, every function would have smaller tree, and separate
functions could be optimized in parallel. With this implemented, we
expect to get even smaller code size but keeping number of iterations
reasonable small.

Priority tuning still stays open for suggestions and further work.

[zoran.jovanovic]

This version introduces new algorithm for exploring decision trees.
As stated in the last patch, splitting one big decision tree into multiple ones for every function in compilation unit can improve results.
Furthermore, separate decision trees are needed for each optimization phase (interprocedural, precodegen and codegen).

The algorithm spends 1/3 of iterations on searching for the best combination of alternative decisions for trees of each phase for every function in parallel. We got some improvement in code size for 5% more test cases which adds up to roughly 25% of test cases where our algorithm achieved smaller code size than non-iterative version.

Those results show that implementing parallel explore enables deeper exploration of the decision tree for the same number of iterations.

Comments are welcome.

[zoran.jovanovic]

Just to PING.
Any comments on this work?

[zoran.jovanovic]

New patch version rebased to r256194.
Any comments on this work?

[grosser]

Hi Zoran,

me and one of my students started to play with this patch. However, unfortunately it does not seem to work. Using a minimal example:

$ cat /tmp/test.c
int main() {}

we see the following error:

bin/clang -S -fiterative-comp=2 /tmp/test.c -c
ITERATIVE COMPILATION ERROR:

The problem seems to be that only one file is written during module finalization:

if (ICPhase != FnNameAndPhase::CodeGenPhase) {                               
  resultsFile = new ICResultsFile(FicResultsFile);                           
}                                                                            
else {                                                                       
  resultsFile = new ICResultsFile(FicResultsFile2);                          
}

but both files are unconditionally read by clang:

+int loadResultFiles(llvm::ModuleDecisionTrees &MDT,
+                    std::vector<llvm::MdtResults> &merged) {
+  llvm::ICResultsFile results1 = MDT.getICResultsFile();
+  llvm::ICResultsFile results2 = MDT.getICResultsFile2();
+
+  int r1 = results1.read();
+  int r2 = results2.read();
+
+  if(r1 || r2)
+    return 1;
+
+  llvm::MdtResults::mergeMdtResults(merged,
+      results1.getResults(), results2.getResults());
+
+  return 0;
+}

It is currently unclear what the expected behavior is. Do you happen a minimal example that would allow us to use this IC patch with clang and see at least two different inlining choices to be explored?

[zoran.jovanovic]

In order to use iterative compilation algorithm for target different then MIPS it is necessary to implement appropriate function fitness pass that evaluates generated code. In our patch criteria used is code size and pass is implemented in lib/Target/Mips/MipsFunctionFitness.cpp file.
In case of X86 code size calculation is more complex because of variable-length machine instruction encoding.
We are looking for possibilities to issue more informative error message until architecture is supported.

include/llvm/Analysis/ICDecisionTree.h

+//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===//
+//
+//                     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 decision tree and decision tree proxy classes
+// which are used in iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ICDECISIONTREE_H
+#define LLVM_ANALYSIS_ICDECISIONTREE_H
+
+#include <string>
+#include <vector>
+#include <map>
+#include "llvm/ADT/BitVector.h"
+#include "llvm/Pass.h"
+#include "llvm/Analysis/ICUtils.h"
+
+namespace llvm {
+
+struct DecisionTreeNode {
+  DecisionTreeNode();
+  DecisionTreeNode(DecisionTreeNode *parent, int id);
+  int calcFinalPriority(int bestFunctionFitness);
+  DecisionTreeNode *Parent;
+  DecisionTreeNode *PrimaryDecision;
+  DecisionTreeNode *AlternativeDecision;
+  int Priority;
+  int Fitness;
+  int Depth;
+  int NodeId;
+  bool IsInterprocedural;
+  ICOptimization Optimization;
+
+  std::string getJSON();
+};
+
+/// Decision tree controls the iterative compilation process so
+/// that compiler takes different path in each compilation except in
+/// the final iteration when the path which generates the best code is taken .
+class DecisionTree {
+protected:
+  DecisionTreeNode *DecisionTreeRoot;
+  DecisionTreeNode *CurrentNode;
+  BitVector Path;
+  SmallVector<ICOptimization, 128> Optimizations;
+  int FunctionFitness;
+  int BestFunctionFitness;
+  BitVector BestPath;
+  int NodeIdCount;
+
+public:
+  DecisionTree();
+  ~DecisionTree();
+
+  int getFunctionFitness() const { return FunctionFitness; }
+  void setFunctionFitness(int x) { FunctionFitness = x; }
+  BitVector &getPath() { return Path; }
+  const BitVector &getPath() const { return Path; }
+  SmallVector<ICOptimization, 128> &getOptimizations()
+    { return Optimizations; }
+  const SmallVector<ICOptimization, 128> &getOptimizations()
+    const { return Optimizations; }
+  int getNodeIdCount() {return NodeIdCount;}
+  DecisionTreeNode* getCurrentNode() {return CurrentNode;}
+
+  bool getDecision(int priority, ICOptimization opt);
+  void updateBestFunctionFitness(int iteration);
+  void findPath(DecisionTreeNode *node, BitVector &path);
+  bool selectPath(bool FinalPass);
+  DecisionTreeNode* selectNode();
+  void startNewIteration();
+  void updateNodesFitness();
+
+  void applyResults(const MdtResults &results);
+
+  void splitPath(
+    const BitVector &paths,
+    BitVector &pathBeforeCodegen,
+    BitVector &pathAfterCodegen);
+
+  void dumpToGv(int currentIteration);
+  void dumpToJSON(int currentIteration);
+
+  void addPrimaryDecision();
+  void addPrimaryDecision(llvm::DecisionTreeNode *node);
+  void addAlternativeDecision();
+  void addAlternativeDecision(llvm::DecisionTreeNode *node);
+  llvm::DecisionTreeNode* getRootNode();
+};
+
+}
+
+#endif

include/llvm/Analysis/ICFileUtils.h

+#ifndef LLVM_ANALYSIS_ICFILEUTILS_H
+#define LLVM_ANALYSIS_ICFILEUTILS_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/Analysis/ICUtils.h"
+#include <string>
+#include <vector>
+#include <map>
+
+namespace llvm {
+
+class ICFile {
+public:
+  ICFile() {}
+  ICFile(std::string filename) { this->filename = filename;}
+  ICFile(std::string filePrefix, int iteration);
+
+  SmallString<128> createTmpFile(std::string filename, int CurrentIteration);
+  void writeToFile(const std::string &fileName, const std::string &data);
+  std::string readFromFile(const std::string &fileName);
+
+  bool exists();
+  void remove();
+
+  std::string getFilename() { return filename; }
+
+  virtual void write() = 0;
+  virtual bool read() = 0;
+
+protected:
+  std::string filename;
+};
+
+class ICInputFile : public ICFile {
+public:
+  ICInputFile() {}
+  ICInputFile(std::string filename) : ICFile(filename) {}
+  ICInputFile(std::string filePrefix, int iteration)
+    : ICFile(filePrefix, iteration) {}
+
+  ICPathsMap getPaths() {return this->paths;}
+  void setPaths(ICPathsMap paths) { this->paths = paths;}
+
+  void write();
+  bool read();
+
+private:
+  ICPathsMap paths;
+};
+
+class ICResultsFile : public ICFile {
+public:
+  ICResultsFile() {}
+  ICResultsFile(std::string filename) : ICFile(filename) {}
+  ICResultsFile(std::string filePrefix, int iteration)
+    : ICFile(filePrefix, iteration) {}
+
+  std::vector<MdtResults> getResults() {return this->results;}
+  void setResults(std::vector<MdtResults> results) { this->results = results;}
+
+  void write();
+  bool read();
+
+private:
+  std::vector<MdtResults> results;
+};
+}
+
+
+#endif

include/llvm/Analysis/ICPass.h

+//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===//
+//
+//                     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 decision tree and decision tree proxy classes
+// which are used in iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ICPASS_H
+#define LLVM_ANALYSIS_ICPASS_H
+
+#include <string>
+#include <vector>
+#include <map>
+#include "llvm/ADT/BitVector.h"
+#include "llvm/Pass.h"
+#include "llvm/Analysis/ICUtils.h"
+#include "llvm/Analysis/ICDecisionTree.h"
+#include "llvm/Analysis/ICProxies.h"
+
+namespace llvm {
+
+/// This ImmutablePass provides a persistent place to hold the
+/// decision trees proxies (for each function and for each
+/// compilation phase) during the iterative compilation process so
+/// they can be easily accessed from passes which can take advantage
+/// of iterative compilation.
+class ModuleDecisionTreeProxies : public ImmutablePass {
+public:
+  static char ID;
+
+  ModuleDecisionTreeProxies();
+  ~ModuleDecisionTreeProxies();
+  virtual bool doInitialization(Module &M);
+  virtual bool doFinalization(Module &M);
+
+  bool getDecision(int priority, ICOptimization opt);
+
+  void setCurrentFunctionAndPhase(const std::string &fnName,
+    FnNameAndPhase::ICPhase phase);
+  void setModuleCompilationPhase();
+  DecisionTreeProxy &getDecisionTreeProxy(const FnNameAndPhase &x);
+  DecisionTreeProxy &getDecisionTreeProxy(const std::string &name,
+    FnNameAndPhase::ICPhase phase);
+  void setPaths(std::map<FnNameAndPhase, BitVector> &paths);
+  void getResults(std::vector<MdtResults> &results) const;
+  DecisionTreeProxy *getCurrFnDecisionTreeProxy()
+  { return CurrFnDecisionTreeProxy; }
+  bool getIterativeCompilation() { return IterativeCompilation; }
+  void setIterativeCompilation(bool x) { IterativeCompilation = x; }
+protected:
+  bool IterativeCompilation;
+  std::map<FnNameAndPhase, DecisionTreeProxy *> DecisionTreeProxies;
+  DecisionTreeProxy *CurrFnDecisionTreeProxy;
+  FnNameAndPhase::ICPhase ICPhase;
+};
+
+}
+
+#endif

include/llvm/Analysis/ICProxies.h

+//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===//
+//
+//                     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 decision tree and decision tree proxy classes
+// which are used in iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ICPROXIES_H
+#define LLVM_ANALYSIS_ICPROXIES_H
+
+#include <string>
+#include <vector>
+#include <map>
+#include "llvm/ADT/BitVector.h"
+#include "llvm/Pass.h"
+#include "llvm/Analysis/ICUtils.h"
+#include "llvm/Analysis/ICDecisionTree.h"
+#include "llvm/Analysis/ICFileUtils.h"
+
+namespace llvm {
+
+/// Decision tree proxy is the proxy class for the decision tree so
+/// that it has the method getDecision and the all data can be effectively
+/// streamed between proxy and the decision tree.
+class DecisionTreeProxy {
+public:
+  DecisionTreeProxy();
+
+  BitVector &getPath() { return Path; }
+  const BitVector &getPath() const { return Path; }
+  int getFunctionFitness() const { return FunctionFitness; }
+  void setFunctionFitness(int x) { FunctionFitness = x; }
+
+  std::vector<int> &getPriorities() { return Priorities; }
+  const std::vector<int> &getPriorities() const { return Priorities; }
+
+  std::vector<ICOptimization> &getOptimizations() { return Optimizations; }
+  const std::vector<ICOptimization> &getOptimizations() const {
+    return Optimizations; }
+
+  bool getDecision(int priority, ICOptimization opt);
+
+  std::string generateResultsString();
+  MdtResults getResults() const;
+  void setPath(const BitVector &path);
+
+protected:
+  BitVector Path;
+  int FunctionFitness;
+  int BestFunctionFitness;
+  std::vector<int> Priorities;
+  std::vector<ICOptimization> Optimizations;
+  int CurrentDepth;
+};
+
+/// This class is the storage for all the decision trees for
+/// each function and compilation phase.
+class ModuleDecisionTrees {
+public:
+
+  ModuleDecisionTrees();
+  ~ModuleDecisionTrees();
+
+  DecisionTree &getDecisionTree(const FnNameAndPhase &fnNameAndPhase);
+
+  void startNewIteration();
+  void getPaths(std::map<FnNameAndPhase, BitVector> &paths);
+  void applyResults(const std::vector<MdtResults> &results);
+  void updateBestFunctionFitness(int iteration);
+  void updateNodesFitness();
+  void selectPath(bool FinalPass);
+  void splitPaths(
+    const std::map<FnNameAndPhase, BitVector> &paths,
+    std::map<FnNameAndPhase, BitVector> &pathBeforeCodegen,
+    std::map<FnNameAndPhase, BitVector> &pathAfterCodegen);
+  std::string &getICInputFileOpt() { return ICInputFileOpt; }
+  std::string &getICInputFile2Opt() { return ICInputFile2Opt; }
+  std::string &getICResultsFileOpt() { return ICResultsFileOpt; }
+  std::string &getICResultsFile2Opt() { return ICResultsFile2Opt; }
+
+  ICInputFile &getICInputFile() { return input1; }
+  ICInputFile &getICInputFile2() { return input2; }
+  ICResultsFile &getICResultsFile() { return results1; }
+  ICResultsFile &getICResultsFile2() { return results2; }
+
+protected:
+  std::map<FnNameAndPhase, DecisionTree *> DecisionTrees;
+  std::string ICInputFileOpt;
+  std::string ICInputFile2Opt;
+  std::string ICResultsFileOpt;
+  std::string ICResultsFile2Opt;
+
+  ICInputFile input1;
+  ICInputFile input2;
+  ICResultsFile results1;
+  ICResultsFile results2;
+};
+
+}
+
+#endif

include/llvm/Analysis/ICSetCurrentFunc.h

+//===-- ICSetCurrentFunc.h - Iterative Comp Set Current Func DT -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implements the pass which sets the decision tree proxy of the
+// current function.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ICSETCURRENTFUNC_H
+#define LLVM_ANALYSIS_ICSETCURRENTFUNC_H
+
+#include "llvm/Pass.h"
+#include "llvm/Analysis/IterativeCompilation.h"
+
+namespace llvm {
+
+class ICSetCurrentFunc : public FunctionPass {
+public:
+  std::string name;
+  ModuleDecisionTreeProxies *MD;
+  static char ID;
+  ICSetCurrentFunc() : FunctionPass(ID) {
+    initializeICSetCurrentFuncPass(*PassRegistry::getPassRegistry());
+  }
+
+  virtual bool runOnFunction(Function &F);
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<ModuleDecisionTreeProxies>();
+  }
+};
+
+}
+
+#endif

include/llvm/Analysis/ICUtils.h

+//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===//
+//
+//                     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 decision tree and decision tree proxy classes
+// which are used in iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ICUTILS_H
+#define LLVM_ANALYSIS_ICUTILS_H
+
+#include <string>
+#include "llvm/Support/CommandLine.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/BitVector.h"
+#include <map>
+#include <vector>
+
+namespace llvm {
+
+extern cl::opt<bool> IterativeCompilationOpt;
+extern cl::opt<std::string> FicInputFile;
+extern cl::opt<std::string> FicInputFile2;
+extern cl::opt<std::string> FicResultsFile;
+extern cl::opt<std::string> FicResultsFile2;
+
+/// Iterative Compilation Optimization
+enum ICOptimization {
+  NoOptimization,
+  InlinerOpt,
+  LicmOpt,
+  RegAllocOpt
+};
+
+const int MaxDtPriority = 1000;
+
+class FnNameAndPhase {
+public:
+
+  /// Iterative Compilation Phase
+  enum ICPhase {
+    FunctionPhase, /// Function level phase include passes that operate
+                   /// with the target independent IR like LICM. In this
+                   /// phase there is one decision tree for each function.
+
+    ModulePhase,   /// Module level phase include interprocedural optimizations
+                   /// like function inliner. In this phase there is only one
+                   /// decision tree for the whole module.
+
+    CodeGenPhase   /// Codegen phase include passes like register allocator,
+                   /// scheduler and instruction selection. In this
+                   /// phase there is also one decision tree for each function.
+  };
+
+  FnNameAndPhase() : Phase(ModulePhase) {}
+  FnNameAndPhase(const FnNameAndPhase &x) : Name(x.Name), Phase(x.Phase)
+    {}
+  FnNameAndPhase(const std::string &name, ICPhase phase)
+    : Name(name), Phase(phase) {}
+
+  bool operator < (const FnNameAndPhase &x) const {
+    if (Phase != x.Phase)
+      return Phase < x.Phase;
+    return Name < x.Name;
+  }
+
+  const std::string &getName() const { return Name; }
+  ICPhase getPhase() const { return Phase; }
+
+protected:
+  std::string Name;
+  ICPhase Phase;
+};
+
+class MdtResults {
+public:
+  FnNameAndPhase FunctionNameAndPhase;
+  int Fitness;
+  std::vector<int> Priorities;
+  std::vector<ICOptimization> Optimizations;
+
+  static bool parseMdtResults(
+      std::vector<MdtResults> &results,
+      const std::string &resString,
+      std::string &ErrorMessage);
+
+  static std::string generateMdtResultsString(
+      const std::vector<MdtResults> &results);
+
+  static void mergeMdtResults(std::vector<MdtResults> &mergedResults,
+                       const std::vector<MdtResults> &results1,
+                       const std::vector<MdtResults> &results2);
+
+  static int calculateTotalFitness(const std::vector<MdtResults> &results);
+  static MdtResults* getByPhase(const std::vector<MdtResults> &results,
+      FnNameAndPhase::ICPhase phase);
+};
+
+typedef std::map<FnNameAndPhase, BitVector> ICPathsMap;
+
+//-------- convert to and from string ----//
+std::string BitVector2Str(const BitVector &path);
+std::string Path2Str(const FnNameAndPhase &nameAndPhase, const BitVector &path);
+
+//--------- parsers and generators --------//
+bool parseMdtPaths(ICPathsMap &paths,
+                   const std::string &pathString,
+                   std::string &ErrorMessage);
+
+std::string generateMdtPathsString(const ICPathsMap &paths);
+}
+
+
+#endif

include/llvm/Analysis/IterativeCompilation.h

+#ifndef LLVM_ANALYSIS_ITERATIVECOMPILATION_H
+#define LLVM_ANALYSIS_ITERATIVECOMPILATION_H
+
+#include "llvm/Analysis/ICUtils.h"
+#include "llvm/Analysis/ICDecisionTree.h"
+#include "llvm/Analysis/ICProxies.h"
+#include "llvm/Analysis/ICPass.h"
+#include "llvm/Analysis/ICFileUtils.h"
+
+#endif

include/llvm/Analysis/Passes.h

namespace llvm {
 
   //===--------------------------------------------------------------------===//
   //
   // createMemDerefPrinter - This pass collects memory dereferenceability
   // information and prints it with -analyze.
   //
   FunctionPass *createMemDerefPrinter();
 
+  //===--------------------------------------------------------------------===//
+  //
+  // createICSetCurrentFuncPass - This pass sets decision tree proxy of the
+  // current function which is used in iterative compilation.
+  //
+  FunctionPass *createICSetCurrentFuncPass();
+
 }
 
 #endif

include/llvm/InitializePasses.h

 void initializeSCCPPass(PassRegistry&);
 void initializeSROAPass(PassRegistry&);
 void initializeSROA_DTPass(PassRegistry&);
 void initializeSROA_SSAUpPass(PassRegistry&);
 void initializeScalarEvolutionAliasAnalysisPass(PassRegistry&);
 void initializeScalarEvolutionWrapperPassPass(PassRegistry&);
 void initializeShrinkWrapPass(PassRegistry &);
 void initializeSimpleInlinerPass(PassRegistry&);
-void initializeShadowStackGCLoweringPass(PassRegistry&);  
+void initializeShadowStackGCLoweringPass(PassRegistry&);
 void initializeRegisterCoalescerPass(PassRegistry&);
 void initializeSingleLoopExtractorPass(PassRegistry&);
 void initializeSinkingPass(PassRegistry&);
 void initializeSeparateConstOffsetFromGEPPass(PassRegistry &);
 void initializeSlotIndexesPass(PassRegistry&);
 void initializeSpillPlacementPass(PassRegistry&);
 void initializeSpeculativeExecutionPass(PassRegistry&);
 void initializeStackProtectorPass(PassRegistry&);

 void initializeWinEHPreparePass(PassRegistry&);
 void initializePlaceBackedgeSafepointsImplPass(PassRegistry&);
 void initializePlaceSafepointsPass(PassRegistry&);
 void initializeDwarfEHPreparePass(PassRegistry&);
 void initializeFloat2IntPass(PassRegistry&);
 void initializeLoopDistributePass(PassRegistry&);
 void initializeSjLjEHPreparePass(PassRegistry&);
 void initializeDemandedBitsPass(PassRegistry&);
+void initializeModuleDecisionTreeProxiesPass(PassRegistry&);
+void initializeFunctionFitnessPass(PassRegistry&);
+void initializeICSetCurrentFuncPass(PassRegistry&);
 }
 
 #endif

include/llvm/Transforms/IPO/InlinerPass.h

 #include "llvm/Analysis/CallGraphSCCPass.h"
 
 namespace llvm {
   class CallSite;
   class DataLayout;
   class InlineCost;
   template<class PtrType, unsigned SmallSize>
   class SmallPtrSet;
+  class ModuleDecisionTreeProxies;
 
 /// Inliner - This class contains all of the helper code which is used to
 /// perform the inlining operations that do not depend on the policy.
 ///
 struct Inliner : public CallGraphSCCPass {
   explicit Inliner(char &ID);
   explicit Inliner(char &ID, int Threshold, bool InsertLifetime);
 

 
 private:
   // InlineThreshold - Cache the value here for easy access.
   unsigned InlineThreshold;
 
   // InsertLifetime - Insert @llvm.lifetime intrinsics.
   bool InsertLifetime;
 
+  ModuleDecisionTreeProxies *MDTP;
+
   /// shouldInline - Return true if the inliner should attempt to
   /// inline at the given CallSite.
   bool shouldInline(CallSite CS);
 };
 
 } // End llvm namespace
 
 #endif

include/llvm/Transforms/Utils/LoopUtils.h

 class DataLayout;
 class DominatorTree;
 class Loop;
 class LoopInfo;
 class Pass;
 class PredIteratorCache;
 class ScalarEvolution;
 class TargetLibraryInfo;
+class ModuleDecisionTreeProxies;
 
 /// \brief Captures loop safety information.
 /// It keep information for loop & its header may throw exception.
 struct LICMSafetyInfo {
   bool MayThrow;           // The current loop contains an instruction which
                            // may throw.
   bool HeaderMayThrow;     // Same as previous, but specific to loop header
   LICMSafetyInfo() : MayThrow(false), HeaderMayThrow(false)

 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 /// uses before definitions, allowing us to sink a loop body in one pass without
 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 /// instructions of the loop and loop safety information as arguments.
 /// It returns changed status.
 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                LICMSafetyInfo *);
+                LICMSafetyInfo *, ModuleDecisionTreeProxies *MDTP);
 
 /// \brief Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 /// loop and loop safety information as arguments. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                 LICMSafetyInfo *);
+                 LICMSafetyInfo *, ModuleDecisionTreeProxies *);
 
 /// \brief Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are 
 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
 /// AliasSet information for all instructions of the loop and loop safety 
 /// information as arguments. It returns changed status.

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeScalarEvolutionWrapperPassPass(Registry);
   initializeScalarEvolutionAliasAnalysisPass(Registry);
   initializeTargetTransformInfoWrapperPassPass(Registry);
   initializeTypeBasedAliasAnalysisPass(Registry);
   initializeScopedNoAliasAAPass(Registry);
+  initializeModuleDecisionTreeProxiesPass(Registry);
+  initializeICSetCurrentFuncPass(Registry);
 }
 
 void LLVMInitializeAnalysis(LLVMPassRegistryRef R) {
   initializeAnalysis(*unwrap(R));
 }
 
 void LLVMInitializeIPA(LLVMPassRegistryRef R) {
   initializeAnalysis(*unwrap(R));

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   CGSCCPassManager.cpp
   CallGraph.cpp
   CallGraphSCCPass.cpp
   CallPrinter.cpp
   CaptureTracking.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
+  ICUtils.cpp
+  ICFileUtils.cpp
+  ICDecisionTree.cpp
+  ICPass.cpp
+  ICProxies.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DominanceFrontier.cpp
   GlobalsModRef.cpp
+  ICSetCurrentFunc.cpp
   IVUsers.cpp
   InlineCost.cpp
   InstCount.cpp
   InstructionSimplify.cpp
   Interval.cpp
   IntervalPartition.cpp
   IteratedDominanceFrontier.cpp
   LazyCallGraph.cpp

lib/Analysis/ICDecisionTree.cpp

+//===-- DecisionTree.cpp - Implement Decision Tree Classes ----------------===//
+//
+//                     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 decision tree and decision tree proxy classes
+// which are used in iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+/* Here is a brief explanation of the forming of the decision tree.
+
+First, some passes need to be modified to call getDecision function.
+If this function returns false, a pass should do exactly as the code
+without modification. If the return value is true, then the alternative
+path is taken.
+
+Function getDecision always returns false in the first iteration.
+And the compiler should work exactly as if there was no iterative framework.
+
+Let us assume that getDecision function is called four times in the
+first iteration of iterative compilation. After the end of the first
+iteration, the decision tree will look like this:
+
+o
+  \
+    o
+      \
+        o
+          \
+            o
+              \
+                o
+
+In the second iteration, exactly one decision is changed and the compiler
+works as in the first iteration until it reaches this particular decision.
+Then alternative path is taken in this point. Further, getDecision function
+returns false until compilation iteration is finished. Let us assume that we
+took alternative decision at the third decision and that there are three more
+calls of getDecision function. Note that different compilation paths may
+have different number of calls of getDecision function.
+
+o
+  \
+    o
+      \
+        o
+      /   \
+     o      o
+       \      \
+         o      o
+           \
+             o
+
+Every new iteration adds one new branch to the decision tree.
+
+At the end of each iteration fitness of the generated code is evaluated.
+In the last iteration, the compiler takes the path with the best fitness.
+
+To augment the selection of a node where alternative decision would be taken,
+getDecision tree takes one parameter. This parameter is interpreted as
+priority and the node with highest priory is selected for next alternative
+decision.
+*/
+
+#include <algorithm>
+#include <fstream>
+#include <sstream>
+#include <limits.h>
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/ICDecisionTree.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/YAMLParser.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <iostream>
+
+using namespace llvm;
+
+DecisionTreeNode::DecisionTreeNode() {
+  Parent = NULL;
+  PrimaryDecision = NULL;
+  AlternativeDecision = NULL;
+  Priority = 0;
+  Optimization = NoOptimization;
+  Fitness = INT_MAX;
+  Depth = 0;
+  NodeId = 0;
+  IsInterprocedural = false;
+}
+
+DecisionTreeNode::DecisionTreeNode(DecisionTreeNode *parent, int id) {
+  Parent = parent;
+  PrimaryDecision = NULL;
+  AlternativeDecision = NULL;
+  Priority = 0;
+  Optimization = NoOptimization;
+  Fitness = INT_MAX;
+  Depth = parent->Depth+1;
+  NodeId = id;
+  IsInterprocedural = false;
+}
+
+DecisionTree::DecisionTree() {
+  DecisionTreeRoot = new DecisionTreeNode;
+  NodeIdCount = 1;
+  FunctionFitness = 0;
+  BestFunctionFitness = INT_MAX;
+  CurrentNode = DecisionTreeRoot;
+}
+
+DecisionTree::~DecisionTree() {
+  delete DecisionTreeRoot;
+}
+
+/// This is the function which controls iterative compilation process.
+bool DecisionTree::getDecision(int priority, ICOptimization opt) {
+  unsigned depth = CurrentNode->Depth;
+  bool decision;
+
+  // If depth is less then the size of the given path, follow this path.
+  if (depth < Path.size()) {
+    decision = Path[depth];
+    if (decision) {
+      if (CurrentNode->AlternativeDecision) {
+        CurrentNode = CurrentNode->AlternativeDecision;
+        return decision;
+      }
+    } else {
+      if (CurrentNode->PrimaryDecision) {
+        CurrentNode = CurrentNode->PrimaryDecision;
+        return decision;
+      }
+    }
+  }
+
+  // Update current node
+  if(opt != NoOptimization) {
+    CurrentNode->Priority = priority;
+    CurrentNode->Optimization = opt;
+  }
+
+  // Create the new decision tree node
+  DecisionTreeNode *newNode = new DecisionTreeNode(CurrentNode, NodeIdCount++);
+
+  // Insert the new node in the decision tree.
+  if (CurrentNode->PrimaryDecision == 0) {
+    CurrentNode->PrimaryDecision = newNode;
+    decision = false;
+  } else {
+    CurrentNode->AlternativeDecision = newNode;
+    decision = true;
+  }
+  CurrentNode = newNode;
+
+  return decision;
+}
+
+/// Updated best function fitness seen so far.
+void DecisionTree::updateBestFunctionFitness(int iteration) {
+  if (FunctionFitness < BestFunctionFitness) {
+    BestFunctionFitness = FunctionFitness;
+    findPath(CurrentNode, BestPath);
+  }
+  updateNodesFitness();
+}
+
+/// Find path which leads to the given node.
+void DecisionTree::findPath(DecisionTreeNode *node, BitVector &path) {
+  path.resize(node->Depth);
+  if (node->PrimaryDecision)
+    path.resize(node->Depth + 1, true);
+  while (node != DecisionTreeRoot) {
+    DecisionTreeNode *parent = node->Parent;
+    if (node == parent->AlternativeDecision)
+      path[parent->Depth] = true;
+    else
+      path[parent->Depth] = false;
+    node = parent;
+  }
+}
+
+/// Select path for the new iteration. In the final iteration use
+/// the best path so far.
+bool DecisionTree::selectPath(bool FinalPass) {
+  if (FinalPass) {
+    Path = BestPath;
+    return true;
+  }
+  DecisionTreeNode *selectedNode = selectNode();
+
+  if (selectedNode) {
+    findPath(selectedNode, Path);
+    return false;
+  } else {
+    Path = BestPath;
+    return true;
+  }
+}
+
+DecisionTreeNode* DecisionTree::selectNode()
+{
+  SmallVector<DecisionTreeNode *, 64> nodesToExplore;
+  int selectedNodePriority = 0;
+  DecisionTreeNode *selectedNode = 0;
+
+  // if tree is empty, select root node
+  if (!DecisionTreeRoot->AlternativeDecision
+        && !DecisionTreeRoot->PrimaryDecision)
+    selectedNode = DecisionTreeRoot;
+
+  // start exploring from root node
+  nodesToExplore.push_back(DecisionTreeRoot);
+  while(!nodesToExplore.empty()) {
+    // get node
+    DecisionTreeNode *n = nodesToExplore.back();
+    nodesToExplore.pop_back();
+    // if we have only primary decision
+    if (n->AlternativeDecision == 0 && n->PrimaryDecision != 0) {
+      double priority = n->calcFinalPriority (BestFunctionFitness);
+      // and final priority is greater than currently selected node
+      // select this node
+      if (priority > selectedNodePriority) {
+        selectedNode = n;
+        selectedNodePriority = priority;
+      }
+    }
+    // if we have alternative decision
+    if (n->AlternativeDecision)
+      nodesToExplore.push_back(n->AlternativeDecision);
+    // if we have primary decision
+    if (n->PrimaryDecision)
+      nodesToExplore.push_back(n->PrimaryDecision);
+  }
+
+  return selectedNode;
+}
+
+/// Prepare decision tree for the new iteration.
+void DecisionTree::startNewIteration() {
+  CurrentNode = DecisionTreeRoot;
+  FunctionFitness = 0;
+}
+
+/// Update fitness field of the nodes on the current path.
+void DecisionTree::updateNodesFitness() {
+  DecisionTreeNode *n = CurrentNode;
+  while(n) {
+    if (n->Fitness > FunctionFitness)
+      n->Fitness = FunctionFitness;
+    n = n->Parent;
+  }
+}
+
+/// Calculate modified priority so that the nodes on the paths which
+/// generate better code are more often selected.
+int DecisionTreeNode::calcFinalPriority(int bestFunctionFitness) {
+  if (Fitness == 0)
+    return Priority;
+  return ((long)Priority * bestFunctionFitness) / Fitness;
+}
+
+/// Apply results from the decision tree proxy so that the
+/// path for the next iteration can be selected.
+void DecisionTree::applyResults(const MdtResults &results) {
+  unsigned pathLen = Path.size();
+  int nOptimizations = (int)results.Optimizations.size();
+  unsigned nPriorities = results.Priorities.size();
+
+  // TODO add some comments
+  // recreate tree structure
+  for (unsigned i = 0; i < pathLen; i++) {
+    getDecision(0, NoOptimization);
+  }
+
+  // actually apply results
+  for (unsigned i = 0; i < nPriorities; i++) {
+    getDecision(results.Priorities[i], results.Optimizations[i]);
+  }
+  setFunctionFitness(results.Fitness);
+}
+
+void DecisionTree::splitPath(
+    const BitVector &path,
+    BitVector &pathBeforeCodegen,
+    BitVector &pathAfterCodegen) {
+
+  pathBeforeCodegen.clear();
+  pathAfterCodegen.clear();
+
+  CurrentNode = DecisionTreeRoot;
+  unsigned pathLen = path.size();
+
+  for (unsigned i = 0; i < pathLen; i++) {
+    assert(CurrentNode);
+
+    unsigned depth = CurrentNode->Depth;
+    bool decision = path[depth];
+    assert(depth < path.size());
+
+    if (CurrentNode->Optimization <= LicmOpt)
+      pathBeforeCodegen.resize(pathBeforeCodegen.size() + 1, decision);
+    else
+      pathAfterCodegen.resize(pathAfterCodegen.size() + 1, decision);
+
+    if (decision)
+      CurrentNode = CurrentNode->AlternativeDecision;
+    else
+      CurrentNode = CurrentNode->PrimaryDecision;
+  }
+
+  CurrentNode = DecisionTreeRoot;
+}
+
+void DecisionTree::dumpToGv(int currentIteration) {
+  DecisionTreeNode *n;
+  SmallVector<DecisionTreeNode*, 64> paths;
+
+  std::stringstream path;
+  path << "/tmp/ic-tree-" << currentIteration << ".gv";
+
+  std::ofstream f(path.str());
+
+  f << "digraph G {\n";
+
+  paths.push_back(DecisionTreeRoot);
+  while(!paths.empty())
+  {
+    n = paths.back();
+    paths.pop_back();
+
+
+    while(n->PrimaryDecision) {
+      f << "n" << n->NodeId << " -> " << "n"
+        << n->PrimaryDecision->NodeId << ";\n";
+
+      if(n->AlternativeDecision)
+      {
+        paths.push_back(n->AlternativeDecision);
+        f << "n" << n->NodeId << " -> " << "n" << n->AlternativeDecision->NodeId
+          << "[weight=0];\n";
+      }
+      n = n->PrimaryDecision;
+    }
+  }
+
+  f << "}";
+  f.close();
+}
+std::string DecisionTreeNode::getJSON() {
+  std::stringstream res;
+
+  res << "{";
+  res << " \"id\" : " << NodeId   << ",";
+  res << " \"priority\" : " << Priority << ",";
+  res << " \"fitness\" : " << Fitness  << ",";
+  res << " \"depth\" : " << Depth    << ",";
+  res << " \"optim\" : " << Optimization;
+  res << "}";
+
+  return res.str();
+}
+
+void DecisionTree::dumpToJSON(int currentIteration) {
+  DecisionTreeNode *n;
+  SmallVector<DecisionTreeNode*, 64> paths;
+
+  std::stringstream filePath;
+  filePath << "/tmp/ic-tree-" << currentIteration << ".json";
+
+  std::ofstream f(filePath.str());
+
+  f << "[\n";
+
+  paths.push_back(DecisionTreeRoot);
+  while(!paths.empty())
+  {
+    n = paths.back();
+
+    if(n->Parent)
+      f << "\n\t{\n\t\"root\" : " << n->Parent->getJSON() << ",";
+    else
+      f << "\n\t{\n\t\"root\" : " << n->getJSON() << ",";
+
+    f << "\n\t\"path\" : [\n";
+
+    paths.pop_back();
+
+    while(n->PrimaryDecision || n->AlternativeDecision) {
+      if(n->AlternativeDecision) {
+        // save new path entry point for later
+        paths.push_back(n->AlternativeDecision);
+      }
+
+      if(n->PrimaryDecision) {
+        // we have regular primary decision,
+        // write it and continue
+        // get node as JSON and append it to current path
+        f << "\t\t" << n->getJSON();
+        n = n->PrimaryDecision;
+      }
+
+      if(n->PrimaryDecision)
+        f << ",\n";
+      else
+        f << "\n";
+
+    }
+
+    if(!paths.empty())
+      f << "\t]},\n";
+    else
+      f << "\t]}\n";
+  }
+
+  f << "]";
+  f.close();
+}
+void DecisionTree::addPrimaryDecision() {
+  DecisionTreeNode *newNode = new DecisionTreeNode;
+  addPrimaryDecision(newNode);
+}
+
+void DecisionTree::addPrimaryDecision(DecisionTreeNode *node)
+{
+  this->CurrentNode->PrimaryDecision = node;
+  node->Parent = this->CurrentNode;
+  node->Depth = this->CurrentNode->Depth + 1;
+  this->CurrentNode = node;
+}
+
+void DecisionTree::addAlternativeDecision() {
+  DecisionTreeNode *newNode = new DecisionTreeNode;
+  addAlternativeDecision(newNode);
+}
+
+void DecisionTree::addAlternativeDecision(DecisionTreeNode *node)
+{
+  this->CurrentNode->AlternativeDecision = node;
+  node->Parent = this->CurrentNode;
+  node->Depth = this->CurrentNode->Depth + 1;
+  this->CurrentNode = node;
+}
+
+DecisionTreeNode* DecisionTree::getRootNode() {
+  return this->DecisionTreeRoot;
+}

lib/Analysis/ICFileUtils.cpp

+#include "llvm/Analysis/ICFileUtils.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/ErrorOr.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include <sstream>
+
+using namespace llvm;
+
+ICFile::ICFile(std::string filePrefix, int iteration) {
+  filename = createTmpFile(filePrefix, iteration).c_str();
+}
+
+bool ICFile::exists() {
+  return llvm::sys::fs::exists(filename);
+}
+
+void ICFile::remove() {
+  llvm::sys::fs::remove(filename);
+}
+
+void ICInputFile::write() {
+  std::string pathsString;
+  pathsString = generateMdtPathsString(paths);
+
+  writeToFile(filename, pathsString);
+}
+
+bool ICInputFile::read() {
+  int res = 0;
+
+  if(exists()) {
+    std::string err;
+    std::string pathsString = readFromFile(filename);
+    res = parseMdtPaths(paths, pathsString, err);
+  }
+
+  return res;
+}
+
+void ICResultsFile::write() {
+  std::string resultsString = MdtResults::generateMdtResultsString(results);
+  writeToFile(filename, resultsString);
+}
+
+bool ICResultsFile::read() {
+  int parsed = 0;
+
+  std::string err;
+  if(exists()) {
+    std::string resultsString = readFromFile(filename);
+    parsed = MdtResults::parseMdtResults(results, resultsString, err);
+  }
+
+  if(!parsed)
+    llvm::errs() << "ITERATIVE COMPILATION ERROR:" << err << "\n";
+
+  return !parsed;
+}
+
+SmallString<128> ICFile::createTmpFile(std::string filename,
+    int CurrentIteration) {
+  std::string ErrMsg;
+  SmallString<128> Path;
+  std::stringstream fullFilename;
+
+  fullFilename << filename << "-" << CurrentIteration;
+
+  if(llvm::sys::fs::createTemporaryFile(fullFilename.str(), ".json", Path)) {
+    llvm::errs() << "Error creating temporary file: " << ErrMsg << "\n";
+  }
+
+  return Path;
+}
+
+/// Write contents of the string to the file.
+void ICFile::writeToFile(const std::string &fileName, const std::string &data) {
+  std::error_code EC;
+  raw_fd_ostream outf(fileName, EC, sys::fs::F_Text);
+  if (EC) {
+    report_fatal_error(Twine("can't open file: ") + fileName
+                       + " (" + EC.message() + ")");
+  }
+  outf << data;
+  outf.close();
+}
+
+/// Read contents of the file.
+std::string ICFile::readFromFile(const std::string &fileName) {
+  llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Buffer =
+      llvm::MemoryBuffer::getFile(fileName);
+
+  // std::cout << "here: " << fileName << std::endl;
+  if (std::error_code Result = Buffer.getError()) {
+    report_fatal_error(Twine("Error while opening file: ")
+      + Result.message());
+  }
+  return (*Buffer)->getBuffer();
+}

lib/Analysis/ICPass.cpp

+#include <algorithm>
+#include <fstream>
+#include <sstream>
+#include <limits.h>
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/ICPass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/YAMLParser.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <iostream>
+
+using namespace llvm;
+
+INITIALIZE_PASS(ModuleDecisionTreeProxies, "module-decision-tree-proxies",
+                "Module Decision Tree Proxies", false, false)
+char ModuleDecisionTreeProxies::ID = 0;
+
+ModuleDecisionTreeProxies::ModuleDecisionTreeProxies()
+: ImmutablePass(ID), IterativeCompilation(false),
+  CurrFnDecisionTreeProxy(0) {
+  initializeModuleDecisionTreeProxiesPass(*PassRegistry::getPassRegistry());
+}
+
+ModuleDecisionTreeProxies::~ModuleDecisionTreeProxies() {
+  for (auto &P : DecisionTreeProxies) {
+    DecisionTreeProxy *dtp = P.second;
+    delete dtp;
+  }
+}
+
+/// Sets decision tree proxy for current function and compilation phase.
+void ModuleDecisionTreeProxies::setCurrentFunctionAndPhase(
+    const std::string &fnName,
+    FnNameAndPhase::ICPhase phase) {
+  ICPhase = phase;
+  if (!IterativeCompilation) {
+    CurrFnDecisionTreeProxy = 0;
+    return;
+  }
+  std::string id;
+  switch(phase) {
+    case FnNameAndPhase::FunctionPhase:
+      id = fnName + ".0";
+      break;
+    case FnNameAndPhase::ModulePhase:
+      id = "module-id";
+      break;
+    case FnNameAndPhase::CodeGenPhase:
+      id = fnName + ".2";
+      break;
+    default:
+      assert(0 && "bad iterative compilation phase");
+  }
+  CurrFnDecisionTreeProxy = &getDecisionTreeProxy(fnName, phase);
+}
+
+/// Sets current compilation phase to module phase.
+void ModuleDecisionTreeProxies::setModuleCompilationPhase() {
+  setCurrentFunctionAndPhase("module-id", FnNameAndPhase::ModulePhase);
+}
+
+/// Find decision tree proxy for specified function and compilation phase.
+DecisionTreeProxy &ModuleDecisionTreeProxies::getDecisionTreeProxy(
+    const FnNameAndPhase &x) {
+  if (DecisionTreeProxies.find(x) == DecisionTreeProxies.end())
+    DecisionTreeProxies[x] = new DecisionTreeProxy();
+
+  return *DecisionTreeProxies[x];
+}
+
+/// Find decision tree proxy for specified function and compilation phase.
+DecisionTreeProxy &ModuleDecisionTreeProxies::getDecisionTreeProxy(
+    const std::string &name,
+    FnNameAndPhase::ICPhase phase) {
+  return getDecisionTreeProxy(FnNameAndPhase(name, phase));
+}
+
+/// Set paths for all decision tree proxies.
+void ModuleDecisionTreeProxies::setPaths(ICPathsMap &paths) {
+  for (const auto &P : paths) {
+    const FnNameAndPhase &fnNameAndPhase = P.first;
+    const BitVector &path = P.second;
+    DecisionTreeProxy &dtp = getDecisionTreeProxy(fnNameAndPhase);
+    dtp.setPath(path);
+  }
+}
+
+/// Get results of this compiler iteration. Result include
+/// measured function fitnesses and decision priorities.
+void ModuleDecisionTreeProxies::getResults(
+    std::vector<MdtResults> &results) const {
+  results.clear();
+  for (const auto &P : DecisionTreeProxies) {
+    const FnNameAndPhase &fnNameAndPhase = P.first;
+    const DecisionTreeProxy &dtp = *P.second;
+    MdtResults res = dtp.getResults();
+    res.FunctionNameAndPhase = fnNameAndPhase;
+    results.push_back(res);
+  }
+}
+
+bool ModuleDecisionTreeProxies::doInitialization(Module &M) {
+  if (IterativeCompilationOpt) {
+    IterativeCompilation = true;
+    std::string MdtPathsString;
+
+    llvm::ICInputFile input1(FicInputFile);
+    llvm::ICInputFile input2(FicInputFile2);
+    ICPathsMap MdtPaths;
+    int parsed;
+
+    if (input1.exists()) {
+      parsed = input1.read();
+      input1.remove();
+      MdtPaths = input1.getPaths();
+    }
+    else if (input2.exists()) {
+      parsed = input2.read();
+      input2.remove();
+      MdtPaths = input2.getPaths();
+    }
+    else {
+      report_fatal_error(Twine("ITERATIVE COMPILATION ERROR:"
+                               "unable to read input file\n"));
+    }
+
+    if (!parsed) {
+      std::string ErrorMsg;
+      report_fatal_error(Twine("ITERATIVE COMPILATION ERROR:") + ErrorMsg + "\n");
+      return false;
+    }
+
+    setPaths(MdtPaths);
+  }
+  return true;
+}
+
+bool ModuleDecisionTreeProxies::doFinalization(Module &M) {
+  if (IterativeCompilationOpt) {
+    std::vector<MdtResults> Results;
+    ICResultsFile *resultsFile;
+    getResults(Results);
+
+    if (ICPhase != FnNameAndPhase::CodeGenPhase) {
+      resultsFile = new ICResultsFile(FicResultsFile);
+    }
+    else {
+      resultsFile = new ICResultsFile(FicResultsFile2);
+    }
+
+    resultsFile->setResults(Results);
+    resultsFile->write();
+  }
+  return true;
+}
+
+/// This function should be called from pass that wants to take advantage
+/// of iterative compilation. If this function returns false, a pass
+/// should do exactly as before, without iterative compilation,
+/// otherwise take an alternative path. Parameter priority is the
+/// estimated priority of this decision. We should pass higher priority
+/// for the decisions which can more influence the code quality and for
+/// which the existing heuristics are not sure that the right decision
+/// is taken.
+bool ModuleDecisionTreeProxies::getDecision(int priority, ICOptimization opt) {
+  if (!CurrFnDecisionTreeProxy)
+    return false;
+  bool r2 = CurrFnDecisionTreeProxy->getDecision(priority, opt);
+  return r2;
+}

lib/Analysis/ICProxies.cpp

+#include "llvm/Analysis/ICProxies.h"
+#include "llvm/Analysis/ICUtils.h"
+
+using namespace llvm;
+
+DecisionTreeProxy::DecisionTreeProxy()
+  : FunctionFitness(0), BestFunctionFitness(INT_MAX), CurrentDepth(0) {}
+
+/// This function is called by ModuleDecisionTreeProxies::getDecision
+/// to obtain decision at some compilation point.
+bool DecisionTreeProxy::getDecision(int priority, ICOptimization opt) {
+  if (CurrentDepth < (int)Path.size()) {
+    bool r = Path[CurrentDepth];
+    CurrentDepth++;
+    return r;
+  }
+  Priorities.push_back(priority);
+  Optimizations.push_back(opt);
+  CurrentDepth++;
+  return false;
+}
+
+MdtResults DecisionTreeProxy::getResults() const {
+  MdtResults results;
+  results.Priorities = Priorities;
+  results.Optimizations = Optimizations;
+  results.Fitness = FunctionFitness;
+  return results;
+}
+
+void DecisionTreeProxy::setPath(const BitVector &path) {
+  Path = path;
+}
+
+ModuleDecisionTrees::ModuleDecisionTrees() {}
+
+ModuleDecisionTrees::~ModuleDecisionTrees() {
+  for (auto &P : DecisionTrees) {
+    DecisionTree *dt = P.second;
+    delete dt;
+  }
+}
+
+/// Find required decision tree.
+DecisionTree &ModuleDecisionTrees::getDecisionTree(
+    const FnNameAndPhase &fnNameAndPhase) {
+  if (DecisionTrees.find(fnNameAndPhase) == DecisionTrees.end()) {
+    DecisionTrees[fnNameAndPhase] = new DecisionTree();
+  }
+  return *DecisionTrees[fnNameAndPhase];
+}
+
+/// Inform all decision trees that new iteration of compilation
+/// has been started.
+void ModuleDecisionTrees::startNewIteration() {
+  for (auto &P : DecisionTrees) {
+    DecisionTree *dt = P.second;
+    dt->startNewIteration();
+  }
+}
+
+/// Get selected paths for decision trees.
+void ModuleDecisionTrees::getPaths(ICPathsMap &paths) {
+  paths.clear();
+  for (const auto &P : DecisionTrees) {
+    const FnNameAndPhase &fnNameAndPhase = P.first;
+    const DecisionTree *dt = P.second;
+    const BitVector &path = dt->getPath();
+    paths[fnNameAndPhase] = path;
+  }
+}
+
+/// Apply results to all decision trees used for a module optimization.
+void ModuleDecisionTrees::applyResults(const std::vector<MdtResults> &results) {
+  for (const auto &R : results) {
+    DecisionTree &DT = getDecisionTree(R.FunctionNameAndPhase);
+    DT.applyResults(R);
+  }
+}
+
+/// Updates best function fitness filed for all decision trees.
+void ModuleDecisionTrees::updateBestFunctionFitness(int Iteration) {
+  for (const auto &P : DecisionTrees) {
+    DecisionTree *DT = P.second;
+    DT->updateBestFunctionFitness(Iteration);
+  }
+}
+
+/// Iterates through all decision trees and calls updateNodesFitness
+/// on them.
+void ModuleDecisionTrees::updateNodesFitness() {
+  for (const auto &P : DecisionTrees) {
+    DecisionTree *DT = P.second;
+    DT->updateNodesFitness();
+  }
+}
+
+/// Selects path for all decision trees.
+void ModuleDecisionTrees::selectPath(bool FinalPass) {
+  for (const auto &P : DecisionTrees) {
+    DecisionTree *DT = P.second;
+    DT->selectPath(FinalPass);
+  }
+}
+
+void ModuleDecisionTrees::splitPaths(
+    const ICPathsMap &paths,
+    ICPathsMap &pathsBeforeCodegen,
+    ICPathsMap &pathsAfterCodegen) {
+  for (auto const &it : paths) {
+    const FnNameAndPhase &fnNameAndPhase = it.first;
+    const BitVector &path = it.second;
+    BitVector path1;
+    BitVector path2;
+    DecisionTree *DT = DecisionTrees[fnNameAndPhase];
+
+    DT->splitPath(path, path1, path2);
+
+    pathsBeforeCodegen[fnNameAndPhase] = path1;
+    pathsAfterCodegen[fnNameAndPhase] = path2;
+  }
+}

lib/Analysis/ICSetCurrentFunc.cpp

+//===-- ICSetCurrentFunc.cpp - Iterative Comp Set Current Func DT ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implements the pass which sets the decision tree proxy of the
+// current function.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ICSetCurrentFunc.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/IR/Function.h"
+
+using namespace llvm;
+
+bool ICSetCurrentFunc::runOnFunction(Function &F) {
+  MD = &getAnalysis<ModuleDecisionTreeProxies>();
+  //MD->setFunctionName(F.getName());
+
+  // TODO: Use module phase decision tree until iterative compilation
+  //       framework can handle multiple decision trees.
+
+  //MD->setCurrentFunctionAndPhase(F.getName(),
+  //                               FnNameAndPhase::FunctionPhase);
+  MD->setModuleCompilationPhase();
+  return false;
+}
+
+char ICSetCurrentFunc::ID = 0;
+
+INITIALIZE_PASS_BEGIN(ICSetCurrentFunc, "icsetcurrentfunc",
+                "Set Current Function DT Proxy", false, true)
+INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies)
+INITIALIZE_PASS_END(ICSetCurrentFunc, "icsetcurrentfunc",
+                "Set Current Function DT Proxy", false, true)
+
+FunctionPass *llvm::createICSetCurrentFuncPass() {
+  return new ICSetCurrentFunc();
+}

lib/Analysis/ICUtils.cpp

+#include "llvm/Analysis/ICUtils.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/ErrorOr.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/YAMLParser.h"
+#include <sstream>
+
+using namespace llvm;
+
+cl::opt<bool>
+llvm::IterativeCompilationOpt("fiterative-comp", cl::init(false),
+                     cl::desc("Enable iterative compilation"));
+cl::opt<std::string>
+llvm::FicInputFile("fic-input-file", cl::init("ic-input"));
+
+cl::opt<std::string>
+llvm::FicInputFile2("fic-input2-file", cl::init("ic-input2"));
+
+cl::opt<std::string>
+llvm::FicResultsFile("fic-results-file", cl::init("ic-results"));
+
+cl::opt<std::string>
+llvm::FicResultsFile2("fic-results2-file", cl::init("ic-results2"));
+
+std::string llvm::BitVector2Str(const BitVector &path) {
+  std::stringstream s;
+
+  s << "\"";
+
+  for(unsigned i = 0; i < path.size(); i++)
+    s << path[i];
+
+  s << "\"";
+
+  return s.str();
+}
+
+std::string llvm::Path2Str(const FnNameAndPhase &nameAndPhase,
+                           const BitVector &path) {
+  std::stringstream s;
+  s << "  {\n";
+  s << "    \"Fn\":\"" << nameAndPhase.getName() << "\",\n";
+  s << "    \"Phase\":" << (int)nameAndPhase.getPhase() << ",\n";
+  s << "    \"Path\":" << BitVector2Str(path) << "\n";
+  s << "  }";
+
+  return s.str();
+}
+
+// Parses string containing paths for multiple decision trees in JSON
+/// format using llmv YAML parser.
+bool llvm::parseMdtPaths(ICPathsMap &paths,
+                                        const std::string &pathString,
+                                        std::string &ErrorMessage) {
+  paths.clear();
+  SourceMgr SM;
+  yaml::Stream YAMLStream(pathString, SM);
+  llvm::yaml::document_iterator I = YAMLStream.begin();
+
+  // sanity checks
+  if (I == YAMLStream.end()) {
+    ErrorMessage = "Error while parsing YAML.";
+    return false;
+  }
+
+  llvm::yaml::Node *Root = I->getRoot();
+  if (!Root) {
+    ErrorMessage = "Error while parsing YAML.";
+    return false;
+  }
+
+  llvm::yaml::SequenceNode *Array = dyn_cast<llvm::yaml::SequenceNode>(Root);
+  if (!Array) {
+    ErrorMessage = "Expected array.";
+    return false;
+  }
+
+  // parse every node
+  for (llvm::yaml::SequenceNode::iterator AI = Array->begin(),
+                                          AE = Array->end();
+       AI != AE; ++AI) {
+    llvm::yaml::MappingNode *Object = dyn_cast<llvm::yaml::MappingNode>(&*AI);
+
+    // another sanity check
+    if (!Object) {
+      ErrorMessage = "Expected object.";
+      return false;
+    }
+
+    llvm::yaml::ScalarNode *Fn = nullptr;
+    llvm::yaml::ScalarNode *Phase = nullptr;
+    llvm::yaml::ScalarNode *Path = nullptr;
+    for (llvm::yaml::MappingNode::iterator KVI = Object->begin(),
+                                           KVE = Object->end();
+         KVI != KVE; ++KVI) {
+      llvm::yaml::Node *Value = (*KVI).getValue();
+      if (!Value) {
+        ErrorMessage = "Expected value.";
+        return false;
+      }
+      llvm::yaml::ScalarNode *ValueString =
+          dyn_cast<llvm::yaml::ScalarNode>(Value);
+      if (!ValueString) {
+        ErrorMessage = "Expected string as value.";
+        return false;
+      }
+
+      llvm::yaml::ScalarNode *KeyString =
+          dyn_cast<llvm::yaml::ScalarNode>((*KVI).getKey());
+      if (!KeyString) {
+        ErrorMessage = "Expected strings as key.";
+        return false;
+      }
+
+      SmallString<8> KeyStorage;
+      if (KeyString->getValue(KeyStorage) == "Fn") {
+        Fn = ValueString;
+      } else if (KeyString->getValue(KeyStorage) == "Phase") {
+        Phase = ValueString;
+      } else if (KeyString->getValue(KeyStorage) == "Path") {
+        Path = ValueString;
+      } else {
+        ErrorMessage = ("Unknown key: \"" +
+                        KeyString->getRawValue() + "\"").str();
+        return false;
+      }
+    }
+
+    // error reporting
+    if (!Fn) {
+      ErrorMessage = "Missing key: \"Fn\".";
+      return false;
+    }
+    if (!Phase) {
+      ErrorMessage = "Missing key: \"Phase\".";
+      return false;
+    }
+    if (!Path) {
+      ErrorMessage = "Missing key: \"Path\".";
+      return false;
+    }
+
+    // populating our structure
+    SmallString<8> FnStorage;
+    StringRef FnStr = Fn->getValue(FnStorage);
+    SmallString<8> PhaseStorage;
+    StringRef PhaseStr = Phase->getValue(PhaseStorage);
+    SmallString<8> PathStorage;
+    StringRef PathStr = Path->getValue(PathStorage);
+
+    FnNameAndPhase::ICPhase CompilationPhase =
+      (FnNameAndPhase::ICPhase) (atoi(PhaseStr.str().c_str()));
+
+    unsigned N = PathStr.size();
+    BitVector PathVector(N);
+    unsigned i;
+    for (i = 0; i < N; i++)
+      PathVector[i] = (PathStr[i] == '0' ? false : true);
+
+    FnNameAndPhase fnNameAndPhase(FnStr.str(), CompilationPhase);
+    paths[fnNameAndPhase] = PathVector;
+  }
+  return true;
+}
+
+/// Converts paths for multiple decision trees to string in JSON format.
+std::string llvm::generateMdtPathsString(const ICPathsMap &paths) {
+  std::stringstream s;
+  s << "[\n";
+  unsigned n = paths.size();
+  unsigned i = 0;
+  for (const auto &P : paths) {
+    const FnNameAndPhase &fnNameAndPhase = P.first;
+    const BitVector &path = P.second;
+
+    s << Path2Str(fnNameAndPhase, path);
+
+    if(i + 1 < n)
+      s << ",\n";
+    else
+      s << "\n";
+
+    i++;
+  }
+  s << "]\n";
+  return s.str();
+}
+
+/// Parses string containing results for multiple decision trees
+/// in JSON format to vector of MdtResults structs using LLMV
+/// YAML parser.
+bool MdtResults::parseMdtResults(
+    std::vector<MdtResults> &results,
+    const std::string &resString,
+    std::string &ErrorMessage) {
+  results.clear();
+  SourceMgr SM;
+  yaml::Stream YAMLStream(resString, SM);
+
+  // sanity checks
+  llvm::yaml::document_iterator I = YAMLStream.begin();
+  if (I == YAMLStream.end()) {
+    ErrorMessage = "Error while parsing YAML.";
+    return false;
+  }
+  llvm::yaml::Node *Root = I->getRoot();
+  if (!Root) {
+    ErrorMessage = "Error while parsing YAML.";
+    return false;
+  }
+  llvm::yaml::SequenceNode *Array = dyn_cast<llvm::yaml::SequenceNode>(Root);
+  if (!Array) {
+    ErrorMessage = "Expected array.";
+    return false;
+  }
+
+  // iterating over nodes
+  for (llvm::yaml::SequenceNode::iterator AI = Array->begin(),
+                                          AE = Array->end();
+       AI != AE; ++AI) {
+    llvm::yaml::MappingNode *Object = dyn_cast<llvm::yaml::MappingNode>(&*AI);
+    if (!Object) {
+      ErrorMessage = "Expected object.";
+      return false;
+    }
+
+    // some init
+    llvm::yaml::ScalarNode *Fn = nullptr;
+    llvm::yaml::ScalarNode *Phase = nullptr;
+    llvm::yaml::ScalarNode *Fitness = nullptr;
+    llvm::yaml::SequenceNode *Priorities = nullptr;
+    llvm::yaml::SequenceNode *Optimizations = nullptr;
+    std::vector<int> PrioritiesVector;
+    std::vector<ICOptimization> OptimizationsVector;
+
+    // another iteration
+    for (llvm::yaml::MappingNode::iterator KVI = Object->begin(),
+                                           KVE = Object->end();
+         KVI != KVE; ++KVI) {
+      llvm::yaml::Node *Value = (*KVI).getValue();
+      if (!Value) {
+        ErrorMessage = "Expected value (1).";
+        return false;
+      }
+      llvm::yaml::ScalarNode *KeyString =
+          dyn_cast<llvm::yaml::ScalarNode>((*KVI).getKey());
+      if (!KeyString) {
+        ErrorMessage = "Expected strings as key.";
+        return false;
+      }
+      SmallString<8> KeyStorage;
+      if (KeyString->getValue(KeyStorage) == "Priorities") {
+        Priorities = dyn_cast<llvm::yaml::SequenceNode>(Value);
+        if (!Priorities) {
+          ErrorMessage = "Expected array.";
+          return false;
+        }
+        for (llvm::yaml::SequenceNode::iterator PI = Priorities->begin(),
+                                            PE = Priorities->end();
+            PI != PE; ++PI) {
+          llvm::yaml::ScalarNode *Priority = dyn_cast<llvm::yaml::ScalarNode>(&*PI);
+          if (!Priority) {
+            ErrorMessage = "Expected value (2).";
+            return false;
+          }
+          SmallString<8> PriorityStorage;
+          StringRef PriorityStr = Priority->getValue(PriorityStorage);
+          int PriorityValue = atoi(PriorityStr.str().c_str());
+          PrioritiesVector.push_back(PriorityValue);
+        }
+
+        continue;
+      }
+      if (KeyString->getValue(KeyStorage) == "Optimizations") {
+        Optimizations = dyn_cast<llvm::yaml::SequenceNode>(Value);
+        if (!Optimizations) {
+          ErrorMessage = "Expected array.";
+          return false;
+        }
+        for (llvm::yaml::SequenceNode::iterator PI = Optimizations->begin(),
+                                            PE = Optimizations->end();
+            PI != PE; ++PI) {
+          llvm::yaml::ScalarNode *Optimization = dyn_cast<llvm::yaml::ScalarNode>(&*PI);
+          if (!Optimization) {
+            ErrorMessage = "Expected value (2).";
+            return false;
+          }
+          SmallString<8> OptimizationStorage;
+          StringRef OptimizationStr = Optimization->getValue(OptimizationStorage);
+          int OptimizationValue = atoi(OptimizationStr.str().c_str());
+          OptimizationsVector.push_back((ICOptimization)OptimizationValue);
+        }
+
+        continue;
+      }
+
+      llvm::yaml::ScalarNode *ValueString =
+          dyn_cast<llvm::yaml::ScalarNode>(Value);
+      if (!ValueString) {
+        ErrorMessage = "Expected string as value.";
+        return false;
+      }
+      if (KeyString->getValue(KeyStorage) == "Fn") {
+        Fn = ValueString;
+      } else if (KeyString->getValue(KeyStorage) == "Phase") {
+        Phase = ValueString;
+      } else if (KeyString->getValue(KeyStorage) == "Fitness") {
+        Fitness = ValueString;
+      } else {
+        ErrorMessage = ("Unknown key: \"" +
+                        KeyString->getRawValue() + "\"").str();
+        return false;
+      }
+    }
+
+    // error reporting
+    if (!Fn) {
+      ErrorMessage = "Missing key: \"Fn\".";
+      return false;
+    }
+    if (!Phase) {
+      ErrorMessage = "Missing key: \"Phase\".";
+      return false;
+    }
+    if (!Fitness) {
+      ErrorMessage = "Missing key: \"Fitness\".";
+      return false;
+    }
+    if (!Priorities) {
+      ErrorMessage = "Missing key: \"Priorities\".";
+      return false;
+    }
+    if (!Optimizations) {
+      ErrorMessage = "Missing key: \"Optimizations\".";
+      return false;
+    }
+
+    // populating our storage
+    SmallString<8> FnStorage;
+    StringRef FnStr = Fn->getValue(FnStorage);
+    SmallString<8> PhaseStorage;
+    StringRef PhaseStr = Phase->getValue(PhaseStorage);
+    SmallString<8> FitnessStorage;
+    StringRef FitnessStr = Fitness->getValue(FitnessStorage);
+
+    FnNameAndPhase::ICPhase CompilationPhase =
+      (FnNameAndPhase::ICPhase) (atoi(PhaseStr.str().c_str()));
+
+    MdtResults mdtResults;
+    mdtResults.FunctionNameAndPhase =
+        FnNameAndPhase(FnStr.str(), CompilationPhase);
+    mdtResults.Fitness = atoi(FitnessStr.str().c_str());
+    mdtResults.Priorities = PrioritiesVector;
+    mdtResults.Optimizations = OptimizationsVector;
+    results.push_back(mdtResults);
+  }
+  return true;
+}
+
+/// Converts vector of MdtResults to string in JSON format.
+std::string MdtResults::generateMdtResultsString(
+    const std::vector<MdtResults> &results) {
+  unsigned i;
+  unsigned n = results.size();
+  std::stringstream s;
+
+  s << "[\n";
+  for (i = 0; i < n; i++) {
+    // TODO: convert one MdtResult to string
+    const MdtResults &res = results[i];
+    const FnNameAndPhase &fnNameAndPhase = res.FunctionNameAndPhase;
+    s << "  {\n";
+    s << "    \"Fn\":\"" << fnNameAndPhase.getName() << "\",\n";
+    s << "    \"Phase\":" << (int)fnNameAndPhase.getPhase() << ",\n";
+    s << "    \"Fitness\":" << res.Fitness << ",\n";
+    s << "    \"Priorities\":[";
+    unsigned j;
+    unsigned nPriorities = res.Priorities.size();
+    for (j = 0; j < nPriorities; j++) {
+      s << res.Priorities[j];
+      if (j + 1 < nPriorities)
+        s << ",";
+    }
+    s << "]\n";
+    s << "    \"Optimizations\":[";
+    unsigned nOptimizations = res.Optimizations.size();
+    for (j = 0; j < nOptimizations; j++) {
+      s << (int)res.Optimizations[j];
+      if (j + 1 < nOptimizations)
+        s << ",";
+    }
+    s << "]\n";
+    if (i + 1 < n)
+      s << "  },\n";
+    else
+      s << "  }\n";
+  }
+  s << "]\n";
+  return s.str();
+}
+
+/// Calculates total module fitness as the sum of the finesses of
+/// all functions in the module.
+int MdtResults::calculateTotalFitness(const std::vector<MdtResults> &results) {
+  int tf = 0;
+  for (const auto &res : results) {
+    if (res.FunctionNameAndPhase.getPhase() == FnNameAndPhase::CodeGenPhase)
+      tf += res.Fitness;
+  }
+  return tf;
+}
+
+void MdtResults::mergeMdtResults(
+    std::vector<MdtResults> &mergedResults,
+    const std::vector<MdtResults> &results1,
+    const std::vector<MdtResults> &results2) {
+
+  const MdtResults *moduleResults1 = 0;
+  const MdtResults *moduleResults2 = 0;
+  MdtResults mergedModuleResults;
+
+  moduleResults1 = MdtResults::getByPhase(results1, FnNameAndPhase::ModulePhase);
+  moduleResults2 = MdtResults::getByPhase(results2, FnNameAndPhase::ModulePhase);
+
+  for (const auto &res : results1) {
+    if (res.FunctionNameAndPhase.getPhase() != FnNameAndPhase::ModulePhase)
+      mergedResults.push_back(res);
+  }
+
+  for (const auto &res : results2) {
+    if (res.FunctionNameAndPhase.getPhase() != FnNameAndPhase::ModulePhase)
+      mergedResults.push_back(res);
+  }
+
+  if (moduleResults1 && !moduleResults2)
+      mergedResults.push_back(*moduleResults1);
+
+  if (!moduleResults1 && moduleResults2)
+      mergedResults.push_back(*moduleResults2);
+
+  if (moduleResults1 && moduleResults2) {
+    mergedModuleResults = *moduleResults1;
+
+    mergedModuleResults.Priorities.insert(mergedModuleResults.Priorities.end(),
+      moduleResults2->Priorities.begin(), moduleResults2->Priorities.end());
+
+    mergedModuleResults.Optimizations.insert(mergedModuleResults.Optimizations.end(),
+      moduleResults2->Optimizations.begin(), moduleResults2->Optimizations.end());
+
+    mergedResults.push_back(mergedModuleResults);
+  }
+}
+
+MdtResults* MdtResults::getByPhase(const std::vector<MdtResults> &results,
+    FnNameAndPhase::ICPhase phase) {
+
+  MdtResults *found = NULL;
+  for (const auto &res : results) {
+    if (res.FunctionNameAndPhase.getPhase() == phase)
+    {
+      found = new MdtResults();
+      *found = res;
+      break;
+    }
+  }
+
+  return found;
+}

lib/CodeGen/RegAllocGreedy.cpp

 #include "InterferenceCache.h"
 #include "LiveDebugVariables.h"
 #include "RegAllocBase.h"
 #include "SpillPlacement.h"
 #include "Spiller.h"
 #include "SplitKit.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/IterativeCompilation.h"
 #include "llvm/CodeGen/CalcSpillWeights.h"
 #include "llvm/CodeGen/EdgeBundles.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveRangeEdit.h"
 #include "llvm/CodeGen/LiveRegMatrix.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/RegAllocRegistry.h"
 #include "llvm/CodeGen/RegisterClassInfo.h"
 #include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/PassAnalysisSupport.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
+#include <fstream>
 #include <queue>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "regalloc"
 
 STATISTIC(NumGlobalSplits, "Number of split global live ranges");
 STATISTIC(NumLocalSplits,  "Number of split local live ranges");
class RAGreedy : public MachineFunctionPass,
 
   // context
   MachineFunction *MF;
 
   // Shortcuts to some useful interface.
   const TargetInstrInfo *TII;
   const TargetRegisterInfo *TRI;
   RegisterClassInfo RCI;
+  ModuleDecisionTreeProxies *MDTP;
 
   // analyses
   SlotIndexes *Indexes;
   MachineBlockFrequencyInfo *MBFI;
   MachineDominatorTree *DomTree;
   MachineLoopInfo *Loops;
   EdgeBundles *Bundles;
   SpillPlacement *SpillPlacer;
void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<SlotIndexes>();
   AU.addPreserved<SlotIndexes>();
   AU.addRequired<LiveDebugVariables>();
   AU.addPreserved<LiveDebugVariables>();
   AU.addRequired<LiveStacks>();
   AU.addPreserved<LiveStacks>();
   AU.addRequired<MachineDominatorTree>();
   AU.addPreserved<MachineDominatorTree>();
+
+  if(IterativeCompilationOpt)
+    AU.addRequired<ModuleDecisionTreeProxies>();
+
   AU.addRequired<MachineLoopInfo>();
   AU.addPreserved<MachineLoopInfo>();
   AU.addRequired<VirtRegMap>();
   AU.addPreserved<VirtRegMap>();
   AU.addRequired<LiveRegMatrix>();
   AU.addPreserved<LiveRegMatrix>();
   AU.addRequired<EdgeBundles>();
   AU.addRequired<SpillPlacement>();
unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
                             unsigned CostPerUseLimit) {
   NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
 
   // Keep track of the cheapest interference seen so far.
   EvictionCost BestCost;
   BestCost.setMax();
   unsigned BestPhys = 0;
   unsigned OrderLimit = Order.getOrder().size();
+  SmallVector<unsigned, 8> EvictionCandidates;
 
   // When we are just looking for a reduced cost per use, don't break any
   // hints, and only evict smaller spill weights.
   if (CostPerUseLimit < ~0u) {
     BestCost.BrokenHints = 0;
     BestCost.MaxWeight = VirtReg.weight;
 
     // Check of any registers in RC are below CostPerUseLimit.
while (unsigned PhysReg = Order.next(OrderLimit)) {
     }
 
     if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
       continue;
 
     // Best so far.
     BestPhys = PhysReg;
 
+    EvictionCandidates.push_back(PhysReg);
+
     // Stop if the hint can be used.
     if (Order.isHint())
       break;
   }
 
+  // Try different choices for register to be evicted.
+  if(IterativeCompilationOpt && (EvictionCandidates.size() > 1)) {
+    int priority = 0x10000;
+
+    for (int i = (int)EvictionCandidates.size() - 2; i >= 0; i--) {
+      bool decision = false;
+
+      decision = MDTP->getDecision(priority, llvm::RegAllocOpt);
+
+      if(decision) {
+        BestPhys = EvictionCandidates[i];
+      }
+      priority = priority / 2;
+    }
+  }
+
   if (!BestPhys)
     return 0;
 
   evictInterference(VirtReg, BestPhys, NewVRegs);
   return BestPhys;
 }
 
 
if (VerifyEnabled)
     MF->verify(this, "Before greedy register allocator");
 
   RegAllocBase::init(getAnalysis<VirtRegMap>(),
                      getAnalysis<LiveIntervals>(),
                      getAnalysis<LiveRegMatrix>());
   Indexes = &getAnalysis<SlotIndexes>();
   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
   DomTree = &getAnalysis<MachineDominatorTree>();
+
+  if(IterativeCompilationOpt) {
+    MDTP = &getAnalysis<ModuleDecisionTreeProxies>();
+    MDTP->setModuleCompilationPhase();
+  }
+
   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
   Loops = &getAnalysis<MachineLoopInfo>();
   Bundles = &getAnalysis<EdgeBundles>();
   SpillPlacer = &getAnalysis<SpillPlacement>();
   DebugVars = &getAnalysis<LiveDebugVariables>();
 
   initializeCSRCost();
 

lib/Target/Mips/CMakeLists.txt

add_llvm_target(MipsCodeGen
   Mips16ISelLowering.cpp
   Mips16RegisterInfo.cpp
   MipsAnalyzeImmediate.cpp
   MipsAsmPrinter.cpp
   MipsCCState.cpp
   MipsConstantIslandPass.cpp
   MipsDelaySlotFiller.cpp
   MipsFastISel.cpp
+  MipsFunctionFitness.cpp
   MipsInstrInfo.cpp
   MipsISelDAGToDAG.cpp
   MipsISelLowering.cpp
   MipsFrameLowering.cpp
   MipsLongBranch.cpp
   MipsMCInstLower.cpp
   MipsMachineFunction.cpp
   MipsModuleISelDAGToDAG.cpp

lib/Target/Mips/Mips.h

namespace llvm {
   ModulePass *createMipsOs16Pass(MipsTargetMachine &TM);
   ModulePass *createMips16HardFloatPass(MipsTargetMachine &TM);
 
   FunctionPass *createMipsModuleISelDagPass(MipsTargetMachine &TM);
   FunctionPass *createMipsOptimizePICCallPass(MipsTargetMachine &TM);
   FunctionPass *createMipsDelaySlotFillerPass(MipsTargetMachine &TM);
   FunctionPass *createMipsLongBranchPass(MipsTargetMachine &TM);
   FunctionPass *createMipsConstantIslandPass(MipsTargetMachine &tm);
+  FunctionPass *createMipsFunctionFitnessPass();
 } // end namespace llvm;
 
 #endif

lib/Target/Mips/MipsFunctionFitness.cpp

+//===-- MipsFunctionFitness.cpp - Function Fitness Implementation ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file estimates the fitness of a function which is used in
+// iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Mips.h"
+#include "MipsTargetMachine.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/IterativeCompilation.h"
+#include "llvm/IR/Function.h"
+
+using namespace llvm;
+
+struct FunctionFitness : public MachineFunctionPass {
+
+  static char ID;
+  FunctionFitness() : MachineFunctionPass(ID), TotalCount(0) { }
+
+  virtual const char *getPassName() const {
+    return "Mips Function Fitness";
+  }
+
+  bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
+  bool runOnMachineFunction(MachineFunction &F) {
+    std::string FnName = F.getFunction()->getName().str();
+    ModuleDecisionTreeProxies &Proxies =
+      getAnalysis<ModuleDecisionTreeProxies>();
+    Proxies.setCurrentFunctionAndPhase(FnName, FnNameAndPhase::CodeGenPhase);
+    DecisionTreeProxy *Proxy = Proxies.getCurrFnDecisionTreeProxy();
+    if (Proxy) {
+      TotalCount = 0;
+      for (MachineFunction::iterator FI = F.begin(), FE = F.end();
+           FI != FE; ++FI)
+        runOnMachineBasicBlock(*FI);
+      Proxy->setFunctionFitness(TotalCount);
+    }
+    return false;
+  }
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<ModuleDecisionTreeProxies>();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+  unsigned TotalCount;
+};
+
+char FunctionFitness::ID = 0;
+
+bool FunctionFitness::
+runOnMachineBasicBlock(MachineBasicBlock &MBB) {
+  unsigned Count = 0;
+
+  for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
+    Count++;
+
+  TotalCount += Count;
+
+  return false;
+}
+
+/// createMipsFunctionFitnessPass - Returns a pass that counts generated
+/// instructions
+/// in
+FunctionPass *llvm::createMipsFunctionFitnessPass() {
+  return new FunctionFitness();
+}

lib/Target/Mips/MipsTargetMachine.cpp

 #include "MipsTargetObjectFile.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Analysis/IterativeCompilation.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "mips"
 
 extern "C" void LLVMInitializeMipsTarget() {
   // Register the target.
   RegisterTargetMachine<MipsebTargetMachine> X(TheMipsTarget);

 }
 
 // Implemented by targets that want to run passes immediately before
 // machine code is emitted. return true if -print-machineinstrs should
 // print out the code after the passes.
 void MipsPassConfig::addPreEmitPass() {
   MipsTargetMachine &TM = getMipsTargetMachine();
   addPass(createMipsDelaySlotFillerPass(TM));
+
+  if(IterativeCompilationOpt)
+    addPass(createMipsFunctionFitnessPass());
+
   addPass(createMipsLongBranchPass(TM));
   addPass(createMipsConstantIslandPass(TM));
 }

lib/Transforms/IPO/InlineAlways.cpp

 
 char AlwaysInliner::ID = 0;
 INITIALIZE_PASS_BEGIN(AlwaysInliner, "always-inline",
                 "Inliner for always_inline functions", false, false)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(InlineCostAnalysis)
+INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies)
 INITIALIZE_PASS_END(AlwaysInliner, "always-inline",
                 "Inliner for always_inline functions", false, false)
 
 Pass *llvm::createAlwaysInlinerPass() { return new AlwaysInliner(); }
 
 Pass *llvm::createAlwaysInlinerPass(bool InsertLifetime) {
   return new AlwaysInliner(InsertLifetime);
 }

lib/Transforms/IPO/InlineSimple.cpp

 
 char SimpleInliner::ID = 0;
 INITIALIZE_PASS_BEGIN(SimpleInliner, "inline",
                 "Function Integration/Inlining", false, false)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(InlineCostAnalysis)
+INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies)
 INITIALIZE_PASS_END(SimpleInliner, "inline",
                 "Function Integration/Inlining", false, false)
 
 Pass *llvm::createFunctionInliningPass() { return new SimpleInliner(); }
 
 Pass *llvm::createFunctionInliningPass(int Threshold) {
   return new SimpleInliner(Threshold);
 }

lib/Transforms/IPO/Inliner.cpp

 #include "llvm/Transforms/IPO/InlinerPass.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/IterativeCompilation.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
+#include <fstream>
 using namespace llvm;
 
 #define DEBUG_TYPE "inline"
 
 STATISTIC(NumInlined, "Number of functions inlined");
 STATISTIC(NumCallsDeleted, "Number of call sites deleted, not inlined");
 STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
 STATISTIC(NumMergedAllocas, "Number of allocas merged together");

 // BFI.
 static cl::opt<int>
 ColdThreshold("inlinecold-threshold", cl::Hidden, cl::init(225),
               cl::desc("Threshold for inlining functions with cold attribute"));
 
 // Threshold to use when optsize is specified (and there is no -inline-limit).
 const int OptSizeThreshold = 75;
 
-Inliner::Inliner(char &ID) 
+Inliner::Inliner(char &ID)
   : CallGraphSCCPass(ID), InlineThreshold(InlineLimit), InsertLifetime(true) {}
 
 Inliner::Inliner(char &ID, int Threshold, bool InsertLifetime)
   : CallGraphSCCPass(ID), InlineThreshold(InlineLimit.getNumOccurrences() > 0 ?
                                           InlineLimit : Threshold),
     InsertLifetime(InsertLifetime) {}
 
 /// For this class, we declare that we require and preserve the call graph.
 /// If the derived class implements this method, it should
 /// always explicitly call the implementation here.
 void Inliner::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<AliasAnalysis>();
   AU.addRequired<AssumptionCacheTracker>();
+  AU.addRequired<ModuleDecisionTreeProxies>();
   CallGraphSCCPass::getAnalysisUsage(AU);
 }
 
 
 typedef DenseMap<ArrayType*, std::vector<AllocaInst*> >
 InlinedArrayAllocasTy;
 
 /// \brief If the inlined function had a higher stack protection level than the
if (IC.isNever()) {
     DEBUG(dbgs() << "    NOT Inlining: cost=never"
           << ", Call: " << *CS.getInstruction() << "\n");
     emitAnalysis(CS, Twine(CS.getCalledFunction()->getName() +
                            " should never be inlined (cost=never)"));
     return false;
   }
   
   Function *Caller = CS.getCaller();
-  if (!IC) {
+  bool doInlinging = (bool)IC;
+
+  int ip = IC.getCostDelta();
+  if (ip < 0)
+    ip = -ip;
+  int t = MaxDtPriority - ip;
+  bool decision = false;
+
+  if (t >= 0) {
+    decision = MDTP->getDecision(t, InlinerOpt);
+  }
+
+  if (decision)
+    doInlinging = !doInlinging;
+
+  if (!doInlinging) {
     DEBUG(dbgs() << "    NOT Inlining: cost=" << IC.getCost()
           << ", thres=" << (IC.getCostDelta() + IC.getCost())
           << ", Call: " << *CS.getInstruction() << "\n");
     emitAnalysis(CS, Twine(CS.getCalledFunction()->getName() +
                            " too costly to inline (cost=") +
                          Twine(IC.getCost()) + ", threshold=" +
                          Twine(IC.getCostDelta() + IC.getCost()) + ")");
     return false;
while (InlineHistoryID != -1) {
     InlineHistoryID = InlineHistory[InlineHistoryID].second;
   }
   return false;
 }
 
 bool Inliner::runOnSCC(CallGraphSCC &SCC) {
   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
   AssumptionCacheTracker *ACT = &getAnalysis<AssumptionCacheTracker>();
+  MDTP = &getAnalysis<ModuleDecisionTreeProxies>();
+  MDTP->setModuleCompilationPhase();
   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
   const TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
   AliasAnalysis *AA = &getAnalysis<AliasAnalysis>();
 
   SmallPtrSet<Function*, 8> SCCFunctions;
   DEBUG(dbgs() << "Inliner visiting SCC:");
   for (CallGraphNode *Node : SCC) {
     Function *F = Node->getFunction();

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(
   MPM.add(createCorrelatedValuePropagationPass()); // Propagate conditionals
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   MPM.add(createInstructionCombiningPass());  // Combine silly seq's
   addExtensionsToPM(EP_Peephole, MPM);
 
   MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   MPM.add(createReassociatePass());           // Reassociate expressions
+  MPM.add(createICSetCurrentFuncPass());      // Set decision tree proxy
   // Rotate Loop - disable header duplication at -Oz
   MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
   MPM.add(createLICMPass());                  // Hoist loop invariants
   MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));
   MPM.add(createInstructionCombiningPass());
   MPM.add(createIndVarSimplifyPass());        // Canonicalize indvars
   MPM.add(createLoopIdiomPass());             // Recognize idioms like memset.
   MPM.add(createLoopDeletionPass());          // Delete dead loops

lib/Transforms/Scalar/LICM.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/IterativeCompilation.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PredIteratorCache.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include <algorithm>
+#include <fstream>
+
 using namespace llvm;
 
 #define DEBUG_TYPE "licm"
 
 STATISTIC(NumSunk      , "Number of instructions sunk out of loop");
 STATISTIC(NumHoisted   , "Number of instructions hoisted out of loop");
 STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
 STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
struct LICM : public LoopPass {
     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 
     /// This transformation requires natural loop information & requires that
     /// loop preheaders be inserted into the CFG...
     ///
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       AU.addRequired<DominatorTreeWrapperPass>();
+      AU.addRequired<ModuleDecisionTreeProxies>();
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addRequiredID(LoopSimplifyID);
       AU.addPreservedID(LoopSimplifyID);
       AU.addRequiredID(LCSSAID);
       AU.addPreservedID(LCSSAID);
       AU.addRequired<AliasAnalysis>();
       AU.addPreserved<AliasAnalysis>();
       AU.addPreserved<ScalarEvolutionWrapperPass>();
       AU.addRequired<TargetLibraryInfoWrapperPass>();
     }
 
     using llvm::Pass::doFinalization;
 
     bool doFinalization() override {
       assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets");
       return false;
     }
 
   private:
     AliasAnalysis *AA;       // Current AliasAnalysis information
     LoopInfo      *LI;       // Current LoopInfo
     DominatorTree *DT;       // Dominator Tree for the current Loop.
 
     TargetLibraryInfo *TLI;  // TargetLibraryInfo for constant folding.
+    ModuleDecisionTreeProxies *MDTP;
 
     // State that is updated as we process loops.
     bool Changed;            // Set to true when we change anything.
     BasicBlock *Preheader;   // The preheader block of the current loop...
     Loop *CurLoop;           // The current loop we are working on...
     AliasSetTracker *CurAST; // AliasSet information for the current loop...
     DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap;
 
     /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info.
     void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
                                  Loop *L) override;
 
     /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias
     /// set.
     void deleteAnalysisValue(Value *V, Loop *L) override;
 
     /// Simple Analysis hook. Delete loop L from alias set map.
     void deleteAnalysisLoop(Loop *L) override;
   };
 }
 
 char LICM::ID = 0;
 INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 INITIALIZE_PASS_DEPENDENCY(LCSSA)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false)
 
 Pass *llvm::createLICMPass() { return new LICM(); }
 
 /// Hoist expressions out of the specified loop. Note, alias info for inner
 /// loop is not preserved so it is not a good idea to run LICM multiple
 /// times on one loop.
 ///
 bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
   if (skipOptnoneFunction(L))
     return false;
 
   Changed = false;
 
   // Get our Loop and Alias Analysis information...
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   AA = &getAnalysis<AliasAnalysis>();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  MDTP = &getAnalysis<ModuleDecisionTreeProxies>();
 
   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
+  int n = 0;
+
   CurAST = new AliasSetTracker(*AA);
   // Collect Alias info from subloops.
   for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end();
        LoopItr != LoopItrE; ++LoopItr) {
     Loop *InnerL = *LoopItr;
     AliasSetTracker *InnerAST = LoopToAliasSetMap[InnerL];
     assert(InnerAST && "Where is my AST?");
 
bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
 
   // Get the preheader block to move instructions into...
   Preheader = L->getLoopPreheader();
 
   // Loop over the body of this loop, looking for calls, invokes, and stores.
   // Because subloops have already been incorporated into AST, we skip blocks in
   // subloops.
   //
+  n = 0;
   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
        I != E; ++I) {
     BasicBlock *BB = *I;
     if (LI->getLoopFor(BB) == L)        // Ignore blocks in subloops.
       CurAST->add(*BB);                 // Incorporate the specified basic block
   }
 
   // Compute loop safety information.
   LICMSafetyInfo SafetyInfo;
   computeLICMSafetyInfo(&SafetyInfo, CurLoop);
 
   // We want to visit all of the instructions in this loop... that are not parts
   // of our subloops (they have already had their invariants hoisted out of
   // their loop, into this loop, so there is no need to process the BODIES of
   // the subloops).
   //
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
   // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
   //
   if (L->hasDedicatedExits())
     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop,
-                          CurAST, &SafetyInfo);
+                          CurAST, &SafetyInfo, MDTP);
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI,
-                           CurLoop, CurAST, &SafetyInfo);
+                           CurLoop, CurAST, &SafetyInfo, MDTP);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
   if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
     SmallVector<BasicBlock *, 8> ExitBlocks;
     SmallVector<Instruction *, 8> InsertPts;
     PredIteratorCache PIC;
 

 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in reverse depth 
 /// first order w.r.t the DominatorTree.  This allows us to visit uses before
 /// definitions, allowing us to sink a loop body in one pass without iteration.
 ///
 bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                       DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
-                      AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
+                      AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo,
+                      ModuleDecisionTreeProxies *MDTP) {
 
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && 
          DT != nullptr && CurLoop != nullptr && CurAST != nullptr && 
          SafetyInfo != nullptr && "Unexpected input to sinkRegion");
 
   // Set changed as false.
   bool Changed = false;
   // Get basic block
   BasicBlock *BB = N->getBlock();
   // If this subregion is not in the top level loop at all, exit.
   if (!CurLoop->contains(BB)) return Changed;
 
   // We are processing blocks in reverse dfo, so process children first.
   const std::vector<DomTreeNode*> &Children = N->getChildren();
   for (unsigned i = 0, e = Children.size(); i != e; ++i)
     Changed |=
-        sinkRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
+        sinkRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo,
+                   MDTP);
   // Only need to process the contents of this block if it is not part of a
   // subloop (which would already have been processed).
   if (inSubLoop(BB,CurLoop,LI)) return Changed;
 
   for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) {
     Instruction &I = *--II;
 
     // If the instruction is dead, we would try to sink it because it isn't used

 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 ///
 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                        DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
-                       AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
+                       AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo,
+                       ModuleDecisionTreeProxies *MDTP) {
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && 
          DT != nullptr && CurLoop != nullptr && CurAST != nullptr && 
          SafetyInfo != nullptr && "Unexpected input to hoistRegion");
   // Set changed as false.
   bool Changed = false;
   // Get basic block
   BasicBlock *BB = N->getBlock();
   // If this subregion is not in the top level loop at all, exit.
   if (!CurLoop->contains(BB)) return Changed;
   // Only need to process the contents of this block if it is not part of a
   // subloop (which would already have been processed).
   if (!inSubLoop(BB, CurLoop, LI))
+  {
     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) {
       Instruction &I = *II++;
       // Try constant folding this instruction.  If all the operands are
       // constants, it is technically hoistable, but it would be better to just
       // fold it.
       if (Constant *C = ConstantFoldInstruction(
               &I, I.getModule()->getDataLayout(), TLI)) {
+
+        if (MDTP->getDecision(MaxDtPriority / 2, LicmOpt))
+        {
+          continue;
+        }
+
         DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C << '\n');
         CurAST->copyValue(&I, C);
         CurAST->deleteValue(&I);
         I.replaceAllUsesWith(C);
         I.eraseFromParent();
         continue;
       }
 
       // Try hoisting the instruction out to the preheader.  We can only do this
       // if all of the operands of the instruction are loop invariant and if it
       // is safe to hoist the instruction.
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
           isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo,
                                  CurLoop->getLoopPreheader()->getTerminator()))
+      {
+        if (!(MDTP->getDecision(MaxDtPriority / 2, LicmOpt))) {
           Changed |= hoist(I, CurLoop->getLoopPreheader());
         }
+      }
+    }
+  }
 
   const std::vector<DomTreeNode*> &Children = N->getChildren();
   for (unsigned i = 0, e = Children.size(); i != e; ++i)
     Changed |=
-        hoistRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
+        hoistRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo,
+                    MDTP);
   return Changed;
 }
 
 /// Computes loop safety information, checks loop body & header
 /// for the possibility of may throw exception.
 ///
 void llvm::computeLICMSafetyInfo(LICMSafetyInfo * SafetyInfo, Loop * CurLoop) {
   assert(CurLoop != nullptr && "CurLoop cant be null");

unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   )
 
 add_llvm_unittest(AnalysisTests
   AliasAnalysisTest.cpp
   CallGraphTest.cpp
   CFGTest.cpp
   LazyCallGraphTest.cpp
   ScalarEvolutionTest.cpp
   MixedTBAATest.cpp
   ValueTrackingTest.cpp
+  ICProxies.cpp
+  ICDecisionTree.cpp
+  ICUtils.cpp
   )

unittests/Analysis/ICDecisionTree.cpp

+#include "gtest/gtest.h"
+#include "llvm/Analysis/ICDecisionTree.h"
+
+namespace llvm {
+
+
+namespace {
+// -------------- FIXTURES -----------------//
+DecisionTreeNode *prepareNode(int priority, int id)
+{
+  DecisionTreeNode *node = new DecisionTreeNode;
+  node->Fitness = 0;
+  node->Priority = priority;
+  node->NodeId = id;
+  return node;
+}
+
+DecisionTree *getDTOnlyPrimary()
+{
+  DecisionTree *dt = new DecisionTree;
+  DecisionTreeNode *newNode;
+
+  newNode = prepareNode(100, 1);
+  dt->addPrimaryDecision(newNode);
+
+  newNode = prepareNode(200, 2);
+  dt->addPrimaryDecision(newNode);
+
+  newNode = prepareNode(300, 3);
+  dt->addPrimaryDecision(newNode);
+
+  return dt;
+}
+
+DecisionTree *getDTPrimaryAndAlternative()
+{
+  DecisionTree *dt = new DecisionTree;
+  DecisionTreeNode *newNode;
+
+  newNode = prepareNode(100, 1);
+  dt->addPrimaryDecision(newNode);
+
+  newNode = prepareNode(200, 2);
+  dt->addPrimaryDecision(newNode);
+
+  newNode = prepareNode(300, 3);
+  dt->addAlternativeDecision(newNode);
+
+  newNode = prepareNode(400, 4);
+  dt->addPrimaryDecision(newNode);
+
+  newNode = prepareNode(500, 5);
+  dt->addPrimaryDecision(newNode);
+
+  return dt;
+}
+
+DecisionTree *getDTOnlyAlternative()
+{
+  DecisionTree *dt = new DecisionTree;
+  DecisionTreeNode *newNode;
+
+  newNode = prepareNode(100, 1);
+  dt->addAlternativeDecision(newNode);
+
+  newNode = prepareNode(200, 2);
+  dt->addAlternativeDecision(newNode);
+
+  newNode = prepareNode(300, 3);
+  dt->addAlternativeDecision(newNode);
+
+  newNode = prepareNode(400, 4);
+  dt->addAlternativeDecision(newNode);
+
+  newNode = prepareNode(500, 5);
+  dt->addAlternativeDecision(newNode);
+
+  return dt;
+}
+
+// ------------- TESTS -------------------//
+TEST(ICDecisionTreeNode, decisionTreeNodeInit)
+{
+  DecisionTreeNode node;
+  ASSERT_TRUE(node.Parent == NULL);
+  ASSERT_TRUE(node.PrimaryDecision == NULL);
+  ASSERT_TRUE(node.AlternativeDecision == NULL);
+}
+
+
+TEST(ICDecisionTree, dummyPopulateTree)
+{
+  DecisionTree dt;
+  llvm::DecisionTreeNode *node = dt.getRootNode();
+
+  EXPECT_FALSE(node == NULL);
+  EXPECT_TRUE(node->PrimaryDecision == NULL);
+  EXPECT_TRUE(node->AlternativeDecision == NULL);
+
+  dt.addPrimaryDecision();
+  ASSERT_FALSE(node->PrimaryDecision == NULL);
+  node = node->PrimaryDecision;
+
+  EXPECT_TRUE(node->AlternativeDecision == NULL);
+  dt.addAlternativeDecision();
+  ASSERT_TRUE(node->AlternativeDecision != NULL);
+}
+
+TEST(ICDecisionTree, splitPathOnlyPrimary)
+{
+  DecisionTree dt;
+  DecisionTreeNode *node;
+
+  node = new DecisionTreeNode;
+  node->Optimization = LicmOpt;
+  dt.addPrimaryDecision(node);
+
+  node = new DecisionTreeNode;
+  node->Optimization = InlinerOpt;
+  dt.addPrimaryDecision(node);
+
+  node = new DecisionTreeNode;
+  node->Optimization = RegAllocOpt;
+  dt.addPrimaryDecision(node);
+
+  BitVector completePath(4, 0);
+
+  BitVector pathBeforeCodegen, pathAfterCodegen;
+
+  dt.splitPath(completePath, pathBeforeCodegen, pathAfterCodegen);
+
+  ASSERT_EQ(pathBeforeCodegen.size(), 3);
+  ASSERT_EQ(pathAfterCodegen.size(), 1);
+}
+
+TEST(ICDecisionTree, getDecisionFirstIteration)
+{
+  DecisionTree dt;
+
+  // check if we got the root node
+  DecisionTreeNode *currentNode = dt.getRootNode();
+  ASSERT_EQ(currentNode->NodeId, 0);
+  ASSERT_EQ(0, currentNode->Priority);
+
+  // add a decision and check if root is updated correctly
+  dt.getDecision(500, LicmOpt);
+  ASSERT_EQ(500, currentNode->Priority);
+  ASSERT_TRUE(currentNode->PrimaryDecision != NULL);
+  ASSERT_TRUE(currentNode->AlternativeDecision == NULL);
+
+  // move one child lower and check it
+  // current node id should be 1
+  currentNode = currentNode->PrimaryDecision;
+  ASSERT_EQ(0, currentNode->Priority);
+  ASSERT_EQ(currentNode->NodeId, 1);
+  ASSERT_TRUE(currentNode->Parent != NULL);
+  ASSERT_EQ(currentNode->Parent->NodeId, 0);
+
+  // add new decision and see if the parent is updated
+  dt.getDecision(600, LicmOpt);
+  ASSERT_EQ(600, currentNode->Priority);
+  ASSERT_TRUE(currentNode->PrimaryDecision != NULL);
+  ASSERT_TRUE(currentNode->AlternativeDecision == NULL);
+
+  // check if new node is sane
+  currentNode = currentNode->PrimaryDecision;
+  ASSERT_EQ(2, currentNode->NodeId);
+  ASSERT_EQ(0, currentNode->Priority);
+  ASSERT_TRUE(currentNode->Parent != NULL);
+  ASSERT_EQ(1, currentNode->Parent->NodeId);
+}
+
+TEST(ICDecisionTree, getDecisionOnPrimaryPath)
+{
+  // build the tree
+  DecisionTree dt;
+  ASSERT_FALSE(dt.getDecision(500, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(500, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(600, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(700, LicmOpt));
+
+  // build and check the path
+  dt.selectPath(false);
+  BitVector path = dt.getPath();
+
+  BitVector correctPath(4, 0);
+  correctPath.set(3);
+  ASSERT_EQ(correctPath, path);
+
+  // start new iteration
+  // try to get new decision and check the path now
+  dt.startNewIteration();
+  ASSERT_FALSE(dt.getDecision(100, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(110, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(120, LicmOpt));
+  // this spawns alternative path
+  ASSERT_TRUE(dt.getDecision(130, LicmOpt));
+
+  // check if only parent of new node is updated
+  ASSERT_EQ(500, dt.getRootNode()->Priority);
+  ASSERT_EQ(3, dt.getCurrentNode()->Parent->NodeId);
+  ASSERT_EQ(130, dt.getCurrentNode()->Parent->Priority);
+}
+
+TEST(ICDecisionTree, getDecisionOnAlternativePath)
+{
+  // build the tree
+  DecisionTree dt;
+  ASSERT_FALSE(dt.getDecision(500, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(500, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(600, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(700, LicmOpt));
+
+  // build and check the path
+  dt.selectPath(false);
+  BitVector path = dt.getPath();
+
+  BitVector correctPath(4, 0);
+  correctPath.set(3);
+  ASSERT_EQ(correctPath, path);
+
+  // start new iteration
+  // try to get new decision and check the path now
+  dt.startNewIteration();
+  ASSERT_FALSE(dt.getDecision(600, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(500, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(600, LicmOpt));
+
+  // ok, we are on alternative path now
+  ASSERT_TRUE(dt.getDecision(700, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(800, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(900, LicmOpt));
+
+  // check if we are on the right track
+  DecisionTreeNode *selectedNode = dt.selectNode();
+  ASSERT_EQ(6, selectedNode->NodeId);
+
+  // everything fine, select this path
+  dt.selectPath(false);
+  dt.startNewIteration();
+  ASSERT_EQ(0, dt.getCurrentNode()->NodeId);
+
+  // still on old path
+  ASSERT_FALSE(dt.getDecision(600, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(500, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(600, LicmOpt));
+
+  // ok, we are on alternative path now
+  ASSERT_TRUE(dt.getDecision(700, LicmOpt));
+  ASSERT_FALSE(dt.getDecision(800, LicmOpt));
+
+  // this should put us on alternative path
+  ASSERT_TRUE(dt.getDecision(1000, LicmOpt));
+  ASSERT_EQ(1000, dt.getCurrentNode()->Parent->Priority);
+
+  ASSERT_FALSE(dt.getDecision(1100, LicmOpt));
+}
+
+TEST(ICDecisionTree, selectPathEmptyTree)
+{
+  DecisionTree dt;
+  DecisionTreeNode *root = dt.getRootNode();
+
+  ASSERT_TRUE(root->PrimaryDecision == NULL);
+  ASSERT_TRUE(root->AlternativeDecision == NULL);
+
+  bool result = dt.selectPath(false);
+  BitVector path = dt.getPath();
+
+  ASSERT_EQ(result, false);
+  ASSERT_EQ(BitVector(0), path);
+}
+
+TEST(ICDecisionTreeNode, calcFinalPriorityWithoutFitness)
+{
+  DecisionTreeNode node;
+  node.Fitness = 0;
+  node.Priority = 100;
+
+  int bestFunctionFitness = 1000;
+
+  double finalPriority = node.calcFinalPriority(bestFunctionFitness);
+
+  ASSERT_EQ(finalPriority, node.Priority);
+}
+
+TEST(ICDecisionTreeNode, calcFinalPriorityWithFitness)
+{
+  DecisionTreeNode node;
+  node.Fitness = INT_MAX;
+  node.Priority = 15;
+
+  int bestFunctionFitness = INT_MAX;
+
+  double finalPriority = node.calcFinalPriority(bestFunctionFitness);
+
+  ASSERT_EQ(15, finalPriority);
+}
+
+TEST(ICDecisionTreeNode, DecisionTreeNodeConstructor)
+{
+  DecisionTreeNode node;
+
+  ASSERT_EQ(node.Depth, 0);
+  ASSERT_TRUE(node.Parent == NULL);
+  ASSERT_TRUE(node.PrimaryDecision == NULL);
+  ASSERT_TRUE(node.AlternativeDecision == NULL);
+  ASSERT_EQ(node.Priority, 0);
+  ASSERT_EQ(node.Fitness, INT_MAX);
+}
+
+TEST(ICDecisionTree, DecisionTreeConstructor)
+{
+  DecisionTree dt;
+  DecisionTreeNode *root = dt.getRootNode();
+
+  ASSERT_EQ(root->Depth, 0);
+}
+
+TEST(ICDecisionTree, findPathToRoot)
+{
+  DecisionTree dt;
+  BitVector path;
+  DecisionTreeNode *node = dt.getRootNode();
+
+  dt.findPath(node, path);
+
+  ASSERT_EQ(BitVector(0), path);
+}
+
+TEST(ICDecisionTree, findPathOnlyPrimary)
+{
+  DecisionTree dt;
+  dt.getDecision(500, NoOptimization);
+  dt.getDecision(500, NoOptimization);
+  dt.getDecision(500, NoOptimization);
+
+  DecisionTreeNode *node = dt.getRootNode();
+  node = node->PrimaryDecision->PrimaryDecision->PrimaryDecision;
+
+  BitVector path;
+  dt.findPath(node, path);
+
+  ASSERT_EQ(BitVector(3, 0), path);
+}
+
+TEST(ICDecisionTree, findPathOnlyAlternative)
+{
+  DecisionTree *dt = getDTOnlyAlternative();
+  DecisionTreeNode *node = dt->getRootNode();
+
+  while(node->AlternativeDecision)
+    node = node->AlternativeDecision;
+
+  BitVector path;
+  dt->findPath(node, path);
+
+  ASSERT_EQ(BitVector(5, 1), path);
+}
+
+TEST(ICDecisionTree, findPathPrimaryAndAlternative)
+{
+  DecisionTree *dt = getDTPrimaryAndAlternative();
+  DecisionTreeNode *node = dt->selectNode();
+
+  BitVector path;
+  dt->findPath(node, path);
+
+  BitVector result(5, 0);
+  result.set(2);
+  result.set(4);
+
+  ASSERT_EQ(result, path);
+}
+
+TEST(ICDecisionTree, selectNodeEmptyTree)
+{
+  DecisionTree dt;
+  DecisionTreeNode *node = dt.selectNode();
+  ASSERT_EQ(0, node->NodeId);
+}
+
+
+TEST(ICDecisionTree, selectNodeOnlyPrimary)
+{
+  DecisionTree *dt = getDTOnlyPrimary();
+  DecisionTreeNode *selectedNode = dt->selectNode();
+  ASSERT_EQ(200, selectedNode->Priority);
+}
+
+TEST(ICDecisionTree, selectNodePrimaryAndAlternative)
+{
+  DecisionTree *dt = getDTPrimaryAndAlternative();
+  DecisionTreeNode *selectedNode = dt->selectNode();
+  ASSERT_EQ(400, selectedNode->Priority);
+}
+
+TEST(ICDecisionTree, selectNodeOnlyAlternative)
+{
+  DecisionTree *dt = getDTOnlyAlternative();
+  DecisionTreeNode *selectedNode = dt->selectNode();
+  ASSERT_TRUE(selectedNode == NULL);
+}
+
+TEST(ICDecisionTree, applyResultsToEmptyTree) {
+  DecisionTree dt;
+  MdtResults moduleResults;
+
+  moduleResults.FunctionNameAndPhase =
+    FnNameAndPhase("module-id", FnNameAndPhase::ModulePhase);
+
+  moduleResults.Priorities.push_back(100);
+  moduleResults.Priorities.push_back(200);
+  moduleResults.Priorities.push_back(300);
+  moduleResults.Priorities.push_back(400);
+  moduleResults.Priorities.push_back(500);
+
+  moduleResults.Optimizations.push_back(LicmOpt);
+  moduleResults.Optimizations.push_back(LicmOpt);
+  moduleResults.Optimizations.push_back(LicmOpt);
+  moduleResults.Optimizations.push_back(InlinerOpt);
+  moduleResults.Optimizations.push_back(InlinerOpt);
+
+  dt.applyResults(moduleResults);
+
+  DecisionTreeNode *node = dt.getRootNode();
+  ASSERT_TRUE(node != NULL);
+
+  int i = 1;
+  while(node != NULL && i < 6) {
+    EXPECT_EQ(100*i, node->Priority);
+
+    if(i < 4)
+      EXPECT_EQ(LicmOpt, node->Optimization);
+    else
+      EXPECT_EQ(InlinerOpt, node->Optimization);
+
+    node = node->PrimaryDecision;
+    i++;
+  }
+}
+
+TEST(ICDecisionTree, applyResultsToNonemptyTree) {
+  DecisionTree dt;
+  MdtResults moduleResults;
+
+  moduleResults.FunctionNameAndPhase =
+    FnNameAndPhase("module-id", FnNameAndPhase::ModulePhase);
+
+  moduleResults.Priorities.push_back(100);
+  moduleResults.Priorities.push_back(500);
+  moduleResults.Priorities.push_back(400);
+
+  moduleResults.Optimizations.push_back(LicmOpt);
+  moduleResults.Optimizations.push_back(LicmOpt);
+  moduleResults.Optimizations.push_back(InlinerOpt);
+
+  dt.applyResults(moduleResults);
+  dt.selectPath(0);
+
+  moduleResults.Priorities.clear();
+  moduleResults.Priorities.push_back(600);
+  moduleResults.Priorities.push_back(300);
+
+  moduleResults.Optimizations.clear();
+  moduleResults.Optimizations.push_back(LicmOpt);
+  moduleResults.Optimizations.push_back(InlinerOpt);
+
+  dt.startNewIteration();
+  dt.applyResults(moduleResults);
+  BitVector p = dt.getPath();
+
+  DecisionTreeNode *node = dt.getRootNode();
+  ASSERT_EQ(100, node->Priority);
+
+  node = node->PrimaryDecision;
+  ASSERT_EQ(500, node->Priority);
+  ASSERT_EQ(400, node->PrimaryDecision->Priority);
+
+  node = node->AlternativeDecision;
+  ASSERT_TRUE(node != NULL);
+  ASSERT_EQ(600, node->Priority);
+  ASSERT_EQ(300, node->PrimaryDecision->Priority);
+}
+
+}
+}
+

unittests/Analysis/ICProxies.cpp

+#include "gtest/gtest.h"
+#include "llvm/Analysis/ICProxies.h"
+#include <string>
+#include <sstream>
+#include <map>
+#include "llvm/ADT/BitVector.h"
+#include <iostream>
+
+namespace llvm {
+namespace {
+
+void addNode(DecisionTree &dt, int priority) {
+  static int nodeIdCtr = 1;
+  DecisionTreeNode *newNode;
+
+  newNode = new DecisionTreeNode;
+  newNode->NodeId = nodeIdCtr++;
+  newNode->Fitness = 0;
+  newNode->Priority = priority;
+  dt.addPrimaryDecision(newNode);
+}
+
+TEST(ICProxies, ModuleDecisionTreesEmpty)
+{
+  ModuleDecisionTrees MDT;
+
+  std::map<llvm::FnNameAndPhase, llvm::BitVector> paths;
+  MDT.getPaths(paths);
+
+  std::string result = generateMdtPathsString(paths);
+
+  ASSERT_STREQ("[\n]\n", result.c_str());
+}
+
+TEST(ICProxies, ModuleDecisionTreesOnePhase)
+{
+  std::string moduleId = "module-id";
+  std::string result;
+
+  ModuleDecisionTrees MDT;
+  FnNameAndPhase nameAndPhase(moduleId, FnNameAndPhase::ModulePhase);
+  std::map<llvm::FnNameAndPhase, llvm::BitVector> paths;
+
+  MDT.getPaths(paths);
+  result = generateMdtPathsString(paths);
+
+  DecisionTree &dt = MDT.getDecisionTree(nameAndPhase);
+
+  addNode(dt, 300);
+  addNode(dt, 300);
+  addNode(dt, 300);
+  addNode(dt, 300);
+  addNode(dt, 450);
+  addNode(dt, 500);
+
+  dt.selectPath(false);
+  MDT.getPaths(paths);
+  result = generateMdtPathsString(paths);
+
+  std::stringstream s;
+  s << "[\n";
+  s << "  {\n";
+  s << "    \"Fn\":\"module-id\",\n";
+  s << "    \"Phase\":1,\n";
+  s << "    \"Path\":\"000001\"\n";
+  s << "  }\n";
+  s << "]\n";
+
+  ASSERT_STREQ(s.str().c_str(), result.c_str());
+}
+
+TEST(ICProxies, ModuleDecisionTreesGetDecision) {
+  DecisionTreeProxy mdt;
+
+  BitVector path(4,0);
+  path.set(2);
+
+  mdt.getPath() = path;
+
+  ASSERT_FALSE(mdt.getDecision(100, LicmOpt));
+  ASSERT_FALSE(mdt.getDecision(200, LicmOpt));
+  ASSERT_TRUE(mdt.getDecision(300, LicmOpt));
+  ASSERT_FALSE(mdt.getDecision(400, InlinerOpt));
+
+  ASSERT_EQ(0, mdt.getPriorities().size());
+  ASSERT_EQ(0, mdt.getOptimizations().size());
+
+  ASSERT_FALSE(mdt.getDecision(500, LicmOpt));
+
+  ASSERT_EQ(1, mdt.getPriorities().size());
+  ASSERT_EQ(1, mdt.getOptimizations().size());
+
+  ASSERT_EQ(500, mdt.getPriorities()[0]);
+  ASSERT_EQ(LicmOpt, mdt.getOptimizations()[0]);
+}
+
+}
+}

unittests/Analysis/ICUtils.cpp

+#include "gtest/gtest.h"
+#include "llvm/Analysis/ICProxies.h"
+#include "llvm/ADT/BitVector.h"
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <map>
+
+namespace llvm {
+namespace {
+
+// fixtures
+MdtResults* createModuleResults(std::string moduleName, int prio) {
+  MdtResults *moduleResults = new MdtResults;
+
+  moduleResults->FunctionNameAndPhase =
+    FnNameAndPhase(moduleName, FnNameAndPhase::ModulePhase);
+
+  moduleResults->Optimizations.push_back(InlinerOpt);
+  moduleResults->Optimizations.push_back(InlinerOpt);
+  moduleResults->Optimizations.push_back(InlinerOpt);
+
+  moduleResults->Priorities.push_back(100+prio);
+  moduleResults->Priorities.push_back(200+prio);
+  moduleResults->Priorities.push_back(300+prio);
+
+  return moduleResults;
+}
+
+MdtResults* createFnResults(std::string fnName, int prio) {
+  MdtResults *fnResults = new MdtResults;
+
+  fnResults->FunctionNameAndPhase =
+    FnNameAndPhase(fnName, FnNameAndPhase::FunctionPhase);
+
+  fnResults->Optimizations.push_back(LicmOpt);
+  fnResults->Optimizations.push_back(LicmOpt);
+  fnResults->Optimizations.push_back(LicmOpt);
+
+  fnResults->Priorities.push_back(100+prio);
+  fnResults->Priorities.push_back(200+prio);
+  fnResults->Priorities.push_back(300+prio);
+
+  return fnResults;
+}
+
+// Parsers and generators
+TEST(ICUtils, PathToString)
+{
+  std::string moduleNameId = "module-id";
+  FnNameAndPhase nameAndPhase = FnNameAndPhase(moduleNameId,
+                                  FnNameAndPhase::ModulePhase);
+
+  BitVector path(4, false);
+  path.resize(path.size()+1, true);
+
+  std::string result = Path2Str(nameAndPhase, path);
+
+  std::stringstream target;
+  target << "  {\n";
+  target << "    \"Fn\":\"module-id\",\n";
+  target << "    \"Phase\":1,\n";
+  target << "    \"Path\":\"00001\"\n";
+  target << "  }";
+
+  ASSERT_STREQ(target.str().c_str(), result.c_str());
+}
+
+// IC Utils logic
+TEST(ICUtils, FnNameAndPhaseCompare) {
+  FnNameAndPhase modulePhase("module-id", FnNameAndPhase::ModulePhase);
+  FnNameAndPhase fnPhase("fun1", FnNameAndPhase::FunctionPhase);
+  FnNameAndPhase fnPhase2("fun2", FnNameAndPhase::FunctionPhase);
+  FnNameAndPhase codegenPhase("codegen", FnNameAndPhase::CodeGenPhase);
+
+  ASSERT_TRUE(fnPhase < modulePhase);
+  ASSERT_TRUE(fnPhase < codegenPhase);
+  ASSERT_TRUE(modulePhase < codegenPhase);
+
+  ASSERT_TRUE(fnPhase < fnPhase2);
+}
+
+TEST(ICUtils, MdtResultsMergeMdtResultsOnlyFirstResult) {
+  std::vector<MdtResults> mergedResults;
+  std::vector<MdtResults> precodegenResults;
+  std::vector<MdtResults> codegenResults;
+
+  MdtResults *moduleResults = createModuleResults("module-id", 0);
+  precodegenResults.push_back(*moduleResults);
+
+  MdtResults::mergeMdtResults(mergedResults, precodegenResults, codegenResults);
+  MdtResults *target;
+  target = MdtResults::getByPhase(mergedResults, FnNameAndPhase::ModulePhase);
+  ASSERT_TRUE(target != NULL);
+}
+
+TEST(ICUtils, MdtResultsMergeMdtResultsOnlySecondResult) {
+  std::vector<MdtResults> mergedResults;
+  std::vector<MdtResults> precodegenResults;
+  std::vector<MdtResults> codegenResults;
+
+  MdtResults *moduleResults = createModuleResults("module-id", 0);
+  codegenResults.push_back(*moduleResults);
+
+  MdtResults::mergeMdtResults(mergedResults, precodegenResults, codegenResults);
+  MdtResults *target;
+  target = MdtResults::getByPhase(mergedResults, FnNameAndPhase::ModulePhase);
+  ASSERT_TRUE(target != NULL);
+}
+
+TEST(ICUtils, MdtResultsMergeMdtResultsBoth) {
+  std::vector<MdtResults> mergedResults;
+  std::vector<MdtResults> precodegenResults;
+  std::vector<MdtResults> codegenResults;
+
+  MdtResults *moduleResults1 = createModuleResults("module-id", 0);
+  MdtResults *moduleResults2 = createModuleResults("module-id", 10);
+
+  precodegenResults.push_back(*moduleResults1);
+  codegenResults.push_back(*moduleResults2);
+
+  MdtResults::mergeMdtResults(mergedResults, precodegenResults, codegenResults);
+  MdtResults *target;
+  target = MdtResults::getByPhase(mergedResults, FnNameAndPhase::ModulePhase);
+
+  ASSERT_TRUE(target != NULL);
+  ASSERT_EQ(6, target->Priorities.size());
+  ASSERT_EQ(100, target->Priorities[0]);
+  ASSERT_EQ(200, target->Priorities[1]);
+  ASSERT_EQ(300, target->Priorities[2]);
+  ASSERT_EQ(110, target->Priorities[3]);
+  ASSERT_EQ(210, target->Priorities[4]);
+  ASSERT_EQ(310, target->Priorities[5]);
+}
+
+TEST(ICUtils, MdtResultsGetByPhase) {
+  std::vector<MdtResults> results;
+
+  MdtResults *moduleResults = createModuleResults("module-id", 0);
+  MdtResults *fnResults = createFnResults("fn1", 10);
+
+  MdtResults *target;
+
+  target = MdtResults::getByPhase(results, FnNameAndPhase::ModulePhase);
+  ASSERT_EQ(NULL, target);
+
+  results.push_back(*moduleResults);
+  target = MdtResults::getByPhase(results, FnNameAndPhase::ModulePhase);
+  ASSERT_TRUE(target != NULL);
+  ASSERT_STREQ("module-id", target->FunctionNameAndPhase.getName().c_str());
+
+  target = MdtResults::getByPhase(results, FnNameAndPhase::FunctionPhase);
+  ASSERT_EQ(NULL, target);
+
+  results.push_back(*fnResults);
+  target = MdtResults::getByPhase(results, FnNameAndPhase::FunctionPhase);
+  ASSERT_TRUE(target != NULL);
+  ASSERT_STREQ("fn1", target->FunctionNameAndPhase.getName().c_str());
+}
+
+}
+}