Maintain ETNode as part of DomTreeNode.

This adds redundancy for now.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37492 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index c6a8a5f5b37eaf1789d89dc931d2b4a1a740d78c..87ea6c1651dc7e8807ae9653095888e8e4de0e7e 100644 (file)
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -63,6 +63,7 @@ public:
 class DomTreeNode {
   BasicBlock *TheBB;
   DomTreeNode *IDom;
+  ETNode *ETN;
   std::vector<DomTreeNode*> Children;
 public:
   typedef std::vector<DomTreeNode*>::iterator iterator;
@@ -75,28 +76,14 @@ public:
   
   inline BasicBlock *getBlock() const { return TheBB; }
   inline DomTreeNode *getIDom() const { return IDom; }
+  inline ETNode *getETNode() const { return ETN; }
   inline const std::vector<DomTreeNode*> &getChildren() const { return Children; }
   
-  /// properlyDominates - Returns true iff this dominates N and this != N.
-  /// Note that this is not a constant time operation!
-  ///
-  bool properlyDominates(const DomTreeNode *N) const {
-    const DomTreeNode *IDom;
-    if (this == 0 || N == 0) return false;
-    while ((IDom = N->getIDom()) != 0 && IDom != this)
-      N = IDom;   // Walk up the tree
-    return IDom != 0;
-  }
-  
-  /// dominates - Returns true iff this dominates N.  Note that this is not a
-  /// constant time operation!
-  ///
-  inline bool dominates(const DomTreeNode *N) const {
-    if (N == this) return true;  // A node trivially dominates itself.
-    return properlyDominates(N);
+  inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom, ETNode *E) 
+    : TheBB(BB), IDom(iDom), ETN(E) {
+    if (IDom)
+      ETN->setFather(IDom->getETNode());
   }
-  
-  inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom) : TheBB(BB), IDom(iDom) {}
   inline DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); return C; }
   void setIDom(DomTreeNode *NewIDom);
 };
@@ -107,12 +94,16 @@ public:
 class DominatorTreeBase : public DominatorBase {
 
 protected:
-  std::map<BasicBlock*, DomTreeNode*> DomTreeNodes;
   void reset();
   typedef std::map<BasicBlock*, DomTreeNode*> DomTreeNodeMapType;
-
+  DomTreeNodeMapType DomTreeNodes;
   DomTreeNode *RootNode;
 
+  typedef std::map<BasicBlock*, ETNode*> ETMapType;
+  ETMapType ETNodes;
+
+  bool DFSInfoValid;
+  unsigned int SlowQueries;
   // Information record used during immediate dominators computation.
   struct InfoRec {
     unsigned Semi;
@@ -134,7 +125,7 @@ protected:
 
   public:
   DominatorTreeBase(intptr_t ID, bool isPostDom) 
-    : DominatorBase(ID, isPostDom) {}
+    : DominatorBase(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {}
   ~DominatorTreeBase() { reset(); }
 
   virtual void releaseMemory() { reset(); }
@@ -161,6 +152,47 @@ protected:
   DomTreeNode *getRootNode() { return RootNode; }
   const DomTreeNode *getRootNode() const { return RootNode; }
 
+  /// properlyDominates - Returns true iff this dominates N and this != N.
+  /// Note that this is not a constant time operation!
+  ///
+  bool properlyDominates(const DomTreeNode *A, DomTreeNode *B) const {
+    if (A == 0 || B == 0) return false;
+    return dominatedBySlowTreeWalk(A, B);
+  }
+
+  bool dominatedBySlowTreeWalk(const DomTreeNode *A, 
+                               const DomTreeNode *B) const {
+    const DomTreeNode *IDom;
+    if (A == 0 || B == 0) return false;
+    while ((IDom = B->getIDom()) != 0 && IDom != A)
+      B = IDom;   // Walk up the tree
+    return IDom != 0;
+  }
+
+  void updateDFSNumbers();  
+  /// dominates - Returns true iff this dominates N.  Note that this is not a
+  /// constant time operation!
+  ///
+  inline bool dominates(const DomTreeNode *A, DomTreeNode *B) {
+    if (B == A) return true;  // A node trivially dominates itself.
+
+    ETNode *NodeA = A->getETNode();
+    ETNode *NodeB = B->getETNode();
+    
+    if (DFSInfoValid)
+      return NodeB->DominatedBy(NodeA);
+
+    // If we end up with too many slow queries, just update the
+    // DFS numbers on the theory that we are going to keep querying.
+    SlowQueries++;
+    if (SlowQueries > 32) {
+      updateDFSNumbers();
+      return NodeB->DominatedBy(NodeA);
+    }
+    //return NodeB->DominatedBySlow(NodeA);
+    return dominatedBySlowTreeWalk(A, B);
+  }
+  
   //===--------------------------------------------------------------------===//
   // API to update (Post)DominatorTree information based on modifications to
   // the CFG...
@@ -172,7 +204,11 @@ protected:
     assert(getNode(BB) == 0 && "Block already in dominator tree!");
     DomTreeNode *IDomNode = getNode(DomBB);
     assert(IDomNode && "Not immediate dominator specified for block!");
-    return DomTreeNodes[BB] = IDomNode->addChild(new DomTreeNode(BB, IDomNode));
+    DFSInfoValid = false;
+    ETNode *E = new ETNode(BB);
+    ETNodes[BB] = E;
+    return DomTreeNodes[BB] = 
+      IDomNode->addChild(new DomTreeNode(BB, IDomNode, E));
   }
 
   /// changeImmediateDominator - This method is used to update the dominator
@@ -180,6 +216,7 @@ protected:
   ///
   void changeImmediateDominator(DomTreeNode *N, DomTreeNode *NewIDom) {
     assert(N && NewIDom && "Cannot change null node pointers!");
+    DFSInfoValid = false;
     N->setIDom(NewIDom);
   }
 
@@ -187,7 +224,6 @@ protected:
     changeImmediateDominator(getNode(BB), getNode(NewBB));
   }
 
-
   /// removeNode - Removes a node from the dominator tree.  Block must not
   /// dominate any other blocks.  Invalidates any node pointing to removed
   /// block.

diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index fc7526ad8f5ea6dfc2f215fb39e91f626b40a4a6..c4d42e9f3c38650bad755c52a55c9b55c1aaf0ab 100644 (file)
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -165,7 +165,9 @@ void PostDominatorTree::calculate(Function &F) {
   // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0)
   // which postdominates all real exits if there are multiple exit blocks.
   BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0;
-  DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0);
+  ETNode *ERoot = new ETNode(Root);
+  ETNodes[Root] = ERoot;
+  DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0, ERoot);
   
   // Loop over all of the reachable blocks in the function...
   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
@@ -177,7 +179,11 @@ void PostDominatorTree::calculate(Function &F) {
         
         // Add a new tree node for this BasicBlock, and link it as a child of
         // IDomNode
-        BBNode = IPDomNode->addChild(new DomTreeNode(I, IPDomNode));
+        ETNode *ET = new ETNode(I);
+        ETNodes[I] = ET;
+        DomTreeNode *C = new DomTreeNode(I, IPDomNode, ET);
+        DomTreeNodes[I] = C;
+        BBNode = IPDomNode->addChild(C);
       }
     }
 
@@ -185,6 +191,16 @@ void PostDominatorTree::calculate(Function &F) {
   IDoms.clear();
   Info.clear();
   std::vector<BasicBlock*>().swap(Vertex);
+
+  int dfsnum = 0;
+  // Iterate over all nodes in depth first order...
+  for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+    for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
+           E = idf_end(Roots[i]); I != E; ++I) {
+      if (!getNodeForBlock(*I)->getETNode()->hasFather())
+        getNodeForBlock(*I)->getETNode()->assignDFSNumber(dfsnum);
+    }
+  DFSInfoValid = true;
 }
 
 
@@ -199,7 +215,11 @@ DomTreeNode *PostDominatorTree::getNodeForBlock(BasicBlock *BB) {
   
   // Add a new tree node for this BasicBlock, and link it as a child of
   // IDomNode
-  return BBNode = IPDomNode->addChild(new DomTreeNode(BB, IPDomNode));
+  ETNode *ET = new ETNode(BB);
+  ETNodes[BB] = ET;
+  DomTreeNode *C = new DomTreeNode(BB, IPDomNode, ET);
+  DomTreeNodes[BB] = C;
+  return BBNode = IPDomNode->addChild(C);
 }
 
 //===----------------------------------------------------------------------===//
@@ -303,7 +323,7 @@ PostDominanceFrontier::calculate(const PostDominatorTree &DT,
 
     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
     for (; CDFI != CDFE; ++CDFI) {
-      if (!Node->properlyDominates(DT[*CDFI]))
+      if (!DT.properlyDominates(Node, DT[*CDFI]))
         S.insert(*CDFI);
     }
   }

diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index 707cdf0edcb2596caf34d627574ea2f77429c1e6..6ceea34270f529214fc209767a38f128a113efae 100644 (file)
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -217,7 +217,7 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P,
         DestBBNode = DT->getNode(DestBB);
         while (!OtherPreds.empty() && NewBBDominatesDestBB) {
           if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back()))
-            NewBBDominatesDestBB = DestBBNode->dominates(OPNode);
+            NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode);
           OtherPreds.pop_back();
         }
         OtherPreds.clear();

diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp
index c43370be9b9c4e7f87d2ef35e801ae1464ae76c7..ed166644d7f14900f110a92b6a0cc5321cf32fc7 100644 (file)
--- a/lib/Transforms/Utils/LCSSA.cpp
+++ b/lib/Transforms/Utils/LCSSA.cpp
@@ -157,7 +157,7 @@ void LCSSA::ProcessInstruction(Instruction *Instr,
     BasicBlock *BB = *BBI;
     DomTreeNode *ExitBBNode = DT->getNode(BB);
     Value *&Phi = Phis[ExitBBNode];
-    if (!Phi && InstrNode->dominates(ExitBBNode)) {
+    if (!Phi && DT->dominates(InstrNode, ExitBBNode)) {
       PHINode *PN = new PHINode(Instr->getType(), Instr->getName()+".lcssa",
                                 BB->begin());
       PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));

diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index c75143e5b6affc8570f0876dc278108c1a99cb3b..9bfbbec9b9b22a40d56e7a87784c2451cb1ea608 100644 (file)
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -233,8 +233,11 @@ void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
 
 void DominatorTree::calculate(Function& F) {
   BasicBlock* Root = Roots[0];
-  
-  DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); // Add a node for the root...
+
+  // Add a node for the root...
+  ETNode *ERoot = new ETNode(Root);
+  ETNodes[Root] = ERoot;
+  DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0, ERoot);
 
   Vertex.push_back(0);
 
@@ -289,7 +292,9 @@ void DominatorTree::calculate(Function& F) {
 
         // Add a new tree node for this BasicBlock, and link it as a child of
         // IDomNode
-        DomTreeNode *C = new DomTreeNode(I, IDomNode);
+        ETNode *ET = new ETNode(I);
+        ETNodes[I] = ET;
+        DomTreeNode *C = new DomTreeNode(I, IDomNode, ET);
         DomTreeNodes[I] = C;
         BBNode = IDomNode->addChild(C);
       }
@@ -299,8 +304,27 @@ void DominatorTree::calculate(Function& F) {
   Info.clear();
   IDoms.clear();
   std::vector<BasicBlock*>().swap(Vertex);
+
+  updateDFSNumbers();
+}
+
+void DominatorTreeBase::updateDFSNumbers()
+{
+  int dfsnum = 0;
+  // Iterate over all nodes in depth first order.
+  for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+    for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
+           E = df_end(Roots[i]); I != E; ++I) {
+      BasicBlock *BB = *I;
+      ETNode *ETN = getNode(BB)->getETNode();
+      if (ETN && !ETN->hasFather())
+        ETN->assignDFSNumber(dfsnum);    
+  }
+  SlowQueries = 0;
+  DFSInfoValid = true;
 }
 
+
 // DominatorTreeBase::reset - Free all of the tree node memory.
 //
 void DominatorTreeBase::reset() {
@@ -326,6 +350,13 @@ void DomTreeNode::setIDom(DomTreeNode *NewIDom) {
     // Switch to new dominator
     IDom = NewIDom;
     IDom->Children.push_back(this);
+
+    if (!ETN->hasFather())
+      ETN->setFather(IDom->getETNode());
+    else if (ETN->getFather()->getData<BasicBlock>() != IDom->getBlock()) {
+        ETN->Split();
+        ETN->setFather(IDom->getETNode());
+    }
   }
 }
 
@@ -340,7 +371,9 @@ DomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) {
 
   // Add a new tree node for this BasicBlock, and link it as a child of
   // IDomNode
-  DomTreeNode *C = new DomTreeNode(BB, IDomNode);
+  ETNode *ET = new ETNode(BB);
+  ETNodes[BB] = ET;
+  DomTreeNode *C = new DomTreeNode(BB, IDomNode, ET);
   DomTreeNodes[BB] = C;
   return BBNode = IDomNode->addChild(C);
 }
@@ -463,7 +496,7 @@ DominanceFrontier::calculate(const DominatorTree &DT,
       DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
       DomSetType &parentSet = Frontiers[parentBB];
       for (; CDFI != CDFE; ++CDFI) {
-        if (!parentNode->properlyDominates(DT[*CDFI]))
+        if (!DT.properlyDominates(parentNode, DT[*CDFI]))
           parentSet.insert(*CDFI);
       }
       workList.pop_back();