[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
Hal Finkel
hfinkel at anl.gov
Sat Jan 17 15:15:20 PST 2015
----- 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.
> 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?).
Thanks again,
Hal
>
>
>
> thought you had concluded that CFL should return only NoAlias or
> MayAlias?
>
>
> Thanks again,
> Hal
>
> ----- Original Message -----
> > From: "Daniel Berlin" < dberlin at dberlin.org >
> > To: "Nick Lewycky" < nlewycky at google.com >
> > 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: Friday, January 16, 2015 2:22:23 PM
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > collecting a57 numbers
> >
> >
> >
> > Okay, overnight i ran a ton of tests on this patch, and it seems
> > right.
> > Nick, Hal, can you review it?
> >
> >
> > I've reattached it for simplicity
> >
> >
> >
> >
> > On Thu, Jan 15, 2015 at 3:05 PM, Daniel Berlin <
> > dberlin at dberlin.org
> > > wrote:
> >
> >
> >
> >
> >
> >
> >
> > On Thu, Jan 15, 2015 at 1:26 PM, Nick Lewycky < nlewycky at google.com
> > >
> > wrote:
> >
> >
> >
> >
> >
> > On 15 January 2015 at 13:10, Daniel Berlin < dberlin at dberlin.org >
> > wrote:
> >
> >
> >
> > Yes.
> > I've attached an updated patch that does the following:
> >
> >
> > 1. Fixes the partialalias of globals/arguments
> > 2. Enables partialalias for cases where nothing has been unified to
> > a
> > global/argument
> > 3. Fixes that select was unifying the condition to the other pieces
> > (the condition does not need to be processed :P). This was causing
> > unnecessary aliasing.
> >
> >
> > Consider this:
> >
> >
> >
> > void *p = ...;
> > uintptr_t i = p;
> > uintptr_t j = 0;
> > for (int a = 0; a < sizeof(uintptr_t); ++a) {
> > j = i >> (sizeof(uintptr_t) - a - 1) ? 1 : 0;
> > j <<= 1;
> > }
> > void *q = j;
> >
> >
> > alias(p, q) isn't NoAlias. (Okay, it kinda is in C++, but not in
> > the
> > equivalent LLVM IR. Please don't make me rewrite my example in LLVM
> > IR.)
> >
> >
> > Agreed :)
> >
> >
> > But after chatting with you, i think we both agree that this change
> > does not affect.
> > I probably should not have said "the condition does not need to be
> > processed". It would be more accurate to say "the reference to a
> > condition in a select instruction, by itself, does not cause
> > aliasing"
> >
> >
> > What happens now is:
> >
> >
> > given %4 = select %1, %2, %3
> >
> >
> > we do
> > aliasset(%4) += %1
> > aliasset(%4) += %2
> > aliasset(%4) += %3
> >
> > The first one is unnecessary.
> > There can be no alias caused simply because it is referenced in
> > condition of the select.
> >
> >
> >
> >
> >
> > We still need to process what %1 refers to (and we do).
> >
> >
> >
> >
> > To make this empirical, in your example, we get the right answer in
> > CFL-AA.
> >
> >
> > Interestingly, i'll point out that basic-aa says:
> >
> > NoAlias: i8* %p, i8** %q
> > NoAlias: i8** %p.addr, i8** %q
> >
> >
> > (I translated your case as best i can :P)
> >
> >
> > So you may want to implement it for real if you think it's supposed
> > to be handled right in basic-aa, because I don't believe it is :)
> >
> >
> >
> > ______________________________ _________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/ mailman/listinfo/llvmdev
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
More information about the llvm-dev
mailing list