diff options
author | ckoenig <ckoenig@91177308-0d34-0410-b5e6-96231b3b80d8> | 2013-02-16 11:27:29 +0000 |
---|---|---|
committer | Tom Stellard <thomas.stellard@amd.com> | 2013-02-19 14:58:22 +0000 |
commit | ba7b51db0d356d51c32aef0240603f2dc1e552da (patch) | |
tree | 277ce1f836a5b983012343a5e001f1f0b4d7878f | |
parent | 52310b0b7744201f14742b5a51c4e52175fb1cfe (diff) |
R600/structurizer: add class to find the Nearest Common Dominator
This is a candidate for the stable branch.
Signed-off-by: Christian König <christian.koenig@amd.com>
Reviewed-by: Tom Stellard <thomas.stellard@amd.com>
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175345 91177308-0d34-0410-b5e6-96231b3b80d8
(cherry picked from commit a11f07b12419d900376b6206a8cf1711ff1445d9)
-rw-r--r-- | lib/Target/R600/AMDGPUStructurizeCFG.cpp | 66 |
1 files changed, 66 insertions, 0 deletions
diff --git a/lib/Target/R600/AMDGPUStructurizeCFG.cpp b/lib/Target/R600/AMDGPUStructurizeCFG.cpp index 169d9541b70..ad628c16858 100644 --- a/lib/Target/R600/AMDGPUStructurizeCFG.cpp +++ b/lib/Target/R600/AMDGPUStructurizeCFG.cpp @@ -39,6 +39,7 @@ typedef SmallVector<BBValuePair, 2> BBValueVector; typedef SmallPtrSet<BasicBlock *, 8> BBSet; typedef DenseMap<PHINode *, BBValueVector> PhiMap; +typedef DenseMap<DomTreeNode *, unsigned> DTN2UnsignedMap; typedef DenseMap<BasicBlock *, PhiMap> BBPhiMap; typedef DenseMap<BasicBlock *, Value *> BBPredicates; typedef DenseMap<BasicBlock *, BBPredicates> PredMap; @@ -48,6 +49,71 @@ typedef DenseMap<BasicBlock *, BBVector> BB2BBVecMap; static const char *FlowBlockName = "Flow"; +/// @brief Find the nearest common dominator for multiple BasicBlocks +/// +/// Helper class for AMDGPUStructurizeCFG +/// TODO: Maybe move into common code +class NearestCommonDominator { + + DominatorTree *DT; + + DTN2UnsignedMap IndexMap; + + BasicBlock *Result; + unsigned ResultIndex; + bool ExplicitMentioned; + +public: + /// \brief Start a new query + NearestCommonDominator(DominatorTree *DomTree) { + DT = DomTree; + Result = 0; + } + + /// \brief Add BB to the resulting dominator + void addBlock(BasicBlock *BB, bool Remember = true) { + + DomTreeNode *Node = DT->getNode(BB); + + if (Result == 0) { + unsigned Numbering = 0; + for (;Node;Node = Node->getIDom()) + IndexMap[Node] = ++Numbering; + Result = BB; + ResultIndex = 1; + ExplicitMentioned = Remember; + return; + } + + for (;Node;Node = Node->getIDom()) + if (IndexMap.count(Node)) + break; + else + IndexMap[Node] = 0; + + assert(Node && "Dominator tree invalid!"); + + unsigned Numbering = IndexMap[Node]; + if (Numbering > ResultIndex) { + Result = Node->getBlock(); + ResultIndex = Numbering; + ExplicitMentioned = Remember && (Result == BB); + } else if (Numbering == ResultIndex) { + ExplicitMentioned |= Remember; + } + } + + /// \brief Is "Result" one of the BBs added with "Remember" = True? + bool wasResultExplicitMentioned() { + return ExplicitMentioned; + } + + /// \brief Get the query result + BasicBlock *getResult() { + return Result; + } +}; + /// @brief Transforms the control flow graph on one single entry/exit region /// at a time. /// |