<div dir="ltr">Note: This is a generic problem with any situation where noalias exists but the pointers are proven equal :)<div>TBAA, for example, has the same generic issue, we just drop the tbaa metadata and declare it okay, even though it would have been UB at the source level.</div><div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 11, 2017 at 3:32 PM, Sanjoy Das via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi all,<br>
<br>
I think I've spotted a semantic issue with marking @malloc and<br>
@realloc as noalias. Say we have the program:<br>
<br>
int f() {<br>
int* p0 = malloc(sizeof(int));<br>
free(p0);<br></blockquote><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
int* p1 = malloc(sizeof(int));<br>
if (!p1) return 20;<br>
int value = 0;<br>
for (int i = 0; i < 1; i++) {<br>
*p1 = 20;<br>
value = *p1;<br>
if (false) // "false" is obscured in a way the compiler can't fathom<br>
if (p0 == p1)<br>
a();<br>
else<br>
b();<br>
}<br>
return result;<br>
}<br>
<br>
The program above is well defined, and will always return 20.<br></blockquote><div><br></div><div>no it won't, you never initialized result :) :) :)</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
However, if we first unswitch loops:<br>
<br>
int f() {<br>
int* p0 = malloc(size of(int));<br>
free(p0);<br>
int* p1 = malloc(sizeof(int));<br>
if (!p1) return 20;<br>
int value = 0;<br>
if (p0 == p1) {<br>
for (int i = 0; i < 1; i++) {<br>
*p1 = 20;<br>
value = *p1;<br>
if (false)<br>
a();<br>
}<br>
} else {<br>
// Other copy of the loop that calls b() in dead code<br>
}<br>
return result;<br>
}<br>
<br>
and then run GVN::propgateEquality that replaces one use of p1 with p0<br>
but not the other (for some reason, say the other use was obscured<br>
behind a function call):<br>
<br>
int f() {<br>
int* p0 = malloc(size of(int));<br>
free(p0);<br>
int* p1 = malloc(sizeof(int));<br>
if (!p1) return 20;<br>
int value = 0;<br>
if (p0 == p1) {<br>
for (int i = 0; i < 1; i++) {<br>
*p0 = 20; // S0<br>
value = *p1; // L0<br>
if (false)<br>
a();<br>
}<br>
} else {<br>
// Other copy of the loop that calls b() in dead code<br>
}<br>
return result;<br>
}<br>
<br>
<br>
Now we have a problem -- since p0 NoAlias p1 (distinct @malloc()<br>
calls), we can reorder S0 and L0 (or LICM L0):<br>
<br>
<br>
int f() {<br>
int* p0 = malloc(size of(int));<br>
free(p0);<br>
int* p1 = malloc(sizeof(int));<br>
if (!p1) return 20;<br>
int value = 0;<br>
if (p0 == p1) {<br>
for (int i = 0; i < 1; i++) {<br>
value = *p1; // L0<br>
*p0 = 20; // S0<br>
if (false)<br>
a();<br>
}<br>
} else {<br>
// Other copy of the loop that calls b() in dead code<br>
}<br>
return result;<br>
}<br>
<br>
and we'll now return garbage if p0 == p1 (likely) and p1 is not null<br>
(also likely).<br></blockquote><div><br></div><div>The free changes p0.</div><div><br></div><div>Otherwise, yes, your fundamental problem is that you are playing games with two different language level objects whose pointers are equal, but it says they do not alias.</div><div>I don't remember who i tried to explain to on irc that this can happen, but they didn't believe me :)</div><div><br></div><div>We have no way of specifying the lifetime has ended, either.</div><div>You can make the problem as hard or as simple as you want above, but you can't solve it in general.</div><div>Even if you wanted to, it is in fact, trivial to come up with cases where basicaa will say no alias for the load/store, but not say noalias at the propagation point.<br></div><div><br>Just put enough copies in between that it hits the various depth or complexity limits and gives up and says mayalias :)</div><div><br></div><div>It would require semantic changes to llvm ir to fix this to properly express object lifetimes that is compatible with all the random babble standards have written down :)</div><div>For now, the only sane solution IMHO, is to say that no alias implies pointer inequality, regardless of the standards. Because the above can occur in any situation noalias exists but they are allowed to be pointer equal (as mentioned, it's trivial to make this happen in TBAA).</div><div><br></div><div>I say sane because you can't actually do anything else and get it right all the time, other than disable noalias in pretty much every case.</div><div><br></div><div>FWIW outside of not propagating when tbaa sets differ, gcc does the same as we do .</div><div>It definitely believes p0 and p1 do not alias in the example above, and would have no trouble propagating them.</div><div>I can't quite get it to optimize it. but it does set the equality p0 == p1, and staring at the pass, it just doesn't bother to simplify the expression, it would, in fact, otherwise propagate.</div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div></div></div></div></div>