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

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

The patch is contributed by Guoping Long!

llvm-svn: 145858

1 files changed, 0 insertions, 160 deletions

diff --git a/clang/lib/Analysis/Dominators.cpp b/clang/lib/Analysis/Dominators.cpp
deleted file mode 100644
index 62b72287f97..00000000000
--- a/clang/lib/Analysis/Dominators.cpp
+++ /dev/null
@@ -1,160 +0,0 @@
-//==- Dominators.cpp - Construct the Dominance Tree Given CFG ----*- C++ --*-==//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements a simple, fast dominance algorithm for source-level CFGs.
-//
-//===----------------------------------------------------------------------===//
-
-#include "clang/Analysis/Analyses/Dominators.h"
-#include "clang/Analysis/CFG.h"
-#include "clang/Analysis/AnalysisContext.h"
-#include "clang/Analysis/Analyses/PostOrderCFGView.h"
-
-using namespace clang;
-
-DominatorTree::~DominatorTree() {
-  IDoms.clear();
-  RootNode = 0;
-}
-
-CFGBlock * DominatorTree::getNode(const CFGBlock *B) const {
-  CFGBlockMapTy::const_iterator I = IDoms.find(B);
-  return I != IDoms.end() ? I->second : 0; 
-}
-
-bool DominatorTree::properlyDominates(const CFGBlock *A, 
-                                      const CFGBlock *B) const {
-  if (0 == A || 0 == B || A == B)
-    return false;
-
-  // The EntryBlock dominates every other block.
-  if (A == RootNode)
-    return true;
-
-  // Note: The dominator of the EntryBlock is itself.
-  CFGBlock *IDom = getNode(B);
-  while (IDom != A && IDom != RootNode)
-    IDom = getNode(IDom);
-
-  return IDom != RootNode;
-}
-
-bool DominatorTree::dominates(const CFGBlock *A,
-                              const CFGBlock *B) const {
-  if (A == B)
-    return true;
-
-  return properlyDominates(A, B);
-}
-
-const CFGBlock * DominatorTree::findNearestCommonDominator
-      (const CFGBlock *A, const CFGBlock *B) const {
-  //If A dominates B, then A is the nearest common dominator
-  if (dominates(A, B))
-    return A;
-
-  //If B dominates A, then B is the nearest common dominator
-  if (dominates(B, A))
-    return B;
-
-  //Collect all A's dominators
-  llvm::SmallPtrSet<CFGBlock *, 16> ADoms;
-  ADoms.insert(RootNode);
-  CFGBlock *ADom = getNode(A);
-  while (ADom != RootNode) {
-    ADoms.insert(ADom);
-    ADom = getNode(ADom);
-  }  
-
-  //Check all B's dominators against ADoms
-  CFGBlock *BDom = getNode(B);
-  while (BDom != RootNode){
-    if (ADoms.count(BDom) != 0)
-      return BDom;
-
-    BDom = getNode(BDom);
-  }
-
-  //The RootNode dominates every other node
-  return RootNode;
-}
-
-/// Constructs immediate dominator tree for a given CFG based on the algorithm
-/// described in this paper:
-///
-///  A Simple, Fast Dominance Algorithm
-///  Keith D. Cooper, Timothy J. Harvey and Ken Kennedy
-///  Software-Practice and Expreience, 2001;4:1-10.
-///
-/// This implementation is simple and runs faster in practice than the classis
-/// Lengauer-Tarjan algorithm. For detailed discussions, refer to the paper. 
-void DominatorTree::BuildDominatorTree() {
-  CFG *cfg = AC.getCFG();
-  CFGBlock *EntryBlk = &cfg->getEntry();
-
-  //Sort all CFGBlocks in reverse order
-  PostOrderCFGView *rpocfg = AC.getAnalysis<PostOrderCFGView>();
-
-  //Set the root of the dominance tree
-  RootNode = EntryBlk;
-  
-  //Compute the immediate dominator for each CFGBlock
-  IDoms[EntryBlk] = EntryBlk;
-  bool changed = true;
-  while (changed){
-    changed = false;
-
-    for (PostOrderCFGView::iterator I = rpocfg->begin(),
-        E = rpocfg->end(); I != E; ++I){
-      if (EntryBlk == *I)
-        continue;
-      if (const CFGBlock *B = *I) {
-        //Compute immediate dominance information for CFGBlock B
-        CFGBlock *IDom = 0;
-        for (CFGBlock::const_pred_iterator J = B->pred_begin(),
-            K = B->pred_end(); J != K; ++J)
-          if( CFGBlock *P = *J) {
-            if (IDoms.find(P) == IDoms.end())
-              continue;
-            if (!IDom)
-              IDom = P;
-            else {
-              //intersect IDom and P
-              CFGBlock *B1 = IDom, *B2 = P;
-              while (B1 != B2) {
-                while ((rpocfg->getComparator())(B2,B1))
-                  B1 = IDoms[B1];
-                while ((rpocfg->getComparator())(B1,B2))
-                  B2 = IDoms[B2];
-              }
-              IDom = B1;
-            }
-          }
-        if (IDoms[B] != IDom) {
-          IDoms[B] = IDom;
-          changed = true;
-        } 
-      }
-    }
-  }//while
-}
-
-void DominatorTree::dump() {
-  CFG *cfg = AC.getCFG();
-
-  llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
-  for (CFG::const_iterator I = cfg->begin(),
-      E = cfg->end(); I != E; ++I) {
-    assert(IDoms[(*I)] && 
-       "Failed to find the immediate dominator for all CFG blocks.");
-    llvm::errs() << "(" << (*I)->getBlockID()
-                 << "," << IDoms[(*I)]->getBlockID() << ")\n";
-  }
-}
-