From d08e3d753e401307b9a7c0316559cc8c1b39fd65 Mon Sep 17 00:00:00 2001
From: Christian Konig <christian.koenig@amd.com>
Date: Sat, 16 Feb 2013 11:27:29 +0000
Subject: [PATCH] R600/structurizer: add class to find the Nearest Common
 Dominator
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

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>
llvm-svn: 175345
---
 llvm/lib/Target/R600/AMDGPUStructurizeCFG.cpp | 66 +++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)

diff --git a/llvm/lib/Target/R600/AMDGPUStructurizeCFG.cpp b/llvm/lib/Target/R600/AMDGPUStructurizeCFG.cpp
index c4c9762..86cb04a 100644
--- a/llvm/lib/Target/R600/AMDGPUStructurizeCFG.cpp
+++ b/llvm/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.
 ///
-- 
2.7.4