Add framework for iterative compilation to llvm

[Radovan.Obradovic]

Summary

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

[Radovan.Obradovic]

This is a follow-up work on the iterative compilation framework
for clang/llvm. Previous 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

In this patch, the decision tree proxies are implemented as immutable
pass (as suggested by Hongbin Zheng) in order to avoid changes of
the base llvm classes. There is a new function level pass (ICSetCurrentFunc)
that sets the current function decision tree proxy. Because
immutable passes are destructed before the codegen phase, we
are saving the results in the two files: one before codegen
and the other after the codegen phase.

We plan to apply the proposed framework to the new
compiler phases. Also, machine learning can be used to better
make the initial decisions and the model for the good decisions
can be learned by the iterative compilation. Static
performance analyser (for example one suggested by Andrew Trick)
should be integrated / developed as the objective function that
is minimized.

This patch needs to be applied along with the corresponding patch for
clang. See below for the link.

All suggestions, comments are welcomed.

[Radovan.Obradovic]

Patch for clang is available at: http://reviews.llvm.org/D4724.

[grosser]

I took a brief first look to understand what is happening here.

I am a little surprised that there is not a _single_ comment added in this patch. I believe a couple of comments that document higher level design choices would be very helpful. I looked through the older emails, but some questions are still open:

What exactly forms the decision tree? If we have three points at which decisions are taken, will we have three nodes in the tree or depends the size of the tree on the module/program size?

What happens if a decision is reached multiple times? E.g. the inliner run on different functions? Can different decisions be taken at each point?

Similarly, is the decision tree statically known or can it change dynamically depending on what kind of decisions have been taken. E.g. if we decide to run dead code elimination, we may not even have code that could be unrolled such that the corresponding unroller decision points may become invalid?

Do you plan to support non-binary decisions. E.g. different unroll factors?

How does all this fit together. Assuming I would like to run this in a JIT compiler, what are the pieces that need to be plugged together to try to iteratively optimize a certain function?

I also have a couple of stylistic comments:

include/llvm/Analysis/DecisionTree.h

18

Maybe LLVM_ANALYSIS_DECISIONTREE_H?

lib/Analysis/DecisionTree.cpp

44

How has this value be choosen? Does it always need to be in sync with BestFunctionFitness?

157

Write:

} else {

207

Typo: applyResults, no?

379

C++11 range loops maybe?

lib/Target/Mips/MipsFunctionFitness.cpp

47

Why is this commented out? (The same for the lines above)

73

We commonly start variable names with upper-case letters.

[etherzhhb]

Looks like you need to add some comments to your code :)

include/llvm/Analysis/DecisionTree.h

45

You could use llvm::Bitvector instead of std::vector<bool>.

105

Please briefly explain all these Phases.

159

Maybe you could clarify your code by adding comments like:
"This ImmutablePass provides a persistent place to hold the decision trees (for each functions) during the iterative compilation process ..."

187

Now you have "nameFunction" for the name of the current function and "CurrFnDecisionTreeProxy" for the DecisionTree of the current function. How about add a pointer to Function to DecisionTreeProxy so that you can always access the current function (as well as its name) when you have a pointer to the current DecisionTree.

Then you can remobe "nameFunction".

You my also need a hook to notify the DecisionTree when the function inlining pass inline and delete a function.

lib/Analysis/DecisionTree.cpp

38

Maybe you could use a constant (like MaxDtPriority) here instead of a magic number.

91

Looks like this line of code appears in both branches, you could move it above the "if" statement.

104

In this function you are creating a vector in a function and return it at the end, such an approach need to copy the vector when the function return.

You could ask the caller of this function to pass in an empty vector by reference then fill the vector, such that the signature of this function become:
void DecisionTree::findPath(DecisionTreeNode *node, std::vector<bool> &path) {
...
}

255

How about use LLVM's streams instead of ofstream?

Maybe you could write your data out in form of JSON, such that you could write python utilities to analyze/debug/render your data. And it is much more human readable.

lib/Transforms/IPO/Inliner.cpp

450

This "" looks confusing.

[Radovan.Obradovic]

In D4723#7, @grosser wrote:

I am a little surprised that there is not a _single_ comment added in this patch. I believe a couple of comments that document higher level design choices would be very helpful.

Agreed. Will do.

I looked through the older emails, but some questions are still open:

What exactly forms the decision tree? If we have three points at which decisions are taken, will we have three nodes in the tree or depends the size of the tree on the module/program size?

What happens if a decision is reached multiple times? E.g. the inliner run on different functions? Can different decisions be taken at each point?

Similarly, is the decision tree statically known or can it change dynamically depending on what kind of decisions have been taken. E.g. if we decide to run dead code elimination, we may not even have code that could be unrolled such that the corresponding unroller decision points may become invalid?

Do you plan to support non-binary decisions. E.g. different unroll factors?

How does all this fit together. Assuming I would like to run this in a JIT compiler, what are the pieces that need to be plugged together to try to iteratively optimize a certain function?

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.

[Radovan.Obradovic]

include/llvm/Analysis/DecisionTree.h

18

Done

45

Done.

105

Done

159

Thanks! Done

187

"nameFunction" is removed. We are now using ModuleDecisionTreeProxies::setCurrentFunctionAndPhase to find and set decision tree proxy for given function name and compilation phase. So function name and
pointer to the Function do not have to be stored.

lib/Analysis/DecisionTree.cpp

38

Now INT_MAX is used.

44

Now INT_MAX is used.

91

Done

104

Done

157

Done

207

Fixed

255

Now using llvm::MemoryBuffer for reading and raw_ostream for writing. Temp files are now saved in JSON format and parsed by llmv YAML parser.

379

Done

lib/Target/Mips/MipsFunctionFitness.cpp

47

Commented out lines deleted.

73

OK. Done for some variables.

lib/Transforms/IPO/Inliner.cpp

450

Now function ModuleDecisionTreeProxies::setModuleCompilationPhase() is called to set decision tree for the ModulePhase.

[Radovan.Obradovic]

Thank you for the comments. This is the new version of the patch which addresses the comments received.

[petarj]

Any more comments here?

[chandlerc]

The design discussion has stalled and not gone any where so I don't think its useful to review this patch yet.

[Radovan.Obradovic]

• Rebase

This version of patch is rebased to current trunk. Old version can be
found here:

• 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.

• 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.

[dblaikie]

This review did not include llvm-commits as a subscriber, so the review
hasn't been sent to/shared with the list.

Please cancel it and start a new one including the list (adding the list
after the review is created is not a great experience for the list as phab
doesn't resend the intro email with all the details/summary)

[petarj]

In D4723#221695, @dblaikie wrote:

This review did not include llvm-commits as a subscriber, so the review
hasn't been sent to/shared with the list.

I see llvm-commits as one of the subscribers, not sure why the post has not
reached the list.

Please cancel it and start a new one including the list (adding the list
after the review is created is not a great experience for the list as phab
doesn't resend the intro email with all the details/summary)

There is a history of this change here, some questions have been already
asked and answered, I suggest we continue to use it for that sake.

I can resend the summary of the latest patch to the llvm-commit list, if
that would help.

Regards,
Petar

[dsanders]

llvm-commits has definitely been there from the start (see http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20140728/228369.html) but this thread was started in July 2014 and the last significant activity was September 2014. I'd suggest starting a new review and linking to this one.

[petarj]

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

include/llvm/Analysis/DecisionTree.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_DECISIONTREE_H
+#define LLVM_ANALYSIS_DECISIONTREE_H
+
+#include <string>
+#include <vector>
+#include <map>
+#include "llvm/ADT/BitVector.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+
+namespace llvm {
+
+extern cl::opt<bool> IterativeCompilationOpt;
+
+/// Iterative Compilation Optimization
+enum ICOptimization {
+  NoOptimization,
+  InlinerOpt,
+  LicmOpt,
+  RegAllocOpt
+};
+
+const int MaxDtPriority = 1000;
+
+class FnNameAndPhase {
+public:
+
+  /// Iterative Compilation Phase
+  enum ICPhase {
+    FunctionPhase, /// Function level phase include passes that operate
+                   /// with the target independent IR like LICM. In this
+                   /// phase there is one decision tree for each function.
+
+    ModulePhase,   /// Module level phase include interprocedural optimizations
+                   /// like function inliner. In this phase there is only one
+                   /// decision tree for the whole module.
+
+    CodeGenPhase   /// Codegen phase include passes like register allocator,
+                   /// scheduler and instruction selection. In this
+                   /// phase there is also one decision tree for each function.
+  };
+
+  FnNameAndPhase() : Phase(ModulePhase) {}
+  FnNameAndPhase(const FnNameAndPhase &x) : Name(x.Name), Phase(x.Phase)
+    {}
+  FnNameAndPhase(const std::string &name,
+      ICPhase phase) : Name(name), Phase(phase) {}
+
+  bool operator < (const FnNameAndPhase &x) const {
+    if (Phase != x.Phase)
+      return Phase < x.Phase;
+    return Name < x.Name;
+  }
+
+const std::string &getName() const { return Name; }
+ICPhase getPhase() const { return Phase; }
+
+protected:
+  std::string Name;
+  ICPhase Phase;
+};
+
+class MdtResults {
+public:
+  FnNameAndPhase FunctionNameAndPhase;
+  int Fitness;
+  std::vector<int> Priorities;
+  std::vector<ICOptimization> Optimizations;
+};
+
+struct DecisionTreeNode {
+  int calcFinalPriority(int bestFunctionFitness);
+  DecisionTreeNode *Parent;
+  DecisionTreeNode *PrimaryDecision;
+  DecisionTreeNode *AlternativeDecision;
+  int Priority;
+  int Fitness;
+  int Depth;
+  int NodeId;
+  bool IsInterprocedural;
+  ICOptimization Optimization;
+
+  std::string getJSON();
+};
+
+/// Decision tree controls the iterative compilation process so
+/// that compiler takes different path in each compilation except in
+/// the final iteration when the path which generates the best code is taken .
+class DecisionTree {
+private:
+  DecisionTreeNode *DecisionTreeRoot;
+  DecisionTreeNode *CurrentNode;
+  BitVector Path;
+  SmallVector<ICOptimization, 128> Optimizations;
+  int FunctionFitness;
+  int BestFunctionFitness;
+  BitVector BestPath;
+  int NodeIdCount;
+
+public:
+  DecisionTree();
+  ~DecisionTree();
+
+  int getFunctionFitness() const { return FunctionFitness; }
+  void setFunctionFitness(int x) { FunctionFitness = x; }
+  BitVector &getPath() { return Path; }
+  const BitVector &getPath() const { return Path; }
+  SmallVector<ICOptimization, 128> &getOptimizations()
+    { return Optimizations; }
+  const SmallVector<ICOptimization, 128> &getOptimizations()
+    const { return Optimizations; }
+
+  bool getDecision(int priority, ICOptimization opt);
+  void updateBestFunctionFitness(int iteration);
+  void findPath(DecisionTreeNode *node, BitVector &path);
+  bool selectPath(bool FinalPass);
+  void startNewIteration();
+  void updateNodesFitness();
+
+  void applyResults(const MdtResults &results);
+
+  void splitPath(
+    const BitVector &paths,
+    BitVector &pathBeforeCodegen,
+    BitVector &pathAfterCodegen);
+
+  static void writeToFile(const std::string &fileName, const std::string &data);
+  static std::string readFromFile(const std::string &fileName);
+  void dumpToGv(int currentIteration);
+  void dumpToJSON(int currentIteration);
+};
+
+/// 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; }
+
+  bool getDecision(int priority, ICOptimization opt);
+
+  std::string generateResultsString();
+  MdtResults getResults() const;
+  void setPath(const BitVector &path);
+
+protected:
+  BitVector Path;
+  int FunctionFitness;
+  int BestFunctionFitness;
+  std::vector<int> Priorities;
+  std::vector<ICOptimization> Optimizations;
+  int CurrentDepth;
+};
+
+/// This class is the storage for all the decision trees for
+/// each function and compilation phase.
+class ModuleDecisionTrees {
+public:
+
+  ModuleDecisionTrees();
+  ~ModuleDecisionTrees();
+
+  DecisionTree &getDecisionTree(const FnNameAndPhase &fnNameAndPhase);
+
+  void startNewIteration();
+  void getPaths(std::map<FnNameAndPhase, BitVector> &paths);
+  void applyResults(const std::vector<MdtResults> &results);
+  void updateBestFunctionFitness(int iteration);
+  void updateNodesFitness();
+  void selectPath(bool FinalPass);
+  void splitPaths(
+    const std::map<FnNameAndPhase, BitVector> &paths,
+    std::map<FnNameAndPhase, BitVector> &pathBeforeCodegen,
+    std::map<FnNameAndPhase, BitVector> &pathAfterCodegen);
+  std::string &getICInputFile() { return ICInputFile; }
+  std::string &getICInputFile2() { return ICInputFile2; }
+  std::string &getICResultsFile() { return ICResultsFile; }
+  std::string &getICResultsFile2() { return ICResultsFile2; }
+  std::string &getICInputFileOpt() { return ICInputFileOpt; }
+  std::string &getICInputFile2Opt() { return ICInputFile2Opt; }
+  std::string &getICResultsFileOpt() { return ICResultsFileOpt; }
+  std::string &getICResultsFile2Opt() { return ICResultsFile2Opt; }
+
+protected:
+  std::map<FnNameAndPhase, DecisionTree *> DecisionTrees;
+  std::string ICInputFile;
+  std::string ICInputFile2;
+  std::string ICResultsFile;
+  std::string ICResultsFile2;
+  std::string ICInputFileOpt;
+  std::string ICInputFile2Opt;
+  std::string ICResultsFileOpt;
+  std::string ICResultsFile2Opt;
+
+public:
+  static bool parseMdtPaths(
+      std::map<FnNameAndPhase, BitVector> &paths,
+      const std::string &pathString,
+      std::string &ErrorMessage);
+  static std::string generateMdtPathsString(
+      const std::map<FnNameAndPhase, BitVector> &paths);
+  static bool parseMdtResults(std::vector<MdtResults> &results,
+                              const std::string &resString,
+                              std::string &ErrorMessage);
+  static std::string generateMdtResultsString(
+      const std::vector<MdtResults> &results);
+
+  static int calculateTotalFitness(const std::vector<MdtResults> &results);
+  static void mergeMdtResults(std::vector<MdtResults> &mergedResults,
+                              const std::vector<MdtResults> &results1,
+                              const std::vector<MdtResults> &results2);
+};
+
+/// This ImmutablePass provides a persistent place to hold the
+/// decision trees proxies (for each function and for each
+/// compilation phase) during the iterative compilation process so
+/// they can be easily accessed from passes which can take advantage
+/// of iterative compilation.
+class ModuleDecisionTreeProxies : public ImmutablePass {
+public:
+  static char ID;
+
+  ModuleDecisionTreeProxies();
+  ~ModuleDecisionTreeProxies();
+  virtual bool doInitialization(Module &M);
+  virtual bool doFinalization(Module &M);
+
+  bool getDecision(int priority, ICOptimization opt);
+
+  void setCurrentFunctionAndPhase(const std::string &fnName,
+    FnNameAndPhase::ICPhase phase);
+  void setModuleCompilationPhase();
+  DecisionTreeProxy &getDecisionTreeProxy(const FnNameAndPhase &x);
+  DecisionTreeProxy &getDecisionTreeProxy(const std::string &name,
+    FnNameAndPhase::ICPhase phase);
+  void setPaths(std::map<FnNameAndPhase, BitVector> &paths);
+  void getResults(std::vector<MdtResults> &results) const;
+  DecisionTreeProxy *getCurrFnDecisionTreeProxy()
+  { return CurrFnDecisionTreeProxy; }
+  bool getIterativeCompilation() { return IterativeCompilation; }
+  void setIterativeCompilation(bool x) { IterativeCompilation = x; }
+protected:
+  bool IterativeCompilation;
+  std::map<FnNameAndPhase, DecisionTreeProxy *> DecisionTreeProxies;
+  DecisionTreeProxy *CurrFnDecisionTreeProxy;
+  FnNameAndPhase::ICPhase ICPhase;
+};
+
+}
+
+#endif

include/llvm/Analysis/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/DecisionTree.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/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 initializeRewriteSymbolsPass(PassRegistry&);
 void initializeWinEHPreparePass(PassRegistry&);
 void initializePlaceBackedgeSafepointsImplPass(PassRegistry&);
 void initializePlaceSafepointsPass(PassRegistry&);
 void initializeDwarfEHPreparePass(PassRegistry&);
 void initializeFloat2IntPass(PassRegistry&);
 void initializeLoopDistributePass(PassRegistry&);
 void initializeSjLjEHPreparePass(PassRegistry&);
+void initializeModuleDecisionTreeProxiesPass(PassRegistry&);
+void initializeFunctionFitnessPass(PassRegistry&);
+void initializeICSetCurrentFuncPass(PassRegistry&);
 }
 
 #endif

include/llvm/Transforms/IPO/InlinerPass.h

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

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

include/llvm/Transforms/Utils/LoopUtils.h

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

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

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeScalarEvolutionPass(Registry);
   initializeScalarEvolutionAliasAnalysisPass(Registry);
   initializeTargetTransformInfoWrapperPassPass(Registry);
   initializeTypeBasedAliasAnalysisPass(Registry);
   initializeScopedNoAliasAAPass(Registry);
+  initializeModuleDecisionTreeProxiesPass(Registry);
+  initializeICSetCurrentFuncPass(Registry);
 }
 
 void LLVMInitializeAnalysis(LLVMPassRegistryRef R) {
   initializeAnalysis(*unwrap(R));
 }
 
 LLVMBool LLVMVerifyModule(LLVMModuleRef M, LLVMVerifierFailureAction Action,
                           char **OutMessages) {

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   CFG.cpp
   CFGPrinter.cpp
   CFLAliasAnalysis.cpp
   CGSCCPassManager.cpp
   CaptureTracking.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
+  DecisionTree.cpp
   Delinearization.cpp
   DependenceAnalysis.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DominanceFrontier.cpp
+  ICSetCurrentFunc.cpp
   IVUsers.cpp
   InstCount.cpp
   InstructionSimplify.cpp
   Interval.cpp
   IntervalPartition.cpp
   IteratedDominanceFrontier.cpp
   LazyCallGraph.cpp
   LazyValueInfo.cpp

lib/Analysis/DecisionTree.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/DecisionTree.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;
+
+cl::opt<bool>
+llvm::IterativeCompilationOpt("fiterative-comp", cl::init(false),
+                     cl::desc("Enable iterative compilation"));
+static cl::opt<std::string>
+FicInputFile("fic-input-file", cl::init("ic-input"));
+static cl::opt<std::string>
+FicInputFile2("fic-input2-file", cl::init("ic-input2"));
+static cl::opt<std::string>
+FicResultsFile("fic-results-file", cl::init("ic-results"));
+static cl::opt<std::string>
+FicResultsFile2("fic-results2-file", cl::init("ic-results2"));
+
+DecisionTree::DecisionTree() {
+  DecisionTreeRoot = new DecisionTreeNode;
+  NodeIdCount = 0;
+  FunctionFitness = 0;
+  BestFunctionFitness = INT_MAX;
+  CurrentNode = DecisionTreeRoot;
+  CurrentNode->Parent = 0;
+  CurrentNode->PrimaryDecision = 0;
+  CurrentNode->AlternativeDecision = 0;
+  CurrentNode->Priority = 0;
+  CurrentNode->Fitness = INT_MAX;
+  CurrentNode->Depth = 0;
+  CurrentNode->NodeId = NodeIdCount++;
+  CurrentNode->IsInterprocedural = false;
+}
+
+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;
+      }
+    }
+  }
+
+  // Create the new decision tree node.
+  if(opt != NoOptimization) {
+    CurrentNode->Priority = priority;
+    CurrentNode->Optimization = opt;
+  }
+  DecisionTreeNode *newNode = new DecisionTreeNode;
+  newNode->Parent = CurrentNode;
+  newNode->PrimaryDecision = 0;
+  newNode->AlternativeDecision = 0;
+  newNode->Priority = 0;
+  newNode->Optimization = NoOptimization;
+  newNode->Fitness = INT_MAX;
+  newNode->Depth = depth + 1;
+  newNode->NodeId = NodeIdCount++;
+  newNode->IsInterprocedural = false;
+
+  // Insert the new node in the decision tree.
+  if (CurrentNode->PrimaryDecision == 0) {
+    CurrentNode->PrimaryDecision = newNode;
+    decision = false;
+  } else {
+    CurrentNode->AlternativeDecision = newNode;
+    decision = true;
+  }
+  CurrentNode = newNode;
+
+  return decision;
+}
+
+/// Updated best function fitness seen so far.
+void DecisionTree::updateBestFunctionFitness(int iteration) {
+  if (FunctionFitness < BestFunctionFitness) {
+    BestFunctionFitness = FunctionFitness;
+    findPath(CurrentNode, BestPath);
+  }
+  updateNodesFitness();
+}
+
+/// Find path which leads to the given node.
+void DecisionTree::findPath(DecisionTreeNode *node, BitVector &path) {
+  path.resize(node->Depth);
+  if (node->PrimaryDecision)
+    path.resize(node->Depth + 1, true);
+  while (node != DecisionTreeRoot) {
+    DecisionTreeNode *parent = node->Parent;
+    if (node == parent->AlternativeDecision)
+      path[parent->Depth] = true;
+    else
+      path[parent->Depth] = false;
+    node = parent;
+  }
+}
+
+/// Select path for the new iteration. In the final iteration use
+/// the best path so far.
+bool DecisionTree::selectPath(bool FinalPass) {
+  if (FinalPass) {
+    Path = BestPath;
+    return true;
+  }
+
+  SmallVector<DecisionTreeNode *, 64> nodesToExplore;
+  int selectedNodePriority = 0;
+  DecisionTreeNode *selectedNode = 0;
+
+  if (!DecisionTreeRoot->AlternativeDecision
+        && !DecisionTreeRoot->PrimaryDecision)
+    selectedNode = DecisionTreeRoot;
+
+  nodesToExplore.push_back(DecisionTreeRoot);
+  while(!nodesToExplore.empty()) {
+    DecisionTreeNode *n = nodesToExplore.back();
+    nodesToExplore.pop_back();
+    if (n->AlternativeDecision == 0 && n->PrimaryDecision != 0) {
+      double priority = n->calcFinalPriority (BestFunctionFitness);
+      if (priority > selectedNodePriority) {
+        selectedNode = n;
+        selectedNodePriority = priority;
+      }
+    }
+    if (n->AlternativeDecision)
+      nodesToExplore.push_back(n->AlternativeDecision);
+    if (n->PrimaryDecision)
+      nodesToExplore.push_back(n->PrimaryDecision);
+  }
+
+  if (selectedNode) {
+    findPath(selectedNode, Path);
+    return false;
+  } else {
+    Path = BestPath;
+    return true;
+  }
+}
+
+/// 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() {
+  BitVector path;
+  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 (Priority * bestFunctionFitness) / Fitness;
+}
+
+/// Apply results from the decision tree proxy so that the
+/// path for the next iteration can be selected.
+void DecisionTree::applyResults(const MdtResults &results) {
+  unsigned pathLen = Path.size();
+  int nOptimizations = (int)results.Optimizations.size();
+  unsigned nPriorities = results.Priorities.size();
+
+// TODO add some comments
+  for (unsigned i = 0; i < pathLen; i++)
+    getDecision(0, NoOptimization);
+
+  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;
+    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;
+}
+
+/// Write contents of the string to the file.
+void DecisionTree::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 DecisionTree::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();
+}
+
+void DecisionTree::dumpToGv(int currentIteration) {
+  DecisionTreeNode *n;
+  SmallVector<DecisionTreeNode*, 64> paths;
+
+  std::stringstream path;
+  path << "/tmp/ic-tree-" << currentIteration << ".gv";
+
+  std::ofstream f(path.str());
+
+  f << "digraph G {\n";
+
+  paths.push_back(DecisionTreeRoot);
+  while(!paths.empty())
+  {
+    n = paths.back();
+    paths.pop_back();
+
+
+    while(n->PrimaryDecision) {
+      f << "n" << n->NodeId << " -> " << "n" << n->PrimaryDecision->NodeId << ";\n";
+
+      if(n->AlternativeDecision)
+      {
+        paths.push_back(n->AlternativeDecision);
+        f << "n" << n->NodeId << " -> " << "n" << n->AlternativeDecision->NodeId
+          << "[weight=0];\n";
+      }
+      n = n->PrimaryDecision;
+    }
+  }
+
+  f << "}";
+  f.close();
+}
+std::string DecisionTreeNode::getJSON() {
+  std::stringstream res;
+
+  res << "{";
+  res << " \"id\" : " << NodeId   << ",";
+  res << " \"priority\" : " << Priority << ",";
+  res << " \"fitness\" : " << Fitness  << ",";
+  res << " \"depth\" : " << Depth    << ",";
+  res << " \"optim\" : " << Optimization;
+  res << "}";
+
+  return res.str();
+}
+
+void DecisionTree::dumpToJSON(int currentIteration) {
+  DecisionTreeNode *n;
+  SmallVector<DecisionTreeNode*, 64> paths;
+
+  std::stringstream filePath;
+  filePath << "/tmp/ic-tree-" << currentIteration << ".json";
+
+  std::ofstream f(filePath.str());
+
+  f << "[\n";
+
+  paths.push_back(DecisionTreeRoot);
+  while(!paths.empty())
+  {
+    // this is path root
+    // start new path
+    n = paths.back();
+
+    if(n->Parent)
+      f << "\n\t{\n\t\"root\" : " << n->Parent->getJSON() << ",";
+    else
+      f << "\n\t{\n\t\"root\" : " << n->getJSON() << ",";
+
+    f << "\n\t\"path\" : [\n";
+
+    paths.pop_back();
+
+
+
+    while(n->PrimaryDecision || n->AlternativeDecision) {
+
+      if(n->AlternativeDecision) {
+        // save new path entry point for later
+        paths.push_back(n->AlternativeDecision);
+      }
+
+      if(n->PrimaryDecision) {
+        // we have regular primary decision,
+        // write it and continue
+        // get node as JSON and append it to current path
+        f << "\t\t" << n->getJSON();
+        n = n->PrimaryDecision;
+      }
+
+      if(n->PrimaryDecision)
+        f << ",\n";
+      else
+        f << "\n";
+
+    }
+
+
+    if(!paths.empty())
+      f << "\t]},\n";
+    else
+      f << "\t]}\n";
+  }
+
+  f << "]";
+  f.close();
+}
+
+DecisionTreeProxy::DecisionTreeProxy()
+  : FunctionFitness(0), BestFunctionFitness(INT_MAX), CurrentDepth(0) {}
+
+/// This function is called by ModuleDecisionTreeProxies::getDecision
+/// to obtain decision at some compilation point.
+bool DecisionTreeProxy::getDecision(int priority, ICOptimization opt) {
+  if (CurrentDepth < (int)Path.size()) {
+    bool r = Path[CurrentDepth];
+    CurrentDepth++;
+    return r;
+  }
+  Priorities.push_back(priority);
+  Optimizations.push_back(opt);
+  CurrentDepth++;
+  return false;
+}
+
+MdtResults DecisionTreeProxy::getResults() const {
+  MdtResults results;
+  results.Priorities = Priorities;
+  results.Optimizations = Optimizations;
+  results.Fitness = FunctionFitness;
+  return results;
+}
+
+void DecisionTreeProxy::setPath(const BitVector &path) {
+  Path = path;
+}
+
+ModuleDecisionTrees::ModuleDecisionTrees()
+{}
+
+ModuleDecisionTrees::~ModuleDecisionTrees() {
+  for (auto &P : DecisionTrees) {
+    DecisionTree *dt = P.second;
+    delete dt;
+  }
+}
+
+/// Find required decision tree.
+DecisionTree &ModuleDecisionTrees::getDecisionTree(
+    const FnNameAndPhase &fnNameAndPhase) {
+  if (DecisionTrees.find(fnNameAndPhase) == DecisionTrees.end()) {
+    DecisionTrees[fnNameAndPhase] = new DecisionTree();
+  }
+  return *DecisionTrees[fnNameAndPhase];
+}
+
+/// Inform all decision trees that new iteration of compilation
+/// has been started.
+void ModuleDecisionTrees::startNewIteration() {
+  for (auto &P : DecisionTrees) {
+    DecisionTree *dt = P.second;
+    dt->startNewIteration();
+  }
+}
+
+/// Get selected paths for decision trees.
+void ModuleDecisionTrees::getPaths(std::map<FnNameAndPhase,
+                                   BitVector> &paths) {
+  paths.clear();
+  for (const auto &P : DecisionTrees) {
+    const FnNameAndPhase &fnNameAndPhase = P.first;
+    const DecisionTree *dt = P.second;
+    const BitVector &path = dt->getPath();
+    paths[fnNameAndPhase] = path;
+  }
+}
+
+/// Apply results to all decision trees used for a module optimization.
+void ModuleDecisionTrees::applyResults(const std::vector<MdtResults> &results) {
+  for (const auto &R : results) {
+    DecisionTree &DT = getDecisionTree(R.FunctionNameAndPhase);
+    DT.applyResults(R);
+  }
+}
+
+/// Updates best function fitness filed for all decision trees.
+void ModuleDecisionTrees::updateBestFunctionFitness(int Iteration) {
+  for (const auto &P : DecisionTrees) {
+    DecisionTree *DT = P.second;
+    DT->updateBestFunctionFitness(Iteration);
+  }
+}
+
+/// Iterates through all decision trees and calls updateNodesFitness
+/// on them.
+void ModuleDecisionTrees::updateNodesFitness()
+{
+  for (const auto &P : DecisionTrees) {
+    DecisionTree *DT = P.second;
+    DT->updateNodesFitness();
+  }
+}
+
+/// Selects path for all decision trees.
+void ModuleDecisionTrees::selectPath(bool FinalPass)
+{
+  for (const auto &P : DecisionTrees) {
+    DecisionTree *DT = P.second;
+    DT->selectPath(FinalPass);
+  }
+}
+
+void ModuleDecisionTrees::splitPaths(
+    const std::map<FnNameAndPhase, BitVector> &paths,
+    std::map<FnNameAndPhase, BitVector> &pathsBeforeCodegen,
+    std::map<FnNameAndPhase, BitVector> &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;
+  }
+}
+
+/// Parses string containing paths for multiple decision trees in JSON
+/// format using llmv YAML parser.
+bool ModuleDecisionTrees::parseMdtPaths(std::map<FnNameAndPhase,
+                                        BitVector> &paths,
+                                        const std::string &pathString,
+                                        std::string &ErrorMessage) {
+  paths.clear();
+  SourceMgr SM;
+  yaml::Stream YAMLStream(pathString, SM);
+  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;
+  }
+  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;
+    }
+    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;
+      }
+    }
+    if (!Fn) {
+      ErrorMessage = "Missing key: \"Fn\".";
+      return false;
+    }
+    if (!Phase) {
+      ErrorMessage = "Missing key: \"Phase\".";
+      return false;
+    }
+    if (!Path) {
+      ErrorMessage = "Missing key: \"Path\".";
+      return false;
+    }
+    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 ModuleDecisionTrees::generateMdtPathsString(
+    const std::map<FnNameAndPhase, BitVector> &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 << "  {\n";
+    s << "    \"Fn\":\"" << fnNameAndPhase.getName() << "\",\n";
+    s << "    \"Phase\":" << (int)fnNameAndPhase.getPhase() << ",\n";
+    s << "    \"Path\":\"";
+    unsigned j;
+    unsigned m = path.size();
+    for (j = 0; j < m; j++)
+      s << path[j];
+    s << "\"\n";
+    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 ModuleDecisionTrees::parseMdtResults(
+    std::vector<MdtResults> &results,
+    const std::string &resString,
+    std::string &ErrorMessage) {
+  results.clear();
+  SourceMgr SM;
+  yaml::Stream YAMLStream(resString, SM);
+  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;
+  }
+  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;
+    }
+    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;
+    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;
+      }
+    }
+    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;
+    }
+    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 ModuleDecisionTrees::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 ModuleDecisionTrees::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 ModuleDecisionTrees::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;
+  for (const auto &res : results1) {
+    if (res.FunctionNameAndPhase.getPhase() != FnNameAndPhase::ModulePhase)
+      mergedResults.push_back(res);
+    else
+      moduleResults1 = &res;
+  }
+  for (const auto &res : results2) {
+    if (res.FunctionNameAndPhase.getPhase() != FnNameAndPhase::ModulePhase)
+      mergedResults.push_back(res);
+    else
+      moduleResults2 = &res;
+  }
+  if (!moduleResults1)
+  {
+    if (moduleResults2)
+      mergedModuleResults = *moduleResults2;
+  }
+  if (!moduleResults2)
+  {
+    if (moduleResults1)
+      mergedModuleResults = *moduleResults1;
+  }
+  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());
+  }
+  if (moduleResults1 || moduleResults2)
+    mergedResults.push_back(mergedModuleResults);
+}
+
+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(std::map<FnNameAndPhase,
+                                         BitVector> &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;
+
+    if (llvm::sys::fs::exists(FicInputFile))
+    {
+      MdtPathsString = DecisionTree::readFromFile(FicInputFile);
+      llvm::sys::fs::remove(FicInputFile);
+    }
+    else if (llvm::sys::fs::exists(FicInputFile2))
+    {
+      MdtPathsString = DecisionTree::readFromFile(FicInputFile2);
+      llvm::sys::fs::remove(FicInputFile2);
+    }
+    else
+    {
+      report_fatal_error(Twine("ITERATIVE COMPILATION ERROR:"
+                               "unable to read input file\n"));
+    }
+    std::map<FnNameAndPhase, BitVector> MdtPaths;
+    std::string ErrorMsg;
+    if (!ModuleDecisionTrees::parseMdtPaths(MdtPaths, MdtPathsString, 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;
+    getResults(Results);
+    std::string ResultsStr =
+      ModuleDecisionTrees::generateMdtResultsString(Results);
+
+    if (ICPhase != FnNameAndPhase::CodeGenPhase)
+    {
+      DecisionTree::writeToFile(FicResultsFile, ResultsStr);
+    }
+    else
+    {
+      DecisionTree::writeToFile(FicResultsFile2, ResultsStr);
+    }
+  }
+  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/ICSetCurrentFunc.cpp

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

lib/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/DecisionTree.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>();
+    MDTP->setModuleCompilationPhase();
+  }
+
   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
   Loops = &getAnalysis<MachineLoopInfo>();
   Bundles = &getAnalysis<EdgeBundles>();
   SpillPlacer = &getAnalysis<SpillPlacement>();
   DebugVars = &getAnalysis<LiveDebugVariables>();
 
   initializeCSRCost();
 

lib/Target/Mips/CMakeLists.txt

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

lib/Target/Mips/Mips.h

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

lib/Target/Mips/MipsFunctionFitness.cpp

+//===-- MipsFunctionFitness.cpp - Function Fitness Implementation ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file estimates the fitness of a function which is used in
+// iterative compilation.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Mips.h"
+#include "MipsTargetMachine.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/DecisionTree.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/DecisionTree.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "mips"
 
 extern "C" void LLVMInitializeMipsTarget() {
   // Register the target.
   RegisterTargetMachine<MipsebTargetMachine> X(TheMipsTarget);

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

lib/Transforms/IPO/InlineAlways.cpp

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

lib/Transforms/IPO/InlineSimple.cpp

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

lib/Transforms/IPO/Inliner.cpp

 #include "llvm/Transforms/IPO/InlinerPass.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/DecisionTree.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"

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

lib/Transforms/IPO/PassManagerBuilder.cpp

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

lib/Transforms/Scalar/LICM.cpp

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

 
 /// 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 && 
+  assert(N != nullptr && AA != nullptr && LI != nullptr &&
+         DT != nullptr && CurLoop != nullptr && CurAST != nullptr &&
          SafetyInfo != nullptr && "Unexpected input to sinkRegion");
 
   // Set changed as false.
   bool Changed = false;
   // Get basic block
   BasicBlock *BB = N->getBlock();
   // If this subregion is not in the top level loop at all, exit.
   if (!CurLoop->contains(BB)) return Changed;
 
   // We are processing blocks in reverse dfo, so process children first.
   const std::vector<DomTreeNode*> &Children = N->getChildren();
   for (unsigned i = 0, e = Children.size(); i != e; ++i)
     Changed |=
-        sinkRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
+        sinkRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo,
+                   MDTP);
   // Only need to process the contents of this block if it is not part of a
   // subloop (which would already have been processed).
   if (inSubLoop(BB,CurLoop,LI)) return Changed;
 
   for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) {
     Instruction &I = *--II;
 
     // If the instruction is dead, we would try to sink it because it isn't used

 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 ///
 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                        DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
-                       AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
+                       AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo,
+                       ModuleDecisionTreeProxies *MDTP) {
   // Verify inputs.
-  assert(N != nullptr && AA != nullptr && LI != nullptr && 
-         DT != nullptr && CurLoop != nullptr && CurAST != nullptr && 
+  assert(N != nullptr && AA != nullptr && LI != nullptr &&
+         DT != nullptr && CurLoop != nullptr && CurAST != nullptr &&
          SafetyInfo != nullptr && "Unexpected input to hoistRegion");
   // Set changed as false.
   bool Changed = false;
   // Get basic block
   BasicBlock *BB = N->getBlock();
   // If this subregion is not in the top level loop at all, exit.
   if (!CurLoop->contains(BB)) return Changed;
   // Only need to process the contents of this block if it is not part of a
   // subloop (which would already have been processed).
   if (!inSubLoop(BB, CurLoop, LI))
+  {
     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) {
       Instruction &I = *II++;
       // Try constant folding this instruction.  If all the operands are
       // constants, it is technically hoistable, but it would be better to just
       // fold it.
       if (Constant *C = ConstantFoldInstruction(
               &I, I.getModule()->getDataLayout(), TLI)) {
+
+        if (MDTP->getDecision(MaxDtPriority / 2, LicmOpt))
+        {
+          continue;
+        }
+
         DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C << '\n');
         CurAST->copyValue(&I, C);
         CurAST->deleteValue(&I);
         I.replaceAllUsesWith(C);
         I.eraseFromParent();
         continue;
       }
 
       // Try hoisting the instruction out to the preheader.  We can only do this
       // if all of the operands of the instruction are loop invariant and if it
       // is safe to hoist the instruction.
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
           isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo,
                                  CurLoop->getLoopPreheader()->getTerminator()))
+      {
+        if (!(MDTP->getDecision(MaxDtPriority / 2, LicmOpt)))
+        {
           Changed |= hoist(I, CurLoop->getLoopPreheader());
         }
+      }
+    }
+  }
 
   const std::vector<DomTreeNode*> &Children = N->getChildren();
   for (unsigned i = 0, e = Children.size(); i != e; ++i)
     Changed |=
-        hoistRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
+        hoistRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo,
+                    MDTP);
   return Changed;
 }
 
 /// Computes loop safety information, checks loop body & header
 /// for the possiblity of may throw exception.
 ///
 void llvm::computeLICMSafetyInfo(LICMSafetyInfo * SafetyInfo, Loop * CurLoop) {
   assert(CurLoop != nullptr && "CurLoop cant be null");
static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
   if (isa<LoadInst>(I)) ++NumMovedLoads;
   else if (isa<CallInst>(I)) ++NumMovedCalls;
   ++NumSunk;
   Changed = true;
 
 #ifndef NDEBUG
   SmallVector<BasicBlock *, 32> ExitBlocks;
   CurLoop->getUniqueExitBlocks(ExitBlocks);
-  SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(), 
+  SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
                                              ExitBlocks.end());
 #endif
 
   // Clones of this instruction. Don't create more than one per exit block!
   SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
 
   // If this instruction is only used outside of the loop, then all users are
   // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
static bool hoist(Instruction &I, BasicBlock *Preheader) {
   else if (isa<CallInst>(I)) ++NumMovedCalls;
   ++NumHoisted;
   return true;
 }
 
 /// Only sink or hoist an instruction if it is not a trapping instruction,
 /// or if the instruction is known not to trap when moved to the preheader.
 /// or if it is a trapping instruction and is guaranteed to execute.
-static bool isSafeToExecuteUnconditionally(const Instruction &Inst, 
+static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
                                            const DominatorTree *DT,
                                            const TargetLibraryInfo *TLI,
                                            const Loop *CurLoop,
                                            const LICMSafetyInfo *SafetyInfo,
                                            const Instruction *CtxI) {
   if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT, TLI))
     return true;
 

 /// 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.
 ///
 bool llvm::promoteLoopAccessesToScalars(AliasSet &AS,
                                         SmallVectorImpl<BasicBlock*>&ExitBlocks,
                                         SmallVectorImpl<Instruction*>&InsertPts,
-                                        PredIteratorCache &PIC, LoopInfo *LI, 
-                                        DominatorTree *DT, Loop *CurLoop, 
-                                        AliasSetTracker *CurAST, 
-                                        LICMSafetyInfo * SafetyInfo) { 
+                                        PredIteratorCache &PIC, LoopInfo *LI,
+                                        DominatorTree *DT, Loop *CurLoop,
+                                        AliasSetTracker *CurAST,
+                                        LICMSafetyInfo * SafetyInfo) {
   // Verify inputs.
-  assert(LI != nullptr && DT != nullptr && 
-         CurLoop != nullptr && CurAST != nullptr && 
-         SafetyInfo != nullptr && 
+  assert(LI != nullptr && DT != nullptr &&
+         CurLoop != nullptr && CurAST != nullptr &&
+         SafetyInfo != nullptr &&
          "Unexpected Input to promoteLoopAccessesToScalars");
   // Initially set Changed status to false.
   bool Changed = false;
   // We can promote this alias set if it has a store, if it is a "Must" alias
   // set, if the pointer is loop invariant, and if we are not eliminating any
   // volatile loads or stores.
   if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
       AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue()))
for (User *U : ASIV->users()) {
         unsigned InstAlignment = store->getAlignment();
         if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0)
           if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) {
             GuaranteedToExecute = true;
             Alignment = InstAlignment;
           }
 
         if (!GuaranteedToExecute)
-          GuaranteedToExecute = isGuaranteedToExecute(*UI, DT, 
+          GuaranteedToExecute = isGuaranteedToExecute(*UI, DT,
                                                       CurLoop, SafetyInfo);
 
       } else
         return Changed; // Not a load or store.
 
       // Merge the AA tags.
       if (LoopUses.empty()) {
         // On the first load/store, just take its AA tags.
void LICM::deleteAnalysisLoop(Loop *L) {
   LoopToAliasSetMap.erase(L);
 }
 
 
 /// Return true if the body of this loop may store into the memory
 /// location pointed to by V.
 ///
 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
-                                     const AAMDNodes &AAInfo, 
+                                     const AAMDNodes &AAInfo,
                                      AliasSetTracker *CurAST) {
   // Check to see if any of the basic blocks in CurLoop invalidate *V.
   return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod();
 }
 
 /// Little predicate that returns true if the specified basic block is in
 /// a subloop of the current one, not the current one itself.
 ///
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
   assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
   return LI->getLoopFor(BB) != CurLoop;
 }