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
218
219
220
221
222
223
224
225
226
227
228
229
230
231
use super::{DominanceInfo, PostDominanceInfo};
use crate::{Block, BlockRef, Operation, Value};
/// This trait is implemented on a type which has a dominance relationship with `Rhs`.
pub trait Dominates<Rhs = Self> {
/// Returns true if `self` dominates `other`.
///
/// In cases where `Rhs = Self`, implementations should return true when `self == other`.
///
/// For a stricter form of dominance, use [Dominates::properly_dominates].
fn dominates(&self, other: &Rhs, dom_info: &DominanceInfo) -> bool;
/// Returns true if `self` properly dominates `other`.
///
/// In cases where `Rhs = Self`, implementations should return false when `self == other`.
fn properly_dominates(&self, other: &Rhs, dom_info: &DominanceInfo) -> bool;
}
/// This trait is implemented on a type which has a post-dominance relationship with `Rhs`.
pub trait PostDominates<Rhs = Self> {
/// Returns true if `self` post-dominates `other`.
///
/// In cases where `Rhs = Self`, implementations should return true when `self == other`.
///
/// For a stricter form of dominance, use [Self::properly_post_dominates].
fn post_dominates(&self, other: &Rhs, dom_info: &PostDominanceInfo) -> bool;
/// Returns true if `self` properly post-dominates `other`.
///
/// In cases where `Rhs = Self`, implementations should return false when `self == other`.
fn properly_post_dominates(&self, other: &Rhs, dom_info: &PostDominanceInfo) -> bool;
}
/// The dominance relationship between two blocks.
impl Dominates for Block {
/// Returns true if `a == b` or `a` properly dominates `b`.
fn dominates(&self, other: &Self, dom_info: &DominanceInfo) -> bool {
core::ptr::addr_eq(self, other) || self.properly_dominates(other, dom_info)
}
/// Returns true if `a != b` and:
///
/// * `a` is an ancestor of `b`
/// * The region containing `a` also contains `b` or some ancestor of `b`, and `a` dominates
/// that block in that kind of region.
/// * In SSA regions, `a` properly dominates `b` if all control flow paths from the entry
/// block to `b`, flow through `a`.
/// * In graph regions, all blocks dominate all other blocks.
fn properly_dominates(&self, other: &Self, dom_info: &DominanceInfo) -> bool {
dom_info.info().properly_dominates(self.as_block_ref(), other.as_block_ref())
}
}
/// The dominance relationship between two blocks.
impl Dominates for BlockRef {
/// Returns true if `a == b` or `a` properly dominates `b`.
fn dominates(&self, other: &Self, dom_info: &DominanceInfo) -> bool {
BlockRef::ptr_eq(self, other) || self.properly_dominates(other, dom_info)
}
/// Returns true if `a != b` and:
///
/// * `a` is an ancestor of `b`
/// * The region containing `a` also contains `b` or some ancestor of `b`, and `a` dominates
/// that block in that kind of region.
/// * In SSA regions, `a` properly dominates `b` if all control flow paths from the entry
/// block to `b`, flow through `a`.
/// * In graph regions, all blocks dominate all other blocks.
fn properly_dominates(&self, other: &Self, dom_info: &DominanceInfo) -> bool {
dom_info.info().properly_dominates(*self, *other)
}
}
/// The post-dominance relationship between two blocks.
impl PostDominates for Block {
fn post_dominates(&self, other: &Self, dom_info: &PostDominanceInfo) -> bool {
core::ptr::addr_eq(self, other) || self.properly_post_dominates(other, dom_info)
}
/// Returns true if `a != b` and:
///
/// * `a` is an ancestor of `b`
/// * The region containing `a` also contains `b` or some ancestor of `b`, and `a` dominates
/// that block in that kind of region.
/// * In SSA regions, `a` properly post-dominates `b` if all control flow paths from `b` to
/// an exit node, flow through `a`.
/// * In graph regions, all blocks post-dominate all other blocks.
fn properly_post_dominates(&self, other: &Self, dom_info: &PostDominanceInfo) -> bool {
dom_info.info().properly_dominates(self.as_block_ref(), other.as_block_ref())
}
}
/// The post-dominance relationship between two blocks.
impl PostDominates for BlockRef {
fn post_dominates(&self, other: &Self, dom_info: &PostDominanceInfo) -> bool {
BlockRef::ptr_eq(self, other) || self.properly_post_dominates(other, dom_info)
}
/// Returns true if `a != b` and:
///
/// * `a` is an ancestor of `b`
/// * The region containing `a` also contains `b` or some ancestor of `b`, and `a` dominates
/// that block in that kind of region.
/// * In SSA regions, `a` properly post-dominates `b` if all control flow paths from `b` to
/// an exit node, flow through `a`.
/// * In graph regions, all blocks post-dominate all other blocks.
fn properly_post_dominates(&self, other: &Self, dom_info: &PostDominanceInfo) -> bool {
dom_info.info().properly_dominates(*self, *other)
}
}
/// The dominance relationship for operations
impl Dominates for Operation {
fn dominates(&self, other: &Self, dom_info: &DominanceInfo) -> bool {
core::ptr::addr_eq(self, other) || self.properly_dominates(other, dom_info)
}
/// Returns true if `a != b`, and:
///
/// * `a` and `b` are in the same block, and `a` properly dominates `b` within the block, or
/// * the block that contains `a` properly dominates the block that contains `b`.
/// * `b` is enclosed in a region of `a`
///
/// In any SSA region, `a` dominates `b` in the same block if `a` precedes `b`. In a graph
/// region all operations in a block dominate all other operations in the same block.
fn properly_dominates(&self, other: &Self, dom_info: &DominanceInfo) -> bool {
let a = self.as_operation_ref();
let b = other.as_operation_ref();
dom_info.properly_dominates_with_options(a, b, /*enclosing_op_ok= */ true)
}
}
/// The post-dominance relationship for operations
impl PostDominates for Operation {
fn post_dominates(&self, other: &Self, dom_info: &PostDominanceInfo) -> bool {
core::ptr::addr_eq(self, other) || self.properly_post_dominates(other, dom_info)
}
/// Returns true if `a != b`, and:
///
/// * `a` and `b` are in the same block, and `a` properly post-dominates `b` within the block
/// * the block that contains `a` properly post-dominates the block that contains `b`.
/// * `b` is enclosed in a region of `a`
///
/// In any SSA region, `a` post-dominates `b` in the same block if `b` precedes `a`. In a graph
/// region all operations in a block post-dominate all other operations in the same block.
fn properly_post_dominates(&self, other: &Self, dom_info: &PostDominanceInfo) -> bool {
let a_block = self.parent().expect("`self` must be in a block");
let mut b_block = other.parent().expect("`other` must be in a block");
// An instruction post dominates, but does not properly post-dominate itself unless this is
// a graph region.
if core::ptr::addr_eq(self, other) {
return !a_block.borrow().has_ssa_dominance();
}
// If these ops are in different regions, then normalize one into the other.
let a_region = a_block.parent();
let b_region = b_block.parent();
let a = self.as_operation_ref();
let mut b = other.as_operation_ref();
if a_region != b_region {
// Walk up `b`'s region tree until we find an operation in `a`'s region that encloses
// it. If this fails, then we know there is no post-dominance relation.
let Some(found) = a_region.as_ref().and_then(|r| r.borrow().find_ancestor_op(b)) else {
return false;
};
b = found;
b_block = b.parent().unwrap();
assert!(b_block.parent() == a_region);
// If `a` encloses `b`, then we consider it to post-dominate.
if a == b {
return true;
}
}
// Ok, they are in the same region. If they are in the same block, check if `b` is before
// `a` in the block.
if a_block == b_block {
// Dominance changes based on the region type
return if a_block.borrow().has_ssa_dominance() {
// If the blocks are the same, then check if `b` is before `a` in the block.
b.borrow().is_before_in_block(&a)
} else {
true
};
}
// If the blocks are different, check if `a`'s block post-dominates `b`'s
dom_info
.info()
.dominance(a_region.unwrap())
.properly_dominates(Some(a_block), Some(b_block))
}
}
/// The dominance relationship between a value and an operation, e.g. between a definition of a
/// value and a user of that same value.
impl Dominates<Operation> for dyn Value {
/// Return true if the definition of `self` dominates a use by operation `other`.
fn dominates(&self, other: &Operation, dom_info: &DominanceInfo) -> bool {
self.get_defining_op().is_some_and(|op| op == other.as_operation_ref())
|| self.properly_dominates(other, dom_info)
}
/// Returns true if the definition of `self` properly dominates `other`.
///
/// This requires the value to either be a block argument, where the block containing `other`
/// is dominated by the block defining `self`, OR that the value is an operation result, and
/// the defining op of `self` properly dominates `other`.
///
/// If the defining op of `self` encloses `b` in one of its regions, `a` does not dominate `b`.
fn properly_dominates(&self, other: &Operation, dom_info: &DominanceInfo) -> bool {
// Block arguments properly dominate all operations in their own block, so we use a
// dominates check here, not a properly_dominates check.
if let Some(block_arg) = self.downcast_ref::<crate::BlockArgument>() {
return block_arg
.owner()
.borrow()
.dominates(&other.parent().unwrap().borrow(), dom_info);
}
// `a` properly dominates `b` if the operation defining `a` properly dominates `b`, but `a`
// does not itself enclose `b` in one of its regions.
let defining_op = self.get_defining_op().unwrap();
dom_info.properly_dominates_with_options(
defining_op,
other.as_operation_ref(),
/*enclosing_op_ok= */ false,
)
}
}