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-15 23:05 UTC

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

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 :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150115/1b1eacb5/attachment.html>

Daniel Berlin

2015-Jan-16 20:22 UTC

head link

[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 :)
>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150116/e2074450/attachment.html>
-------------- next part --------------
diff --git a/lib/Analysis/CFLAliasAnalysis.cpp
b/lib/Analysis/CFLAliasAnalysis.cpp
index 88bb84a..3741bb9 100644
--- a/lib/Analysis/CFLAliasAnalysis.cpp
+++ b/lib/Analysis/CFLAliasAnalysis.cpp
@@ -227,10 +227,13 @@ public:
     // Comparisons between global variables and other constants should be
     // handled by BasicAA.
     if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
{
-      return MayAlias;
+      return AliasAnalysis::alias(LocA, LocB);
     }
+    AliasResult QueryResult = query(LocA, LocB);
+    if (QueryResult == MayAlias)
+      return AliasAnalysis::alias(LocA, LocB);
 
-    return query(LocA, LocB);
+    return QueryResult;
   }
 
   void initializePass() override { InitializeAliasAnalysis(this); }
@@ -295,8 +298,11 @@ public:
   }
 
   void visitSelectInst(SelectInst &Inst) {
-    auto *Condition = Inst.getCondition();
-    Output.push_back(Edge(&Inst, Condition, EdgeType::Assign, AttrNone));
+    // Condition is not processed here (The actual statement producing
+    // the condition result is processed elsewhere). For select, the
+    // condition is evaluated, but not loaded, stored, or assigned
+    // simply as a result of being the condition of a select.
+
     auto *TrueVal = Inst.getTrueValue();
     Output.push_back(Edge(&Inst, TrueVal, EdgeType::Assign, AttrNone));
     auto *FalseVal = Inst.getFalseValue();
@@ -768,7 +774,10 @@ static Optional<StratifiedAttr>
valueToAttrIndex(Value *Val) {
     return AttrGlobalIndex;
 
   if (auto *Arg = dyn_cast<Argument>(Val))
-    if (!Arg->hasNoAliasAttr())
+    // Only pointer arguments should have the argument attribute,
+    // because things can't escape through scalars without us seeing a
+    // cast, and thus, interaction with them doesn't matter.
+    if (!Arg->hasNoAliasAttr() &&
Arg->getType()->isPointerTy())
       return argNumberToAttrIndex(Arg->getArgNo());
   return NoneType();
 }
@@ -991,10 +1000,6 @@ CFLAliasAnalysis::query(const AliasAnalysis::Location
&LocA,
 
   auto SetA = *MaybeA;
   auto SetB = *MaybeB;
-
-  if (SetA.Index == SetB.Index)
-    return AliasAnalysis::PartialAlias;
-
   auto AttrsA = Sets.getLink(SetA.Index).Attrs;
   auto AttrsB = Sets.getLink(SetB.Index).Attrs;
   // Stratified set attributes are used as markets to signify whether a member
@@ -1009,5 +1014,12 @@ CFLAliasAnalysis::query(const AliasAnalysis::Location
&LocA,
   if (AttrsA.any() && AttrsB.any())
     return AliasAnalysis::MayAlias;
 
+  // If we haven't interacted with globals, and they still got
+  // unified, they are partial alias right now.
+  // NOTE: This assumes we don't unify for any reason other than
+  // assignments
+  if (SetA.Index == SetB.Index)
+    return AliasAnalysis::PartialAlias;
+
   return AliasAnalysis::NoAlias;
 }
diff --git a/lib/CodeGen/Passes.cpp b/lib/CodeGen/Passes.cpp
index 28e9f84..82ca024 100644
--- a/lib/CodeGen/Passes.cpp
+++ b/lib/CodeGen/Passes.cpp
@@ -400,10 +400,10 @@ void TargetPassConfig::addIRPasses() {
   // 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());
 
   // Before running any passes, run the verifier to determine if the input
diff --git a/lib/Transforms/IPO/PassManagerBuilder.cpp
b/lib/Transforms/IPO/PassManagerBuilder.cpp
index bb776ef..645686c 100644
--- a/lib/Transforms/IPO/PassManagerBuilder.cpp
+++ b/lib/Transforms/IPO/PassManagerBuilder.cpp
@@ -132,10 +132,10 @@
PassManagerBuilder::addInitialAliasAnalysisPasses(PassManagerBase &PM) const
{
   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
   // BasicAliasAnalysis wins if they disagree. This is intended to help
   // support "obvious" type-punning idioms.
-  if (UseCFLAA)
-    PM.add(createCFLAliasAnalysisPass());
   PM.add(createTypeBasedAliasAnalysisPass());
   PM.add(createScopedNoAliasAAPass());
+  if (UseCFLAA)
+    PM.add(createCFLAliasAnalysisPass());
   PM.add(createBasicAliasAnalysisPass());
 }
 
diff --git a/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll
b/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll
index a0195d7..f68edaf 100644
--- a/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll
+++ b/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll
@@ -5,7 +5,8 @@ target datalayout = "e-p:32:32:32"
 
 ; CHECK: 1 partial alias response
 
-define i32 @test(i32* %tab, i32 %indvar) nounwind {
+define i32 @test(i32 %indvar) nounwind {
+  %tab = alloca i32, align 4
   %tmp31 = mul i32 %indvar, -2
   %tmp32 = add i32 %tmp31, 30
   %t.5 = getelementptr i32* %tab, i32 %tmp32
diff --git a/test/Analysis/CFLAliasAnalysis/must-and-partial.ll
b/test/Analysis/CFLAliasAnalysis/must-and-partial.ll
index df7de38..2c66d90 100644
--- a/test/Analysis/CFLAliasAnalysis/must-and-partial.ll
+++ b/test/Analysis/CFLAliasAnalysis/must-and-partial.ll
@@ -7,8 +7,9 @@
 target datalayout =
"e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 
 ; 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:
 }
 
 ; CHECK: PartialAlias:  i16* %bigbase1, i8* %sel
-define i8 @test1(i8* %base, i1 %x) {
+define i8 @test1(i1 %x) {
 entry:
+  %base = alloca i8, align 4
   %baseplusone = getelementptr i8* %base, i64 1
   %sel = select i1 %x, i8* %baseplusone, i8* %base
   store i8 0, i8* %sel
@@ -37,3 +39,15 @@ entry:
   %loaded = load i8* %sel
   ret i8 %loaded
 }
+
+; Arguments should not be partial alias
+; CHECK: MayAlias:  double* %A, double* %Index
+define void @testr2(double* nocapture readonly %A, double* nocapture readonly
%Index) {
+  %arrayidx22 = getelementptr inbounds double* %Index, i64 2
+  %1 = load double* %arrayidx22
+  %arrayidx25 = getelementptr inbounds double* %A, i64 2
+  %2 = load double* %arrayidx25
+  %mul26 = fmul double %1, %2
+  ret void
+}
+

Chandler Carruth

2015-Jan-16 21:11 UTC

head link

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

I'm pretty sure I had the ordering of the passes backwards. The previous
ordering is correct.  Sorry for the confusion.

The last alias analysis created is the first one queried. It delegates to
the previous alias analysis created. At least, that is my reading of this
(very confusing) code.

The most frustrating aspect of this is that it means the delegation
behavior of CFL shouldn't have mattered at all because BasicAA ran first...
However BasicAA does do its own caching, so who knows.

On Fri, Jan 16, 2015 at 12:22 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> 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
>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150116/0bc511ff/attachment.html>

Hal Finkel

2015-Jan-17 08:03 UTC

head link

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

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