blob: 4d8d140373eabd5790cb039ee0d67d3d66c2a899 (
plain)
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
|
//=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file exposes interfaces to post dominance information.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_POST_DOMINATORS_H
#define LLVM_ANALYSIS_POST_DOMINATORS_H
#include "llvm/Analysis/Dominators.h"
namespace llvm {
//===-------------------------------------
/// ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase
/// that is used to compute a normal immediate dominator set.
///
struct ImmediatePostDominators : public ImmediateDominatorsBase {
ImmediatePostDominators() : ImmediateDominatorsBase(false) {}
virtual bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
}
private:
unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
void Compress(BasicBlock *V, InfoRec &VInfo);
BasicBlock *Eval(BasicBlock *v);
void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
};
/// PostDominatorSet Class - Concrete subclass of DominatorSetBase that is used
/// to compute the post-dominator set. Because there can be multiple exit nodes
/// in an LLVM function, we calculate post dominators with a special null block
/// which is the virtual exit node that the real exit nodes all virtually branch
/// to. Clients should be prepared to see an entry in the dominator sets with a
/// null BasicBlock*.
///
struct PostDominatorSet : public DominatorSetBase {
PostDominatorSet() : DominatorSetBase(true) {}
virtual bool runOnFunction(Function &F);
/// getAnalysisUsage - This simply provides a dominator set
///
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<ImmediatePostDominators>();
AU.setPreservesAll();
}
// stub - dummy function, just ignore it
static void stub();
};
/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
/// compute the a post-dominator tree.
///
struct PostDominatorTree : public DominatorTreeBase {
PostDominatorTree() : DominatorTreeBase(true) {}
virtual bool runOnFunction(Function &F) {
reset(); // Reset from the last time we were run...
ImmediatePostDominators &IPD = getAnalysis<ImmediatePostDominators>();
Roots = IPD.getRoots();
calculate(IPD);
return false;
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<ImmediatePostDominators>();
}
private:
void calculate(const ImmediatePostDominators &IPD);
Node *getNodeForBlock(BasicBlock *BB);
};
/// PostETForest Class - Concrete subclass of ETForestBase that is used to
/// compute a forwards post-dominator ET-Forest.
struct PostETForest : public ETForestBase {
PostETForest() : ETForestBase(true) {}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<ImmediatePostDominators>();
}
virtual bool runOnFunction(Function &F) {
reset(); // Reset from the last time we were run...
ImmediatePostDominators &ID = getAnalysis<ImmediatePostDominators>();
Roots = ID.getRoots();
calculate(ID);
return false;
}
void calculate(const ImmediatePostDominators &ID);
ETNode *getNodeForBlock(BasicBlock *BB);
};
/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
/// used to compute the a post-dominance frontier.
///
struct PostDominanceFrontier : public DominanceFrontierBase {
PostDominanceFrontier() : DominanceFrontierBase(true) {}
virtual bool runOnFunction(Function &) {
Frontiers.clear();
PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
Roots = DT.getRoots();
if (const DominatorTree::Node *Root = DT.getRootNode())
calculate(DT, Root);
return false;
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<PostDominatorTree>();
}
private:
const DomSetType &calculate(const PostDominatorTree &DT,
const DominatorTree::Node *Node);
};
} // End llvm namespace
// Make sure that any clients of this file link in PostDominators.cpp
FORCE_DEFINING_FILE_TO_BE_LINKED(PostDominanceFrontier)
#endif
|
