Add framework for iterative compilation to llvm

[zoran.jovanovic]

Summary

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

[zoran.jovanovic]

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

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

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

http://reviews.llvm.org/D4723

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

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

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

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

o
\
  o
    \
      o
        \
          o
            \
              o

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

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

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

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

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

Machine learning approach

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

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

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

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

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

This patch includes:

Code refactoring.

Rebase
This version of patch is rebased to current trunk.

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

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

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

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

Added unit tests for DecissionTree, FileUtils and ModuleDecisionTreeProxies.

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

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

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

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

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

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

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

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

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

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

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

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

[zoran.jovanovic]

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

[zoran.jovanovic]

*Places for improvement*

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

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

*Implemented solutions*
This patch addresses the first issue.

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

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

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

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

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

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

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

Priority tuning still stays open for suggestions and further work.

[zoran.jovanovic]

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

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

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

Comments are welcome.

[zoran.jovanovic]

Just to PING.
Any comments on this work?

[zoran.jovanovic]

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

[grosser]

Hi Zoran,

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

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

we see the following error:

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

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

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

but both files are unconditionally read by clang:

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

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

[zoran.jovanovic]

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

include/llvm/Analysis/ICDecisionTree.h

+//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the decision tree and decision tree proxy classes
+// which are used in iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ICDECISIONTREE_H
+#define LLVM_ANALYSIS_ICDECISIONTREE_H
+
+#include <string>
+#include <vector>
+#include <map>
+#include "llvm/ADT/BitVector.h"
+#include "llvm/Pass.h"
+#include "llvm/Analysis/ICUtils.h"
+
+namespace llvm {
+
+struct DecisionTreeNode {
+  DecisionTreeNode();
+  DecisionTreeNode(DecisionTreeNode *parent, int id);
+  int calcFinalPriority(int bestFunctionFitness);
+  DecisionTreeNode *Parent;
+  DecisionTreeNode *PrimaryDecision;
+  DecisionTreeNode *AlternativeDecision;
+  int Priority;
+  int Fitness;
+  int Depth;
+  int NodeId;
+  bool IsInterprocedural;
+  ICOptimization Optimization;
+
+  std::string getJSON();
+
+  bool operator==(const DecisionTreeNode &other) const;
+  bool operator!=(const DecisionTreeNode &other) const;
+  bool operator>(const DecisionTreeNode &other) const;
+  bool operator<(const DecisionTreeNode &other) const;
+  bool operator>=(const DecisionTreeNode &other) const;
+  bool operator<=(const DecisionTreeNode &other) const;
+};
+
+class NodeList {
+  public:
+    int size();
+    void add(DecisionTreeNode *node);
+    DecisionTreeNode* getFront() { return storage.front(); }
+    DecisionTreeNode* choice();
+    void clear() { storage.clear(); }
+    std::vector<DecisionTreeNode*> getStorage() {return storage;}
+
+  protected:
+    std::vector<DecisionTreeNode*> storage;
+};
+
+class NodeSelector {
+  public:
+    virtual void add(DecisionTreeNode *node) = 0;
+    virtual DecisionTreeNode* selectNode() = 0;
+    virtual ~NodeSelector() {};
+};
+
+class NodeSelectorRR : public NodeSelector {
+  public:
+    NodeSelectorRR();
+
+    void add(DecisionTreeNode *node);
+    DecisionTreeNode* selectNode();
+
+    NodeList getList(ICOptimization optim);
+    ICOptimization bestOptim();
+    int countEmptyLists();
+    int countUsedOptims();
+    ~NodeSelectorRR();
+
+  protected:
+    std::map<ICOptimization, NodeList> lists;
+    std::map<ICOptimization, bool> usedOptims;
+    void clearLists();
+    void updateUsedOptims();
+    void resetUsedOptims();
+};
+
+class NodeSelectorSimple : public NodeSelector {
+  public:
+    NodeSelectorSimple();
+
+    void add(DecisionTreeNode *node);
+    DecisionTreeNode* selectNode();
+
+    ~NodeSelectorSimple();
+
+  protected:
+    NodeList list;
+};
+
+/// 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;
+  DecisionTreeNode *LastSelectedNode;
+  BitVector Path;
+  SmallVector<ICOptimization, 128> Optimizations;
+  int FunctionFitness;
+  int BestFunctionFitness;
+  BitVector BestPath;
+  int NodeIdCount;
+  NodeSelector *selector;
+
+public:
+  DecisionTree();
+  ~DecisionTree();
+
+  int getFunctionFitness() const { return FunctionFitness; }
+  void setFunctionFitness(int x) { FunctionFitness = x; }
+  int getBestFunctionFitness() { return BestFunctionFitness; }
+  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();
+  DecisionTreeNode* getLastSelectedNode() { return LastSelectedNode; }
+
+  void applyResults(const MdtResults &results);
+
+  void splitPath(
+    const BitVector &paths,
+    BitVector &pathBeforeCodegen,
+    BitVector &pathAfterCodegen);
+
+  void dumpToGv(int currentIteration);
+  std::string getJSON();
+  void dumpToJSON(int currentIteration);
+
+  void addPrimaryDecision();
+  void addPrimaryDecision(llvm::DecisionTreeNode *node);
+  void addAlternativeDecision();
+  void addAlternativeDecision(llvm::DecisionTreeNode *node);
+  llvm::DecisionTreeNode* getRootNode();
+};
+
+}
+
+#endif

include/llvm/Analysis/ICFileUtils.h

+#ifndef LLVM_ANALYSIS_ICFILEUTILS_H
+#define LLVM_ANALYSIS_ICFILEUTILS_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/Analysis/ICUtils.h"
+#include <string>
+#include <vector>
+#include <map>
+
+namespace llvm {
+
+class ICFile {
+public:
+  ICFile() {}
+  ICFile(std::string filename) { this->filename = filename;}
+  ICFile(std::string filePrefix, int iteration);
+  virtual ~ICFile() {};
+
+  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) {}
+  ~ICInputFile() {}
+
+  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) {}
+  ~ICResultsFile() {}
+
+  std::vector<MdtResults> getResults() {return this->results;}
+  void setResults(std::vector<MdtResults> results) { this->results = results;}
+
+  void write();
+  bool read();
+
+private:
+  std::vector<MdtResults> results;
+};
+}
+
+
+#endif

include/llvm/Analysis/ICPass.h

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

include/llvm/Analysis/ICProxies.h

+//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the decision tree and decision tree proxy classes
+// which are used in iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ICPROXIES_H
+#define LLVM_ANALYSIS_ICPROXIES_H
+
+#include <string>
+#include <vector>
+#include <map>
+#include "llvm/ADT/BitVector.h"
+#include "llvm/Pass.h"
+#include "llvm/Analysis/ICUtils.h"
+#include "llvm/Analysis/ICDecisionTree.h"
+#include "llvm/Analysis/ICFileUtils.h"
+
+namespace llvm {
+
+/// Decision tree proxy is the proxy class for the decision tree so
+/// that it has the method getDecision and the all data can be effectively
+/// streamed between proxy and the decision tree.
+class DecisionTreeProxy {
+public:
+  DecisionTreeProxy();
+
+  BitVector &getPath() { return Path; }
+  const BitVector &getPath() const { return Path; }
+  int getFunctionFitness() const { return FunctionFitness; }
+  void setFunctionFitness(int x) { FunctionFitness = x; }
+
+  std::vector<int> &getPriorities() { return Priorities; }
+  const std::vector<int> &getPriorities() const { return Priorities; }
+
+  std::vector<ICOptimization> &getOptimizations() { return Optimizations; }
+  const std::vector<ICOptimization> &getOptimizations() const {
+    return Optimizations; }
+
+  bool getDecision(int priority, ICOptimization opt);
+
+  std::string generateResultsString();
+  MdtResults getResults() const;
+  void setPath(const BitVector &path);
+
+protected:
+  BitVector Path;
+  int FunctionFitness;
+  int BestFunctionFitness;
+  std::vector<int> Priorities;
+  std::vector<ICOptimization> Optimizations;
+  int CurrentDepth;
+};
+
+/// This class is the storage for all the decision trees for
+/// each function and compilation phase.
+class ModuleDecisionTrees {
+public:
+
+  ModuleDecisionTrees(int totalIters = -1, bool parallel = false, std::string filename = "");
+  ~ModuleDecisionTrees();
+
+  DecisionTree &getDecisionTree(const FnNameAndPhase &fnNameAndPhase);
+
+  void startNewIteration();
+  void getPaths(ICPathsMap &paths);
+  void applyResults(const std::vector<MdtResults> &results);
+  void setFunctionFitness(int totalFitness);
+  void updateBestFunctionFitness(int iteration);
+  void updateNodesFitness();
+  void selectPath(bool FinalPass);
+  void splitPaths(
+    const ICPathsMap &paths,
+    ICPathsMap &pathBeforeCodegen,
+    ICPathsMap &pathAfterCodegen);
+  void splitPathsMap(
+      const ICPathsMap &paths,
+      ICPathsMap &pathsBeforeCodegen,
+      ICPathsMap &pathsAfterCodegen);
+  void showTrees();
+  std::string &getICInputFileOpt() { return ICInputFileOpt; }
+  std::string &getICInputFile2Opt() { return ICInputFile2Opt; }
+  std::string &getICResultsFileOpt() { return ICResultsFileOpt; }
+  std::string &getICResultsFile2Opt() { return ICResultsFile2Opt; }
+  FnNameAndPhase::ICPhase getCurrentPhase();
+
+  ICInputFile &getICInputFile() { return input1; }
+  ICInputFile &getICInputFile2() { return input2; }
+  ICResultsFile &getICResultsFile() { return results1; }
+  ICResultsFile &getICResultsFile2() { return results2; }
+  std::map<FnNameAndPhase, DecisionTree*> &getDecisionTrees() {
+    return DecisionTrees;
+  }
+  void log();
+
+protected:
+  int NumberOfIterations;
+  int CurrentIteration;
+  bool ParallelExplore;
+  std::map<FnNameAndPhase, DecisionTree *> DecisionTrees;
+  std::string ICInputFileOpt;
+  std::string ICInputFile2Opt;
+  std::string ICResultsFileOpt;
+  std::string ICResultsFile2Opt;
+  std::string ModuleName;
+
+  ICInputFile input1;
+  ICInputFile input2;
+  ICResultsFile results1;
+  ICResultsFile results2;
+};
+
+}
+
+#endif

include/llvm/Analysis/ICSetCurrentFunc.h

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

include/llvm/Analysis/ICUtils.h

+//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the decision tree and decision tree proxy classes
+// which are used in iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ICUTILS_H
+#define LLVM_ANALYSIS_ICUTILS_H
+
+#include <string>
+#include "llvm/Support/CommandLine.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/BitVector.h"
+#include <map>
+#include <vector>
+
+namespace llvm {
+
+extern cl::opt<bool> IterativeCompilationOpt;
+extern cl::opt<std::string> FicInputFile;
+extern cl::opt<std::string> FicInputFile2;
+extern cl::opt<std::string> FicResultsFile;
+extern cl::opt<std::string> FicResultsFile2;
+
+/// Iterative Compilation Optimization
+enum ICOptimization {
+  NoOptimization,
+  InlinerOpt,
+  LicmOpt,
+  RegAllocOpt,
+  ErrOpt = -1
+};
+
+enum ICExploreAlg {
+  Sequential,
+  RoundRobin,
+  Parallel
+};
+
+const int MaxDtPriority = 1000;
+extern bool UseRand;
+extern ICExploreAlg ExploreAlg;
+
+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);
+
+std::string getModuleName(int argc, const char **argv);
+
+}
+
+
+#endif

include/llvm/Analysis/IterativeCompilation.h

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

include/llvm/Analysis/Passes.h

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

include/llvm/InitializePasses.h

 void initializeSjLjEHPreparePass(PassRegistry&);
 void initializeDemandedBitsWrapperPassPass(PassRegistry&);
 void initializeFuncletLayoutPass(PassRegistry &);
 void initializeLoopLoadEliminationPass(PassRegistry&);
 void initializeFunctionImportPassPass(PassRegistry &);
 void initializeLoopVersioningPassPass(PassRegistry &);
 void initializeWholeProgramDevirtPass(PassRegistry &);
 void initializePatchableFunctionPass(PassRegistry &);
+void initializeModuleDecisionTreeProxiesPass(PassRegistry&);
+void initializeFunctionFitnessPass(PassRegistry&);
+void initializeICSetCurrentFuncPass(PassRegistry&);
 }
 
 #endif

include/llvm/Transforms/IPO/InlinerPass.h

 #include "llvm/Analysis/CallGraphSCCPass.h"
 
 namespace llvm {
 class AssumptionCacheTracker;
 class CallSite;
 class DataLayout;
 class InlineCost;
 template <class PtrType, unsigned SmallSize> class SmallPtrSet;
+class ModuleDecisionTreeProxies;
 
 /// Inliner - This class contains all of the helper code which is used to
 /// perform the inlining operations that do not depend on the policy.
 ///
 struct Inliner : public CallGraphSCCPass {
   explicit Inliner(char &ID);
   explicit Inliner(char &ID, bool InsertLifetime);
 
struct Inliner : public CallGraphSCCPass {
   /// attribute. This is useful for the InlineAlways pass that only wants to
   /// deal with that subset of the functions.
   bool removeDeadFunctions(CallGraph &CG, bool AlwaysInlineOnly = false);
 
 private:
   // 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);
 
 protected:
   AssumptionCacheTracker *ACT;
 };
 
 } // End llvm namespace
 
 #endif

include/llvm/Transforms/Utils/LoopUtils.h

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

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

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeSCEVAAWrapperPassPass(Registry);
   initializeScalarEvolutionWrapperPassPass(Registry);
   initializeTargetTransformInfoWrapperPassPass(Registry);
   initializeTypeBasedAAWrapperPassPass(Registry);
   initializeScopedNoAliasAAWrapperPassPass(Registry);
+  initializeModuleDecisionTreeProxiesPass(Registry);
 }
 
 void LLVMInitializeAnalysis(LLVMPassRegistryRef R) {
   initializeAnalysis(*unwrap(R));
 }
 
 void LLVMInitializeIPA(LLVMPassRegistryRef R) {
   initializeAnalysis(*unwrap(R));

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   CGSCCPassManager.cpp
   CallGraph.cpp
   CallGraphSCCPass.cpp
   CallPrinter.cpp
   CaptureTracking.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
+  ICUtils.cpp
+  ICFileUtils.cpp
+  ICDecisionTree.cpp
+  ICPass.cpp
+  ICProxies.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DominanceFrontier.cpp
   EHPersonalities.cpp
   GlobalsModRef.cpp

lib/Analysis/ICDecisionTree.cpp

+//===-- DecisionTree.cpp - Implement Decision Tree Classes ----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the decision tree and decision tree proxy classes
+// which are used in iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+/* Here is a brief explanation of the forming of the decision tree.
+
+First, some passes need to be modified to call getDecision function.
+If this function returns false, a pass should do exactly as the code
+without modification. If the return value is true, then the alternative
+path is taken.
+
+Function getDecision always returns false in the first iteration.
+And the compiler should work exactly as if there was no iterative framework.
+
+Let us assume that getDecision function is called four times in the
+first iteration of iterative compilation. After the end of the first
+iteration, the decision tree will look like this:
+
+o
+  \
+    o
+      \
+        o
+          \
+            o
+              \
+                o
+
+In the second iteration, exactly one decision is changed and the compiler
+works as in the first iteration until it reaches this particular decision.
+Then alternative path is taken in this point. Further, getDecision function
+returns false until compilation iteration is finished. Let us assume that we
+took alternative decision at the third decision and that there are three more
+calls of getDecision function. Note that different compilation paths may
+have different number of calls of getDecision function.
+
+o
+  \
+    o
+      \
+        o
+      /   \
+     o      o
+       \      \
+         o      o
+           \
+             o
+
+Every new iteration adds one new branch to the decision tree.
+
+At the end of each iteration fitness of the generated code is evaluated.
+In the last iteration, the compiler takes the path with the best fitness.
+
+To augment the selection of a node where alternative decision would be taken,
+getDecision tree takes one parameter. This parameter is interpreted as
+priority and the node with highest priory is selected for next alternative
+decision.
+*/
+
+#include <algorithm>
+#include <fstream>
+#include <sstream>
+#include <limits.h>
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/ICDecisionTree.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/YAMLParser.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <iostream>
+#include <vector>
+#include <cstdlib>
+#include <ctime>
+
+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;
+
+  if(llvm::ExploreAlg == llvm::ICExploreAlg::RoundRobin ||
+      llvm::ExploreAlg == llvm::ICExploreAlg::Parallel) {
+    selector = new NodeSelectorRR();
+  }
+  else {
+    selector = new NodeSelectorSimple();
+  }
+}
+
+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;
+    puts("Returning best function fintess");
+    return true;
+  }
+  DecisionTreeNode *selectedNode = selectNode();
+
+  if (selectedNode) {
+    LastSelectedNode = selectedNode;
+    findPath(selectedNode, Path);
+    return false;
+  } else {
+    Path = BestPath;
+    return true;
+  }
+}
+
+DecisionTreeNode* DecisionTree::selectNode() {
+  SmallVector<DecisionTreeNode *, 64> nodesToExplore;
+  DecisionTreeNode *selectedNode = 0;
+
+  // if tree is empty, select root node
+  if (!DecisionTreeRoot->AlternativeDecision
+        && !DecisionTreeRoot->PrimaryDecision)
+    return 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) {
+      selector->add(n);
+    }
+
+    // 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);
+  }
+
+  selectedNode = selector->selectNode();
+
+  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();
+
+  // 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();
+}
+
+std::string DecisionTree::getJSON() {
+  std::stringstream JSON;
+  DecisionTreeNode *n;
+  SmallVector<DecisionTreeNode*, 64> paths;
+
+  JSON << "[\n";
+
+  paths.push_back(DecisionTreeRoot);
+  while(!paths.empty())
+  {
+    // this is path root
+    // start new path
+    n = paths.back();
+
+    if(n->Parent)
+      JSON << "\n\t{\n\t\"root\" : " << n->Parent->getJSON() << ",";
+    else
+      JSON << "\n\t{\n\t\"root\" : " << n->getJSON() << ",";
+
+    JSON << "\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
+        JSON << "\t\t" << n->getJSON();
+        n = n->PrimaryDecision;
+      }
+
+      if(n->PrimaryDecision)
+        JSON << ",\n";
+      else
+        JSON << "\n";
+
+    }
+
+    if(!paths.empty())
+      JSON << "\t]},\n";
+    else
+      JSON << "\t]}\n";
+  }
+
+  JSON << "]";
+
+  return JSON.str();
+}
+
+void DecisionTree::dumpToJSON(int currentIteration) {
+  std::stringstream filePath;
+  std::string JSON = getJSON();
+
+  filePath << "/tmp/ic-tree-" << currentIteration << ".json";
+  std::ofstream f(filePath.str());
+
+  f << JSON;
+
+  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;
+}
+
+NodeSelectorSimple::NodeSelectorSimple() {
+}
+
+NodeSelectorSimple::~NodeSelectorSimple() {
+}
+
+void NodeSelectorSimple::add(DecisionTreeNode *node) {
+  list.add(node);
+}
+
+DecisionTreeNode* NodeSelectorSimple::selectNode(){
+  return list.choice();
+}
+
+NodeSelectorRR::NodeSelectorRR() {
+  lists[LicmOpt] = NodeList();
+  lists[InlinerOpt] = NodeList();
+  lists[RegAllocOpt] = NodeList();
+
+  usedOptims[LicmOpt] = false;
+  usedOptims[InlinerOpt] = false;
+  usedOptims[RegAllocOpt] = false;
+}
+
+NodeSelectorRR::~NodeSelectorRR() {
+}
+
+int NodeSelectorRR::countUsedOptims() {
+  int cnt = 0;
+
+  for(auto it : usedOptims) {
+    cnt += it.second == true;
+  }
+
+  return cnt;
+}
+
+void NodeSelectorRR::add(DecisionTreeNode *node) {
+  lists[node->Optimization].add(node);
+}
+
+NodeList NodeSelectorRR::getList(ICOptimization optim) {
+  return lists[optim];
+}
+
+ICOptimization NodeSelectorRR::bestOptim() {
+  ICOptimization bestOptim;
+  DecisionTreeNode *currentBest = NULL;
+
+  updateUsedOptims();
+
+  if(countEmptyLists() == 3) {
+    bestOptim = ErrOpt;
+  }
+  else {
+    for(auto it : usedOptims) {
+      if(it.second == true) {
+        continue;
+      }
+      if(currentBest == NULL || *lists[it.first].getFront() > *currentBest)  {
+        currentBest = lists[it.first].getFront();
+      }
+    }
+    bestOptim = currentBest->Optimization;
+  }
+
+  return bestOptim;
+}
+
+int NodeSelectorRR::countEmptyLists() {
+  int r = 0;
+
+  for(auto it : lists)
+    r += it.second.size() == 0;
+
+  return r;
+}
+
+DecisionTreeNode* NodeSelectorRR::selectNode() {
+  ICOptimization opt = bestOptim();
+  DecisionTreeNode *n;
+
+  if(opt == ErrOpt) {
+    n = NULL;
+  }
+  else {
+    n = lists[opt].choice();
+    usedOptims[opt] = true;
+    clearLists();
+  }
+
+  return n;
+}
+
+void NodeSelectorRR::clearLists() {
+  for(auto &it : lists) {
+    it.second.clear();
+  }
+}
+
+void NodeSelectorRR::updateUsedOptims() {
+  if(countUsedOptims() == 3)
+    resetUsedOptims();
+
+  for(auto it : lists) {
+    if(it.second.size() == 0) {
+      usedOptims[it.first] = true;
+    }
+  }
+}
+
+void NodeSelectorRR::resetUsedOptims() {
+  for(auto &it : usedOptims) {
+    it.second = false;
+  }
+}
+
+int NodeList::size() {
+  return storage.size();
+}
+
+void NodeList::add(DecisionTreeNode *node) {
+  if(storage.size() != 0 && (*node > *storage.front())) {
+    storage.clear();
+  }
+
+  if(storage.size() == 0) {
+    storage.push_back(node);
+  }
+  else if(*node == *storage.front()){
+    storage.push_back(node);
+  }
+}
+
+DecisionTreeNode* NodeList::choice() {
+  int choice;
+
+  if(UseRand) {
+    choice = time(NULL) % storage.size();
+  }
+  else {
+    choice = 0;
+  }
+
+  return storage[choice];
+}
+
+bool DecisionTreeNode::operator==(const DecisionTreeNode &other) const {
+  bool fitness = this->Fitness == other.Fitness;
+  bool priority = this->Priority == other.Priority;
+
+  return fitness && priority;
+}
+
+bool DecisionTreeNode::operator!=(const DecisionTreeNode &other) const {
+  return !(*this == other);
+}
+
+bool DecisionTreeNode::operator>(const DecisionTreeNode &other) const {
+  bool retval;
+
+  if(*this == other) retval = false;
+  else if(this->Fitness > other.Fitness) retval = false;
+  else if(this->Fitness < other.Fitness) retval = true;
+  else if(this->Fitness == other.Fitness && this->Priority > other.Priority)
+    retval = true;
+
+  return retval;
+}
+
+bool DecisionTreeNode::operator<(const DecisionTreeNode &other) const {
+  bool retval;
+
+  if(*this == other) retval = false;
+  else retval = !(*this > other);
+
+  return retval;
+}

lib/Analysis/ICFileUtils.cpp

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

lib/Analysis/ICPass.cpp

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

lib/Analysis/ICProxies.cpp

+#include "llvm/Analysis/ICProxies.h"
+#include "llvm/Analysis/ICUtils.h"
+#include <sstream>
+#include <fstream>
+
+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(int totalIters, bool parallel,
+    std::string filename) :
+  NumberOfIterations(totalIters), CurrentIteration(-1), ModuleName(filename) {
+    if(NumberOfIterations == -1) {
+      ParallelExplore = false;
+    }
+    else if(ExploreAlg == ICExploreAlg::Parallel) {
+      ParallelExplore = true;
+    }
+    else {
+      ParallelExplore = false;
+    }
+  }
+
+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();
+  }
+  CurrentIteration++;
+}
+
+/// 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;
+  }
+}
+
+FnNameAndPhase::ICPhase ModuleDecisionTrees::getCurrentPhase() {
+  FnNameAndPhase::ICPhase targetPhase;
+
+  if(CurrentIteration < NumberOfIterations/3) {
+    targetPhase = FnNameAndPhase::FunctionPhase;
+  }
+  else if(CurrentIteration < 2*NumberOfIterations/3) {
+    targetPhase = FnNameAndPhase::ModulePhase;
+  }
+  else {
+    targetPhase = FnNameAndPhase::CodeGenPhase;
+  }
+
+  return targetPhase;
+}
+
+/// Apply results to all decision trees used for a module optimization.
+void ModuleDecisionTrees::applyResults(const std::vector<MdtResults> &results) {
+  FnNameAndPhase::ICPhase targetPhase;
+
+  if(ParallelExplore) {
+    targetPhase = getCurrentPhase();
+  }
+  else {
+    targetPhase = FnNameAndPhase::ModulePhase;
+  }
+
+  for (const auto &R : results) {
+    if(R.FunctionNameAndPhase.getPhase() == targetPhase) {
+      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)
+{
+  FnNameAndPhase::ICPhase targetPhase;
+  bool isFinal;
+
+  if(ParallelExplore) {
+    targetPhase = getCurrentPhase();
+
+    if(CurrentIteration < NumberOfIterations/3*2)
+      isFinal = (CurrentIteration+1)%(NumberOfIterations/3) == 0;
+    else
+      isFinal = CurrentIteration >= (NumberOfIterations-2);
+
+  }
+  else {
+    targetPhase = FnNameAndPhase::ModulePhase;
+    isFinal = CurrentIteration >= (NumberOfIterations);
+  }
+
+  for (const auto &P : DecisionTrees) {
+    if(P.first.getPhase() == targetPhase) {
+      DecisionTree *DT = P.second;
+      DT->selectPath(isFinal);
+    }
+  }
+}
+
+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;
+  }
+}
+
+void ModuleDecisionTrees::splitPathsMap(
+    const ICPathsMap &paths,
+    ICPathsMap &pathsBeforeCodegen,
+    ICPathsMap &pathsAfterCodegen) {
+
+  pathsBeforeCodegen.clear();
+  pathsAfterCodegen.clear();
+
+  for(auto const &it : paths) {
+    if(it.first.getPhase() == FnNameAndPhase::CodeGenPhase) {
+      pathsAfterCodegen[it.first] = it.second;
+    }
+    else {
+      pathsBeforeCodegen[it.first] = it.second;
+    }
+  }
+}
+
+void ModuleDecisionTrees::setFunctionFitness(int totalFitness) {
+  for(auto &dt : DecisionTrees) {
+    dt.second->setFunctionFitness(totalFitness);
+  }
+}
+
+void ModuleDecisionTrees::log() {
+  std::stringstream commonLogFilename, treeLogFilename, commonPartFilename;
+  std::ofstream commonLogFile, treeLogFile;
+  DecisionTree *dt;
+
+
+    for(const auto &it : DecisionTrees ) {
+      std::string treeName = it.first.getName();
+      int phase = it.first.getPhase();
+      dt = it.second;
+
+      // compose filenames and open files
+      commonPartFilename << CurrentIteration << "-";
+      commonPartFilename << ModuleName << "-";
+      commonPartFilename << treeName << "-";
+      commonPartFilename << "ph" << phase;
+
+      commonLogFilename << "/tmp/ic-log-" << commonPartFilename.str() << ".json";
+      treeLogFilename << "/tmp/ic-tree-" << commonPartFilename.str() << ".json";
+
+      commonLogFile.open(commonLogFilename.str(), std::fstream::trunc);
+      treeLogFile.open(treeLogFilename.str(), std::fstream::trunc);
+
+      // get tree json - tree has dumpToJSON, change it to get JSON
+      std::string treeJSON = dt->getJSON();
+      treeLogFile << treeJSON;
+
+      commonLogFile << "{\n";
+      int bestFunctionFitness = dt->getBestFunctionFitness();
+      commonLogFile << "\t\"BestFunctionFitness\"\t: ";
+      commonLogFile << bestFunctionFitness << ",\n";
+
+      // current function fitness - already implemented
+      int currentFunctionFitness = dt->getFunctionFitness();
+      commonLogFile << "\t\"CurrentFunctionFitness\": ";
+      commonLogFile << currentFunctionFitness << ",\n";
+
+      // selected node - get path and descent to it
+      int lastSelectedNodeID = dt->getLastSelectedNode()->NodeId;
+      commonLogFile << "\t\"LastSelectedNodeID\"\t: ";
+      commonLogFile << lastSelectedNodeID << "\n";
+
+      commonLogFile << "}\n";
+
+      commonPartFilename.str("");
+      commonLogFilename.str("");
+      treeLogFilename.str("");
+
+      commonLogFile.close();
+      treeLogFile.close();
+    }
+}

lib/Analysis/ICUtils.cpp

+#include "llvm/Analysis/ICUtils.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/ErrorOr.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/YAMLParser.h"
+#include <sstream>
+
+using namespace llvm;
+
+cl::opt<bool>
+llvm::IterativeCompilationOpt("fiterative-comp", cl::init(false),
+                    cl::desc("Enable iterative compilation"));
+
+cl::opt<std::string>
+llvm::FicInputFile("fic-input-file", cl::init("ic-input"));
+
+cl::opt<std::string>
+llvm::FicInputFile2("fic-input2-file", cl::init("ic-input2"));
+
+cl::opt<std::string>
+llvm::FicResultsFile("fic-results-file", cl::init("ic-results"));
+
+cl::opt<std::string>
+llvm::FicResultsFile2("fic-results2-file", cl::init("ic-results2"));
+
+bool llvm::UseRand = true;
+ICExploreAlg llvm::ExploreAlg = RoundRobin;
+
+
+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++) {
+    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);
+
+  // push all results which aren't module phase
+  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 only one has module phase results
+  if (moduleResults1 && !moduleResults2)
+      mergedResults.push_back(*moduleResults1);
+
+  if (!moduleResults1 && moduleResults2)
+      mergedResults.push_back(*moduleResults2);
+
+  // if both have module phase results
+  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;
+}
+
+std::string llvm::getModuleName(int argc, const char **argv) {
+  std::string filename;
+
+  for(int i = 0; i < argc; i++) {
+    if(strstr(argv[i], ".i.c")) {
+      filename.assign(argv[i]);
+      filename = filename.substr(0, filename.find(".i.c"));
+      break;
+    }
+  }
+
+  return filename;
+}

lib/CodeGen/RegAllocGreedy.cpp

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

lib/Target/Mips/CMakeLists.txt

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

lib/Target/Mips/Mips.h

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

lib/Target/Mips/MipsFunctionFitness.cpp

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

lib/Target/Mips/MipsTargetMachine.cpp

 #include "MipsTargetObjectFile.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Analysis/IterativeCompilation.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "mips"
 
 extern "C" void LLVMInitializeMipsTarget() {
   // Register the target.
   RegisterTargetMachine<MipsebTargetMachine> X(TheMipsTarget);
void MipsPassConfig::addPreEmitPass() {
   MipsTargetMachine &TM = getMipsTargetMachine();
 
   // The delay slot filler pass can potientially create forbidden slot (FS)
   // hazards for MIPSR6 which the hazard schedule pass (HSP) will fix. Any
   // (new) pass that creates compact branches after the HSP must handle FS
   // hazards itself or be pipelined before the HSP.
   addPass(createMipsDelaySlotFillerPass(TM));
   addPass(createMipsHazardSchedule());
+
+  if(IterativeCompilationOpt)
+    addPass(createMipsFunctionFitnessPass());
+
   addPass(createMipsLongBranchPass(TM));
   addPass(createMipsConstantIslandPass(TM));
 }

lib/Transforms/IPO/InlineAlways.cpp

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

lib/Transforms/IPO/InlineSimple.cpp

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

lib/Transforms/IPO/Inliner.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/IterativeCompilation.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"

 
 /// For this class, we declare that we require and preserve the call graph.
 /// If the derived class implements this method, it should
 /// always explicitly call the implementation here.
 void Inliner::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   getAAResultsAnalysisUsage(AU);
+  AU.addRequired<ModuleDecisionTreeProxies>();
   CallGraphSCCPass::getAnalysisUsage(AU);
 }
 
 
 typedef DenseMap<ArrayType*, std::vector<AllocaInst*> >
 InlinedArrayAllocasTy;
 
 /// If it is possible to inline the specified call site,
if (IC.isNever()) {
     DEBUG(dbgs() << "    NOT Inlining: cost=never"
           << ", Call: " << *CS.getInstruction() << "\n");
     emitAnalysis(CS, Twine(CS.getCalledFunction()->getName() +
                            " should never be inlined (cost=never)"));
     return false;
   }
   
   Function *Caller = CS.getCaller();
-  if (!IC) {
+  bool doInlinging = (bool)IC;
+
+  int ip = IC.getCostDelta();
+  if (ip < 0)
+    ip = -ip;
+  int t = MaxDtPriority - ip;
+  bool decision = false;
+
+  if (t >= 0) {
+    decision = MDTP->getDecision(t, InlinerOpt);
+  }
+
+  if (decision)
+    doInlinging = !doInlinging;
+
+  if (!doInlinging) {
     DEBUG(dbgs() << "    NOT Inlining: cost=" << IC.getCost()
           << ", thres=" << (IC.getCostDelta() + IC.getCost())
           << ", Call: " << *CS.getInstruction() << "\n");
     emitAnalysis(CS, Twine(CS.getCalledFunction()->getName() +
                            " too costly to inline (cost=") +
                          Twine(IC.getCost()) + ", threshold=" +
                          Twine(IC.getCostDelta() + IC.getCost()) + ")");
     return false;
static bool InlineHistoryIncludes(Function *F, int InlineHistoryID,
   return false;
 }
 
 bool Inliner::runOnSCC(CallGraphSCC &SCC) {
   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
   ACT = &getAnalysis<AssumptionCacheTracker>();
   auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
+  MDTP = &getAnalysis<ModuleDecisionTreeProxies>();
+  MDTP->setModuleCompilationPhase();
+
+
   SmallPtrSet<Function*, 8> SCCFunctions;
   DEBUG(dbgs() << "Inliner visiting SCC:");
   for (CallGraphNode *Node : SCC) {
     Function *F = Node->getFunction();
     if (F) SCCFunctions.insert(F);
     DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE"));
   }
 
bool Inliner::runOnSCC(CallGraphSCC &SCC) {
 
   // Now that we have all of the call sites, move the ones to functions in the
   // current SCC to the end of the list.
   unsigned FirstCallInSCC = CallSites.size();
   for (unsigned i = 0; i < FirstCallInSCC; ++i)
     if (Function *F = CallSites[i].first.getCalledFunction())
       if (SCCFunctions.count(F))
         std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
   
-  
   InlinedArrayAllocasTy InlinedArrayAllocas;
   InlineFunctionInfo InlineInfo(&CG, ACT);
 
   // Now that we have all of the call sites, loop over them and inline them if
   // it looks profitable to do so.
   bool Changed = false;
   bool LocalChange;
   do {

lib/Transforms/Scalar/LICM.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/Loads.h"
+#include "llvm/Analysis/IterativeCompilation.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
struct LICM : public LoopPass {
 
     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 
     /// This transformation requires natural loop information & requires that
     /// loop preheaders be inserted into the CFG...
     ///
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
+      AU.addRequired<ModuleDecisionTreeProxies>();
       AU.addRequired<TargetLibraryInfoWrapperPass>();
       getLoopAnalysisUsage(AU);
     }
 
     using llvm::Pass::doFinalization;
 
     bool doFinalization() override {
       assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets");
       return false;
     }
 
   private:
     AliasAnalysis *AA;       // Current AliasAnalysis information
     LoopInfo      *LI;       // Current LoopInfo
     DominatorTree *DT;       // Dominator Tree for the current Loop.
 
     TargetLibraryInfo *TLI;  // TargetLibraryInfo for constant folding.
+    ModuleDecisionTreeProxies *MDTP;
 
     // State that is updated as we process loops.
     bool Changed;            // Set to true when we change anything.
     BasicBlock *Preheader;   // The preheader block of the current loop...
     Loop *CurLoop;           // The current loop we are working on...
     AliasSetTracker *CurAST; // AliasSet information for the current loop...
     DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap;
 
private:
 
     AliasSetTracker *collectAliasInfoForLoop(Loop *L);
   };
 }
 
 char LICM::ID = 0;
 INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
+INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false)
 
 Pass *llvm::createLICMPass() { return new LICM(); }
 
 /// Hoist expressions out of the specified loop. Note, alias info for inner
 /// loop is not preserved so it is not a good idea to run LICM multiple
 /// times on one loop.
 ///
 bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
   if (skipOptnoneFunction(L))
     return false;
 
   Changed = false;
 
   // Get our Loop and Alias Analysis information...
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  MDTP = &getAnalysis<ModuleDecisionTreeProxies>();
 
   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
   CurAST = collectAliasInfoForLoop(L);
 
   CurLoop = L;
 
   // Get the preheader block to move instructions into...
   Preheader = L->getLoopPreheader();
 
+  if(llvm::ExploreAlg == llvm::ICExploreAlg::Parallel) {
+    std::string fnName = Preheader->getParent()->getName().str();
+    MDTP->setCurrentFunctionAndPhase(fnName, FnNameAndPhase::FunctionPhase);
+  }
+  else {
+    MDTP->setModuleCompilationPhase();
+  }
+
   // Compute loop safety information.
   LICMSafetyInfo SafetyInfo;
   computeLICMSafetyInfo(&SafetyInfo, CurLoop);
 
   // We want to visit all of the instructions in this loop... that are not parts
   // of our subloops (they have already had their invariants hoisted out of
   // their loop, into this loop, so there is no need to process the BODIES of
   // the subloops).
   //
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
   // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
   //
   if (L->hasDedicatedExits())
     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop,
-                          CurAST, &SafetyInfo);
+                          CurAST, &SafetyInfo, MDTP);
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI,
-                           CurLoop, CurAST, &SafetyInfo);
+                           CurLoop, CurAST, &SafetyInfo, MDTP);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
   if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
     SmallVector<BasicBlock *, 8> ExitBlocks;
     SmallVector<Instruction *, 8> InsertPts;
     PredIteratorCache PIC;
 

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

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

unittests/Analysis/CMakeLists.txt

add_llvm_unittest(AnalysisTests
   CFGTest.cpp
   CGSCCPassManagerTest.cpp
   LazyCallGraphTest.cpp
   LoopPassManagerTest.cpp
   ScalarEvolutionTest.cpp
   MixedTBAATest.cpp
   ValueTrackingTest.cpp
   UnrollAnalyzer.cpp
+  ICProxies.cpp
+  ICDecisionTree.cpp
+  ICUtils.cpp
+  ICParallel.cpp
   )

unittests/Analysis/ICDecisionTree.cpp

+#include "gtest/gtest.h"
+#include "llvm/Analysis/ICDecisionTree.h"
+
+namespace llvm {
+
+
+namespace {
+// -------------- FIXTURES -----------------//
+DecisionTreeNode *prepareNode(int priority, int id)
+{
+  DecisionTreeNode *node = new DecisionTreeNode;
+  node->Fitness = 0;
+  node->Priority = priority;
+  node->NodeId = id;
+  node->Optimization = LicmOpt;
+  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();
+
+  ASSERT_TRUE(node != NULL);
+
+  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_TRUE(selectedNode != NULL);
+  ASSERT_EQ(200, selectedNode->Priority);
+}
+
+TEST(ICDecisionTree, selectNodePrimaryAndAlternative)
+{
+  DecisionTree *dt = getDTPrimaryAndAlternative();
+  DecisionTreeNode *selectedNode = dt->selectNode();
+  ASSERT_TRUE(selectedNode != NULL);
+  ASSERT_EQ(400, selectedNode->Priority);
+}
+
+TEST(ICDecisionTree, selectNodeOnlyAlternative)
+{
+  DecisionTree *dt = getDTOnlyAlternative();
+  DecisionTreeNode *selectedNode = dt->selectNode();
+  ASSERT_TRUE(selectedNode == NULL);
+}
+
+
+// scenario 1:
+// given there is an empty tree
+// and there are new decisions stored in merged results
+// when those results are applied to a decision tree
+// then new nodes have to be added to the tree
+// and their priorirites and optimizations set
+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++;
+  }
+}
+// scenario 2:
+// given there is non empty tree
+// and new iteration is started
+// and there are new resusults in merged results
+// when those results are applied to an existing decision tree
+// then old nodes should be preserved
+// and new nodes added to correct place
+// and their priorities and optimizations set
+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);
+}
+
+TEST(ICNodeSelector, AddNodes) {
+  NodeSelector selector;
+
+  DecisionTreeNode *nl = new DecisionTreeNode();
+  nl->Optimization = LicmOpt;
+  selector.add(nl);
+
+  DecisionTreeNode *ni = new DecisionTreeNode();
+  ni->Optimization = InlinerOpt;
+  selector.add(ni);
+
+  DecisionTreeNode *nra = new DecisionTreeNode();
+  nra->Optimization = RegAllocOpt;
+  selector.add(nra);
+
+  NodeList licmOpt      = selector.getList(LicmOpt);
+  NodeList inlinerList  = selector.getList(InlinerOpt);
+  NodeList regAllocList = selector.getList(RegAllocOpt);
+
+  ASSERT_EQ(licmOpt.size(), 1);
+  ASSERT_EQ(inlinerList.size(), 1);
+  ASSERT_EQ(regAllocList.size(), 1);
+}
+
+TEST(ICNodeSelector, bestListEmpty) {
+  NodeSelector selector;
+  ICOptimization best = selector.bestOptim();
+
+  ASSERT_EQ(best, ErrOpt);
+}
+
+TEST(ICNodeSelector, bestList) {
+  NodeSelector selector;
+
+  DecisionTreeNode *n1 = new DecisionTreeNode;
+  DecisionTreeNode *n2 = new DecisionTreeNode;
+  DecisionTreeNode *n3 = new DecisionTreeNode;
+
+  n1->Optimization = LicmOpt;
+  n1->Fitness = 300;
+  n1->Priority = 500;
+
+  n2->Optimization = RegAllocOpt;
+  n2->Fitness = 500;
+  n2->Priority = 500;
+
+  n3->Optimization = InlinerOpt;
+  n3->Fitness = 500;
+  n3->Priority = 500;
+
+  selector.add(n1);
+  selector.add(n2);
+  selector.add(n3);
+
+  ASSERT_EQ(selector.bestOptim(), LicmOpt);
+}
+
+TEST(ICNodeSelector, selectNodeEmpty) {
+  NodeSelector selector;
+  DecisionTreeNode *n = selector.selectNode();
+
+  ASSERT_TRUE(n == NULL);
+}
+
+TEST(ICNodeSelector, selectNodeOneOptim) {
+  NodeSelector selector;
+  DecisionTreeNode *n = new DecisionTreeNode();
+
+  n->Optimization = LicmOpt;
+  n->Fitness = 100;
+  n->Priority = 500;
+
+  selector.add(n);
+
+  DecisionTreeNode *selectedNode = selector.selectNode();
+
+  ASSERT_FALSE(selectedNode == NULL);
+  ASSERT_TRUE(selectedNode == n);
+}
+
+TEST(ICNodeSelector, usedOptimsOnlyOne) {
+  NodeSelector selector;
+  DecisionTreeNode *n1 = new DecisionTreeNode();
+  DecisionTreeNode *n2 = new DecisionTreeNode();
+  DecisionTreeNode *s1 = NULL, *s2 = NULL;
+
+  n1->Optimization = LicmOpt;
+  n1->Fitness = 100;
+  n1->Priority = 100;
+  selector.add(n1);
+  s1 = selector.selectNode();
+  ASSERT_FALSE(s1 == NULL);
+  ASSERT_TRUE(s1 == n1);
+  ASSERT_EQ(selector.getList(LicmOpt).size(), 0);
+
+  n2->Optimization = LicmOpt;
+  n2->Fitness = 100;
+  n2->Priority = 100;
+  selector.add(n2);
+  s2 = selector.selectNode();
+
+  ASSERT_FALSE(s2 == NULL);
+  ASSERT_TRUE(s2 == n2);
+}
+
+TEST(ICNodeSelector, usedOptimsSwapTwo) {
+  NodeSelector selector;
+  DecisionTreeNode *n1 = new DecisionTreeNode;
+  DecisionTreeNode *n2 = new DecisionTreeNode;
+  DecisionTreeNode *s1, *s2, *s3;
+  s1 = s2 = s3 = NULL;
+
+  n1->Optimization = LicmOpt;
+  n1->Priority = 500;
+  n1->Fitness = 500;
+
+  n2->Optimization = InlinerOpt;
+  n2->Priority = 500;
+  n2->Fitness = 600;
+
+  selector.add(n1);
+  selector.add(n2);
+  s1 = selector.selectNode();
+
+  selector.add(n1);
+  selector.add(n2);
+  s2 = selector.selectNode();
+
+  selector.add(n1);
+  selector.add(n2);
+  s3 = selector.selectNode();
+
+  ASSERT_FALSE(s1 == NULL);
+  ASSERT_FALSE(s2 == NULL);
+  ASSERT_FALSE(s3 == NULL);
+
+  ASSERT_EQ(LicmOpt, s1->Optimization);
+  ASSERT_EQ(InlinerOpt, s2->Optimization);
+  ASSERT_EQ(LicmOpt, s3->Optimization);
+}
+
+TEST(ICNodeList, addNode) {
+  NodeList list;
+  DecisionTreeNode *node = new DecisionTreeNode;
+
+  list.add(node);
+
+  ASSERT_EQ(list.size(), 1);
+}
+
+TEST(ICNodeList, addSameFitness) {
+  NodeList list;
+  DecisionTreeNode *n1 = new DecisionTreeNode;
+  n1->Fitness = 100;
+
+  DecisionTreeNode *n2 = new DecisionTreeNode;
+  n2->Fitness = 100;
+
+  list.add(n1);
+  list.add(n2);
+
+  ASSERT_EQ(list.size(), 2);
+}
+
+TEST(ICNodeList, addBetterFitness) {
+  NodeList list;
+
+  ASSERT_EQ(list.size(), 0);
+
+  DecisionTreeNode *n1 = new DecisionTreeNode;
+  DecisionTreeNode *n2 = new DecisionTreeNode;
+  DecisionTreeNode *n3 = new DecisionTreeNode;
+
+  n1->Fitness = 300;
+  list.add(n1);
+  ASSERT_EQ(list.size(), 1);
+
+  n2->Fitness = 200;
+  list.add(n2);
+  ASSERT_EQ(list.size(), 1);
+
+  n3->Fitness = 200;
+  list.add(n3);
+  ASSERT_EQ(list.size(), 2);
+}
+
+TEST(ICNodeList, addWorseFitness) {
+  NodeList list;
+  DecisionTreeNode *n1 = new DecisionTreeNode;
+  DecisionTreeNode *n2 = new DecisionTreeNode;
+  DecisionTreeNode *n3 = new DecisionTreeNode;
+
+  n1->Fitness = 200;
+  n2->Fitness = 200;
+  n3->Fitness = 300;
+
+  list.add(n1);
+  list.add(n2);
+  list.add(n3);
+
+  ASSERT_EQ(list.size(), 2);
+}
+
+TEST(ICNodeList, addBetterPrioritySameFitness) {
+  NodeList list;
+  DecisionTreeNode *n1 = new DecisionTreeNode;
+  DecisionTreeNode *n2 = new DecisionTreeNode;
+
+  n1->Fitness = 100;
+  n2->Fitness = 100;
+
+  n1->Priority = 500;
+  n2->Priority = 600;
+
+  list.add(n1);
+  list.add(n2);
+
+  ASSERT_EQ(list.size(), 1);
+}
+
+TEST(ICNodeList, addWorsePrioritySameFitness) {
+  NodeList list;
+  DecisionTreeNode *n1 = new DecisionTreeNode;
+  DecisionTreeNode *n2 = new DecisionTreeNode;
+
+  n1->Fitness = 100;
+  n1->Priority = 200;
+
+  n2->Fitness = 100;
+  n2->Priority = 100;
+
+  list.add(n1);
+  list.add(n2);
+
+  ASSERT_EQ(list.size(), 1);
+}
+
+TEST(ICNodeList, clearList) {
+  NodeList list;
+  DecisionTreeNode *n1 = new DecisionTreeNode;
+  DecisionTreeNode *n2 = new DecisionTreeNode;
+
+  list.add(n1);
+  ASSERT_EQ(list.size(), 1);
+
+  list.clear();
+  ASSERT_EQ(list.size(), 0);
+
+  list.add(n2);
+  ASSERT_EQ(list.size(), 1);
+}
+
+
+TEST(ICDecisionTreeNode, NodeCompareEqual) {
+  DecisionTreeNode n1, n2, n3;
+
+  n1.Fitness = 100;
+  n1.Priority = 100;
+
+  n2.Fitness = 100;
+  n2.Priority = 100;
+
+  n3.Fitness = 100;
+  n3.Priority = 200;
+
+  ASSERT_EQ(n1, n2);
+  ASSERT_FALSE(n1 == n3);
+
+  ASSERT_NE(n1, n3);
+  ASSERT_FALSE(n1 != n2);
+}
+
+TEST(ICDecisionTreeNode, NodeCompareGreater) {
+  DecisionTreeNode n1, n2, n3, n4, n5;
+
+  n1.Fitness = 100;
+  n1.Priority = 500;
+
+  n2.Fitness = 200;
+  n2.Priority = 500;
+
+  n3.Fitness = 100;
+  n3.Priority = 500;
+
+  n4.Fitness = 50;
+  n4.Priority = 500;
+
+  n5.Fitness = 100;
+  n5.Priority = 400;
+
+  ASSERT_TRUE(n1 > n2);
+  ASSERT_FALSE(n1 > n3);
+  ASSERT_FALSE(n1 > n4);
+  ASSERT_TRUE(n1 > n5);
+}
+
+TEST(ICDecisionTreeNode, NodeCompareLess) {
+  DecisionTreeNode n1, n2;
+
+  n1.Optimization = LicmOpt;
+  n1.Fitness = 300;
+  n1.Priority = 500;
+
+  n2.Optimization = RegAllocOpt;
+  n2.Fitness = 500;
+  n2.Priority = 500;
+
+  ASSERT_TRUE(n2 < n1);
+}
+
+
+}
+}

unittests/Analysis/ICParallel.cpp

+#include "gtest/gtest.h"
+#include "llvm/Analysis/IterativeCompilation.h"
+
+namespace llvm {
+namespace {
+
+// Scenario 0:
+// ---------------
+// Set module phase
+// getDecision
+// assert that node is added
+// getDecision
+// assert that node is added
+// setCurrentFunctionAndPhase()
+// assert that tree has changed
+// getDecision()
+// assert that node is added
+// getDecision()
+// assert that node is added
+TEST(ICParallel, TestProxyCreation) {
+  ModuleDecisionTreeProxies MDTP;
+  MDTP.setIterativeCompilation(true);
+  MDTP.setModuleCompilationPhase();
+
+  DecisionTreeProxy &moduleTree = MDTP.getDecisionTreeProxy("module-id",
+      FnNameAndPhase::ModulePhase);
+  ASSERT_EQ(0u, moduleTree.getPriorities().size());
+
+  MDTP.getDecision(100, InlinerOpt);
+  ASSERT_EQ(1u, moduleTree.getPriorities().size());
+
+  MDTP.getDecision(100, InlinerOpt);
+  ASSERT_EQ(2u, moduleTree.getPriorities().size());
+
+  MDTP.setCurrentFunctionAndPhase("f1", FnNameAndPhase::FunctionPhase);
+  DecisionTreeProxy &fnTree = MDTP.getDecisionTreeProxy("f1",
+      FnNameAndPhase::FunctionPhase);
+
+  ASSERT_EQ(0u, fnTree.getPriorities().size());
+
+  MDTP.getDecision(100, LicmOpt);
+  ASSERT_EQ(1u, fnTree.getPriorities().size());
+
+  MDTP.setModuleCompilationPhase();
+  MDTP.getDecision(100, InlinerOpt);
+  ASSERT_EQ(3u, moduleTree.getPriorities().size());
+
+  MDTP.setCurrentFunctionAndPhase("f2", FnNameAndPhase::FunctionPhase);
+  DecisionTreeProxy &fn2Tree = MDTP.getDecisionTreeProxy("f2",
+      FnNameAndPhase::FunctionPhase);
+
+  ASSERT_EQ(0u, fn2Tree.getPriorities().size());
+  MDTP.getDecision(100, LicmOpt);
+
+  ASSERT_EQ(1u, fn2Tree.getPriorities().size());
+}
+
+// Scenario 1:
+// -------------
+// given that MDTP is empty
+// when we select module
+// and we call getDecision()
+// and select current function
+// and call getDecision() few times
+// when we get results
+// then assert that in results there are tree entries we need
+bool compare_results(MdtResults r1, MdtResults r2) {
+  bool res = true;
+
+  res &= r1.FunctionNameAndPhase.getName() == r2.FunctionNameAndPhase.getName();
+  res &= r1.FunctionNameAndPhase.getPhase() == r2.FunctionNameAndPhase.getPhase();
+
+  res &= r1.Fitness == r2.Fitness;
+  res &= r1.Priorities == r2.Priorities;
+  res &= r1.Optimizations == r2.Optimizations;
+
+  return res;
+}
+
+bool results_are_same(std::vector<MdtResults> rv1, std::vector<MdtResults> rv2){
+  if(rv1.size() != rv2.size()) {
+    return false;
+  }
+
+  bool res = true;
+
+  for(unsigned int i = 0; i < rv1.size(); i++) {
+    res &= compare_results(rv1[i], rv2[i]);
+  }
+
+  return res;
+}
+
+TEST(ICParallel, ResultsFiles) {
+  ModuleDecisionTreeProxies MDTP;
+  MDTP.setIterativeCompilation(true);
+
+  MDTP.setModuleCompilationPhase();
+  MDTP.getDecision(10, InlinerOpt);
+
+  MDTP.setCurrentFunctionAndPhase("f1", FnNameAndPhase::FunctionPhase);
+  MDTP.getDecision(100, LicmOpt);
+  MDTP.getDecision(110, LicmOpt);
+  MDTP.getDecision(120, LicmOpt);
+
+  std::vector<MdtResults> oResults;
+  MDTP.getResults(oResults);
+
+  std::string s = MdtResults::generateMdtResultsString(oResults);
+
+  std::string err;
+  std::vector<MdtResults> iResults;
+  MdtResults::parseMdtResults(iResults, s, err);
+
+  ASSERT_TRUE(results_are_same(iResults, oResults));
+}
+
+// Scenario 2:
+// -------------
+// given that MDTP is populated
+// when we get results
+// and load them to module decision trees
+// then assert that needed trees are created
+TEST(ICParallel, LoadParallelResults) {
+  ModuleDecisionTreeProxies MDTP1, MDTP2;
+  MDTP1.setIterativeCompilation(true);
+  MDTP2.setIterativeCompilation(true);
+
+  // IPO phase - global tree
+  MDTP1.setModuleCompilationPhase();
+  MDTP1.getDecision(10, InlinerOpt);
+  MDTP1.getDecision(11, InlinerOpt);
+
+  // function phase - tree per function
+  MDTP1.setCurrentFunctionAndPhase("f1", FnNameAndPhase::FunctionPhase);
+  MDTP1.getDecision(100, LicmOpt);
+  MDTP1.getDecision(110, LicmOpt);
+  MDTP1.getDecision(120, LicmOpt);
+
+  MDTP1.setCurrentFunctionAndPhase("f2", FnNameAndPhase::FunctionPhase);
+  MDTP1.getDecision(100, LicmOpt);
+  MDTP1.getDecision(110, LicmOpt);
+  MDTP1.getDecision(120, LicmOpt);
+
+  // codegen phase - tree per function
+  MDTP2.setCurrentFunctionAndPhase("f1", FnNameAndPhase::CodeGenPhase);
+  MDTP2.getDecision(100, RegAllocOpt);
+  MDTP2.getDecision(110, RegAllocOpt);
+  MDTP2.getDecision(120, RegAllocOpt);
+
+  // this goes into f1 tree, but results 2 (codegen)
+  MDTP2.setCurrentFunctionAndPhase("f2", FnNameAndPhase::CodeGenPhase);
+  MDTP2.getDecision(100, RegAllocOpt);
+  MDTP2.getDecision(110, RegAllocOpt);
+  MDTP2.getDecision(120, RegAllocOpt);
+
+  // fetch results
+  std::vector<MdtResults> results1, results2;
+  std::vector<MdtResults> mergedResults;
+
+  MDTP1.getResults(results1);
+  MDTP2.getResults(results2);
+
+  ASSERT_EQ(3u, results1.size()); // module, and licm for f1 and f2
+  ASSERT_EQ(2u, results2.size()); // just regalloc for f1 and f2
+  // skip conversion to and from file
+
+  MdtResults::mergeMdtResults(mergedResults, results1, results2);
+  ASSERT_EQ(5u, mergedResults.size());
+
+  ModuleDecisionTrees MDT;
+  MDT.applyResults(mergedResults);
+
+  ModuleDecisionTreeProxies MDTP3;
+  MDTP3.setIterativeCompilation(true);
+  MDTP3.setModuleCompilationPhase();
+
+  MDTP3.setModuleCompilationPhase();
+  MDTP3.getDecision(10, InlinerOpt);
+  MDTP3.getDecision(11, InlinerOpt);
+
+  MDTP3.setCurrentFunctionAndPhase("f1", FnNameAndPhase::FunctionPhase);
+  MDTP3.getDecision(100, LicmOpt);
+  MDTP3.getDecision(110, LicmOpt);
+  MDTP3.getDecision(120, LicmOpt);
+
+  MDTP3.setCurrentFunctionAndPhase("f2", FnNameAndPhase::FunctionPhase);
+  MDTP3.getDecision(100, LicmOpt);
+  MDTP3.getDecision(110, LicmOpt);
+  MDTP3.getDecision(120, LicmOpt);
+
+  results1.clear();
+  results2.clear();
+  mergedResults.clear();
+
+  MDTP3.getResults(results1);
+  MdtResults::mergeMdtResults(mergedResults, results1, results2);
+  MDT.applyResults(mergedResults);
+
+  ASSERT_EQ(5u, MDT.getDecisionTrees().size());
+}
+
+// Scenario 3:
+// -----------
+// given that there are more than one decision tree
+// when we call select path with total number of iterations
+// and with current iteration
+// then assert that selected nodes are in LICM if current < total/3
+// and assert that selected nodes are in INLINER if current < 2*total/3
+// and assert that selected nodes are in REGALLOC if current > 2*total/3
+TEST(ICParallel, SelectNode) {
+  ModuleDecisionTreeProxies MDTP1, MDTP2, MDTP3;
+  std::vector<MdtResults> results1, results2, mergedResults;
+  ModuleDecisionTrees MDT(3); // total number of iterations
+  MDT.startNewIteration();
+
+  MDTP1.setIterativeCompilation(true);
+  MDTP2.setIterativeCompilation(true);
+  MDTP3.setIterativeCompilation(true);
+
+  MDTP1.setModuleCompilationPhase();
+  MDTP1.getDecision(20, InlinerOpt);
+  MDTP1.getDecision(15, InlinerOpt);
+
+  MDTP1.setCurrentFunctionAndPhase("f1", FnNameAndPhase::FunctionPhase);
+  MDTP1.getDecision(100, LicmOpt);
+  MDTP1.getDecision(250, LicmOpt);
+  MDTP1.getDecision(150, LicmOpt);
+
+  MDTP2.setCurrentFunctionAndPhase("f1", FnNameAndPhase::CodeGenPhase);
+  MDTP2.getDecision(500, RegAllocOpt);
+  MDTP2.getDecision(610, RegAllocOpt);
+  MDTP2.getDecision(520, RegAllocOpt);
+
+  MDTP1.getResults(results1);
+  MDTP2.getResults(results2);
+  MdtResults::mergeMdtResults(mergedResults, results1, results2);
+
+  MDT.applyResults(mergedResults);
+  MDT.updateBestFunctionFitness(0);
+  MDT.selectPath(false);
+
+  FnNameAndPhase codegenPhase("f1", FnNameAndPhase::CodeGenPhase);
+  FnNameAndPhase precodegenPhase("f1", FnNameAndPhase::FunctionPhase);
+  FnNameAndPhase modulePhase("module-id", FnNameAndPhase::ModulePhase);
+
+  DecisionTree &precodegenDT = MDT.getDecisionTree(precodegenPhase);
+  DecisionTree &moduleDT = MDT.getDecisionTree(modulePhase);
+  DecisionTree &codegenDT = MDT.getDecisionTree(codegenPhase);
+
+  ASSERT_EQ(2u, precodegenDT.getPath().size());
+  ASSERT_EQ(0u, moduleDT.getPath().size());
+  ASSERT_EQ(0u, codegenDT.getPath().size());
+
+  ICPathsMap paths;
+  ICPathsMap pathsBeforeCodegen;
+  ICPathsMap pathsAfterCodegen;
+
+  MDT.getPaths(paths);
+  MDT.splitPathsMap(paths, pathsBeforeCodegen, pathsAfterCodegen);
+  MDTP3.setPaths(pathsBeforeCodegen);
+
+  MDT.startNewIteration();
+  // MDT.selectPath(false);
+  // std::cout << paths.size() << std::endl;
+
+  // DecisionTree &dt = MDT.getDecisionTree(FnNameAndPhase("f1", FnNameAndPhase::FunctionPhase));
+  // std::cout << "node count: " << dt.getNodeIdCount() << std::endl;
+  // dt.selectPath(false);
+  // BitVector path = dt.getPath();
+  //
+  // std::cout << BitVector2Str(path) << std::endl;
+
+  // load results into proxy - setPaths()
+  //
+  // set iterative comp on MDTP3
+  // set total iterations
+  // start new iteration
+  // select node
+  // create new proxies
+  // get and apply results again
+  // start new iteration
+  // select node
+  FAIL() << "in progress";
+}
+
+// Scenario 4:
+// ------------
+// given that there are more than one decision tree
+// when we go through all of iterations for an optimization point
+// then assert that after that we always return the best, and not the last path
+// for every tree of that optimization point
+TEST(ICParallel, ReturnBestTree) {
+  FAIL() << "finish this test";
+}
+
+// Scenario 5:
+// ------------
+// Merge parallel trees and do we need it?
+// Is applyResults() enough?
+TEST(ICParallel, MergeResults) {
+  FAIL() << "finish this test";
+}
+
+}
+}

unittests/Analysis/ICProxies.cpp

+#include "gtest/gtest.h"
+#include "llvm/Analysis/ICProxies.h"
+#include <string>
+#include <sstream>
+#include <map>
+#include "llvm/ADT/BitVector.h"
+#include <iostream>
+
+namespace llvm {
+namespace {
+
+void addNode(DecisionTree &dt, int priority) {
+  static int nodeIdCtr = 1;
+  DecisionTreeNode *newNode;
+
+  newNode = new DecisionTreeNode;
+  newNode->NodeId = nodeIdCtr++;
+  newNode->Fitness = 0;
+  newNode->Priority = priority;
+  newNode->Optimization = LicmOpt;
+  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(0u, mdt.getPriorities().size());
+  ASSERT_EQ(0u, mdt.getOptimizations().size());
+
+  ASSERT_FALSE(mdt.getDecision(500, LicmOpt));
+
+  ASSERT_EQ(1u, mdt.getPriorities().size());
+  ASSERT_EQ(1u, mdt.getOptimizations().size());
+
+  ASSERT_EQ(500, mdt.getPriorities()[0]);
+  ASSERT_EQ(LicmOpt, mdt.getOptimizations()[0]);
+}
+
+}
+}

unittests/Analysis/ICUtils.cpp

+#include "gtest/gtest.h"
+#include "llvm/Analysis/ICProxies.h"
+#include "llvm/ADT/BitVector.h"
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <map>
+
+namespace llvm {
+namespace {
+
+// fixtures
+MdtResults* createModuleResults(std::string moduleName, int prio) {
+  MdtResults *moduleResults = new MdtResults;
+
+  moduleResults->FunctionNameAndPhase =
+    FnNameAndPhase(moduleName, FnNameAndPhase::ModulePhase);
+
+  moduleResults->Optimizations.push_back(InlinerOpt);
+  moduleResults->Optimizations.push_back(InlinerOpt);
+  moduleResults->Optimizations.push_back(InlinerOpt);
+
+  moduleResults->Priorities.push_back(100+prio);
+  moduleResults->Priorities.push_back(200+prio);
+  moduleResults->Priorities.push_back(300+prio);
+
+  return moduleResults;
+}
+
+MdtResults* createFnResults(std::string fnName, int prio) {
+  MdtResults *fnResults = new MdtResults;
+
+  fnResults->FunctionNameAndPhase =
+    FnNameAndPhase(fnName, FnNameAndPhase::FunctionPhase);
+
+  fnResults->Optimizations.push_back(LicmOpt);
+  fnResults->Optimizations.push_back(LicmOpt);
+  fnResults->Optimizations.push_back(LicmOpt);
+
+  fnResults->Priorities.push_back(100+prio);
+  fnResults->Priorities.push_back(200+prio);
+  fnResults->Priorities.push_back(300+prio);
+
+  return fnResults;
+}
+
+// Parsers and generators
+
+TEST(ICUtils, PathToString)
+{
+  std::string moduleNameId = "module-id";
+  FnNameAndPhase nameAndPhase = FnNameAndPhase(moduleNameId,
+                                  FnNameAndPhase::ModulePhase);
+
+  BitVector path(4, false);
+  path.resize(path.size()+1, true);
+
+  std::string result = Path2Str(nameAndPhase, path);
+
+  std::stringstream target;
+  target << "  {\n";
+  target << "    \"Fn\":\"module-id\",\n";
+  target << "    \"Phase\":1,\n";
+  target << "    \"Path\":\"00001\"\n";
+  target << "  }";
+
+  ASSERT_STREQ(target.str().c_str(), result.c_str());
+}
+
+
+// TEST(ICUtils, MdtResultsParseMdtResults) {
+// // needs refactoring
+// // write this test first and develop helper methods
+// // by TDD principles
+// }
+//
+// TEST(ICUtils, MdtResultsGenerateMdtResultsString) {
+// }
+//
+// TEST(ICUtils, ICPathsMapParseMdtPaths) {
+// }
+//
+// TEST(ICUtils, ICPathsMapGenerateMdtPaths) {
+// }
+//
+// TEST(ICUtils, ICPathsMapPath2Str) {
+// }
+//
+// TEST(ICUtils, ICPathsMapBitVector2Str) {
+// }
+
+// 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(6u, 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());
+}
+
+
+}
+}