[LLVMdev] question about enabling cfl-aa and collecting a57 numbers

[Daniel Berlin]

Updated testcases to have MayAlias/note issues as FIXME.



On Tue Jan 20 2015 at 3:54:10 PM Hal Finkel <hfinkel at anl.gov> wrote:

> ----- Original Message -----
> > From: "Daniel Berlin" <dberlin at dberlin.org>
> > To: "Hal Finkel" <hfinkel at anl.gov>
> > Cc: "Jiangning Liu" <Jiangning.Liu at arm.com>, "George Burgess IV" <
> george.burgess.iv at gmail.com>, "LLVM Developers
> > Mailing List" <llvmdev at cs.uiuc.edu>, "Nick Lewycky" <nlewycky at google.com
> >
> > Sent: Tuesday, January 20, 2015 1:48:44 PM
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57
> numbers
> >
> > So, I can make all these testcases work, but it's a little tricky (it
> > involves tracking some things, like GEP byte range, and then
> > checking bases and using getObjectSize, much like BasicAA does).
> >
> >
> > Because i really don't want to put that much "not well tested" code
> > in a bugfix, and honestly, i'm not sure we will catch any cases here
> > that BasicAA does not, i've attached a change to XFAIL these
> > testcases, and updated the code to return MayAlias.
>
> 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.
>
> >
> > I will build and test a patch to get these back to PartialAlias, but
> > this patch will at least get us to not be "giving wrong answers". I
> > will also see if we catch anything with it that BasicAA does not,
> > because if we don't, it doesn't seem worth it to me.
>
> My guess is that BasicAA will get almost all of the interesting
> PartialAlias cases, and as I said, we essentially ignore them anyway.
>
> As a side note, there is this one place in lib/Analysis/MemoryDependenceAnalysis.cpp
> that could use some attention:
>
> #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads
>       // in terms of clobbering loads, but since it does this by looking
>       // at the clobbering load directly, it doesn't know about any
>       // phi translation that may have happened along the way.
>
>         // If we have a partial alias, then return this as a clobber for
> the
>         // client to handle.
>         if (R == AliasAnalysis::PartialAlias)
>           return MemDepResult::getClobber(Inst);
> #endif
>
> >
> >
> > Conservative new patch attached.
> >
> >
> >
> > (Note that i still updated the testcases, because we will *never* be
> > able to legally return PartialAlias as they were written)
> >
>
> Yes, sounds good.
>
>  -Hal
>
> >
> >
> >
> >
> >
> >
> >
> > On Sun Jan 18 2015 at 2:12:47 PM Daniel Berlin < dberlin at dberlin.org
> > > wrote:
> >
> >
> >
> > On Sat Jan 17 2015 at 3:15:27 PM Hal Finkel < hfinkel at anl.gov >
> > wrote:
> >
> >
> > ----- Original Message -----
> > > From: "Daniel Berlin" < dberlin at dberlin.org >
> > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com >, "George Burgess IV"
> > > < george.burgess.iv at gmail.com >, "LLVM Developers
> > > Mailing List" < llvmdev at cs.uiuc.edu >, "Nick Lewycky" <
> > > nlewycky at google.com >
> > > Sent: Saturday, January 17, 2015 1:08:10 PM
> > > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > > collecting a57 numbers
> > >
> > >
> > >
> > >
> > > On Sat Jan 17 2015 at 12:03:33 AM Hal Finkel < hfinkel at anl.gov >
> > > wrote:
> > >
> > >
> > > Hi Danny,
> > >
> > > // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
> > > // BasicAliasAnalysis wins if they disagree. This is intended to
> > > help
> > > // support "obvious" type-punning idioms.
> > > - if (UseCFLAA)
> > > - addPass( createCFLAliasAnalysisPass());
> > > addPass( createTypeBasedAliasAnalysisPa ss());
> > > addPass( createScopedNoAliasAAPass());
> > > + if (UseCFLAA)
> > > + addPass( createCFLAliasAnalysisPass());
> > > addPass( createBasicAliasAnalysisPass() );
> > >
> > > Do we really want to change the order here? I had originally placed
> > > it after the metadata-based passes thinking that the compile-time
> > > would be better (guessing that the metadata queries would be faster
> > > than the CFL queries, so if the metadata could quickly return a
> > > NoAlias, then we'd cut out unecessary CFL queries). Perhaps this is
> > > an irrelevant effect, but we should have some documented rationale.
> > >
> > >
> > >
> > > Yeah, this was a mistake (Chandler had suggested it was right
> > > earlier, but we were both wrong :P)
> > >
> > >
> > >
> > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
> > > -define i8 @test0(i8* %base, i1 %x) {
> > > +define i8 @test0(i1 %x) {
> > > entry:
> > > + %base = alloca i8, align 4
> > > %baseplusone = getelementptr i8* %base, i64 1
> > > br i1 %x, label %red, label %green
> > > red:
> > > @@ -25,8 +26,9 @@ green:
> > > }
> > >
> > > why should this return PartialAlias? %ohi does partially overlap,
> > > so
> > > this correct, but what happens when the overlap is partial or
> > > control dependent?
> > > So, after talking with some people offline, they convinced me in
> > > SSA
> > > form, the name would change in these situations, and the only
> > > situations you can get into trouble is with things "based on
> > > pointer
> > > arguments" (because you have no idea what their initial state is),
> > > or "globals" (because they are not in SSA form)
> > > I could not come up with a case otherwise
> >
> > Okay; that part of the code could really use some more commentary.
> > I'd really appreciate it if you should put these thoughts in written
> > form that could be added as comments.
> >
> >
> >
> >
> >
> > Will do
> >
> >
> >
> > > But i'm welcome to hear if you think this is wrong.
> > >
> > > FWIW: I bootstrapped/tested the compiler with an assert that
> > > triggered if CFL-AA was going to return PartialAlias and BasicAA
> > > would have returned NoAlias, and it did not trigger with this
> > > change.
> > >
> > >
> > > (It would have triggered before this set of changes)
> > >
> > > Not proof of course, but it at least tells me it's not "obviously
> > > wrong" :)
> > >
> > >
> >
> > That's good :) -- but, not exactly what I was concerned about. Our
> > general convention has been that PartialAlias is a "strong" result,
> > like MustAlias, but implies that AA has proved that only a partial
> > overlap will occur.
> >
> > So, in this test case we get the right result:
> >
> > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
> > define i8 @test0(i1 %x) {
> > entry:
> > %base = alloca i8, align 4
> > %baseplusone = getelementptr i8* %base, i64 1
> > br i1 %x, label %red, label %green
> > red:
> > br label %green
> > green:
> > %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]
> > store i8 0, i8* %phi
> >
> > %bigbase0 = bitcast i8* %base to i16*
> > store i16 -1, i16* %bigbase0
> >
> > %loaded = load i8* %phi
> > ret i8 %loaded
> > }
> >
> > because %phi will have a partial overlap with %bigbase0, the only
> > uncertainty is whether the overlap is with the low byte or the high
> > byte. But if I modify the test to be this:
> >
> > define i8 @test0x(i1 %x) {
> > entry:
> > %base = alloca i8, align 4
> > %baseplustwo = getelementptr i8* %base, i64 2
> > br i1 %x, label %red, label %green
> > red:
> > br label %green
> > green:
> > %phi = phi i8* [ %baseplustwo, %red ], [ %base, %entry ]
> > store i8 0, i8* %phi
> >
> > %bigbase0 = bitcast i8* %base to i16*
> > store i16 -1, i16* %bigbase0
> >
> > %loaded = load i8* %phi
> > ret i8 %loaded
> > }
> >
> > I still get this result:
> > PartialAlias: i16* %bigbase0, i8* %phi
> >
> >
> >
> >
> >
> >
> >
> > but now %phi might not overlap %bigbase0 at all (although, when it
> > does, there is a partial overlap), so we should just return MayAlias
> > (perhaps without delegation because this is a definitive result?).
> >
> >
> >
> >
> > Yeah, i have to do some size checking, let me see if we have the info
> > and i'll update the patch.
> >
> >
> >
> >
> > Otherwise, my view is that we should always delegate MayAlias,
> > because we have no idea what order the passes are in or what pass
> > someone has inserted where :)
> >
> >
> > (WIW: I believe the same about everything except MustAlias and
> > NoAlias, but currently we don't delegate PartialAlias.
> > We claim PartialAlias is a definitive result, but it really isn't.
> > Right now we have TBAA that will give NoAlias results on things other
> > passes claim are PartialAlias, and that result is correct. That's
> > just in our default, we have no idea what other people do. Even if
> > you ignore TBAA, plenty of other compilers have noalias/mustalias
> > metadata that would have the same effect.
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150121/6cdf0f67/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cflaafix.diff
Type: application/octet-stream
Size: 6713 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150121/6cdf0f67/attachment.obj>