The TargetData is not used for the isPowerOfTwo determination. It has never

[oota-llvm.git] / include / llvm / Analysis / DominatorInternals.h

diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h
index 7d15fc4ad36415c7449850f20da78ea674ca3d93..c0f95cbd9b9b698a33adbc196526e3877e6d549b 100644 (file)
--- a/include/llvm/Analysis/DominatorInternals.h
+++ b/include/llvm/Analysis/DominatorInternals.h
@@ -10,8 +10,8 @@
 #ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
 #define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
 
-#include "llvm/Analysis/Dominators.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Analysis/Dominators.h"
 
 //===----------------------------------------------------------------------===//
 //
@@ -42,9 +42,6 @@ unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
   VInfo.Label = V;
 
   Vertex.push_back(V);        // Vertex[n] = V;
-  //Info[V].Ancestor = 0;     // Ancestor[n] = 0
-  //Info[V].Child = 0;        // Child[v] = 0
-  VInfo.Size = 1;             // Size[v] = 1
 
   for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
     InfoRec &SuccVInfo = DT.Info[*SI];
@@ -56,8 +53,8 @@ unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
 #else
   bool IsChildOfArtificialExit = (N != 0);
 
-  std::vector<std::pair<typename GraphT::NodeType*,
-                        typename GraphT::ChildIteratorType> > Worklist;
+  SmallVector<std::pair<typename GraphT::NodeType*,
+                        typename GraphT::ChildIteratorType>, 32> Worklist;
   Worklist.push_back(std::make_pair(V, GraphT::child_begin(V)));
   while (!Worklist.empty()) {
     typename GraphT::NodeType* BB = Worklist.back().first;
@@ -72,9 +69,6 @@ unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
       BBInfo.Label = BB;
 
       DT.Vertex.push_back(BB);       // Vertex[n] = V;
-      //BBInfo[V].Ancestor = 0;   // Ancestor[n] = 0
-      //BBInfo[V].Child = 0;      // Child[v] = 0
-      BBInfo.Size = 1;            // Size[v] = 1
 
       if (IsChildOfArtificialExit)
         BBInfo.Parent = 1;
@@ -110,53 +104,47 @@ unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
 }
 
 template<class GraphT>
-void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
-              typename GraphT::NodeType *VIn) {
+typename GraphT::NodeType* 
+Eval(DominatorTreeBase<typename GraphT::NodeType>& DT,
+     typename GraphT::NodeType *VIn, unsigned LastLinked) {
+  typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInInfo =
+                                                                  DT.Info[VIn];
+  if (VInInfo.DFSNum < LastLinked)
+    return VIn;
+
   SmallVector<typename GraphT::NodeType*, 32> Work;
   SmallPtrSet<typename GraphT::NodeType*, 32> Visited;
-  typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInVAInfo =
-                                      DT.Info[DT.Vertex[DT.Info[VIn].Ancestor]];
 
-  if (VInVAInfo.Ancestor != 0)
+  if (VInInfo.Parent >= LastLinked)
     Work.push_back(VIn);
   
   while (!Work.empty()) {
     typename GraphT::NodeType* V = Work.back();
     typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo =
                                                                      DT.Info[V];
-    typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Ancestor];
-    typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo =
-                                                             DT.Info[VAncestor];
+    typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Parent];
 
     // Process Ancestor first
-    if (Visited.insert(VAncestor) &&
-        VAInfo.Ancestor != 0) {
+    if (Visited.insert(VAncestor) && VInfo.Parent >= LastLinked) {
       Work.push_back(VAncestor);
       continue;
     } 
     Work.pop_back(); 
 
     // Update VInfo based on Ancestor info
-    if (VAInfo.Ancestor == 0)
+    if (VInfo.Parent < LastLinked)
       continue;
+
+    typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo =
+                                                             DT.Info[VAncestor];
     typename GraphT::NodeType* VAncestorLabel = VAInfo.Label;
     typename GraphT::NodeType* VLabel = VInfo.Label;
     if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi)
       VInfo.Label = VAncestorLabel;
-    VInfo.Ancestor = VAInfo.Ancestor;
+    VInfo.Parent = VAInfo.Parent;
   }
-}
 
-template<class GraphT>
-typename GraphT::NodeType* 
-Eval(DominatorTreeBase<typename GraphT::NodeType>& DT,
-     typename GraphT::NodeType *V) {
-  typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo =
-                                                                     DT.Info[V];
-  if (VInfo.Ancestor == 0)
-    return V;
-  Compress<GraphT>(DT, V);
-  return VInfo.Label;
+  return VInInfo.Label;
 }
 
 template<class FuncT, class NodeT>
@@ -173,9 +161,6 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
     BBInfo.Label = NULL;
 
     DT.Vertex.push_back(NULL);       // Vertex[n] = V;
-      //BBInfo[V].Ancestor = 0;   // Ancestor[n] = 0
-      //BBInfo[V].Child = 0;      // Child[v] = 0
-    BBInfo.Size = 1;            // Size[v] = 1
   }
 
   // Step #1: Number blocks in depth-first order and initialize variables used
@@ -186,7 +171,7 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
 
   // it might be that some blocks did not get a DFS number (e.g., blocks of 
   // infinite loops). In these cases an artificial exit node is required.
-  MultipleRoots |= (DT.isPostDominator() && N != F.size());
+  MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F));
 
   // When naively implemented, the Lengauer-Tarjan algorithm requires a separate
   // bucket for each vertex. However, this is unnecessary, because each vertex
@@ -198,7 +183,7 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
   // Buckets[i] stores the index of the first element in V's bucket. After V's
   // bucket is processed, Buckets[i] stores the index of the next element in the
   // bucket containing V, if any.
-  std::vector<unsigned> Buckets;
+  SmallVector<unsigned, 32> Buckets;
   Buckets.resize(N + 1);
   for (unsigned i = 1; i <= N; ++i)
     Buckets[i] = i;
@@ -211,7 +196,7 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
     // Step #2: Implicitly define the immediate dominator of vertices
     for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) {
       typename GraphT::NodeType* V = DT.Vertex[Buckets[j]];
-      typename GraphT::NodeType* U = Eval<GraphT>(DT, V);
+      typename GraphT::NodeType* U = Eval<GraphT>(DT, V, i + 1);
       DT.IDoms[V] = DT.Info[U].Semi < i ? U : W;
     }
 
@@ -225,7 +210,7 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
          E = InvTraits::child_end(W); CI != E; ++CI) {
       typename InvTraits::NodeType *N = *CI;
       if (DT.Info.count(N)) {  // Only if this predecessor is reachable!
-        unsigned SemiU = DT.Info[Eval<GraphT>(DT, N)].Semi;
+        unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi;
         if (SemiU < WInfo.Semi)
           WInfo.Semi = SemiU;
       }
@@ -240,9 +225,6 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
       Buckets[i] = Buckets[WInfo.Semi];
       Buckets[WInfo.Semi] = i;
     }
-
-    // Link W to its DFS tree parent.
-    WInfo.Ancestor = WInfo.Parent;
   }
 
   if (N >= 1) {