Vendor import of llvm trunk r154661:

http://llvm.org/svn/llvm-project/llvm/trunk@r154661

1 files changed, 80 insertions, 52 deletions

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 230e83d..6e8e4246 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -185,6 +185,18 @@ void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
 
 template<class NodeT>
 class DominatorTreeBase : public DominatorBase<NodeT> {
+  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
+                               const DomTreeNodeBase<NodeT> *B) const {
+    assert(A != B);
+    assert(isReachableFromEntry(B));
+    assert(isReachableFromEntry(A));
+
+    const DomTreeNodeBase<NodeT> *IDom;
+    while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
+      B = IDom;   // Walk up the tree
+    return IDom != 0;
+  }
+
 protected:
   typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
   DomTreeNodeMapType DomTreeNodes;
@@ -321,8 +333,7 @@ public:
   /// block.  This is the same as using operator[] on this class.
   ///
   inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
-    typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
-    return I != DomTreeNodes.end() ? I->second : 0;
+    return DomTreeNodes.lookup(BB);
   }
 
   /// getRootNode - This returns the entry node for the CFG of the function.  If
@@ -339,38 +350,26 @@ public:
   /// Note that this is not a constant time operation!
   ///
   bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
-                         const DomTreeNodeBase<NodeT> *B) const {
-    if (A == 0 || B == 0) return false;
-    return dominatedBySlowTreeWalk(A, B);
-  }
-
-  inline bool properlyDominates(const NodeT *A, const NodeT *B) {
+                         const DomTreeNodeBase<NodeT> *B) {
+    if (A == 0 || B == 0)
+      return false;
     if (A == B)
       return false;
-
-    // Cast away the const qualifiers here. This is ok since
-    // this function doesn't actually return the values returned
-    // from getNode.
-    return properlyDominates(getNode(const_cast<NodeT *>(A)),
-                             getNode(const_cast<NodeT *>(B)));
-  }
-
-  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
-                               const DomTreeNodeBase<NodeT> *B) const {
-    const DomTreeNodeBase<NodeT> *IDom;
-    if (A == 0 || B == 0) return false;
-    while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
-      B = IDom;   // Walk up the tree
-    return IDom != 0;
+    return dominates(A, B);
   }
 
+  bool properlyDominates(const NodeT *A, const NodeT *B);
 
   /// isReachableFromEntry - Return true if A is dominated by the entry
   /// block of the function containing it.
-  bool isReachableFromEntry(const NodeT* A) {
+  bool isReachableFromEntry(const NodeT* A) const {
     assert(!this->isPostDominator() &&
            "This is not implemented for post dominators");
-    return dominates(&A->getParent()->front(), A);
+    return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
+  }
+
+  inline bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const {
+    return A;
   }
 
   /// dominates - Returns true iff A dominates B.  Note that this is not a
@@ -378,10 +377,16 @@ public:
   ///
   inline bool dominates(const DomTreeNodeBase<NodeT> *A,
                         const DomTreeNodeBase<NodeT> *B) {
+    // A node trivially dominates itself.
     if (B == A)
-      return true;  // A node trivially dominates itself.
+      return true;
 
-    if (A == 0 || B == 0)
+    // An unreachable node is dominated by anything.
+    if (!isReachableFromEntry(B))
+      return true;
+
+    // And dominates nothing.
+    if (!isReachableFromEntry(A))
       return false;
 
     // Compare the result of the tree walk and the dfs numbers, if expensive
@@ -406,16 +411,7 @@ public:
     return dominatedBySlowTreeWalk(A, B);
   }
 
-  inline bool dominates(const NodeT *A, const NodeT *B) {
-    if (A == B)
-      return true;
-
-    // Cast away the const qualifiers here. This is ok since
-    // this function doesn't actually return the values returned
-    // from getNode.
-    return dominates(getNode(const_cast<NodeT *>(A)),
-                     getNode(const_cast<NodeT *>(B)));
-  }
+  bool dominates(const NodeT *A, const NodeT *B);
 
   NodeT *getRoot() const {
     assert(this->Roots.size() == 1 && "Should always have entry node!");
@@ -623,9 +619,8 @@ protected:
   }
 
   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
-    typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.find(BB);
-    if (I != this->DomTreeNodes.end() && I->second)
-      return I->second;
+    if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
+      return Node;
 
     // Haven't calculated this node yet?  Get or calculate the node for the
     // immediate dominator.
@@ -641,8 +636,7 @@ protected:
   }
 
   inline NodeT *getIDom(NodeT *BB) const {
-    typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB);
-    return I != IDoms.end() ? I->second : 0;
+    return IDoms.lookup(BB);
   }
 
   inline void addRoot(NodeT* BB) {
@@ -653,21 +647,24 @@ public:
   /// recalculate - compute a dominator tree for the given function
   template<class FT>
   void recalculate(FT& F) {
+    typedef GraphTraits<FT*> TraitsTy;
     reset();
     this->Vertex.push_back(0);
 
     if (!this->IsPostDominators) {
       // Initialize root
-      this->Roots.push_back(&F.front());
-      this->IDoms[&F.front()] = 0;
-      this->DomTreeNodes[&F.front()] = 0;
+      NodeT *entry = TraitsTy::getEntryNode(&F);
+      this->Roots.push_back(entry);
+      this->IDoms[entry] = 0;
+      this->DomTreeNodes[entry] = 0;
 
       Calculate<FT, NodeT*>(*this, F);
     } else {
       // Initialize the roots list
-      for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {
-        if (std::distance(GraphTraits<FT*>::child_begin(I),
-                          GraphTraits<FT*>::child_end(I)) == 0)
+      for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F),
+                                        E = TraitsTy::nodes_end(&F); I != E; ++I) {
+        if (std::distance(TraitsTy::child_begin(I),
+                          TraitsTy::child_end(I)) == 0)
           addRoot(I);
 
         // Prepopulate maps so that we don't get iterator invalidation issues later.
@@ -680,6 +677,32 @@ public:
   }
 };
 
+// These two functions are declared out of line as a workaround for building
+// with old (< r147295) versions of clang because of pr11642.
+template<class NodeT>
+bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) {
+  if (A == B)
+    return true;
+
+  // Cast away the const qualifiers here. This is ok since
+  // this function doesn't actually return the values returned
+  // from getNode.
+  return dominates(getNode(const_cast<NodeT *>(A)),
+                   getNode(const_cast<NodeT *>(B)));
+}
+template<class NodeT>
+bool
+DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, const NodeT *B) {
+  if (A == B)
+    return false;
+
+  // Cast away the const qualifiers here. This is ok since
+  // this function doesn't actually return the values returned
+  // from getNode.
+  return dominates(getNode(const_cast<NodeT *>(A)),
+                   getNode(const_cast<NodeT *>(B)));
+}
+
 EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
 
 //===-------------------------------------
@@ -749,9 +772,12 @@ public:
     return DT->dominates(A, 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(const Instruction *A, const Instruction *B) const;
+  // dominates - Return true if Def dominates a use in User. This performs
+  // the special checks necessary if Def and User are in the same basic block.
+  // Note that Def doesn't dominate a use in Def itself!
+  bool dominates(const Instruction *Def, const Use &U) const;
+  bool dominates(const Instruction *Def, const Instruction *User) const;
+  bool dominates(const Instruction *Def, const BasicBlock *BB) const;
 
   bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const {
     return DT->properlyDominates(A, B);
@@ -814,10 +840,12 @@ public:
     DT->splitBlock(NewBB);
   }
 
-  bool isReachableFromEntry(const BasicBlock* A) {
+  bool isReachableFromEntry(const BasicBlock* A) const {
     return DT->isReachableFromEntry(A);
   }
 
+  bool isReachableFromEntry(const Use &U) const;
+
 
   virtual void releaseMemory() {
     DT->releaseMemory();