Index: include/llvm/Analysis/ICDecisionTree.h
===================================================================
--- /dev/null
+++ include/llvm/Analysis/ICDecisionTree.h
@@ -0,0 +1,100 @@
+//===-- 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
Index: include/llvm/Analysis/ICFileUtils.h
===================================================================
--- /dev/null
+++ include/llvm/Analysis/ICFileUtils.h
@@ -0,0 +1,70 @@
+#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
Index: include/llvm/Analysis/ICPass.h
===================================================================
--- /dev/null
+++ include/llvm/Analysis/ICPass.h
@@ -0,0 +1,66 @@
+//===-- 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
Index: include/llvm/Analysis/ICProxies.h
===================================================================
--- /dev/null
+++ include/llvm/Analysis/ICProxies.h
@@ -0,0 +1,108 @@
+//===-- 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
Index: include/llvm/Analysis/ICSetCurrentFunc.h
===================================================================
--- /dev/null
+++ include/llvm/Analysis/ICSetCurrentFunc.h
@@ -0,0 +1,42 @@
+//===-- 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
Index: include/llvm/Analysis/ICUtils.h
===================================================================
--- /dev/null
+++ include/llvm/Analysis/ICUtils.h
@@ -0,0 +1,120 @@
+//===-- 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
Index: include/llvm/Analysis/IterativeCompilation.h
===================================================================
--- /dev/null
+++ include/llvm/Analysis/IterativeCompilation.h
@@ -0,0 +1,10 @@
+#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
Index: include/llvm/Analysis/Passes.h
===================================================================
--- include/llvm/Analysis/Passes.h
+++ include/llvm/Analysis/Passes.h
@@ -109,6 +109,13 @@
   //
   FunctionPass *createMemDerefPrinter();
 
+  //===--------------------------------------------------------------------===//
+  //
+  // createICSetCurrentFuncPass - This pass sets decision tree proxy of the
+  // current function which is used in iterative compilation.
+  //
+  FunctionPass *createICSetCurrentFuncPass();
+
 }
 
 #endif
Index: include/llvm/InitializePasses.h
===================================================================
--- include/llvm/InitializePasses.h
+++ include/llvm/InitializePasses.h
@@ -247,7 +247,7 @@
 void initializeScalarEvolutionWrapperPassPass(PassRegistry&);
 void initializeShrinkWrapPass(PassRegistry &);
 void initializeSimpleInlinerPass(PassRegistry&);
-void initializeShadowStackGCLoweringPass(PassRegistry&);  
+void initializeShadowStackGCLoweringPass(PassRegistry&);
 void initializeRegisterCoalescerPass(PassRegistry&);
 void initializeSingleLoopExtractorPass(PassRegistry&);
 void initializeSinkingPass(PassRegistry&);
@@ -300,6 +300,9 @@
 void initializeLoopDistributePass(PassRegistry&);
 void initializeSjLjEHPreparePass(PassRegistry&);
 void initializeDemandedBitsPass(PassRegistry&);
+void initializeModuleDecisionTreeProxiesPass(PassRegistry&);
+void initializeFunctionFitnessPass(PassRegistry&);
+void initializeICSetCurrentFuncPass(PassRegistry&);
 }
 
 #endif
Index: include/llvm/Transforms/IPO/InlinerPass.h
===================================================================
--- include/llvm/Transforms/IPO/InlinerPass.h
+++ include/llvm/Transforms/IPO/InlinerPass.h
@@ -25,6 +25,7 @@
   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.
@@ -81,6 +82,8 @@
   // 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);
Index: include/llvm/Transforms/Utils/LoopUtils.h
===================================================================
--- include/llvm/Transforms/Utils/LoopUtils.h
+++ include/llvm/Transforms/Utils/LoopUtils.h
@@ -32,6 +32,7 @@
 class PredIteratorCache;
 class ScalarEvolution;
 class TargetLibraryInfo;
+class ModuleDecisionTreeProxies;
 
 /// \brief Captures loop safety information.
 /// It keep information for loop & its header may throw exception.
@@ -245,7 +246,7 @@
 /// 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
@@ -256,7 +257,7 @@
 /// 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
Index: lib/Analysis/Analysis.cpp
===================================================================
--- lib/Analysis/Analysis.cpp
+++ lib/Analysis/Analysis.cpp
@@ -73,6 +73,8 @@
   initializeTargetTransformInfoWrapperPassPass(Registry);
   initializeTypeBasedAliasAnalysisPass(Registry);
   initializeScopedNoAliasAAPass(Registry);
+  initializeModuleDecisionTreeProxiesPass(Registry);
+  initializeICSetCurrentFuncPass(Registry);
 }
 
 void LLVMInitializeAnalysis(LLVMPassRegistryRef R) {
Index: lib/Analysis/CMakeLists.txt
===================================================================
--- lib/Analysis/CMakeLists.txt
+++ lib/Analysis/CMakeLists.txt
@@ -20,6 +20,11 @@
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
+  ICUtils.cpp
+  ICFileUtils.cpp
+  ICDecisionTree.cpp
+  ICPass.cpp
+  ICProxies.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
@@ -27,6 +32,7 @@
   DomPrinter.cpp
   DominanceFrontier.cpp
   GlobalsModRef.cpp
+  ICSetCurrentFunc.cpp
   IVUsers.cpp
   InlineCost.cpp
   InstCount.cpp
Index: lib/Analysis/ICDecisionTree.cpp
===================================================================
--- /dev/null
+++ lib/Analysis/ICDecisionTree.cpp
@@ -0,0 +1,453 @@
+//===-- 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;
+}
Index: lib/Analysis/ICFileUtils.cpp
===================================================================
--- /dev/null
+++ lib/Analysis/ICFileUtils.cpp
@@ -0,0 +1,99 @@
+#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();
+}
Index: lib/Analysis/ICPass.cpp
===================================================================
--- /dev/null
+++ lib/Analysis/ICPass.cpp
@@ -0,0 +1,173 @@
+#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;
+}
Index: lib/Analysis/ICProxies.cpp
===================================================================
--- /dev/null
+++ lib/Analysis/ICProxies.cpp
@@ -0,0 +1,122 @@
+#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;
+  }
+}
Index: lib/Analysis/ICSetCurrentFunc.cpp
===================================================================
--- /dev/null
+++ lib/Analysis/ICSetCurrentFunc.cpp
@@ -0,0 +1,44 @@
+//===-- 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();
+}
Index: lib/Analysis/ICUtils.cpp
===================================================================
--- /dev/null
+++ lib/Analysis/ICUtils.cpp
@@ -0,0 +1,472 @@
+#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;
+}
Index: lib/CodeGen/RegAllocGreedy.cpp
===================================================================
--- lib/CodeGen/RegAllocGreedy.cpp
+++ lib/CodeGen/RegAllocGreedy.cpp
@@ -22,6 +22,7 @@
 #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"
@@ -45,6 +46,7 @@
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
+#include <fstream>
 #include <queue>
 
 using namespace llvm;
@@ -119,6 +121,7 @@
   const TargetInstrInfo *TII;
   const TargetRegisterInfo *TRI;
   RegisterClassInfo RCI;
+  ModuleDecisionTreeProxies *MDTP;
 
   // analyses
   SlotIndexes *Indexes;
@@ -473,6 +476,10 @@
   AU.addPreserved<LiveStacks>();
   AU.addRequired<MachineDominatorTree>();
   AU.addPreserved<MachineDominatorTree>();
+
+  if(IterativeCompilationOpt)
+    AU.addRequired<ModuleDecisionTreeProxies>();
+
   AU.addRequired<MachineLoopInfo>();
   AU.addPreserved<MachineLoopInfo>();
   AU.addRequired<VirtRegMap>();
@@ -864,6 +871,7 @@
   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.
@@ -907,11 +915,29 @@
     // 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;
 
@@ -2578,6 +2604,12 @@
   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>();
Index: lib/Target/Mips/CMakeLists.txt
===================================================================
--- lib/Target/Mips/CMakeLists.txt
+++ lib/Target/Mips/CMakeLists.txt
@@ -27,6 +27,7 @@
   MipsConstantIslandPass.cpp
   MipsDelaySlotFiller.cpp
   MipsFastISel.cpp
+  MipsFunctionFitness.cpp
   MipsInstrInfo.cpp
   MipsISelDAGToDAG.cpp
   MipsISelLowering.cpp
Index: lib/Target/Mips/Mips.h
===================================================================
--- lib/Target/Mips/Mips.h
+++ lib/Target/Mips/Mips.h
@@ -31,6 +31,7 @@
   FunctionPass *createMipsDelaySlotFillerPass(MipsTargetMachine &TM);
   FunctionPass *createMipsLongBranchPass(MipsTargetMachine &TM);
   FunctionPass *createMipsConstantIslandPass(MipsTargetMachine &tm);
+  FunctionPass *createMipsFunctionFitnessPass();
 } // end namespace llvm;
 
 #endif
Index: lib/Target/Mips/MipsFunctionFitness.cpp
===================================================================
--- /dev/null
+++ lib/Target/Mips/MipsFunctionFitness.cpp
@@ -0,0 +1,84 @@
+//===-- 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();
+}
Index: lib/Target/Mips/MipsTargetMachine.cpp
===================================================================
--- lib/Target/Mips/MipsTargetMachine.cpp
+++ lib/Target/Mips/MipsTargetMachine.cpp
@@ -31,6 +31,7 @@
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Analysis/IterativeCompilation.h"
 
 using namespace llvm;
 
@@ -251,6 +252,10 @@
 void MipsPassConfig::addPreEmitPass() {
   MipsTargetMachine &TM = getMipsTargetMachine();
   addPass(createMipsDelaySlotFillerPass(TM));
+
+  if(IterativeCompilationOpt)
+    addPass(createMipsFunctionFitnessPass());
+
   addPass(createMipsLongBranchPass(TM));
   addPass(createMipsConstantIslandPass(TM));
 }
Index: lib/Transforms/IPO/InlineAlways.cpp
===================================================================
--- lib/Transforms/IPO/InlineAlways.cpp
+++ lib/Transforms/IPO/InlineAlways.cpp
@@ -71,6 +71,7 @@
 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)
 
Index: lib/Transforms/IPO/InlineSimple.cpp
===================================================================
--- lib/Transforms/IPO/InlineSimple.cpp
+++ lib/Transforms/IPO/InlineSimple.cpp
@@ -79,6 +79,7 @@
 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)
 
Index: lib/Transforms/IPO/Inliner.cpp
===================================================================
--- lib/Transforms/IPO/Inliner.cpp
+++ lib/Transforms/IPO/Inliner.cpp
@@ -21,6 +21,7 @@
 #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"
@@ -32,6 +33,7 @@
 #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"
@@ -64,7 +66,7 @@
 // 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)
@@ -78,6 +80,7 @@
 void Inliner::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<AliasAnalysis>();
   AU.addRequired<AssumptionCacheTracker>();
+  AU.addRequired<ModuleDecisionTreeProxies>();
   CallGraphSCCPass::getAnalysisUsage(AU);
 }
 
@@ -322,7 +325,22 @@
   }
   
   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");
@@ -432,6 +450,8 @@
 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>();
Index: lib/Transforms/IPO/PassManagerBuilder.cpp
===================================================================
--- lib/Transforms/IPO/PassManagerBuilder.cpp
+++ lib/Transforms/IPO/PassManagerBuilder.cpp
@@ -257,6 +257,7 @@
   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
Index: lib/Transforms/Scalar/LICM.cpp
===================================================================
--- lib/Transforms/Scalar/LICM.cpp
+++ lib/Transforms/Scalar/LICM.cpp
@@ -35,6 +35,7 @@
 #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"
@@ -57,6 +58,8 @@
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include <algorithm>
+#include <fstream>
+
 using namespace llvm;
 
 #define DEBUG_TYPE "licm"
@@ -113,6 +116,7 @@
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       AU.addRequired<DominatorTreeWrapperPass>();
+      AU.addRequired<ModuleDecisionTreeProxies>();
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addRequiredID(LoopSimplifyID);
       AU.addPreservedID(LoopSimplifyID);
@@ -137,6 +141,7 @@
     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.
@@ -161,6 +166,7 @@
 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)
@@ -185,11 +191,14 @@
   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();
@@ -216,6 +225,7 @@
   // 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;
@@ -239,10 +249,10 @@
   //
   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.
@@ -297,7 +307,8 @@
 ///
 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 && 
@@ -315,7 +326,8 @@
   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;
@@ -355,7 +367,8 @@
 ///
 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 && 
@@ -369,6 +382,7 @@
   // 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
@@ -376,6 +390,12 @@
       // 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);
@@ -392,13 +412,19 @@
           canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
           isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo,
                                  CurLoop->getLoopPreheader()->getTerminator()))
-        Changed |= hoist(I, CurLoop->getLoopPreheader());
+      {
+        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;
 }
 
Index: unittests/Analysis/CMakeLists.txt
===================================================================
--- unittests/Analysis/CMakeLists.txt
+++ unittests/Analysis/CMakeLists.txt
@@ -13,4 +13,7 @@
   ScalarEvolutionTest.cpp
   MixedTBAATest.cpp
   ValueTrackingTest.cpp
+  ICProxies.cpp
+  ICDecisionTree.cpp
+  ICUtils.cpp
   )
Index: unittests/Analysis/ICDecisionTree.cpp
===================================================================
--- /dev/null
+++ unittests/Analysis/ICDecisionTree.cpp
@@ -0,0 +1,488 @@
+#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);
+}
+
+}
+}
+
Index: unittests/Analysis/ICProxies.cpp
===================================================================
--- /dev/null
+++ unittests/Analysis/ICProxies.cpp
@@ -0,0 +1,98 @@
+#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]);
+}
+
+}
+}
Index: unittests/Analysis/ICUtils.cpp
===================================================================
--- /dev/null
+++ unittests/Analysis/ICUtils.cpp
@@ -0,0 +1,162 @@
+#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());
+}
+
+}
+}