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

[Daniel Berlin]

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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150120/c105eec8/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cflaafix.diff
Type: application/octet-stream
Size: 5811 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150120/c105eec8/attachment.obj>