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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
use crate::control_flow_graph::{CFGNode, ControlFlowGraph};
use crate::dominator_tree::PostDominatorTree;
use llvm_ir::Name;
use petgraph::prelude::{DfsPostOrder, DiGraphMap, Direction};
use petgraph::visit::Walker;
use std::collections::HashSet;
/// The control dependence graph for a particular function.
/// https://en.wikipedia.org/wiki/Data_dependency#Control_Dependency
///
/// To construct a `ControlDependenceGraph`, use
/// [`FunctionAnalysis`](struct.FunctionAnalysis.html), which you can get
/// from [`ModuleAnalysis`](struct.ModuleAnalysis.html).
pub struct ControlDependenceGraph<'m> {
/// The graph itself. An edge from bbX to bbY indicates that bbX has an
/// immediate control dependence on bbY. A path from bbX to bbY indicates
/// that bbX has a control dependence on bbY.
graph: DiGraphMap<CFGNode<'m>, ()>,
/// Entry node for the function
pub(crate) entry_node: CFGNode<'m>,
}
impl<'m> ControlDependenceGraph<'m> {
pub(crate) fn new(cfg: &ControlFlowGraph<'m>, postdomtree: &PostDominatorTree<'m>) -> Self {
// algorithm thanks to Cytron, Ferrante, Rosen, et al. "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph"
// https://www.cs.utexas.edu/~pingali/CS380C/2010/papers/ssaCytron.pdf (Figure 10)
let mut graph = DiGraphMap::new();
for block_x in
DfsPostOrder::new(&postdomtree.graph, CFGNode::Return).iter(&postdomtree.graph)
{
let mut postdominance_frontier_of_x = vec![];
for block_y in cfg.preds_as_nodes(block_x) {
if postdomtree.ipostdom_of_cfgnode(block_y) != Some(block_x) {
postdominance_frontier_of_x.push(block_y);
}
}
for block_z in postdomtree.children_of_cfgnode(block_x) {
// we should have already computed all of the outgoing edges from block_z
for block_y in graph.neighbors_directed(block_z, Direction::Outgoing) {
if postdomtree.ipostdom_of_cfgnode(block_y) != Some(block_x) {
postdominance_frontier_of_x.push(block_y);
}
}
}
for node in postdominance_frontier_of_x {
graph.add_edge(block_x, node, ());
}
}
Self {
graph,
entry_node: cfg.entry_node,
}
}
/// Get the blocks that `block` has an immediate control dependency on.
pub fn get_imm_control_dependencies<'s>(
&'s self,
block: &'m Name,
) -> impl Iterator<Item = &'m Name> + 's {
self.get_imm_control_dependencies_of_cfgnode(CFGNode::Block(block))
}
pub(crate) fn get_imm_control_dependencies_of_cfgnode<'s>(
&'s self,
node: CFGNode<'m>,
) -> impl Iterator<Item = &'m Name> + 's {
self.graph
.neighbors_directed(node, Direction::Outgoing)
.map(|node| match node {
CFGNode::Block(block) => block,
CFGNode::Return => panic!("Nothing should be control-dependent on Return"),
})
}
/// Get the blocks that `block` has a control dependency on (including
/// transitively).
///
/// This is the block's immediate control dependencies, along with all the
/// control dependencies of those dependencies, and so on recursively.
pub fn get_control_dependencies<'s>(
&'s self,
block: &'m Name,
) -> impl Iterator<Item = &'m Name> + 's {
ControlDependenciesIterator::new(self, block)
}
/// Get the blocks that have an immediate control dependency on `block`.
pub fn get_imm_control_dependents<'s>(
&'s self,
block: &'m Name,
) -> impl Iterator<Item = CFGNode<'m>> + 's {
self.get_imm_control_dependents_of_cfgnode(CFGNode::Block(block))
}
pub(crate) fn get_imm_control_dependents_of_cfgnode<'s>(
&'s self,
node: CFGNode<'m>,
) -> impl Iterator<Item = CFGNode<'m>> + 's {
self.graph.neighbors_directed(node, Direction::Incoming)
}
/// Get the blocks that have a control dependency on `block` (including
/// transitively).
///
/// This is the block's immediate control dependents, along with all the
/// control dependents of those dependents, and so on recursively.
pub fn get_control_dependents<'s>(
&'s self,
block: &'m Name,
) -> impl Iterator<Item = CFGNode<'m>> + 's {
ControlDependentsIterator::new(self, block)
}
/// Does `block_a` have a control dependency on `block_b`?
pub fn is_control_dependent(&self, block_a: &'m Name, block_b: &'m Name) -> bool {
if block_a != block_b {
// the simple case: `has_path_connecting()` does exactly what we want
petgraph::algo::has_path_connecting(
&self.graph,
CFGNode::Block(block_a),
CFGNode::Block(block_b),
None,
)
} else {
// more complicated: we want to know if there is a nonzero-length
// path from the block to itself, while `has_path_connecting()` is
// content to always return `true` due to the zero-length path,
// which is not what we want.
// Instead, we check if there is a (zero-or-greater-length) path
// from any of the block's successors to the block.
self.graph
.neighbors_directed(CFGNode::Block(block_a), Direction::Outgoing)
.any(|succ| {
petgraph::algo::has_path_connecting(
&self.graph,
succ,
CFGNode::Block(block_a),
None,
)
})
}
}
/// Get the `Name` of the entry block for the function
pub fn entry(&self) -> &'m Name {
match self.entry_node {
CFGNode::Block(block) => block,
CFGNode::Return => panic!("Return node should not be entry"), // perhaps you tried to call this on a reversed CFG? In-crate users can use the `entry_node` field directly if they need to account for the possibility of a reversed CFG
}
}
}
struct ControlDependenciesIterator<'m> {
/// Currently implemented by computing all dependencies into a `HashSet` at
/// the beginning and then iterating over that `HashSet`. But this may
/// change, hence the opaque interface
deps: std::collections::hash_set::IntoIter<&'m Name>,
}
impl<'m> ControlDependenciesIterator<'m> {
/// Get a new iterator which will iterate over the control dependencies of `block`
fn new(cdg: &ControlDependenceGraph<'m>, block: &'m Name) -> Self {
let mut worklist: Vec<&'m Name> = cdg.get_imm_control_dependencies(block).collect();
let mut deps: HashSet<&'m Name> = HashSet::new();
while let Some(block) = worklist.pop() {
if deps.insert(block) {
worklist.extend(cdg.get_imm_control_dependencies(block))
}
}
Self {
deps: deps.into_iter(),
}
}
}
impl<'m> Iterator for ControlDependenciesIterator<'m> {
type Item = &'m Name;
fn next(&mut self) -> Option<&'m Name> {
self.deps.next()
}
}
struct ControlDependentsIterator<'m> {
/// Currently implemented by computing all dependents into a `HashSet` at the
/// beginning and then iterating over that `HashSet`. But this may change,
/// hence the opaque interface
deps: std::collections::hash_set::IntoIter<CFGNode<'m>>,
}
impl<'m> ControlDependentsIterator<'m> {
/// Get a new iterator which will iterate over the control dependents of `block`
fn new(cdg: &ControlDependenceGraph<'m>, block: &'m Name) -> Self {
let mut worklist: Vec<CFGNode<'m>> = cdg.get_imm_control_dependents(block).collect();
let mut deps: HashSet<CFGNode<'m>> = HashSet::new();
while let Some(node) = worklist.pop() {
if deps.insert(node) {
worklist.extend(cdg.get_imm_control_dependents_of_cfgnode(node))
}
}
Self {
deps: deps.into_iter(),
}
}
}
impl<'m> Iterator for ControlDependentsIterator<'m> {
type Item = CFGNode<'m>;
fn next(&mut self) -> Option<CFGNode<'m>> {
self.deps.next()
}
}