<div dir="ltr"><div><div>Thanks Daniel!<br><br></div>I think you've cleared up some of my misconceptions, but I still am a bit confused about some of the corner cases.<br><br></div>Suppose we had something like this<br>
<br><br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
<div><div>std::vector<int> A(100); <br></div><div>int* x,y;<br></div><div>x=&A[0];<br></div></div></blockquote><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
<div><div>for(int i=0; i<100; i++) {<br> y=&A[i];<br> *y=*x; <br> x=&A[i+1];<br>}<br></div></div></blockquote><br><div><br></div><div>Would the load and store instructions be MustAlias? I think what it boils down to is the distinction between static instructions and dynamic instructions and how they are handled by alias analysis.<br>
<br></div><div>I originally interpreted MustAlias as saying /all/ dynamic instructions A must alias with /all/ dynamic instructions B. However, you're saying that this is not the case. So it seems to me that instead we are only checking if certain dynamic instructions alias. It's not clear to me how the dynamic instructions are matched up. For example, in the above code, you could match up the instructions by execution count, and find that they never alias. Or you could match up each dynamic load with the most recent dynamic store, in which case they May/Must alias (depending on how you look at it). This is what I mean by aliasing model.<br>
<br></div><div>I'm also a bit unclear how this case would be handled:<br><br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
<div><div>std::vector<int> A(100); <br></div><div>int* x,y;<br></div><div>x=&A[0];<br></div></div></blockquote><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
<div><div>for(int i=0; i<100; i++) {<br> A[i]=5;<br>} <br></div><div>int z=A[2];<br></div></div></blockquote><div><br></div>MayAlias? MustAlias? NeverAlias? It depends on which dynamic instructions the semantics refer to.<br>
</div><div><br></div><div>Thank you,<br>Jeremy</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Aug 13, 2014 at 5:22 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="">On Wed, Aug 13, 2014 at 1:39 PM, Jeremy Salwen <<a href="mailto:jeremysalwen@gmail.com">jeremysalwen@gmail.com</a>> wrote:<br>
> Hello all,<br>
><br>
> I've read the documentation on alias analysis, and I think I understand it<br>
> literally, but I just want to be sure, because it seems a bit strange.<br>
><br>
> As it says on this web page,<br>
><br>
>> The MayAlias response is used whenever the two pointers might refer to the<br>
>> same object.<br>
>><br>
>> The PartialAlias response is used when the two memory objects are known to<br>
>> be overlapping in some way, but do not start at the same address.<br>
>><br>
>> The MustAlias response may only be returned if the two memory objects are<br>
>> guaranteed to always start at exactly the same location. A MustAlias<br>
>> response implies that the pointers compare equal.<br>
><br>
> Reading this, it seems the "MustAlias" result is exceptionally strong.<br>
</div>Yes.<br>
<div class=""><br>
><br>
> Consider this loop<br>
><br>
>> std::vector<int> A(100);<br>
>> int* x,y;<br>
>><br>
>> for(int i=0; i<100; i++) {<br>
>> x=&A[i];<br>
>> y=&A[i];<br>
>> *y=*x;<br>
>> }<br>
><br>
><br>
> Here it seems obvious that the load and store on the last line must "alias"<br>
> in some sense, but the load and store in fact have different values between<br>
> different iterations of the loop, so if we interpret "always start at<br>
> exactly the same location" literally, that would mean "mustalias" is false<br>
</div>I think one of us reads that sentence "wrong" :)<br>
The two memory objects here are "x" and "y". They are guaranteed to<br>
always start at the same location, and are pointer equal.<br>
Thus, they are MustAlias.<br>
I don't think "guaranteed to always start at the same location" meant<br>
"each individual pointer is guaranteed to always have the same value<br>
over the lifetime of the program". If so, must-alias would be a<br>
proxy for loop-invariant + a bunch of other stuff, and you'd be able<br>
to simply do replacement of values if they mustalias. But you can't.<br>
<br>
In LLVM, a MustAlias b does not imply that the values of a and b<br>
individually do not change, but that "a and b" are pointer equal<br>
always.<br>
<br>
<br>
What I describe is how, AFAICT, it is implemented in all of the alias passes.<br>
For example, SCEVAA, which actually computes the recurrences for these<br>
loop expressions, has this:<br>
// This is ScalarEvolutionAliasAnalysis. Get the SCEVs!<br>
const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr));<br>
const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr));<br>
<br>
// If they evaluate to the same expression, it's a MustAlias.<br>
if (AS == BS) return MustAlias;<br>
<br>
<br>
IE if the two recurrences for the pointers are equal, it's a mustalias.<br>
<br>
This should return mustalias for x and y above.<br>
<div class=""><br>
<br>
><br>
> Is MustAlias considering only the most recent execution?<br>
<br>
</div>At least as defined, MustAlias should be an invariant that holds over<br>
the lifetime of the program.<br>
This is not a flow-sensitive or context-sensitive result.<br>
<div class=""><br>
<br>
> Or is it only<br>
> considering within the same iteration of a loop? Does MustAlias use the<br>
> same aliasing model as the other results?<br>
<br>
</div>What do you mean by aliasing model?<br>
<div class=""><br>
><br>
> Thank you for clearing this up for me.<br>
><br>
> Jeremy<br>
><br>
</div>> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
><br>
</blockquote></div><br></div>