Index: include/llvm/Analysis/DecisionTree.h =================================================================== --- /dev/null +++ include/llvm/Analysis/DecisionTree.h @@ -0,0 +1,272 @@ +//===-- 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 +#include +#include +#include "llvm/ADT/BitVector.h" +#include "llvm/Pass.h" +#include "llvm/Support/CommandLine.h" + +namespace llvm { + +extern cl::opt 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 Priorities; + std::vector 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 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 &getOptimizations() + { return Optimizations; } + const SmallVector &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 &getPriorities() { return Priorities; } + const std::vector &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 Priorities; + std::vector 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 &paths); + void applyResults(const std::vector &results); + void updateBestFunctionFitness(int iteration); + void updateNodesFitness(); + void selectPath(bool FinalPass); + void splitPaths( + const std::map &paths, + std::map &pathBeforeCodegen, + std::map &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 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 &paths, + const std::string &pathString, + std::string &ErrorMessage); + static std::string generateMdtPathsString( + const std::map &paths); + static bool parseMdtResults(std::vector &results, + const std::string &resString, + std::string &ErrorMessage); + static std::string generateMdtResultsString( + const std::vector &results); + + static int calculateTotalFitness(const std::vector &results); + static void mergeMdtResults(std::vector &mergedResults, + const std::vector &results1, + const std::vector &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 &paths); + void getResults(std::vector &results) const; + DecisionTreeProxy *getCurrFnDecisionTreeProxy() + { return CurrFnDecisionTreeProxy; } + bool getIterativeCompilation() { return IterativeCompilation; } + void setIterativeCompilation(bool x) { IterativeCompilation = x; } +protected: + bool IterativeCompilation; + std::map DecisionTreeProxies; + DecisionTreeProxy *CurrFnDecisionTreeProxy; + FnNameAndPhase::ICPhase ICPhase; +}; + +} + +#endif Index: include/llvm/Analysis/ICSetCurrentFunc.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ICSetCurrentFunc.h @@ -0,0 +1,42 @@ +//===-- ICSetCurrentFunc.h - Iterative Comp Set Current Func DT -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Implements the pass which sets the decision tree proxy of the +// current function. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ICSETCURRENTFUNC_H +#define LLVM_ANALYSIS_ICSETCURRENTFUNC_H + +#include "llvm/Pass.h" +#include "llvm/Analysis/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(); + } +}; + +} + +#endif Index: include/llvm/Analysis/Passes.h =================================================================== --- include/llvm/Analysis/Passes.h +++ include/llvm/Analysis/Passes.h @@ -173,6 +173,13 @@ // FunctionPass *createMemDerefPrinter(); + //===--------------------------------------------------------------------===// + // + // createICSetCurrentFuncPass - This pass sets decision tree proxy of the + // current function which is used in iterative compilation. + // + FunctionPass *createICSetCurrentFuncPass(); + } #endif Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -304,6 +304,9 @@ void initializeFloat2IntPass(PassRegistry&); void initializeLoopDistributePass(PassRegistry&); void initializeSjLjEHPreparePass(PassRegistry&); +void initializeModuleDecisionTreeProxiesPass(PassRegistry&); +void initializeFunctionFitnessPass(PassRegistry&); +void initializeICSetCurrentFuncPass(PassRegistry&); } #endif Index: include/llvm/Transforms/IPO/InlinerPass.h =================================================================== --- include/llvm/Transforms/IPO/InlinerPass.h +++ include/llvm/Transforms/IPO/InlinerPass.h @@ -25,6 +25,7 @@ class InlineCost; template class SmallPtrSet; + class ModuleDecisionTreeProxies; /// Inliner - This class contains all of the helper code which is used to /// perform the inlining operations that do not depend on the policy. @@ -81,6 +82,8 @@ // InsertLifetime - Insert @llvm.lifetime intrinsics. bool InsertLifetime; + ModuleDecisionTreeProxies *MDTP; + /// shouldInline - Return true if the inliner should attempt to /// inline at the given CallSite. bool shouldInline(CallSite CS); Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -32,6 +32,7 @@ class PredIteratorCache; class ScalarEvolution; class TargetLibraryInfo; +class ModuleDecisionTreeProxies; /// \brief Captures loop safety information. /// It keep information for loop & its header may throw exception. @@ -226,7 +227,7 @@ /// It returns changed status. bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + LICMSafetyInfo *, ModuleDecisionTreeProxies *MDTP); /// \brief Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth @@ -237,7 +238,7 @@ /// loop and loop safety information as arguments. It returns changed status. bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + LICMSafetyInfo *, ModuleDecisionTreeProxies *); /// \brief Try to promote memory values to scalars by sinking stores out of /// the loop and moving loads to before the loop. We do this by looping over Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -69,6 +69,8 @@ initializeTargetTransformInfoWrapperPassPass(Registry); initializeTypeBasedAliasAnalysisPass(Registry); initializeScopedNoAliasAAPass(Registry); + initializeModuleDecisionTreeProxiesPass(Registry); + initializeICSetCurrentFuncPass(Registry); } void LLVMInitializeAnalysis(LLVMPassRegistryRef R) { Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -18,11 +18,13 @@ 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 Index: lib/Analysis/DecisionTree.cpp =================================================================== --- /dev/null +++ lib/Analysis/DecisionTree.cpp @@ -0,0 +1,1096 @@ +//===-- 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 +#include +#include +#include +#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 + +using namespace llvm; + +cl::opt +llvm::IterativeCompilationOpt("fiterative-comp", cl::init(false), + cl::desc("Enable iterative compilation")); +static cl::opt +FicInputFile("fic-input-file", cl::init("ic-input")); +static cl::opt +FicInputFile2("fic-input2-file", cl::init("ic-input2")); +static cl::opt +FicResultsFile("fic-results-file", cl::init("ic-results")); +static cl::opt +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 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> 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 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 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 &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 &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 &paths, + std::map &pathsBeforeCodegen, + std::map &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 &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(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(&*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(Value); + if (!ValueString) { + ErrorMessage = "Expected string as value."; + return false; + } + llvm::yaml::ScalarNode *KeyString = + dyn_cast((*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 &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 &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(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(&*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 PrioritiesVector; + std::vector 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((*KVI).getKey()); + if (!KeyString) { + ErrorMessage = "Expected strings as key."; + return false; + } + SmallString<8> KeyStorage; + if (KeyString->getValue(KeyStorage) == "Priorities") { + Priorities = dyn_cast(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(&*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(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(&*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(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 &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 &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 &mergedResults, + const std::vector &results1, + const std::vector &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 &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 &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 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 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; +} Index: lib/Analysis/ICSetCurrentFunc.cpp =================================================================== --- /dev/null +++ lib/Analysis/ICSetCurrentFunc.cpp @@ -0,0 +1,44 @@ +//===-- ICSetCurrentFunc.cpp - Iterative Comp Set Current Func DT ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Implements the pass which sets the decision tree proxy of the +// current function. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/ICSetCurrentFunc.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/IR/Function.h" + +using namespace llvm; + +bool ICSetCurrentFunc::runOnFunction(Function &F) { + MD = &getAnalysis(); + //MD->setFunctionName(F.getName()); + + // TODO: Use module phase decision tree until iterative compilation + // framework can handle multiple decision trees. + + //MD->setCurrentFunctionAndPhase(F.getName(), + // FnNameAndPhase::FunctionPhase); + MD->setModuleCompilationPhase(); + return false; +} + +char ICSetCurrentFunc::ID = 0; + +INITIALIZE_PASS_BEGIN(ICSetCurrentFunc, "icsetcurrentfunc", + "Set Current Function DT Proxy", false, true) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) +INITIALIZE_PASS_END(ICSetCurrentFunc, "icsetcurrentfunc", + "Set Current Function DT Proxy", false, true) + +FunctionPass *llvm::createICSetCurrentFuncPass() { + return new ICSetCurrentFunc(); +} Index: lib/CodeGen/RegAllocGreedy.cpp =================================================================== --- lib/CodeGen/RegAllocGreedy.cpp +++ lib/CodeGen/RegAllocGreedy.cpp @@ -22,6 +22,7 @@ #include "SplitKit.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/DecisionTree.h" #include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/EdgeBundles.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" @@ -119,6 +120,7 @@ const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; RegisterClassInfo RCI; + ModuleDecisionTreeProxies *MDTP; // analyses SlotIndexes *Indexes; @@ -473,6 +475,10 @@ AU.addPreserved(); AU.addRequired(); AU.addPreserved(); + + if(IterativeCompilationOpt) + AU.addRequired(); + AU.addRequired(); AU.addPreserved(); AU.addRequired(); @@ -864,6 +870,7 @@ BestCost.setMax(); unsigned BestPhys = 0; unsigned OrderLimit = Order.getOrder().size(); + SmallVector EvictionCandidates; // When we are just looking for a reduced cost per use, don't break any // hints, and only evict smaller spill weights. @@ -907,11 +914,29 @@ // Best so far. BestPhys = PhysReg; + EvictionCandidates.push_back(PhysReg); + // Stop if the hint can be used. if (Order.isHint()) break; } + // Try different choices for register to be evicted. + if(IterativeCompilationOpt && (EvictionCandidates.size() > 1)) { + int priority = 0x10000; + + for (int i = (int)EvictionCandidates.size() - 2; i >= 0; i--) { + bool decision = false; + + decision = MDTP->getDecision(priority, llvm::RegAllocOpt); + + if(decision) + BestPhys = EvictionCandidates[i]; + + priority = priority / 2; + } + } + if (!BestPhys) return 0; @@ -2578,6 +2603,13 @@ Indexes = &getAnalysis(); MBFI = &getAnalysis(); DomTree = &getAnalysis(); + + if(IterativeCompilationOpt) + { + MDTP = &getAnalysis(); + MDTP->setModuleCompilationPhase(); + } + SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); Loops = &getAnalysis(); Bundles = &getAnalysis(); Index: lib/Target/Mips/CMakeLists.txt =================================================================== --- lib/Target/Mips/CMakeLists.txt +++ lib/Target/Mips/CMakeLists.txt @@ -27,6 +27,7 @@ MipsConstantIslandPass.cpp MipsDelaySlotFiller.cpp MipsFastISel.cpp + MipsFunctionFitness.cpp MipsInstrInfo.cpp MipsISelDAGToDAG.cpp MipsISelLowering.cpp Index: lib/Target/Mips/Mips.h =================================================================== --- lib/Target/Mips/Mips.h +++ lib/Target/Mips/Mips.h @@ -31,6 +31,7 @@ FunctionPass *createMipsDelaySlotFillerPass(MipsTargetMachine &TM); FunctionPass *createMipsLongBranchPass(MipsTargetMachine &TM); FunctionPass *createMipsConstantIslandPass(MipsTargetMachine &tm); + FunctionPass *createMipsFunctionFitnessPass(); } // end namespace llvm; #endif Index: lib/Target/Mips/MipsFunctionFitness.cpp =================================================================== --- /dev/null +++ lib/Target/Mips/MipsFunctionFitness.cpp @@ -0,0 +1,84 @@ +//===-- MipsFunctionFitness.cpp - Function Fitness Implementation ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file estimates the fitness of a function which is used in +// iterative compilation. +// +//===----------------------------------------------------------------------===// + +#include "Mips.h" +#include "MipsTargetMachine.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/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(); + 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(); + MachineFunctionPass::getAnalysisUsage(AU); + } + + unsigned TotalCount; +}; + +char FunctionFitness::ID = 0; + +bool FunctionFitness:: +runOnMachineBasicBlock(MachineBasicBlock &MBB) { + unsigned Count = 0; + + for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) + Count++; + + TotalCount += Count; + + return false; +} + +/// createMipsFunctionFitnessPass - Returns a pass that counts generated +/// instructions +/// in +FunctionPass *llvm::createMipsFunctionFitnessPass() { + return new FunctionFitness(); +} Index: lib/Target/Mips/MipsTargetMachine.cpp =================================================================== --- lib/Target/Mips/MipsTargetMachine.cpp +++ lib/Target/Mips/MipsTargetMachine.cpp @@ -31,6 +31,7 @@ #include "llvm/Support/TargetRegistry.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Analysis/DecisionTree.h" using namespace llvm; @@ -251,6 +252,10 @@ void MipsPassConfig::addPreEmitPass() { MipsTargetMachine &TM = getMipsTargetMachine(); addPass(createMipsDelaySlotFillerPass(TM)); + + if(IterativeCompilationOpt) + addPass(createMipsFunctionFitnessPass()); + addPass(createMipsLongBranchPass(TM)); addPass(createMipsConstantIslandPass(TM)); } Index: lib/Transforms/IPO/InlineAlways.cpp =================================================================== --- lib/Transforms/IPO/InlineAlways.cpp +++ lib/Transforms/IPO/InlineAlways.cpp @@ -71,6 +71,7 @@ INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) INITIALIZE_PASS_DEPENDENCY(InlineCostAnalysis) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) INITIALIZE_PASS_END(AlwaysInliner, "always-inline", "Inliner for always_inline functions", false, false) Index: lib/Transforms/IPO/InlineSimple.cpp =================================================================== --- lib/Transforms/IPO/InlineSimple.cpp +++ lib/Transforms/IPO/InlineSimple.cpp @@ -79,6 +79,7 @@ INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) INITIALIZE_PASS_DEPENDENCY(InlineCostAnalysis) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) INITIALIZE_PASS_END(SimpleInliner, "inline", "Function Integration/Inlining", false, false) Index: lib/Transforms/IPO/Inliner.cpp =================================================================== --- lib/Transforms/IPO/Inliner.cpp +++ lib/Transforms/IPO/Inliner.cpp @@ -21,6 +21,7 @@ #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/InlineCost.h" #include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/DecisionTree.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DiagnosticInfo.h" @@ -64,7 +65,7 @@ // Threshold to use when optsize is specified (and there is no -inline-limit). const int OptSizeThreshold = 75; -Inliner::Inliner(char &ID) +Inliner::Inliner(char &ID) : CallGraphSCCPass(ID), InlineThreshold(InlineLimit), InsertLifetime(true) {} Inliner::Inliner(char &ID, int Threshold, bool InsertLifetime) @@ -78,6 +79,7 @@ void Inliner::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.addRequired(); + AU.addRequired(); CallGraphSCCPass::getAnalysisUsage(AU); } @@ -321,7 +323,21 @@ } 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"); @@ -431,6 +447,8 @@ bool Inliner::runOnSCC(CallGraphSCC &SCC) { CallGraph &CG = getAnalysis().getCallGraph(); AssumptionCacheTracker *ACT = &getAnalysis(); + MDTP = &getAnalysis(); + MDTP->setModuleCompilationPhase(); auto *TLIP = getAnalysisIfAvailable(); const TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr; AliasAnalysis *AA = &getAnalysis(); Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -252,6 +252,7 @@ MPM.add(createTailCallEliminationPass()); // Eliminate tail calls MPM.add(createCFGSimplificationPass()); // Merge & remove BBs MPM.add(createReassociatePass()); // Reassociate expressions + MPM.add(createICSetCurrentFuncPass()); // Set decision tree proxy // Rotate Loop - disable header duplication at -Oz MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1)); MPM.add(createLICMPass()); // Hoist loop invariants Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -35,6 +35,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/DecisionTree.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolution.h" @@ -57,6 +58,7 @@ #include "llvm/Transforms/Utils/LoopUtils.h" #include "llvm/Transforms/Utils/SSAUpdater.h" #include + using namespace llvm; #define DEBUG_TYPE "licm" @@ -113,6 +115,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequiredID(LoopSimplifyID); AU.addPreservedID(LoopSimplifyID); @@ -137,6 +140,7 @@ DominatorTree *DT; // Dominator Tree for the current Loop. TargetLibraryInfo *TLI; // TargetLibraryInfo for constant folding. + ModuleDecisionTreeProxies *MDTP; // State that is updated as we process loops. bool Changed; // Set to true when we change anything. @@ -161,6 +165,7 @@ char LICM::ID = 0; INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_DEPENDENCY(LCSSA) @@ -185,11 +190,14 @@ LI = &getAnalysis().getLoopInfo(); AA = &getAnalysis(); DT = &getAnalysis().getDomTree(); + MDTP = &getAnalysis(); TLI = &getAnalysis().getTLI(); assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form."); + int n = 0; + CurAST = new AliasSetTracker(*AA); // Collect Alias info from subloops. for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end(); @@ -216,6 +224,7 @@ // Because subloops have already been incorporated into AST, we skip blocks in // subloops. // + n = 0; for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E; ++I) { BasicBlock *BB = *I; @@ -239,10 +248,10 @@ // if (L->hasDedicatedExits()) Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop, - CurAST, &SafetyInfo); + CurAST, &SafetyInfo, MDTP); if (Preheader) Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, - CurLoop, CurAST, &SafetyInfo); + CurLoop, CurAST, &SafetyInfo, MDTP); // Now that all loop invariants have been removed from the loop, promote any // memory references to scalars that we can. @@ -254,8 +263,8 @@ // 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 @@ -296,11 +305,12 @@ /// 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. @@ -314,7 +324,8 @@ const std::vector &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; @@ -354,10 +365,11 @@ /// 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; @@ -368,6 +380,7 @@ // Only need to process the contents of this block if it is not part of a // subloop (which would already have been processed). if (!inSubLoop(BB, CurLoop, LI)) + { for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { Instruction &I = *II++; // Try constant folding this instruction. If all the operands are @@ -375,6 +388,12 @@ // fold it. if (Constant *C = ConstantFoldInstruction( &I, I.getModule()->getDataLayout(), TLI)) { + + if (MDTP->getDecision(MaxDtPriority / 2, LicmOpt)) + { + continue; + } + DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n'); CurAST->copyValue(&I, C); CurAST->deleteValue(&I); @@ -391,13 +410,20 @@ canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) && isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo, CurLoop->getLoopPreheader()->getTerminator())) - Changed |= hoist(I, CurLoop->getLoopPreheader()); + { + if (!(MDTP->getDecision(MaxDtPriority / 2, LicmOpt))) + { + Changed |= hoist(I, CurLoop->getLoopPreheader()); + } + } } + } const std::vector &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; } @@ -591,7 +617,7 @@ #ifndef NDEBUG SmallVector ExitBlocks; CurLoop->getUniqueExitBlocks(ExitBlocks); - SmallPtrSet ExitBlockSet(ExitBlocks.begin(), + SmallPtrSet ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); #endif @@ -660,7 +686,7 @@ /// 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, @@ -798,14 +824,14 @@ bool llvm::promoteLoopAccessesToScalars(AliasSet &AS, SmallVectorImpl&ExitBlocks, SmallVectorImpl&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; @@ -903,7 +929,7 @@ } if (!GuaranteedToExecute) - GuaranteedToExecute = isGuaranteedToExecute(*UI, DT, + GuaranteedToExecute = isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo); } else @@ -1009,7 +1035,7 @@ /// 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();