1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
//==- 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";
}
}
|
