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

[Hal Finkel]

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.

 ; 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