Index: include/llvm/Analysis/DecisionTree.h =================================================================== --- /dev/null +++ include/llvm/Analysis/DecisionTree.h @@ -0,0 +1,231 @@ +//===-- DecisionTree.h - Implement Decision Tree Classes --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the decision tree and decision tree proxy classes +// which are used in iterative compilation. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_DECISIONTREE_H +#define LLVM_ANALYSIS_DECISIONTREE_H + +#include +#include +#include +#include "llvm/ADT/BitVector.h" +#include "llvm/Pass.h" + +namespace llvm { + +const int MaxDtPriority = 1000; + +class FnNameAndPhase { +public: + enum IterativeCompilationPhase { + 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, + IterativeCompilationPhase 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; } +IterativeCompilationPhase getPhase() const { return Phase; } + +protected: + std::string Name; + IterativeCompilationPhase Phase; +}; + +class MdtResults { +public: + FnNameAndPhase FunctionNameAndPhase; + int Fitness; + std::vector Priorities; +}; + +struct DecisionTreeNode { + int calcFinalPriority(int bestFunctionFitness); + DecisionTreeNode *Parent; + DecisionTreeNode *PrimaryDecision; + DecisionTreeNode *AlternativeDecision; + int Priority; + int Fitness; + int Depth; + int NodeId; + bool IsInterprocedural; +}; + +/// Decision tree controls the iterative compilation process so +/// that compiler takes different path in each compilation except in +/// the final iteration when the path which generates the best code is taken . +class DecisionTree { +private: + DecisionTreeNode *DecisionTreeRoot; + DecisionTreeNode *CurrentNode; + BitVector Path; + int FunctionFitness; + int BestFunctionFitness; + BitVector BestPath; + int NodeIdCount; + +public: + DecisionTree(); + ~DecisionTree(); + + int getFunctionFitness() const { return FunctionFitness; } + void setFunctionFitness(int x) { FunctionFitness = x; } + BitVector &getPath() { return Path; } + const BitVector &getPath() const { return Path; } + + bool getDecision(int priority); + void updateBestFunctionFitness(int iteration); + void findPath(DecisionTreeNode *node, BitVector &path); + bool selectPath(bool FinalPass); + void startNewIteration(); + void updateNodesFitness(); + + void applyResults(const MdtResults &results); + + static void writeToFile(const std::string &fileName, const std::string &data); + static std::string readFromFile(const std::string &fileName); +}; + +/// Decision tree proxy is the proxy class for the decision tree so +/// that it has the method getDecision and the all data can be effectively +/// streamed between proxy and the decision tree. +class DecisionTreeProxy { +public: + DecisionTreeProxy(); + + BitVector &getPath() { return Path; } + const BitVector &getPath() const { return Path; } + int getFunctionFitness() const { return FunctionFitness; } + void setFunctionFitness(int x) { FunctionFitness = x; } + std::vector &getPriorities() { return Priorities; } + const std::vector &getPriorities() const { return Priorities; } + + bool getDecision(int priority); + + std::string generateResultsString(); + MdtResults getResults() const; + void setPath(const BitVector &path); + +protected: + BitVector Path; + int FunctionFitness; + int BestFunctionFitness; + std::vector Priorities; + int CurrentDepth; +}; + +/// This class is the storage for all the decision trees for +/// each function and compilation phase. +class ModuleDecisionTrees { +public: + + ModuleDecisionTrees(); + ~ModuleDecisionTrees(); + + DecisionTree &getDecisionTree(const FnNameAndPhase &fnNameAndPhase); + + void startNewIteration(); + void getPaths(std::map &paths); + void applyResults(const std::vector &results); + void updateBestFunctionFitness(int iteration); + void updateNodesFitness(); + void selectPath(bool FinalPass); + std::string &getICInputFile() { return ICInputFile; } + std::string &getICResultsFile() { return ICResultsFile; } + std::string &getICResultsFile2() { return ICResultsFile2; } + std::string &getICInputFileOpt() { return ICInputFileOpt; } + std::string &getICResultsFileOpt() { return ICResultsFileOpt; } + std::string &getICResultsFile2Opt() { return ICResultsFile2Opt; } + +protected: + std::map DecisionTrees; + std::string ICInputFile; + std::string ICResultsFile; + std::string ICResultsFile2; + std::string ICInputFileOpt; + std::string ICResultsFileOpt; + std::string ICResultsFile2Opt; + +public: + static bool parseMdtPaths( + std::map &paths, + const std::string &pathString, + std::string &ErrorMessage); + static std::string generateMdtPathsString( + const std::map &paths); + static bool parseMdtResults(std::vector &results, + const std::string &resString, + std::string &ErrorMessage); + static std::string generateMdtResultsString( + const std::vector &results); + + static int calculateTotalFitness(const std::vector &results); +}; + +/// 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); + + void setCurrentFunctionAndPhase(const std::string &fnName, + FnNameAndPhase::IterativeCompilationPhase phase); + void setModuleCompilationPhase(); + DecisionTreeProxy &getDecisionTreeProxy(const FnNameAndPhase &x); + DecisionTreeProxy &getDecisionTreeProxy(const std::string &name, + FnNameAndPhase::IterativeCompilationPhase phase); + void setPaths(std::map &paths); + void getResults(std::vector &results) const; + DecisionTreeProxy *getCurrFnDecisionTreeProxy() + { return CurrFnDecisionTreeProxy; } + bool getIterativeCompilation() { return IterativeCompilation; } + void setIterativeCompilation(bool x) { IterativeCompilation = x; } +protected: + bool IterativeCompilation; + std::map DecisionTreeProxies; + DecisionTreeProxy *CurrFnDecisionTreeProxy; + FnNameAndPhase::IterativeCompilationPhase ICPhase; +}; + +} + +#endif Index: include/llvm/Analysis/ICSetCurrentFunc.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ICSetCurrentFunc.h @@ -0,0 +1,42 @@ +//===-- ICSetCurrentFunc.h - Iterative Comp Set Current Func DT -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Implements the pass which sets the decision tree proxy of the +// current function. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ICSETCURRENTFUNC_H +#define LLVM_ANALYSIS_ICSETCURRENTFUNC_H + +#include "llvm/Pass.h" +#include "llvm/Analysis/DecisionTree.h" + +namespace llvm { + +class ICSetCurrentFunc : public FunctionPass { +public: + std::string name; + ModuleDecisionTreeProxies *MD; + static char ID; + ICSetCurrentFunc() : FunctionPass(ID) { + initializeICSetCurrentFuncPass(*PassRegistry::getPassRegistry()); + } + + virtual bool runOnFunction(Function &F); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); + } +}; + +} + +#endif Index: include/llvm/Analysis/Passes.h =================================================================== --- include/llvm/Analysis/Passes.h +++ include/llvm/Analysis/Passes.h @@ -157,6 +157,13 @@ // FunctionPass *createMemDepPrinter(); + //===--------------------------------------------------------------------===// + // + // createICSetCurrentFuncPass - This pass sets decision tree proxy of the + // current function which is used in iterative compilation. + // + FunctionPass *createICSetCurrentFuncPass(); + // createJumpInstrTableInfoPass - This creates a pass that stores information // about the jump tables created by JumpInstrTables ImmutablePass *createJumpInstrTableInfoPass(); Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -283,6 +283,9 @@ void initializeStackMapLivenessPass(PassRegistry&); void initializeMachineCombinerPass(PassRegistry &); void initializeLoadCombinePass(PassRegistry&); +void initializeModuleDecisionTreeProxiesPass(PassRegistry&); +void initializeFunctionFitnessPass(PassRegistry&); +void initializeICSetCurrentFuncPass(PassRegistry&); } #endif Index: include/llvm/Transforms/IPO/InlinerPass.h =================================================================== --- include/llvm/Transforms/IPO/InlinerPass.h +++ include/llvm/Transforms/IPO/InlinerPass.h @@ -25,6 +25,7 @@ class InlineCost; template class SmallPtrSet; + class ModuleDecisionTreeProxies; /// Inliner - This class contains all of the helper code which is used to /// perform the inlining operations that do not depend on the policy. @@ -81,6 +82,8 @@ // InsertLifetime - Insert @llvm.lifetime intrinsics. bool InsertLifetime; + ModuleDecisionTreeProxies *MDTP; + /// shouldInline - Return true if the inliner should attempt to /// inline at the given CallSite. bool shouldInline(CallSite CS); Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -68,6 +68,8 @@ initializeTargetTransformInfoAnalysisGroup(Registry); initializeTypeBasedAliasAnalysisPass(Registry); initializeScopedNoAliasAAPass(Registry); + initializeModuleDecisionTreeProxiesPass(Registry); + initializeICSetCurrentFuncPass(Registry); } void LLVMInitializeAnalysis(LLVMPassRegistryRef R) { Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -18,10 +18,12 @@ CostModel.cpp CodeMetrics.cpp ConstantFolding.cpp + DecisionTree.cpp Delinearization.cpp DependenceAnalysis.cpp DomPrinter.cpp DominanceFrontier.cpp + ICSetCurrentFunc.cpp IVUsers.cpp InstCount.cpp InstructionSimplify.cpp Index: lib/Analysis/DecisionTree.cpp =================================================================== --- /dev/null +++ lib/Analysis/DecisionTree.cpp @@ -0,0 +1,826 @@ +//===-- DecisionTree.cpp - Implement Decision Tree Classes ----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the decision tree and decision tree proxy classes +// which are used in iterative compilation. +// +//===----------------------------------------------------------------------===// + +/* Here is a brief explanation of the forming of the decision tree. + +First, some passes need to be modified to call getDecision function. +If this function returns false, a pass should do exactly as the code +without modification. If the return value is true, then the alternative +path is taken. + +Function getDecision always returns false in the first iteration. +And the compiler should work exactly as if there was no iterative framework. + +Let us assume that getDecision function is called four times in the +first iteration of iterative compilation. After the end of the first +iteration, the decision tree will look like this: + +o + \ + o + \ + o + \ + o + \ + o + +In the second iteration, exactly one decision is changed and the compiler +works as in the first iteration until it reaches this particular decision. +Then alternative path is taken in this point. Further, getDecision function +returns false until compilation iteration is finished. Let us assume that we +took alternative decision at the third decision and that there are three more +calls of getDecision function. Note that different compilation paths may +have different number of calls of getDecision function. + +o + \ + o + \ + o + / \ + o o + \ \ + o o + \ + o + +Every new iteration adds one new branch to the decision tree. + +At the end of each iteration fitness of the generated code is evaluated. +In the last iteration, the compiler takes the path with the best fitness. + +To augment the selection of a node where alternative decision would be taken, +getDecision tree takes one parameter. This parameter is interpreted as +priority and the node with highest priory is selected for next alternative +decision. +*/ + +#include +#include +#include +#include +#include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/DecisionTree.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/SourceMgr.h" +#include "llvm/Support/YAMLParser.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/ErrorHandling.h" + +using namespace llvm; + +static cl::opt +IterativeCompilationOpt("fiterative-comp", cl::init(false), + cl::desc("Enable iterative compilation")); +static cl::opt +FicInputFile("fic-input-file", cl::init("ic-input")); +static cl::opt +FicResultsFile("fic-results-file", cl::init("ic-results")); +static cl::opt +FicResultsFile2("fic-results2-file", cl::init("ic-results2")); + +DecisionTree::DecisionTree() { + DecisionTreeRoot = new DecisionTreeNode; + NodeIdCount = 0; + FunctionFitness = 0; + BestFunctionFitness = INT_MAX; + CurrentNode = DecisionTreeRoot; + CurrentNode->Parent = 0; + CurrentNode->PrimaryDecision = 0; + CurrentNode->AlternativeDecision = 0; + CurrentNode->Priority = 0; + CurrentNode->Fitness = INT_MAX; + CurrentNode->Depth = 0; + CurrentNode->NodeId = NodeIdCount++; + CurrentNode->IsInterprocedural = false; +} + +DecisionTree::~DecisionTree() { + delete DecisionTreeRoot; +} + +/// This is the function which controls iterative compilation process. +bool DecisionTree::getDecision(int priority) { + unsigned depth = CurrentNode->Depth; + bool decision; + + // If depth is less then the size of the given path, follow this path. + if (depth < Path.size()) { + decision = Path[depth]; + if (decision) { + if (CurrentNode->AlternativeDecision) { + CurrentNode = CurrentNode->AlternativeDecision; + return decision; + } + } else { + if (CurrentNode->PrimaryDecision) { + CurrentNode = CurrentNode->PrimaryDecision; + return decision; + } + } + } + + // Create the new decision tree node. + CurrentNode->Priority = priority; + DecisionTreeNode *newNode = new DecisionTreeNode; + newNode->Parent = CurrentNode; + newNode->PrimaryDecision = 0; + newNode->AlternativeDecision = 0; + newNode->Priority = 0; + newNode->Fitness = INT_MAX; + newNode->Depth = depth + 1; + newNode->NodeId = NodeIdCount++; + newNode->IsInterprocedural = false; + + // Insert the new node in the decision tree. + if (CurrentNode->PrimaryDecision == 0) { + CurrentNode->PrimaryDecision = newNode; + decision = false; + } else { + CurrentNode->AlternativeDecision = newNode; + decision = true; + } + CurrentNode = newNode; + return decision; +} + +/// Updated best function fitness seen so far. +void DecisionTree::updateBestFunctionFitness(int iteration) { + if (FunctionFitness < BestFunctionFitness) { + BestFunctionFitness = FunctionFitness; + findPath(CurrentNode, BestPath); + } + updateNodesFitness(); +} + +/// Find path which leads to the given node. +void DecisionTree::findPath(DecisionTreeNode *node, BitVector &path) { + path.resize(node->Depth); + if (node->PrimaryDecision) + path.resize(node->Depth + 1, true); + while (node != DecisionTreeRoot) { + DecisionTreeNode *parent = node->Parent; + if (node == parent->AlternativeDecision) + path[parent->Depth] = true; + else + path[parent->Depth] = false; + node = parent; + } +} + +/// Select path for the new iteration. In the final iteration use +/// the best path so far. +bool DecisionTree::selectPath(bool FinalPass) { + if (FinalPass) { + Path = BestPath; + return true; + } + + SmallVector nodesToExplore; + int selectedNodePriority = 0; + DecisionTreeNode *selectedNode = 0; + + if (!DecisionTreeRoot->AlternativeDecision + && !DecisionTreeRoot->PrimaryDecision) + selectedNode = DecisionTreeRoot; + + nodesToExplore.push_back(DecisionTreeRoot); + while(!nodesToExplore.empty()) { + DecisionTreeNode *n = nodesToExplore.back(); + nodesToExplore.pop_back(); + if (n->AlternativeDecision == 0 && n->PrimaryDecision != 0) { + double priority = n->calcFinalPriority (BestFunctionFitness); + if (priority > selectedNodePriority) { + selectedNode = n; + selectedNodePriority = priority; + } + } + if (n->AlternativeDecision) + nodesToExplore.push_back(n->AlternativeDecision); + if (n->PrimaryDecision) + nodesToExplore.push_back(n->PrimaryDecision); + } + + if (selectedNode) { + findPath(selectedNode, Path); + return false; + } else { + Path = BestPath; + return true; + } +} + +/// Prepare decision tree for the new iteration. +void DecisionTree::startNewIteration() { + CurrentNode = DecisionTreeRoot; + FunctionFitness = 0; +} + +/// Update fitness field of the nodes on the current path. +void DecisionTree::updateNodesFitness() { + BitVector path; + DecisionTreeNode *n = CurrentNode; + while(n) { + if (n->Fitness > FunctionFitness) + n->Fitness = FunctionFitness; + n = n->Parent; + } +} + +/// Calculate modified priority so that the nodes on the paths which +/// generate better code are more often selected. +int DecisionTreeNode::calcFinalPriority(int bestFunctionFitness) { + if (Fitness == 0) + return Priority; + return (Priority * bestFunctionFitness) / Fitness; +} + +/// Apply results from the decision tree proxy so that the +/// path for the next iteration can be selected. +void DecisionTree::applyResults(const MdtResults &results) { + unsigned pathLen = Path.size(); +// TODO add some comments + for (unsigned i = 0; i < pathLen; i++) + getDecision(0); + for (int t : results.Priorities) + getDecision(t); + setFunctionFitness(results.Fitness); +} + +/// Write contents of the string to the file. +void DecisionTree::writeToFile(const std::string &fileName, + const std::string &data) { + std::error_code EC; + raw_fd_ostream outf(fileName, EC, sys::fs::F_Text); + if (EC) { + report_fatal_error(Twine("can't open file: ") + fileName + + " (" + EC.message() + ")"); + } + outf << data; + outf.close(); +} + +/// Read contents of the file. +std::string DecisionTree::readFromFile(const std::string &fileName) { + llvm::ErrorOr> Buffer = + llvm::MemoryBuffer::getFile(fileName); + if (std::error_code Result = Buffer.getError()) { + report_fatal_error(Twine("Error while opening file: ") + + Result.message()); + } + return (*Buffer)->getBuffer(); +} + +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) { + if (CurrentDepth < (int)Path.size()) { + bool r = Path[CurrentDepth]; + CurrentDepth++; + return r; + } + Priorities.push_back(priority); + CurrentDepth++; + return false; +} + +MdtResults DecisionTreeProxy::getResults() const { + MdtResults results; + results.Priorities = Priorities; + results.Fitness = FunctionFitness; + return results; +} + +void DecisionTreeProxy::setPath(const BitVector &path) { + Path = path; +} + +ModuleDecisionTrees::ModuleDecisionTrees() +{} + +ModuleDecisionTrees::~ModuleDecisionTrees() { + for (auto &P : DecisionTrees) { + DecisionTree *dt = P.second; + delete dt; + } +} + +/// Find required decision tree. +DecisionTree &ModuleDecisionTrees::getDecisionTree( + const FnNameAndPhase &fnNameAndPhase) { + if (DecisionTrees.find(fnNameAndPhase) == DecisionTrees.end()) { + DecisionTrees[fnNameAndPhase] = new DecisionTree(); + } + return *DecisionTrees[fnNameAndPhase]; +} + +/// Inform all decision trees that new iteration of compilation +/// has been started. +void ModuleDecisionTrees::startNewIteration() { + for (auto &P : DecisionTrees) { + DecisionTree *dt = P.second; + dt->startNewIteration(); + } +} + +/// Get selected paths for decision trees. +void ModuleDecisionTrees::getPaths(std::map &paths) { + paths.clear(); + for (const auto &P : DecisionTrees) { + const FnNameAndPhase &fnNameAndPhase = P.first; + const DecisionTree *dt = P.second; + const BitVector &path = dt->getPath(); + paths[fnNameAndPhase] = path; + } +} + +/// Apply results to all decision trees used for a module optimization. +void ModuleDecisionTrees::applyResults(const std::vector &results) { + for (const auto &R : results) { + DecisionTree &DT = getDecisionTree(R.FunctionNameAndPhase); + DT.applyResults(R); + } +} + +/// Updates best function fitness filed for all decision trees. +void ModuleDecisionTrees::updateBestFunctionFitness(int Iteration) { + for (const auto &P : DecisionTrees) { + DecisionTree *DT = P.second; + DT->updateBestFunctionFitness(Iteration); + } +} + +/// Iterates through all decision trees and calls updateNodesFitness +/// on them. +void ModuleDecisionTrees::updateNodesFitness() +{ + for (const auto &P : DecisionTrees) { + DecisionTree *DT = P.second; + DT->updateNodesFitness(); + } +} + +/// Selects path for all decision trees. +void ModuleDecisionTrees::selectPath(bool FinalPass) +{ + for (const auto &P : DecisionTrees) { + DecisionTree *DT = P.second; + DT->selectPath(FinalPass); + } +} + +/// Parses string containing paths for multiple decision trees in JSON +/// format using llmv YAML parser. +bool ModuleDecisionTrees::parseMdtPaths(std::map &paths, + const std::string &pathString, + std::string &ErrorMessage) { + paths.clear(); + SourceMgr SM; + yaml::Stream YAMLStream(pathString, SM); + llvm::yaml::document_iterator I = YAMLStream.begin(); + if (I == YAMLStream.end()) { + ErrorMessage = "Error while parsing YAML."; + return false; + } + llvm::yaml::Node *Root = I->getRoot(); + if (!Root) { + ErrorMessage = "Error while parsing YAML."; + return false; + } + llvm::yaml::SequenceNode *Array = dyn_cast(Root); + if (!Array) { + ErrorMessage = "Expected array."; + return false; + } + for (llvm::yaml::SequenceNode::iterator AI = Array->begin(), + AE = Array->end(); + AI != AE; ++AI) { + llvm::yaml::MappingNode *Object = dyn_cast(&*AI); + if (!Object) { + ErrorMessage = "Expected object."; + return false; + } + llvm::yaml::ScalarNode *Fn = nullptr; + llvm::yaml::ScalarNode *Phase = nullptr; + llvm::yaml::ScalarNode *Path = nullptr; + for (llvm::yaml::MappingNode::iterator KVI = Object->begin(), + KVE = Object->end(); + KVI != KVE; ++KVI) { + llvm::yaml::Node *Value = (*KVI).getValue(); + if (!Value) { + ErrorMessage = "Expected value."; + return false; + } + llvm::yaml::ScalarNode *ValueString = + dyn_cast(Value); + if (!ValueString) { + ErrorMessage = "Expected string as value."; + return false; + } + llvm::yaml::ScalarNode *KeyString = + dyn_cast((*KVI).getKey()); + if (!KeyString) { + ErrorMessage = "Expected strings as key."; + return false; + } + SmallString<8> KeyStorage; + if (KeyString->getValue(KeyStorage) == "Fn") { + Fn = ValueString; + } else if (KeyString->getValue(KeyStorage) == "Phase") { + Phase = ValueString; + } else if (KeyString->getValue(KeyStorage) == "Path") { + Path = ValueString; + } else { + ErrorMessage = ("Unknown key: \"" + + KeyString->getRawValue() + "\"").str(); + return false; + } + } + if (!Fn) { + ErrorMessage = "Missing key: \"Fn\"."; + return false; + } + if (!Phase) { + ErrorMessage = "Missing key: \"Phase\"."; + return false; + } + if (!Path) { + ErrorMessage = "Missing key: \"Path\"."; + return false; + } + SmallString<8> FnStorage; + StringRef FnStr = Fn->getValue(FnStorage); + SmallString<8> PhaseStorage; + StringRef PhaseStr = Phase->getValue(PhaseStorage); + SmallString<8> PathStorage; + StringRef PathStr = Path->getValue(PathStorage); + + FnNameAndPhase::IterativeCompilationPhase CompilationPhase = + (FnNameAndPhase::IterativeCompilationPhase) (atoi(PhaseStr.str().c_str())); + + unsigned N = PathStr.size(); + BitVector PathVector(N); + unsigned i; + for (i = 0; i < N; i++) + PathVector[i] = (PathStr[i] == '0' ? false : true); + + FnNameAndPhase fnNameAndPhase(FnStr.str(), CompilationPhase); + paths[fnNameAndPhase] = PathVector; + } + return true; +} + +/// Converts paths for multiple decision trees to string in JSON format. +std::string ModuleDecisionTrees::generateMdtPathsString( + const std::map &paths) { + std::stringstream s; + s << "[\n"; + unsigned n = paths.size(); + unsigned i = 0; + for (const auto &P : paths) { + const FnNameAndPhase &fnNameAndPhase = P.first; + const BitVector &path = P.second; + s << " {\n"; + s << " \"Fn\":\"" << fnNameAndPhase.getName() << "\",\n"; + s << " \"Phase\":" << (int)fnNameAndPhase.getPhase() << ",\n"; + s << " \"Path\":\""; + unsigned j; + unsigned m = path.size(); + for (j = 0; j < m; j++) + s << path[j]; + s << "\"\n"; + if (i + 1 < n) + s << " },\n"; + else + s << " }\n"; + i++; + } + s << "]\n"; + return s.str(); +} + +/// Parses string containing results for multiple decision trees +/// in JSON format to vector of MdtResults structs using LLMV +/// YAML parser. +bool ModuleDecisionTrees::parseMdtResults( + std::vector &results, + const std::string &resString, + std::string &ErrorMessage) { + results.clear(); + SourceMgr SM; + yaml::Stream YAMLStream(resString, SM); + llvm::yaml::document_iterator I = YAMLStream.begin(); + if (I == YAMLStream.end()) { + ErrorMessage = "Error while parsing YAML."; + return false; + } + llvm::yaml::Node *Root = I->getRoot(); + if (!Root) { + ErrorMessage = "Error while parsing YAML."; + return false; + } + llvm::yaml::SequenceNode *Array = dyn_cast(Root); + if (!Array) { + ErrorMessage = "Expected array."; + return false; + } + for (llvm::yaml::SequenceNode::iterator AI = Array->begin(), + AE = Array->end(); + AI != AE; ++AI) { + llvm::yaml::MappingNode *Object = dyn_cast(&*AI); + if (!Object) { + ErrorMessage = "Expected object."; + return false; + } + llvm::yaml::ScalarNode *Fn = nullptr; + llvm::yaml::ScalarNode *Phase = nullptr; + llvm::yaml::ScalarNode *Fitness = nullptr; + llvm::yaml::SequenceNode *Priorities = nullptr; + std::vector PrioritiesVector; + 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; + } + llvm::yaml::ScalarNode *ValueString = + dyn_cast(Value); + if (!ValueString) { + ErrorMessage = "Expected string as value."; + return false; + } + if (KeyString->getValue(KeyStorage) == "Fn") { + Fn = ValueString; + } else if (KeyString->getValue(KeyStorage) == "Phase") { + Phase = ValueString; + } else if (KeyString->getValue(KeyStorage) == "Fitness") { + Fitness = ValueString; + } else { + ErrorMessage = ("Unknown key: \"" + + KeyString->getRawValue() + "\"").str(); + return false; + } + } + if (!Fn) { + ErrorMessage = "Missing key: \"Fn\"."; + return false; + } + if (!Phase) { + ErrorMessage = "Missing key: \"Phase\"."; + return false; + } + if (!Fitness) { + ErrorMessage = "Missing key: \"Fitness\"."; + return false; + } + if (!Priorities) { + ErrorMessage = "Missing key: \"Priorities\"."; + return false; + } + 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::IterativeCompilationPhase CompilationPhase = + (FnNameAndPhase::IterativeCompilationPhase) (atoi(PhaseStr.str().c_str())); + + MdtResults mdtResults; + mdtResults.FunctionNameAndPhase = + FnNameAndPhase(FnStr.str(), CompilationPhase); + mdtResults.Fitness = atoi(FitnessStr.str().c_str()); + mdtResults.Priorities = PrioritiesVector; + results.push_back(mdtResults); + } + return true; +} + +/// Converts vector of MdtResults to string in JSON format. +std::string ModuleDecisionTrees::generateMdtResultsString( + const std::vector &results) { + unsigned i; + unsigned n = results.size(); + std::stringstream s; + + s << "[\n"; + for (i = 0; i < n; i++) { + const MdtResults &res = results[i]; + const FnNameAndPhase &fnNameAndPhase = res.FunctionNameAndPhase; + s << " {\n"; + s << " \"Fn\":\"" << fnNameAndPhase.getName() << "\",\n"; + s << " \"Phase\":" << (int)fnNameAndPhase.getPhase() << ",\n"; + s << " \"Fitness\":" << res.Fitness << ",\n"; + s << " \"Priorities\":["; + const std::vector &priorities = res.Priorities; + unsigned nPriorities = priorities.size(); + unsigned j; + for (j = 0; j < nPriorities; j++) { + s << priorities[j]; + if (j + 1 < nPriorities) + s << ","; + } + s << "]\n"; + if (i + 1 < n) + s << " },\n"; + else + s << " }\n"; + } + s << "]\n"; + return s.str(); +} + +/// Calculates total module fitness as the sum of the finesses of +/// all functions in the module. +int ModuleDecisionTrees::calculateTotalFitness( + const std::vector &results) { + int tf = 0; + for (const auto &res : results) { + if (res.FunctionNameAndPhase.getPhase() == FnNameAndPhase::CodeGenPhase) + tf += res.Fitness; + } + return tf; +} + +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::IterativeCompilationPhase 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::IterativeCompilationPhase phase) { + return getDecisionTreeProxy(FnNameAndPhase(name, phase)); +} + +/// Set paths for all decision tree proxies. +void ModuleDecisionTreeProxies::setPaths(std::map &paths) { + for (const auto &P : paths) { + const FnNameAndPhase &fnNameAndPhase = P.first; + const BitVector &path = P.second; + DecisionTreeProxy &dtp = getDecisionTreeProxy(fnNameAndPhase); + dtp.setPath(path); + } +} + +/// Get results of this compiler iteration. Result include +/// measured function fitnesses and decision priorities. +void ModuleDecisionTreeProxies::getResults( + std::vector &results) const { + results.clear(); + for (const auto &P : DecisionTreeProxies) { + const FnNameAndPhase &fnNameAndPhase = P.first; + const DecisionTreeProxy &dtp = *P.second; + MdtResults res = dtp.getResults(); + res.FunctionNameAndPhase = fnNameAndPhase; + results.push_back(res); + } +} + +bool ModuleDecisionTreeProxies::doInitialization(Module &M) { + if (IterativeCompilationOpt) { + IterativeCompilation = true; + std::string MdtPathsString = DecisionTree::readFromFile(FicInputFile); + std::map MdtPaths; + std::string ErrorMsg; + if (!ModuleDecisionTrees::parseMdtPaths(MdtPaths, MdtPathsString, ErrorMsg)) { + report_fatal_error(Twine("ITERATIVE COMPILATION ERROR:") + ErrorMsg + "\n"); + return false; + } + setPaths(MdtPaths); + } + return true; +} + +bool ModuleDecisionTreeProxies::doFinalization(Module &M) { + if (IterativeCompilationOpt) { + std::vector Results; + getResults(Results); + std::string ResultsStr = ModuleDecisionTrees::generateMdtResultsString(Results); + if (ICPhase != FnNameAndPhase::CodeGenPhase) + DecisionTree::writeToFile(FicResultsFile, ResultsStr); + else + DecisionTree::writeToFile(FicResultsFile2, ResultsStr); + } + return true; +} + +/// This function should be called from pass that wants to take advantage +/// of iterative compilation. If this function returns false, a pass +/// should do exactly as before, without iterative compilation, +/// otherwise take an alternative path. Parameter priority is the +/// estimated priority of this decision. We should pass higher priority +/// for the decisions which can more influence the code quality and for +/// which the existing heuristics are not sure that the right decision +/// is taken. +bool ModuleDecisionTreeProxies::getDecision(int priority) { + if (!CurrFnDecisionTreeProxy) + return false; + bool r2 = CurrFnDecisionTreeProxy->getDecision(priority); + return r2; +} Index: lib/Analysis/ICSetCurrentFunc.cpp =================================================================== --- /dev/null +++ lib/Analysis/ICSetCurrentFunc.cpp @@ -0,0 +1,44 @@ +//===-- ICSetCurrentFunc.cpp - Iterative Comp Set Current Func DT ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Implements the pass which sets the decision tree proxy of the +// current function. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/ICSetCurrentFunc.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/IR/Function.h" + +using namespace llvm; + +bool ICSetCurrentFunc::runOnFunction(Function &F) { + MD = &getAnalysis(); + //MD->setFunctionName(F.getName()); + + // TODO: Use module phase decision tree until iterative compilation + // framework can handle multiple decision trees. + + //MD->setCurrentFunctionAndPhase(F.getName(), + // FnNameAndPhase::FunctionPhase); + MD->setModuleCompilationPhase(); + return false; +} + +char ICSetCurrentFunc::ID = 0; + +INITIALIZE_PASS_BEGIN(ICSetCurrentFunc, "icsetcurrentfunc", + "Set Current Function DT Proxy", false, true) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) +INITIALIZE_PASS_END(ICSetCurrentFunc, "icsetcurrentfunc", + "Set Current Function DT Proxy", false, true) + +FunctionPass *llvm::createICSetCurrentFuncPass() { + return new ICSetCurrentFunc(); +} Index: lib/Target/Mips/CMakeLists.txt =================================================================== --- lib/Target/Mips/CMakeLists.txt +++ lib/Target/Mips/CMakeLists.txt @@ -26,6 +26,7 @@ MipsConstantIslandPass.cpp MipsDelaySlotFiller.cpp MipsFastISel.cpp + MipsFunctionFitness.cpp MipsInstrInfo.cpp MipsISelDAGToDAG.cpp MipsISelLowering.cpp Index: lib/Target/Mips/Mips.h =================================================================== --- lib/Target/Mips/Mips.h +++ lib/Target/Mips/Mips.h @@ -27,6 +27,7 @@ FunctionPass *createMipsDelaySlotFillerPass(MipsTargetMachine &TM); FunctionPass *createMipsLongBranchPass(MipsTargetMachine &TM); FunctionPass *createMipsConstantIslandPass(MipsTargetMachine &tm); + FunctionPass *createMipsFunctionFitnessPass(); } // end namespace llvm; #endif Index: lib/Target/Mips/MipsFunctionFitness.cpp =================================================================== --- /dev/null +++ lib/Target/Mips/MipsFunctionFitness.cpp @@ -0,0 +1,84 @@ +//===-- MipsFunctionFitness.cpp - Function Fitness Implementation ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file estimates the fitness of a function which is used in +// iterative compilation. +// +//===----------------------------------------------------------------------===// + +#include "Mips.h" +#include "MipsTargetMachine.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/DecisionTree.h" +#include "llvm/IR/Function.h" + +using namespace llvm; + +struct FunctionFitness : public MachineFunctionPass { + + static char ID; + FunctionFitness() : MachineFunctionPass(ID), TotalCount(0) { } + + virtual const char *getPassName() const { + return "Mips Function Fitness"; + } + + bool runOnMachineBasicBlock(MachineBasicBlock &MBB); + bool runOnMachineFunction(MachineFunction &F) { + std::string FnName = F.getFunction()->getName().str(); + ModuleDecisionTreeProxies &Proxies = + getAnalysis(); + Proxies.setCurrentFunctionAndPhase(FnName, FnNameAndPhase::CodeGenPhase); + DecisionTreeProxy *Proxy = Proxies.getCurrFnDecisionTreeProxy(); + if (Proxy) { + TotalCount = 0; + for (MachineFunction::iterator FI = F.begin(), FE = F.end(); + FI != FE; ++FI) + runOnMachineBasicBlock(*FI); + Proxy->setFunctionFitness(TotalCount); + } + return false; + } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); + MachineFunctionPass::getAnalysisUsage(AU); + } + + unsigned TotalCount; +}; + +char FunctionFitness::ID = 0; + +bool FunctionFitness:: +runOnMachineBasicBlock(MachineBasicBlock &MBB) { + unsigned Count = 0; + + for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) + Count++; + + TotalCount += Count; + + return false; +} + +/// createMipsFunctionFitnessPass - Returns a pass that counts generated +/// instructions +/// in +FunctionPass *llvm::createMipsFunctionFitnessPass() { + return new FunctionFitness(); +} Index: lib/Target/Mips/MipsTargetMachine.cpp =================================================================== --- lib/Target/Mips/MipsTargetMachine.cpp +++ lib/Target/Mips/MipsTargetMachine.cpp @@ -185,6 +185,7 @@ bool MipsPassConfig::addPreEmitPass() { MipsTargetMachine &TM = getMipsTargetMachine(); addPass(createMipsDelaySlotFillerPass(TM)); + addPass(createMipsFunctionFitnessPass()); addPass(createMipsLongBranchPass(TM)); addPass(createMipsConstantIslandPass(TM)); return true; Index: lib/Transforms/IPO/InlineAlways.cpp =================================================================== --- lib/Transforms/IPO/InlineAlways.cpp +++ lib/Transforms/IPO/InlineAlways.cpp @@ -71,6 +71,7 @@ INITIALIZE_PASS_DEPENDENCY(AssumptionTracker) INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) INITIALIZE_PASS_DEPENDENCY(InlineCostAnalysis) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) INITIALIZE_PASS_END(AlwaysInliner, "always-inline", "Inliner for always_inline functions", false, false) Index: lib/Transforms/IPO/InlineSimple.cpp =================================================================== --- lib/Transforms/IPO/InlineSimple.cpp +++ lib/Transforms/IPO/InlineSimple.cpp @@ -79,6 +79,7 @@ INITIALIZE_PASS_DEPENDENCY(AssumptionTracker) INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) INITIALIZE_PASS_DEPENDENCY(InlineCostAnalysis) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) INITIALIZE_PASS_END(SimpleInliner, "inline", "Function Integration/Inlining", false, false) Index: lib/Transforms/IPO/Inliner.cpp =================================================================== --- lib/Transforms/IPO/Inliner.cpp +++ lib/Transforms/IPO/Inliner.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/AssumptionTracker.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/InlineCost.h" +#include "llvm/Analysis/DecisionTree.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DiagnosticInfo.h" @@ -78,6 +79,7 @@ void Inliner::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.addRequired(); + AU.addRequired(); CallGraphSCCPass::getAnalysisUsage(AU); } @@ -334,7 +336,17 @@ } Function *Caller = CS.getCaller(); - if (!IC) { + bool doInlinging = (bool)IC; + + int t = MaxDtPriority - abs(IC.getCostDelta()); + bool decision = false; + if (t >= 0) { + decision = MDTP->getDecision(t); + } + if (decision) + doInlinging = !doInlinging; + + if (!doInlinging) { DEBUG(dbgs() << " NOT Inlining: cost=" << IC.getCost() << ", thres=" << (IC.getCostDelta() + IC.getCost()) << ", Call: " << *CS.getInstruction() << "\n"); @@ -444,6 +456,8 @@ bool Inliner::runOnSCC(CallGraphSCC &SCC) { CallGraph &CG = getAnalysis().getCallGraph(); AssumptionTracker *AT = &getAnalysis(); + MDTP = &getAnalysis(); + MDTP->setModuleCompilationPhase(); DataLayoutPass *DLP = getAnalysisIfAvailable(); const DataLayout *DL = DLP ? &DLP->getDataLayout() : nullptr; const TargetLibraryInfo *TLI = getAnalysisIfAvailable(); Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -219,6 +219,7 @@ MPM.add(createTailCallEliminationPass()); // Eliminate tail calls MPM.add(createCFGSimplificationPass()); // Merge & remove BBs MPM.add(createReassociatePass()); // Reassociate expressions + MPM.add(createICSetCurrentFuncPass()); // Set decision tree proxy MPM.add(createLoopRotatePass()); // Rotate Loop MPM.add(createLICMPass()); // Hoist loop invariants MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3)); Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -35,6 +35,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/DecisionTree.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolution.h" @@ -86,6 +87,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequiredID(LoopSimplifyID); AU.addPreservedID(LoopSimplifyID); @@ -111,6 +113,7 @@ const DataLayout *DL; // DataLayout for constant folding. TargetLibraryInfo *TLI; // TargetLibraryInfo for constant folding. + ModuleDecisionTreeProxies *MDTP; // State that is updated as we process loops. bool Changed; // Set to true when we change anything. @@ -206,6 +209,7 @@ char LICM::ID = 0; INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ModuleDecisionTreeProxies) INITIALIZE_PASS_DEPENDENCY(LoopInfo) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_DEPENDENCY(LCSSA) @@ -230,6 +234,7 @@ LI = &getAnalysis(); AA = &getAnalysis(); DT = &getAnalysis().getDomTree(); + MDTP = &getAnalysis(); DataLayoutPass *DLP = getAnalysisIfAvailable(); DL = DLP ? &DLP->getDataLayout() : nullptr; @@ -406,6 +411,8 @@ // constants, it is technically hoistable, but it would be better to just // fold it. if (Constant *C = ConstantFoldInstruction(&I, DL, TLI)) { + if (MDTP->getDecision(MaxDtPriority / 2)) + continue; DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n'); CurAST->copyValue(&I, C); CurAST->deleteValue(&I); @@ -420,7 +427,8 @@ // if (CurLoop->hasLoopInvariantOperands(&I) && canSinkOrHoistInst(I) && isSafeToExecuteUnconditionally(I)) - hoist(I); + if (!MDTP->getDecision(MaxDtPriority / 2)) + hoist(I); } const std::vector &Children = N->getChildren();