incorrect transformation around icmp: unclear semantics of "lifetime" intrinsics leads to miscompilation

[RalfJung]

Bugzilla Link	46380
Version	trunk
OS	Linux
CC	@comex,@efriedma-quic,@hfinkel,@jdoerfert,@dobbelaj-snps,@aqjune,@LebedevRI,@Meinersbur,@nunoplopes,@rotateright

Extended Description

(Bugzilla made me pick a component, so I made a wild guess. I do not have the slightest idea which of these internal LLVM components is responsible here. Would be nice if I could select "unknown"...)

In #33896 #c99, Eli Friedman wrote

icmp is defined to just take the raw pointer bits as an integer.
If some transform isn't consistent with this, please file a bug.

I think Juneyoung found a transformation that is indeed not consistent with this, which I adjusted as follows (https://godbolt.org/z/XYQ7Vx):

define i1 @compare(i32* %p, i32* %q) {
  %c = icmp eq i32* %p, %q
  ret i1 %c
}
define void @src() {
  %p = alloca i32
  %q = alloca i32
  call void @llvm.lifetime.start.p0i32(i64 1, i32* %p)
  call void @llvm.lifetime.end.p0i32(i64 1, i32* %p)
  call void @llvm.lifetime.start.p0i32(i64 1, i32* %q)
  %c = call i1 @compare(i32* %p, i32* %q)
  br i1 %c, label %A, label %B
A: ; compare() == true
  call void @f(i1 true)
  %c2 = icmp eq i32* %p, %q
  call void @f(i1 %c2)
  br label %EXIT
B: ; compare() == false
  call void @f(i1 false)
  %c3 = icmp eq i32* %p, %q
  call void @f(i1 %c3)
  br label %EXIT
EXIT:
  call void @llvm.lifetime.end.p0i32(i64 1, i32* %q)
  ret void
}

The function "src" compares "p" and "q" twice, once inside "compare". It calls "f" twice with the two results of the comparison. The first comparison is passed via indirect information flow, i.e., the equivalent of "if p == q { f(true) } else { f(false) }" in Rust. "p" and "q" could be equal or not, so this function has two possible executions: either "f" gets called twice with "true" as argument, or it gets called twice with "false" as argument.

The transformed program (with "opt -instsimplify") is

define i1 @compare(i32* %p, i32* %q) {
  %c = icmp eq i32* %p, %q
  ret i1 %c
}
define void @src() {
  %p = alloca i32, align 4
  %q = alloca i32, align 4
  call void @llvm.lifetime.start.p0i32(i64 1, i32* %p)
  call void @llvm.lifetime.end.p0i32(i64 1, i32* %p)
  call void @llvm.lifetime.start.p0i32(i64 1, i32* %q)
  %c = call i1 @compare(i32* %p, i32* %q)
  br i1 %c, label %A, label %B
A:                                                ; preds = %0
  call void @f(i1 true)
  call void @f(i1 false)
  br label %EXIT
B:                                                ; preds = %0
  call void @f(i1 false)
  call void @f(i1 false)
  br label %EXIT
EXIT:                                             ; preds = %B, %A
  call void @llvm.lifetime.end.p0i32(i64 1, i32* %q)
  ret void
}

Notice how in block A, "f" gets called with two different values, which should be impossible because the original program only calls f with two times the same value.

[Meinersbur]

Since %p and %q are different allocas, they will have two different values, including different integer representations (both alloca are 4 bytes).

InstCombine is making the deduction

%p = alloca i32, align 4
%q = alloca i32, align 4
%c2 = icmp eq i32* %p, %q

to

%c2 = false

because of this. It does not change the compare function because InstCombine is not interprocedural.

The basic block A is dead code, it will never be executed. Dead code can be arbitrarily wrong.

[RalfJung]

The alloca have disjoint lifetimes. That means LLVM may actually allocate them to the same stack slot.

[efriedma-quic]

I think the issue you're talking about is something like the following?

void z(long*);
int a() { 
    long raddr1, raddr2;
    {
       long r; z(&r); raddr1 = (long)&r;
    }
    {
       long r; z(&r); raddr2 = (long)&r;
    }
    return raddr1 == raddr2;
}

clangs allocate the two versions of "r" at the same address, but folds the compare to "false".

This isn't really an integer icmp vs. pointer icmp thing; it's more of a "our representation of local variable lifetimes is wrong" thing.

Interestingly, both gcc and msvc do the same thing.

[Meinersbur]

The alloca have disjoint lifetimes. That means LLVM may actually allocate
them to the same stack slot.

Correct, I missed that. However, I wonder why/whether it is legal to shorten the lifetime even though the pointers are still used for the compare call.

I case of Eli's example, I think C++20 justifies it in http://eel.is/c++draft/basic.stc#4:

When the end of the duration of a region of storage is reached, the values of all pointers representing the address of any part of that region of storage become invalid pointer values. Indirection through an invalid pointer value and passing an invalid pointer value to a deallocation function have undefined behavior. Any other use of an invalid pointer value has implementation-defined behavior.

Note that all compilers optimize the function even without the ptr2int cast:
https://godbolt.org/z/MDp3Ut

[efriedma-quic]

The alloca have disjoint lifetimes. That means LLVM may actually allocate
them to the same stack slot.

Correct, I missed that. However, I wonder why/whether it is legal to shorten
the lifetime even though the pointers are still used for the compare call.

If you're talking about C/C++ variables, the lifetime is defined by the standard. In my example, the two variables aren't live at the same time, so the addresses may or may not be numerically equal. (The problem is just the contradiction.) If two variables are live at the same time, the addresses must not be numerically equal.

If you're talking about the semantics of LLVM, according to the LangRef, two allocas can't have the same address. The rules for alloca specify that the memory is not freed until the function returns. And the rules for llvm.lifetime.start/end don't say anything about the address, only that accessing the memory is undefined outside the lifetime. Therefore, it's illegal for stack coloring to allocate two variables whose address escapes at the same address.

Obviously stack coloring does in fact allocate variables at the same address. And we can't fix it to match LangRef without causing a significant regression for C++ code.

I case of Eli's example, I think C++20 justifies it in
http://eel.is/c++draft/basic.stc#4:

raddr1 and raddr2 are pointers, not integers; the rule in question doesn't apply.

[efriedma-quic]

=

raddr1 and raddr2 are pointers, not integers; the rule in question doesn't
apply.

Somehow got this backwards; meant to say "integers, not pointers".

[RalfJung]

I think the issue you're talking about is something like the following?

Not sure if "you" is me here, but I agree that is a similar example -- z could observe the two addresses and so we have a contradiction, like in my example.

(The problem is just the contradiction.)

Agreed: whether or not the addresses are equal is non-deterministic. That's why I said my example has two possible executions. It's just, "f(true); f(false);" is not one of them.

raddr1 and raddr2 are integers, not pointers; the rule in question doesn't apply.

The rule in question is a C++ rule, so it applies to Eli's example, but AFAIK LLVM has no such rule and thus it does not apply to my example. Is that not right?

If you're talking about the semantics of LLVM, according to the LangRef, two allocas can't have the same address.
The rules for alloca specify that the memory is not freed until the function returns. And the rules for llvm.lifetime.start/end don't say anything about the address, only that
accessing the memory is undefined outside the lifetime. Therefore, it's illegal for stack coloring to allocate two variables whose address escapes at the same address.

Oh, that is surprising. Why would LLVM explicitly say that about alloca and not about malloc? And what about popping and then pushing the same stack frame, so that a stack slot ends up at the same physical address -- that would also be two allocas with the same address (just different in provenance, similar to malloc reusing memory), why is that not a problem?

I thought the entire point of these lifetime annotations was to let LLVM re-use the same stack slots for different variables, and this rule seems to make that unnecessarily hard.

according to the LangRef, two allocas can't have the same address.
All I could find in the LangRef is
Allocating zero bytes is legal, but the returned pointer may not be unique.
But this doesn't say that otherwise, it is unique.

I wonder if it would be possible to adjust lifetime.end semantics to say that this may (or may not) free the memory for that alloca, to permit reusing addresses.

[efriedma-quic]

Oh, that is surprising. Why would LLVM explicitly say that about alloca and
not about malloc?

malloc'ed memory is allocated until you call free(), according to the C standard. This is a similar thing, except that it's freed implicitly when the function returns. To be clear, I only mean allocas which are live at the same time; obviously later function calls can reuse the same stack.

(For dynamic allocas, there's also stacksave/stackrestore; a stackrestore also frees memory. But those are pretty rare in most code.)

according to the LangRef, two allocas can't have the same address.
All I could find in the LangRef is
Allocating zero bytes is legal, but the returned pointer may not be unique.
But this doesn't say that otherwise, it is unique.

I think it's implied by "allocating" memory; two allocations can't overlap. This roughly matches the semantics of the languages we're trying to model.

I wonder if it would be possible to adjust lifetime.end semantics to say
that this may (or may not) free the memory for that alloca, to permit
reusing addresses.

Maybe. It would be pretty inconvenient to reason about, since the uses of the memory aren't tied to the actual allocation. And it would be difficult to describe the rules in an intuitive way. But I can't think of any showstoppers.

[RalfJung]

To be clear, I only mean allocas which are live at the same time; obviously
later function calls can reuse the same stack.

These are not live at the same time though? I do not recall the exact wording, but as far as I know C does not require local variables to be live for the entire function; when they are declared in a sub-scope like in your example, they can be deallocated earlier.

So given that LLVM encodes these source-level scopes into its IR using lifetime.start/end, it seems odd to say that allocas are "freed implicitly when the function returns". It seems more useful, and closer to C, to instead say they are "freed implicitly when their lifetime ends". This also reflects what stack coloring is doing.

I think it's implied by "allocating" memory; two allocations can't overlap.
This roughly matches the semantics of the languages we're trying to model.

In my mental model, an "alloca" is only really allocated once it becomes live (lifetime.start), and it gets deallocated when its live range ends. LLVM does not have "scopes"/"blocks" like C or many other source languages do, so what should those languages do when they want stack variables to be allocated only when their scope begins, and deallocated when their scope ends (which I think is common)? They add lifetime.start/end.

(There is a special case for alloca that don't have lifetime intrinsics associated with those; those are indeed live until the function returns. This does create some nasty corner cases, which has been the subject of discussion in Rust for quite a while, but progress has been hard as it is not very clear what exactly LLVM's requirements are. See e.g. rust-lang/rust#42371.)

[RalfJung]

(I got a sendmail error from the web frontend, re-triggering notifications.)

[RalfJung]

(More email errors.)

[RalfJung]

(There have been posts but no notifications.)

[aqjune]

FYI: In Alive2, the semantics of alloca depends on whether it has lifetime intrisic uses at parsing time. :)
If alloca has any uses with lifetime intrinsics, it is truly allocated at lifetime.start. Before that, it is assigned a block id, but it does not occupy the space and accessing it is UB.
If alloca is not used by any lifetime intrinsics, it is immediately allocated at the definition.
This has worked pretty well so far while testing with LLVM unit tests and running -O3 from a few agglomerated C single programs.

[aqjune]

For more details which might be related with the github link:

• Having lifetime.start twice on the same alloca does not reallocate the block
• Alive2 does not consider executions that has two live allocas (and mallocs of course) have addresses overlapped

[RalfJung]

FYI: In Alive2, the semantics of alloca depends on whether it has lifetime intrisic uses at parsing time. :)

That is funny, this is exactly what Miri also does.^^

If alloca has any uses with lifetime intrinsics, it is truly allocated at lifetime.start. Before that, it is assigned a block id, but it does not occupy the space and accessing it is UB.

Interesting, Miri does not even reserve a block ID. Each new lifetime.start generates a fresh block ID. This models that we want pointers to be invalidated when the lifetime of a local ends, even if the same local becomes live again later. (Compilation from that to Alive2's semantics seems fine, it just restricts allocator choice.)