thr3ads.net - llvm dev - [LLVMdev] question about enabling cfl-aa and collecting a57 numbers [Jan 2015]

If this information is useful, please help other people find it:
Share via:

Daniel Berlin

2015-Jan-20 19:48 UTC

[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.
>-------------- 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>

Ana Pazos

2015-Jan-20 21:41 UTC

head link

[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.

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
<mailto:dberlin at dberlin.org> > wrote:

On Sat Jan 17 2015 at 3:15:27 PM Hal Finkel <hfinkel at anl.gov
<mailto:hfinkel at anl.gov> > wrote:

----- Original Message -----> From: "Daniel Berlin" <dberlin at dberlin.org
<mailto:dberlin at dberlin.org> >
> To: "Hal Finkel" <hfinkel at anl.gov <mailto:hfinkel at
anl.gov> >
> Cc: "Jiangning Liu" <Jiangning.Liu at arm.com
<mailto:Jiangning.Liu at arm.com> >, "George Burgess IV"
<george.burgess.iv at gmail.com <mailto:george.burgess.iv at gmail.com>
>, "LLVM Developers
> Mailing List" <llvmdev at cs.uiuc.edu <mailto:llvmdev at
cs.uiuc.edu> >, "Nick Lewycky" <nlewycky at google.com
<mailto: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
<mailto: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/1349accf/attachment.html>

Hal Finkel

2015-Jan-20 23:54 UTC

head link

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

----- 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

Hal Finkel

2015-Jan-20 23:57 UTC

head link

[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

Daniel Berlin

2015-Jan-21 19:10 UTC

head link

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

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>

llvm dev - Jan 2015 - [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

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

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

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

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

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