Index: include/llvm/Analysis/DecisionTree.h =================================================================== --- /dev/null +++ include/llvm/Analysis/DecisionTree.h @@ -0,0 +1,192 @@ +//===-- 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_DECISIONTREE_H +#define LLVM_DECISIONTREE_H + +#include +#include +#include +#include "llvm/ADT/SmallVector.h" +#include "llvm/Pass.h" + +namespace llvm { + +const int MaxDtPriority = 1000; + +struct DecisionTreeNode { + int calcFinalPriority(int bestFunctionFitness); + DecisionTreeNode *Parent; + DecisionTreeNode *PrimaryDecision; + DecisionTreeNode *AlternativeDecision; + int Priority; + int Fitness; + int Depth; + int NodeId; + bool IsInterprocedural; +}; + +class DecisionTree { +private: + DecisionTreeNode *DecisionTreeRoot; + DecisionTreeNode *CurrentNode; + std::vector Path; + int FunctionFitness; + int BestFunctionFitness; + std::vector BestPath; + int NodeIdCount; + +public: + DecisionTree(); + ~DecisionTree(); + + int getFunctionFitness() const { return FunctionFitness; } + void setFunctionFitness(int x) { FunctionFitness = x; } + std::vector &getPath() { return Path; } + + bool getDecision(int priority); + void updateBestFunctionFitness(int iteration); + std::vector findPath(DecisionTreeNode *node); + bool selectPath(bool finalPass); + void startNewIteation(); + void updatePriorities(); + + static std::string generateDecisionTreePathString(std::vector &path_); + static std::string generateResultsString(std::vector &results); + static void parseResultsString(std::vector &results, + std::string &resultString, int &position); + static int parseInteger(std::string &s, int &position); + static int findDelimiter(std::string &s, int position, char delimiter); + static void parseDecisionTreePath(std::vector &path_, + std::string &pathString, int &position); + void applayResults(std::vector &results); + + static void writeToFile(const std::string &fileName, const std::string &data); + static std::string readFromFile(const std::string &fileName); +}; + +class DecisionTreeProxy { +public: + DecisionTreeProxy(); + + std::vector &getPath() { return Path; } + int getFunctionFitness() const { return FunctionFitness; } + void setFunctionFitness(int x) { FunctionFitness = x; } + std::vector &getPriorities() { return Priorities; } + + bool getDecision(int priority); + + std::string generateResultsString(); + std::vector getResults(); + void setPath(std::vector &path_); + +protected: + std::vector Path; + int FunctionFitness; + int BestFunctionFitness; + std::vector Priorities; + int CurrentDepth; +}; + +class ModuleDecisionTrees { +public: + enum IterativeCompilationPhase { + FunctionPhase, ///< Function level optimizations. + ModulePhase, ///< Module level optimizations. + CodeGenPhase ///< Codegen optimizations. + }; + + ModuleDecisionTrees(); + ~ModuleDecisionTrees(); + + std::string generateDecisionTreePathString(); + void parseResultsString(std::string &resultString); + + DecisionTree &getDecisionTree(const std::string &name); + std::map &getDecisionTrees() + { return DecisionTrees; } + + void startNewIteration(); + void getPaths(std::map > &paths); + void applayResults(std::map > &results); + void updateBestFunctionFitness(int iteration); + void updatePriorities(); + void selectPath(bool finalPass); + std::string &getICInputFile() { return ICInputFile; } + std::string &getICResultsFile() { return ICResultsFile; } + std::string &getICResultsFile2() { return ICResultsFile2; } + std::string &getICInputFileOpt() { return ICInputFileOpt; } + std::string &getICResultsFileOpt() { return ICResultsFileOpt; } + std::string &getICResultsFile2Opt() { return ICResultsFile2Opt; } + +protected: + std::map DecisionTrees; + std::string ICInputFile; + std::string ICResultsFile; + std::string ICResultsFile2; + std::string ICInputFileOpt; + std::string ICResultsFileOpt; + std::string ICResultsFile2Opt; + +public: + static void parseMdtPaths(std::map > &paths, + std::string &pathString); + static std::string generateMdtPathsString( + std::map > &paths); + static void parseMdtResults( + std::map > &results, + std::string &resString); + static std::string generateMdtResultsString( + std::map > &results); + static std::string decorateName(std::string &name); + static std::string undecorateName(std::string &s, int &position); + static int calculateTotalFitness( + std::map > &results); +}; + +class ModuleDecisionTreeProxies : public ImmutablePass { +public: + static char ID; + + ModuleDecisionTreeProxies(); + ~ModuleDecisionTreeProxies(); + virtual bool doInitialization(Module &M); + virtual bool doFinalization(Module &M); + + bool getDecision(int priority); + + std::string nameFunction; + + void setFunctionName(std::string fname) { nameFunction = fname; } + void setCurrentFunctionAndPhase(const std::string &fnName, + ModuleDecisionTrees::IterativeCompilationPhase phase); + DecisionTreeProxy &getDecisionTreeProxy(const std::string &name); + void setPaths(std::map > &paths); + void getResults(std::map > &results); + DecisionTreeProxy *getCurrFnDecisionTreeProxy() + { return CurrFnDecisionTreeProxy; } + void setCurrFnDecisionTreeProxy(DecisionTreeProxy *x) + { CurrFnDecisionTreeProxy = x; } + bool getIterativeCompilation() { return IterativeCompilation; } + void setIterativeCompilation(bool x) { IterativeCompilation = x; } +protected: + bool IterativeCompilation; + std::map DecisionTreeProxies; + DecisionTreeProxy *CurrFnDecisionTreeProxy; + ModuleDecisionTrees::IterativeCompilationPhase 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 @@ -150,6 +150,13 @@ // FunctionPass *createMemDepPrinter(); + //===--------------------------------------------------------------------===// + // + // createICSetCurrentFuncPass - This pass sets decision tree proxy of the + // current function which is used in iterative compilation. + // + FunctionPass *createICSetCurrentFuncPass(); + // createJumpInstrTableInfoPass - This creates a pass that stores information // about the jump tables created by JumpInstrTables ImmutablePass *createJumpInstrTableInfoPass(); Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -280,6 +280,9 @@ void initializeMachineFunctionPrinterPassPass(PassRegistry&); void initializeStackMapLivenessPass(PassRegistry&); void initializeLoadCombinePass(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: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -67,6 +67,8 @@ initializeTargetTransformInfoAnalysisGroup(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 @@ -16,10 +16,12 @@ CostModel.cpp CodeMetrics.cpp ConstantFolding.cpp + DecisionTree.cpp Delinearization.cpp DependenceAnalysis.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,652 @@ +//===-- 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. +// +//===----------------------------------------------------------------------===// + +#include +#include +#include +#include +#include "llvm/Analysis/DecisionTree.h" +#include "llvm/Support/CommandLine.h" +using namespace llvm; + +static cl::opt +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 +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 = 100000; + CurrentNode = DecisionTreeRoot; + CurrentNode->Parent = 0; + CurrentNode->PrimaryDecision = 0; + CurrentNode->AlternativeDecision = 0; + CurrentNode->Priority = 0; + CurrentNode->Fitness = 100000; + CurrentNode->Depth = 0; + CurrentNode->NodeId = NodeIdCount++; + CurrentNode->IsInterprocedural = false; +} + +DecisionTree::~DecisionTree() { + delete DecisionTreeRoot; +} + +bool DecisionTree::getDecision(int priority) { + unsigned depth = CurrentNode->Depth; + if (depth < Path.size()) { + bool decision = Path[depth]; + if (decision) { + if (CurrentNode->AlternativeDecision) { + CurrentNode = CurrentNode->AlternativeDecision; + return decision; + } + } + else { + if (CurrentNode->PrimaryDecision) { + CurrentNode = CurrentNode->PrimaryDecision; + return decision; + } + } + } + + CurrentNode->Priority = priority; + + DecisionTreeNode *newNode = new DecisionTreeNode; + newNode->Parent = CurrentNode; + newNode->PrimaryDecision = 0; + newNode->AlternativeDecision = 0; + newNode->Priority = 0; + newNode->Fitness = INT_MAX; + newNode->Depth = depth + 1; + newNode->NodeId = NodeIdCount++; + newNode->IsInterprocedural = false; + + if (CurrentNode->PrimaryDecision == 0) { + CurrentNode->PrimaryDecision = newNode; + CurrentNode = newNode; + return false; + } + else { + CurrentNode->AlternativeDecision = newNode; + CurrentNode = newNode; + return true; + } +} + +void DecisionTree::updateBestFunctionFitness(int iteration) { + if (FunctionFitness < BestFunctionFitness) { + BestFunctionFitness = FunctionFitness; + BestPath = findPath(CurrentNode); + } + updatePriorities (); +} + +std::vector DecisionTree::findPath(DecisionTreeNode *node) { + std::vector path; + DecisionTreeNode *n = node; + while(n != DecisionTreeRoot) { + DecisionTreeNode *parent = n->Parent; + if (n == parent->AlternativeDecision) + path.push_back(true); + else + path.push_back(false); + n = parent; + } + std::reverse(path.begin(), path.end()); + if (node->PrimaryDecision != 0) + path.push_back(true); + return path; +} + +bool DecisionTree::selectPath(bool finalPass) { + if (finalPass) { + Path = BestPath; + return true; + } + + std::vector 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) { + Path = findPath(selectedNode); + return false; + } + else { + Path = BestPath; + return true; + } +} + +void DecisionTree::startNewIteation() { + CurrentNode = DecisionTreeRoot; + FunctionFitness = 0; +} + +void DecisionTree::updatePriorities() { + std::vector path; + DecisionTreeNode *n = CurrentNode; + while(n) { + if (n->Fitness > FunctionFitness) + n->Fitness = FunctionFitness; + n = n->Parent; + } +} + +int DecisionTreeNode::calcFinalPriority(int bestFunctionFitness) { + if (Fitness == 0) + return Priority; + return (Priority * bestFunctionFitness) / Fitness; +} + +std::string DecisionTree::generateDecisionTreePathString( + std::vector &path_) { + std::string pathString = "<"; + int len = (int)path_.size(); + int i; + for (i = 0; i < len; i++) { + if (path_[i]) + pathString += std::string("1"); + else + pathString += std::string("0"); + } + pathString += std::string(">"); + return pathString; +} + +std::string DecisionTree::generateResultsString(std::vector &results) { + unsigned len = results.size(); + std::stringstream s; + s << (len - 1) << ";"; + for (unsigned i = 0; i < len; i++) + s << results[i] << ";"; + return s.str(); +} + +void DecisionTree::applayResults(std::vector &results) { + unsigned i; + unsigned pathLen = Path.size(); + if (results.empty()) + return; + for (i = 0; i < pathLen; i++) + getDecision(0); + unsigned n = results.size() - 1; + for (i = 0; i < n; i++) { + int t = results[i]; + getDecision(t); + } + int t = results[n]; + setFunctionFitness(t); +} + +void DecisionTree::parseResultsString(std::vector &results, + std::string &resultString, + int &position) { + int i; + int len = parseInteger(resultString, position); + for (i = 0; i < len; i++) { + int t = parseInteger(resultString, position); + results.push_back(t); + } + int t = parseInteger(resultString, position); + results.push_back(t); +} + +int DecisionTree::parseInteger(std::string &s, int &position) { + int r = atoi(s.c_str() + position); + position = findDelimiter(s, position, ';') + 1; + return r; +} + +int DecisionTree::findDelimiter(std::string &s, int position, char delimiter) { + int i = 0; + for (;;) { + if (s[position + i] == delimiter) + return position + i; + i++; + if (position + i >= (int)s.size()) + return 0; + } +} + +void DecisionTree::writeToFile(const std::string &fileName, + const std::string &data) { + std::ofstream outf(fileName.c_str()); + if (!outf) + return; + outf.write(&data[0], data.size()); +} + +std::string DecisionTree::readFromFile(const std::string &fileName) { + std::ifstream inf(fileName.c_str(), std::ios::in | std::ios::binary); + if (!inf) + return ""; + std::string contents; + inf.seekg(0, std::ios::end); + if (!inf.tellg()) + return ""; + contents.resize(inf.tellg()); + inf.seekg(0, std::ios::beg); + inf.read(&contents[0], contents.size()); + inf.close(); + return contents; +} + +DecisionTreeProxy::DecisionTreeProxy() + : FunctionFitness(0), BestFunctionFitness(INT_MAX), CurrentDepth(0) {} + +bool DecisionTreeProxy::getDecision(int priority) { + if (CurrentDepth < (int)Path.size()) { + bool r = Path[CurrentDepth]; + CurrentDepth++; + return r; + } + Priorities.push_back(priority); + CurrentDepth++; + return false; +} + +void DecisionTree::parseDecisionTreePath(std::vector &path_, + std::string &pathString, + int &position) { + path_.resize(0); + int len = (int)pathString.size(); + if (len < 2) + return; + if (pathString[position] != '<') + return; + for (int i = position + 1; i < position + len; i++) { + char c = pathString[i]; + if (c == '>') { + position = i + 1; + return; + } + if (c == '0') { + path_.push_back(false); + continue; + } + if (c == '1') { + path_.push_back(true); + continue; + } + return; + } +} + +std::vector DecisionTreeProxy::getResults() { + std::vector results = Priorities; + results.push_back(FunctionFitness); + return results; +} + +void DecisionTreeProxy::setPath(std::vector &path_) { + Path = path_; +} + +ModuleDecisionTrees::ModuleDecisionTrees() +{} + +ModuleDecisionTrees::~ModuleDecisionTrees() { + std::map::iterator it = DecisionTrees.begin(); + for (; it != DecisionTrees.end(); it++) { + DecisionTree *dt = it->second; + delete dt; + } +} + +DecisionTree &ModuleDecisionTrees::getDecisionTree(const std::string &name) { + if (DecisionTrees.find(name) == DecisionTrees.end()) { + DecisionTrees[name] = new DecisionTree(); + } + return *DecisionTrees[name]; +} + +void ModuleDecisionTrees::startNewIteration() { + std::map::iterator it; + for (it = DecisionTrees.begin(); it != DecisionTrees.end(); it++) { + DecisionTree *dt = it->second; + dt->startNewIteation(); + } +} + +void ModuleDecisionTrees::getPaths(std::map > &paths) { + paths.clear(); + std::map::iterator it; + for (it = DecisionTrees.begin(); it != DecisionTrees.end(); it++) { + std::string fnName = it->first; + DecisionTree *dt = it->second; + dt->startNewIteation(); + std::vector &path = dt->getPath(); + paths[fnName] = path; + } +} + +void ModuleDecisionTrees::applayResults(std::map > &results) { + std::map >::iterator it, e; + for(it = results.begin(), e = results.end(); it != e; it++) { + std::string fnName = it->first; + std::vector &results = it->second; + DecisionTree &dt = this->getDecisionTree(fnName); + dt.applayResults(results); + } +} + +void ModuleDecisionTrees::updateBestFunctionFitness(int iteration) { + std::map::iterator it, e; + for (it = DecisionTrees.begin(), e = DecisionTrees.end(); it != e; it++) { + DecisionTree *dt = it->second; + dt->updateBestFunctionFitness(iteration); + } +} + +void ModuleDecisionTrees::updatePriorities() +{ + std::map::iterator it, e; + for (it = DecisionTrees.begin(), e = DecisionTrees.end(); it != e; it++) { + DecisionTree *dt = it->second; + dt->updatePriorities(); + } +} + +void ModuleDecisionTrees::selectPath(bool finalPass) +{ + std::map::iterator it, e; + for (it = DecisionTrees.begin(), e = DecisionTrees.end(); it != e ;it++) { + DecisionTree *dt = it->second; + dt->selectPath(finalPass); + } +} + +void ModuleDecisionTrees::parseMdtPaths(std::map > &paths, + std::string &pathsString) { + paths.clear(); + int len = (int)pathsString.size(); + int pos = 0; + bool started = false; + if (!len) + return; + for (;;) { + char c = pathsString[pos]; + if (c == '\n' || c == '\r') { + pos++; + continue; + } + if (c == '{' && !started) { + started = true; + pos++; + continue; + } + if (c == '}') + return; + std::string name = undecorateName(pathsString, pos); + std::vector path; + DecisionTree::parseDecisionTreePath(path, pathsString, pos); + paths[name] = path; + if (pos >= len) + return; + } +} + +std::string ModuleDecisionTrees::generateMdtPathsString( + std::map > &paths) { + std::string pathsString = "{\n"; + std::map >::iterator it, e; + for (it = paths.begin(), e = paths.end(); it != e; it++) { + std::string fnName = it->first; + pathsString += decorateName(fnName); + std::vector &path_ = it->second; + std::string pathString = + DecisionTree::generateDecisionTreePathString(path_); + pathsString += pathString + "\n"; + } + pathsString += "}"; + return pathsString; +} + +void ModuleDecisionTrees::parseMdtResults( + std::map > &results, + std::string &resString) { + results.clear(); + int len = (int)resString.size(); + if (!len) + return; + int pos = 0; + bool started = false; + for (;;) { + char c = resString[pos]; + if (c == '\n' || c == '\r') { + pos++; + continue; + } + if (c == '{' && !started) { + started = true; + pos++; + continue; + } + if (c == '}') + return; + std::string name = undecorateName(resString, pos); + std::vector res; + DecisionTree::parseResultsString(res, resString, pos); + results[name] = res; + if (pos >= len) + return; + } +} + +std::string ModuleDecisionTrees::generateMdtResultsString( + std::map > &results) +{ + std::string resultsString = "{\n"; + std::map >::iterator it, e; + for (it = results.begin(), e = results.end(); it != e; it++) { + std::string fnName = it->first; + resultsString += decorateName(fnName); + std::vector &results = it->second; + std::string resString = + DecisionTree::generateResultsString(results); + resultsString += resString + "\n"; + } + resultsString += "}"; + return resultsString; +} + +std::string ModuleDecisionTrees::decorateName(std::string &name) { + std::string decoratedName = "{" + name + "}"; + return decoratedName; +} + +std::string ModuleDecisionTrees::undecorateName(std::string &s, int &position) { + std::string undecoratedName; + int i = position; + int len = (int)s.size(); + bool started = false; + for (i = position; i < len; i++) { + char c = s[i]; + if (c == '\n' || c == '\r') + continue; + if (c == '{') { + if (started) + return undecoratedName; + started = true; + continue; + } + if (c == '}') { + if (!started) + return undecoratedName; + position = i + 1; + break; + } + undecoratedName += c; + } + return undecoratedName; +} + +int ModuleDecisionTrees::calculateTotalFitness( + std::map > &results) { + int tf = 0; + std::map >::iterator it, e; + for (it = results.begin(), e = results.end(); it != e; it++) { + const std::string &key = it->first; + int n = (int)key.size(); + if (n < 2) + continue; + if (key[n - 2] == '.' && key[n - 1] == '2') { + std::vector &r = it->second; + if (r.empty()) + continue; + tf += r.back(); + } + } + return tf; +} + +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() { + std::map::iterator it, e; + it = DecisionTreeProxies.begin(), e = DecisionTreeProxies.end(); + for (; it != e; it++) { + DecisionTreeProxy *dtp = it->second; + delete dtp; + } +} + +void ModuleDecisionTreeProxies::setCurrentFunctionAndPhase( + const std::string &fnName, + ModuleDecisionTrees::IterativeCompilationPhase phase) { + ICPhase = phase; + if (!IterativeCompilation) { + CurrFnDecisionTreeProxy = 0; + return; + } + std::string id; + switch(phase) { + case ModuleDecisionTrees::FunctionPhase: + id = fnName + ".0"; + break; + case ModuleDecisionTrees::ModulePhase: + id = "module-id"; + break; + case ModuleDecisionTrees::CodeGenPhase: + id = fnName + ".2"; + break; + default: + assert(0 && "bad iterative compilation phase"); + } + CurrFnDecisionTreeProxy = &getDecisionTreeProxy(id); +} + +DecisionTreeProxy &ModuleDecisionTreeProxies::getDecisionTreeProxy( + const std::string &name) { + if (DecisionTreeProxies.find(name) == DecisionTreeProxies.end()) + DecisionTreeProxies[name] = new DecisionTreeProxy(); + + return *DecisionTreeProxies[name]; +} + +void ModuleDecisionTreeProxies::setPaths(std::map > &paths) { + std::map >::iterator it, e; + for (it = paths.begin(), e = paths.end(); it != e; it++) { + std::string name = it->first; + std::vector &path = it->second; + DecisionTreeProxy &dtp = getDecisionTreeProxy(name); + dtp.setPath(path); + } +} + +void ModuleDecisionTreeProxies::getResults(std::map > &results) { + results.clear(); + std::map::iterator it, e; + it = DecisionTreeProxies.begin(), e = DecisionTreeProxies.end(); + for (; it != e; it++) { + std::string name = it->first; + DecisionTreeProxy &dtp = *(it->second); + std::vector res = dtp.getResults(); + results[name] = res; + } +} + +bool ModuleDecisionTreeProxies::doInitialization(Module &M) { + if (IterativeCompilationOpt) { + IterativeCompilation = true; + std::string mdtPathsString = DecisionTree::readFromFile(FicInputFile); + std::map > mdtPaths; + ModuleDecisionTrees::parseMdtPaths(mdtPaths, mdtPathsString); + setPaths(mdtPaths); + } + return true; +} + +bool ModuleDecisionTreeProxies::doFinalization(Module &M) { + if (IterativeCompilationOpt) { + std::map > results; + getResults(results); + std::string resultsStr = ModuleDecisionTrees::generateMdtResultsString(results); + if (ICPhase != ModuleDecisionTrees::CodeGenPhase) + DecisionTree::writeToFile(FicResultsFile, resultsStr); + else + DecisionTree::writeToFile(FicResultsFile2, resultsStr); + } + return true; +} + +bool ModuleDecisionTreeProxies::getDecision(int priority) +{ + if (!CurrFnDecisionTreeProxy) + return false; + return CurrFnDecisionTreeProxy->getDecision(priority); +} 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(), + // ModuleDecisionTrees::FunctionPhase); + MD->setCurrentFunctionAndPhase("", ModuleDecisionTrees::ModulePhase); + 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/Target/Mips/CMakeLists.txt =================================================================== --- lib/Target/Mips/CMakeLists.txt +++ lib/Target/Mips/CMakeLists.txt @@ -28,6 +28,7 @@ MipsConstantIslandPass.cpp MipsDelaySlotFiller.cpp MipsFastISel.cpp + MipsFunctionFitness.cpp MipsJITInfo.cpp MipsInstrInfo.cpp MipsISelDAGToDAG.cpp Index: lib/Target/Mips/Mips.h =================================================================== --- lib/Target/Mips/Mips.h +++ lib/Target/Mips/Mips.h @@ -29,6 +29,7 @@ FunctionPass *createMipsJITCodeEmitterPass(MipsTargetMachine &TM, JITCodeEmitter &JCE); 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,87 @@ +//===-- 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" +#include + +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(); + //std::string n = fnName + ".2"; + ModuleDecisionTreeProxies &proxies = + getAnalysis(); + //DecisionTreeProxy &proxy = proxies.getDecisionTreeProxy(n); + proxies.setCurrentFunctionAndPhase(fnName, ModuleDecisionTrees::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 @@ -184,6 +184,7 @@ bool MipsPassConfig::addPreEmitPass() { MipsTargetMachine &TM = getMipsTargetMachine(); addPass(createMipsDelaySlotFillerPass(TM)); + addPass(createMipsFunctionFitnessPass()); addPass(createMipsLongBranchPass(TM)); addPass(createMipsConstantIslandPass(TM)); return true; Index: lib/Transforms/IPO/InlineAlways.cpp =================================================================== --- lib/Transforms/IPO/InlineAlways.cpp +++ lib/Transforms/IPO/InlineAlways.cpp @@ -67,6 +67,7 @@ "Inliner for always_inline functions", false, false) 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 @@ -75,6 +75,7 @@ "Function Integration/Inlining", false, false) 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 @@ -18,6 +18,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/InlineCost.h" +#include "llvm/Analysis/DecisionTree.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DiagnosticInfo.h" @@ -74,6 +75,7 @@ /// 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(); CallGraphSCCPass::getAnalysisUsage(AU); } @@ -330,7 +332,17 @@ } Function *Caller = CS.getCaller(); - if (!IC) { + bool doInlinging = (bool)IC; + + int t = MaxDtPriority - abs(IC.getCostDelta()); + bool decision = false; + if (t >= 0) { + decision = MDTP->getDecision(t); + } + if (decision) + doInlinging = !doInlinging; + + if (!doInlinging) { DEBUG(dbgs() << " NOT Inlining: cost=" << IC.getCost() << ", thres=" << (IC.getCostDelta() + IC.getCost()) << ", Call: " << *CS.getInstruction() << "\n"); @@ -440,6 +452,8 @@ bool Inliner::runOnSCC(CallGraphSCC &SCC) { CallGraph &CG = getAnalysis().getCallGraph(); + MDTP = &getAnalysis(); + MDTP->setCurrentFunctionAndPhase("", ModuleDecisionTrees::ModulePhase); DataLayoutPass *DLP = getAnalysisIfAvailable(); const DataLayout *DL = DLP ? &DLP->getDataLayout() : nullptr; const TargetLibraryInfo *TLI = getAnalysisIfAvailable(); Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -196,6 +196,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 MPM.add(createLoopRotatePass()); // Rotate Loop MPM.add(createLICMPass()); // Hoist loop invariants MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3)); 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" @@ -86,6 +87,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequiredID(LoopSimplifyID); AU.addPreservedID(LoopSimplifyID); @@ -111,6 +113,7 @@ const DataLayout *DL; // DataLayout for constant folding. 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. @@ -206,6 +209,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(LoopInfo) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_DEPENDENCY(LCSSA) @@ -230,6 +234,7 @@ LI = &getAnalysis(); AA = &getAnalysis(); DT = &getAnalysis().getDomTree(); + MDTP = &getAnalysis(); DataLayoutPass *DLP = getAnalysisIfAvailable(); DL = DLP ? &DLP->getDataLayout() : nullptr; @@ -406,6 +411,8 @@ // constants, it is technically hoistable, but it would be better to just // fold it. if (Constant *C = ConstantFoldInstruction(&I, DL, TLI)) { + if (MDTP->getDecision(MaxDtPriority / 2)) + continue; DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n'); CurAST->copyValue(&I, C); CurAST->deleteValue(&I); @@ -420,7 +427,8 @@ // if (CurLoop->hasLoopInvariantOperands(&I) && canSinkOrHoistInst(I) && isSafeToExecuteUnconditionally(I)) - hoist(I); + if (!MDTP->getDecision(MaxDtPriority / 2)) + hoist(I); } const std::vector &Children = N->getChildren();