Updated testcases to have MayAlias/note issues as FIXME.<div><br><div><br><br><div class="gmail_quote">On Tue Jan 20 2015 at 3:54:10 PM Hal Finkel <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">----- 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" <<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>
> Sent: Tuesday, January 20, 2015 1:48:44 PM<br>
> Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers<br>
><br>
> So, I can make all these testcases work, but it's a little tricky (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" code<br>
> in a bugfix, and honestly, i'm not sure we will catch any cases 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 MayAlias, and put a FIXME comment explaining that they could be PartialAlias. As far as I know, there is no code in LLVM that really handles a PartialAlias differently than a MayAlias or MustAlias, and so while there may be some benefit here, I'm not sure it will be worth the effort.<br>
<br>
><br>
> I will build and test a patch to get these back to PartialAlias, but<br>
> this patch will at least get us to not be "giving wrong answers". 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 PartialAlias cases, and as I said, we essentially ignore them anyway.<br>
<br>
As a side note, there is this one place in lib/Analysis/<u></u>MemoryDependenceAnalysis.cpp that could use some attention:<br>
<br>
#if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting 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 the<br>
        // client to handle.<br>
        if (R == AliasAnalysis::PartialAlias)<br>
          return MemDepResult::getClobber(Inst)<u></u>;<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* 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 < <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 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>
> > wrote:<br>
> ><br>
> ><br>
> > Hi Danny,<br>
> ><br>
> > // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that<br>
> > // BasicAliasAnalysis wins if they disagree. This is intended 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 placed<br>
> > it after the metadata-based passes thinking that the compile-time<br>
> > would be better (guessing that the metadata queries would be 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 this is<br>
> > an irrelevant effect, but we should have some documented 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 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 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 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 commentary.<br>
> I'd really appreciate it if you should put these thoughts in 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 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 "obviously<br>
> > wrong" :)<br>
> ><br>
> ><br>
><br>
> That's good :) -- but, not exactly what I was concerned about. Our<br>
> general convention has been that PartialAlias is a "strong" result,<br>
> like MustAlias, but implies that AA has proved that only a 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 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 it<br>
> does, there is a partial overlap), so we should just return MayAlias<br>
> (perhaps without delegation because this is a definitive result?).<br>
><br>
><br>
><br>
><br>
> Yeah, i have to do some size checking, let me see if we have the 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 isn't.<br>
> Right now we have TBAA that will give NoAlias results on things 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 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>
</blockquote></div></div></div>