-
Notifications
You must be signed in to change notification settings - Fork 12.5k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Incorrectly unified locals at -Zmir-opt-level=2 #79191
Comments
Hmm, seems like it doesn't see the conflict because the assignment is unreachable: // init: <unreachable>
// live: <unreachable>
bb3: {
// init: <unreachable>
// live: <unreachable>
_2 = _7; // scope 2 at borken.rs:2:8: 2:16
// init: <unreachable>
// live: <unreachable>
goto -> bb4; // scope 2 at borken.rs:2:8: 2:16
// init: <unreachable>
// live: <unreachable>
} Seems like we should consider assignments in dead blocks as propagation candidates. But does that fix the whole bug? |
I think that the main issue is that the notion of conflicts is based on liveness. A local could be never live but still conflict with others merely because there are dead stores to it. For example, in code below #![allow(unused)]
#[inline(never)]
pub fn id<T>(x: T) -> T { x }
pub fn main() {
assert_eq!(1, g(1));
}
#[inline(never)]
pub fn g(x: usize) -> usize {
f(x)
}
#[inline(always)]
pub fn f(a: usize) -> usize {
let mut b = 3;
b = a;
b = 4;
id(a)
} |
Right. I think this briefly came up when implementing the pass, but I never wrote it down anywhere, nor could I produce an example. Sounds like we need to run a dead store elimination pass before destination propagation, or change the analysis it uses to account for dead stores. |
@rustbot claim |
@JakobDegen I'm interested in this, too. Have you done some work? If not, I should be able to submit a PR soon |
Yeah, I have a local branch up. Looking to open a PR today. The PR will be a draft though - the opt actually has significantly more problems than are reported in issues, and some of those problems being resolved is blocked on open questions about MIR semantics |
Fix Dest Prop Closes rust-lang#82678, rust-lang#79191 . This was not originally a total re-write of the pass but is has gradually turned into one. Notable changes: 1. Significant improvements to documentation all around. The top of the file has been extended with a more precise argument for soundness. The code should be fairly readable, and I've done my best to add useful comments wherever possible. I would very much like for the bus factor to not be one on this code. 3. Improved handling of conflicts that are not visible in normal dataflow. This was the cause of rust-lang#79191. Handling this correctly requires us to make decision about the semantics and specifically evaluation order of basically all MIR constructs (see specifically rust-lang#68364 rust-lang#71117. The way this is implemented is based on my preferred resolution to these questions around the semantics of assignment statements. 4. Some re-architecting to improve performance. More details below. 5. Possible future improvements to this optimization are documented, and the code is written with the needs of those improvements in mind. The hope is that adding support for more precise analyses will not require a full re-write of this opt, but just localized changes. ### Regarding Performance The previous approach had some performance issues; letting `l` be the number of locals and `s` be the number of statements/terminators, the runtime of the pass was `O(l^2 * s)`, both in theory and in practice. This version is smarter about not calculating unnecessary things and doing more caching. Our runtime is now dominated by one invocation of `MaybeLiveLocals` for each "round," and the number of rounds is less than 5 in over 90% of cases. This means it's linear-ish in practice. r? `@oli-obk` who reviewed the last version of this, but review from anyone else would be more than welcome
Fixed in #96451. |
The text was updated successfully, but these errors were encountered: