Thanks Daniel! I think you've cleared up some of my misconceptions, but I still am a bit confused about some of the corner cases. Suppose we had something like this std::vector<int> A(100);> int* x,y; > x=&A[0]; >for(int i=0; i<100; i++) {> y=&A[i]; > *y=*x; > x=&A[i+1]; > } >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. 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. I'm also a bit unclear how this case would be handled: std::vector<int> A(100);> int* x,y; > x=&A[0]; >for(int i=0; i<100; i++) {> A[i]=5; > } > int z=A[2]; >MayAlias? MustAlias? NeverAlias? It depends on which dynamic instructions the semantics refer to. Thank you, Jeremy On Wed, Aug 13, 2014 at 5:22 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> On Wed, Aug 13, 2014 at 1:39 PM, Jeremy Salwen <jeremysalwen at gmail.com> > wrote: > > Hello all, > > > > I've read the documentation on alias analysis, and I think I understand > it > > literally, but I just want to be sure, because it seems a bit strange. > > > > As it says on this web page, > > > >> The MayAlias response is used whenever the two pointers might refer to > the > >> same object. > >> > >> The PartialAlias response is used when the two memory objects are known > to > >> be overlapping in some way, but do not start at the same address. > >> > >> The MustAlias response may only be returned if the two memory objects > are > >> guaranteed to always start at exactly the same location. A MustAlias > >> response implies that the pointers compare equal. > > > > Reading this, it seems the "MustAlias" result is exceptionally strong. > Yes. > > > > > Consider this loop > > > >> std::vector<int> A(100); > >> int* x,y; > >> > >> for(int i=0; i<100; i++) { > >> x=&A[i]; > >> y=&A[i]; > >> *y=*x; > >> } > > > > > > Here it seems obvious that the load and store on the last line must > "alias" > > in some sense, but the load and store in fact have different values > between > > different iterations of the loop, so if we interpret "always start at > > exactly the same location" literally, that would mean "mustalias" is > false > I think one of us reads that sentence "wrong" :) > The two memory objects here are "x" and "y". They are guaranteed to > always start at the same location, and are pointer equal. > Thus, they are MustAlias. > I don't think "guaranteed to always start at the same location" meant > "each individual pointer is guaranteed to always have the same value > over the lifetime of the program". If so, must-alias would be a > proxy for loop-invariant + a bunch of other stuff, and you'd be able > to simply do replacement of values if they mustalias. But you can't. > > In LLVM, a MustAlias b does not imply that the values of a and b > individually do not change, but that "a and b" are pointer equal > always. > > > What I describe is how, AFAICT, it is implemented in all of the alias > passes. > For example, SCEVAA, which actually computes the recurrences for these > loop expressions, has this: > // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! > const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr)); > const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr)); > > // If they evaluate to the same expression, it's a MustAlias. > if (AS == BS) return MustAlias; > > > IE if the two recurrences for the pointers are equal, it's a mustalias. > > This should return mustalias for x and y above. > > > > > > Is MustAlias considering only the most recent execution? > > At least as defined, MustAlias should be an invariant that holds over > the lifetime of the program. > This is not a flow-sensitive or context-sensitive result. > > > > Or is it only > > considering within the same iteration of a loop? Does MustAlias use the > > same aliasing model as the other results? > > What do you mean by aliasing model? > > > > > Thank you for clearing this up for me. > > > > Jeremy > > > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140813/7ab5fefe/attachment.html>
On Wed, Aug 13, 2014 at 2:52 PM, Jeremy Salwen <jeremysalwen at gmail.com> wrote:> Thanks Daniel! > > I think you've cleared up some of my misconceptions, but I still am a bit > confused about some of the corner cases. > > Suppose we had something like this > > >> std::vector<int> A(100); >> int* x,y; >> x=&A[0]; >> >> for(int i=0; i<100; i++) { >> y=&A[i]; >> *y=*x; >> x=&A[i+1]; >> } > > > > Would the load and store instructions be MustAlias?Yes. They always have the same pointer value at the point of *y = *x. Though note, in SSA form, you would likely end up with two or three x's (x_1 = &A[0], x_2 = phi(x_1, x_3), x_3 = &A[i+1]), and only mustalias(y, x_2) would be true.> I think what it boils > down to is the distinction between static instructions and dynamic > instructions and how they are handled by alias analysis. > > 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.Right. It's a query about specific loads and stores.> 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.The question is what happens at the point of the load/store. The queries you perform in LLVM are about a specific load and a specific store. At the point of *y = *x, y MUSTALIAS x. There are other points this is not true, but that's not relevant to *this store* and *this load*. There is no generic query mechanism to ask "does this relationship hold over all points of the program" (and if there was, it would return false :P)>I'm also a bit unclear how this case would be handled: > >> std::vector<int> A(100); >> int* x,y; >> x=&A[0]; >> >> for(int i=0; i<100; i++) { >> A[i]=5; >> } >> int z=A[2]; > > > MayAlias? MustAlias? NeverAlias? It depends on which dynamic instructions > the semantics refer to.These are all MayAlias.> > Thank you, > Jeremy > > > On Wed, Aug 13, 2014 at 5:22 PM, Daniel Berlin <dberlin at dberlin.org> wrote: >> >> On Wed, Aug 13, 2014 at 1:39 PM, Jeremy Salwen <jeremysalwen at gmail.com> >> wrote: >> > Hello all, >> > >> > I've read the documentation on alias analysis, and I think I understand >> > it >> > literally, but I just want to be sure, because it seems a bit strange. >> > >> > As it says on this web page, >> > >> >> The MayAlias response is used whenever the two pointers might refer to >> >> the >> >> same object. >> >> >> >> The PartialAlias response is used when the two memory objects are known >> >> to >> >> be overlapping in some way, but do not start at the same address. >> >> >> >> The MustAlias response may only be returned if the two memory objects >> >> are >> >> guaranteed to always start at exactly the same location. A MustAlias >> >> response implies that the pointers compare equal. >> > >> > Reading this, it seems the "MustAlias" result is exceptionally strong. >> Yes. >> >> > >> > Consider this loop >> > >> >> std::vector<int> A(100); >> >> int* x,y; >> >> >> >> for(int i=0; i<100; i++) { >> >> x=&A[i]; >> >> y=&A[i]; >> >> *y=*x; >> >> } >> > >> > >> > Here it seems obvious that the load and store on the last line must >> > "alias" >> > in some sense, but the load and store in fact have different values >> > between >> > different iterations of the loop, so if we interpret "always start at >> > exactly the same location" literally, that would mean "mustalias" is >> > false >> I think one of us reads that sentence "wrong" :) >> The two memory objects here are "x" and "y". They are guaranteed to >> always start at the same location, and are pointer equal. >> Thus, they are MustAlias. >> I don't think "guaranteed to always start at the same location" meant >> "each individual pointer is guaranteed to always have the same value >> over the lifetime of the program". If so, must-alias would be a >> proxy for loop-invariant + a bunch of other stuff, and you'd be able >> to simply do replacement of values if they mustalias. But you can't. >> >> In LLVM, a MustAlias b does not imply that the values of a and b >> individually do not change, but that "a and b" are pointer equal >> always. >> >> >> What I describe is how, AFAICT, it is implemented in all of the alias >> passes. >> For example, SCEVAA, which actually computes the recurrences for these >> loop expressions, has this: >> // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! >> const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr)); >> const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr)); >> >> // If they evaluate to the same expression, it's a MustAlias. >> if (AS == BS) return MustAlias; >> >> >> IE if the two recurrences for the pointers are equal, it's a mustalias. >> >> This should return mustalias for x and y above. >> >> >> > >> > Is MustAlias considering only the most recent execution? >> >> At least as defined, MustAlias should be an invariant that holds over >> the lifetime of the program. >> This is not a flow-sensitive or context-sensitive result. >> >> >> > Or is it only >> > considering within the same iteration of a loop? Does MustAlias use the >> > same aliasing model as the other results? >> >> What do you mean by aliasing model? >> >> > >> > Thank you for clearing this up for me. >> > >> > Jeremy >> > >> > _______________________________________________ >> > LLVM Developers mailing list >> > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > > >
Hey Daniel, 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. 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.. Perhaps someone else could clear the confusion, because I feel like there is a gap of communication. For example, in this code what would the result be for the first store and the first load? #include <cstdio>> #include <cstdlib> > int main(int c, char** argv) { > int* A=(int*)malloc(100*sizeof(int)); > > if(c>1) { > for(int i=0; i<5; i++) { > A[i]=5; > } > } else { > A[1]=5; > } > printf("%d\n",A[4]); > free(A); > } >MustAlias? Because whenever they are executed, they do alias. Or MayAlias? Jeremy On Wed, Aug 13, 2014 at 7:31 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> On Wed, Aug 13, 2014 at 2:52 PM, Jeremy Salwen <jeremysalwen at gmail.com> > wrote: > > Thanks Daniel! > > > > I think you've cleared up some of my misconceptions, but I still am a bit > > confused about some of the corner cases. > > > > Suppose we had something like this > > > > > >> std::vector<int> A(100); > >> int* x,y; > >> x=&A[0]; > >> > >> for(int i=0; i<100; i++) { > >> y=&A[i]; > >> *y=*x; > >> x=&A[i+1]; > >> } > > > > > > > > Would the load and store instructions be MustAlias? > Yes. They always have the same pointer value at the point of *y = *x. > Though note, in SSA form, you would likely end up with two or three > x's (x_1 = &A[0], x_2 = phi(x_1, x_3), x_3 = &A[i+1]), and only > mustalias(y, x_2) would be true. > > > > I think what it boils > > down to is the distinction between static instructions and dynamic > > instructions and how they are handled by alias analysis. > > > > 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. > > Right. It's a query about specific loads and stores. > > > 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. > > The question is what happens at the point of the load/store. The > queries you perform in LLVM are about a specific load and a specific > store. > > At the point of *y = *x, y MUSTALIAS x. > There are other points this is not true, but that's not relevant to > *this store* and *this load*. > > There is no generic query mechanism to ask "does this relationship > hold over all points of the program" (and if there was, it would > return false :P) > > >I'm also a bit unclear how this case would be handled: > > > >> std::vector<int> A(100); > >> int* x,y; > >> x=&A[0]; > >> > >> for(int i=0; i<100; i++) { > >> A[i]=5; > >> } > >> int z=A[2]; > > > > > > MayAlias? MustAlias? NeverAlias? It depends on which dynamic > instructions > > the semantics refer to. > These are all MayAlias. > > > > > > Thank you, > > Jeremy > > > > > > On Wed, Aug 13, 2014 at 5:22 PM, Daniel Berlin <dberlin at dberlin.org> > wrote: > >> > >> On Wed, Aug 13, 2014 at 1:39 PM, Jeremy Salwen <jeremysalwen at gmail.com> > >> wrote: > >> > Hello all, > >> > > >> > I've read the documentation on alias analysis, and I think I > understand > >> > it > >> > literally, but I just want to be sure, because it seems a bit strange. > >> > > >> > As it says on this web page, > >> > > >> >> The MayAlias response is used whenever the two pointers might refer > to > >> >> the > >> >> same object. > >> >> > >> >> The PartialAlias response is used when the two memory objects are > known > >> >> to > >> >> be overlapping in some way, but do not start at the same address. > >> >> > >> >> The MustAlias response may only be returned if the two memory objects > >> >> are > >> >> guaranteed to always start at exactly the same location. A MustAlias > >> >> response implies that the pointers compare equal. > >> > > >> > Reading this, it seems the "MustAlias" result is exceptionally strong. > >> Yes. > >> > >> > > >> > Consider this loop > >> > > >> >> std::vector<int> A(100); > >> >> int* x,y; > >> >> > >> >> for(int i=0; i<100; i++) { > >> >> x=&A[i]; > >> >> y=&A[i]; > >> >> *y=*x; > >> >> } > >> > > >> > > >> > Here it seems obvious that the load and store on the last line must > >> > "alias" > >> > in some sense, but the load and store in fact have different values > >> > between > >> > different iterations of the loop, so if we interpret "always start at > >> > exactly the same location" literally, that would mean "mustalias" is > >> > false > >> I think one of us reads that sentence "wrong" :) > >> The two memory objects here are "x" and "y". They are guaranteed to > >> always start at the same location, and are pointer equal. > >> Thus, they are MustAlias. > >> I don't think "guaranteed to always start at the same location" meant > >> "each individual pointer is guaranteed to always have the same value > >> over the lifetime of the program". If so, must-alias would be a > >> proxy for loop-invariant + a bunch of other stuff, and you'd be able > >> to simply do replacement of values if they mustalias. But you can't. > >> > >> In LLVM, a MustAlias b does not imply that the values of a and b > >> individually do not change, but that "a and b" are pointer equal > >> always. > >> > >> > >> What I describe is how, AFAICT, it is implemented in all of the alias > >> passes. > >> For example, SCEVAA, which actually computes the recurrences for these > >> loop expressions, has this: > >> // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! > >> const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr)); > >> const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr)); > >> > >> // If they evaluate to the same expression, it's a MustAlias. > >> if (AS == BS) return MustAlias; > >> > >> > >> IE if the two recurrences for the pointers are equal, it's a mustalias. > >> > >> This should return mustalias for x and y above. > >> > >> > >> > > >> > Is MustAlias considering only the most recent execution? > >> > >> At least as defined, MustAlias should be an invariant that holds over > >> the lifetime of the program. > >> This is not a flow-sensitive or context-sensitive result. > >> > >> > >> > Or is it only > >> > considering within the same iteration of a loop? Does MustAlias use > the > >> > same aliasing model as the other results? > >> > >> What do you mean by aliasing model? > >> > >> > > >> > Thank you for clearing this up for me. > >> > > >> > Jeremy > >> > > >> > _______________________________________________ > >> > LLVM Developers mailing list > >> > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > >> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >> > > > > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140813/d2aa990b/attachment.html>