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

[Anna Thomas via llvm-dev]

Thanks. I missed that we could use alive to prove these kinds of transforms!


Anna
On Nov 30, 2020, at 6:40 PM, Stefanos Baziotis <stefanos.baziotis at gmail.com<mailto:stefanos.baziotis at gmail.com>> wrote:

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<mailto: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<mailto: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/bc23a4aa/attachment.html>