From 2372a193ba904fdc85de3cc559e0bc162f14f144 Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Tue, 21 Apr 2015 19:13:02 +0000 Subject: Move IDF Calculation to a separate file, expose an interface to it. Summary: MemorySSA uses this algorithm as well, and this enables us to reuse the code in both places. There are no actual algorithm or datastructure changes in here, just code movement. Reviewers: qcolombet, chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9118 llvm-svn: 235406 --- llvm/lib/Analysis/CMakeLists.txt | 1 + llvm/lib/Analysis/IteratedDominanceFrontier.cpp | 95 ++++++++++++ .../Transforms/Utils/PromoteMemoryToRegister.cpp | 162 ++++----------------- 3 files changed, 128 insertions(+), 130 deletions(-) create mode 100644 llvm/lib/Analysis/IteratedDominanceFrontier.cpp (limited to 'llvm/lib') diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt index 1335a6db846..32fe9b9495d 100644 --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -28,6 +28,7 @@ add_llvm_library(LLVMAnalysis InstructionSimplify.cpp Interval.cpp IntervalPartition.cpp + IteratedDominanceFrontier.cpp LazyCallGraph.cpp LazyValueInfo.cpp LibCallAliasAnalysis.cpp diff --git a/llvm/lib/Analysis/IteratedDominanceFrontier.cpp b/llvm/lib/Analysis/IteratedDominanceFrontier.cpp new file mode 100644 index 00000000000..9f1edd21820 --- /dev/null +++ b/llvm/lib/Analysis/IteratedDominanceFrontier.cpp @@ -0,0 +1,95 @@ +//===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// \brief Compute iterated dominance frontiers using a linear time algorithm. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/IteratedDominanceFrontier.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Dominators.h" +#include + +using namespace llvm; + +void IDFCalculator::calculate(SmallVectorImpl &PHIBlocks) { + // If we haven't computed dominator tree levels, do so now. + if (DomLevels.empty()) { + for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode()); + DFI != DFE; ++DFI) { + DomLevels[*DFI] = DFI.getPathLength() - 1; + } + } + + // 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 (useLiveIn && !LiveInBlocks->count(SuccBB)) + continue; + + PHIBlocks.emplace_back(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); + } + } + } +} diff --git a/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index 54e1733c3f6..623dbc9f42c 100644 --- a/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -13,16 +13,6 @@ // traversing the function in depth-first order to rewrite loads and stores as // appropriate. // -// The algorithm used here is based on: -// -// Sreedhar and Gao. A linear time algorithm for placing phi-nodes. -// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of -// Programming Languages -// POPL '95. ACM, New York, NY, 62-73. -// -// It has been modified to not explicitly use the DJ graph data structure and to -// directly compute pruned SSA using per-variable liveness information. -// //===----------------------------------------------------------------------===// #include "llvm/Transforms/Utils/PromoteMemToReg.h" @@ -34,6 +24,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/IteratedDominanceFrontier.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" @@ -48,7 +39,6 @@ #include "llvm/IR/Module.h" #include "llvm/Transforms/Utils/Local.h" #include -#include using namespace llvm; #define DEBUG_TYPE "mem2reg" @@ -275,9 +265,6 @@ struct PromoteMem2Reg { /// behavior. DenseMap BBNumbers; - /// Maps DomTreeNodes to their level in the dominator tree. - DenseMap DomLevels; - /// Lazily compute the number of predecessors a block has. DenseMap BBNumPreds; @@ -304,8 +291,6 @@ private: return NP - 1; } - void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, - AllocaInfo &Info); void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, const SmallPtrSetImpl &DefBlocks, SmallPtrSetImpl &LiveInBlocks); @@ -532,6 +517,7 @@ void PromoteMem2Reg::run() { AllocaInfo Info; LargeBlockInfo LBI; + IDFCalculator IDF(DT); for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { AllocaInst *AI = Allocas[AllocaNum]; @@ -579,31 +565,12 @@ void PromoteMem2Reg::run() { continue; } - // 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); - } - } - } - // If we haven't computed a numbering for the BB's in the function, do so // now. if (BBNumbers.empty()) { unsigned ID = 0; - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) - BBNumbers[I] = ID++; + for (auto &BB : F) + BBNumbers[&BB] = ID++; } // If we have an AST to keep updated, remember some pointer value that is @@ -622,7 +589,34 @@ void PromoteMem2Reg::run() { // 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); + + + // 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); + + // 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. + IDF.setLiveInBlocks(LiveInBlocks); + IDF.setDefiningBlocks(DefBlocks); + SmallVector PHIBlocks; + IDF.calculate(PHIBlocks); + if (PHIBlocks.size() > 1) + std::sort(PHIBlocks.begin(), PHIBlocks.end(), + [this](BasicBlock *A, BasicBlock *B) { + return BBNumbers.lookup(A) < BBNumbers.lookup(B); + }); + + unsigned CurrentVersion = 0; + for (unsigned i = 0, e = PHIBlocks.size(); i != e; ++i) + QueuePhiNode(PHIBlocks[i], AllocaNum, CurrentVersion); } if (Allocas.empty()) @@ -844,98 +838,6 @@ void PromoteMem2Reg::ComputeLiveInBlocks( } } -/// 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. /// /// Returns true if there wasn't already a phi-node for that variable -- cgit v1.2.3