Move NearestCommonDominator class into common code.

[arsenm]

Summary

Use the dominator base class so it could also be used for machine dominators.
This is a helper class for more efficiently finding the common dominator of N nodes, rather than only two as findNearestCommonDominator does.

This is the result of the discussion had previously when I moved StructurizeCFG out of R600:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130603/176639.html

[• rafael]

The typedef of DTN2UnsignedMap in StructurizeCFG.cpp is now dead, no?

[arsenm]

Remove now unused typedef

[• rafael]

LGTM assuming a use with machine basic blocks is coming soon.

Just one somewhat related request. Try to do a build with -Wweak-vtables? I remember seeing some warning on this area last time I used it.

[Eugene.Zelenko]

Looks like patch was not committed.

include/llvm/IR/Dominators.h

 
 EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
 EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
+EXTERN_TEMPLATE_INSTANTIATION(class NearestCommonDominatorBase<BasicBlock>);
 
 typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
 

   void verifyDomTree() const;
 };
 
+/// \brief Concrete subclass of NearestCommonDominatorBase that is used to
+/// compute a the nearest common dominator for N nodes in a normal dominator
+/// tree.
+class NearestCommonDominator : public NearestCommonDominatorBase<BasicBlock> {
+public:
+  typedef NearestCommonDominatorBase<BasicBlock> Base;
+
+  NearestCommonDominator(DominatorTreeBase<BasicBlock> *DT_) :
+    NearestCommonDominatorBase<BasicBlock>(DT_) {}
+};
+
 //===-------------------------------------
 // DominatorTree GraphTraits specializations so the DominatorTree can be
 // iterable by generic graph iterators.

include/llvm/Support/GenericDomTree.h

                    getNode(const_cast<NodeT *>(B)));
 }
 
+/// @brief Find the nearest common dominator for multiple BasicBlocks
+///
+template<class NodeT>
+class NearestCommonDominatorBase {
+  typedef DenseMap<DomTreeNodeBase<NodeT> *, unsigned> DTN2UnsignedMap;
+
+  DominatorTreeBase<NodeT> *DT;
+
+  DTN2UnsignedMap IndexMap;
+
+  NodeT *Result;
+  unsigned ResultIndex;
+  bool ExplicitMentioned;
+
+public:
+  /// \brief Start a new query
+  NearestCommonDominatorBase(DominatorTreeBase<NodeT> *DomTree) {
+    DT = DomTree;
+    Result = 0;
+  }
+
+  /// \brief Add BB to the resulting dominator
+  void addNode(NodeT *BB, bool Remember = true) {
+    DomTreeNodeBase<NodeT> *Node = DT->getNode(BB);
+
+    if (!Result) {
+      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
+  NodeT *getResult() {
+    return Result;
+  }
+};
+
 }
 
 #endif

lib/IR/Dominators.cpp

 
 TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>);
 TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>);
+TEMPLATE_INSTANTIATION(class llvm::NearestCommonDominatorBase<BasicBlock>);
 
 // dominates - Return true if Def dominates a use in User. This performs
 // the special checks necessary if Def and User are in the same basic block.

lib/Transforms/Scalar/StructurizeCFG.cpp

 typedef MapVector<PHINode *, BBValueVector> PhiMap;
 typedef MapVector<BasicBlock *, BBVector> BB2BBVecMap;
 
-typedef DenseMap<DomTreeNode *, unsigned> DTN2UnsignedMap;
 typedef DenseMap<BasicBlock *, PhiMap> BBPhiMap;
 typedef DenseMap<BasicBlock *, Value *> BBPredicates;
 typedef DenseMap<BasicBlock *, BBPredicates> PredMap;

 
 static const char *const FlowBlockName = "Flow";
 
-/// @brief Find the nearest common dominator for multiple BasicBlocks
-///
-/// Helper class for StructurizeCFG
-/// 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.
 ///

     BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue];
 
     NearestCommonDominator Dominator(DT);
-    Dominator.addBlock(Parent, false);
+    Dominator.addNode(Parent, false);
 
     Value *ParentValue = 0;
     for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end();

         break;
       }
       PhiInserter.AddAvailableValue(PI->first, PI->second);
-      Dominator.addBlock(PI->first);
+      Dominator.addNode(PI->first);
     }
 
     if (ParentValue) {

       Updater.AddAvailableValue(To, Undef);
 
       NearestCommonDominator Dominator(DT);
-      Dominator.addBlock(To, false);
+      Dominator.addNode(To, false);
       for (BBValueVector::iterator VI = PI->second.begin(),
            VE = PI->second.end(); VI != VE; ++VI) {
 
         Updater.AddAvailableValue(VI->first, VI->second);
-        Dominator.addBlock(VI->first);
+        Dominator.addNode(VI->first);
       }
 
       if (!Dominator.wasResultExplicitMentioned())