Dominators.cpp revision 7c4629c8bba02762119c873b657329d28abaa4ca 
1//==- Dominators.cpp - Construct the Dominance Tree Given CFG ----*- C++ --*-==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements a simple, fast dominance algorithm for source-level CFGs.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Analysis/Analyses/Dominators.h"
15#include "clang/Analysis/CFG.h"
16#include "clang/Analysis/AnalysisContext.h"
17#include "clang/Analysis/Analyses/PostOrderCFGView.h"
18
19using namespace clang;
20
21DominatorTree::~DominatorTree() {
22  IDoms.clear();
23  RootNode = 0;
24}
25
26CFGBlock * DominatorTree::getNode(const CFGBlock *B) const {
27  CFGBlockMapTy::const_iterator I = IDoms.find(B);
28  return I != IDoms.end() ? I->second : 0;
29}
30
31bool DominatorTree::properlyDominates(const CFGBlock *A,
32                                      const CFGBlock *B) const {
33  if (0 == A || 0 == B || A == B)
34    return false;
35
36  // The EntryBlock dominates every other block.
37  if (A == RootNode)
38    return true;
39
40  // Note: The dominator of the EntryBlock is itself.
41  CFGBlock *IDom = getNode(B);
42  while (IDom != A && IDom != RootNode)
43    IDom = getNode(IDom);
44
45  return IDom != RootNode;
46}
47
48bool DominatorTree::dominates(const CFGBlock *A,
49                              const CFGBlock *B) const {
50  if (A == B)
51    return true;
52
53  return properlyDominates(A, B);
54}
55
56const CFGBlock * DominatorTree::findNearestCommonDominator
57      (const CFGBlock *A, const CFGBlock *B) const {
58  //If A dominates B, then A is the nearest common dominator
59  if (dominates(A, B))
60    return A;
61
62  //If B dominates A, then B is the nearest common dominator
63  if (dominates(B, A))
64    return B;
65
66  //Collect all A's dominators
67  llvm::SmallPtrSet<CFGBlock *, 16> ADoms;
68  ADoms.insert(RootNode);
69  CFGBlock *ADom = getNode(A);
70  while (ADom != RootNode) {
71    ADoms.insert(ADom);
72    ADom = getNode(ADom);
73  }
74
75  //Check all B's dominators against ADoms
76  CFGBlock *BDom = getNode(B);
77  while (BDom != RootNode){
78    if (ADoms.count(BDom) != 0)
79      return BDom;
80
81    BDom = getNode(BDom);
82  }
83
84  //The RootNode dominates every other node
85  return RootNode;
86}
87
88/// Constructs immediate dominator tree for a given CFG based on the algorithm
89/// described in this paper:
90///
91///  A Simple, Fast Dominance Algorithm
92///  Keith D. Cooper, Timothy J. Harvey and Ken Kennedy
93///  Software-Practice and Expreience, 2001;4:1-10.
94///
95/// This implementation is simple and runs faster in practice than the classis
96/// Lengauer-Tarjan algorithm. For detailed discussions, refer to the paper.
97void DominatorTree::BuildDominatorTree() {
98  CFG *cfg = AC.getCFG();
99  CFGBlock *EntryBlk = &cfg->getEntry();
100
101  //Sort all CFGBlocks in reverse order
102  PostOrderCFGView *rpocfg = AC.getAnalysis<PostOrderCFGView>();
103
104  //Set the root of the dominance tree
105  RootNode = EntryBlk;
106
107  //Compute the immediate dominator for each CFGBlock
108  IDoms[EntryBlk] = EntryBlk;
109  bool changed = true;
110  while (changed){
111    changed = false;
112
113    for (PostOrderCFGView::iterator I = rpocfg->begin(),
114        E = rpocfg->end(); I != E; ++I){
115      if (EntryBlk == *I)
116        continue;
117      if (const CFGBlock *B = *I) {
118        //Compute immediate dominance information for CFGBlock B
119        CFGBlock *IDom = 0;
120        for (CFGBlock::const_pred_iterator J = B->pred_begin(),
121            K = B->pred_end(); J != K; ++J)
122          if( CFGBlock *P = *J) {
123            if (IDoms.find(P) == IDoms.end())
124              continue;
125            if (!IDom)
126              IDom = P;
127            else {
128              //intersect IDom and P
129              CFGBlock *B1 = IDom, *B2 = P;
130              while (B1 != B2) {
131                while ((rpocfg->getComparator())(B2,B1))
132                  B1 = IDoms[B1];
133                while ((rpocfg->getComparator())(B1,B2))
134                  B2 = IDoms[B2];
135              }
136              IDom = B1;
137            }
138          }
139        if (IDoms[B] != IDom) {
140          IDoms[B] = IDom;
141          changed = true;
142        }
143      }
144    }
145  }//while
146}
147
148void DominatorTree::dump() {
149  CFG *cfg = AC.getCFG();
150
151  llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
152  for (CFG::const_iterator I = cfg->begin(),
153      E = cfg->end(); I != E; ++I) {
154    assert(IDoms[(*I)] &&
155       "Failed to find the immediate dominator for all CFG blocks.");
156    llvm::errs() << "(" << (*I)->getBlockID()
157                 << "," << IDoms[(*I)]->getBlockID() << ")\n";
158  }
159}
160
161