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

[Hal Finkel]

----- Original Message -----
> From: "Hal Finkel" <hfinkel at anl.gov>
> To: "Daniel Berlin" <dberlin at dberlin.org>
> 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: Saturday, January 17, 2015 2:03:18 AM
> Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting	a57	numbers
> 
> 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(createTypeBasedAliasAnalysisPass());
>    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.

Please ignore the above question; I had forgotten that you had posted a newer version of the patch without the ordering change. Only the question below matters...

Thanks again,
Hal

> 
>  ; 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? I 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
> _______________________________________________
> 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