llvm dev - Jul 2020 - (When) Do function calls read/latch/freeze their parameters?

Hi,

We're looking at what may be a real-life bug encountered by our
compiler related to `undef` values and function calls.

The input program effectively contains the expression

    clamp(v, x, x)

expecting that the result will be equal to `x`, even when `v` is read
from uninitialized memory. In the input language, `clamp` is a
built-in, so this expectation is somewhat reasonable.

In our compiler, the clamp gets replaced by the logically equivalent
corresponding sequence of icmp/select instructions, which leads to
multiple reads from v, which changes the result when v is undef.

We should be able to fix this in our compiler by inserting a freeze
instruction, but to me this raises a more complicated point around
function inlining that is illustrated by this example:
https://alive2.llvm.org/ce/z/wcYxCB (I don't know if the output of
Alive2 is meaningful here or if there are limitations around function
calls).

Function inlining in LLVM currently does *not* introduce freezes.
However, calls to intrinsics such as llvm.minimum.* etc. are
presumably expected to introduce freezes. So if we think of intrinsics
as being implemented by library functions (as is de facto the case
with the `clamp` example above), should those library functions be
treated differently by inlining? Should such functions be written with
explicit `freeze`s in the beginning? Does this mean it would make
sense to expose `freeze` as an intrinsic accessible from C/C++ in
Clang, so that such library functions can be written in a high-level
language?

As you can see, I unfortunately have more questions than answers right now ;)

Cheers,
Nicolai
-- 
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.

Hi,

Inlining doesn't need to introduce freeze. But each function must know that
they may get inlined. Alive2 proves transformations for "normal" input
values, undef values, poison values, and combinations of these. (we could do
things the other way around: inline adds freeze, functions assume inputs are
"normal", but that is a bit pessimistic, and would likely result in
too many freezes)

I agree that expansions of intrinsics like "llvm.minimum.*" probably
need to introduce freezes if done at IR level. If done at assembly level no, as
there's no LLVM IR-style undef value in assembly. At least not in the ISAs
I'm aware :)
Your clamp should introduce freeze as well.

To remove unneeded freezes, we could tag functions with a no-more-IPOs tag after
the last IPO in the pipeline. Each function could then assume that the input was
non-poison and non-undef. There's a new attribute for arguments under
review, I think name noundef, that may allow us to get rid of undef as well, but
I didn't follow the last proposed semantics closely to be sure.

Nuno

P.S.: Alive2 doesn't support inlining at the moment FYI. Only
intra-procedural optimizations are supported ATM.


-----Original Message-----
From: Nicolai Hähnle
Sent: 13 July 2020 20:58
Subject: [llvm-dev] (When) Do function calls read/latch/freeze their parameters?

Hi,

We're looking at what may be a real-life bug encountered by our compiler
related to `undef` values and function calls.

The input program effectively contains the expression

    clamp(v, x, x)

expecting that the result will be equal to `x`, even when `v` is read from
uninitialized memory. In the input language, `clamp` is a built-in, so this
expectation is somewhat reasonable.

In our compiler, the clamp gets replaced by the logically equivalent
corresponding sequence of icmp/select instructions, which leads to multiple
reads from v, which changes the result when v is undef.

We should be able to fix this in our compiler by inserting a freeze instruction,
but to me this raises a more complicated point around function inlining that is
illustrated by this example:
https://alive2.llvm.org/ce/z/wcYxCB (I don't know if the output of
Alive2 is meaningful here or if there are limitations around function calls).

Function inlining in LLVM currently does *not* introduce freezes.
However, calls to intrinsics such as llvm.minimum.* etc. are presumably expected
to introduce freezes. So if we think of intrinsics as being implemented by
library functions (as is de facto the case with the `clamp` example above),
should those library functions be treated differently by inlining? Should such
functions be written with explicit `freeze`s in the beginning? Does this mean it
would make sense to expose `freeze` as an intrinsic accessible from C/C++ in
Clang, so that such library functions can be written in a high-level language?

As you can see, I unfortunately have more questions than answers right now ;)

Cheers,
Nicolai

On 7/13/20 2:57 PM, Nicolai Hähnle via llvm-dev wrote:
> calls to intrinsics such as llvm.minimum.* etc. are
> presumably expected to introduce freezes.
I can see how lowering/implementing intrinsics might require `freeze` but

as Nuno mentioned, I doubt "inlining" (as in our inliner pass)
requires
this.

On 7/13/20 4:56 PM, Nuno Lopes via llvm-dev wrote:
> There's a new attribute for arguments under review, I think name
noundef,

Was merged: 
https://reviews.llvm.org/rG89f1ad88b3f1ecf32e797247b9eab5662ed4bcf4


```

|noundef|
    This attribute applies to parameters and return values. If the value
    representation contains any undefined or poison bits, the behavior
    is undefined. Note that this does not refer to padding introduced by
    the type’s storage representation.
```


Next step is to make existing attributes not create UB but produce 
poison if violated.

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200714/1ecfa619/attachment.html>

On Tue, Jul 14, 2020 at 10:15 PM Johannes Doerfert
<johannesdoerfert at gmail.com> wrote:
> On 7/13/20 2:57 PM, Nicolai Hähnle via llvm-dev wrote:
> > calls to intrinsics such as llvm.minimum.* etc. are
> > presumably expected to introduce freezes.
>
> I can see how lowering/implementing intrinsics might require `freeze` but
> as Nuno mentioned, I doubt "inlining" (as in our inliner pass)
requires
> this.
Yes, this makes sense to me. Thanks!

Cheers,
Nicolai

-- 
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.