<div dir="ltr">Works for me</div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 22, 2015 at 8:27 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 dir="ltr">We should use graph edges, so we can do something better at set build time :)<br><br></div><div class="HOEnZb"><div class="h5"><br><div class="gmail_quote">On Thu Jan 22 2015 at 5:20:46 PM George Burgess IV <<a href="mailto:george.burgess.iv@gmail.com" target="_blank">george.burgess.iv@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><span style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif;font-size:13px">> Should we be added an edge from the inttoptr to all other pointer values? Is there a better way?</span><br><div class="gmail_extra"><br></div></div><div dir="ltr"><div class="gmail_extra">We can add a special "Unknown" StratifiedAttr and query it before anything else, i.e:</div><div class="gmail_extra"><br></div><div class="gmail_extra">// in CFLAliasAnalysis::query, as the first potential return</div><div class="gmail_extra">if (AttrsA[AttrUnknown] || AttrsB[AttrUnknown])</div><div class="gmail_extra">  return MayAlias;</div><div class="gmail_extra"><br></div><div class="gmail_extra">The only *potential* issue with this approach would be that in the following code segment:</div><div class="gmail_extra"><br></div><div class="gmail_extra">void fn() {</div><div class="gmail_extra">  int *foo = (int*)rand();</div><div class="gmail_extra">  int *bar = new int;</div><div class="gmail_extra">  int **baz = rand() ? &foo : &bar;</div><div class="gmail_extra">  int value = **baz;</div><div class="gmail_extra">}</div><div class="gmail_extra"><br></div><div class="gmail_extra">The stratified sets would look like:</div><div class="gmail_extra">    {value} is below {foo, bar} is below {baz}. </div><div class="gmail_extra"><br></div><div class="gmail_extra">Potential issue: The sets {foo, bar} and {value} would be marked with the "Unknown" attribute, while {baz} would have no attributes. I can't immediately think of a case where {baz} lacking "Unknown" would be harmful, but if such a case exists, then we may need a different approach.</div></div><div dir="ltr"><div class="gmail_extra"><br></div><div class="gmail_extra">George</div></div><div dir="ltr"><div class="gmail_extra"><br></div><div class="gmail_extra"><div class="gmail_quote">On Thu, Jan 22, 2015 at 8:03 PM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)"><hr><br><blockquote><span> From: "Daniel Berlin" <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>><br> To: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br> Cc: "Jiangning Liu" <<a href="mailto:Jiangning.Liu@arm.com" target="_blank">Jiangning.Liu@arm.com</a>>, "George Burgess IV" <<a href="mailto:george.burgess.iv@gmail.com" target="_blank">george.burgess.iv@gmail.com</a>>, "LLVM Developers<br> Mailing List" <<a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a>>, "Nick Lewycky" <<a href="mailto:nlewycky@google.com" target="_blank">nlewycky@google.com</a>><br></span> Sent: Wednesday, January 21, 2015 3:48:25 PM<span><br> Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers<br> <br></span><span> On Wed Jan 21 2015 at 12:30:50 PM Hal Finkel < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> wrote:<br> <br> ----- Original Message -----<br> > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a> ><br> > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com" target="_blank">Jiangning.Liu@arm.com</a> >, "George Burgess IV"<br> > < <a href="mailto:george.burgess.iv@gmail.com" target="_blank">george.burgess.iv@gmail.com</a> >, "LLVM Developers<br> > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a> >, "Nick Lewycky" <<br> > <a href="mailto:nlewycky@google.com" target="_blank">nlewycky@google.com</a> ><br> > Sent: Wednesday, January 21, 2015 1:10:07 PM<br> > Subject: Re: [LLVMdev] question about enabling cfl-aa and<br> > collecting a57 numbers<br> > <br> > Updated testcases to have MayAlias/note issues as FIXME.<br> > <br> <br> Okay, thanks! This LGTM, but we should probably split the delegation<br> fixes from the others and commit as two separate patches (especially<br> because Ana noted some potential miscompiles caused by the other<br> improvements).<br> <br> <br> <br> I think she mentioned the miscompiles due to us returning<br> partialalias. But in any case, i 'm happy to, but just to note they<br> are all required to get the LICM issue fixed :)<br></span></blockquote><br>Okay, please do that and commit them.<span><br><br><blockquote> <br> <br> <br> Regarding this:<br> <br> @@ -768,7 +774,10 @@ static Optional<StratifiedAttr><br> valueToAttrIndex(Value *Val) {<br> return AttrGlobalIndex;<br> <br> if (auto *Arg = dyn_cast<Argument>(Val))<br> - if (!Arg->hasNoAliasAttr())<br> + // Only pointer arguments should have the argument attribute,<br> + // because things can't escape through scalars without us seeing a<br> + // cast, and thus, interaction with them doesn't matter.<br> + if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy())<br> return argNumberToAttrIndex(Arg-> getArgNo());<br> return NoneType();<br> }<br> <br> when we do see the inttoptr case, we add an edge from the source to<br> the destination.<br> <br> <br> Correct.<br> <br> <br> If we've not noted potential aliasing of the non-pointer-typed<br> argument, then does this end up looking like a unique global?<br> <br> <br> <br> No. It will end up looking like something that points to nothing.<br> Even without this change, it will end up looking like something that<br> points to nothing, it will just have an attribute that says<br> "argument". :)<br></blockquote><br></span>Okay, fair enough.<span><br><br><blockquote> <br> <br> You can come up with cases where even with this attribute set, it<br> will get the wrong answer. It just happens to have code that,<br> through luck, gets the right answer in a lot of cases:<br> <br> (That is this code:<br> <br> <br> if (AttrsA.any() && AttrsB.any())<br> return AliasAnalysis::MayAlias;<br> )<br> <br> <br> So there is a bug here, but it's not caused by this code.<br> <br> <br> The bug here is that we can't ever know what happens as the result of<br> inttoptr. We never do math, and the tracking we do is never going to<br> be sufficient to determine the range of possible pointers for an<br> inttoptr in all cases (in theory, it could point to anything<br> anywhere in the program. If we knew the sizes of *all* objects, and<br> any binary operator performed on it was evaluable, we could do a<br> little better. If we knew the value came from a ptrtoint, we could<br> do better, etc).<br> Same with ptrtoint.<br> <br> <br> The result of both of these instructions should start to be "we have<br> no idea what the pointer that comes from inttoptr or goes to<br> ptrtoint points to", and we should return mayalias for anything that<br> interacts with them.<br> We don't do that right now.<br> We are just hiding it mildly well.<br></blockquote><br></span>Should we be added an edge from the inttoptr to all other pointer values? Is there a better way?<span><br><br><blockquote> <br> <br> <br> <br> <br> Speaking of which, the code has checks for global variables in<br> several places. Do these need to be for globals that are not aliases<br> and don't have weak linkage?<br> <br> <br> <br> It's more a question of whether they are in SSA form than if they are<br> globals.<br> <br> <br> It's effectively using Globals/Arguments as a way to say "don't know"<br> in some cases, where it should really just say "don't know".<br> <br> <br> There is a bunch of code i now have marked for cleanup and bugfixes<br> around these issues (constant vs global handling, handling of<br> non-pointer values, etc).<br></blockquote><br></span>Okay, thanks!<span><br><br><blockquote> <br> <br> As mentioned, the above is necessary to fix the LICM issue (and is<br> correct, even if somewhere else is wrong. For reference, GCC does<br> the identical thing to what i'm saying :P), but i'm happy to move it<br> to a separate fix (that includes fixes for the other<br> argument/unknown related issues) if you like.<br> <br> <br></blockquote><br></span>Generically speaking, I'd prefer the fixes to be broken up as much as practical. Please go ahead and commit them.<span><font color="#888888"><br><br> -Hal</font></span><div><div><br><blockquote> <br> <br> <br> <br> <br> <br> Thanks again,<br> Hal<br> <br> > <br> > <br> > <br> > <br> > On Tue Jan 20 2015 at 3:54:10 PM Hal Finkel < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> > wrote:<br> > <br> > <br> > ----- Original Message -----<br> > > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a> ><br> > > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> > > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com" target="_blank">Jiangning.Liu@arm.com</a> >, "George Burgess<br> > > IV"<br> > > < <a href="mailto:george.burgess.iv@gmail.com" target="_blank">george.burgess.iv@gmail.com</a> >, "LLVM Developers<br> > > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a> >, "Nick Lewycky" <<br> > > <a href="mailto:nlewycky@google.com" target="_blank">nlewycky@google.com</a> ><br> > > Sent: Tuesday, January 20, 2015 1:48:44 PM<br> > > Subject: Re: [LLVMdev] question about enabling cfl-aa and<br> > > collecting a57 numbers<br> > > <br> > > So, I can make all these testcases work, but it's a little tricky<br> > > (it<br> > > involves tracking some things, like GEP byte range, and then<br> > > checking bases and using getObjectSize, much like BasicAA does).<br> > > <br> > > <br> > > Because i really don't want to put that much "not well tested"<br> > > code<br> > > in a bugfix, and honestly, i'm not sure we will catch any cases<br> > > here<br> > > that BasicAA does not, i've attached a change to XFAIL these<br> > > testcases, and updated the code to return MayAlias.<br> > <br> > Okay. I think you might as well just update the test cases to want<br> > MayAlias, and put a FIXME comment explaining that they could be<br> > PartialAlias. As far as I know, there is no code in LLVM that<br> > really<br> > handles a PartialAlias differently than a MayAlias or MustAlias,<br> > and<br> > so while there may be some benefit here, I'm not sure it will be<br> > worth the effort.<br> > <br> > > <br> > > I will build and test a patch to get these back to PartialAlias,<br> > > but<br> > > this patch will at least get us to not be "giving wrong answers".<br> > > I<br> > > will also see if we catch anything with it that BasicAA does not,<br> > > because if we don't, it doesn't seem worth it to me.<br> > <br> > My guess is that BasicAA will get almost all of the interesting<br> > PartialAlias cases, and as I said, we essentially ignore them<br> > anyway.<br> > <br> > As a side note, there is this one place in lib/Analysis/<br> > MemoryDependenceAnalysis.cpp that could use some attention:<br> > <br> > #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting<br> > loads<br> > // in terms of clobbering loads, but since it does this by looking<br> > // at the clobbering load directly, it doesn't know about any<br> > // phi translation that may have happened along the way.<br> > <br> > // If we have a partial alias, then return this as a clobber for<br> > the<br> > // client to handle.<br> > if (R == AliasAnalysis::PartialAlias)<br> > return MemDepResult::getClobber(Inst) ;<br> > #endif<br> > <br> > > <br> > > <br> > > Conservative new patch attached.<br> > > <br> > > <br> > > <br> > > (Note that i still updated the testcases, because we will *never*<br> > > be<br> > > able to legally return PartialAlias as they were written)<br> > > <br> > <br> > Yes, sounds good.<br> > <br> > -Hal<br> > <br> > > <br> > > <br> > > <br> > > <br> > > <br> > > <br> > > <br> > > On Sun Jan 18 2015 at 2:12:47 PM Daniel Berlin <<br> > > <a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a><br> > > > wrote:<br> > > <br> > > <br> > > <br> > > On Sat Jan 17 2015 at 3:15:27 PM Hal Finkel < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> > > wrote:<br> > > <br> > > <br> > > ----- Original Message -----<br> > > > From: "Daniel Berlin" < <a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a> ><br> > > > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ><br> > > > Cc: "Jiangning Liu" < <a href="mailto:Jiangning.Liu@arm.com" target="_blank">Jiangning.Liu@arm.com</a> >, "George Burgess<br> > > > IV"<br> > > > < <a href="mailto:george.burgess.iv@gmail.com" target="_blank">george.burgess.iv@gmail.com</a> >, "LLVM Developers<br> > > > Mailing List" < <a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a> >, "Nick Lewycky" <<br> > > > <a href="mailto:nlewycky@google.com" target="_blank">nlewycky@google.com</a> ><br> > > > Sent: Saturday, January 17, 2015 1:08:10 PM<br> > > > Subject: Re: [LLVMdev] question about enabling cfl-aa and<br> > > > collecting a57 numbers<br> > > > <br> > > > <br> > > > <br> > > > <br> > > > On Sat Jan 17 2015 at 12:03:33 AM Hal Finkel < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a><br> > > > ><br> > > > wrote:<br> > > > <br> > > > <br> > > > Hi Danny,<br> > > > <br> > > > // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that<br> > > > // BasicAliasAnalysis wins if they disagree. This is intended<br> > > > to<br> > > > help<br> > > > // support "obvious" type-punning idioms.<br> > > > - if (UseCFLAA)<br> > > > - addPass( createCFLAliasAnalysisPass());<br> > > > addPass( createTypeBasedAliasAnalysisPa ss());<br> > > > addPass( createScopedNoAliasAAPass());<br> > > > + if (UseCFLAA)<br> > > > + addPass( createCFLAliasAnalysisPass());<br> > > > addPass( createBasicAliasAnalysisPass() );<br> > > > <br> > > > Do we really want to change the order here? I had originally<br> > > > placed<br> > > > it after the metadata-based passes thinking that the<br> > > > compile-time<br> > > > would be better (guessing that the metadata queries would be<br> > > > faster<br> > > > than the CFL queries, so if the metadata could quickly return a<br> > > > NoAlias, then we'd cut out unecessary CFL queries). Perhaps<br> > > > this<br> > > > is<br> > > > an irrelevant effect, but we should have some documented<br> > > > rationale.<br> > > > <br> > > > <br> > > > <br> > > > Yeah, this was a mistake (Chandler had suggested it was right<br> > > > earlier, but we were both wrong :P)<br> > > > <br> > > > <br> > > > <br> > > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi<br> > > > -define i8 @test0(i8* %base, i1 %x) {<br> > > > +define i8 @test0(i1 %x) {<br> > > > entry:<br> > > > + %base = alloca i8, align 4<br> > > > %baseplusone = getelementptr i8* %base, i64 1<br> > > > br i1 %x, label %red, label %green<br> > > > red:<br> > > > @@ -25,8 +26,9 @@ green:<br> > > > }<br> > > > <br> > > > why should this return PartialAlias? %ohi does partially<br> > > > overlap,<br> > > > so<br> > > > this correct, but what happens when the overlap is partial or<br> > > > control dependent?<br> > > > So, after talking with some people offline, they convinced me<br> > > > in<br> > > > SSA<br> > > > form, the name would change in these situations, and the only<br> > > > situations you can get into trouble is with things "based on<br> > > > pointer<br> > > > arguments" (because you have no idea what their initial state<br> > > > is),<br> > > > or "globals" (because they are not in SSA form)<br> > > > I could not come up with a case otherwise<br> > > <br> > > Okay; that part of the code could really use some more<br> > > commentary.<br> > > I'd really appreciate it if you should put these thoughts in<br> > > written<br> > > form that could be added as comments.<br> > > <br> > > <br> > > <br> > > <br> > > <br> > > Will do<br> > > <br> > > <br> > > <br> > > > But i'm welcome to hear if you think this is wrong.<br> > > > <br> > > > FWIW: I bootstrapped/tested the compiler with an assert that<br> > > > triggered if CFL-AA was going to return PartialAlias and<br> > > > BasicAA<br> > > > would have returned NoAlias, and it did not trigger with this<br> > > > change.<br> > > > <br> > > > <br> > > > (It would have triggered before this set of changes)<br> > > > <br> > > > Not proof of course, but it at least tells me it's not<br> > > > "obviously<br> > > > wrong" :)<br> > > > <br> > > > <br> > > <br> > > That's good :) -- but, not exactly what I was concerned about.<br> > > Our<br> > > general convention has been that PartialAlias is a "strong"<br> > > result,<br> > > like MustAlias, but implies that AA has proved that only a<br> > > partial<br> > > overlap will occur.<br> > > <br> > > So, in this test case we get the right result:<br> > > <br> > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi<br> > > define i8 @test0(i1 %x) {<br> > > entry:<br> > > %base = alloca i8, align 4<br> > > %baseplusone = getelementptr i8* %base, i64 1<br> > > br i1 %x, label %red, label %green<br> > > red:<br> > > br label %green<br> > > green:<br> > > %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]<br> > > store i8 0, i8* %phi<br> > > <br> > > %bigbase0 = bitcast i8* %base to i16*<br> > > store i16 -1, i16* %bigbase0<br> > > <br> > > %loaded = load i8* %phi<br> > > ret i8 %loaded<br> > > }<br> > > <br> > > because %phi will have a partial overlap with %bigbase0, the only<br> > > uncertainty is whether the overlap is with the low byte or the<br> > > high<br> > > byte. But if I modify the test to be this:<br> > > <br> > > define i8 @test0x(i1 %x) {<br> > > entry:<br> > > %base = alloca i8, align 4<br> > > %baseplustwo = getelementptr i8* %base, i64 2<br> > > br i1 %x, label %red, label %green<br> > > red:<br> > > br label %green<br> > > green:<br> > > %phi = phi i8* [ %baseplustwo, %red ], [ %base, %entry ]<br> > > store i8 0, i8* %phi<br> > > <br> > > %bigbase0 = bitcast i8* %base to i16*<br> > > store i16 -1, i16* %bigbase0<br> > > <br> > > %loaded = load i8* %phi<br> > > ret i8 %loaded<br> > > }<br> > > <br> > > I still get this result:<br> > > PartialAlias: i16* %bigbase0, i8* %phi<br> > > <br> > > <br> > > <br> > > <br> > > <br> > > <br> > > <br> > > but now %phi might not overlap %bigbase0 at all (although, when<br> > > it<br> > > does, there is a partial overlap), so we should just return<br> > > MayAlias<br> > > (perhaps without delegation because this is a definitive<br> > > result?).<br> > > <br> > > <br> > > <br> > > <br> > > Yeah, i have to do some size checking, let me see if we have the<br> > > info<br> > > and i'll update the patch.<br> > > <br> > > <br> > > <br> > > <br> > > Otherwise, my view is that we should always delegate MayAlias,<br> > > because we have no idea what order the passes are in or what pass<br> > > someone has inserted where :)<br> > > <br> > > <br> > > (WIW: I believe the same about everything except MustAlias and<br> > > NoAlias, but currently we don't delegate PartialAlias.<br> > > We claim PartialAlias is a definitive result, but it really<br> > > isn't.<br> > > Right now we have TBAA that will give NoAlias results on things<br> > > other<br> > > passes claim are PartialAlias, and that result is correct. That's<br> > > just in our default, we have no idea what other people do. Even<br> > > if<br> > > you ignore TBAA, plenty of other compilers have noalias/mustalias<br> > > metadata that would have the same effect.<br> > <br> > --<br> > Hal Finkel<br> > Assistant Computational Scientist<br> > Leadership Computing Facility<br> > Argonne National Laboratory<br> > <br> <br> --<br> Hal Finkel<br> Assistant Computational Scientist<br> Leadership Computing Facility<br> Argonne National Laboratory<br> <br><br>-- </blockquote><br>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<br></div></div></div></div></blockquote></div><br></div></div></blockquote></div>
</div></div></blockquote></div><br></div>