Repository navigation
Tracking Issue for Non-Lexical Constant Propagation #80038
Description
This is a tracking issue for the work I'm doing together with @oli-obk, regarding the upgrade of the MIR const-prop pass into a dataflow-analysis-enhanced Constant Propagation pass. This is part of my undergrad thesis, so as long as I am able to work on it, I should have at least the equivalent of part-time availability for the development of the feature.
The feature gate for this issue is #![feature(non_lexical_constprop)]
(feature gate is not in-tree yet)
What this feature means
Currently, there is a MIR optimization pass that does what is commonly know as Constant Folding. In this post however, I'll refer to it as Constant Propagation, since that is the name that we've given it in the mir-opts directory and documentation 🙂
What the Constant Propagation pass currently does is very limited in scope: it has no awareness of conditional execution (the true and false branches of an if block, for example) and therefore, it limits the propagation range of values known-to-be-constant to just the block in which these values reside.
In this work we will do our best to bring CP up to at least the standard constant propagation passes present in the literature: where the compiler is smart enough to understand control flow, and can conditionally propagate values into control-flow-dependent blocks. For this, the tool we expect to use is the MIR dataflow analysis framework, since CP is a problem known to be well-suited for dataflow analysis.
There are two end goals for this feature so far:
- To bring faster compilation times via the
rustcfrontend givingIRof greater quality toLLVM. - To make certain kinds of static analyses possible, that so far require ad-hoc machinery to even be possible, like this Clippy lint that tries to catch whether or not the user is transmuting a
nullpointer at compile time. By having better compile-time information on the value of variables, we expect many analyses like this one to be more viable to realize.
Steps
(Subject to further breakup into smaller steps)
- Implement CP based on the MIR dataflow framework that's currently available in
rustc - Test the implementation thoroughly (using a feature flag).
- Adjust relevant documentation (CC @oli-obk is there docs on MIR opts? I think we've discussed this before. Maybe it doesn't make sense to document the optimization per se until we've really found an end to the road of available const-prop enhancements, since CP will definitely get upgraded until that happens).
- Stabilization PR (see instructions on rustc-dev-guide)
Unresolved Questions
None so far. Please ask away, I'm sure there's something I've missed 🙂
Implementation history
There's no implementation yet, although I can look up the recent changes to the const-prop pass and outline them here.
Closing note
This should probably be called Non-Lexical ConstProp, since Lexical boundaries are precisely as far as ConstProp can reach right now, and dataflow-aware ConstProp will go beyond, just like the Lifetime analysis did ^^
Activity
felix91gr commentedon Dec 14, 2020
Here's an addendum for questions that might occur to the readers:
What about Value-Range Analysis?
Value-Range Analysis is something that the MIR-opts do not have at all yet. It's pretty clear that VRA can be treated like a generalization of Constant Propagation, since a Constant of value
acan be seen as a range restriction of[x >= a, x <= a]. Therefore if implemented well, it could be used as the tool for this issue's feature as well.However, its complexity is much greater than simple CP, and its use-cases go beyond the CP use cases as well.
This makes it harder to plan for: what are the test cases? What is the scope? Have we exhausted this feature yet?
The writer of this issue (me, Félix) in particular feels that they cannot really attack it head on just yet.
Ideally, one would implement just VRA and piggyback on it for CP. However, given the overall risk of going directly for VRA, the author prefers to first conquer CP and then go for VRA after getting a better understanding of the whole.
leonardo-m commentedon Dec 14, 2020
Value-Range Analysis (and slice-length analysis) is important for lot of things, but I agree it's a better idea to think about CP first.
oli-obk commentedon Dec 15, 2020
cc @rust-lang/wg-mir-opt
Ideally we'd use the new (closed PR #77665, feel free to reopen :D) optimization selection framework. This allows us fine grained control over which optimization passes to run via the command line.
There may be a little bit in the rustc guide, but I think keeping optimization specific documentation close to the optimization impl is probably for the best. This way it'll show up in the rustc internal rustdoc generated docs. Though I'll happily concede that point to someone who put more thought into this than I have.
wesleywiser commentedon Dec 15, 2020
This sounds great and I'm really excited to see some work on this!
At least in terms of goal 1 (reducing compilation times), it would be good to keep in mind the guidelines about
-Zmir-opt-level. It may be necessary to enable or disable some parts of the new pass based on the value of that flag.I would also recommend starting the new pass from scratch and not attempting to modify the existing one. Since the current one is enabled by default, bugs introduced there can easily result in unsound behavior in the program being compiled. I think it will also make it easier at the end of this project as we can simply delete the old pass and enable the new one.
felix91gr commentedon Dec 15, 2020
Indeed, I think I completely agree with both points 🙂
leonardo-m commentedon Dec 16, 2020
An example where Value-Range Analysis could help:
#80075
[-]Tracking Issue for Control-Flow-Aware Constant Propagation[/-][+]Tracking Issue for Non-Lexical Constant Propagation[/+]felix91gr commentedon Jan 21, 2021
Another space where VRA can help: #81237
felix91gr commentedon Feb 27, 2021
Small update:
It's been a hectic month here. I got an injury in my right elbow and that's limiting my ability to use the right arm in general. Also one of our puppers had to have an urgent, very dangerous surgery and that also took away basically all of my attention and energy. Currently I'm working on getting my arm in better shape, and struggling a bit with MH stuff.
I've been studying the fundamental theory behind dataflow analysis, because things are currently such that I have no one to bother with my questions about it. So I'm trying to become an expert in the stuff.
During my work on this feature, I'll also fix some issues there are in the documentation, namely that the Convergence Requisites are not sufficient for all cases. Below, a more technical explanation of what I've elucidated so far:
True requirements for a dataflow analysis' semilattice to reach fixpoint
We find the Maximum Fixed Point in our analysis. We work with the
joinoperation, starting with thebottomvalue and looking for the MFP from there. This MFP can be computed, only if:a1 < a2 < a3 < a4 ...) are finite.fis a flow function in our analysis, andaandbare elements in the semilattice such thata <= b, then we know thatf(a) <= f(b)holds as well.Currently the requisites are weaker, and there are examples of semilattices which satisfy the conditions in our docs which actually don't have a computable, or even an existing MFP.
Sorry if anyone's been trying to find me in Zulip or expected me to get this done quicker. Things are just very hard at the moment. Much love to y'all ❤️
Auto merge of rust-lang#101168 - jachris:dataflow-const-prop, r=oli-obk