Index: include/llvm/Transforms/Utils/PromoteMemToReg.h =================================================================== --- include/llvm/Transforms/Utils/PromoteMemToReg.h +++ include/llvm/Transforms/Utils/PromoteMemToReg.h @@ -16,9 +16,14 @@ #define LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H #include "llvm/ADT/ArrayRef.h" - +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" namespace llvm { +class BasicBlock; +template class DomTreeNodeBase; +typedef DomTreeNodeBase DomTreeNode; class AllocaInst; class DominatorTree; class AliasSetTracker; @@ -45,6 +50,22 @@ AliasSetTracker *AST = nullptr, AssumptionCache *AC = nullptr); + +/// \brief Determine where a set of PHI nodes should be placed, given a set of +/// defining blocks and a set of live-in blocks. +/// +/// \p BBNumbers is expected to be a mapping from a unique number to a basic +/// block, and is used to order the resulting PHIBlocks. +/// +/// \p DomLevels is expected to be a mapping from Dominator tree node to depth +/// in the dominator tree. +void determinePHINodes(DominatorTree &DT, + const SmallPtrSetImpl &DefBlocks, + const SmallPtrSetImpl &LiveInBlocks, + const DenseMap &BBNumbers, + const DenseMap &DomLevels, + SmallVectorImpl> &PHIBlocks); + } // End llvm namespace #endif Index: lib/Transforms/Utils/PromoteMemoryToRegister.cpp =================================================================== --- lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -47,6 +47,7 @@ #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/PromoteMemToReg.h" #include #include using namespace llvm; @@ -304,8 +305,6 @@ return NP - 1; } - void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, - AllocaInfo &Info); void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, const SmallPtrSetImpl &DefBlocks, SmallPtrSetImpl &LiveInBlocks); @@ -581,21 +580,10 @@ // If we haven't computed dominator tree levels, do so now. if (DomLevels.empty()) { - SmallVector Worklist; - - DomTreeNode *Root = DT.getRootNode(); - DomLevels[Root] = 0; - Worklist.push_back(Root); - - while (!Worklist.empty()) { - DomTreeNode *Node = Worklist.pop_back_val(); - unsigned ChildLevel = DomLevels[Node] + 1; - for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); - CI != CE; ++CI) { - DomLevels[*CI] = ChildLevel; - Worklist.push_back(*CI); - } - } + for (auto DFI = df_begin(DT.getRootNode()), + DFE = df_end(DT.getRootNode()); + DFI != DFE; ++DFI) + DomLevels[*DFI] = DFI.getPathLength() - 1; } // If we haven't computed a numbering for the BB's in the function, do so @@ -622,7 +610,27 @@ // the standard SSA construction algorithm. Determine which blocks need PHI // nodes and see if we can optimize out some work by avoiding insertion of // dead phi nodes. - DetermineInsertionPoint(AI, AllocaNum, Info); + + SmallVector, 32> PHIBlocks; + + // Unique the set of defining blocks for efficient lookup. + SmallPtrSet DefBlocks; + DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end()); + + // Determine which blocks the value is live in. These are blocks which lead + // to uses. + SmallPtrSet LiveInBlocks; + ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks); + + + llvm::determinePHINodes(DT, DefBlocks, LiveInBlocks, BBNumbers, DomLevels, + PHIBlocks); + if (PHIBlocks.size() > 1) + std::sort(PHIBlocks.begin(), PHIBlocks.end()); + + unsigned CurrentVersion = 0; + for (unsigned i = 0, e = PHIBlocks.size(); i != e; ++i) + QueuePhiNode(PHIBlocks[i].second, AllocaNum, CurrentVersion); } if (Allocas.empty()) @@ -844,97 +852,6 @@ } } -/// At this point, we're committed to promoting the alloca using IDF's, and the -/// standard SSA construction algorithm. Determine which blocks need phi nodes -/// and see if we can optimize out some work by avoiding insertion of dead phi -/// nodes. -void PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, - AllocaInfo &Info) { - // Unique the set of defining blocks for efficient lookup. - SmallPtrSet DefBlocks; - DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end()); - - // Determine which blocks the value is live in. These are blocks which lead - // to uses. - SmallPtrSet LiveInBlocks; - ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks); - - // Use a priority queue keyed on dominator tree level so that inserted nodes - // are handled from the bottom of the dominator tree upwards. - typedef std::pair DomTreeNodePair; - typedef std::priority_queue, - less_second> IDFPriorityQueue; - IDFPriorityQueue PQ; - - for (BasicBlock *BB : DefBlocks) { - if (DomTreeNode *Node = DT.getNode(BB)) - PQ.push(std::make_pair(Node, DomLevels[Node])); - } - - SmallVector, 32> DFBlocks; - SmallVector Worklist; - SmallPtrSet VisitedPQ; - SmallPtrSet VisitedWorklist; - - while (!PQ.empty()) { - DomTreeNodePair RootPair = PQ.top(); - PQ.pop(); - DomTreeNode *Root = RootPair.first; - unsigned RootLevel = RootPair.second; - - // Walk all dominator tree children of Root, inspecting their CFG edges with - // targets elsewhere on the dominator tree. Only targets whose level is at - // most Root's level are added to the iterated dominance frontier of the - // definition set. - - Worklist.clear(); - Worklist.push_back(Root); - VisitedWorklist.insert(Root); - - while (!Worklist.empty()) { - DomTreeNode *Node = Worklist.pop_back_val(); - BasicBlock *BB = Node->getBlock(); - - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; - ++SI) { - DomTreeNode *SuccNode = DT.getNode(*SI); - - // Quickly skip all CFG edges that are also dominator tree edges instead - // of catching them below. - if (SuccNode->getIDom() == Node) - continue; - - unsigned SuccLevel = DomLevels[SuccNode]; - if (SuccLevel > RootLevel) - continue; - - if (!VisitedPQ.insert(SuccNode).second) - continue; - - BasicBlock *SuccBB = SuccNode->getBlock(); - if (!LiveInBlocks.count(SuccBB)) - continue; - - DFBlocks.push_back(std::make_pair(BBNumbers[SuccBB], SuccBB)); - if (!DefBlocks.count(SuccBB)) - PQ.push(std::make_pair(SuccNode, SuccLevel)); - } - - for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); CI != CE; - ++CI) { - if (VisitedWorklist.insert(*CI).second) - Worklist.push_back(*CI); - } - } - } - - if (DFBlocks.size() > 1) - std::sort(DFBlocks.begin(), DFBlocks.end()); - - unsigned CurrentVersion = 0; - for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) - QueuePhiNode(DFBlocks[i].second, AllocaNum, CurrentVersion); -} /// \brief Queue a phi-node to be added to a basic-block for a specific Alloca. /// @@ -1084,3 +1001,81 @@ PromoteMem2Reg(Allocas, DT, AST, AC).run(); } + +/// At this point, we're committed to promoting the alloca using IDF's, and the +/// standard SSA construction algorithm. Determine which blocks need phi nodes +/// and see if we can optimize out some work by avoiding insertion of dead phi +/// nodes. +void llvm::determinePHINodes(DominatorTree &DT, + const SmallPtrSetImpl &DefBlocks, + const SmallPtrSetImpl &LiveInBlocks, + const DenseMap &BBNumbers, + const DenseMap &DomLevels, + SmallVectorImpl> &PHIBlocks) { + + // Use a priority queue keyed on dominator tree level so that inserted nodes + // are handled from the bottom of the dominator tree upwards. + typedef std::pair DomTreeNodePair; + typedef std::priority_queue, + less_second> IDFPriorityQueue; + IDFPriorityQueue PQ; + + for (BasicBlock *BB : DefBlocks) { + if (DomTreeNode *Node = DT.getNode(BB)) + PQ.push(std::make_pair(Node, DomLevels.lookup(Node))); + } + + SmallVector Worklist; + SmallPtrSet VisitedPQ; + SmallPtrSet VisitedWorklist; + + while (!PQ.empty()) { + DomTreeNodePair RootPair = PQ.top(); + PQ.pop(); + DomTreeNode *Root = RootPair.first; + unsigned RootLevel = RootPair.second; + + // Walk all dominator tree children of Root, inspecting their CFG edges with + // targets elsewhere on the dominator tree. Only targets whose level is at + // most Root's level are added to the iterated dominance frontier of the + // definition set. + + Worklist.clear(); + Worklist.push_back(Root); + VisitedWorklist.insert(Root); + + while (!Worklist.empty()) { + DomTreeNode *Node = Worklist.pop_back_val(); + BasicBlock *BB = Node->getBlock(); + + for (auto Succ : successors(BB)) { + DomTreeNode *SuccNode = DT.getNode(Succ); + + // Quickly skip all CFG edges that are also dominator tree edges instead + // of catching them below. + if (SuccNode->getIDom() == Node) + continue; + + unsigned SuccLevel = DomLevels.lookup(SuccNode); + if (SuccLevel > RootLevel) + continue; + + if (!VisitedPQ.insert(SuccNode).second) + continue; + + BasicBlock *SuccBB = SuccNode->getBlock(); + if (!LiveInBlocks.count(SuccBB)) + continue; + + PHIBlocks.push_back(std::make_pair(BBNumbers.lookup(SuccBB), SuccBB)); + if (!DefBlocks.count(SuccBB)) + PQ.push(std::make_pair(SuccNode, SuccLevel)); + } + + for (auto DomChild : *Node){ + if (VisitedWorklist.insert(DomChild).second) + Worklist.push_back(DomChild); + } + } + } +}