[llvm-dev] Hoisting instructions in presence of Undefined Behaviour

[Stefanos Baziotis via llvm-dev]

Hi,

Just wanted to point out the importance of _non-determinism_, it
confused me when I first learned about it. AFAIU, if the branch was `if (*p
for which we know nothing)` (consider no UB here),
the execution can take any of the two paths. However, in this case there's
no non-determinism and this transformation would be incorrect because there
could be an execution
of the program, for a fixed input, where the original program would not
have UB (it took the return path) while the target program would (it took
the return path as well but it executed
the load unconditionally).

Best,
Stefanos

Στις Τρί, 1 Δεκ 2020 στις 1:34 π.μ., ο/η Nuno Lopes via llvm-dev <
llvm-dev at lists.llvm.org> έγραψε:

> Both transformations are correct, yes. See here:
> https://alive2.llvm.org/ce/z/EpqCUT
> https://alive2.llvm.org/ce/z/yyj9TQ
>
> For a fixed input, if the source triggers UB for *at least one* set of
> chosen non-deterministic values (e.g., undef, freeze), then the source is
> declared UB for that input. So you can optimize it away to UB.
>
> Nuno
>
> -----Original Message-----
> From: Anna Thomas
> Sent: Monday, November 30, 2020 10:45 PM
> Subject: [llvm-dev] Hoisting instructions in presence of Undefined
> Behaviour
>
> We’d like to clarify whether the following transform is valid. Given the
> code:
> ```
> if (freeze(undef))
>    return
> UB
> ```
>
> Can we hoist the UB above the `if` block:
> ```
> UB
> if (freeze(undef))
>   return
> ```
>
> The reasoning is that:
> 1. We were already having undefined behaviour in the code initially. `if
> freeze(undef)` evaluates to true or false. So, a valid execution of the
> program will fall through the `if` block and execute the UB.
> 2. Given #1, hoisting a UB to above the `if` block is valid.
>
>
> Taking this one step further, if the program was:
> ```
> if (freeze(undef))
>   return
> load
> ```
> Can we hoist the load over the if-block? I think we can.
>
> The `if freeze(undef)` being taken or not is independent of any other
> program variables and the compiler is free to refine the code into one
> where
> the if block is not taken.
> So, although the load is not guaranteedToExecute, we know that the
> execution
> of the load is not actually control dependent on the branch.
>
> Anything incorrect with the above transforms?
>
>
> Thanks,
> Anna
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201201/5e413ee8/attachment.html>