[analyzer] Rely on LLVM Dominators in Clang dominator computation.

(Previously, Clang used it's implementation of dominators.)

The patch is contributed by Guoping Long!

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

2 files changed, 286 insertions, 54 deletions

diff --git a/include/clang/Analysis/Analyses/Dominators.h b/include/clang/Analysis/Analyses/Dominators.h
index 98a9bf1222..a9b80593d1 100644
--- a/include/clang/Analysis/Analyses/Dominators.h
+++ b/include/clang/Analysis/Analyses/Dominators.h
@@ -1,4 +1,4 @@
-//==- Dominators.h - Construct the Dominance Tree Given CFG -----*- C++ --*-==//
+//==- Dominators.h - Implementation of dominators tree for Clang CFG C++ -*-==//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,74 +7,205 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements a simple, fast dominance algorithm for source-level
-// CFGs.
+// This file implements the dominators tree functionality for Clang CFGs.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_DOMINATORS_H
 #define LLVM_CLANG_DOMINATORS_H
 
-#include "clang/Analysis/CFG.h"
 #include "clang/Analysis/AnalysisContext.h"
-#include "llvm/ADT/DenseMap.h"
+
+#include "llvm/Module.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "clang/Analysis/CFG.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/DominatorInternals.h"
 
 namespace clang {
 
-class CFG;
 class CFGBlock;
+typedef llvm::DomTreeNodeBase<CFGBlock> DomTreeNode;
 
+/// \brief Concrete subclass of DominatorTreeBase for Clang
+/// This class implements the dominators tree functionality given a Clang CFG.
+///
 class DominatorTree : public ManagedAnalysis {
-  typedef llvm::DenseMap<const CFGBlock *, CFGBlock*> CFGBlockMapTy;
-
 public:
-  DominatorTree(AnalysisDeclContext &ac)
-      : AC(ac) {}
+  llvm::DominatorTreeBase<CFGBlock>* DT;
 
-  virtual ~DominatorTree();
+  DominatorTree() {
+    DT = new llvm::DominatorTreeBase<CFGBlock>(false);
+  }
 
-  /// Return the immediate dominator node given a CFGBlock.
-  /// For entry block, the dominator is itself.
-  /// This is the same as using operator[] on this class.
-  CFGBlock *getNode(const CFGBlock *B) const;
+  ~DominatorTree() {
+    delete DT;
+  }
 
-  /// This returns the Entry Block for the given CFG
-  CFGBlock *getRootNode() { return RootNode; }
-  const CFGBlock *getRootNode() const { return RootNode; }
+  llvm::DominatorTreeBase<CFGBlock>& getBase() { return *DT; }
 
-  /// Returns true iff A dominates B and A != B.
-  /// Note that this is not a constant time operation.
-  bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const;
+  /// \brief This method returns the root CFGBlock of the dominators tree.
+  ///
+  inline CFGBlock *getRoot() const {
+    return DT->getRoot();
+  }
+
+  /// \brief This method returns the root DomTreeNode, which is the wrapper
+  /// for CFGBlock.
+  inline DomTreeNode *getRootNode() const {
+    return DT->getRootNode();
+  }
+
+  /// \brief This method compares two dominator trees.
+  /// The method returns false if the other dominator tree matches this
+  /// dominator tree, otherwise returns true.
+  ///
+  inline bool compare(DominatorTree &Other) const {
+    DomTreeNode *R = getRootNode();
+    DomTreeNode *OtherR = Other.getRootNode();
 
-  /// Returns true iff A dominates B.
-  bool dominates(const CFGBlock *A, const CFGBlock *B) const;
+    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
+      return true;
 
-  /// Find nearest common dominator for blocks A and B.
-  /// Common dominator always exists, ex: entry block.
-  const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
-                                       const CFGBlock *B) const;
+    if (DT->compare(Other.getBase()))
+      return true;
 
-  /// Constructs immediate dominator tree for a given CFG based on the algorithm
-  /// described in this paper:
+    return false;
+  }
+
+  /// \brief This method builds the dominator tree for a given CFG
+  /// The CFG information is passed via AnalysisDeclContext
   ///
-  ///  A Simple, Fast Dominance Algorithm
-  ///  Keith D. Cooper, Timothy J. Harvey and Ken Kennedy
-  ///  Software-Practice and Expreience, 2001;4:1-10.
+  void buildDominatorTree(AnalysisDeclContext &AC) {
+    cfg = AC.getCFG();
+    DT->recalculate(*cfg);
+  }
+
+  /// \brief This method dumps immediate dominators for each block,
+  /// mainly used for debug purposes.
   ///
-  /// This implementation is simple and runs faster in practice than the classis
-  /// Lengauer-Tarjan algorithm. For detailed discussions, refer to the paper.
-  void BuildDominatorTree();
+  void dump() {
+    llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
+    for (CFG::const_iterator I = cfg->begin(),
+        E = cfg->end(); I != E; ++I) {
+      if(DT->getNode(*I)->getIDom())
+        llvm::errs() << "(" << (*I)->getBlockID()
+                     << ","
+                     << DT->getNode(*I)->getIDom()->getBlock()->getBlockID()
+                     << ")\n";
+      else llvm::errs() << "(" << (*I)->getBlockID()
+                        << "," << (*I)->getBlockID() << ")\n";
+    }
+  }
+
+  /// \brief This method tests if one CFGBlock dominates the other.
+  /// The method return true if A dominates B, false otherwise.
+  /// Note a block always dominates itself.
+  ///
+  inline bool dominates(const CFGBlock* A, const CFGBlock* B) const {
+    return DT->dominates(A, B);
+  }
+
+  /// \brief This method tests if one CFGBlock properly dominates the other.
+  /// The method return true if A properly dominates B, false otherwise.
+  ///
+  bool properlyDominates(const CFGBlock*A, const CFGBlock*B) const {
+    return DT->properlyDominates(A, B);
+  }
 
-  /// Dump the immediate dominance tree
-  void dump();
+  /// \brief This method finds the nearest common dominator CFG block
+  /// for CFG block A and B. If there is no such block then return NULL.
+  ///
+  inline CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
+    return DT->findNearestCommonDominator(A, B);
+  }
+
+  inline const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
+                                                      const CFGBlock *B) {
+    return DT->findNearestCommonDominator(A, B);
+  }
+
+  /// \brief This method is used to update the dominator
+  /// tree information when a node's immediate dominator changes.
+  ///
+  inline void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
+    DT->changeImmediateDominator(N, NewIDom);
+  }
+
+  /// \brief This method tests if the given CFGBlock can be reachable from root.
+  /// Returns true if reachable, false otherwise.
+  ///
+  bool isReachableFromEntry(const CFGBlock *A) {
+    return DT->isReachableFromEntry(A);
+  }
+
+  /// \brief This method releases the memory held by the dominator tree.
+  ///
+  virtual void releaseMemory() {
+    DT->releaseMemory();
+  }
+
+  /// \brief This method converts the dominator tree to human readable form.
+  ///
+  virtual void print(raw_ostream &OS, const llvm::Module* M= 0) const {
+    DT->print(OS);
+  }
 
 private:
-  AnalysisDeclContext &AC;
-  CFGBlock *RootNode;
-  CFGBlockMapTy IDoms;
+  CFG *cfg;
 };
 
+void WriteAsOperand(raw_ostream &OS, const CFGBlock *BB,
+                          bool t) {
+  OS << "BB#" << BB->getBlockID();
+}
+
 } // end namespace clang
 
-#endif
+//===-------------------------------------
+/// DominatorTree GraphTraits specialization so the DominatorTree can be
+/// iterable by generic graph iterators.
+///
+namespace llvm {
+template <> struct GraphTraits< ::clang::DomTreeNode* > {
+  typedef ::clang::DomTreeNode 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();
+  }
+
+  typedef df_iterator< ::clang::DomTreeNode* > nodes_iterator;
+
+  static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
+    return df_begin(getEntryNode(N));
+  }
+
+  static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
+    return df_end(getEntryNode(N));
+  }
+};
+
+template <> struct GraphTraits< ::clang::DominatorTree* >
+  : public GraphTraits< ::clang::DomTreeNode* > {
+  static NodeType *getEntryNode(::clang::DominatorTree *DT) {
+    return DT->getRootNode();
+  }
+
+  static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
+    return df_begin(getEntryNode(N));
+  }
 
+  static nodes_iterator nodes_end(::clang::DominatorTree *N) {
+    return df_end(getEntryNode(N));
+  }
+};
+} // end namespace llvm
+
+#endif
diff --git a/include/clang/Analysis/CFG.h b/include/clang/Analysis/CFG.h
index 66b7a6de64..ad23d42f42 100644
--- a/include/clang/Analysis/CFG.h
+++ b/include/clang/Analysis/CFG.h
@@ -344,10 +344,14 @@ class CFGBlock {
   /// storage if the memory usage of CFGBlock becomes an issue.
   unsigned HasNoReturnElement : 1;
 
+  /// Parent - The parent CFG that owns this CFGBlock.
+  CFG *Parent;
+
 public:
-  explicit CFGBlock(unsigned blockid, BumpVectorContext &C)
-    : Elements(C), Label(NULL), Terminator(NULL), LoopTarget(NULL),
-      BlockID(blockid), Preds(C, 1), Succs(C, 1), HasNoReturnElement(false) {}
+  explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent)
+    : Elements(C), Label(NULL), Terminator(NULL), LoopTarget(NULL), 
+      BlockID(blockid), Preds(C, 1), Succs(C, 1), HasNoReturnElement(false),
+      Parent(parent) {}
   ~CFGBlock() {}
 
   // Statement iterators
@@ -489,6 +493,8 @@ public:
 
   unsigned getBlockID() const { return BlockID; }
 
+  CFG *getParent() const { return Parent; }
+
   void dump(const CFG *cfg, const LangOptions &LO) const;
   void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO) const;
   void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
@@ -583,6 +589,55 @@ public:
       ,AddImplicitDtors(false) {}
   };
 
+  /// \brief Provides a custom implementation of the iterator class to have the
+  /// same interface as Function::iterator - iterator returns CFGBlock
+  /// (not a pointer to CFGBlock).
+  class graph_iterator {
+  public:
+    typedef const CFGBlock                  value_type;
+    typedef value_type&                     reference;
+    typedef value_type*                     pointer;
+    typedef BumpVector<CFGBlock*>::iterator ImplTy;
+
+    graph_iterator(const ImplTy &i) : I(i) {}
+
+    bool operator==(const graph_iterator &X) const { return I == X.I; }
+    bool operator!=(const graph_iterator &X) const { return I != X.I; }
+
+    reference operator*()    const { return **I; }
+    pointer operator->()     const { return  *I; }
+    operator CFGBlock* ()          { return  *I; }
+
+    graph_iterator &operator++() { ++I; return *this; }
+    graph_iterator &operator--() { --I; return *this; }
+
+  private:
+    ImplTy I;
+  };
+
+  class const_graph_iterator {
+  public:
+    typedef const CFGBlock                  value_type;
+    typedef value_type&                     reference;
+    typedef value_type*                     pointer;
+    typedef BumpVector<CFGBlock*>::const_iterator ImplTy;
+
+    const_graph_iterator(const ImplTy &i) : I(i) {}
+
+    bool operator==(const const_graph_iterator &X) const { return I == X.I; }
+    bool operator!=(const const_graph_iterator &X) const { return I != X.I; }
+
+    reference operator*() const { return **I; }
+    pointer operator->()  const { return  *I; }
+    operator CFGBlock* () const { return  *I; }
+
+    const_graph_iterator &operator++() { ++I; return *this; }
+    const_graph_iterator &operator--() { --I; return *this; }
+
+  private:
+    ImplTy I;
+  };
+
   /// buildCFG - Builds a CFG from an AST.  The responsibility to free the
   ///   constructed CFG belongs to the caller.
   static CFG* buildCFG(const Decl *D, Stmt *AST, ASTContext *C,
@@ -619,6 +674,15 @@ public:
   const_iterator            begin()       const    { return Blocks.begin(); }
   const_iterator            end()         const    { return Blocks.end(); }
 
+  graph_iterator nodes_begin() { return graph_iterator(Blocks.begin()); }
+  graph_iterator nodes_end() { return graph_iterator(Blocks.end()); }
+  const_graph_iterator nodes_begin() const {
+    return const_graph_iterator(Blocks.begin());
+  }
+  const_graph_iterator nodes_end() const {
+    return const_graph_iterator(Blocks.end());
+  }
+
   reverse_iterator          rbegin()               { return Blocks.rbegin(); }
   reverse_iterator          rend()                 { return Blocks.rend(); }
   const_reverse_iterator    rbegin()      const    { return Blocks.rbegin(); }
@@ -681,6 +745,11 @@ public:
   /// start at 0).
   unsigned getNumBlockIDs() const { return NumBlockIDs; }
 
+  /// size - Return the total number of CFGBlocks within the CFG
+  /// This is simply a renaming of the getNumBlockIDs(). This is necessary 
+  /// because the dominator implementation needs such an interface.
+  unsigned size() const { return NumBlockIDs; }
+
   //===--------------------------------------------------------------------===//
   // CFG Debugging: Pretty-Printing and Visualization.
   //===--------------------------------------------------------------------===//
@@ -781,6 +850,20 @@ template <> struct GraphTraits< const ::clang::CFGBlock *> {
   { return N->succ_end(); }
 };
 
+template <> struct GraphTraits<Inverse< ::clang::CFGBlock*> > {
+  typedef ::clang::CFGBlock NodeType;
+  typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(Inverse< ::clang::CFGBlock*> G)
+  { return G.Graph; }
+
+  static inline ChildIteratorType child_begin(NodeType* N)
+  { return N->pred_begin(); }
+
+  static inline ChildIteratorType child_end(NodeType* N)
+  { return N->pred_end(); }
+};
+
 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > {
   typedef const ::clang::CFGBlock NodeType;
   typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
@@ -800,37 +883,55 @@ template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > {
 template <> struct GraphTraits< ::clang::CFG* >
     : public GraphTraits< ::clang::CFGBlock *>  {
 
-  typedef ::clang::CFG::iterator nodes_iterator;
+  typedef ::clang::CFG::graph_iterator nodes_iterator;
 
-  static NodeType *getEntryNode(::clang::CFG* F) { return &F->getEntry(); }
-  static nodes_iterator nodes_begin(::clang::CFG* F) { return F->begin(); }
-  static nodes_iterator nodes_end(::clang::CFG* F) { return F->end(); }
+  static NodeType     *getEntryNode(::clang::CFG* F) { return &F->getEntry(); }
+  static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
+  static nodes_iterator   nodes_end(::clang::CFG* F) { return F->nodes_end(); }
+  static unsigned              size(::clang::CFG* F) { return F->size(); }
 };
 
 template <> struct GraphTraits<const ::clang::CFG* >
     : public GraphTraits<const ::clang::CFGBlock *>  {
 
-  typedef ::clang::CFG::const_iterator nodes_iterator;
+  typedef ::clang::CFG::const_graph_iterator nodes_iterator;
 
   static NodeType *getEntryNode( const ::clang::CFG* F) {
     return &F->getEntry();
   }
   static nodes_iterator nodes_begin( const ::clang::CFG* F) {
-    return F->begin();
+    return F->nodes_begin();
   }
   static nodes_iterator nodes_end( const ::clang::CFG* F) {
-    return F->end();
+    return F->nodes_end();
   }
+  static unsigned size(const ::clang::CFG* F) {
+    return F->size();
+  }
+};
+
+template <> struct GraphTraits<Inverse< ::clang::CFG*> >
+  : public GraphTraits<Inverse< ::clang::CFGBlock*> > {
+
+  typedef ::clang::CFG::graph_iterator nodes_iterator;
+
+  static NodeType *getEntryNode( ::clang::CFG* F) { return &F->getExit(); }
+  static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
+  static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
 };
 
 template <> struct GraphTraits<Inverse<const ::clang::CFG*> >
   : public GraphTraits<Inverse<const ::clang::CFGBlock*> > {
 
-  typedef ::clang::CFG::const_iterator nodes_iterator;
+  typedef ::clang::CFG::const_graph_iterator nodes_iterator;
 
   static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); }
-  static nodes_iterator nodes_begin(const ::clang::CFG* F) { return F->begin();}
-  static nodes_iterator nodes_end(const ::clang::CFG* F) { return F->end(); }
+  static nodes_iterator nodes_begin(const ::clang::CFG* F) {
+    return F->nodes_begin();
+  }
+  static nodes_iterator nodes_end(const ::clang::CFG* F) {
+    return F->nodes_end();
+  }
 };
 } // end llvm namespace
 #endif