<div dir="ltr"><div><div>Hey Daniel,<br><br></div>Thanks again for the help. I'm still a bit confused about the interface to the alias analysis. It seems like we are talking about different interfaces. Has it changed from what the documentation says? As far as I can tell, the documentation takes a specific Value*, and no information about which dynamic execution it is talking about. <br>
<br>When you say "Right. It's a query about specific loads and stores." it sounds like you are saying that it does consider dynamic executions, and that you can make queries about specific dynamic executions. I can't seem to find this option anywhere in the API..<br>
<br></div><div>Perhaps someone else could clear the confusion, because I feel like there is a gap of communication.<br><br></div><div>For example, in this code what would the result be for the first store and the first load?<br>
<br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">#include <cstdio><br>#include <cstdlib><br>int main(int c, char** argv) {<br> int* A=(int*)malloc(100*sizeof(int));<br>
<br> if(c>1) {<br> for(int i=0; i<5; i++) {<br> A[i]=5;<br> }<br> } else {<br> A[1]=5;<br> }<br> printf("%d\n",A[4]);<br> free(A);<br>}<br></blockquote><br></div><div>MustAlias? Because whenever they are executed, they do alias. Or MayAlias?<br>
<br></div><div>Jeremy<br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Aug 13, 2014 at 7:31 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 2:52 PM, Jeremy Salwen <<a href="mailto:jeremysalwen@gmail.com">jeremysalwen@gmail.com</a>> wrote:<br>
> Thanks Daniel!<br>
><br>
> I think you've cleared up some of my misconceptions, but I still am a bit<br>
> confused about some of the corner cases.<br>
><br>
> Suppose we had something like this<br>
><br>
><br>
>> std::vector<int> A(100);<br>
>> int* x,y;<br>
>> x=&A[0];<br>
>><br>
>> for(int i=0; i<100; i++) {<br>
>> y=&A[i];<br>
>> *y=*x;<br>
>> x=&A[i+1];<br>
>> }<br>
><br>
><br>
><br>
> Would the load and store instructions be MustAlias?<br>
</div>Yes. They always have the same pointer value at the point of *y = *x.<br>
Though note, in SSA form, you would likely end up with two or three<br>
x's (x_1 = &A[0], x_2 = phi(x_1, x_3), x_3 = &A[i+1]), and only<br>
mustalias(y, x_2) would be true.<br>
<div class=""><br>
<br>
> I think what it boils<br>
> down to is the distinction between static instructions and dynamic<br>
> instructions and how they are handled by alias analysis.<br>
><br>
> I originally interpreted MustAlias as saying /all/ dynamic instructions A<br>
> must alias with /all/ dynamic instructions B. However, you're saying that<br>
> this is not the case.<br>
<br>
</div>Right. It's a query about specific loads and stores.<br>
<div class=""><br>
> So it seems to me that instead we are only checking if<br>
> certain dynamic instructions alias.<br>
<br>
> It's not clear to me how the dynamic<br>
> instructions are matched up.<br>
<br>
</div>The question is what happens at the point of the load/store. The<br>
queries you perform in LLVM are about a specific load and a specific<br>
store.<br>
<br>
At the point of *y = *x, y MUSTALIAS x.<br>
There are other points this is not true, but that's not relevant to<br>
*this store* and *this load*.<br>
<br>
There is no generic query mechanism to ask "does this relationship<br>
hold over all points of the program" (and if there was, it would<br>
return false :P)<br>
<div class=""><br>
>I'm also a bit unclear how this case would be handled:<br>
><br>
>> std::vector<int> A(100);<br>
>> int* x,y;<br>
>> x=&A[0];<br>
>><br>
>> for(int i=0; i<100; i++) {<br>
>> A[i]=5;<br>
>> }<br>
>> int z=A[2];<br>
><br>
><br>
> MayAlias? MustAlias? NeverAlias? It depends on which dynamic instructions<br>
> the semantics refer to.<br>
</div>These are all MayAlias.<br>
<div class="HOEnZb"><div class="h5"><br>
<br>
><br>
> Thank you,<br>
> Jeremy<br>
><br>
><br>
> On Wed, Aug 13, 2014 at 5:22 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:<br>
>><br>
>> On Wed, Aug 13, 2014 at 1:39 PM, Jeremy Salwen <<a href="mailto:jeremysalwen@gmail.com">jeremysalwen@gmail.com</a>><br>
>> wrote:<br>
>> > Hello all,<br>
>> ><br>
>> > I've read the documentation on alias analysis, and I think I understand<br>
>> > 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<br>
>> >> the<br>
>> >> same object.<br>
>> >><br>
>> >> The PartialAlias response is used when the two memory objects are known<br>
>> >> 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<br>
>> >> 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>
>> Yes.<br>
>><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<br>
>> > "alias"<br>
>> > in some sense, but the load and store in fact have different values<br>
>> > 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<br>
>> > false<br>
>> 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<br>
>> 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>
>><br>
>><br>
>> ><br>
>> > Is MustAlias considering only the most recent execution?<br>
>><br>
>> 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>
>><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>
>> What do you mean by aliasing model?<br>
>><br>
>> ><br>
>> > Thank you for clearing this up for me.<br>
>> ><br>
>> > Jeremy<br>
>> ><br>
>> > _______________________________________________<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>
><br>
><br>
</div></div></blockquote></div><br></div>