<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Jul 16, 2017 at 2:58 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.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"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="gmail-h5">On Sun, Jul 16, 2017 at 2:34 PM, Nuno Lopes <span dir="ltr"><<a href="mailto:nunoplopes@sapo.pt" target="_blank">nunoplopes@sapo.pt</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"><div class="gmail-m_-6315228819239687214HOEnZb"><div class="gmail-m_-6315228819239687214h5"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
On Sun, Jul 16, 2017, 12:45 PM Nuno Lopes wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
On 07/15/2017 04:51 AM, Nuno Lopes wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
On 07/14/2017 04:37 PM, Nuno Lopes wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Thank you all for your replies.<br>
So here seems to be an agreement that the documentation for<br>
PartialAlias is incorrect.<br>
<br>
Daniel: now you got me wondering about MustAlias. This is what the<br>
docs say:<br>
"The MustAlias response may only be returned if the two memory<br>
objects are *guaranteed to always start at exactly the same location*"<br>
<br>
This statement is regardless of the access sizes.  For example, in<br>
SCEV AA:<br>
// If they evaluate to the same expression, it's a MustAlias.<br>
if (AS == BS)<br>
 return MustAlias;<br>
<br>
AS/BS are scev expressions for the pointers. So no check for the<br>
access size.<br>
<br>
So, does must needs to check for access sizes?  If so, SCEV AA is<br>
buggy and the documentation needs tweaking.<br>
</blockquote>
<br>
I'm under the impression that there is code that depends on the size<br>
check, but I don't trust my recollection in this regard. SCEV AA is<br>
known to cause miscompiles, IIRC, maybe you just found out why ;)<br>
</blockquote>
<br>
It's true that the CFL AAs have this code:<br>
if (LocA.Ptr == LocB.Ptr)<br>
 return LocA.Size == LocB.Size ? MustAlias : PartialAlias;<br>
<br>
<br>
I grepped for clients of MustAlias:<br>
~/llvm/lib/Transforms $ grep -Rl MustAlias .<br>
./ObjCARC/ObjCARCOpts.cpp<br>
./ObjCARC/ProvenanceAnalysis.c<wbr>pp<br>
./Scalar/DeadStoreElimination.<wbr>cpp<br>
./Scalar/GVN.cpp<br>
./Scalar/LICM.cpp<br>
./Scalar/LoopVersioningLICM.cp<wbr>p<br>
./Scalar/MemCpyOptimizer.cpp<br>
./Scalar/MergedLoadStoreMotion<wbr>.cpp<br>
./Scalar/NewGVN.cpp<br>
./Utils/VNCoercion.cpp<br>
<br>
I glanced over all the uses in these files and I couldn't find any<br>
usage that requires sizes to match.  Actually most clients check<br>
access sizes themselves. Most don't need equal sizes, just need one to<br>
be smaller than the other.<br>
</blockquote>
<br>
Does aliasing actually check both ways?<br>
Otherwise, alias (A, B) will give different results than alias (B, A).<br>
</blockquote>
<br>
Sorry for the delay.<br>
I'm not sure I understood what you wrote, sorry.  What you wrote is true in<br>
general, but I don't see how MustAlias in particular is worse than the other<br>
AA results.<br>
</blockquote>
<br>
Historically, in llvm, we have guaranteed that alias(a, b) ==alias(b, a)<br>
<br>
If it does:<br>
<br>
If start (a) == start (b)<br>
  If size(b) < size(a)<br>
      Return mustalias<br>
  Return may or partial<br>
<br>
It will give different answers for alias(a, b) and alias (b, a)<br>
</blockquote>
<br></div></div>
Wait, but the size check is done in the clients, not in AA.<br>
AA only does (according to my understanding):<span class="gmail-m_-6315228819239687214im gmail-m_-6315228819239687214HOEnZb"><br>
<br>
If start (a) == start (b)<br></span><div class="gmail-m_-6315228819239687214HOEnZb"><div class="gmail-m_-6315228819239687214h5">
    Return mustalias<br>
Return may or partial<br>
<br></div></div></blockquote><div><br></div></div></div><div>That seems ... wrong to me, but i haven't thought very hard about it.</div></div></div></div></blockquote><div><br></div><div>In particular, this would mean the documentation for partialalias *is* correct :P.</div><div>IE it will only return partial if the starting addresses are not the same.<br></div><div><br></div><div>I actually would have expected something like:<br><br></div><div>if start(a) == start (b):</div><div>  if sizes equal:</div><div>    return mustalias</div><div>  else:</div><div>    return partialalias</div><div>if otherwise overlap</div><div>   return partial</div><div>return may</div><div><br></div><div>That said, i feel like both our existing code is trying to encode too much info into these simple enum answers.</div><div><br></div><div>Maybe we should really be having something like:<br><br></div><div>enum aliaskind {<br></div><div>MustAlias,  // Exactly the same start and size</div><div>PartialAliasSameStart, </div><div>PartialAlias,</div><div>Mayalias</div><div>}<br>enum overlapkind {</div><div>FullOverlap, // Either the accesses are the same size, or one fully covers the other</div><div>PartialOverlap, // They partially cover each other</div><div>Unknown // No idea</div><div>}</div><div><br></div><div>std::pair<aliaskind, overlapkind> alias(A, B) {</div><div>if (start(A) == start(B))</div><div>  if sizes unknown:</div><div>     return {PartialAliasSameStart, Unknown}</div><div>  if sizes equal:</div><div>     return {MustAlias, FullOverlap}</div><div>  if one smaller than the other</div><div>     return {PartialAliasSameStart, FullOverlap}</div><div>etc</div><div><br></div><div>Then we don't have to muck around in the definitions of must/partial/may too much, and the clients don't have to do too much when, for example, the CSE/DSE like ones really want to know either "are these accessing exactly the same memory location" *or* "can i eliminate this load/store in favor of of an earlier/later one, maybe with some masking".</div><div><br></div><div>But maybe this doesn't need cleaning up.</div><div><br></div><div> </div><div><br></div><div><br></div><div> </div></div><br></div></div>