<div dir="ltr">Hi,<div><br></div><div>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),</div><div>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</div><div>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</div><div>the load unconditionally).</div><div><br></div><div>Best,<br>Stefanos</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Τρί, 1 Δεκ 2020 στις 1:34 π.μ., ο/η Nuno Lopes via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> έγραψε:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Both transformations are correct, yes. See here:<br>
<a href="https://alive2.llvm.org/ce/z/EpqCUT" rel="noreferrer" target="_blank">https://alive2.llvm.org/ce/z/EpqCUT</a><br>
<a href="https://alive2.llvm.org/ce/z/yyj9TQ" rel="noreferrer" target="_blank">https://alive2.llvm.org/ce/z/yyj9TQ</a><br>
<br>
For a fixed input, if the source triggers UB for *at least one* set of <br>
chosen non-deterministic values (e.g., undef, freeze), then the source is <br>
declared UB for that input. So you can optimize it away to UB.<br>
<br>
Nuno<br>
<br>
-----Original Message----- <br>
From: Anna Thomas<br>
Sent: Monday, November 30, 2020 10:45 PM<br>
Subject: [llvm-dev] Hoisting instructions in presence of Undefined Behaviour<br>
<br>
We’d like to clarify whether the following transform is valid. Given the <br>
code:<br>
```<br>
if (freeze(undef))<br>
   return<br>
UB<br>
```<br>
<br>
Can we hoist the UB above the `if` block:<br>
```<br>
UB<br>
if (freeze(undef))<br>
  return<br>
```<br>
<br>
The reasoning is that:<br>
1. We were already having undefined behaviour in the code initially. `if <br>
freeze(undef)` evaluates to true or false. So, a valid execution of the <br>
program will fall through the `if` block and execute the UB.<br>
2. Given #1, hoisting a UB to above the `if` block is valid.<br>
<br>
<br>
Taking this one step further, if the program was:<br>
```<br>
if (freeze(undef))<br>
  return<br>
load<br>
```<br>
Can we hoist the load over the if-block? I think we can.<br>
<br>
The `if freeze(undef)` being taken or not is independent of any other <br>
program variables and the compiler is free to refine the code into one where <br>
the if block is not taken.<br>
So, although the load is not guaranteedToExecute, we know that the execution <br>
of the load is not actually control dependent on the branch.<br>
<br>
Anything incorrect with the above transforms?<br>
<br>
<br>
Thanks,<br>
Anna <br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>