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

[Ana Pazos]

Yes, fixing the delegation resolved the LICM degradation in the test I shared.
I will collect new perf numbers to see where we are now.
Ana.

-----Original Message-----
From: Hal Finkel [mailto:hfinkel at anl.gov] 
Sent: Tuesday, January 20, 2015 3:57 PM
To: Ana Pazos
Cc: Jiangning Liu; George Burgess IV; LLVM Developers Mailing List; Daniel Berlin
Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

----- Original Message -----
> From: "Ana Pazos" <apazos at codeaurora.org>
> To: "Daniel Berlin" <dberlin at dberlin.org>, "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>
> Sent: Tuesday, January 20, 2015 3:41:06 PM
> Subject: RE: [LLVMdev] question about enabling cfl-aa and collecting a57	numbers
> 
> 
> 
> 
> Daniel, I see correctness failures with the previous patch in AArch64 
> spec2006/h264ref and an internal test code we have.
> 
> So I think your patch should only have the code fix for the delegation 
> issue.
> 
> I will try the new patch you attached and let you know the results.
> 

Ana, Danny, just because I've somewhat lost track of this: Does fixing the delegation issue fix the LICM degradation using the existing pass ordering? Or is something else necessary for that?

Thanks again,
Hal

> 
> 
> Thanks,
> 
> Ana.
> 
> 
> 
> From: llvmdev-bounces at cs.uiuc.edu
> [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Daniel Berlin
> Sent: Tuesday, January 20, 2015 11:49 AM
> To: Hal Finkel
> Cc: Jiangning Liu; George Burgess IV; LLVM Developers Mailing List
> 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.
> 
> 
> 
> 
> 
> 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.
> 
> 
> 
> 
> 
> 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)
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 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