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

[Daniel Berlin]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150118/e55362dd/attachment.html>