Skip to content

Commit 357f660

Browse files
borsbors
committed
Auto merge of #101168 - jachris:dataflow-const-prop, r=oli-obk
Add new MIR constant propagation based on dataflow analysis The current constant propagation in `rustc_mir_transform/src/const_prop.rs` fails to handle many cases that would be expected from a constant propagation optimization. For example: ```rust let x = if true { 0 } else { 0 }; ``` This pull request adds a new constant propagation MIR optimization pass based on the existing dataflow analysis framework. Since most of the analysis is not unique to constant propagation, a generic framework has been extracted. It works on top of the existing framework and could be reused for other optimzations. Closes #80038. Closes #81605. ## Todo ### Essential - [x] [Writes to inactive enum variants](#101168 (review)). Resolved by rejecting the registration of places with downcast projections for now. Could be improved by flooding other variants if mutable access to a variant is observed. - [X] Handle [`StatementKind::CopyNonOverlapping`](#101168 (comment)). Resolved by flooding the destination. - [x] Handle `UnsafeCell` / `!Freeze` correctly. - [X] Overflow propagation of `CheckedBinaryOp`: Decided to not propagate if overflow flag is `true` (`false` will still be propagated) - [x] More documentation in general. - [x] Arguments for correctness, documentation of necessary assumptions. - [x] Better performance, or alternatively, require `-Zmir-opt-level=3` for now. ### Extra - [x] Add explicit unreachability, i.e. upgrading the lattice from $\mathbb{P} \to \mathbb{V}$ to $\set{\bot} \cup (\mathbb{P} \to \mathbb{V})$. - [x] Use storage statements to improve precision. - [ ] Consider opening issue for duplicate diagnostics: #101168 (comment) - [ ] Flood moved-from places with $\bot$ (requires some changes for places with tracked projections). - [ ] Add downcast projections back in. - [ ] [Algebraic simplifications](#101168 (comment)) (possibly with a shared API; done by old const prop). - [ ] Propagation through slices / arrays. - [ ] Find other optimizations that are done by old `const_prop.rs`, but not by this one.
2 parents ca92d90 + 24d2e90 commit 357f660

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

43 files changed

+2441
-25
lines changed

‎compiler/rustc_graphviz/src/lib.rs

+5-1
Original file line numberDiff line numberDiff line change
@@ -471,7 +471,11 @@ pub trait Labeller<'a> {
471471
/// Escape tags in such a way that it is suitable for inclusion in a
472472
/// Graphviz HTML label.
473473
pub fn escape_html(s: &str) -> String {
474-
s.replace('&', "&amp;").replace('\"', "&quot;").replace('<', "&lt;").replace('>', "&gt;")
474+
s.replace('&', "&amp;")
475+
.replace('\"', "&quot;")
476+
.replace('<', "&lt;")
477+
.replace('>', "&gt;")
478+
.replace('\n', "<br align=\"left\"/>")
475479
}
476480

477481
impl<'a> LabelText<'a> {

‎compiler/rustc_middle/src/mir/generic_graphviz.rs

+3-4
Original file line numberDiff line numberDiff line change
@@ -126,7 +126,7 @@ impl<
126126
write!(
127127
w,
128128
r#"<tr><td align="left" balign="left">{}</td></tr>"#,
129-
dot::escape_html(&section).replace('\n', "<br/>")
129+
dot::escape_html(&section)
130130
)?;
131131
}
132132

@@ -147,7 +147,7 @@ impl<
147147
let src = self.node(source);
148148
let trg = self.node(target);
149149
let escaped_edge_label = if let Some(edge_label) = edge_labels.get(index) {
150-
dot::escape_html(edge_label).replace('\n', r#"<br align="left"/>"#)
150+
dot::escape_html(edge_label)
151151
} else {
152152
"".to_owned()
153153
};
@@ -162,8 +162,7 @@ impl<
162162
where
163163
W: Write,
164164
{
165-
let lines = label.split('\n').map(|s| dot::escape_html(s)).collect::<Vec<_>>();
166-
let escaped_label = lines.join(r#"<br align="left"/>"#);
165+
let escaped_label = dot::escape_html(label);
167166
writeln!(w, r#" label=<<br/><br/>{}<br align="left"/><br/><br/><br/>>;"#, escaped_label)
168167
}
169168

‎compiler/rustc_middle/src/mir/visit.rs

+9
Original file line numberDiff line numberDiff line change
@@ -1320,6 +1320,15 @@ impl PlaceContext {
13201320
)
13211321
}
13221322

1323+
/// Returns `true` if this place context represents an address-of.
1324+
pub fn is_address_of(&self) -> bool {
1325+
matches!(
1326+
self,
1327+
PlaceContext::NonMutatingUse(NonMutatingUseContext::AddressOf)
1328+
| PlaceContext::MutatingUse(MutatingUseContext::AddressOf)
1329+
)
1330+
}
1331+
13231332
/// Returns `true` if this place context represents a storage live or storage dead marker.
13241333
#[inline]
13251334
pub fn is_storage_marker(&self) -> bool {

‎compiler/rustc_mir_dataflow/src/framework/graphviz.rs

+4-1
Original file line numberDiff line numberDiff line change
@@ -475,7 +475,10 @@ where
475475
r#"<td colspan="{colspan}" {fmt} align="left">{state}</td>"#,
476476
colspan = this.style.num_state_columns(),
477477
fmt = fmt,
478-
state = format!("{:?}", DebugWithAdapter { this: state, ctxt: analysis }),
478+
state = dot::escape_html(&format!(
479+
"{:?}",
480+
DebugWithAdapter { this: state, ctxt: analysis }
481+
)),
479482
)
480483
})
481484
}

‎compiler/rustc_mir_dataflow/src/framework/lattice.rs

+34
Original file line numberDiff line numberDiff line change
@@ -73,6 +73,16 @@ pub trait MeetSemiLattice: Eq {
7373
fn meet(&mut self, other: &Self) -> bool;
7474
}
7575

76+
/// A set that has a "bottom" element, which is less than or equal to any other element.
77+
pub trait HasBottom {
78+
fn bottom() -> Self;
79+
}
80+
81+
/// A set that has a "top" element, which is greater than or equal to any other element.
82+
pub trait HasTop {
83+
fn top() -> Self;
84+
}
85+
7686
/// A `bool` is a "two-point" lattice with `true` as the top element and `false` as the bottom:
7787
///
7888
/// ```text
@@ -102,6 +112,18 @@ impl MeetSemiLattice for bool {
102112
}
103113
}
104114

115+
impl HasBottom for bool {
116+
fn bottom() -> Self {
117+
false
118+
}
119+
}
120+
121+
impl HasTop for bool {
122+
fn top() -> Self {
123+
true
124+
}
125+
}
126+
105127
/// A tuple (or list) of lattices is itself a lattice whose least upper bound is the concatenation
106128
/// of the least upper bounds of each element of the tuple (or list).
107129
///
@@ -250,3 +272,15 @@ impl<T: Clone + Eq> MeetSemiLattice for FlatSet<T> {
250272
true
251273
}
252274
}
275+
276+
impl<T> HasBottom for FlatSet<T> {
277+
fn bottom() -> Self {
278+
Self::Bottom
279+
}
280+
}
281+
282+
impl<T> HasTop for FlatSet<T> {
283+
fn top() -> Self {
284+
Self::Top
285+
}
286+
}

‎compiler/rustc_mir_dataflow/src/lib.rs

+1
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,7 @@ pub mod move_paths;
4141
pub mod rustc_peek;
4242
pub mod storage;
4343
pub mod un_derefer;
44+
pub mod value_analysis;
4445

4546
pub(crate) mod indexes {
4647
pub(crate) use super::move_paths::MovePathIndex;

0 commit comments

Comments
 (0)