Repository navigation
Semantics of StorageLive in loops #42371
Description
This code
fn factorial_loop() -> i64 {
let mut product = 1;
let mut i = 1;
while i <= 10 {
product *= i;
i += 1;
}
product
}compiles to
fn factorial_loop() -> i64 {
let mut _0: i64; // return pointer
scope 1 {
let mut _1: i64; // "product" in scope 1 at src/main.rs:2:9: 2:20
scope 2 {
let mut _2: i64; // "i" in scope 2 at src/main.rs:3:9: 3:14
}
}
let mut _3: ();
let mut _4: bool;
let mut _5: i64;
let mut _6: ();
let mut _7: i64;
let mut _8: (i64, bool);
let mut _9: (i64, bool);
let mut _10: i64;
bb0: {
StorageLive(_1); // scope 0 at src/main.rs:2:9: 2:20
_1 = const 1i64; // scope 0 at src/main.rs:2:23: 2:24
StorageLive(_2); // scope 1 at src/main.rs:3:9: 3:14
_2 = const 1i64; // scope 1 at src/main.rs:3:17: 3:18
goto -> bb1; // scope 2 at src/main.rs:5:5: 8:6
}
bb1: {
StorageLive(_4); // scope 2 at src/main.rs:5:11: 5:18
StorageLive(_5); // scope 2 at src/main.rs:5:11: 5:12
_5 = _2; // scope 2 at src/main.rs:5:11: 5:12
_4 = Le(_5, const 10i64); // scope 2 at src/main.rs:5:11: 5:18
StorageDead(_5); // scope 2 at src/main.rs:5:18: 5:18
switchInt(_4) -> [0u8: bb2, otherwise: bb3]; // scope 2 at src/main.rs:5:5: 8:6
}
bb2: {
_3 = (); // scope 2 at src/main.rs:5:5: 8:6
StorageDead(_4); // scope 2 at src/main.rs:8:6: 8:6
StorageLive(_10); // scope 2 at src/main.rs:10:5: 10:12
_10 = _1; // scope 2 at src/main.rs:10:5: 10:12
_0 = _10; // scope 2 at src/main.rs:10:5: 10:12
StorageDead(_10); // scope 2 at src/main.rs:10:12: 10:12
StorageDead(_2); // scope 1 at src/main.rs:11:2: 11:2
StorageDead(_1); // scope 0 at src/main.rs:11:2: 11:2
return; // scope 0 at src/main.rs:11:2: 11:2
}
bb3: {
StorageLive(_7); // scope 2 at src/main.rs:6:20: 6:21
_7 = _2; // scope 2 at src/main.rs:6:20: 6:21
_8 = CheckedMul(_1, _7); // scope 2 at src/main.rs:6:9: 6:21
assert(!(_8.1: bool), "attempt to multiply with overflow") -> bb4; // scope 2 at src/main.rs:6:9: 6:21
}
bb4: {
_1 = (_8.0: i64); // scope 2 at src/main.rs:6:9: 6:21
StorageDead(_7); // scope 2 at src/main.rs:6:21: 6:21
_9 = CheckedAdd(_2, const 1i64); // scope 2 at src/main.rs:7:9: 7:15
assert(!(_9.1: bool), "attempt to add with overflow") -> bb5; // scope 2 at src/main.rs:7:9: 7:15
}
bb5: {
_2 = (_9.0: i64); // scope 2 at src/main.rs:7:9: 7:15
_6 = (); // scope 2 at src/main.rs:5:19: 8:6
goto -> bb1; // scope 2 at src/main.rs:5:5: 8:6
}
}
On every run through the loop, StorageLive(_4) is executed, and there is no matching StorageDead.
The intended semantics of multiple StorageLive on the same location are unclear. However, evidence suggests that LLVM considers a variable dead before any llvm.lifetime.start, in particular, in llvm.lifetime.start; load; llvm.lifetime.start, LLVM feels free to treat that load as yielding undef. The reference manual says so (however, it doesn't say anything about llvm.lifetime.start; load; llvm.lifetime.end; llvm.lifetime.start being fine, so it seems incomplete), and @eddyb managed to actually obtain UB from a redundant llvm.lifetime.start in
#![feature(link_llvm_intrinsics, untagged_unions)]
extern {
#[link_name = "llvm.lifetime.start"]
fn MyStorageLive(size: usize, ptr: *const u8);
}
#[allow(unions_with_drop_fields)]
union Foo<T> { x: T }
fn main() {
unsafe {
let mut x = Foo { x: String::new() };
while x.x.len() < 10 {
x.x.push('a');
assert_eq!(std::mem::size_of_val(&x.x), 24);
MyStorageLive(24, &x.x as *const _ as *const _);
println!("{}", &x.x[..])
}
}
}Playpen
If you comment out the MyStorageLive, this prints some a's. If you leave it in, nothing is printed.
This suggests we should rather not permit "redundant" StorageLive, and hence the program at the beginning of this report should be translated such that _4 is marked live before the loop, rather than inside the loop.
Activity
RalfJung commentedon Jun 2, 2017
I suppose a somewhat weaker interpretation would be for
llvm.lifetime.startto kill the current value in the memory, even if it is already live. (This has been suggested by @arielb1.)Then the code above would be correct. I guess part of the question is how conservative we want to be here.
[-]StorageLive emitted incorrectly for loop conditionals[/-][+]Semantics of StorageLive in loops[/+]RalfJung commentedon Jun 2, 2017
FYI, I implemented the above suggestion in Miri, and the test suite passes. Now that's not a whole lot of code on the grand scheme of things, but this does invoke some interesting unsafe code in Vec and the
startlang item, so it's better than nothing.RalfJung commentedon May 18, 2019
Accidental triage (because I forgot about this and just rediscovered the issue^^): the situation is unchanged.
Auto merge of #61872 - matthewjasper:refactor-mir-drop-gen, r=nikomat…
RalfJung commentedon Jun 26, 2019
@matthewjasper I don't think this is fixed. I am still seeing already-live locals marked as live if I make Miri check for that.
You can see that in this example: the MIR with your patch is
Expand MIR
You can see that there is a
StorageLive(_18)each time around the loop, and no correspondingStorageDead.RalfJung commentedon Jun 26, 2019
In fact, MIR generation in that example does not seem to change at all with your PR.
2 remaining items
RalfJung commentedon Jun 21, 2020
Alive2 is a tool to check LLVM optimizations correct, and it has to give an operational semantics to LLVM IR. What they do for lifetime.start/end is interesting:
This is close to what Miri does, except Miri re-assigns a new block ID and address each time the lifetime of a local ends and starts again. (Compiling from Miri to Alive2 semantics is correct but not the other way around, so we are good.)
Also:
and
aqjune commentedon Jun 22, 2020
Hi, maybe a silly question - is there a reason that Rust emits
StorageLive(_4);at bb0 instead of bb1?I'm wondering whether it makes sense for LLVM to typecheck whether a program has lifetime intrinsics arranged within well-known patterns only. If the usage pattern was too complex, LLVM would already have given up using the pairs for optimization.
RalfJung commentedon Jun 23, 2020
You mean the other way around? It seems to be in bb1.
I'm afraid I do not know why we emit
StorageLivethe way we do. Cc @matthewjaspertmiasko commentedon Nov 21, 2020
The
lifetime.startmarks a stack slot as in-scope, and overwrites it withundef, so a direct translation of the example MIR to LLVM would be correct. BTW, StackColoring, which is primary user of lifetime intrinsics, describes the effects of those intrinsics in more detail than the reference.The MIR now has a
StorageDeadbefore next iteration of the loop, regardless.RalfJung commentedon Nov 21, 2020
Would be good to have the LangRef updated then... where can I read more about StackColoring?
Oh, nice! I'll try to see if I can now adjust
StorageLiveto be UB when called on an already-live stack slot.tmiasko commentedon Nov 21, 2020
https://github.com/rust-lang/llvm-project/blob/ee1617457899ef2eb55dcf7ee2758b4340b6533f/llvm/lib/CodeGen/StackColoring.cpp#L160-L177
RalfJung commentedon Nov 21, 2020
I love the introduction^^
Seems like everyone is very sure what these things do... doesn't make me worried about LLVM as the foundation of Rust at all...^^
RalfJung commentedon Nov 21, 2020
Currently this fails to evaluate many constants; I suspect that is related to @oli-obk's #78679. I'll try again once that landed.
For future reference, this is the branch.
aqjune commentedon Dec 26, 2020
(I'm not sure whether here is a good place to ask this, but) can Rust generate lifetime.start/end with non-zero offset?
I found this old bug report from LLVM bugzilla: https://bugs.llvm.org/show_bug.cgi?id=27999 . Its fix patch shows a simple example.
Rust was fiercely changing at that point; I wonder whether this is still happening.
RalfJung commentedon Dec 26, 2020
Syntactically, the Rust/MIR equivalent of these intrinsics can only be applied to locals, not to a part of a place/local.
However, fixing #71416 might require adding offsets to dynamically-sized alloca to make sure the alignment is right. Not sure if there is a way to make the lifetime intrinsics still refer to the original alloca as opposed to the properly aligned ptr.
aqjune commentedon Dec 29, 2020
Okay, I understood the issue.
I feel like this should be allowed, thanks.