Index: include/llvm/Analysis/ICDecisionTree.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ICDecisionTree.h @@ -0,0 +1,166 @@ +//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the decision tree and decision tree proxy classes +// which are used in iterative compilation. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ICDECISIONTREE_H +#define LLVM_ANALYSIS_ICDECISIONTREE_H + +#include +#include +#include +#include "llvm/ADT/BitVector.h" +#include "llvm/Pass.h" +#include "llvm/Analysis/ICUtils.h" + +namespace llvm { + +struct DecisionTreeNode { + DecisionTreeNode(); + DecisionTreeNode(DecisionTreeNode *parent, int id); + int calcFinalPriority(int bestFunctionFitness); + DecisionTreeNode *Parent; + DecisionTreeNode *PrimaryDecision; + DecisionTreeNode *AlternativeDecision; + int Priority; + int Fitness; + int Depth; + int NodeId; + bool IsInterprocedural; + ICOptimization Optimization; + + std::string getJSON(); + + bool operator==(const DecisionTreeNode &other) const; + bool operator!=(const DecisionTreeNode &other) const; + bool operator>(const DecisionTreeNode &other) const; + bool operator<(const DecisionTreeNode &other) const; + bool operator>=(const DecisionTreeNode &other) const; + bool operator<=(const DecisionTreeNode &other) const; +}; + +class NodeList { + public: + int size(); + void add(DecisionTreeNode *node); + DecisionTreeNode* getFront() { return storage.front(); } + DecisionTreeNode* choice(); + void clear() { storage.clear(); } + std::vector getStorage() {return storage;} + + protected: + std::vector storage; +}; + +class NodeSelector { + public: + virtual void add(DecisionTreeNode *node) = 0; + virtual DecisionTreeNode* selectNode() = 0; + virtual ~NodeSelector() {}; +}; + +class NodeSelectorRR : public NodeSelector { + public: + NodeSelectorRR(); + + void add(DecisionTreeNode *node); + DecisionTreeNode* selectNode(); + + NodeList getList(ICOptimization optim); + ICOptimization bestOptim(); + int countEmptyLists(); + int countUsedOptims(); + ~NodeSelectorRR(); + + protected: + std::map lists; + std::map usedOptims; + void clearLists(); + void updateUsedOptims(); + void resetUsedOptims(); +}; + +class NodeSelectorSimple : public NodeSelector { + public: + NodeSelectorSimple(); + + void add(DecisionTreeNode *node); + DecisionTreeNode* selectNode(); + + ~NodeSelectorSimple(); + + protected: + NodeList list; +}; + +/// Decision tree controls the iterative compilation process so +/// that compiler takes different path in each compilation except in +/// the final iteration when the path which generates the best code is taken . +class DecisionTree { +protected: + DecisionTreeNode *DecisionTreeRoot; + DecisionTreeNode *CurrentNode; + DecisionTreeNode *LastSelectedNode; + BitVector Path; + SmallVector Optimizations; + int FunctionFitness; + int BestFunctionFitness; + BitVector BestPath; + int NodeIdCount; + NodeSelector *selector; + +public: + DecisionTree(); + ~DecisionTree(); + + int getFunctionFitness() const { return FunctionFitness; } + void setFunctionFitness(int x) { FunctionFitness = x; } + int getBestFunctionFitness() { return BestFunctionFitness; } + BitVector &getPath() { return Path; } + const BitVector &getPath() const { return Path; } + SmallVector &getOptimizations() + { return Optimizations; } + const SmallVector &getOptimizations() + const { return Optimizations; } + int getNodeIdCount() {return NodeIdCount;} + DecisionTreeNode* getCurrentNode() {return CurrentNode;} + + bool getDecision(int priority, ICOptimization opt); + void updateBestFunctionFitness(int iteration); + void findPath(DecisionTreeNode *node, BitVector &path); + bool selectPath(bool FinalPass); + DecisionTreeNode* selectNode(); + void startNewIteration(); + void updateNodesFitness(); + DecisionTreeNode* getLastSelectedNode() { return LastSelectedNode; } + + void applyResults(const MdtResults &results); + + void splitPath( + const BitVector &paths, + BitVector &pathBeforeCodegen, + BitVector &pathAfterCodegen); + + void dumpToGv(int currentIteration); + std::string getJSON(); + void dumpToJSON(int currentIteration); + + void addPrimaryDecision(); + void addPrimaryDecision(llvm::DecisionTreeNode *node); + void addAlternativeDecision(); + void addAlternativeDecision(llvm::DecisionTreeNode *node); + llvm::DecisionTreeNode* getRootNode(); +}; + +} + +#endif Index: include/llvm/Analysis/ICFileUtils.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ICFileUtils.h @@ -0,0 +1,73 @@ +#ifndef LLVM_ANALYSIS_ICFILEUTILS_H +#define LLVM_ANALYSIS_ICFILEUTILS_H + +#include "llvm/ADT/BitVector.h" +#include "llvm/Analysis/ICUtils.h" +#include +#include +#include + +namespace llvm { + +class ICFile { +public: + ICFile() {} + ICFile(std::string filename) { this->filename = filename;} + ICFile(std::string filePrefix, int iteration); + virtual ~ICFile() {}; + + SmallString<128> createTmpFile(std::string filename, int CurrentIteration); + void writeToFile(const std::string &fileName, const std::string &data); + std::string readFromFile(const std::string &fileName); + + bool exists(); + void remove(); + + std::string getFilename() { return filename; } + + virtual void write() = 0; + virtual bool read() = 0; + +protected: + std::string filename; +}; + +class ICInputFile : public ICFile { +public: + ICInputFile() {} + ICInputFile(std::string filename) : ICFile(filename) {} + ICInputFile(std::string filePrefix, int iteration) + : ICFile(filePrefix, iteration) {} + ~ICInputFile() {} + + ICPathsMap getPaths() {return this->paths;} + void setPaths(ICPathsMap paths) { this->paths = paths;} + + void write(); + bool read(); + +private: + ICPathsMap paths; +}; + +class ICResultsFile : public ICFile { +public: + ICResultsFile() {} + ICResultsFile(std::string filename) : ICFile(filename) {} + ICResultsFile(std::string filePrefix, int iteration) + : ICFile(filePrefix, iteration) {} + ~ICResultsFile() {} + + std::vector getResults() {return this->results;} + void setResults(std::vector results) { this->results = results;} + + void write(); + bool read(); + +private: + std::vector results; +}; +} + + +#endif Index: include/llvm/Analysis/ICPass.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ICPass.h @@ -0,0 +1,69 @@ +//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the decision tree and decision tree proxy classes +// which are used in iterative compilation. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ICPASS_H +#define LLVM_ANALYSIS_ICPASS_H + +#include +#include +#include +#include "llvm/ADT/BitVector.h" +#include "llvm/Pass.h" +#include "llvm/Analysis/ICUtils.h" +#include "llvm/Analysis/ICDecisionTree.h" +#include "llvm/Analysis/ICProxies.h" + +namespace llvm { + +/// This ImmutablePass provides a persistent place to hold the +/// decision trees proxies (for each function and for each +/// compilation phase) during the iterative compilation process so +/// they can be easily accessed from passes which can take advantage +/// of iterative compilation. +class ModuleDecisionTreeProxies : public ImmutablePass { +public: + static char ID; + + ModuleDecisionTreeProxies(); + ~ModuleDecisionTreeProxies(); + virtual bool doInitialization(Module &M); + virtual bool doFinalization(Module &M); + + bool getDecision(int priority, ICOptimization opt); + + void setCurrentFunctionAndPhase(const std::string &fnName, + FnNameAndPhase::ICPhase phase); + void setModuleCompilationPhase(); + DecisionTreeProxy &getDecisionTreeProxy(const FnNameAndPhase &x); + DecisionTreeProxy &getDecisionTreeProxy(const std::string &name, + FnNameAndPhase::ICPhase phase); + void setPaths(std::map &paths); + void getResults(std::vector &results) const; + DecisionTreeProxy *getCurrFnDecisionTreeProxy() + { return CurrFnDecisionTreeProxy; } + bool getIterativeCompilation() { return IterativeCompilation; } + void setIterativeCompilation(bool iterative) { + IterativeCompilation = iterative; + } +protected: + bool IterativeCompilation; + bool ParallelExplore; + std::map DecisionTreeProxies; + DecisionTreeProxy *CurrFnDecisionTreeProxy; + FnNameAndPhase::ICPhase ICPhase; +}; + +} + +#endif Index: include/llvm/Analysis/ICProxies.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ICProxies.h @@ -0,0 +1,123 @@ +//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the decision tree and decision tree proxy classes +// which are used in iterative compilation. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ICPROXIES_H +#define LLVM_ANALYSIS_ICPROXIES_H + +#include +#include +#include +#include "llvm/ADT/BitVector.h" +#include "llvm/Pass.h" +#include "llvm/Analysis/ICUtils.h" +#include "llvm/Analysis/ICDecisionTree.h" +#include "llvm/Analysis/ICFileUtils.h" + +namespace llvm { + +/// Decision tree proxy is the proxy class for the decision tree so +/// that it has the method getDecision and the all data can be effectively +/// streamed between proxy and the decision tree. +class DecisionTreeProxy { +public: + DecisionTreeProxy(); + + BitVector &getPath() { return Path; } + const BitVector &getPath() const { return Path; } + int getFunctionFitness() const { return FunctionFitness; } + void setFunctionFitness(int x) { FunctionFitness = x; } + + std::vector &getPriorities() { return Priorities; } + const std::vector &getPriorities() const { return Priorities; } + + std::vector &getOptimizations() { return Optimizations; } + const std::vector &getOptimizations() const { + return Optimizations; } + + bool getDecision(int priority, ICOptimization opt); + + std::string generateResultsString(); + MdtResults getResults() const; + void setPath(const BitVector &path); + +protected: + BitVector Path; + int FunctionFitness; + int BestFunctionFitness; + std::vector 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(int totalIters = -1, bool parallel = false, std::string filename = ""); + ~ModuleDecisionTrees(); + + DecisionTree &getDecisionTree(const FnNameAndPhase &fnNameAndPhase); + + void startNewIteration(); + void getPaths(ICPathsMap &paths); + void applyResults(const std::vector &results); + void setFunctionFitness(int totalFitness); + void updateBestFunctionFitness(int iteration); + void updateNodesFitness(); + void selectPath(bool FinalPass); + void splitPaths( + const ICPathsMap &paths, + ICPathsMap &pathBeforeCodegen, + ICPathsMap &pathAfterCodegen); + void splitPathsMap( + const ICPathsMap &paths, + ICPathsMap &pathsBeforeCodegen, + ICPathsMap &pathsAfterCodegen); + void showTrees(); + std::string &getICInputFileOpt() { return ICInputFileOpt; } + std::string &getICInputFile2Opt() { return ICInputFile2Opt; } + std::string &getICResultsFileOpt() { return ICResultsFileOpt; } + std::string &getICResultsFile2Opt() { return ICResultsFile2Opt; } + FnNameAndPhase::ICPhase getCurrentPhase(); + + ICInputFile &getICInputFile() { return input1; } + ICInputFile &getICInputFile2() { return input2; } + ICResultsFile &getICResultsFile() { return results1; } + ICResultsFile &getICResultsFile2() { return results2; } + std::map &getDecisionTrees() { + return DecisionTrees; + } + void log(); + +protected: + int NumberOfIterations; + int CurrentIteration; + bool ParallelExplore; + std::map DecisionTrees; + std::string ICInputFileOpt; + std::string ICInputFile2Opt; + std::string ICResultsFileOpt; + std::string ICResultsFile2Opt; + std::string ModuleName; + + ICInputFile input1; + ICInputFile input2; + ICResultsFile results1; + ICResultsFile results2; +}; + +} + +#endif Index: include/llvm/Analysis/ICSetCurrentFunc.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ICSetCurrentFunc.h @@ -0,0 +1,42 @@ +//===-- ICSetCurrentFunc.h - Iterative Comp Set Current Func DT -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Implements the pass which sets the decision tree proxy of the +// current function. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ICSETCURRENTFUNC_H +#define LLVM_ANALYSIS_ICSETCURRENTFUNC_H + +#include "llvm/Pass.h" +#include "llvm/Analysis/IterativeCompilation.h" + +namespace llvm { + +class ICSetCurrentFunc : public FunctionPass { +public: + std::string name; + ModuleDecisionTreeProxies *MD; + static char ID; + ICSetCurrentFunc() : FunctionPass(ID) { + initializeICSetCurrentFuncPass(*PassRegistry::getPassRegistry()); + } + + virtual bool runOnFunction(Function &F); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); + } +}; + +} + +#endif Index: include/llvm/Analysis/ICUtils.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ICUtils.h @@ -0,0 +1,132 @@ +//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the decision tree and decision tree proxy classes +// which are used in iterative compilation. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ICUTILS_H +#define LLVM_ANALYSIS_ICUTILS_H + +#include +#include "llvm/Support/CommandLine.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/BitVector.h" +#include +#include + +namespace llvm { + +extern cl::opt IterativeCompilationOpt; +extern cl::opt FicInputFile; +extern cl::opt FicInputFile2; +extern cl::opt FicResultsFile; +extern cl::opt FicResultsFile2; + +/// Iterative Compilation Optimization +enum ICOptimization { + NoOptimization, + InlinerOpt, + LicmOpt, + RegAllocOpt, + ErrOpt = -1 +}; + +enum ICExploreAlg { + Sequential, + RoundRobin, + Parallel +}; + +const int MaxDtPriority = 1000; +extern bool UseRand; +extern ICExploreAlg ExploreAlg; + +class FnNameAndPhase { +public: + + /// Iterative Compilation Phase + enum ICPhase { + FunctionPhase, /// Function level phase include passes that operate + /// with the target independent IR like LICM. In this + /// phase there is one decision tree for each function. + + ModulePhase, /// Module level phase include interprocedural optimizations + /// like function inliner. In this phase there is only one + /// decision tree for the whole module. + + CodeGenPhase /// Codegen phase include passes like register allocator, + /// scheduler and instruction selection. In this + /// phase there is also one decision tree for each function. + }; + + FnNameAndPhase() : Phase(ModulePhase) {} + FnNameAndPhase(const FnNameAndPhase &x) : Name(x.Name), Phase(x.Phase) + {} + FnNameAndPhase(const std::string &name, ICPhase phase) + : Name(name), Phase(phase) {} + + bool operator < (const FnNameAndPhase &x) const { + if (Phase != x.Phase) + return Phase < x.Phase; + return Name < x.Name; + } + + const std::string &getName() const { return Name; } + ICPhase getPhase() const { return Phase; } + +protected: + std::string Name; + ICPhase Phase; +}; + +class MdtResults { +public: + FnNameAndPhase FunctionNameAndPhase; + int Fitness; + std::vector Priorities; + std::vector Optimizations; + + static bool parseMdtResults( + std::vector &results, + const std::string &resString, + std::string &ErrorMessage); + + static std::string generateMdtResultsString( + const std::vector &results); + + static void mergeMdtResults(std::vector &mergedResults, + const std::vector &results1, + const std::vector &results2); + + static int calculateTotalFitness(const std::vector &results); + static MdtResults* getByPhase(const std::vector &results, + FnNameAndPhase::ICPhase phase); +}; + +typedef std::map ICPathsMap; + +//-------- convert to and from string ----// +std::string BitVector2Str(const BitVector &path); +std::string Path2Str(const FnNameAndPhase &nameAndPhase, const BitVector &path); + +//--------- parsers and generators --------// +bool parseMdtPaths(ICPathsMap &paths, + const std::string &pathString, + std::string &ErrorMessage); + +std::string generateMdtPathsString(const ICPathsMap &paths); + +std::string getModuleName(int argc, const char **argv); + +} + + +#endif Index: include/llvm/Analysis/IterativeCompilation.h =================================================================== --- /dev/null +++ include/llvm/Analysis/IterativeCompilation.h @@ -0,0 +1,10 @@ +#ifndef LLVM_ANALYSIS_ITERATIVECOMPILATION_H +#define LLVM_ANALYSIS_ITERATIVECOMPILATION_H + +#include "llvm/Analysis/ICUtils.h" +#include "llvm/Analysis/ICDecisionTree.h" +#include "llvm/Analysis/ICProxies.h" +#include "llvm/Analysis/ICPass.h" +#include "llvm/Analysis/ICFileUtils.h" + +#endif Index: include/llvm/Analysis/Passes.h =================================================================== --- include/llvm/Analysis/Passes.h +++ include/llvm/Analysis/Passes.h @@ -96,6 +96,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 @@ -331,6 +331,9 @@ void initializeLoopVersioningPassPass(PassRegistry &); void initializeWholeProgramDevirtPass(PassRegistry &); void initializePatchableFunctionPass(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 DataLayout; 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. @@ -66,6 +67,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 @@ -33,6 +33,7 @@ class PredIteratorCache; class ScalarEvolution; class TargetLibraryInfo; +class ModuleDecisionTreeProxies; /// \brief Captures loop safety information. /// It keep information for loop & its header may throw exception. @@ -350,7 +351,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 @@ -361,7 +362,7 @@ /// loop and loop safety information as arguments. It returns changed status. bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + LICMSafetyInfo *, ModuleDecisionTreeProxies *); /// \brief Try to promote memory values to scalars by sinking stores out of /// the loop and moving loads to before the loop. We do this by looping over Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -73,6 +73,7 @@ initializeTargetTransformInfoWrapperPassPass(Registry); initializeTypeBasedAAWrapperPassPass(Registry); initializeScopedNoAliasAAWrapperPassPass(Registry); + initializeModuleDecisionTreeProxiesPass(Registry); } void LLVMInitializeAnalysis(LLVMPassRegistryRef R) { Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -19,6 +19,11 @@ CostModel.cpp CodeMetrics.cpp ConstantFolding.cpp + ICUtils.cpp + ICFileUtils.cpp + ICDecisionTree.cpp + ICPass.cpp + ICProxies.cpp Delinearization.cpp DemandedBits.cpp DependenceAnalysis.cpp Index: lib/Analysis/ICDecisionTree.cpp =================================================================== --- /dev/null +++ lib/Analysis/ICDecisionTree.cpp @@ -0,0 +1,651 @@ +//===-- 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/ICDecisionTree.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/SourceMgr.h" +#include "llvm/Support/YAMLParser.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/ErrorHandling.h" +#include +#include +#include +#include + +using namespace llvm; + +DecisionTreeNode::DecisionTreeNode() { + Parent = NULL; + PrimaryDecision = NULL; + AlternativeDecision = NULL; + Priority = 0; + Optimization = NoOptimization; + Fitness = INT_MAX; + Depth = 0; + NodeId = 0; + IsInterprocedural = false; +} + +DecisionTreeNode::DecisionTreeNode(DecisionTreeNode *parent, int id) { + Parent = parent; + PrimaryDecision = NULL; + AlternativeDecision = NULL; + Priority = 0; + Optimization = NoOptimization; + Fitness = INT_MAX; + Depth = parent->Depth+1; + NodeId = id; + IsInterprocedural = false; +} + +DecisionTree::DecisionTree() { + DecisionTreeRoot = new DecisionTreeNode; + NodeIdCount = 1; + FunctionFitness = 0; + BestFunctionFitness = INT_MAX; + CurrentNode = DecisionTreeRoot; + + if(llvm::ExploreAlg == llvm::ICExploreAlg::RoundRobin || + llvm::ExploreAlg == llvm::ICExploreAlg::Parallel) { + selector = new NodeSelectorRR(); + } + else { + selector = new NodeSelectorSimple(); + } +} + +DecisionTree::~DecisionTree() { + delete DecisionTreeRoot; +} + +/// This is the function which controls iterative compilation process. +bool DecisionTree::getDecision(int priority, ICOptimization opt) { + unsigned depth = CurrentNode->Depth; + bool decision; + + // If depth is less then the size of the given path, follow this path. + if (depth < Path.size()) { + decision = Path[depth]; + if (decision) { + if (CurrentNode->AlternativeDecision) { + CurrentNode = CurrentNode->AlternativeDecision; + return decision; + } + } else { + if (CurrentNode->PrimaryDecision) { + CurrentNode = CurrentNode->PrimaryDecision; + return decision; + } + } + } + + // Update current node + if(opt != NoOptimization) { + CurrentNode->Priority = priority; + CurrentNode->Optimization = opt; + } + + // Create the new decision tree node + DecisionTreeNode *newNode = new DecisionTreeNode(CurrentNode, NodeIdCount++); + + // Insert the new node in the decision tree. + if (CurrentNode->PrimaryDecision == 0) { + CurrentNode->PrimaryDecision = newNode; + decision = false; + } else { + CurrentNode->AlternativeDecision = newNode; + decision = true; + } + CurrentNode = newNode; + + return decision; +} + +/// Updated best function fitness seen so far. +void DecisionTree::updateBestFunctionFitness(int iteration) { + if (FunctionFitness < BestFunctionFitness) { + BestFunctionFitness = FunctionFitness; + findPath(CurrentNode, BestPath); + } + updateNodesFitness(); +} + +/// Find path which leads to the given node. +void DecisionTree::findPath(DecisionTreeNode *node, BitVector &path) { + path.resize(node->Depth); + if (node->PrimaryDecision) + path.resize(node->Depth + 1, true); + while (node != DecisionTreeRoot) { + DecisionTreeNode *parent = node->Parent; + if (node == parent->AlternativeDecision) + path[parent->Depth] = true; + else + path[parent->Depth] = false; + node = parent; + } +} + +/// Select path for the new iteration. In the final iteration use +/// the best path so far. +bool DecisionTree::selectPath(bool FinalPass) { + if (FinalPass) { + Path = BestPath; + puts("Returning best function fintess"); + return true; + } + DecisionTreeNode *selectedNode = selectNode(); + + if (selectedNode) { + LastSelectedNode = selectedNode; + findPath(selectedNode, Path); + return false; + } else { + Path = BestPath; + return true; + } +} + +DecisionTreeNode* DecisionTree::selectNode() { + SmallVector nodesToExplore; + DecisionTreeNode *selectedNode = 0; + + // if tree is empty, select root node + if (!DecisionTreeRoot->AlternativeDecision + && !DecisionTreeRoot->PrimaryDecision) + return DecisionTreeRoot; + + // start exploring from root node + nodesToExplore.push_back(DecisionTreeRoot); + while(!nodesToExplore.empty()) { + // get node + DecisionTreeNode *n = nodesToExplore.back(); + nodesToExplore.pop_back(); + // if we have only primary decision + if (n->AlternativeDecision == 0 && n->PrimaryDecision != 0) { + selector->add(n); + } + + // if we have alternative decision + if (n->AlternativeDecision) + nodesToExplore.push_back(n->AlternativeDecision); + // if we have primary decision + if (n->PrimaryDecision) + nodesToExplore.push_back(n->PrimaryDecision); + } + + selectedNode = selector->selectNode(); + + return selectedNode; +} + +/// Prepare decision tree for the new iteration. +void DecisionTree::startNewIteration() { + CurrentNode = DecisionTreeRoot; + FunctionFitness = 0; +} + +/// Update fitness field of the nodes on the current path. +void DecisionTree::updateNodesFitness() { + DecisionTreeNode *n = CurrentNode; + while(n) { + if (n->Fitness > FunctionFitness) + n->Fitness = FunctionFitness; + n = n->Parent; + } +} + +/// Calculate modified priority so that the nodes on the paths which +/// generate better code are more often selected. +int DecisionTreeNode::calcFinalPriority(int bestFunctionFitness) { + if (Fitness == 0) + return Priority; + return ((long)Priority * bestFunctionFitness) / Fitness; +} + +/// Apply results from the decision tree proxy so that the +/// path for the next iteration can be selected. +void DecisionTree::applyResults(const MdtResults &results) { + unsigned pathLen = Path.size(); + int nOptimizations = (int)results.Optimizations.size(); + unsigned nPriorities = results.Priorities.size(); + + // recreate tree structure + for (unsigned i = 0; i < pathLen; i++) { + getDecision(0, NoOptimization); + } + + // actually apply results + for (unsigned i = 0; i < nPriorities; i++) { + getDecision(results.Priorities[i], results.Optimizations[i]); + } + setFunctionFitness(results.Fitness); +} + +void DecisionTree::splitPath( + const BitVector &path, + BitVector &pathBeforeCodegen, + BitVector &pathAfterCodegen) { + + pathBeforeCodegen.clear(); + pathAfterCodegen.clear(); + + CurrentNode = DecisionTreeRoot; + unsigned pathLen = path.size(); + + for (unsigned i = 0; i < pathLen; i++) { + assert(CurrentNode); + + unsigned depth = CurrentNode->Depth; + bool decision = path[depth]; + assert(depth < path.size()); + + if (CurrentNode->Optimization <= LicmOpt) { + pathBeforeCodegen.resize(pathBeforeCodegen.size() + 1, decision); + } + else { + pathAfterCodegen.resize(pathAfterCodegen.size() + 1, decision); + } + + if (decision) + CurrentNode = CurrentNode->AlternativeDecision; + else + CurrentNode = CurrentNode->PrimaryDecision; + } + + CurrentNode = DecisionTreeRoot; +} + +void DecisionTree::dumpToGv(int currentIteration) { + DecisionTreeNode *n; + SmallVector paths; + + std::stringstream path; + path << "/tmp/ic-tree-" << currentIteration << ".gv"; + + std::ofstream f(path.str()); + + f << "digraph G {\n"; + + paths.push_back(DecisionTreeRoot); + while(!paths.empty()) + { + n = paths.back(); + paths.pop_back(); + + + while(n->PrimaryDecision) { + f << "n" << n->NodeId << " -> " << "n" << n->PrimaryDecision->NodeId << ";\n"; + + if(n->AlternativeDecision) + { + paths.push_back(n->AlternativeDecision); + f << "n" << n->NodeId << " -> " << "n" << n->AlternativeDecision->NodeId + << "[weight=0];\n"; + } + n = n->PrimaryDecision; + } + } + + f << "}"; + f.close(); +} +std::string DecisionTreeNode::getJSON() { + std::stringstream res; + + res << "{"; + res << " \"id\" : " << NodeId << ","; + res << " \"priority\" : " << Priority << ","; + res << " \"fitness\" : " << Fitness << ","; + res << " \"depth\" : " << Depth << ","; + res << " \"optim\" : " << Optimization; + res << "}"; + + return res.str(); +} + +std::string DecisionTree::getJSON() { + std::stringstream JSON; + DecisionTreeNode *n; + SmallVector paths; + + JSON << "[\n"; + + paths.push_back(DecisionTreeRoot); + while(!paths.empty()) + { + // this is path root + // start new path + n = paths.back(); + + if(n->Parent) + JSON << "\n\t{\n\t\"root\" : " << n->Parent->getJSON() << ","; + else + JSON << "\n\t{\n\t\"root\" : " << n->getJSON() << ","; + + JSON << "\n\t\"path\" : [\n"; + + paths.pop_back(); + + while(n->PrimaryDecision || n->AlternativeDecision) { + if(n->AlternativeDecision) { + // save new path entry point for later + paths.push_back(n->AlternativeDecision); + } + + if(n->PrimaryDecision) { + // we have regular primary decision, + // write it and continue + // get node as JSON and append it to current path + JSON << "\t\t" << n->getJSON(); + n = n->PrimaryDecision; + } + + if(n->PrimaryDecision) + JSON << ",\n"; + else + JSON << "\n"; + + } + + if(!paths.empty()) + JSON << "\t]},\n"; + else + JSON << "\t]}\n"; + } + + JSON << "]"; + + return JSON.str(); +} + +void DecisionTree::dumpToJSON(int currentIteration) { + std::stringstream filePath; + std::string JSON = getJSON(); + + filePath << "/tmp/ic-tree-" << currentIteration << ".json"; + std::ofstream f(filePath.str()); + + f << JSON; + + f.close(); +} +void DecisionTree::addPrimaryDecision() { + DecisionTreeNode *newNode = new DecisionTreeNode; + addPrimaryDecision(newNode); +} + +void DecisionTree::addPrimaryDecision(DecisionTreeNode *node) +{ + this->CurrentNode->PrimaryDecision = node; + node->Parent = this->CurrentNode; + node->Depth = this->CurrentNode->Depth + 1; + this->CurrentNode = node; +} + +void DecisionTree::addAlternativeDecision() { + DecisionTreeNode *newNode = new DecisionTreeNode; + addAlternativeDecision(newNode); +} + +void DecisionTree::addAlternativeDecision(DecisionTreeNode *node) +{ + this->CurrentNode->AlternativeDecision = node; + node->Parent = this->CurrentNode; + node->Depth = this->CurrentNode->Depth + 1; + this->CurrentNode = node; +} + +DecisionTreeNode* DecisionTree::getRootNode() { + return this->DecisionTreeRoot; +} + +NodeSelectorSimple::NodeSelectorSimple() { +} + +NodeSelectorSimple::~NodeSelectorSimple() { +} + +void NodeSelectorSimple::add(DecisionTreeNode *node) { + list.add(node); +} + +DecisionTreeNode* NodeSelectorSimple::selectNode(){ + return list.choice(); +} + +NodeSelectorRR::NodeSelectorRR() { + lists[LicmOpt] = NodeList(); + lists[InlinerOpt] = NodeList(); + lists[RegAllocOpt] = NodeList(); + + usedOptims[LicmOpt] = false; + usedOptims[InlinerOpt] = false; + usedOptims[RegAllocOpt] = false; +} + +NodeSelectorRR::~NodeSelectorRR() { +} + +int NodeSelectorRR::countUsedOptims() { + int cnt = 0; + + for(auto it : usedOptims) { + cnt += it.second == true; + } + + return cnt; +} + +void NodeSelectorRR::add(DecisionTreeNode *node) { + lists[node->Optimization].add(node); +} + +NodeList NodeSelectorRR::getList(ICOptimization optim) { + return lists[optim]; +} + +ICOptimization NodeSelectorRR::bestOptim() { + ICOptimization bestOptim; + DecisionTreeNode *currentBest = NULL; + + updateUsedOptims(); + + if(countEmptyLists() == 3) { + bestOptim = ErrOpt; + } + else { + for(auto it : usedOptims) { + if(it.second == true) { + continue; + } + if(currentBest == NULL || *lists[it.first].getFront() > *currentBest) { + currentBest = lists[it.first].getFront(); + } + } + bestOptim = currentBest->Optimization; + } + + return bestOptim; +} + +int NodeSelectorRR::countEmptyLists() { + int r = 0; + + for(auto it : lists) + r += it.second.size() == 0; + + return r; +} + +DecisionTreeNode* NodeSelectorRR::selectNode() { + ICOptimization opt = bestOptim(); + DecisionTreeNode *n; + + if(opt == ErrOpt) { + n = NULL; + } + else { + n = lists[opt].choice(); + usedOptims[opt] = true; + clearLists(); + } + + return n; +} + +void NodeSelectorRR::clearLists() { + for(auto &it : lists) { + it.second.clear(); + } +} + +void NodeSelectorRR::updateUsedOptims() { + if(countUsedOptims() == 3) + resetUsedOptims(); + + for(auto it : lists) { + if(it.second.size() == 0) { + usedOptims[it.first] = true; + } + } +} + +void NodeSelectorRR::resetUsedOptims() { + for(auto &it : usedOptims) { + it.second = false; + } +} + +int NodeList::size() { + return storage.size(); +} + +void NodeList::add(DecisionTreeNode *node) { + if(storage.size() != 0 && (*node > *storage.front())) { + storage.clear(); + } + + if(storage.size() == 0) { + storage.push_back(node); + } + else if(*node == *storage.front()){ + storage.push_back(node); + } +} + +DecisionTreeNode* NodeList::choice() { + int choice; + + if(UseRand) { + choice = time(NULL) % storage.size(); + } + else { + choice = 0; + } + + return storage[choice]; +} + +bool DecisionTreeNode::operator==(const DecisionTreeNode &other) const { + bool fitness = this->Fitness == other.Fitness; + bool priority = this->Priority == other.Priority; + + return fitness && priority; +} + +bool DecisionTreeNode::operator!=(const DecisionTreeNode &other) const { + return !(*this == other); +} + +bool DecisionTreeNode::operator>(const DecisionTreeNode &other) const { + bool retval; + + if(*this == other) retval = false; + else if(this->Fitness > other.Fitness) retval = false; + else if(this->Fitness < other.Fitness) retval = true; + else if(this->Fitness == other.Fitness && this->Priority > other.Priority) + retval = true; + + return retval; +} + +bool DecisionTreeNode::operator<(const DecisionTreeNode &other) const { + bool retval; + + if(*this == other) retval = false; + else retval = !(*this > other); + + return retval; +} Index: lib/Analysis/ICFileUtils.cpp =================================================================== --- /dev/null +++ lib/Analysis/ICFileUtils.cpp @@ -0,0 +1,98 @@ +#include "llvm/Analysis/ICFileUtils.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/ErrorOr.h" +#include "llvm/Support/MemoryBuffer.h" +#include + +using namespace llvm; + +ICFile::ICFile(std::string filePrefix, int iteration) { + filename = createTmpFile(filePrefix, iteration).c_str(); +} + +bool ICFile::exists() { + return llvm::sys::fs::exists(filename); +} + +void ICFile::remove() { + llvm::sys::fs::remove(filename); +} + +void ICInputFile::write() { + std::string pathsString; + pathsString = generateMdtPathsString(paths); + + writeToFile(filename, pathsString); +} + +bool ICInputFile::read() { + int res = 0; + + if(exists()) { + std::string err; + std::string pathsString = readFromFile(filename); + res = parseMdtPaths(paths, pathsString, err); + } + + return res; +} + +void ICResultsFile::write() { + std::string resultsString = MdtResults::generateMdtResultsString(results); + writeToFile(filename, resultsString); +} + +bool ICResultsFile::read() { + int parsed = 0; + + std::string err; + if(exists()) { + std::string resultsString = readFromFile(filename); + parsed = MdtResults::parseMdtResults(results, resultsString, err); + } + + if(!parsed) + llvm::errs() << "ITERATIVE COMPILATION ERROR:" << err << "\n"; + + return !parsed; +} + +SmallString<128> ICFile::createTmpFile(std::string filename, int CurrentIteration) +{ + std::string ErrMsg; + SmallString<128> Path; + std::stringstream fullFilename; + + fullFilename << filename << "-" << CurrentIteration; + + if(llvm::sys::fs::createTemporaryFile(fullFilename.str(), ".json", Path)) { + llvm::errs() << "Error creating temporary file: " << ErrMsg << "\n"; + } + + return Path; +} + +/// Write contents of the string to the file. +void ICFile::writeToFile(const std::string &fileName, const std::string &data) { + std::error_code EC; + raw_fd_ostream outf(fileName, EC, sys::fs::F_Text); + if (EC) { + report_fatal_error(Twine("can't open file: ") + fileName + + " (" + EC.message() + ")"); + } + outf << data; + outf.close(); +} + +/// Read contents of the file. +std::string ICFile::readFromFile(const std::string &fileName) { + llvm::ErrorOr> 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(); +} Index: lib/Analysis/ICPass.cpp =================================================================== --- /dev/null +++ lib/Analysis/ICPass.cpp @@ -0,0 +1,173 @@ +#include +#include +#include +#include +#include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/ICPass.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/SourceMgr.h" +#include "llvm/Support/YAMLParser.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/ErrorHandling.h" +#include + +using namespace llvm; + +INITIALIZE_PASS(ModuleDecisionTreeProxies, "module-decision-tree-proxies", + "Module Decision Tree Proxies", false, false) +char ModuleDecisionTreeProxies::ID = 0; + +ModuleDecisionTreeProxies::ModuleDecisionTreeProxies() +: ImmutablePass(ID), IterativeCompilation(false), + CurrFnDecisionTreeProxy(0) { + initializeModuleDecisionTreeProxiesPass(*PassRegistry::getPassRegistry()); +} + +ModuleDecisionTreeProxies::~ModuleDecisionTreeProxies() { + for (auto &P : DecisionTreeProxies) { + DecisionTreeProxy *dtp = P.second; + delete dtp; + } +} + +/// Sets decision tree proxy for current function and compilation phase. +void ModuleDecisionTreeProxies::setCurrentFunctionAndPhase( + const std::string &fnName, + FnNameAndPhase::ICPhase phase) { + ICPhase = phase; + if (!IterativeCompilation) { + CurrFnDecisionTreeProxy = 0; + return; + } + std::string id; + switch(phase) { + case FnNameAndPhase::FunctionPhase: + id = fnName + ".0"; + break; + case FnNameAndPhase::ModulePhase: + id = "module-id"; + break; + case FnNameAndPhase::CodeGenPhase: + id = fnName + ".2"; + break; + default: + assert(0 && "bad iterative compilation phase"); + } + CurrFnDecisionTreeProxy = &getDecisionTreeProxy(fnName, phase); +} + +/// Sets current compilation phase to module phase. +void ModuleDecisionTreeProxies::setModuleCompilationPhase() { + setCurrentFunctionAndPhase("module-id", FnNameAndPhase::ModulePhase); +} + +/// Find decision tree proxy for specified function and compilation phase. +DecisionTreeProxy &ModuleDecisionTreeProxies::getDecisionTreeProxy( + const FnNameAndPhase &x) { + if (DecisionTreeProxies.find(x) == DecisionTreeProxies.end()) + DecisionTreeProxies[x] = new DecisionTreeProxy(); + + return *DecisionTreeProxies[x]; +} + +/// Find decision tree proxy for specified function and compilation phase. +DecisionTreeProxy &ModuleDecisionTreeProxies::getDecisionTreeProxy( + const std::string &name, + FnNameAndPhase::ICPhase phase) { + return getDecisionTreeProxy(FnNameAndPhase(name, phase)); +} + +/// Set paths for all decision tree proxies. +void ModuleDecisionTreeProxies::setPaths(ICPathsMap &paths) { + for (const auto &P : paths) { + const FnNameAndPhase &fnNameAndPhase = P.first; + const BitVector &path = P.second; + DecisionTreeProxy &dtp = getDecisionTreeProxy(fnNameAndPhase); + dtp.setPath(path); + } +} + +/// Get results of this compiler iteration. Result include +/// measured function fitnesses and decision priorities. +void ModuleDecisionTreeProxies::getResults( + std::vector &results) const { + results.clear(); + for (const auto &P : DecisionTreeProxies) { + const FnNameAndPhase &fnNameAndPhase = P.first; + const DecisionTreeProxy &dtp = *P.second; + MdtResults res = dtp.getResults(); + res.FunctionNameAndPhase = fnNameAndPhase; + results.push_back(res); + } +} + +bool ModuleDecisionTreeProxies::doInitialization(Module &M) { + if (IterativeCompilationOpt) { + IterativeCompilation = true; + std::string MdtPathsString; + + llvm::ICInputFile input1(FicInputFile); + llvm::ICInputFile input2(FicInputFile2); + ICPathsMap MdtPaths; + int parsed; + + if (input1.exists()) { + parsed = input1.read(); + input1.remove(); + MdtPaths = input1.getPaths(); + } + else if (input2.exists()) { + parsed = input2.read(); + input2.remove(); + MdtPaths = input2.getPaths(); + } + else { + report_fatal_error(Twine("ITERATIVE COMPILATION ERROR:" + "unable to read input file\n")); + } + + if (!parsed) { + std::string ErrorMsg; + report_fatal_error(Twine("ITERATIVE COMPILATION ERROR:") + ErrorMsg + "\n"); + return false; + } + + setPaths(MdtPaths); + } + return true; +} + +bool ModuleDecisionTreeProxies::doFinalization(Module &M) { + if (IterativeCompilationOpt) { + std::vector Results; + ICResultsFile *resultsFile; + getResults(Results); + + if (ICPhase != FnNameAndPhase::CodeGenPhase) { + resultsFile = new ICResultsFile(FicResultsFile); + } + else { + resultsFile = new ICResultsFile(FicResultsFile2); + } + + resultsFile->setResults(Results); + resultsFile->write(); + } + return true; +} + +/// This function should be called from pass that wants to take advantage +/// of iterative compilation. If this function returns false, a pass +/// should do exactly as before, without iterative compilation, +/// otherwise take an alternative path. Parameter priority is the +/// estimated priority of this decision. We should pass higher priority +/// for the decisions which can more influence the code quality and for +/// which the existing heuristics are not sure that the right decision +/// is taken. +bool ModuleDecisionTreeProxies::getDecision(int priority, ICOptimization opt) { + if (!CurrFnDecisionTreeProxy) + return false; + bool r2 = CurrFnDecisionTreeProxy->getDecision(priority, opt); + return r2; +} Index: lib/Analysis/ICProxies.cpp =================================================================== --- /dev/null +++ lib/Analysis/ICProxies.cpp @@ -0,0 +1,262 @@ +#include "llvm/Analysis/ICProxies.h" +#include "llvm/Analysis/ICUtils.h" +#include +#include + +using namespace llvm; + +DecisionTreeProxy::DecisionTreeProxy() + : FunctionFitness(0), BestFunctionFitness(INT_MAX), CurrentDepth(0) {} + +/// This function is called by ModuleDecisionTreeProxies::getDecision +/// to obtain decision at some compilation point. +bool DecisionTreeProxy::getDecision(int priority, ICOptimization opt) { + if (CurrentDepth < (int)Path.size()) { + bool r = Path[CurrentDepth]; + CurrentDepth++; + return r; + } + Priorities.push_back(priority); + Optimizations.push_back(opt); + CurrentDepth++; + return false; +} + +MdtResults DecisionTreeProxy::getResults() const { + MdtResults results; + results.Priorities = Priorities; + results.Optimizations = Optimizations; + results.Fitness = FunctionFitness; + return results; +} + +void DecisionTreeProxy::setPath(const BitVector &path) { + Path = path; +} + +ModuleDecisionTrees::ModuleDecisionTrees(int totalIters, bool parallel, + std::string filename) : + NumberOfIterations(totalIters), CurrentIteration(-1), ModuleName(filename) { + if(NumberOfIterations == -1) { + ParallelExplore = false; + } + else if(ExploreAlg == ICExploreAlg::Parallel) { + ParallelExplore = true; + } + else { + ParallelExplore = false; + } + } + +ModuleDecisionTrees::~ModuleDecisionTrees() { + for (auto &P : DecisionTrees) { + DecisionTree *dt = P.second; + delete dt; + } +} + +/// Find required decision tree. +DecisionTree &ModuleDecisionTrees::getDecisionTree( + const FnNameAndPhase &fnNameAndPhase) { + if (DecisionTrees.find(fnNameAndPhase) == DecisionTrees.end()) { + DecisionTrees[fnNameAndPhase] = new DecisionTree(); + } + return *DecisionTrees[fnNameAndPhase]; +} + +/// Inform all decision trees that new iteration of compilation +/// has been started. +void ModuleDecisionTrees::startNewIteration() { + for (auto &P : DecisionTrees) { + DecisionTree *dt = P.second; + dt->startNewIteration(); + } + CurrentIteration++; +} + +/// Get selected paths for decision trees. +void ModuleDecisionTrees::getPaths(ICPathsMap &paths) { + paths.clear(); + for (const auto &P : DecisionTrees) { + const FnNameAndPhase &fnNameAndPhase = P.first; + const DecisionTree *dt = P.second; + const BitVector &path = dt->getPath(); + paths[fnNameAndPhase] = path; + } +} + +FnNameAndPhase::ICPhase ModuleDecisionTrees::getCurrentPhase() { + FnNameAndPhase::ICPhase targetPhase; + + if(CurrentIteration < NumberOfIterations/3) { + targetPhase = FnNameAndPhase::FunctionPhase; + } + else if(CurrentIteration < 2*NumberOfIterations/3) { + targetPhase = FnNameAndPhase::ModulePhase; + } + else { + targetPhase = FnNameAndPhase::CodeGenPhase; + } + + return targetPhase; +} + +/// Apply results to all decision trees used for a module optimization. +void ModuleDecisionTrees::applyResults(const std::vector &results) { + FnNameAndPhase::ICPhase targetPhase; + + if(ParallelExplore) { + targetPhase = getCurrentPhase(); + } + else { + targetPhase = FnNameAndPhase::ModulePhase; + } + + for (const auto &R : results) { + if(R.FunctionNameAndPhase.getPhase() == targetPhase) { + DecisionTree &DT = getDecisionTree(R.FunctionNameAndPhase); + DT.applyResults(R); + } + } +} + +/// Updates best function fitness filed for all decision trees. +void ModuleDecisionTrees::updateBestFunctionFitness(int Iteration) { + for (const auto &P : DecisionTrees) { + DecisionTree *DT = P.second; + DT->updateBestFunctionFitness(Iteration); + } +} + +/// Iterates through all decision trees and calls updateNodesFitness +/// on them. +void ModuleDecisionTrees::updateNodesFitness() +{ + for (const auto &P : DecisionTrees) { + DecisionTree *DT = P.second; + DT->updateNodesFitness(); + } +} + +/// Selects path for all decision trees. +void ModuleDecisionTrees::selectPath(bool FinalPass) +{ + FnNameAndPhase::ICPhase targetPhase; + bool isFinal; + + if(ParallelExplore) { + targetPhase = getCurrentPhase(); + + if(CurrentIteration < NumberOfIterations/3*2) + isFinal = (CurrentIteration+1)%(NumberOfIterations/3) == 0; + else + isFinal = CurrentIteration >= (NumberOfIterations-2); + + } + else { + targetPhase = FnNameAndPhase::ModulePhase; + isFinal = CurrentIteration >= (NumberOfIterations); + } + + for (const auto &P : DecisionTrees) { + if(P.first.getPhase() == targetPhase) { + DecisionTree *DT = P.second; + DT->selectPath(isFinal); + } + } +} + +void ModuleDecisionTrees::splitPaths( + const ICPathsMap &paths, + ICPathsMap &pathsBeforeCodegen, + ICPathsMap &pathsAfterCodegen) { + for (auto const &it : paths) { + const FnNameAndPhase &fnNameAndPhase = it.first; + const BitVector &path = it.second; + BitVector path1; + BitVector path2; + DecisionTree *DT = DecisionTrees[fnNameAndPhase]; + + DT->splitPath(path, path1, path2); + + pathsBeforeCodegen[fnNameAndPhase] = path1; + pathsAfterCodegen[fnNameAndPhase] = path2; + } +} + +void ModuleDecisionTrees::splitPathsMap( + const ICPathsMap &paths, + ICPathsMap &pathsBeforeCodegen, + ICPathsMap &pathsAfterCodegen) { + + pathsBeforeCodegen.clear(); + pathsAfterCodegen.clear(); + + for(auto const &it : paths) { + if(it.first.getPhase() == FnNameAndPhase::CodeGenPhase) { + pathsAfterCodegen[it.first] = it.second; + } + else { + pathsBeforeCodegen[it.first] = it.second; + } + } +} + +void ModuleDecisionTrees::setFunctionFitness(int totalFitness) { + for(auto &dt : DecisionTrees) { + dt.second->setFunctionFitness(totalFitness); + } +} + +void ModuleDecisionTrees::log() { + std::stringstream commonLogFilename, treeLogFilename, commonPartFilename; + std::ofstream commonLogFile, treeLogFile; + DecisionTree *dt; + + + for(const auto &it : DecisionTrees ) { + std::string treeName = it.first.getName(); + int phase = it.first.getPhase(); + dt = it.second; + + // compose filenames and open files + commonPartFilename << CurrentIteration << "-"; + commonPartFilename << ModuleName << "-"; + commonPartFilename << treeName << "-"; + commonPartFilename << "ph" << phase; + + commonLogFilename << "/tmp/ic-log-" << commonPartFilename.str() << ".json"; + treeLogFilename << "/tmp/ic-tree-" << commonPartFilename.str() << ".json"; + + commonLogFile.open(commonLogFilename.str(), std::fstream::trunc); + treeLogFile.open(treeLogFilename.str(), std::fstream::trunc); + + // get tree json - tree has dumpToJSON, change it to get JSON + std::string treeJSON = dt->getJSON(); + treeLogFile << treeJSON; + + commonLogFile << "{\n"; + int bestFunctionFitness = dt->getBestFunctionFitness(); + commonLogFile << "\t\"BestFunctionFitness\"\t: "; + commonLogFile << bestFunctionFitness << ",\n"; + + // current function fitness - already implemented + int currentFunctionFitness = dt->getFunctionFitness(); + commonLogFile << "\t\"CurrentFunctionFitness\": "; + commonLogFile << currentFunctionFitness << ",\n"; + + // selected node - get path and descent to it + int lastSelectedNodeID = dt->getLastSelectedNode()->NodeId; + commonLogFile << "\t\"LastSelectedNodeID\"\t: "; + commonLogFile << lastSelectedNodeID << "\n"; + + commonLogFile << "}\n"; + + commonPartFilename.str(""); + commonLogFilename.str(""); + treeLogFilename.str(""); + + commonLogFile.close(); + treeLogFile.close(); + } +} Index: lib/Analysis/ICUtils.cpp =================================================================== --- /dev/null +++ lib/Analysis/ICUtils.cpp @@ -0,0 +1,493 @@ +#include "llvm/Analysis/ICUtils.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/ErrorOr.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/SourceMgr.h" +#include "llvm/Support/YAMLParser.h" +#include + +using namespace llvm; + +cl::opt +llvm::IterativeCompilationOpt("fiterative-comp", cl::init(false), + cl::desc("Enable iterative compilation")); + +cl::opt +llvm::FicInputFile("fic-input-file", cl::init("ic-input")); + +cl::opt +llvm::FicInputFile2("fic-input2-file", cl::init("ic-input2")); + +cl::opt +llvm::FicResultsFile("fic-results-file", cl::init("ic-results")); + +cl::opt +llvm::FicResultsFile2("fic-results2-file", cl::init("ic-results2")); + +bool llvm::UseRand = true; +ICExploreAlg llvm::ExploreAlg = RoundRobin; + + +std::string llvm::BitVector2Str(const BitVector &path) { + std::stringstream s; + + s << "\""; + + for(unsigned i = 0; i < path.size(); i++) + s << path[i]; + + s << "\""; + + return s.str(); +} + +std::string llvm::Path2Str(const FnNameAndPhase &nameAndPhase, + const BitVector &path) { + std::stringstream s; + s << " {\n"; + s << " \"Fn\":\"" << nameAndPhase.getName() << "\",\n"; + s << " \"Phase\":" << (int)nameAndPhase.getPhase() << ",\n"; + s << " \"Path\":" << BitVector2Str(path) << "\n"; + s << " }"; + + return s.str(); +} + +// Parses string containing paths for multiple decision trees in JSON +/// format using llmv YAML parser. +bool llvm::parseMdtPaths(ICPathsMap &paths, + const std::string &pathString, + std::string &ErrorMessage) { + paths.clear(); + SourceMgr SM; + yaml::Stream YAMLStream(pathString, SM); + llvm::yaml::document_iterator I = YAMLStream.begin(); + + // sanity checks + if (I == YAMLStream.end()) { + ErrorMessage = "Error while parsing YAML."; + return false; + } + + llvm::yaml::Node *Root = I->getRoot(); + if (!Root) { + ErrorMessage = "Error while parsing YAML."; + return false; + } + + llvm::yaml::SequenceNode *Array = dyn_cast(Root); + if (!Array) { + ErrorMessage = "Expected array."; + return false; + } + + // parse every node + for (llvm::yaml::SequenceNode::iterator AI = Array->begin(), + AE = Array->end(); + AI != AE; ++AI) { + llvm::yaml::MappingNode *Object = dyn_cast(&*AI); + + // another sanity check + if (!Object) { + ErrorMessage = "Expected object."; + return false; + } + + llvm::yaml::ScalarNode *Fn = nullptr; + llvm::yaml::ScalarNode *Phase = nullptr; + llvm::yaml::ScalarNode *Path = nullptr; + for (llvm::yaml::MappingNode::iterator KVI = Object->begin(), + KVE = Object->end(); + KVI != KVE; ++KVI) { + llvm::yaml::Node *Value = (*KVI).getValue(); + if (!Value) { + ErrorMessage = "Expected value."; + return false; + } + llvm::yaml::ScalarNode *ValueString = + dyn_cast(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; + } + } + + // error reporting + if (!Fn) { + ErrorMessage = "Missing key: \"Fn\"."; + return false; + } + if (!Phase) { + ErrorMessage = "Missing key: \"Phase\"."; + return false; + } + if (!Path) { + ErrorMessage = "Missing key: \"Path\"."; + return false; + } + + // populating our structure + SmallString<8> FnStorage; + StringRef FnStr = Fn->getValue(FnStorage); + SmallString<8> PhaseStorage; + StringRef PhaseStr = Phase->getValue(PhaseStorage); + SmallString<8> PathStorage; + StringRef PathStr = Path->getValue(PathStorage); + + FnNameAndPhase::ICPhase CompilationPhase = + (FnNameAndPhase::ICPhase) (atoi(PhaseStr.str().c_str())); + + unsigned N = PathStr.size(); + BitVector PathVector(N); + unsigned i; + for (i = 0; i < N; i++) + PathVector[i] = (PathStr[i] == '0' ? false : true); + + FnNameAndPhase fnNameAndPhase(FnStr.str(), CompilationPhase); + paths[fnNameAndPhase] = PathVector; + } + return true; +} + +/// Converts paths for multiple decision trees to string in JSON format. +std::string llvm::generateMdtPathsString(const ICPathsMap &paths) { + std::stringstream s; + s << "[\n"; + unsigned n = paths.size(); + unsigned i = 0; + for (const auto &P : paths) { + const FnNameAndPhase &fnNameAndPhase = P.first; + const BitVector &path = P.second; + + s << Path2Str(fnNameAndPhase, path); + + if(i + 1 < n) + s << ",\n"; + else + s << "\n"; + + i++; + } + s << "]\n"; + return s.str(); +} + +/// Parses string containing results for multiple decision trees +/// in JSON format to vector of MdtResults structs using LLMV +/// YAML parser. +bool MdtResults::parseMdtResults( + std::vector &results, + const std::string &resString, + std::string &ErrorMessage) { + results.clear(); + SourceMgr SM; + yaml::Stream YAMLStream(resString, SM); + + // sanity checks + llvm::yaml::document_iterator I = YAMLStream.begin(); + if (I == YAMLStream.end()) { + ErrorMessage = "Error while parsing YAML."; + return false; + } + llvm::yaml::Node *Root = I->getRoot(); + if (!Root) { + ErrorMessage = "Error while parsing YAML."; + return false; + } + llvm::yaml::SequenceNode *Array = dyn_cast(Root); + if (!Array) { + ErrorMessage = "Expected array."; + return false; + } + + // iterating over nodes + for (llvm::yaml::SequenceNode::iterator AI = Array->begin(), + AE = Array->end(); + AI != AE; ++AI) { + llvm::yaml::MappingNode *Object = dyn_cast(&*AI); + if (!Object) { + ErrorMessage = "Expected object."; + return false; + } + + // some init + llvm::yaml::ScalarNode *Fn = nullptr; + llvm::yaml::ScalarNode *Phase = nullptr; + llvm::yaml::ScalarNode *Fitness = nullptr; + llvm::yaml::SequenceNode *Priorities = nullptr; + llvm::yaml::SequenceNode *Optimizations = nullptr; + std::vector PrioritiesVector; + std::vector OptimizationsVector; + + // another iteration + for (llvm::yaml::MappingNode::iterator KVI = Object->begin(), + KVE = Object->end(); + KVI != KVE; ++KVI) { + llvm::yaml::Node *Value = (*KVI).getValue(); + if (!Value) { + ErrorMessage = "Expected value (1)."; + return false; + } + llvm::yaml::ScalarNode *KeyString = + dyn_cast((*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; + } + } + + // error reporting + if (!Fn) { + ErrorMessage = "Missing key: \"Fn\"."; + return false; + } + if (!Phase) { + ErrorMessage = "Missing key: \"Phase\"."; + return false; + } + if (!Fitness) { + ErrorMessage = "Missing key: \"Fitness\"."; + return false; + } + if (!Priorities) { + ErrorMessage = "Missing key: \"Priorities\"."; + return false; + } + if (!Optimizations) { + ErrorMessage = "Missing key: \"Optimizations\"."; + return false; + } + + // populating our storage + SmallString<8> FnStorage; + StringRef FnStr = Fn->getValue(FnStorage); + SmallString<8> PhaseStorage; + StringRef PhaseStr = Phase->getValue(PhaseStorage); + SmallString<8> FitnessStorage; + StringRef FitnessStr = Fitness->getValue(FitnessStorage); + + FnNameAndPhase::ICPhase CompilationPhase = + (FnNameAndPhase::ICPhase) (atoi(PhaseStr.str().c_str())); + + MdtResults mdtResults; + mdtResults.FunctionNameAndPhase = + FnNameAndPhase(FnStr.str(), CompilationPhase); + mdtResults.Fitness = atoi(FitnessStr.str().c_str()); + mdtResults.Priorities = PrioritiesVector; + mdtResults.Optimizations = OptimizationsVector; + results.push_back(mdtResults); + } + return true; +} + +/// Converts vector of MdtResults to string in JSON format. +std::string MdtResults::generateMdtResultsString( + const std::vector &results) { + unsigned i; + unsigned n = results.size(); + std::stringstream s; + + s << "[\n"; + for (i = 0; i < n; i++) { + const MdtResults &res = results[i]; + const FnNameAndPhase &fnNameAndPhase = res.FunctionNameAndPhase; + s << " {\n"; + s << " \"Fn\":\"" << fnNameAndPhase.getName() << "\",\n"; + s << " \"Phase\":" << (int)fnNameAndPhase.getPhase() << ",\n"; + s << " \"Fitness\":" << res.Fitness << ",\n"; + s << " \"Priorities\":["; + unsigned j; + unsigned nPriorities = res.Priorities.size(); + for (j = 0; j < nPriorities; j++) { + s << res.Priorities[j]; + if (j + 1 < nPriorities) + s << ","; + } + s << "]\n"; + s << " \"Optimizations\":["; + unsigned nOptimizations = res.Optimizations.size(); + for (j = 0; j < nOptimizations; j++) { + s << (int)res.Optimizations[j]; + if (j + 1 < nOptimizations) + s << ","; + } + s << "]\n"; + if (i + 1 < n) + s << " },\n"; + else + s << " }\n"; + } + s << "]\n"; + return s.str(); +} + +/// Calculates total module fitness as the sum of the finesses of +/// all functions in the module. +int MdtResults::calculateTotalFitness(const std::vector &results) { + int tf = 0; + for (const auto &res : results) { + if (res.FunctionNameAndPhase.getPhase() == FnNameAndPhase::CodeGenPhase) + tf += res.Fitness; + } + return tf; +} + +void MdtResults::mergeMdtResults( + std::vector &mergedResults, + const std::vector &results1, + const std::vector &results2) { + + const MdtResults *moduleResults1 = 0; + const MdtResults *moduleResults2 = 0; + MdtResults mergedModuleResults; + + moduleResults1 = MdtResults::getByPhase(results1, FnNameAndPhase::ModulePhase); + moduleResults2 = MdtResults::getByPhase(results2, FnNameAndPhase::ModulePhase); + + // push all results which aren't module phase + for (const auto &res : results1) { + if (res.FunctionNameAndPhase.getPhase() != FnNameAndPhase::ModulePhase) + mergedResults.push_back(res); + } + + for (const auto &res : results2) { + if (res.FunctionNameAndPhase.getPhase() != FnNameAndPhase::ModulePhase) + mergedResults.push_back(res); + } + + // if only one has module phase results + if (moduleResults1 && !moduleResults2) + mergedResults.push_back(*moduleResults1); + + if (!moduleResults1 && moduleResults2) + mergedResults.push_back(*moduleResults2); + + // if both have module phase results + if (moduleResults1 && moduleResults2) { + mergedModuleResults = *moduleResults1; + + mergedModuleResults.Priorities.insert(mergedModuleResults.Priorities.end(), + moduleResults2->Priorities.begin(), moduleResults2->Priorities.end()); + + mergedModuleResults.Optimizations.insert(mergedModuleResults.Optimizations.end(), + moduleResults2->Optimizations.begin(), moduleResults2->Optimizations.end()); + + mergedResults.push_back(mergedModuleResults); + } +} + +MdtResults* MdtResults::getByPhase(const std::vector &results, + FnNameAndPhase::ICPhase phase) { + + MdtResults *found = NULL; + for (const auto &res : results) { + if (res.FunctionNameAndPhase.getPhase() == phase) + { + found = new MdtResults(); + *found = res; + break; + } + } + + return found; +} + +std::string llvm::getModuleName(int argc, const char **argv) { + std::string filename; + + for(int i = 0; i < argc; i++) { + if(strstr(argv[i], ".i.c")) { + filename.assign(argv[i]); + filename = filename.substr(0, filename.find(".i.c")); + break; + } + } + + return filename; +} Index: lib/CodeGen/RegAllocGreedy.cpp =================================================================== --- lib/CodeGen/RegAllocGreedy.cpp +++ lib/CodeGen/RegAllocGreedy.cpp @@ -21,6 +21,7 @@ #include "SplitKit.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/IterativeCompilation.h" #include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/EdgeBundles.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" @@ -120,6 +121,7 @@ const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; RegisterClassInfo RCI; + ModuleDecisionTreeProxies *MDTP; // analyses SlotIndexes *Indexes; @@ -474,6 +476,10 @@ AU.addPreserved(); AU.addRequired(); AU.addPreserved(); + + if(IterativeCompilationOpt) + AU.addRequired(); + AU.addRequired(); AU.addPreserved(); AU.addRequired(); @@ -865,6 +871,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. @@ -908,11 +915,29 @@ // Best so far. BestPhys = PhysReg; + EvictionCandidates.push_back(PhysReg); + // Stop if the hint can be used. if (Order.isHint()) break; } + // Try different choices for register to be evicted. + if(IterativeCompilationOpt && (EvictionCandidates.size() > 1)) { + int priority = 0x10000; + + for (int i = (int)EvictionCandidates.size() - 2; i >= 0; i--) { + bool decision = false; + + decision = MDTP->getDecision(priority, llvm::RegAllocOpt); + + if(decision) { + BestPhys = EvictionCandidates[i]; + } + priority = priority / 2; + } + } + if (!BestPhys) return 0; @@ -2587,6 +2612,21 @@ Indexes = &getAnalysis(); MBFI = &getAnalysis(); DomTree = &getAnalysis(); + + if(IterativeCompilationOpt) + { + MDTP = &getAnalysis(); + + if(llvm::ExploreAlg == llvm::ICExploreAlg::Parallel) { + std::string fnName = mf.getName().str(); + MDTP->setCurrentFunctionAndPhase(fnName, FnNameAndPhase::CodeGenPhase); + } + else { + MDTP->setModuleCompilationPhase(); + } + } + + SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); Loops = &getAnalysis(); Bundles = &getAnalysis(); Index: lib/Target/Mips/CMakeLists.txt =================================================================== --- lib/Target/Mips/CMakeLists.txt +++ lib/Target/Mips/CMakeLists.txt @@ -28,6 +28,7 @@ MipsDelaySlotFiller.cpp MipsFastISel.cpp MipsHazardSchedule.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 @@ -32,6 +32,7 @@ FunctionPass *createMipsHazardSchedule(); FunctionPass *createMipsLongBranchPass(MipsTargetMachine &TM); FunctionPass *createMipsConstantIslandPass(MipsTargetMachine &tm); + FunctionPass *createMipsFunctionFitnessPass(); } // end namespace llvm; #endif Index: lib/Target/Mips/MipsFunctionFitness.cpp =================================================================== --- /dev/null +++ lib/Target/Mips/MipsFunctionFitness.cpp @@ -0,0 +1,84 @@ +//===-- MipsFunctionFitness.cpp - Function Fitness Implementation ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file estimates the fitness of a function which is used in +// iterative compilation. +// +//===----------------------------------------------------------------------===// + +#include "Mips.h" +#include "MipsTargetMachine.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/IterativeCompilation.h" +#include "llvm/IR/Function.h" + +using namespace llvm; + +struct FunctionFitness : public MachineFunctionPass { + + static char ID; + FunctionFitness() : MachineFunctionPass(ID), TotalCount(0) { } + + virtual const char *getPassName() const { + return "Mips Function Fitness"; + } + + bool runOnMachineBasicBlock(MachineBasicBlock &MBB); + bool runOnMachineFunction(MachineFunction &F) { + std::string FnName = F.getFunction()->getName().str(); + ModuleDecisionTreeProxies &Proxies = + getAnalysis(); + 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/IterativeCompilation.h" using namespace llvm; @@ -257,6 +258,10 @@ // hazards itself or be pipelined before the HSP. addPass(createMipsDelaySlotFillerPass(TM)); addPass(createMipsHazardSchedule()); + + 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 @@ -63,6 +63,7 @@ INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) INITIALIZE_PASS_END(AlwaysInliner, "always-inline", "Inliner for always_inline functions", false, false) Index: lib/Transforms/IPO/InlineSimple.cpp =================================================================== --- lib/Transforms/IPO/InlineSimple.cpp +++ lib/Transforms/IPO/InlineSimple.cpp @@ -79,6 +79,7 @@ INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) INITIALIZE_PASS_END(SimpleInliner, "inline", "Function Integration/Inlining", false, false) Index: lib/Transforms/IPO/Inliner.cpp =================================================================== --- lib/Transforms/IPO/Inliner.cpp +++ lib/Transforms/IPO/Inliner.cpp @@ -21,6 +21,7 @@ #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/InlineCost.h" #include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/IterativeCompilation.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DiagnosticInfo.h" @@ -58,6 +59,7 @@ AU.addRequired(); AU.addRequired(); getAAResultsAnalysisUsage(AU); + AU.addRequired(); CallGraphSCCPass::getAnalysisUsage(AU); } @@ -248,7 +250,22 @@ } Function *Caller = CS.getCaller(); - if (!IC) { + bool doInlinging = (bool)IC; + + int ip = IC.getCostDelta(); + if (ip < 0) + ip = -ip; + int t = MaxDtPriority - ip; + bool decision = false; + + if (t >= 0) { + decision = MDTP->getDecision(t, InlinerOpt); + } + + if (decision) + doInlinging = !doInlinging; + + if (!doInlinging) { DEBUG(dbgs() << " NOT Inlining: cost=" << IC.getCost() << ", thres=" << (IC.getCostDelta() + IC.getCost()) << ", Call: " << *CS.getInstruction() << "\n"); @@ -360,6 +377,10 @@ ACT = &getAnalysis(); auto &TLI = getAnalysis().getTLI(); + MDTP = &getAnalysis(); + MDTP->setModuleCompilationPhase(); + + SmallPtrSet SCCFunctions; DEBUG(dbgs() << "Inliner visiting SCC:"); for (CallGraphNode *Node : SCC) { @@ -415,8 +436,8 @@ if (Function *F = CallSites[i].first.getCalledFunction()) if (SCCFunctions.count(F)) std::swap(CallSites[i--], CallSites[--FirstCallInSCC]); - + InlinedArrayAllocasTy InlinedArrayAllocas; InlineFunctionInfo InlineInfo(&CG, ACT); Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -39,6 +39,7 @@ #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/Loads.h" +#include "llvm/Analysis/IterativeCompilation.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/MemoryBuiltins.h" @@ -121,6 +122,7 @@ /// void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); + AU.addRequired(); AU.addRequired(); getLoopAnalysisUsage(AU); } @@ -138,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. @@ -164,6 +167,7 @@ char LICM::ID = 0; INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false) INITIALIZE_PASS_DEPENDENCY(LoopPass) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false) @@ -183,6 +187,7 @@ LI = &getAnalysis().getLoopInfo(); AA = &getAnalysis().getAAResults(); DT = &getAnalysis().getDomTree(); + MDTP = &getAnalysis(); TLI = &getAnalysis().getTLI(); @@ -195,6 +200,14 @@ // Get the preheader block to move instructions into... Preheader = L->getLoopPreheader(); + if(llvm::ExploreAlg == llvm::ICExploreAlg::Parallel) { + std::string fnName = Preheader->getParent()->getName().str(); + MDTP->setCurrentFunctionAndPhase(fnName, FnNameAndPhase::FunctionPhase); + } + else { + MDTP->setModuleCompilationPhase(); + } + // Compute loop safety information. LICMSafetyInfo SafetyInfo; computeLICMSafetyInfo(&SafetyInfo, CurLoop); @@ -211,10 +224,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. @@ -268,7 +281,8 @@ /// bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, - AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) { + AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo, + ModuleDecisionTreeProxies *MDTP) { // Verify inputs. assert(N != nullptr && AA != nullptr && LI != nullptr && @@ -282,8 +296,10 @@ // We are processing blocks in reverse dfo, so process children first. bool Changed = false; const std::vector &Children = N->getChildren(); + for (DomTreeNode *Child : Children) - Changed |= sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo); + Changed |= sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo, + MDTP); // Only need to process the contents of this block if it is not part of a // subloop (which would already have been processed). @@ -324,7 +340,8 @@ /// bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, - AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) { + AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo, + ModuleDecisionTreeProxies *MDTP) { // Verify inputs. assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && CurAST != nullptr && @@ -339,6 +356,7 @@ // subloop (which would already have been processed). bool Changed = false; if (!inSubLoop(BB, CurLoop, LI)) + { for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { Instruction &I = *II++; // Try constant folding this instruction. If all the operands are @@ -346,6 +364,11 @@ // 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); @@ -361,13 +384,19 @@ if (CurLoop->hasLoopInvariantOperands(&I) && canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) && isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo, - CurLoop->getLoopPreheader()->getTerminator())) - Changed |= hoist(I, DT, CurLoop, SafetyInfo); + CurLoop->getLoopPreheader()->getTerminator())) { + if (!(MDTP->getDecision(MaxDtPriority / 2, LicmOpt))) { + Changed |= hoist(I, DT, CurLoop, SafetyInfo); + } + } } + } const std::vector &Children = N->getChildren(); + for (DomTreeNode *Child : Children) - Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo); + Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo, + MDTP); return Changed; } Index: unittests/Analysis/CMakeLists.txt =================================================================== --- unittests/Analysis/CMakeLists.txt +++ unittests/Analysis/CMakeLists.txt @@ -17,4 +17,8 @@ MixedTBAATest.cpp ValueTrackingTest.cpp UnrollAnalyzer.cpp + ICProxies.cpp + ICDecisionTree.cpp + ICUtils.cpp + ICParallel.cpp ) Index: unittests/Analysis/ICDecisionTree.cpp =================================================================== --- /dev/null +++ unittests/Analysis/ICDecisionTree.cpp @@ -0,0 +1,817 @@ +#include "gtest/gtest.h" +#include "llvm/Analysis/ICDecisionTree.h" + +namespace llvm { + + +namespace { +// -------------- FIXTURES -----------------// +DecisionTreeNode *prepareNode(int priority, int id) +{ + DecisionTreeNode *node = new DecisionTreeNode; + node->Fitness = 0; + node->Priority = priority; + node->NodeId = id; + node->Optimization = LicmOpt; + return node; +} + +DecisionTree *getDTOnlyPrimary() +{ + DecisionTree *dt = new DecisionTree; + DecisionTreeNode *newNode; + + newNode = prepareNode(100, 1); + dt->addPrimaryDecision(newNode); + + newNode = prepareNode(200, 2); + dt->addPrimaryDecision(newNode); + + newNode = prepareNode(300, 3); + dt->addPrimaryDecision(newNode); + + return dt; +} + +DecisionTree *getDTPrimaryAndAlternative() +{ + DecisionTree *dt = new DecisionTree; + DecisionTreeNode *newNode; + + newNode = prepareNode(100, 1); + dt->addPrimaryDecision(newNode); + + newNode = prepareNode(200, 2); + dt->addPrimaryDecision(newNode); + + newNode = prepareNode(300, 3); + dt->addAlternativeDecision(newNode); + + newNode = prepareNode(400, 4); + dt->addPrimaryDecision(newNode); + + newNode = prepareNode(500, 5); + dt->addPrimaryDecision(newNode); + + return dt; +} + +DecisionTree *getDTOnlyAlternative() +{ + DecisionTree *dt = new DecisionTree; + DecisionTreeNode *newNode; + + newNode = prepareNode(100, 1); + dt->addAlternativeDecision(newNode); + + newNode = prepareNode(200, 2); + dt->addAlternativeDecision(newNode); + + newNode = prepareNode(300, 3); + dt->addAlternativeDecision(newNode); + + newNode = prepareNode(400, 4); + dt->addAlternativeDecision(newNode); + + newNode = prepareNode(500, 5); + dt->addAlternativeDecision(newNode); + + return dt; +} + +// ------------- TESTS -------------------// +TEST(ICDecisionTreeNode, decisionTreeNodeInit) +{ + DecisionTreeNode node; + ASSERT_TRUE(node.Parent == NULL); + ASSERT_TRUE(node.PrimaryDecision == NULL); + ASSERT_TRUE(node.AlternativeDecision == NULL); +} + + +TEST(ICDecisionTree, dummyPopulateTree) +{ + DecisionTree dt; + llvm::DecisionTreeNode *node = dt.getRootNode(); + + EXPECT_FALSE(node == NULL); + EXPECT_TRUE(node->PrimaryDecision == NULL); + EXPECT_TRUE(node->AlternativeDecision == NULL); + + dt.addPrimaryDecision(); + ASSERT_FALSE(node->PrimaryDecision == NULL); + node = node->PrimaryDecision; + + EXPECT_TRUE(node->AlternativeDecision == NULL); + dt.addAlternativeDecision(); + ASSERT_TRUE(node->AlternativeDecision != NULL); +} + +TEST(ICDecisionTree, splitPathOnlyPrimary) +{ + DecisionTree dt; + DecisionTreeNode *node; + + node = new DecisionTreeNode; + node->Optimization = LicmOpt; + dt.addPrimaryDecision(node); + + node = new DecisionTreeNode; + node->Optimization = InlinerOpt; + dt.addPrimaryDecision(node); + + node = new DecisionTreeNode; + node->Optimization = RegAllocOpt; + dt.addPrimaryDecision(node); + + BitVector completePath(4, 0); + + BitVector pathBeforeCodegen, pathAfterCodegen; + + dt.splitPath(completePath, pathBeforeCodegen, pathAfterCodegen); + + ASSERT_EQ(pathBeforeCodegen.size(), 3); + ASSERT_EQ(pathAfterCodegen.size(), 1); +} + +TEST(ICDecisionTree, getDecisionFirstIteration) +{ + DecisionTree dt; + + // check if we got the root node + DecisionTreeNode *currentNode = dt.getRootNode(); + ASSERT_EQ(currentNode->NodeId, 0); + ASSERT_EQ(0, currentNode->Priority); + + // add a decision and check if root is updated correctly + dt.getDecision(500, LicmOpt); + ASSERT_EQ(500, currentNode->Priority); + ASSERT_TRUE(currentNode->PrimaryDecision != NULL); + ASSERT_TRUE(currentNode->AlternativeDecision == NULL); + + // move one child lower and check it + // current node id should be 1 + currentNode = currentNode->PrimaryDecision; + ASSERT_EQ(0, currentNode->Priority); + ASSERT_EQ(currentNode->NodeId, 1); + ASSERT_TRUE(currentNode->Parent != NULL); + ASSERT_EQ(currentNode->Parent->NodeId, 0); + + // add new decision and see if the parent is updated + dt.getDecision(600, LicmOpt); + ASSERT_EQ(600, currentNode->Priority); + ASSERT_TRUE(currentNode->PrimaryDecision != NULL); + ASSERT_TRUE(currentNode->AlternativeDecision == NULL); + + // check if new node is sane + currentNode = currentNode->PrimaryDecision; + ASSERT_EQ(2, currentNode->NodeId); + ASSERT_EQ(0, currentNode->Priority); + ASSERT_TRUE(currentNode->Parent != NULL); + ASSERT_EQ(1, currentNode->Parent->NodeId); +} + +TEST(ICDecisionTree, getDecisionOnPrimaryPath) +{ + // build the tree + DecisionTree dt; + ASSERT_FALSE(dt.getDecision(500, LicmOpt)); + ASSERT_FALSE(dt.getDecision(500, LicmOpt)); + ASSERT_FALSE(dt.getDecision(600, LicmOpt)); + ASSERT_FALSE(dt.getDecision(700, LicmOpt)); + + // build and check the path + dt.selectPath(false); + BitVector path = dt.getPath(); + + BitVector correctPath(4, 0); + correctPath.set(3); + ASSERT_EQ(correctPath, path); + + // start new iteration + // try to get new decision and check the path now + dt.startNewIteration(); + ASSERT_FALSE(dt.getDecision(100, LicmOpt)); + ASSERT_FALSE(dt.getDecision(110, LicmOpt)); + ASSERT_FALSE(dt.getDecision(120, LicmOpt)); + // this spawns alternative path + ASSERT_TRUE(dt.getDecision(130, LicmOpt)); + + // check if only parent of new node is updated + ASSERT_EQ(500, dt.getRootNode()->Priority); + ASSERT_EQ(3, dt.getCurrentNode()->Parent->NodeId); + ASSERT_EQ(130, dt.getCurrentNode()->Parent->Priority); +} + +TEST(ICDecisionTree, getDecisionOnAlternativePath) +{ + // build the tree + DecisionTree dt; + ASSERT_FALSE(dt.getDecision(500, LicmOpt)); + ASSERT_FALSE(dt.getDecision(500, LicmOpt)); + ASSERT_FALSE(dt.getDecision(600, LicmOpt)); + ASSERT_FALSE(dt.getDecision(700, LicmOpt)); + + // build and check the path + dt.selectPath(false); + BitVector path = dt.getPath(); + + BitVector correctPath(4, 0); + correctPath.set(3); + ASSERT_EQ(correctPath, path); + + // start new iteration + // try to get new decision and check the path now + dt.startNewIteration(); + ASSERT_FALSE(dt.getDecision(600, LicmOpt)); + ASSERT_FALSE(dt.getDecision(500, LicmOpt)); + ASSERT_FALSE(dt.getDecision(600, LicmOpt)); + + // ok, we are on alternative path now + ASSERT_TRUE(dt.getDecision(700, LicmOpt)); + ASSERT_FALSE(dt.getDecision(800, LicmOpt)); + ASSERT_FALSE(dt.getDecision(900, LicmOpt)); + + // check if we are on the right track + DecisionTreeNode *selectedNode = dt.selectNode(); + ASSERT_EQ(6, selectedNode->NodeId); + + // everything fine, select this path + dt.selectPath(false); + dt.startNewIteration(); + ASSERT_EQ(0, dt.getCurrentNode()->NodeId); + + // still on old path + ASSERT_FALSE(dt.getDecision(600, LicmOpt)); + ASSERT_FALSE(dt.getDecision(500, LicmOpt)); + ASSERT_FALSE(dt.getDecision(600, LicmOpt)); + + // ok, we are on alternative path now + ASSERT_TRUE(dt.getDecision(700, LicmOpt)); + ASSERT_FALSE(dt.getDecision(800, LicmOpt)); + + // this should put us on alternative path + ASSERT_TRUE(dt.getDecision(1000, LicmOpt)); + ASSERT_EQ(1000, dt.getCurrentNode()->Parent->Priority); + + ASSERT_FALSE(dt.getDecision(1100, LicmOpt)); +} + +TEST(ICDecisionTree, selectPathEmptyTree) +{ + DecisionTree dt; + DecisionTreeNode *root = dt.getRootNode(); + + ASSERT_TRUE(root->PrimaryDecision == NULL); + ASSERT_TRUE(root->AlternativeDecision == NULL); + + bool result = dt.selectPath(false); + BitVector path = dt.getPath(); + + ASSERT_EQ(result, false); + ASSERT_EQ(BitVector(0), path); +} + +TEST(ICDecisionTreeNode, calcFinalPriorityWithoutFitness) +{ + DecisionTreeNode node; + node.Fitness = 0; + node.Priority = 100; + + int bestFunctionFitness = 1000; + + double finalPriority = node.calcFinalPriority(bestFunctionFitness); + + ASSERT_EQ(finalPriority, node.Priority); +} + +TEST(ICDecisionTreeNode, calcFinalPriorityWithFitness) +{ + DecisionTreeNode node; + node.Fitness = INT_MAX; + node.Priority = 15; + + int bestFunctionFitness = INT_MAX; + + double finalPriority = node.calcFinalPriority(bestFunctionFitness); + + ASSERT_EQ(15, finalPriority); +} + +TEST(ICDecisionTreeNode, DecisionTreeNodeConstructor) +{ + DecisionTreeNode node; + + ASSERT_EQ(node.Depth, 0); + ASSERT_TRUE(node.Parent == NULL); + ASSERT_TRUE(node.PrimaryDecision == NULL); + ASSERT_TRUE(node.AlternativeDecision == NULL); + ASSERT_EQ(node.Priority, 0); + ASSERT_EQ(node.Fitness, INT_MAX); +} + +TEST(ICDecisionTree, DecisionTreeConstructor) +{ + DecisionTree dt; + DecisionTreeNode *root = dt.getRootNode(); + + ASSERT_EQ(root->Depth, 0); +} + +TEST(ICDecisionTree, findPathToRoot) +{ + DecisionTree dt; + BitVector path; + DecisionTreeNode *node = dt.getRootNode(); + + dt.findPath(node, path); + + ASSERT_EQ(BitVector(0), path); +} + +TEST(ICDecisionTree, findPathOnlyPrimary) +{ + DecisionTree dt; + dt.getDecision(500, NoOptimization); + dt.getDecision(500, NoOptimization); + dt.getDecision(500, NoOptimization); + + DecisionTreeNode *node = dt.getRootNode(); + node = node->PrimaryDecision->PrimaryDecision->PrimaryDecision; + + BitVector path; + dt.findPath(node, path); + + ASSERT_EQ(BitVector(3, 0), path); +} + +TEST(ICDecisionTree, findPathOnlyAlternative) +{ + DecisionTree *dt = getDTOnlyAlternative(); + DecisionTreeNode *node = dt->getRootNode(); + + while(node->AlternativeDecision) + node = node->AlternativeDecision; + + BitVector path; + dt->findPath(node, path); + + ASSERT_EQ(BitVector(5, 1), path); +} + +TEST(ICDecisionTree, findPathPrimaryAndAlternative) +{ + DecisionTree *dt = getDTPrimaryAndAlternative(); + DecisionTreeNode *node = dt->selectNode(); + + ASSERT_TRUE(node != NULL); + + BitVector path; + dt->findPath(node, path); + + BitVector result(5, 0); + result.set(2); + result.set(4); + + ASSERT_EQ(result, path); +} + +TEST(ICDecisionTree, selectNodeEmptyTree) +{ + DecisionTree dt; + DecisionTreeNode *node = dt.selectNode(); + ASSERT_EQ(0, node->NodeId); +} + + +TEST(ICDecisionTree, selectNodeOnlyPrimary) +{ + DecisionTree *dt = getDTOnlyPrimary(); + DecisionTreeNode *selectedNode = dt->selectNode(); + ASSERT_TRUE(selectedNode != NULL); + ASSERT_EQ(200, selectedNode->Priority); +} + +TEST(ICDecisionTree, selectNodePrimaryAndAlternative) +{ + DecisionTree *dt = getDTPrimaryAndAlternative(); + DecisionTreeNode *selectedNode = dt->selectNode(); + ASSERT_TRUE(selectedNode != NULL); + ASSERT_EQ(400, selectedNode->Priority); +} + +TEST(ICDecisionTree, selectNodeOnlyAlternative) +{ + DecisionTree *dt = getDTOnlyAlternative(); + DecisionTreeNode *selectedNode = dt->selectNode(); + ASSERT_TRUE(selectedNode == NULL); +} + + +// scenario 1: +// given there is an empty tree +// and there are new decisions stored in merged results +// when those results are applied to a decision tree +// then new nodes have to be added to the tree +// and their priorirites and optimizations set +TEST(ICDecisionTree, applyResultsToEmptyTree) { + DecisionTree dt; + MdtResults moduleResults; + + moduleResults.FunctionNameAndPhase = + FnNameAndPhase("module-id", FnNameAndPhase::ModulePhase); + + moduleResults.Priorities.push_back(100); + moduleResults.Priorities.push_back(200); + moduleResults.Priorities.push_back(300); + moduleResults.Priorities.push_back(400); + moduleResults.Priorities.push_back(500); + + moduleResults.Optimizations.push_back(LicmOpt); + moduleResults.Optimizations.push_back(LicmOpt); + moduleResults.Optimizations.push_back(LicmOpt); + moduleResults.Optimizations.push_back(InlinerOpt); + moduleResults.Optimizations.push_back(InlinerOpt); + + dt.applyResults(moduleResults); + + DecisionTreeNode *node = dt.getRootNode(); + ASSERT_TRUE(node != NULL); + + int i = 1; + while(node != NULL && i < 6) { + EXPECT_EQ(100*i, node->Priority); + + if(i < 4) + EXPECT_EQ(LicmOpt, node->Optimization); + else + EXPECT_EQ(InlinerOpt, node->Optimization); + + node = node->PrimaryDecision; + i++; + } +} +// scenario 2: +// given there is non empty tree +// and new iteration is started +// and there are new resusults in merged results +// when those results are applied to an existing decision tree +// then old nodes should be preserved +// and new nodes added to correct place +// and their priorities and optimizations set +TEST(ICDecisionTree, applyResultsToNonemptyTree) { + DecisionTree dt; + MdtResults moduleResults; + + moduleResults.FunctionNameAndPhase = + FnNameAndPhase("module-id", FnNameAndPhase::ModulePhase); + + moduleResults.Priorities.push_back(100); + moduleResults.Priorities.push_back(500); + moduleResults.Priorities.push_back(400); + + moduleResults.Optimizations.push_back(LicmOpt); + moduleResults.Optimizations.push_back(LicmOpt); + moduleResults.Optimizations.push_back(InlinerOpt); + + dt.applyResults(moduleResults); + dt.selectPath(0); + + moduleResults.Priorities.clear(); + moduleResults.Priorities.push_back(600); + moduleResults.Priorities.push_back(300); + + moduleResults.Optimizations.clear(); + moduleResults.Optimizations.push_back(LicmOpt); + moduleResults.Optimizations.push_back(InlinerOpt); + + dt.startNewIteration(); + dt.applyResults(moduleResults); + BitVector p = dt.getPath(); + + DecisionTreeNode *node = dt.getRootNode(); + ASSERT_EQ(100, node->Priority); + + node = node->PrimaryDecision; + ASSERT_EQ(500, node->Priority); + ASSERT_EQ(400, node->PrimaryDecision->Priority); + + node = node->AlternativeDecision; + ASSERT_TRUE(node != NULL); + ASSERT_EQ(600, node->Priority); + ASSERT_EQ(300, node->PrimaryDecision->Priority); +} + +TEST(ICNodeSelector, AddNodes) { + NodeSelector selector; + + DecisionTreeNode *nl = new DecisionTreeNode(); + nl->Optimization = LicmOpt; + selector.add(nl); + + DecisionTreeNode *ni = new DecisionTreeNode(); + ni->Optimization = InlinerOpt; + selector.add(ni); + + DecisionTreeNode *nra = new DecisionTreeNode(); + nra->Optimization = RegAllocOpt; + selector.add(nra); + + NodeList licmOpt = selector.getList(LicmOpt); + NodeList inlinerList = selector.getList(InlinerOpt); + NodeList regAllocList = selector.getList(RegAllocOpt); + + ASSERT_EQ(licmOpt.size(), 1); + ASSERT_EQ(inlinerList.size(), 1); + ASSERT_EQ(regAllocList.size(), 1); +} + +TEST(ICNodeSelector, bestListEmpty) { + NodeSelector selector; + ICOptimization best = selector.bestOptim(); + + ASSERT_EQ(best, ErrOpt); +} + +TEST(ICNodeSelector, bestList) { + NodeSelector selector; + + DecisionTreeNode *n1 = new DecisionTreeNode; + DecisionTreeNode *n2 = new DecisionTreeNode; + DecisionTreeNode *n3 = new DecisionTreeNode; + + n1->Optimization = LicmOpt; + n1->Fitness = 300; + n1->Priority = 500; + + n2->Optimization = RegAllocOpt; + n2->Fitness = 500; + n2->Priority = 500; + + n3->Optimization = InlinerOpt; + n3->Fitness = 500; + n3->Priority = 500; + + selector.add(n1); + selector.add(n2); + selector.add(n3); + + ASSERT_EQ(selector.bestOptim(), LicmOpt); +} + +TEST(ICNodeSelector, selectNodeEmpty) { + NodeSelector selector; + DecisionTreeNode *n = selector.selectNode(); + + ASSERT_TRUE(n == NULL); +} + +TEST(ICNodeSelector, selectNodeOneOptim) { + NodeSelector selector; + DecisionTreeNode *n = new DecisionTreeNode(); + + n->Optimization = LicmOpt; + n->Fitness = 100; + n->Priority = 500; + + selector.add(n); + + DecisionTreeNode *selectedNode = selector.selectNode(); + + ASSERT_FALSE(selectedNode == NULL); + ASSERT_TRUE(selectedNode == n); +} + +TEST(ICNodeSelector, usedOptimsOnlyOne) { + NodeSelector selector; + DecisionTreeNode *n1 = new DecisionTreeNode(); + DecisionTreeNode *n2 = new DecisionTreeNode(); + DecisionTreeNode *s1 = NULL, *s2 = NULL; + + n1->Optimization = LicmOpt; + n1->Fitness = 100; + n1->Priority = 100; + selector.add(n1); + s1 = selector.selectNode(); + ASSERT_FALSE(s1 == NULL); + ASSERT_TRUE(s1 == n1); + ASSERT_EQ(selector.getList(LicmOpt).size(), 0); + + n2->Optimization = LicmOpt; + n2->Fitness = 100; + n2->Priority = 100; + selector.add(n2); + s2 = selector.selectNode(); + + ASSERT_FALSE(s2 == NULL); + ASSERT_TRUE(s2 == n2); +} + +TEST(ICNodeSelector, usedOptimsSwapTwo) { + NodeSelector selector; + DecisionTreeNode *n1 = new DecisionTreeNode; + DecisionTreeNode *n2 = new DecisionTreeNode; + DecisionTreeNode *s1, *s2, *s3; + s1 = s2 = s3 = NULL; + + n1->Optimization = LicmOpt; + n1->Priority = 500; + n1->Fitness = 500; + + n2->Optimization = InlinerOpt; + n2->Priority = 500; + n2->Fitness = 600; + + selector.add(n1); + selector.add(n2); + s1 = selector.selectNode(); + + selector.add(n1); + selector.add(n2); + s2 = selector.selectNode(); + + selector.add(n1); + selector.add(n2); + s3 = selector.selectNode(); + + ASSERT_FALSE(s1 == NULL); + ASSERT_FALSE(s2 == NULL); + ASSERT_FALSE(s3 == NULL); + + ASSERT_EQ(LicmOpt, s1->Optimization); + ASSERT_EQ(InlinerOpt, s2->Optimization); + ASSERT_EQ(LicmOpt, s3->Optimization); +} + +TEST(ICNodeList, addNode) { + NodeList list; + DecisionTreeNode *node = new DecisionTreeNode; + + list.add(node); + + ASSERT_EQ(list.size(), 1); +} + +TEST(ICNodeList, addSameFitness) { + NodeList list; + DecisionTreeNode *n1 = new DecisionTreeNode; + n1->Fitness = 100; + + DecisionTreeNode *n2 = new DecisionTreeNode; + n2->Fitness = 100; + + list.add(n1); + list.add(n2); + + ASSERT_EQ(list.size(), 2); +} + +TEST(ICNodeList, addBetterFitness) { + NodeList list; + + ASSERT_EQ(list.size(), 0); + + DecisionTreeNode *n1 = new DecisionTreeNode; + DecisionTreeNode *n2 = new DecisionTreeNode; + DecisionTreeNode *n3 = new DecisionTreeNode; + + n1->Fitness = 300; + list.add(n1); + ASSERT_EQ(list.size(), 1); + + n2->Fitness = 200; + list.add(n2); + ASSERT_EQ(list.size(), 1); + + n3->Fitness = 200; + list.add(n3); + ASSERT_EQ(list.size(), 2); +} + +TEST(ICNodeList, addWorseFitness) { + NodeList list; + DecisionTreeNode *n1 = new DecisionTreeNode; + DecisionTreeNode *n2 = new DecisionTreeNode; + DecisionTreeNode *n3 = new DecisionTreeNode; + + n1->Fitness = 200; + n2->Fitness = 200; + n3->Fitness = 300; + + list.add(n1); + list.add(n2); + list.add(n3); + + ASSERT_EQ(list.size(), 2); +} + +TEST(ICNodeList, addBetterPrioritySameFitness) { + NodeList list; + DecisionTreeNode *n1 = new DecisionTreeNode; + DecisionTreeNode *n2 = new DecisionTreeNode; + + n1->Fitness = 100; + n2->Fitness = 100; + + n1->Priority = 500; + n2->Priority = 600; + + list.add(n1); + list.add(n2); + + ASSERT_EQ(list.size(), 1); +} + +TEST(ICNodeList, addWorsePrioritySameFitness) { + NodeList list; + DecisionTreeNode *n1 = new DecisionTreeNode; + DecisionTreeNode *n2 = new DecisionTreeNode; + + n1->Fitness = 100; + n1->Priority = 200; + + n2->Fitness = 100; + n2->Priority = 100; + + list.add(n1); + list.add(n2); + + ASSERT_EQ(list.size(), 1); +} + +TEST(ICNodeList, clearList) { + NodeList list; + DecisionTreeNode *n1 = new DecisionTreeNode; + DecisionTreeNode *n2 = new DecisionTreeNode; + + list.add(n1); + ASSERT_EQ(list.size(), 1); + + list.clear(); + ASSERT_EQ(list.size(), 0); + + list.add(n2); + ASSERT_EQ(list.size(), 1); +} + + +TEST(ICDecisionTreeNode, NodeCompareEqual) { + DecisionTreeNode n1, n2, n3; + + n1.Fitness = 100; + n1.Priority = 100; + + n2.Fitness = 100; + n2.Priority = 100; + + n3.Fitness = 100; + n3.Priority = 200; + + ASSERT_EQ(n1, n2); + ASSERT_FALSE(n1 == n3); + + ASSERT_NE(n1, n3); + ASSERT_FALSE(n1 != n2); +} + +TEST(ICDecisionTreeNode, NodeCompareGreater) { + DecisionTreeNode n1, n2, n3, n4, n5; + + n1.Fitness = 100; + n1.Priority = 500; + + n2.Fitness = 200; + n2.Priority = 500; + + n3.Fitness = 100; + n3.Priority = 500; + + n4.Fitness = 50; + n4.Priority = 500; + + n5.Fitness = 100; + n5.Priority = 400; + + ASSERT_TRUE(n1 > n2); + ASSERT_FALSE(n1 > n3); + ASSERT_FALSE(n1 > n4); + ASSERT_TRUE(n1 > n5); +} + +TEST(ICDecisionTreeNode, NodeCompareLess) { + DecisionTreeNode n1, n2; + + n1.Optimization = LicmOpt; + n1.Fitness = 300; + n1.Priority = 500; + + n2.Optimization = RegAllocOpt; + n2.Fitness = 500; + n2.Priority = 500; + + ASSERT_TRUE(n2 < n1); +} + + +} +} Index: unittests/Analysis/ICParallel.cpp =================================================================== --- /dev/null +++ unittests/Analysis/ICParallel.cpp @@ -0,0 +1,306 @@ +#include "gtest/gtest.h" +#include "llvm/Analysis/IterativeCompilation.h" + +namespace llvm { +namespace { + +// Scenario 0: +// --------------- +// Set module phase +// getDecision +// assert that node is added +// getDecision +// assert that node is added +// setCurrentFunctionAndPhase() +// assert that tree has changed +// getDecision() +// assert that node is added +// getDecision() +// assert that node is added +TEST(ICParallel, TestProxyCreation) { + ModuleDecisionTreeProxies MDTP; + MDTP.setIterativeCompilation(true); + MDTP.setModuleCompilationPhase(); + + DecisionTreeProxy &moduleTree = MDTP.getDecisionTreeProxy("module-id", + FnNameAndPhase::ModulePhase); + ASSERT_EQ(0u, moduleTree.getPriorities().size()); + + MDTP.getDecision(100, InlinerOpt); + ASSERT_EQ(1u, moduleTree.getPriorities().size()); + + MDTP.getDecision(100, InlinerOpt); + ASSERT_EQ(2u, moduleTree.getPriorities().size()); + + MDTP.setCurrentFunctionAndPhase("f1", FnNameAndPhase::FunctionPhase); + DecisionTreeProxy &fnTree = MDTP.getDecisionTreeProxy("f1", + FnNameAndPhase::FunctionPhase); + + ASSERT_EQ(0u, fnTree.getPriorities().size()); + + MDTP.getDecision(100, LicmOpt); + ASSERT_EQ(1u, fnTree.getPriorities().size()); + + MDTP.setModuleCompilationPhase(); + MDTP.getDecision(100, InlinerOpt); + ASSERT_EQ(3u, moduleTree.getPriorities().size()); + + MDTP.setCurrentFunctionAndPhase("f2", FnNameAndPhase::FunctionPhase); + DecisionTreeProxy &fn2Tree = MDTP.getDecisionTreeProxy("f2", + FnNameAndPhase::FunctionPhase); + + ASSERT_EQ(0u, fn2Tree.getPriorities().size()); + MDTP.getDecision(100, LicmOpt); + + ASSERT_EQ(1u, fn2Tree.getPriorities().size()); +} + +// Scenario 1: +// ------------- +// given that MDTP is empty +// when we select module +// and we call getDecision() +// and select current function +// and call getDecision() few times +// when we get results +// then assert that in results there are tree entries we need +bool compare_results(MdtResults r1, MdtResults r2) { + bool res = true; + + res &= r1.FunctionNameAndPhase.getName() == r2.FunctionNameAndPhase.getName(); + res &= r1.FunctionNameAndPhase.getPhase() == r2.FunctionNameAndPhase.getPhase(); + + res &= r1.Fitness == r2.Fitness; + res &= r1.Priorities == r2.Priorities; + res &= r1.Optimizations == r2.Optimizations; + + return res; +} + +bool results_are_same(std::vector rv1, std::vector rv2){ + if(rv1.size() != rv2.size()) { + return false; + } + + bool res = true; + + for(unsigned int i = 0; i < rv1.size(); i++) { + res &= compare_results(rv1[i], rv2[i]); + } + + return res; +} + +TEST(ICParallel, ResultsFiles) { + ModuleDecisionTreeProxies MDTP; + MDTP.setIterativeCompilation(true); + + MDTP.setModuleCompilationPhase(); + MDTP.getDecision(10, InlinerOpt); + + MDTP.setCurrentFunctionAndPhase("f1", FnNameAndPhase::FunctionPhase); + MDTP.getDecision(100, LicmOpt); + MDTP.getDecision(110, LicmOpt); + MDTP.getDecision(120, LicmOpt); + + std::vector oResults; + MDTP.getResults(oResults); + + std::string s = MdtResults::generateMdtResultsString(oResults); + + std::string err; + std::vector iResults; + MdtResults::parseMdtResults(iResults, s, err); + + ASSERT_TRUE(results_are_same(iResults, oResults)); +} + +// Scenario 2: +// ------------- +// given that MDTP is populated +// when we get results +// and load them to module decision trees +// then assert that needed trees are created +TEST(ICParallel, LoadParallelResults) { + ModuleDecisionTreeProxies MDTP1, MDTP2; + MDTP1.setIterativeCompilation(true); + MDTP2.setIterativeCompilation(true); + + // IPO phase - global tree + MDTP1.setModuleCompilationPhase(); + MDTP1.getDecision(10, InlinerOpt); + MDTP1.getDecision(11, InlinerOpt); + + // function phase - tree per function + MDTP1.setCurrentFunctionAndPhase("f1", FnNameAndPhase::FunctionPhase); + MDTP1.getDecision(100, LicmOpt); + MDTP1.getDecision(110, LicmOpt); + MDTP1.getDecision(120, LicmOpt); + + MDTP1.setCurrentFunctionAndPhase("f2", FnNameAndPhase::FunctionPhase); + MDTP1.getDecision(100, LicmOpt); + MDTP1.getDecision(110, LicmOpt); + MDTP1.getDecision(120, LicmOpt); + + // codegen phase - tree per function + MDTP2.setCurrentFunctionAndPhase("f1", FnNameAndPhase::CodeGenPhase); + MDTP2.getDecision(100, RegAllocOpt); + MDTP2.getDecision(110, RegAllocOpt); + MDTP2.getDecision(120, RegAllocOpt); + + // this goes into f1 tree, but results 2 (codegen) + MDTP2.setCurrentFunctionAndPhase("f2", FnNameAndPhase::CodeGenPhase); + MDTP2.getDecision(100, RegAllocOpt); + MDTP2.getDecision(110, RegAllocOpt); + MDTP2.getDecision(120, RegAllocOpt); + + // fetch results + std::vector results1, results2; + std::vector mergedResults; + + MDTP1.getResults(results1); + MDTP2.getResults(results2); + + ASSERT_EQ(3u, results1.size()); // module, and licm for f1 and f2 + ASSERT_EQ(2u, results2.size()); // just regalloc for f1 and f2 + // skip conversion to and from file + + MdtResults::mergeMdtResults(mergedResults, results1, results2); + ASSERT_EQ(5u, mergedResults.size()); + + ModuleDecisionTrees MDT; + MDT.applyResults(mergedResults); + + ModuleDecisionTreeProxies MDTP3; + MDTP3.setIterativeCompilation(true); + MDTP3.setModuleCompilationPhase(); + + MDTP3.setModuleCompilationPhase(); + MDTP3.getDecision(10, InlinerOpt); + MDTP3.getDecision(11, InlinerOpt); + + MDTP3.setCurrentFunctionAndPhase("f1", FnNameAndPhase::FunctionPhase); + MDTP3.getDecision(100, LicmOpt); + MDTP3.getDecision(110, LicmOpt); + MDTP3.getDecision(120, LicmOpt); + + MDTP3.setCurrentFunctionAndPhase("f2", FnNameAndPhase::FunctionPhase); + MDTP3.getDecision(100, LicmOpt); + MDTP3.getDecision(110, LicmOpt); + MDTP3.getDecision(120, LicmOpt); + + results1.clear(); + results2.clear(); + mergedResults.clear(); + + MDTP3.getResults(results1); + MdtResults::mergeMdtResults(mergedResults, results1, results2); + MDT.applyResults(mergedResults); + + ASSERT_EQ(5u, MDT.getDecisionTrees().size()); +} + +// Scenario 3: +// ----------- +// given that there are more than one decision tree +// when we call select path with total number of iterations +// and with current iteration +// then assert that selected nodes are in LICM if current < total/3 +// and assert that selected nodes are in INLINER if current < 2*total/3 +// and assert that selected nodes are in REGALLOC if current > 2*total/3 +TEST(ICParallel, SelectNode) { + ModuleDecisionTreeProxies MDTP1, MDTP2, MDTP3; + std::vector results1, results2, mergedResults; + ModuleDecisionTrees MDT(3); // total number of iterations + MDT.startNewIteration(); + + MDTP1.setIterativeCompilation(true); + MDTP2.setIterativeCompilation(true); + MDTP3.setIterativeCompilation(true); + + MDTP1.setModuleCompilationPhase(); + MDTP1.getDecision(20, InlinerOpt); + MDTP1.getDecision(15, InlinerOpt); + + MDTP1.setCurrentFunctionAndPhase("f1", FnNameAndPhase::FunctionPhase); + MDTP1.getDecision(100, LicmOpt); + MDTP1.getDecision(250, LicmOpt); + MDTP1.getDecision(150, LicmOpt); + + MDTP2.setCurrentFunctionAndPhase("f1", FnNameAndPhase::CodeGenPhase); + MDTP2.getDecision(500, RegAllocOpt); + MDTP2.getDecision(610, RegAllocOpt); + MDTP2.getDecision(520, RegAllocOpt); + + MDTP1.getResults(results1); + MDTP2.getResults(results2); + MdtResults::mergeMdtResults(mergedResults, results1, results2); + + MDT.applyResults(mergedResults); + MDT.updateBestFunctionFitness(0); + MDT.selectPath(false); + + FnNameAndPhase codegenPhase("f1", FnNameAndPhase::CodeGenPhase); + FnNameAndPhase precodegenPhase("f1", FnNameAndPhase::FunctionPhase); + FnNameAndPhase modulePhase("module-id", FnNameAndPhase::ModulePhase); + + DecisionTree &precodegenDT = MDT.getDecisionTree(precodegenPhase); + DecisionTree &moduleDT = MDT.getDecisionTree(modulePhase); + DecisionTree &codegenDT = MDT.getDecisionTree(codegenPhase); + + ASSERT_EQ(2u, precodegenDT.getPath().size()); + ASSERT_EQ(0u, moduleDT.getPath().size()); + ASSERT_EQ(0u, codegenDT.getPath().size()); + + ICPathsMap paths; + ICPathsMap pathsBeforeCodegen; + ICPathsMap pathsAfterCodegen; + + MDT.getPaths(paths); + MDT.splitPathsMap(paths, pathsBeforeCodegen, pathsAfterCodegen); + MDTP3.setPaths(pathsBeforeCodegen); + + MDT.startNewIteration(); + // MDT.selectPath(false); + // std::cout << paths.size() << std::endl; + + // DecisionTree &dt = MDT.getDecisionTree(FnNameAndPhase("f1", FnNameAndPhase::FunctionPhase)); + // std::cout << "node count: " << dt.getNodeIdCount() << std::endl; + // dt.selectPath(false); + // BitVector path = dt.getPath(); + // + // std::cout << BitVector2Str(path) << std::endl; + + // load results into proxy - setPaths() + // + // set iterative comp on MDTP3 + // set total iterations + // start new iteration + // select node + // create new proxies + // get and apply results again + // start new iteration + // select node + FAIL() << "in progress"; +} + +// Scenario 4: +// ------------ +// given that there are more than one decision tree +// when we go through all of iterations for an optimization point +// then assert that after that we always return the best, and not the last path +// for every tree of that optimization point +TEST(ICParallel, ReturnBestTree) { + FAIL() << "finish this test"; +} + +// Scenario 5: +// ------------ +// Merge parallel trees and do we need it? +// Is applyResults() enough? +TEST(ICParallel, MergeResults) { + FAIL() << "finish this test"; +} + +} +} Index: unittests/Analysis/ICProxies.cpp =================================================================== --- /dev/null +++ unittests/Analysis/ICProxies.cpp @@ -0,0 +1,99 @@ +#include "gtest/gtest.h" +#include "llvm/Analysis/ICProxies.h" +#include +#include +#include +#include "llvm/ADT/BitVector.h" +#include + +namespace llvm { +namespace { + +void addNode(DecisionTree &dt, int priority) { + static int nodeIdCtr = 1; + DecisionTreeNode *newNode; + + newNode = new DecisionTreeNode; + newNode->NodeId = nodeIdCtr++; + newNode->Fitness = 0; + newNode->Priority = priority; + newNode->Optimization = LicmOpt; + dt.addPrimaryDecision(newNode); +} + +TEST(ICProxies, ModuleDecisionTreesEmpty) +{ + ModuleDecisionTrees MDT; + + std::map paths; + MDT.getPaths(paths); + + std::string result = generateMdtPathsString(paths); + + ASSERT_STREQ("[\n]\n", result.c_str()); +} + +TEST(ICProxies, ModuleDecisionTreesOnePhase) +{ + std::string moduleId = "module-id"; + std::string result; + + ModuleDecisionTrees MDT; + FnNameAndPhase nameAndPhase(moduleId, FnNameAndPhase::ModulePhase); + std::map paths; + + MDT.getPaths(paths); + result = generateMdtPathsString(paths); + + DecisionTree &dt = MDT.getDecisionTree(nameAndPhase); + + addNode(dt, 300); + addNode(dt, 300); + addNode(dt, 300); + addNode(dt, 300); + addNode(dt, 450); + addNode(dt, 500); + + dt.selectPath(false); + MDT.getPaths(paths); + result = generateMdtPathsString(paths); + + std::stringstream s; + s << "[\n"; + s << " {\n"; + s << " \"Fn\":\"module-id\",\n"; + s << " \"Phase\":1,\n"; + s << " \"Path\":\"000001\"\n"; + s << " }\n"; + s << "]\n"; + + ASSERT_STREQ(s.str().c_str(), result.c_str()); +} + +TEST(ICProxies, ModuleDecisionTreesGetDecision) { + DecisionTreeProxy mdt; + + BitVector path(4,0); + path.set(2); + + mdt.getPath() = path; + + ASSERT_FALSE(mdt.getDecision(100, LicmOpt)); + ASSERT_FALSE(mdt.getDecision(200, LicmOpt)); + ASSERT_TRUE(mdt.getDecision(300, LicmOpt)); + ASSERT_FALSE(mdt.getDecision(400, InlinerOpt)); + + ASSERT_EQ(0u, mdt.getPriorities().size()); + ASSERT_EQ(0u, mdt.getOptimizations().size()); + + ASSERT_FALSE(mdt.getDecision(500, LicmOpt)); + + ASSERT_EQ(1u, mdt.getPriorities().size()); + ASSERT_EQ(1u, mdt.getOptimizations().size()); + + ASSERT_EQ(500, mdt.getPriorities()[0]); + ASSERT_EQ(LicmOpt, mdt.getOptimizations()[0]); +} + +} +} Index: unittests/Analysis/ICUtils.cpp =================================================================== --- /dev/null +++ unittests/Analysis/ICUtils.cpp @@ -0,0 +1,186 @@ +#include "gtest/gtest.h" +#include "llvm/Analysis/ICProxies.h" +#include "llvm/ADT/BitVector.h" +#include +#include +#include +#include + +namespace llvm { +namespace { + +// fixtures +MdtResults* createModuleResults(std::string moduleName, int prio) { + MdtResults *moduleResults = new MdtResults; + + moduleResults->FunctionNameAndPhase = + FnNameAndPhase(moduleName, FnNameAndPhase::ModulePhase); + + moduleResults->Optimizations.push_back(InlinerOpt); + moduleResults->Optimizations.push_back(InlinerOpt); + moduleResults->Optimizations.push_back(InlinerOpt); + + moduleResults->Priorities.push_back(100+prio); + moduleResults->Priorities.push_back(200+prio); + moduleResults->Priorities.push_back(300+prio); + + return moduleResults; +} + +MdtResults* createFnResults(std::string fnName, int prio) { + MdtResults *fnResults = new MdtResults; + + fnResults->FunctionNameAndPhase = + FnNameAndPhase(fnName, FnNameAndPhase::FunctionPhase); + + fnResults->Optimizations.push_back(LicmOpt); + fnResults->Optimizations.push_back(LicmOpt); + fnResults->Optimizations.push_back(LicmOpt); + + fnResults->Priorities.push_back(100+prio); + fnResults->Priorities.push_back(200+prio); + fnResults->Priorities.push_back(300+prio); + + return fnResults; +} + +// Parsers and generators + +TEST(ICUtils, PathToString) +{ + std::string moduleNameId = "module-id"; + FnNameAndPhase nameAndPhase = FnNameAndPhase(moduleNameId, + FnNameAndPhase::ModulePhase); + + BitVector path(4, false); + path.resize(path.size()+1, true); + + std::string result = Path2Str(nameAndPhase, path); + + std::stringstream target; + target << " {\n"; + target << " \"Fn\":\"module-id\",\n"; + target << " \"Phase\":1,\n"; + target << " \"Path\":\"00001\"\n"; + target << " }"; + + ASSERT_STREQ(target.str().c_str(), result.c_str()); +} + + +// TEST(ICUtils, MdtResultsParseMdtResults) { +// // needs refactoring +// // write this test first and develop helper methods +// // by TDD principles +// } +// +// TEST(ICUtils, MdtResultsGenerateMdtResultsString) { +// } +// +// TEST(ICUtils, ICPathsMapParseMdtPaths) { +// } +// +// TEST(ICUtils, ICPathsMapGenerateMdtPaths) { +// } +// +// TEST(ICUtils, ICPathsMapPath2Str) { +// } +// +// TEST(ICUtils, ICPathsMapBitVector2Str) { +// } + +// IC Utils logic +TEST(ICUtils, FnNameAndPhaseCompare) { + FnNameAndPhase modulePhase("module-id", FnNameAndPhase::ModulePhase); + FnNameAndPhase fnPhase("fun1", FnNameAndPhase::FunctionPhase); + FnNameAndPhase fnPhase2("fun2", FnNameAndPhase::FunctionPhase); + FnNameAndPhase codegenPhase("codegen", FnNameAndPhase::CodeGenPhase); + + ASSERT_TRUE(fnPhase < modulePhase); + ASSERT_TRUE(fnPhase < codegenPhase); + ASSERT_TRUE(modulePhase < codegenPhase); + + ASSERT_TRUE(fnPhase < fnPhase2); +} + +TEST(ICUtils, MdtResultsMergeMdtResultsOnlyFirstResult) { + std::vector mergedResults; + std::vector precodegenResults; + std::vector codegenResults; + + MdtResults *moduleResults = createModuleResults("module-id", 0); + precodegenResults.push_back(*moduleResults); + + MdtResults::mergeMdtResults(mergedResults, precodegenResults, codegenResults); + MdtResults *target; + target = MdtResults::getByPhase(mergedResults, FnNameAndPhase::ModulePhase); + ASSERT_TRUE(target != NULL); +} + +TEST(ICUtils, MdtResultsMergeMdtResultsOnlySecondResult) { + std::vector mergedResults; + std::vector precodegenResults; + std::vector codegenResults; + + MdtResults *moduleResults = createModuleResults("module-id", 0); + codegenResults.push_back(*moduleResults); + + MdtResults::mergeMdtResults(mergedResults, precodegenResults, codegenResults); + MdtResults *target; + target = MdtResults::getByPhase(mergedResults, FnNameAndPhase::ModulePhase); + ASSERT_TRUE(target != NULL); +} + +TEST(ICUtils, MdtResultsMergeMdtResultsBoth) { + std::vector mergedResults; + std::vector precodegenResults; + std::vector codegenResults; + + MdtResults *moduleResults1 = createModuleResults("module-id", 0); + MdtResults *moduleResults2 = createModuleResults("module-id", 10); + + precodegenResults.push_back(*moduleResults1); + codegenResults.push_back(*moduleResults2); + + MdtResults::mergeMdtResults(mergedResults, precodegenResults, codegenResults); + MdtResults *target; + target = MdtResults::getByPhase(mergedResults, FnNameAndPhase::ModulePhase); + + ASSERT_TRUE(target != NULL); + ASSERT_EQ(6u, target->Priorities.size()); + ASSERT_EQ(100, target->Priorities[0]); + ASSERT_EQ(200, target->Priorities[1]); + ASSERT_EQ(300, target->Priorities[2]); + ASSERT_EQ(110, target->Priorities[3]); + ASSERT_EQ(210, target->Priorities[4]); + ASSERT_EQ(310, target->Priorities[5]); +} + +TEST(ICUtils, MdtResultsGetByPhase) { + std::vector results; + + MdtResults *moduleResults = createModuleResults("module-id", 0); + MdtResults *fnResults = createFnResults("fn1", 10); + + MdtResults *target; + + target = MdtResults::getByPhase(results, FnNameAndPhase::ModulePhase); + ASSERT_EQ(NULL, target); + + results.push_back(*moduleResults); + target = MdtResults::getByPhase(results, FnNameAndPhase::ModulePhase); + ASSERT_TRUE(target != NULL); + ASSERT_STREQ("module-id", target->FunctionNameAndPhase.getName().c_str()); + + target = MdtResults::getByPhase(results, FnNameAndPhase::FunctionPhase); + ASSERT_EQ(NULL, target); + + results.push_back(*fnResults); + target = MdtResults::getByPhase(results, FnNameAndPhase::FunctionPhase); + ASSERT_TRUE(target != NULL); + ASSERT_STREQ("fn1", target->FunctionNameAndPhase.getName().c_str()); +} + + +} +}