[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h ET-Forest.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.106 - 1.107
ET-Forest.h (r1.10) removed
---
Log message:

Remove ETForest.


---
Diffs of the changes:  (+1 -168)

 Dominators.h |  169 ---
 1 files changed, 1 insertion(+), 168 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.106 
llvm/include/llvm/Analysis/Dominators.h:1.107
--- llvm/include/llvm/Analysis/Dominators.h:1.106   Thu Jun 21 12:23:45 2007
+++ llvm/include/llvm/Analysis/Dominators.h Wed Jun 27 15:53:52 2007
@@ -9,9 +9,7 @@
 //
 // This file defines the following classes:
 //  1. DominatorTree: Represent dominators as an explicit tree structure.
-//  2. ETForest: Efficient data structure for dominance comparisons and 
-// nearest-common-ancestor queries.
-//  3. DominanceFrontier: Calculate and hold the dominance frontier for a
+//  2. DominanceFrontier: Calculate and hold the dominance frontier for a
 // function.
 //
 //  These data structures are listed in increasing order of complexity.  It
@@ -23,7 +21,6 @@
 #ifndef LLVM_ANALYSIS_DOMINATORS_H
 #define LLVM_ANALYSIS_DOMINATORS_H
 
-#include llvm/Analysis/ET-Forest.h
 #include llvm/Pass.h
 #include set
 
@@ -347,170 +344,6 @@
 };
 
 
-//===-
-/// ET-Forest Class - Class used to construct forwards and backwards 
-/// ET-Forests
-///
-class ETForestBase : public DominatorBase {
-public:
-  ETForestBase(intptr_t ID, bool isPostDom) 
-: DominatorBase(ID, isPostDom), Nodes(), 
-  DFSInfoValid(false), SlowQueries(0) {}
-  
-  virtual void releaseMemory() { reset(); }
-
-  typedef std::mapBasicBlock*, ETNode* ETMapType;
-
-  // FIXME : There is no need to make this interface public. 
-  // Fix predicate simplifier.
-  void updateDFSNumbers();
-
-  /// dominates - Return true if A dominates B.
-  ///
-  inline bool dominates(BasicBlock *A, BasicBlock *B) {
-if (A == B)
-  return true;
-
-ETNode *NodeA = getNode(A);
-ETNode *NodeB = getNode(B);
-
-if (DFSInfoValid)
-  return NodeB-DominatedBy(NodeA);
-else {
-  // 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);
-}
-  }
-
-  // dominates - Return true if A dominates B. This performs the
-  // special checks necessary if A and B are in the same basic block.
-  bool dominates(Instruction *A, Instruction *B);
-
-  /// properlyDominates - Return true if A dominates B and A != B.
-  ///
-  bool properlyDominates(BasicBlock *A, BasicBlock *B) {
-return dominates(A, B)  A != B;
-  }
-
-  /// isReachableFromEntry - Return true if A is dominated by the entry
-  /// block of the function containing it.
-  const bool isReachableFromEntry(BasicBlock* A);
-  
-  /// Return the nearest common dominator of A and B.
-  BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const  {
-ETNode *NodeA = getNode(A);
-ETNode *NodeB = getNode(B);
-
-ETNode *Common = NodeA-NCA(NodeB);
-if (!Common)
-  return NULL;
-return Common-getDataBasicBlock();
-  }
-  
-  /// Return the immediate dominator of A.
-  BasicBlock *getIDom(BasicBlock *A) const {
-ETNode *NodeA = getNode(A);
-if (!NodeA) return 0;
-const ETNode *idom = NodeA-getFather();
-return idom ? idom-getDataBasicBlock() : 0;
-  }
-  
-  void getETNodeChildren(BasicBlock *A, std::vectorBasicBlock* children) 
const {
-ETNode *NodeA = getNode(A);
-if (!NodeA) return;
-const ETNode* son = NodeA-getSon();
-
-if (!son) return;
-children.push_back(son-getDataBasicBlock());
-
-const ETNode* brother = son-getBrother();
-while (brother != son) {
-  children.push_back(brother-getDataBasicBlock());
-  brother = brother-getBrother();
-}
-  }
-
-  virtual void getAnalysisUsage(AnalysisUsage AU) const {
-AU.setPreservesAll();
-AU.addRequiredDominatorTree();
-  }
-  
//======//
-  // API to update Forest information based on modifications
-  // to the CFG...
-
-  /// addNewBlock - Add a new block to the CFG, with the specified immediate
-  /// dominator.
-  ///
-  void addNewBlock(BasicBlock *BB, BasicBlock *IDom);
-
-  /// setImmediateDominator - Update the immediate dominator information to
-  /// change the current immediate dominator for the specified block
-  /// to another block.  This method requires that BB for NewIDom
-  /// already have an ETNode, otherwise just use addNewBlock.
-  ///
-  void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom);
-  /// print - Convert to human readable form
-  ///
-  virtual void print(std::ostream OS, 

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.107 - 1.108
---
Log message:

Handle the case when block dominates itself.


---
Diffs of the changes:  (+4 -1)

 Dominators.h |5 -
 1 files changed, 4 insertions(+), 1 deletion(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.107 
llvm/include/llvm/Analysis/Dominators.h:1.108
--- llvm/include/llvm/Analysis/Dominators.h:1.107   Wed Jun 27 15:53:52 2007
+++ llvm/include/llvm/Analysis/Dominators.h Wed Jun 27 21:07:08 2007
@@ -185,7 +185,7 @@
const DomTreeNode *B) const {
 const DomTreeNode *IDom;
 if (A == 0 || B == 0) return false;
-while ((IDom = B-getIDom()) != 0  IDom != A)
+while ((IDom = B-getIDom()) != 0  IDom != A  IDom != B)
   B = IDom;   // Walk up the tree
 return IDom != 0;
   }
@@ -244,6 +244,9 @@
   DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
 assert(getNode(BB) == 0  Block already in dominator tree!);
 DomTreeNode *IDomNode = getNode(DomBB);
+// Check if BB dominates itself.
+//if (!IDomNode  BB == DomBB) 
+//  IDomNode = BB;
 assert(IDomNode  Not immediate dominator specified for block!);
 DFSInfoValid = false;
 return DomTreeNodes[BB] = 



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.108 - 1.109
---
Log message:

Remove unnecessary comments.


---
Diffs of the changes:  (+0 -3)

 Dominators.h |3 ---
 1 files changed, 3 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.108 
llvm/include/llvm/Analysis/Dominators.h:1.109
--- llvm/include/llvm/Analysis/Dominators.h:1.108   Wed Jun 27 21:07:08 2007
+++ llvm/include/llvm/Analysis/Dominators.h Wed Jun 27 21:11:54 2007
@@ -244,9 +244,6 @@
   DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
 assert(getNode(BB) == 0  Block already in dominator tree!);
 DomTreeNode *IDomNode = getNode(DomBB);
-// Check if BB dominates itself.
-//if (!IDomNode  BB == DomBB) 
-//  IDomNode = BB;
 assert(IDomNode  Not immediate dominator specified for block!);
 DFSInfoValid = false;
 return DomTreeNodes[BB] = 



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.105 - 1.106
---
Log message:

Move code to update dominator information after basic block is split
from LoopSimplify.cpp to Dominator.cpp


---
Diffs of the changes:  (+10 -0)

 Dominators.h |   10 ++
 1 files changed, 10 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.105 
llvm/include/llvm/Analysis/Dominators.h:1.106
--- llvm/include/llvm/Analysis/Dominators.h:1.105   Tue Jun 12 12:30:56 2007
+++ llvm/include/llvm/Analysis/Dominators.h Thu Jun 21 12:23:45 2007
@@ -302,6 +302,11 @@
   virtual void getAnalysisUsage(AnalysisUsage AU) const {
 AU.setPreservesAll();
   }
+
+  /// splitBlock
+  /// BB is split and now it has one successor. Update dominator tree to
+  /// reflect this change.
+  void splitBlock(BasicBlock *BB);
 private:
   void calculate(Function F);
   DomTreeNode *getNodeForBlock(BasicBlock *BB);
@@ -587,6 +592,11 @@
 AU.addRequiredDominatorTree();
   }
 
+  /// splitBlock
+  /// BB is split and now it has one successor. Update dominace frontier to
+  /// reflect this change.
+  void splitBlock(BasicBlock *BB);
+
 private:
   const DomSetType calculate(const DominatorTree DT,
   const DomTreeNode *Node);



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.104 - 1.105
---
Log message:

Protect updateDFSNumbers()


---
Diffs of the changes:  (+3 -2)

 Dominators.h |5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.104 
llvm/include/llvm/Analysis/Dominators.h:1.105
--- llvm/include/llvm/Analysis/Dominators.h:1.104   Tue Jun 12 00:49:31 2007
+++ llvm/include/llvm/Analysis/Dominators.h Tue Jun 12 12:30:56 2007
@@ -131,6 +131,8 @@
   // Info - Collection of information used during the computation of idoms.
   std::mapBasicBlock*, InfoRec Info;
 
+  void updateDFSNumbers();
+
   public:
   DominatorTreeBase(intptr_t ID, bool isPostDom) 
 : DominatorBase(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {}
@@ -191,13 +193,12 @@
 return IDom != 0;
   }
 
-  void updateDFSNumbers();  
 
   /// isReachableFromEntry - Return true if A is dominated by the entry
   /// block of the function containing it.
   const bool isReachableFromEntry(BasicBlock* A);
   
-  /// dominates - Returns true iff this dominates N.  Note that this is not a
+  /// dominates - Returns true iff A dominates B.  Note that this is not a
   /// constant time operation!
   ///
   inline bool dominates(const DomTreeNode *A, DomTreeNode *B) {



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.100 - 1.101
---
Log message:

Add and use DominatorTreeBase::findNearestCommonDominator().


---
Diffs of the changes:  (+4 -0)

 Dominators.h |4 
 1 files changed, 4 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.100 
llvm/include/llvm/Analysis/Dominators.h:1.101
--- llvm/include/llvm/Analysis/Dominators.h:1.100   Fri Jun  8 12:59:02 2007
+++ llvm/include/llvm/Analysis/Dominators.h Mon Jun 11 18:31:22 2007
@@ -234,6 +234,10 @@
 return dominates(getNode(A), getNode(B));
   }
 
+  /// findNearestCommonDominator - Find nearest common dominator basic block
+  /// for basic block A and B. If there is no such block then return NULL.
+  BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B);
+
   // dominates - Return true if A dominates B. This performs the
   // special checks necessary if A and B are in the same basic block.
   bool dominates(Instruction *A, Instruction *B);



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.101 - 1.102
---
Log message:

Maintain DFS number in DomTreeNode itself.
This means now ETNodes are not useful anymore.


---
Diffs of the changes:  (+17 -3)

 Dominators.h |   20 +---
 1 files changed, 17 insertions(+), 3 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.101 
llvm/include/llvm/Analysis/Dominators.h:1.102
--- llvm/include/llvm/Analysis/Dominators.h:1.101   Mon Jun 11 18:31:22 2007
+++ llvm/include/llvm/Analysis/Dominators.h Mon Jun 11 19:14:41 2007
@@ -65,6 +65,8 @@
   DomTreeNode *IDom;
   ETNode *ETN;
   std::vectorDomTreeNode* Children;
+  int DFSNumIn, DFSNumOut;
+
 public:
   typedef std::vectorDomTreeNode*::iterator iterator;
   typedef std::vectorDomTreeNode*::const_iterator const_iterator;
@@ -80,12 +82,22 @@
   inline const std::vectorDomTreeNode* getChildren() const { return 
Children; }
   
   inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom, ETNode *E) 
-: TheBB(BB), IDom(iDom), ETN(E) {
+: TheBB(BB), IDom(iDom), ETN(E), DFSNumIn(-1), DFSNumOut(-1) {
 if (IDom)
   ETN-setFather(IDom-getETNode());
   }
   inline DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); return 
C; }
   void setIDom(DomTreeNode *NewIDom);
+
+  // Return true if this node is dominated by other. Use this only if DFS info 
is valid.
+  bool DominatedBy(const DomTreeNode *other) const {
+return this-DFSNumIn = other-DFSNumIn 
+  this-DFSNumOut = other-DFSNumOut;
+  }
+
+  /// assignDFSNumber - Assign In and Out numbers while walking dominator tree
+  /// in dfs order.
+  void assignDFSNumber(int num);
 };
 
 
//===--===//
@@ -214,14 +226,16 @@
 ETNode *NodeB = B-getETNode();
 
 if (DFSInfoValid)
-  return NodeB-DominatedBy(NodeA);
+  return B-DominatedBy(A);
+  //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 B-DominatedBy(A);
+  //return NodeB-DominatedBy(NodeA);
 }
 //return NodeB-DominatedBySlow(NodeA);
 return dominatedBySlowTreeWalk(A, B);



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h PostDominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.102 - 1.103
PostDominators.h updated: 1.23 - 1.24
---
Log message:

Break DominatorTree from ETNode.
Remove unused PostETForest.


---
Diffs of the changes:  (+4 -54)

 Dominators.h |   34 --
 PostDominators.h |   24 
 2 files changed, 4 insertions(+), 54 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.102 
llvm/include/llvm/Analysis/Dominators.h:1.103
--- llvm/include/llvm/Analysis/Dominators.h:1.102   Mon Jun 11 19:14:41 2007
+++ llvm/include/llvm/Analysis/Dominators.h Mon Jun 11 19:54:38 2007
@@ -63,7 +63,6 @@
 class DomTreeNode {
   BasicBlock *TheBB;
   DomTreeNode *IDom;
-  ETNode *ETN;
   std::vectorDomTreeNode* Children;
   int DFSNumIn, DFSNumOut;
 
@@ -78,14 +77,10 @@
   
   inline BasicBlock *getBlock() const { return TheBB; }
   inline DomTreeNode *getIDom() const { return IDom; }
-  inline ETNode *getETNode() const { return ETN; }
   inline const std::vectorDomTreeNode* getChildren() const { return 
Children; }
   
-  inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom, ETNode *E) 
-: TheBB(BB), IDom(iDom), ETN(E), DFSNumIn(-1), DFSNumOut(-1) {
-if (IDom)
-  ETN-setFather(IDom-getETNode());
-  }
+  inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom)
+: TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
   inline DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); return 
C; }
   void setIDom(DomTreeNode *NewIDom);
 
@@ -111,9 +106,6 @@
   DomTreeNodeMapType DomTreeNodes;
   DomTreeNode *RootNode;
 
-  typedef std::mapBasicBlock*, ETNode* ETMapType;
-  ETMapType ETNodes;
-
   bool DFSInfoValid;
   unsigned int SlowQueries;
   // Information record used during immediate dominators computation.
@@ -197,17 +189,6 @@
 
   void updateDFSNumbers();  
 
-  /// Return the nearest common dominator of A and B.
-  BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const  {
-ETNode *NodeA = getNode(A)-getETNode();
-ETNode *NodeB = getNode(B)-getETNode();
-
-ETNode *Common = NodeA-NCA(NodeB);
-if (!Common)
-  return NULL;
-return Common-getDataBasicBlock();
-  }
-
   /// isReachableFromEntry - Return true if A is dominated by the entry
   /// block of the function containing it.
   const bool isReachableFromEntry(BasicBlock* A);
@@ -222,12 +203,8 @@
 if (A == 0 || B == 0)
   return false;
 
-ETNode *NodeA = A-getETNode();
-ETNode *NodeB = B-getETNode();
-
 if (DFSInfoValid)
   return B-DominatedBy(A);
-  //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.
@@ -235,9 +212,8 @@
 if (SlowQueries  32) {
   updateDFSNumbers();
   return B-DominatedBy(A);
-  //return NodeB-DominatedBy(NodeA);
 }
-//return NodeB-DominatedBySlow(NodeA);
+
 return dominatedBySlowTreeWalk(A, B);
   }
 
@@ -268,10 +244,8 @@
 DomTreeNode *IDomNode = getNode(DomBB);
 assert(IDomNode  Not immediate dominator specified for block!);
 DFSInfoValid = false;
-ETNode *E = new ETNode(BB);
-ETNodes[BB] = E;
 return DomTreeNodes[BB] = 
-  IDomNode-addChild(new DomTreeNode(BB, IDomNode, E));
+  IDomNode-addChild(new DomTreeNode(BB, IDomNode));
   }
 
   /// changeImmediateDominator - This method is used to update the dominator


Index: llvm/include/llvm/Analysis/PostDominators.h
diff -u llvm/include/llvm/Analysis/PostDominators.h:1.23 
llvm/include/llvm/Analysis/PostDominators.h:1.24
--- llvm/include/llvm/Analysis/PostDominators.h:1.23Sun Jun  3 19:32:21 2007
+++ llvm/include/llvm/Analysis/PostDominators.h Mon Jun 11 19:54:38 2007
@@ -51,30 +51,6 @@
 };
 
 
-/// PostETForest Class - Concrete subclass of ETForestBase that is used to
-/// compute a forwards post-dominator ET-Forest.
-struct PostETForest : public ETForestBase {
-  static char ID;
-  PostETForest() : ETForestBase((intptr_t)ID, true) {}
-
-  virtual void getAnalysisUsage(AnalysisUsage AU) const {
-AU.setPreservesAll();
-AU.addRequiredPostDominatorTree();
-  }
-
-  virtual bool runOnFunction(Function F) {
-reset(); // Reset from the last time we were run...
-PostDominatorTree DT = getAnalysisPostDominatorTree();
-Roots = DT.getRoots();
-calculate(DT);
-return false;
-  }
-
-  void calculate(const PostDominatorTree DT);
-  ETNode *getNodeForBlock(BasicBlock *BB);
-};
-
-
 /// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that 
is
 /// used to compute the a post-dominance frontier.
 ///



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Re: [llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

 --- llvm/include/llvm/Analysis/Dominators.h:1.95  Thu Jun  7  
 16:34:22 2007
 +++ llvm/include/llvm/Analysis/Dominators.h   Thu Jun  7 17:17:16 2007
 @@ -142,6 +142,16 @@
  return getNode(BB);
}

 +  /// getIDomBlock - return basic block BB's immediate domiantor  
 basic block.
 +  ///
 +  BasicBlock *getIDomBlock(BasicBlock *BB) {
 +DomTreeNode *N = getNode(BB);
 +assert (N  Missing dominator tree node);
 +DomTreeNode *I = N-getIDom();
 +assert (N  Missing immediate dominator);
 +return I-getBlock();
 +  }

This will assert and die if called on the entry node, because it has  
no idom.  Would it make sense to have this function return null in  
this case?  If so, please document it as returning null in that  
case.  Also, domiantor is misspelled in the comment,

-Chris

___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.99 - 1.100
---
Log message:

Fix spelling.


---
Diffs of the changes:  (+1 -1)

 Dominators.h |2 +-
 1 files changed, 1 insertion(+), 1 deletion(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.99 
llvm/include/llvm/Analysis/Dominators.h:1.100
--- llvm/include/llvm/Analysis/Dominators.h:1.99Thu Jun  7 20:50:32 2007
+++ llvm/include/llvm/Analysis/Dominators.h Fri Jun  8 12:59:02 2007
@@ -142,7 +142,7 @@
 return getNode(BB);
   }
 
-  /// getIDomBlock - return basic block BB's immediate domiantor basic block.
+  /// getIDomBlock - return basic block BB's immediate dominator basic block.
   ///
   BasicBlock *getIDomBlock(BasicBlock *BB) {
 DomTreeNode *N = getNode(BB);



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Re: [llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

 +  /// getIDomBlock - return basic block BB's immediate domiantor
 basic block.
 +  ///
 +  BasicBlock *getIDomBlock(BasicBlock *BB) {
 +DomTreeNode *N = getNode(BB);
 +assert (N  Missing dominator tree node);
 +DomTreeNode *I = N-getIDom();
 +assert (N  Missing immediate dominator);
 +return I-getBlock();
 +  }

 This will assert and die if called on the entry node, because it has
 no idom.  Would it make sense to have this function return null in
 this case?  If so, please document it as returning null in that
 case.

 Current clients do not expect null here.

I assume that current clients never call this on an entry block. If  
they did it would assert :).

I'm just saying that would be the behavior I would expect if calling  
this from a new client.

-Chris

___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.92 - 1.93
---
Log message:

Maintain ETNode as part of DomTreeNode. 
This adds redundancy for now.


---
Diffs of the changes:  (+60 -24)

 Dominators.h |   84 ++-
 1 files changed, 60 insertions(+), 24 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.92 
llvm/include/llvm/Analysis/Dominators.h:1.93
--- llvm/include/llvm/Analysis/Dominators.h:1.92Tue Jun  5 19:59:48 2007
+++ llvm/include/llvm/Analysis/Dominators.h Thu Jun  7 12:47:21 2007
@@ -63,6 +63,7 @@
 class DomTreeNode {
   BasicBlock *TheBB;
   DomTreeNode *IDom;
+  ETNode *ETN;
   std::vectorDomTreeNode* Children;
 public:
   typedef std::vectorDomTreeNode*::iterator iterator;
@@ -75,28 +76,14 @@
   
   inline BasicBlock *getBlock() const { return TheBB; }
   inline DomTreeNode *getIDom() const { return IDom; }
+  inline ETNode *getETNode() const { return ETN; }
   inline const std::vectorDomTreeNode* 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 @@
 class DominatorTreeBase : public DominatorBase {
 
 protected:
-  std::mapBasicBlock*, DomTreeNode* DomTreeNodes;
   void reset();
   typedef std::mapBasicBlock*, DomTreeNode* DomTreeNodeMapType;
-
+  DomTreeNodeMapType DomTreeNodes;
   DomTreeNode *RootNode;
 
+  typedef std::mapBasicBlock*, ETNode* ETMapType;
+  ETMapType ETNodes;
+
+  bool DFSInfoValid;
+  unsigned int SlowQueries;
   // Information record used during immediate dominators computation.
   struct InfoRec {
 unsigned Semi;
@@ -134,7 +125,7 @@
 
   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 @@
   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 @@
 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 = 

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.93 - 1.94
---
Log message:

Add BasicBlock level dominates(A,B) interface.


---
Diffs of the changes:  (+14 -2)

 Dominators.h |   16 ++--
 1 files changed, 14 insertions(+), 2 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.93 
llvm/include/llvm/Analysis/Dominators.h:1.94
--- llvm/include/llvm/Analysis/Dominators.h:1.93Thu Jun  7 12:47:21 2007
+++ llvm/include/llvm/Analysis/Dominators.h Thu Jun  7 13:39:40 2007
@@ -170,11 +170,16 @@
   }
 
   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.
+if (B == A) 
+  return true;  // A node trivially dominates itself.
+
+if (A == 0 || B == 0)
+  return false;
 
 ETNode *NodeA = A-getETNode();
 ETNode *NodeB = B-getETNode();
@@ -192,7 +197,14 @@
 //return NodeB-DominatedBySlow(NodeA);
 return dominatedBySlowTreeWalk(A, B);
   }
-  
+
+  inline bool dominates(BasicBlock *A, BasicBlock *B) {
+if (A == B) 
+  return true;
+
+return dominates(getNode(A), getNode(B));
+  }
+
   
//======//
   // API to update (Post)DominatorTree information based on modifications to
   // the CFG...



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.96 - 1.97
---
Log message:

Add instruction level dominates(A,B) interface.


---
Diffs of the changes:  (+4 -0)

 Dominators.h |4 
 1 files changed, 4 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.96 
llvm/include/llvm/Analysis/Dominators.h:1.97
--- llvm/include/llvm/Analysis/Dominators.h:1.96Thu Jun  7 17:17:16 2007
+++ llvm/include/llvm/Analysis/Dominators.h Thu Jun  7 18:52:40 2007
@@ -219,6 +219,10 @@
 return dominates(getNode(A), getNode(B));
   }
 
+  // dominates - Return true if A dominates B. This performs the
+  // special checks necessary if A and B are in the same basic block.
+  bool dominates(Instruction *A, Instruction *B);
+
   
//======//
   // API to update (Post)DominatorTree information based on modifications to
   // the CFG...



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.97 - 1.98
---
Log message:

Add new method - nearestCommonDominator().


---
Diffs of the changes:  (+11 -0)

 Dominators.h |   11 +++
 1 files changed, 11 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.97 
llvm/include/llvm/Analysis/Dominators.h:1.98
--- llvm/include/llvm/Analysis/Dominators.h:1.97Thu Jun  7 18:52:40 2007
+++ llvm/include/llvm/Analysis/Dominators.h Thu Jun  7 19:21:17 2007
@@ -185,6 +185,17 @@
 
   void updateDFSNumbers();  
 
+  /// Return the nearest common dominator of A and B.
+  BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const  {
+ETNode *NodeA = getNode(A)-getETNode();
+ETNode *NodeB = getNode(B)-getETNode();
+
+ETNode *Common = NodeA-NCA(NodeB);
+if (!Common)
+  return NULL;
+return Common-getDataBasicBlock();
+  }
+  
   /// dominates - Returns true iff this dominates N.  Note that this is not a
   /// constant time operation!
   ///



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.98 - 1.99
---
Log message:

Update LoopSimplify to require and preserve DominatorTree only.
Now LoopSimplify does not require nor preserve ETForest.


---
Diffs of the changes:  (+4 -0)

 Dominators.h |4 
 1 files changed, 4 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.98 
llvm/include/llvm/Analysis/Dominators.h:1.99
--- llvm/include/llvm/Analysis/Dominators.h:1.98Thu Jun  7 19:21:17 2007
+++ llvm/include/llvm/Analysis/Dominators.h Thu Jun  7 20:50:32 2007
@@ -195,6 +195,10 @@
   return NULL;
 return Common-getDataBasicBlock();
   }
+
+  /// isReachableFromEntry - Return true if A is dominated by the entry
+  /// block of the function containing it.
+  const bool isReachableFromEntry(BasicBlock* A);
   
   /// dominates - Returns true iff this dominates N.  Note that this is not a
   /// constant time operation!



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.90 - 1.91
---
Log message:

Simplify class hierarchy.


---
Diffs of the changes:  (+1 -3)

 Dominators.h |4 +---
 1 files changed, 1 insertion(+), 3 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.90 
llvm/include/llvm/Analysis/Dominators.h:1.91
--- llvm/include/llvm/Analysis/Dominators.h:1.90Mon Jun  4 18:45:02 2007
+++ llvm/include/llvm/Analysis/Dominators.h Tue Jun  5 19:46:36 2007
@@ -63,7 +63,7 @@
 class DomTreeNode {
   friend class DominatorTree;
   friend struct PostDominatorTree;
-  friend class DominatorTreeBase;
+
   BasicBlock *TheBB;
   DomTreeNode *IDom;
   std::vectorDomTreeNode* Children;
@@ -99,10 +99,8 @@
 return properlyDominates(N);
   }
   
-private:
   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);
 };
 



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.85 - 1.86
---
Log message:

Add basic block level interface to change immediate dominator
and create new node.


---
Diffs of the changes:  (+12 -3)

 Dominators.h |   15 ---
 1 files changed, 12 insertions(+), 3 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.85 
llvm/include/llvm/Analysis/Dominators.h:1.86
--- llvm/include/llvm/Analysis/Dominators.h:1.85Sun Jun  3 19:32:21 2007
+++ llvm/include/llvm/Analysis/Dominators.h Mon Jun  4 11:22:33 2007
@@ -110,7 +110,7 @@
 /// DominatorTree - Calculate the immediate dominator tree for a function.
 ///
 class DominatorTreeBase : public DominatorBase {
-public:
+
 protected:
   std::mapBasicBlock*, DomTreeNode* DomTreeNodes;
   void reset();
@@ -118,6 +118,7 @@
 
   DomTreeNode *RootNode;
 
+  // Information record used during immediate dominators computation.
   struct InfoRec {
 unsigned Semi;
 unsigned Size;
@@ -136,8 +137,7 @@
   // Info - Collection of information used during the computation of idoms.
   std::mapBasicBlock*, InfoRec Info;
 
-public:
-public:
+  public:
   DominatorTreeBase(intptr_t ID, bool isPostDom) 
 : DominatorBase(ID, isPostDom) {}
   ~DominatorTreeBase() { reset(); }
@@ -180,6 +180,10 @@
 return DomTreeNodes[BB] = IDomNode-addChild(new DomTreeNode(BB, 
IDomNode));
   }
 
+  void createNewNode(BasicBlock *BB, BasicBlock *DomBB) {
+createNewNode(BB, getNode(DomBB));
+  }
+
   /// changeImmediateDominator - This method is used to update the dominator
   /// tree information when a node's immediate dominator changes.
   ///
@@ -188,6 +192,11 @@
 N-setIDom(NewIDom);
   }
 
+  void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB) {
+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.



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.87 - 1.88
---
Log message:

Remove unused method.


---
Diffs of the changes:  (+2 -5)

 Dominators.h |7 ++-
 1 files changed, 2 insertions(+), 5 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.87 
llvm/include/llvm/Analysis/Dominators.h:1.88
--- llvm/include/llvm/Analysis/Dominators.h:1.87Mon Jun  4 11:43:25 2007
+++ llvm/include/llvm/Analysis/Dominators.h Mon Jun  4 11:49:36 2007
@@ -173,16 +173,13 @@
   /// addNewBlock - Add a new node to the dominator tree information.  This
   /// creates a new node as a child of DomBB dominator node,linking it into 
   /// the children list of the immediate dominator.
-  DomTreeNode *addNewBlock(BasicBlock *BB, DomTreeNode *IDomNode) {
+  DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
 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));
   }
 
-  DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
-return addNewBlock(BB, getNode(DomBB));
-  }
-
   /// changeImmediateDominator - This method is used to update the dominator
   /// tree information when a node's immediate dominator changes.
   ///



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.88 - 1.89
---
Log message:

Add FIXMEs.


---
Diffs of the changes:  (+4 -0)

 Dominators.h |4 
 1 files changed, 4 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.88 
llvm/include/llvm/Analysis/Dominators.h:1.89
--- llvm/include/llvm/Analysis/Dominators.h:1.88Mon Jun  4 11:49:36 2007
+++ llvm/include/llvm/Analysis/Dominators.h Mon Jun  4 12:37:59 2007
@@ -283,6 +283,8 @@
 
   typedef std::mapBasicBlock*, ETNode* ETMapType;
 
+  // FIXME : There is no need to make this interface public. 
+  // Fix predicate simplifier.
   void updateDFSNumbers();
 
   /// dominates - Return true if A dominates B.
@@ -426,6 +428,8 @@
   }
 
   void calculate(const DominatorTree DT);
+  // FIXME : There is no need to make getNodeForBlock public. Fix
+  // predicate simplifier.
   ETNode *getNodeForBlock(BasicBlock *BB);
 };
 



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.89 - 1.90
---
Log message:

s/ETNode::getChildren/ETNode::getETNodeChildren/g


---
Diffs of the changes:  (+1 -1)

 Dominators.h |2 +-
 1 files changed, 1 insertion(+), 1 deletion(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.89 
llvm/include/llvm/Analysis/Dominators.h:1.90
--- llvm/include/llvm/Analysis/Dominators.h:1.89Mon Jun  4 12:37:59 2007
+++ llvm/include/llvm/Analysis/Dominators.h Mon Jun  4 18:45:02 2007
@@ -343,7 +343,7 @@
 return idom ? idom-getDataBasicBlock() : 0;
   }
   
-  void getChildren(BasicBlock *A, std::vectorBasicBlock* children) const {
+  void getETNodeChildren(BasicBlock *A, std::vectorBasicBlock* children) 
const {
 ETNode *NodeA = getNode(A);
 if (!NodeA) return;
 const ETNode* son = NodeA-getSon();



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h PostDominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.83 - 1.84
PostDominators.h updated: 1.21 - 1.22
---
Log message:

s/DominatorTreeBase::Node/DominatorTreeBase:DomTreeNode/g



---
Diffs of the changes:  (+35 -35)

 Dominators.h |   64 +++
 PostDominators.h |6 ++---
 2 files changed, 35 insertions(+), 35 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.83 
llvm/include/llvm/Analysis/Dominators.h:1.84
--- llvm/include/llvm/Analysis/Dominators.h:1.83Wed May 23 14:55:36 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sun Jun  3 01:26:14 2007
@@ -61,13 +61,13 @@
 ///
 class DominatorTreeBase : public DominatorBase {
 public:
-  class Node;
+  class DomTreeNode;
 protected:
-  std::mapBasicBlock*, Node* Nodes;
+  std::mapBasicBlock*, DomTreeNode* DomTreeNodes;
   void reset();
-  typedef std::mapBasicBlock*, Node* NodeMapType;
+  typedef std::mapBasicBlock*, DomTreeNode* DomTreeNodeMapType;
 
-  Node *RootNode;
+  DomTreeNode *RootNode;
 
   struct InfoRec {
 unsigned Semi;
@@ -88,16 +88,16 @@
   std::mapBasicBlock*, InfoRec Info;
 
 public:
-  class Node {
+  class DomTreeNode {
 friend class DominatorTree;
 friend struct PostDominatorTree;
 friend class DominatorTreeBase;
 BasicBlock *TheBB;
-Node *IDom;
-std::vectorNode* Children;
+DomTreeNode *IDom;
+std::vectorDomTreeNode* Children;
   public:
-typedef std::vectorNode*::iterator iterator;
-typedef std::vectorNode*::const_iterator const_iterator;
+typedef std::vectorDomTreeNode*::iterator iterator;
+typedef std::vectorDomTreeNode*::const_iterator const_iterator;
 
 iterator begin() { return Children.begin(); }
 iterator end()   { return Children.end(); }
@@ -105,14 +105,14 @@
 const_iterator end()   const { return Children.end(); }
 
 inline BasicBlock *getBlock() const { return TheBB; }
-inline Node *getIDom() const { return IDom; }
-inline const std::vectorNode* getChildren() const { return Children; }
+inline DomTreeNode *getIDom() const { return IDom; }
+inline const std::vectorDomTreeNode* 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 Node *N) const {
-  const Node *IDom;
+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
@@ -122,16 +122,16 @@
 /// dominates - Returns true iff this dominates N.  Note that this is not a
 /// constant time operation!
 ///
-inline bool dominates(const Node *N) const {
+inline bool dominates(const DomTreeNode *N) const {
   if (N == this) return true;  // A node trivially dominates itself.
   return properlyDominates(N);
 }
 
   private:
-inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {}
-inline Node *addChild(Node *C) { Children.push_back(C); return C; }
+inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom) : TheBB(BB), 
IDom(iDom) {}
+inline DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); 
return C; }
 
-void setIDom(Node *NewIDom);
+void setIDom(DomTreeNode *NewIDom);
   };
 
 public:
@@ -144,12 +144,12 @@
   /// getNode - return the (Post)DominatorTree node for the specified basic
   /// block.  This is the same as using operator[] on this class.
   ///
-  inline Node *getNode(BasicBlock *BB) const {
-NodeMapType::const_iterator i = Nodes.find(BB);
-return (i != Nodes.end()) ? i-second : 0;
+  inline DomTreeNode *getNode(BasicBlock *BB) const {
+DomTreeNodeMapType::const_iterator i = DomTreeNodes.find(BB);
+return (i != DomTreeNodes.end()) ? i-second : 0;
   }
 
-  inline Node *operator[](BasicBlock *BB) const {
+  inline DomTreeNode *operator[](BasicBlock *BB) const {
 return getNode(BB);
   }
 
@@ -160,8 +160,8 @@
   /// post-dominance information must be capable of dealing with this
   /// possibility.
   ///
-  Node *getRootNode() { return RootNode; }
-  const Node *getRootNode() const { return RootNode; }
+  DomTreeNode *getRootNode() { return RootNode; }
+  const DomTreeNode *getRootNode() const { return RootNode; }
 
   
//======//
   // API to update (Post)DominatorTree information based on modifications to
@@ -171,16 +171,16 @@
   /// creates a new node as a child of IDomNode, linking it into the children
   /// list of the immediate dominator.
   ///
-  Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
+  DomTreeNode *createNewNode(BasicBlock *BB, DomTreeNode *IDomNode) {
 assert(getNode(BB) == 0  Block 

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h PostDominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.84 - 1.85
PostDominators.h updated: 1.22 - 1.23
---
Log message:

s/llvm::DominatorTreeBase::DomTreeNode/llvm::DomTreeNode/g


---
Diffs of the changes:  (+57 -53)

 Dominators.h |  106 ---
 PostDominators.h |4 +-
 2 files changed, 57 insertions(+), 53 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.84 
llvm/include/llvm/Analysis/Dominators.h:1.85
--- llvm/include/llvm/Analysis/Dominators.h:1.84Sun Jun  3 01:26:14 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sun Jun  3 19:32:21 2007
@@ -56,12 +56,61 @@
   bool isPostDominator() const { return IsPostDominators; }
 };
 
+
+//===--===//
+// DomTreeNode - Dominator Tree Node
+
+class DomTreeNode {
+  friend class DominatorTree;
+  friend struct PostDominatorTree;
+  friend class DominatorTreeBase;
+  BasicBlock *TheBB;
+  DomTreeNode *IDom;
+  std::vectorDomTreeNode* Children;
+public:
+  typedef std::vectorDomTreeNode*::iterator iterator;
+  typedef std::vectorDomTreeNode*::const_iterator const_iterator;
+  
+  iterator begin() { return Children.begin(); }
+  iterator end()   { return Children.end(); }
+  const_iterator begin() const { return Children.begin(); }
+  const_iterator end()   const { return Children.end(); }
+  
+  inline BasicBlock *getBlock() const { return TheBB; }
+  inline DomTreeNode *getIDom() const { return IDom; }
+  inline const std::vectorDomTreeNode* 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);
+  }
+  
+private:
+  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);
+};
+
 
//===--===//
 /// DominatorTree - Calculate the immediate dominator tree for a function.
 ///
 class DominatorTreeBase : public DominatorBase {
 public:
-  class DomTreeNode;
 protected:
   std::mapBasicBlock*, DomTreeNode* DomTreeNodes;
   void reset();
@@ -88,52 +137,6 @@
   std::mapBasicBlock*, InfoRec Info;
 
 public:
-  class DomTreeNode {
-friend class DominatorTree;
-friend struct PostDominatorTree;
-friend class DominatorTreeBase;
-BasicBlock *TheBB;
-DomTreeNode *IDom;
-std::vectorDomTreeNode* Children;
-  public:
-typedef std::vectorDomTreeNode*::iterator iterator;
-typedef std::vectorDomTreeNode*::const_iterator const_iterator;
-
-iterator begin() { return Children.begin(); }
-iterator end()   { return Children.end(); }
-const_iterator begin() const { return Children.begin(); }
-const_iterator end()   const { return Children.end(); }
-
-inline BasicBlock *getBlock() const { return TheBB; }
-inline DomTreeNode *getIDom() const { return IDom; }
-inline const std::vectorDomTreeNode* 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);
-}
-
-  private:
-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);
-  };
-
 public:
   DominatorTreeBase(intptr_t ID, bool isPostDom) 
 : DominatorBase(ID, isPostDom) {}
@@ -238,8 +241,8 @@
 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 /// iterable by generic graph iterators.
 

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.82 - 1.83
---
Log message:

Add dump() routines for debugging assistance.


---
Diffs of the changes:  (+3 -0)

 Dominators.h |3 +++
 1 files changed, 3 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.82 
llvm/include/llvm/Analysis/Dominators.h:1.83
--- llvm/include/llvm/Analysis/Dominators.h:1.82Sun May 13 20:54:16 2007
+++ llvm/include/llvm/Analysis/Dominators.h Wed May 23 14:55:36 2007
@@ -199,6 +199,7 @@
   void print(std::ostream *OS, const Module* M = 0) const {
 if (OS) print(*OS, M);
   }
+  virtual void dump();
 };
 
 //===-
@@ -372,6 +373,7 @@
   void print(std::ostream *OS, const Module* M = 0) const {
 if (OS) print(*OS, M);
   }
+  virtual void dump();
 protected:
   /// getNode - return the (Post)DominatorTree node for the specified basic
   /// block.  This is the same as using operator[] on this class.
@@ -467,6 +469,7 @@
   void print(std::ostream *OS, const Module* M = 0) const {
 if (OS) print(*OS, M);
   }
+  virtual void dump();
 };
 
 



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.81 - 1.82
---
Log message:

update comments


---
Diffs of the changes:  (+2 -3)

 Dominators.h |5 ++---
 1 files changed, 2 insertions(+), 3 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.81 
llvm/include/llvm/Analysis/Dominators.h:1.82
--- llvm/include/llvm/Analysis/Dominators.h:1.81Sun May  6 08:37:15 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sun May 13 20:54:16 2007
@@ -8,8 +8,7 @@
 
//===--===//
 //
 // This file defines the following classes:
-//  1. DominatorTree: Represent the ImmediateDominator as an explicit tree
-// structure.
+//  1. DominatorTree: Represent dominators as an explicit tree structure.
 //  2. ETForest: Efficient data structure for dominance comparisons and 
 // nearest-common-ancestor queries.
 //  3. DominanceFrontier: Calculate and hold the dominance frontier for a
@@ -17,7 +16,7 @@
 //
 //  These data structures are listed in increasing order of complexity.  It
 //  takes longer to calculate the dominator frontier, for example, than the
-//  ImmediateDominator mapping.
+//  DominatorTree mapping.
 //
 
//===--===//
 



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h FindUsedTypes.h IntervalPartition.h LoopInfo.h PostDominators.h ScalarEvolution.h

[Nick Lewycky]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.80 - 1.81
FindUsedTypes.h updated: 1.32 - 1.33
IntervalPartition.h updated: 1.26 - 1.27
LoopInfo.h updated: 1.66 - 1.67
PostDominators.h updated: 1.20 - 1.21
ScalarEvolution.h updated: 1.20 - 1.21
---
Log message:

Fix typo in comment.


---
Diffs of the changes:  (+6 -6)

 Dominators.h|2 +-
 FindUsedTypes.h |2 +-
 IntervalPartition.h |2 +-
 LoopInfo.h  |2 +-
 PostDominators.h|2 +-
 ScalarEvolution.h   |2 +-
 6 files changed, 6 insertions(+), 6 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.80 
llvm/include/llvm/Analysis/Dominators.h:1.81
--- llvm/include/llvm/Analysis/Dominators.h:1.80Thu May  3 15:55:18 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sun May  6 08:37:15 2007
@@ -399,7 +399,7 @@
 
 class ETForest : public ETForestBase {
 public:
-  static char ID; // Pass identifcation, replacement for typeid
+  static char ID; // Pass identification, replacement for typeid
 
   ETForest() : ETForestBase((intptr_t)ID, false) {}
 


Index: llvm/include/llvm/Analysis/FindUsedTypes.h
diff -u llvm/include/llvm/Analysis/FindUsedTypes.h:1.32 
llvm/include/llvm/Analysis/FindUsedTypes.h:1.33
--- llvm/include/llvm/Analysis/FindUsedTypes.h:1.32 Wed May  2 20:11:53 2007
+++ llvm/include/llvm/Analysis/FindUsedTypes.h  Sun May  6 08:37:15 2007
@@ -24,7 +24,7 @@
 class FindUsedTypes : public ModulePass {
   std::setconst Type * UsedTypes;
 public:
-  static char ID; // Pass identifcation, replacement for typeid
+  static char ID; // Pass identification, replacement for typeid
   FindUsedTypes() : ModulePass((intptr_t)ID) {}
 
   /// getTypes - After the pass has been run, return the set containing all of


Index: llvm/include/llvm/Analysis/IntervalPartition.h
diff -u llvm/include/llvm/Analysis/IntervalPartition.h:1.26 
llvm/include/llvm/Analysis/IntervalPartition.h:1.27
--- llvm/include/llvm/Analysis/IntervalPartition.h:1.26 Wed May  2 20:11:53 2007
+++ llvm/include/llvm/Analysis/IntervalPartition.h  Sun May  6 08:37:15 2007
@@ -45,7 +45,7 @@
   std::vectorInterval* Intervals;
 
 public:
-  static char ID; // Pass identifcation, replacement for typeid
+  static char ID; // Pass identification, replacement for typeid
 
   IntervalPartition() : FunctionPass((intptr_t)ID), RootInterval(0) {}
 


Index: llvm/include/llvm/Analysis/LoopInfo.h
diff -u llvm/include/llvm/Analysis/LoopInfo.h:1.66 
llvm/include/llvm/Analysis/LoopInfo.h:1.67
--- llvm/include/llvm/Analysis/LoopInfo.h:1.66  Wed May  2 20:11:53 2007
+++ llvm/include/llvm/Analysis/LoopInfo.h   Sun May  6 08:37:15 2007
@@ -241,7 +241,7 @@
   std::vectorLoop* TopLevelLoops;
   friend class Loop;
 public:
-  static char ID; // Pass identifcation, replacement for typeid
+  static char ID; // Pass identification, replacement for typeid
 
   LoopInfo() : FunctionPass((intptr_t)ID) {}
   ~LoopInfo() { releaseMemory(); }


Index: llvm/include/llvm/Analysis/PostDominators.h
diff -u llvm/include/llvm/Analysis/PostDominators.h:1.20 
llvm/include/llvm/Analysis/PostDominators.h:1.21
--- llvm/include/llvm/Analysis/PostDominators.h:1.20Wed May  2 20:11:53 2007
+++ llvm/include/llvm/Analysis/PostDominators.h Sun May  6 08:37:15 2007
@@ -22,7 +22,7 @@
 /// compute the a post-dominator tree.
 ///
 struct PostDominatorTree : public DominatorTreeBase {
-  static char ID; // Pass identifcation, replacement for typeid
+  static char ID; // Pass identification, replacement for typeid
 
   PostDominatorTree() : 
 DominatorTreeBase((intptr_t)ID, true) {}


Index: llvm/include/llvm/Analysis/ScalarEvolution.h
diff -u llvm/include/llvm/Analysis/ScalarEvolution.h:1.20 
llvm/include/llvm/Analysis/ScalarEvolution.h:1.21
--- llvm/include/llvm/Analysis/ScalarEvolution.h:1.20   Thu May  3 13:45:06 2007
+++ llvm/include/llvm/Analysis/ScalarEvolution.hSun May  6 08:37:15 2007
@@ -197,7 +197,7 @@
   class ScalarEvolution : public FunctionPass {
 void *Impl;// ScalarEvolution uses the pimpl pattern
   public:
-static char ID; // Pass identifcation, replacement for typeid
+static char ID; // Pass identification, replacement for typeid
 ScalarEvolution() : FunctionPass((intptr_t)ID), Impl(0) {}
 
 /// getSCEV - Return a SCEV expression handle for the full generality of 
the



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.79 - 1.80
---
Log message:

Use iterative while loop instead of recursive function call.


---
Diffs of the changes:  (+1 -1)

 Dominators.h |2 +-
 1 files changed, 1 insertion(+), 1 deletion(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.79 
llvm/include/llvm/Analysis/Dominators.h:1.80
--- llvm/include/llvm/Analysis/Dominators.h:1.79Wed May  2 20:11:53 2007
+++ llvm/include/llvm/Analysis/Dominators.h Thu May  3 15:55:18 2007
@@ -225,7 +225,7 @@
   void calculate(Function F);
   Node *getNodeForBlock(BasicBlock *BB);
   unsigned DFSPass(BasicBlock *V, InfoRec VInfo, unsigned N);
-  void Compress(BasicBlock *V, InfoRec VInfo);
+  void Compress(BasicBlock *V);
   BasicBlock *Eval(BasicBlock *v);
   void Link(BasicBlock *V, BasicBlock *W, InfoRec WInfo);
   inline BasicBlock *getIDom(BasicBlock *BB) const {



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Re: [llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h ET-Forest.h

[Chris Lattner]

 Add accessor to get the blocks immediately dominated by a given  
 block to ETForest.

Ok...

 @@ -327,6 +327,20 @@
  const ETNode *idom = NodeA-getFather();
  return idom ? idom-getDataBasicBlock() : 0;
}
 +
 +  void getChildren(BasicBlock *A, std::vectorBasicBlock*  
 children) {
 +ETNode *NodeA = getNode(A);
 +const ETNode* son = NodeA-getSon();
 +
 +if (!son) return;
 +children.push_back(son-getDataBasicBlock());
 +
 +const ETNode* brother = son-getBrother();
 +while (brother != son) {
 +  children.push_back(brother-getDataBasicBlock());
 +  brother = brother-getBrother();
 +}
 +  }

Two things :).  First, why merge domtree into etforest?  The tree  
structure used by domtree is more efficient for representing children  
than the one used by etforest.  If you really want to merge into  
etforest, please change it to keep a vector of children, instead of  
the brother scheme it uses.  This will allow this accessor to be a  
constant time operation (returning a const reference to a pre- 
existing vector) that doesn't do a ton of pointer chasing.

Is that feasible?

-Chris


___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.75 - 1.76
---
Log message:

Fix some null checks to actually test the part that needs checking.


---
Diffs of the changes:  (+2 -3)

 Dominators.h |5 ++---
 1 files changed, 2 insertions(+), 3 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.75 
llvm/include/llvm/Analysis/Dominators.h:1.76
--- llvm/include/llvm/Analysis/Dominators.h:1.75Fri Apr 20 00:44:16 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sat Apr 21 02:04:45 2007
@@ -323,16 +323,15 @@
   
   /// Return the immediate dominator of A.
   BasicBlock *getIDom(BasicBlock *A) const {
-if (!A) return 0;
-
 ETNode *NodeA = getNode(A);
+if (!NodeA) return 0;
 const ETNode *idom = NodeA-getFather();
 return idom ? idom-getDataBasicBlock() : 0;
   }
   
   void getChildren(BasicBlock *A, std::vectorBasicBlock* children) const {
-if (!A) return;
 ETNode *NodeA = getNode(A);
+if (!NodeA) return;
 const ETNode* son = NodeA-getSon();
 
 if (!son) return;



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.74 - 1.75
---
Log message:

Add null checks and const-ify these accessors.


---
Diffs of the changes:  (+5 -2)

 Dominators.h |7 +--
 1 files changed, 5 insertions(+), 2 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.74 
llvm/include/llvm/Analysis/Dominators.h:1.75
--- llvm/include/llvm/Analysis/Dominators.h:1.74Wed Apr 18 00:25:09 2007
+++ llvm/include/llvm/Analysis/Dominators.h Fri Apr 20 00:44:16 2007
@@ -322,13 +322,16 @@
   }
   
   /// Return the immediate dominator of A.
-  BasicBlock *getIDom(BasicBlock *A) {
+  BasicBlock *getIDom(BasicBlock *A) const {
+if (!A) return 0;
+
 ETNode *NodeA = getNode(A);
 const ETNode *idom = NodeA-getFather();
 return idom ? idom-getDataBasicBlock() : 0;
   }
   
-  void getChildren(BasicBlock *A, std::vectorBasicBlock* children) {
+  void getChildren(BasicBlock *A, std::vectorBasicBlock* children) const {
+if (!A) return;
 ETNode *NodeA = getNode(A);
 const ETNode* son = NodeA-getSon();
 



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Re: [llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

/// Return the immediate dominator of A.
 -  BasicBlock *getIDom(BasicBlock *A) {
 +  BasicBlock *getIDom(BasicBlock *A) const {
 +if (!A) return 0;
 +
  ETNode *NodeA = getNode(A);

A can't be null here, please check that NodeA isn't null instead  
(i.e. that A is reachable).

-Chris

  const ETNode *idom = NodeA-getFather();
  return idom ? idom-getDataBasicBlock() : 0;
}

 -  void getChildren(BasicBlock *A, std::vectorBasicBlock*  
 children) {
 +  void getChildren(BasicBlock *A, std::vectorBasicBlock*  
 children) const {
 +if (!A) return;
  ETNode *NodeA = getNode(A);
  const ETNode* son = NodeA-getSon();




 ___
 llvm-commits mailing list
 llvm-commits@cs.uiuc.edu
 http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Re: [llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

On Apr 17, 2007, at 9:38 PM, Owen Anderson wrote:

 Index: llvm/include/llvm/Analysis/Dominators.h
 diff -u llvm/include/llvm/Analysis/Dominators.h:1.72 llvm/include/ 
 llvm/Analysis/Dominators.h:1.73
 --- llvm/include/llvm/Analysis/Dominators.h:1.72  Sun Apr 15 18:14:18  
 2007
 +++ llvm/include/llvm/Analysis/Dominators.h   Tue Apr 17 23:38:39 2007
 @@ -320,6 +320,13 @@
   return NULL;
 return Common-getDataBasicBlock();
   }
 +
 +  /// Return the immediate dominator of A.
 +  BasicBlock *getIDom(BasicBlock *A) {
 +ETNode *NodeA = getNode(A);

Please add an assert to check that  NodeA is not null. Thanks!
-
Devang

 +const ETNode *idom = NodeA-getFather();
 +return idom ? idom-getDataBasicBlock() : 0;
 +  }

   virtual void getAnalysisUsage(AnalysisUsage AU) const {
 AU.setPreservesAll();



 ___
 llvm-commits mailing list
 llvm-commits@cs.uiuc.edu
 http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Re: [llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

On Apr 19, 2007, at 11:10 AM, Devang Patel wrote:


 On Apr 17, 2007, at 9:38 PM, Owen Anderson wrote:

 Index: llvm/include/llvm/Analysis/Dominators.h
 diff -u llvm/include/llvm/Analysis/Dominators.h:1.72 llvm/include/
 llvm/Analysis/Dominators.h:1.73
 --- llvm/include/llvm/Analysis/Dominators.h:1.72 Sun Apr 15 18:14:18
 2007
 +++ llvm/include/llvm/Analysis/Dominators.h  Tue Apr 17 23:38:39 2007
 @@ -320,6 +320,13 @@
   return NULL;
 return Common-getDataBasicBlock();
   }
 +
 +  /// Return the immediate dominator of A.
 +  BasicBlock *getIDom(BasicBlock *A) {
 +ETNode *NodeA = getNode(A);

 Please add an assert to check that  NodeA is not null. Thanks!

Also, please mark this method const :)

-Chris


___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Re: [llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

 +  /// Return the immediate dominator of A.
 +  BasicBlock *getIDom(BasicBlock *A) {
 +ETNode *NodeA = getNode(A);
 +const ETNode *idom = NodeA-getFather();
 +return idom ? idom-getDataBasicBlock() : 0;
 +  }

Random other question: Why does ETNode have a template accessor to  
get its data?  Is the Data pointer every anything other than a  
BasicBlock*?  If not, why not just type the pointer as BasicBlock*  
and rename getData() - getBasicBlock() ?

-Chris
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.72 - 1.73
---
Log message:

Add an accessor to make ETForest more useful.


---
Diffs of the changes:  (+7 -0)

 Dominators.h |7 +++
 1 files changed, 7 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.72 
llvm/include/llvm/Analysis/Dominators.h:1.73
--- llvm/include/llvm/Analysis/Dominators.h:1.72Sun Apr 15 18:14:18 2007
+++ llvm/include/llvm/Analysis/Dominators.h Tue Apr 17 23:38:39 2007
@@ -320,6 +320,13 @@
   return NULL;
 return Common-getDataBasicBlock();
   }
+  
+  /// Return the immediate dominator of A.
+  BasicBlock *getIDom(BasicBlock *A) {
+ETNode *NodeA = getNode(A);
+const ETNode *idom = NodeA-getFather();
+return idom ? idom-getDataBasicBlock() : 0;
+  }
 
   virtual void getAnalysisUsage(AnalysisUsage AU) const {
 AU.setPreservesAll();



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h ET-Forest.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.73 - 1.74
ET-Forest.h updated: 1.9 - 1.10
---
Log message:

Add accessor to get the blocks immediately dominated by a given block to 
ETForest.


---
Diffs of the changes:  (+22 -0)

 Dominators.h |   14 ++
 ET-Forest.h  |8 
 2 files changed, 22 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.73 
llvm/include/llvm/Analysis/Dominators.h:1.74
--- llvm/include/llvm/Analysis/Dominators.h:1.73Tue Apr 17 23:38:39 2007
+++ llvm/include/llvm/Analysis/Dominators.h Wed Apr 18 00:25:09 2007
@@ -327,6 +327,20 @@
 const ETNode *idom = NodeA-getFather();
 return idom ? idom-getDataBasicBlock() : 0;
   }
+  
+  void getChildren(BasicBlock *A, std::vectorBasicBlock* children) {
+ETNode *NodeA = getNode(A);
+const ETNode* son = NodeA-getSon();
+
+if (!son) return;
+children.push_back(son-getDataBasicBlock());
+
+const ETNode* brother = son-getBrother();
+while (brother != son) {
+  children.push_back(brother-getDataBasicBlock());
+  brother = brother-getBrother();
+}
+  }
 
   virtual void getAnalysisUsage(AnalysisUsage AU) const {
 AU.setPreservesAll();


Index: llvm/include/llvm/Analysis/ET-Forest.h
diff -u llvm/include/llvm/Analysis/ET-Forest.h:1.9 
llvm/include/llvm/Analysis/ET-Forest.h:1.10
--- llvm/include/llvm/Analysis/ET-Forest.h:1.9  Wed Feb 21 13:57:33 2007
+++ llvm/include/llvm/Analysis/ET-Forest.h  Wed Apr 18 00:25:09 2007
@@ -275,6 +275,14 @@
 return DFSNumOut;
   }
 
+  const ETNode *getSon() const {
+return Son;
+  }
+  
+  const ETNode *getBrother() const {
+return Left;
+  }
+
  private:
   // Data represented by the node
   void *data;



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Re: [llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h PostDominators.h

[Chris Lattner]

 Remove ImmediateDominator analysis.  The same information can be  
 obtained from DomTree.  A lot of code for
 constructing ImmediateDominator is now folded into DomTree  
 construction.

 This is part of the ongoing work for PR217: http://llvm.org/PR217 .

Woot.
 +
 + struct InfoRec {

tab

 -return false;
 -  }
 + virtual bool runOnFunction(Function F);

tab

 +  BasicBlock *Eval(BasicBlock *v);
 +  void Link(BasicBlock *V, BasicBlock *W, InfoRec WInfo);
 + inline BasicBlock *getIDom(BasicBlock *BB) const {
 + std::mapBasicBlock*, BasicBlock*::const_iterator I =  
 IDoms.find(BB);
 + return I != IDoms.end() ? I-second : 0;
 +   }
  };

tabz

 -  void calculate(const ImmediatePostDominators IPD);
 +  void calculate(Function F);
Node *getNodeForBlock(BasicBlock *BB);
 +  unsigned DFSPass(BasicBlock *V, InfoRec VInfo,unsigned N);
 + void Compress(BasicBlock *V, InfoRec VInfo);
 + BasicBlock *Eval(BasicBlock *V);
 + void Link(BasicBlock *V, BasicBlock *W, InfoRec WInfo);
 +

tabs

 +  inline BasicBlock *getIDom(BasicBlock *BB) const {
 +   std::mapBasicBlock*, BasicBlock*::const_iterator I =  
 IDoms.find(BB);
 +   return I != IDoms.end() ? I-second : 0;
 + }
  };

tabz

-Chris
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h PostDominators.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.71 - 1.72
PostDominators.h updated: 1.16 - 1.17
---
Log message:

Tabs - Spaces


---
Diffs of the changes:  (+12 -12)

 Dominators.h |   12 ++--
 PostDominators.h |   12 ++--
 2 files changed, 12 insertions(+), 12 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.71 
llvm/include/llvm/Analysis/Dominators.h:1.72
--- llvm/include/llvm/Analysis/Dominators.h:1.71Sun Apr 15 03:47:27 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sun Apr 15 18:14:18 2007
@@ -69,7 +69,7 @@
 
   Node *RootNode;
 
-   struct InfoRec {
+  struct InfoRec {
 unsigned Semi;
 unsigned Size;
 BasicBlock *Label, *Parent, *Child, *Ancestor;
@@ -213,7 +213,7 @@
 return Roots[0];
   }
   
-   virtual bool runOnFunction(Function F);
+  virtual bool runOnFunction(Function F);
   
   virtual void getAnalysisUsage(AnalysisUsage AU) const {
 AU.setPreservesAll();
@@ -225,10 +225,10 @@
   void Compress(BasicBlock *V, InfoRec VInfo);
   BasicBlock *Eval(BasicBlock *v);
   void Link(BasicBlock *V, BasicBlock *W, InfoRec WInfo);
-   inline BasicBlock *getIDom(BasicBlock *BB) const {
-   std::mapBasicBlock*, BasicBlock*::const_iterator I = 
IDoms.find(BB);
-   return I != IDoms.end() ? I-second : 0;
- }
+  inline BasicBlock *getIDom(BasicBlock *BB) const {
+  std::mapBasicBlock*, BasicBlock*::const_iterator I = IDoms.find(BB);
+  return I != IDoms.end() ? I-second : 0;
+}
 };
 
 //===-


Index: llvm/include/llvm/Analysis/PostDominators.h
diff -u llvm/include/llvm/Analysis/PostDominators.h:1.16 
llvm/include/llvm/Analysis/PostDominators.h:1.17
--- llvm/include/llvm/Analysis/PostDominators.h:1.16Sun Apr 15 03:47:27 2007
+++ llvm/include/llvm/Analysis/PostDominators.h Sun Apr 15 18:14:18 2007
@@ -37,14 +37,14 @@
   void calculate(Function F);
   Node *getNodeForBlock(BasicBlock *BB);
   unsigned DFSPass(BasicBlock *V, InfoRec VInfo,unsigned N);
-   void Compress(BasicBlock *V, InfoRec VInfo);
-   BasicBlock *Eval(BasicBlock *V);
-   void Link(BasicBlock *V, BasicBlock *W, InfoRec WInfo);
+  void Compress(BasicBlock *V, InfoRec VInfo);
+  BasicBlock *Eval(BasicBlock *V);
+  void Link(BasicBlock *V, BasicBlock *W, InfoRec WInfo);
 
   inline BasicBlock *getIDom(BasicBlock *BB) const {
- std::mapBasicBlock*, BasicBlock*::const_iterator I = IDoms.find(BB);
- return I != IDoms.end() ? I-second : 0;
-   }
+std::mapBasicBlock*, BasicBlock*::const_iterator I = IDoms.find(BB);
+return I != IDoms.end() ? I-second : 0;
+  }
 };
 
 



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Re: [llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h PostDominators.h

[Chris Lattner]

 @@ -225,10 +225,10 @@
void Compress(BasicBlock *V, InfoRec VInfo);
BasicBlock *Eval(BasicBlock *v);
void Link(BasicBlock *V, BasicBlock *W, InfoRec WInfo);
 - inline BasicBlock *getIDom(BasicBlock *BB) const {
 - std::mapBasicBlock*, BasicBlock*::const_iterator I =  
 IDoms.find(BB);
 - return I != IDoms.end() ? I-second : 0;
 -   }
 +  inline BasicBlock *getIDom(BasicBlock *BB) const {
 +  std::mapBasicBlock*, BasicBlock*::const_iterator I =  
 IDoms.find(BB);
 +  return I != IDoms.end() ? I-second : 0;
 +}
  };

Heh, try again :)

Thanks Owen!

-Chris


___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.69 - 1.70
---
Log message:

Make ETForest depend on DomTree rather than IDom.  This is the first step
in the long process that will be fixing PR 217: http://llvm.org/PR217 .


---
Diffs of the changes:  (+5 -5)

 Dominators.h |   10 +-
 1 files changed, 5 insertions(+), 5 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.69 
llvm/include/llvm/Analysis/Dominators.h:1.70
--- llvm/include/llvm/Analysis/Dominators.h:1.69Sun Apr  8 23:07:36 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sat Apr 14 18:49:24 2007
@@ -422,7 +422,7 @@
 
   virtual void getAnalysisUsage(AnalysisUsage AU) const {
 AU.setPreservesAll();
-AU.addRequiredImmediateDominators();
+AU.addRequiredDominatorTree();
   }
   
//======//
   // API to update Forest information based on modifications
@@ -480,13 +480,13 @@
 
   virtual bool runOnFunction(Function F) {
 reset(); // Reset from the last time we were run...
-ImmediateDominators ID = getAnalysisImmediateDominators();
-Roots = ID.getRoots();
-calculate(ID);
+DominatorTree DT = getAnalysisDominatorTree();
+Roots = DT.getRoots();
+calculate(DT);
 return false;
   }
 
-  void calculate(const ImmediateDominators ID);
+  void calculate(const DominatorTree DT);
   ETNode *getNodeForBlock(BasicBlock *BB);
 };
 



___
llvm-commits mailing list
[EMAIL PROTECTED]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.66 - 1.67
---
Log message:

Remove DomSet completely.  This concludes work on PR1171: 
http://llvm.org/PR1171 .


---
Diffs of the changes:  (+3 -127)

 Dominators.h |  130 +--
 1 files changed, 3 insertions(+), 127 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.66 
llvm/include/llvm/Analysis/Dominators.h:1.67
--- llvm/include/llvm/Analysis/Dominators.h:1.66Sat Apr  7 13:23:27 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sun Apr  8 16:30:05 2007
@@ -10,12 +10,11 @@
 // This file defines the following classes:
 //  1. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
 // and their immediate dominator.
-//  2. DominatorSet: Calculates the [reverse] dominator set for a function
-//  3. DominatorTree: Represent the ImmediateDominator as an explicit tree
+//  2. DominatorTree: Represent the ImmediateDominator as an explicit tree
 // structure.
-//  4. ETForest: Efficient data structure for dominance comparisons and 
+//  3. ETForest: Efficient data structure for dominance comparisons and 
 // nearest-common-ancestor queries.
-//  5. DominanceFrontier: Calculate and hold the dominance frontier for a
+//  4. DominanceFrontier: Calculate and hold the dominance frontier for a
 // function.
 //
 //  These data structures are listed in increasing order of complexity.  It
@@ -176,126 +175,6 @@
 };
 
 
-
-//===--===//
-/// DominatorSet - Maintain a setBasicBlock* for every basic block in a
-/// function, that represents the blocks that dominate the block.  If the block
-/// is unreachable in this function, the set will be empty.  This cannot happen
-/// for reachable code, because every block dominates at least itself.
-///
-class DominatorSetBase : public DominatorBase {
-public:
-  typedef std::setBasicBlock* DomSetType;// Dom set for a bb
-  // Map of dom sets
-  typedef std::mapBasicBlock*, DomSetType DomSetMapType;
-protected:
-  DomSetMapType Doms;
-public:
-  DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
-
-  virtual void releaseMemory() { Doms.clear(); }
-
-  // Accessor interface:
-  typedef DomSetMapType::const_iterator const_iterator;
-  typedef DomSetMapType::iterator iterator;
-  inline const_iterator begin() const { return Doms.begin(); }
-  inline   iterator begin()   { return Doms.begin(); }
-  inline const_iterator end()   const { return Doms.end(); }
-  inline   iterator end() { return Doms.end(); }
-  inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
-  inline   iterator find(BasicBlock* B)   { return Doms.find(B); }
-
-
-  /// getDominators - Return the set of basic blocks that dominate the 
specified
-  /// block.
-  ///
-  inline const DomSetType getDominators(BasicBlock *BB) const {
-const_iterator I = find(BB);
-assert(I != end()  BB not in function!);
-return I-second;
-  }
-
-  /// isReachable - Return true if the specified basicblock is reachable.  If
-  /// the block is reachable, we have dominator set information for it.
-  ///
-  bool isReachable(BasicBlock *BB) const {
-return !getDominators(BB).empty();
-  }
-
-  /// dominates - Return true if A dominates B.
-  ///
-  inline bool dominates(BasicBlock *A, BasicBlock *B) const {
-return getDominators(B).count(A) != 0;
-  }
-
-  /// properlyDominates - Return true if A dominates B and A != B.
-  ///
-  bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
-return dominates(A, B)  A != B;
-  }
-
-  /// print - Convert to human readable form
-  ///
-  virtual void print(std::ostream OS, const Module* = 0) const;
-  void print(std::ostream *OS, const Module* M = 0) const {
-if (OS) print(*OS, M);
-  }
-
-  /// dominates - Return true if A dominates B.  This performs the special
-  /// checks necessary if A and B are in the same basic block.
-  ///
-  bool dominates(Instruction *A, Instruction *B) const;
-
-  
//======//
-  // API to update (Post)DominatorSet information based on modifications to
-  // the CFG...
-
-  /// addBasicBlock - Call to update the dominator set with information about a
-  /// new block that was inserted into the function.
-  ///
-  void addBasicBlock(BasicBlock *BB, const DomSetType Dominators) {
-assert(find(BB) == end()  Block already in DominatorSet!);
-Doms.insert(std::make_pair(BB, Dominators));
-  }
-
-  /// addDominator - If a new block is inserted into the CFG, then method may 
be
-  /// called to notify the blocks it dominates that it is in their set.
-  ///
-  void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
-iterator I = find(BB);
-assert(I != end()  BB is not in DominatorSet!);
-

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.67 - 1.68
---
Log message:

Cleanup some from my DomSet-removal changes.  Add a new 
isReachableFromEntry
test to ETForest to factor a common test out of code.


---
Diffs of the changes:  (+8 -1)

 Dominators.h |9 -
 1 files changed, 8 insertions(+), 1 deletion(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.67 
llvm/include/llvm/Analysis/Dominators.h:1.68
--- llvm/include/llvm/Analysis/Dominators.h:1.67Sun Apr  8 16:30:05 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sun Apr  8 19:52:49 2007
@@ -27,6 +27,7 @@
 #define LLVM_ANALYSIS_DOMINATORS_H
 
 #include llvm/Analysis/ET-Forest.h
+#include llvm/Function.h
 #include llvm/Pass.h
 #include set
 
@@ -395,7 +396,7 @@
 }
   }
 
-  // dominates - Return true if A dominates B. THis performs the
+  // dominates - Return true if A dominates B. This performs the
   // special checks necessary if A and B are in the same basic block.
   bool dominates(Instruction *A, Instruction *B);
 
@@ -405,6 +406,12 @@
 return dominates(A, B)  A != B;
   }
 
+  /// isReachableFromEntry - Return true if A is dominated by the entry
+  /// block of the function containing it.
+  bool isReachableFromEntry(BasicBlock* A) {
+return dominates(A-getParent()-getEntryBlock(), A);
+  }
+  
   /// Return the nearest common dominator of A and B.
   BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const  {
 ETNode *NodeA = getNode(A);



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Re: [llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

 --- llvm/include/llvm/Analysis/Dominators.h:1.67  Sun Apr  8  
 16:30:05 2007
 +++ llvm/include/llvm/Analysis/Dominators.h   Sun Apr  8 19:52:49 2007
 @@ -27,6 +27,7 @@
  #define LLVM_ANALYSIS_DOMINATORS_H

  #include llvm/Analysis/ET-Forest.h
 +#include llvm/Function.h
  #include llvm/Pass.h
  #include set

Please move the method out-of-line so that you can avoid this #include.


 +  bool isReachableFromEntry(BasicBlock* A) {

This should be const.

-Chris

 +return dominates(A-getParent()-getEntryBlock(), A);
 +  }
 +
/// Return the nearest common dominator of A and B.
BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B)  
 const  {
  ETNode *NodeA = getNode(A);



 ___
 llvm-commits mailing list
 llvm-commits@cs.uiuc.edu
 http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.68 - 1.69
---
Log message:

Move isReachableFromEntry out of line to avoid an unnecessary #include


---
Diffs of the changes:  (+1 -4)

 Dominators.h |5 +
 1 files changed, 1 insertion(+), 4 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.68 
llvm/include/llvm/Analysis/Dominators.h:1.69
--- llvm/include/llvm/Analysis/Dominators.h:1.68Sun Apr  8 19:52:49 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sun Apr  8 23:07:36 2007
@@ -27,7 +27,6 @@
 #define LLVM_ANALYSIS_DOMINATORS_H
 
 #include llvm/Analysis/ET-Forest.h
-#include llvm/Function.h
 #include llvm/Pass.h
 #include set
 
@@ -408,9 +407,7 @@
 
   /// isReachableFromEntry - Return true if A is dominated by the entry
   /// block of the function containing it.
-  bool isReachableFromEntry(BasicBlock* A) {
-return dominates(A-getParent()-getEntryBlock(), A);
-  }
+  const bool isReachableFromEntry(BasicBlock* A);
   
   /// Return the nearest common dominator of A and B.
   BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const  {



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h PostDominators.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.64 - 1.65
PostDominators.h updated: 1.14 - 1.15
---
Log message:

Completely purge DomSet.  This is the (hopefully) final patch for PR1171: 
http://llvm.org/PR1171 .


---
Diffs of the changes:  (+1 -149)

 Dominators.h |  127 ---
 PostDominators.h |   23 -
 2 files changed, 1 insertion(+), 149 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.64 
llvm/include/llvm/Analysis/Dominators.h:1.65
--- llvm/include/llvm/Analysis/Dominators.h:1.64Tue Mar 20 15:19:48 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sat Apr  7 02:17:27 2007
@@ -10,8 +10,7 @@
 // This file defines the following classes:
 //  1. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
 // and their immediate dominator.
-//  2. DominatorSet: Calculates the [reverse] dominator set for a function
-//  3. DominatorTree: Represent the ImmediateDominator as an explicit tree
+//  2. DominatorTree: Represent the ImmediateDominator as an explicit tree
 // structure.
 //  4. ETForest: Efficient data structure for dominance comparisons and 
 // nearest-common-ancestor queries.
@@ -175,127 +174,6 @@
   void Link(BasicBlock *V, BasicBlock *W, InfoRec WInfo);
 };
 
-
-
-//===--===//
-/// DominatorSet - Maintain a setBasicBlock* for every basic block in a
-/// function, that represents the blocks that dominate the block.  If the block
-/// is unreachable in this function, the set will be empty.  This cannot happen
-/// for reachable code, because every block dominates at least itself.
-///
-class DominatorSetBase : public DominatorBase {
-public:
-  typedef std::setBasicBlock* DomSetType;// Dom set for a bb
-  // Map of dom sets
-  typedef std::mapBasicBlock*, DomSetType DomSetMapType;
-protected:
-  DomSetMapType Doms;
-public:
-  DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
-
-  virtual void releaseMemory() { Doms.clear(); }
-
-  // Accessor interface:
-  typedef DomSetMapType::const_iterator const_iterator;
-  typedef DomSetMapType::iterator iterator;
-  inline const_iterator begin() const { return Doms.begin(); }
-  inline   iterator begin()   { return Doms.begin(); }
-  inline const_iterator end()   const { return Doms.end(); }
-  inline   iterator end() { return Doms.end(); }
-  inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
-  inline   iterator find(BasicBlock* B)   { return Doms.find(B); }
-
-
-  /// getDominators - Return the set of basic blocks that dominate the 
specified
-  /// block.
-  ///
-  inline const DomSetType getDominators(BasicBlock *BB) const {
-const_iterator I = find(BB);
-assert(I != end()  BB not in function!);
-return I-second;
-  }
-
-  /// isReachable - Return true if the specified basicblock is reachable.  If
-  /// the block is reachable, we have dominator set information for it.
-  ///
-  bool isReachable(BasicBlock *BB) const {
-return !getDominators(BB).empty();
-  }
-
-  /// dominates - Return true if A dominates B.
-  ///
-  inline bool dominates(BasicBlock *A, BasicBlock *B) const {
-return getDominators(B).count(A) != 0;
-  }
-
-  /// properlyDominates - Return true if A dominates B and A != B.
-  ///
-  bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
-return dominates(A, B)  A != B;
-  }
-
-  /// print - Convert to human readable form
-  ///
-  virtual void print(std::ostream OS, const Module* = 0) const;
-  void print(std::ostream *OS, const Module* M = 0) const {
-if (OS) print(*OS, M);
-  }
-
-  /// dominates - Return true if A dominates B.  This performs the special
-  /// checks necessary if A and B are in the same basic block.
-  ///
-  bool dominates(Instruction *A, Instruction *B) const;
-
-  
//======//
-  // API to update (Post)DominatorSet information based on modifications to
-  // the CFG...
-
-  /// addBasicBlock - Call to update the dominator set with information about a
-  /// new block that was inserted into the function.
-  ///
-  void addBasicBlock(BasicBlock *BB, const DomSetType Dominators) {
-assert(find(BB) == end()  Block already in DominatorSet!);
-Doms.insert(std::make_pair(BB, Dominators));
-  }
-
-  /// addDominator - If a new block is inserted into the CFG, then method may 
be
-  /// called to notify the blocks it dominates that it is in their set.
-  ///
-  void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
-iterator I = find(BB);
-assert(I != end()  BB is not in DominatorSet!);
-I-second.insert(NewDominator);
-  }
-};
-
-
-//===-
-/// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
-/// compute a 

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Owen Anderson]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.65 - 1.66
---
Log message:

Add DomSet back, and revert the changes to LoopSimplify.  Apparently the 
ETForest updating mechanisms don't work as I thought they did.  These changes
will be reapplied once the issue is worked out.


---
Diffs of the changes:  (+126 -1)

 Dominators.h |  127 ++-
 1 files changed, 126 insertions(+), 1 deletion(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.65 
llvm/include/llvm/Analysis/Dominators.h:1.66
--- llvm/include/llvm/Analysis/Dominators.h:1.65Sat Apr  7 02:17:27 2007
+++ llvm/include/llvm/Analysis/Dominators.h Sat Apr  7 13:23:27 2007
@@ -10,7 +10,8 @@
 // This file defines the following classes:
 //  1. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
 // and their immediate dominator.
-//  2. DominatorTree: Represent the ImmediateDominator as an explicit tree
+//  2. DominatorSet: Calculates the [reverse] dominator set for a function
+//  3. DominatorTree: Represent the ImmediateDominator as an explicit tree
 // structure.
 //  4. ETForest: Efficient data structure for dominance comparisons and 
 // nearest-common-ancestor queries.
@@ -174,6 +175,127 @@
   void Link(BasicBlock *V, BasicBlock *W, InfoRec WInfo);
 };
 
+
+
+//===--===//
+/// DominatorSet - Maintain a setBasicBlock* for every basic block in a
+/// function, that represents the blocks that dominate the block.  If the block
+/// is unreachable in this function, the set will be empty.  This cannot happen
+/// for reachable code, because every block dominates at least itself.
+///
+class DominatorSetBase : public DominatorBase {
+public:
+  typedef std::setBasicBlock* DomSetType;// Dom set for a bb
+  // Map of dom sets
+  typedef std::mapBasicBlock*, DomSetType DomSetMapType;
+protected:
+  DomSetMapType Doms;
+public:
+  DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
+
+  virtual void releaseMemory() { Doms.clear(); }
+
+  // Accessor interface:
+  typedef DomSetMapType::const_iterator const_iterator;
+  typedef DomSetMapType::iterator iterator;
+  inline const_iterator begin() const { return Doms.begin(); }
+  inline   iterator begin()   { return Doms.begin(); }
+  inline const_iterator end()   const { return Doms.end(); }
+  inline   iterator end() { return Doms.end(); }
+  inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
+  inline   iterator find(BasicBlock* B)   { return Doms.find(B); }
+
+
+  /// getDominators - Return the set of basic blocks that dominate the 
specified
+  /// block.
+  ///
+  inline const DomSetType getDominators(BasicBlock *BB) const {
+const_iterator I = find(BB);
+assert(I != end()  BB not in function!);
+return I-second;
+  }
+
+  /// isReachable - Return true if the specified basicblock is reachable.  If
+  /// the block is reachable, we have dominator set information for it.
+  ///
+  bool isReachable(BasicBlock *BB) const {
+return !getDominators(BB).empty();
+  }
+
+  /// dominates - Return true if A dominates B.
+  ///
+  inline bool dominates(BasicBlock *A, BasicBlock *B) const {
+return getDominators(B).count(A) != 0;
+  }
+
+  /// properlyDominates - Return true if A dominates B and A != B.
+  ///
+  bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
+return dominates(A, B)  A != B;
+  }
+
+  /// print - Convert to human readable form
+  ///
+  virtual void print(std::ostream OS, const Module* = 0) const;
+  void print(std::ostream *OS, const Module* M = 0) const {
+if (OS) print(*OS, M);
+  }
+
+  /// dominates - Return true if A dominates B.  This performs the special
+  /// checks necessary if A and B are in the same basic block.
+  ///
+  bool dominates(Instruction *A, Instruction *B) const;
+
+  
//======//
+  // API to update (Post)DominatorSet information based on modifications to
+  // the CFG...
+
+  /// addBasicBlock - Call to update the dominator set with information about a
+  /// new block that was inserted into the function.
+  ///
+  void addBasicBlock(BasicBlock *BB, const DomSetType Dominators) {
+assert(find(BB) == end()  Block already in DominatorSet!);
+Doms.insert(std::make_pair(BB, Dominators));
+  }
+
+  /// addDominator - If a new block is inserted into the CFG, then method may 
be
+  /// called to notify the blocks it dominates that it is in their set.
+  ///
+  void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
+iterator I = find(BB);
+assert(I != end()  BB is not in DominatorSet!);
+I-second.insert(NewDominator);
+  }
+};
+
+
+//===-
+/// DominatorSet Class - Concrete subclass of DominatorSetBase that is 

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Devang Patel]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.63 - 1.64
---
Log message:


LoopSimplify::FindPHIToPartitionLoops()
Use ETForest instead of DominatorSet.



---
Diffs of the changes:  (+4 -0)

 Dominators.h |4 
 1 files changed, 4 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.63 
llvm/include/llvm/Analysis/Dominators.h:1.64
--- llvm/include/llvm/Analysis/Dominators.h:1.63Sat Dec 16 23:15:12 2006
+++ llvm/include/llvm/Analysis/Dominators.h Tue Mar 20 15:19:48 2007
@@ -516,6 +516,10 @@
 }
   }
 
+  // dominates - Return true if A dominates B. THis performs the
+  // special checks necessary if A and B are in the same basic block.
+  bool dominates(Instruction *A, Instruction *B);
+
   /// properlyDominates - Return true if A dominates B and A != B.
   ///
   bool properlyDominates(BasicBlock *A, BasicBlock *B) {



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h LoopInfo.h

[Jeff Cohen]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.61 - 1.62
LoopInfo.h updated: 1.59 - 1.60
---
Log message:

Unbreak VC++ build.

---
Diffs of the changes:  (+3 -3)

 Dominators.h |4 ++--
 LoopInfo.h   |2 +-
 2 files changed, 3 insertions(+), 3 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.61 
llvm/include/llvm/Analysis/Dominators.h:1.62
--- llvm/include/llvm/Analysis/Dominators.h:1.61Tue Oct  3 00:24:56 2006
+++ llvm/include/llvm/Analysis/Dominators.h Sun Nov  5 13:31:28 2006
@@ -304,9 +304,9 @@
   Node *RootNode;
 public:
   class Node {
-friend struct DominatorTree;
+friend class DominatorTree;
 friend struct PostDominatorTree;
-friend struct DominatorTreeBase;
+friend class DominatorTreeBase;
 BasicBlock *TheBB;
 Node *IDom;
 std::vectorNode* Children;


Index: llvm/include/llvm/Analysis/LoopInfo.h
diff -u llvm/include/llvm/Analysis/LoopInfo.h:1.59 
llvm/include/llvm/Analysis/LoopInfo.h:1.60
--- llvm/include/llvm/Analysis/LoopInfo.h:1.59  Fri Oct 27 20:24:05 2006
+++ llvm/include/llvm/Analysis/LoopInfo.h   Sun Nov  5 13:31:28 2006
@@ -35,7 +35,7 @@
 
 namespace llvm {
 
-struct ETForest;
+class ETForest;
 class LoopInfo;
 class PHINode;
 class Instruction;



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.60 - 1.61
---
Log message:

Move DominatorTree to immediately follow DominatorTreeBase


---
Diffs of the changes:  (+56 -56)

 Dominators.h |  112 +--
 1 files changed, 56 insertions(+), 56 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.60 
llvm/include/llvm/Analysis/Dominators.h:1.61
--- llvm/include/llvm/Analysis/Dominators.h:1.60Mon Sep 11 19:18:28 2006
+++ llvm/include/llvm/Analysis/Dominators.h Tue Oct  3 00:24:56 2006
@@ -412,6 +412,62 @@
   virtual void print(std::ostream OS, const Module* = 0) const;
 };
 
+//===-
+/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used 
to
+/// compute a normal dominator tree.
+///
+class DominatorTree : public DominatorTreeBase {
+public:
+  DominatorTree() : DominatorTreeBase(false) {}
+  
+  BasicBlock *getRoot() const {
+assert(Roots.size() == 1  Should always have entry node!);
+return Roots[0];
+  }
+  
+  virtual bool runOnFunction(Function F) {
+reset(); // Reset from the last time we were run...
+ImmediateDominators ID = getAnalysisImmediateDominators();
+Roots = ID.getRoots();
+calculate(ID);
+return false;
+  }
+  
+  virtual void getAnalysisUsage(AnalysisUsage AU) const {
+AU.setPreservesAll();
+AU.addRequiredImmediateDominators();
+  }
+private:
+  void calculate(const ImmediateDominators ID);
+  Node *getNodeForBlock(BasicBlock *BB);
+};
+
+//===-
+/// DominatorTree GraphTraits specialization so the DominatorTree can be
+/// iterable by generic graph iterators.
+///
+template  struct GraphTraitsDominatorTree::Node* {
+  typedef DominatorTree::Node NodeType;
+  typedef NodeType::iterator  ChildIteratorType;
+  
+  static NodeType *getEntryNode(NodeType *N) {
+return N;
+  }
+  static inline ChildIteratorType child_begin(NodeType* N) {
+return N-begin();
+  }
+  static inline ChildIteratorType child_end(NodeType* N) {
+return N-end();
+  }
+};
+
+template  struct GraphTraitsDominatorTree*
+  : public GraphTraitsDominatorTree::Node* {
+  static NodeType *getEntryNode(DominatorTree *DT) {
+return DT-getRootNode();
+  }
+};
+
 
 //===-
 /// ET-Forest Class - Class used to construct forwards and backwards 
@@ -535,62 +591,6 @@
   ETNode *getNodeForBlock(BasicBlock *BB);
 };
 
-//===-
-/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used 
to
-/// compute a normal dominator tree.
-///
-class DominatorTree : public DominatorTreeBase {
-public:
-  DominatorTree() : DominatorTreeBase(false) {}
-
-  BasicBlock *getRoot() const {
-assert(Roots.size() == 1  Should always have entry node!);
-return Roots[0];
-  }
-
-  virtual bool runOnFunction(Function F) {
-reset(); // Reset from the last time we were run...
-ImmediateDominators ID = getAnalysisImmediateDominators();
-Roots = ID.getRoots();
-calculate(ID);
-return false;
-  }
-
-  virtual void getAnalysisUsage(AnalysisUsage AU) const {
-AU.setPreservesAll();
-AU.addRequiredImmediateDominators();
-  }
-private:
-  void calculate(const ImmediateDominators ID);
-  Node *getNodeForBlock(BasicBlock *BB);
-};
-
-//===-
-/// DominatorTree GraphTraits specialization so the DominatorTree can be
-/// iterable by generic graph iterators.
-///
-template  struct GraphTraitsDominatorTree::Node* {
-  typedef DominatorTree::Node NodeType;
-  typedef NodeType::iterator  ChildIteratorType;
-
-  static NodeType *getEntryNode(NodeType *N) {
-return N;
-  }
-  static inline ChildIteratorType child_begin(NodeType* N) {
-return N-begin();
-  }
-  static inline ChildIteratorType child_end(NodeType* N) {
-return N-end();
-  }
-};
-
-template  struct GraphTraitsDominatorTree*
-  : public GraphTraitsDominatorTree::Node* {
-  static NodeType *getEntryNode(DominatorTree *DT) {
-return DT-getRootNode();
-  }
-};
-
 
//===--===//
 /// DominanceFrontierBase - Common base class for computing forward and inverse
 /// dominance frontiers for a function.



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Nick Lewycky]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.59 - 1.60
---
Log message:

Add ability to remove nodes from DominatorTree, for when a BasicBlock
is being removed.


---
Diffs of the changes:  (+8 -0)

 Dominators.h |8 
 1 files changed, 8 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.59 
llvm/include/llvm/Analysis/Dominators.h:1.60
--- llvm/include/llvm/Analysis/Dominators.h:1.59Tue Aug  1 17:24:38 2006
+++ llvm/include/llvm/Analysis/Dominators.h Mon Sep 11 19:18:28 2006
@@ -399,6 +399,14 @@
 N-setIDom(NewIDom);
   }
 
+  /// removeNode - Removes a node from the dominator tree.  Block must not
+  /// dominate any other blocks.  Invalidates any node pointing to removed
+  /// block.
+  void removeNode(BasicBlock *BB) {
+assert(getNode(BB)  Removing node that isn't in dominator tree.);
+Nodes.erase(BB);
+  }
+
   /// print - Convert to human readable form
   ///
   virtual void print(std::ostream OS, const Module* = 0) const;



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.58 - 1.59
---
Log message:

Add dominates/properlyDominates queries to IDom.


---
Diffs of the changes:  (+10 -0)

 Dominators.h |   10 ++
 1 files changed, 10 insertions(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.58 
llvm/include/llvm/Analysis/Dominators.h:1.59
--- llvm/include/llvm/Analysis/Dominators.h:1.58Wed Jun  7 17:00:25 2006
+++ llvm/include/llvm/Analysis/Dominators.h Tue Aug  1 17:24:38 2006
@@ -101,7 +101,17 @@
   inline BasicBlock *operator[](BasicBlock *BB) const {
 return get(BB);
   }
+  
+  /// dominates - Return true if A dominates B.
+  ///
+  bool dominates(BasicBlock *A, BasicBlock *B) const;
 
+  /// properlyDominates - Return true if A dominates B and A != B.
+  ///
+  bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
+return A != B || properlyDominates(A, B);
+  }
+  
   /// get() - Synonym for operator[].
   ///
   inline BasicBlock *get(BasicBlock *BB) const {



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.55 - 1.56
---
Log message:

Fix pastos in comments


---
Diffs of the changes:  (+4 -3)

 Dominators.h |7 ---
 1 files changed, 4 insertions(+), 3 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.55 
llvm/include/llvm/Analysis/Dominators.h:1.56
--- llvm/include/llvm/Analysis/Dominators.h:1.55Fri May 19 12:17:12 2006
+++ llvm/include/llvm/Analysis/Dominators.h Sat May 27 01:57:55 2006
@@ -574,7 +574,8 @@
 };
 
 
//===--===//
-/// DominanceFrontier - Calculate the dominance frontiers for a function.
+/// DominanceFrontierBase - Common base class for computing forward and inverse
+/// dominance frontiers for a function.
 ///
 class DominanceFrontierBase : public DominatorBase {
 public:
@@ -620,8 +621,8 @@
 
 
 //===-
-/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used 
to
-/// compute a normal dominator tree.
+/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that 
is
+/// used to compute a forward dominator frontiers.
 ///
 class DominanceFrontier : public DominanceFrontierBase {
 public:



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.54 - 1.55
---
Log message:

Use class tags instead of struct tags.  The coding standards specify this
for public classes for improved win32 compatibility.


---
Diffs of the changes:  (+18 -9)

 Dominators.h |   27 ++-
 1 files changed, 18 insertions(+), 9 deletions(-)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.54 
llvm/include/llvm/Analysis/Dominators.h:1.55
--- llvm/include/llvm/Analysis/Dominators.h:1.54Mon Mar 20 13:32:48 2006
+++ llvm/include/llvm/Analysis/Dominators.h Fri May 19 12:17:12 2006
@@ -140,7 +140,8 @@
 /// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase
 /// that is used to compute a normal immediate dominator set.
 ///
-struct ImmediateDominators : public ImmediateDominatorsBase {
+class ImmediateDominators : public ImmediateDominatorsBase {
+public:
   ImmediateDominators() : ImmediateDominatorsBase(false) {}
 
   BasicBlock *getRoot() const {
@@ -169,7 +170,8 @@
 /// is unreachable in this function, the set will be empty.  This cannot happen
 /// for reachable code, because every block dominates at least itself.
 ///
-struct DominatorSetBase : public DominatorBase {
+class DominatorSetBase : public DominatorBase {
+public:
   typedef std::setBasicBlock* DomSetType;// Dom set for a bb
   // Map of dom sets
   typedef std::mapBasicBlock*, DomSetType DomSetMapType;
@@ -255,7 +257,8 @@
 /// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
 /// compute a normal dominator set.
 ///
-struct DominatorSet : public DominatorSetBase {
+class DominatorSet : public DominatorSetBase {
+public:
   DominatorSet() : DominatorSetBase(false) {}
 
   virtual bool runOnFunction(Function F);
@@ -280,7 +283,8 @@
 
//===--===//
 /// DominatorTree - Calculate the immediate dominator tree for a function.
 ///
-struct DominatorTreeBase : public DominatorBase {
+class DominatorTreeBase : public DominatorBase {
+public:
   class Node;
 protected:
   std::mapBasicBlock*, Node* Nodes;
@@ -395,7 +399,8 @@
 /// ET-Forest Class - Class used to construct forwards and backwards 
 /// ET-Forests
 ///
-struct ETForestBase : public DominatorBase {
+class ETForestBase : public DominatorBase {
+public:
   ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(), 
  DFSInfoValid(false), SlowQueries(0) {}
   
@@ -491,7 +496,8 @@
 /// ETForest Class - Concrete subclass of ETForestBase that is used to
 /// compute a forwards ET-Forest.
 
-struct ETForest : public ETForestBase {
+class ETForest : public ETForestBase {
+public:
   ETForest() : ETForestBase(false) {}
 
   BasicBlock *getRoot() const {
@@ -515,7 +521,8 @@
 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used 
to
 /// compute a normal dominator tree.
 ///
-struct DominatorTree : public DominatorTreeBase {
+class DominatorTree : public DominatorTreeBase {
+public:
   DominatorTree() : DominatorTreeBase(false) {}
 
   BasicBlock *getRoot() const {
@@ -569,7 +576,8 @@
 
//===--===//
 /// DominanceFrontier - Calculate the dominance frontiers for a function.
 ///
-struct DominanceFrontierBase : public DominatorBase {
+class DominanceFrontierBase : public DominatorBase {
+public:
   typedef std::setBasicBlock* DomSetType;// Dom set for a bb
   typedef std::mapBasicBlock*, DomSetType DomSetMapType; // Dom set map
 protected:
@@ -615,7 +623,8 @@
 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used 
to
 /// compute a normal dominator tree.
 ///
-struct DominanceFrontier : public DominanceFrontierBase {
+class DominanceFrontier : public DominanceFrontierBase {
+public:
   DominanceFrontier() : DominanceFrontierBase(false) {}
 
   BasicBlock *getRoot() const {



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/include/llvm/Analysis/Dominators.h

[Chris Lattner]

Changes in directory llvm/include/llvm/Analysis:

Dominators.h updated: 1.50 - 1.51
---
Log message:

Fix PR670: http://llvm.cs.uiuc.edu/PR670  and 
test/Regression/Transforms/Mem2Reg/2005-11-28-Crash.ll


---
Diffs of the changes:  (+1 -0)

 Dominators.h |1 +
 1 files changed, 1 insertion(+)


Index: llvm/include/llvm/Analysis/Dominators.h
diff -u llvm/include/llvm/Analysis/Dominators.h:1.50 
llvm/include/llvm/Analysis/Dominators.h:1.51
--- llvm/include/llvm/Analysis/Dominators.h:1.50Fri Nov 18 01:27:33 2005
+++ llvm/include/llvm/Analysis/Dominators.h Mon Nov 28 19:07:12 2005
@@ -311,6 +311,7 @@
 ///
 bool properlyDominates(const Node *N) const {
   const Node *IDom;
+  if (this == 0 || N == 0) return false;
   while ((IDom = N-getIDom()) != 0  IDom != this)
 N = IDom;   // Walk up the tree
   return IDom != 0;



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits