llvm dev - Nov 2009 - [LLVMdev] BasicAliasAnalysis: constant does not alias with noalias parameter

Here is another change I'd like to suggest to the BasicAliasAnalysis.

LLVM fails to remove the dead store in the following code:

%t = type { i32 }

define void @f(%t* noalias nocapture %stuff ) {
     %p = getelementptr inbounds %t* %stuff, i32 0, i32 0

     store i32 1, i32* %p; <-- This store is dead

     %x = load i32* inttoptr (i32 12345 to i32*)
     store i32 %x, i32* %p
     ret void
}


when run through
./llvm-as -o - test2.ll | ./opt -O3 -o - | ./llvm-dis -o -


The problem is that the alias analysis is unsure about whether %p and 
12345 may alias. But since %p is derived from %stuff, which has the 
noalias attribute, and 12345 is a constant and therefore cannot be 
derived from %stuff, they cannot alias.

I'm attaching a patch which implements this. Please comment on whether 
this is sane, and if my code is the right way of doing it.


/ Hans
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BasicAliasAnalysis.patch
Type: text/x-patch
Size: 1151 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091104/33e67b8a/attachment.bin>

On Nov 4, 2009, at 6:43 AM, Hans Wennborg wrote:
> Here is another change I'd like to suggest to the BasicAliasAnalysis.
> 
> LLVM fails to remove the dead store in the following code:
> 
> %t = type { i32 }
> 
> define void @f(%t* noalias nocapture %stuff ) {
>    %p = getelementptr inbounds %t* %stuff, i32 0, i32 0
> 
>    store i32 1, i32* %p; <-- This store is dead
> 
>    %x = load i32* inttoptr (i32 12345 to i32*)
>    store i32 %x, i32* %p
>    ret void
> }
> 
> 
> when run through
> ./llvm-as -o - test2.ll | ./opt -O3 -o - | ./llvm-dis -o -
> 
> 
> The problem is that the alias analysis is unsure about whether %p and 12345
may alias. But since %p is derived from %stuff, which has the noalias attribute,
and 12345 is a constant and therefore cannot be derived from %stuff, they cannot
alias.
This sounds right. And actually, it's not limited to noalias;
isIdentifiedObject objects don't alias inttoptr-casted integer
literals either. I have a few comments on the patch below.
> 
> I'm attaching a patch which implements this. Please comment on whether
this is sane, and if my code is the right way of doing it.
> 
> 
> / Hans
> Index: lib/Analysis/BasicAliasAnalysis.cpp
> ==================================================================> ---
lib/Analysis/BasicAliasAnalysis.cpp	(revision 86023)
> +++ lib/Analysis/BasicAliasAnalysis.cpp	(working copy)
> @@ -643,6 +643,23 @@
>   if (!isa<PointerType>(V1->getType()) ||
!isa<PointerType>(V2->getType()))
>     return NoAlias;  // Scalars cannot alias each other
> 
> +  // Constant ptr cannot alias with a noalias attribute
> +  if (isa<Constant>(V1) &&
isa<PointerType>(V2->getType())) {
> +    while (const GEPOperator *g = dyn_cast<GEPOperator>(V2))
> +      V2 = g->getOperand(0);
> +
> +    if (const Argument *A = dyn_cast<Argument>(V2))
> +      if (A->hasNoAliasAttr())
> +        return NoAlias;
> +  } else if (isa<Constant>(V2) &&
isa<PointerType>(V1->getType())) {
> +    while (const GEPOperator *g = dyn_cast<GEPOperator>(V1))
> +      V1 = g->getOperand(0);
> +
> +    if (const Argument *A = dyn_cast<Argument>(V1))
> +      if (A->hasNoAliasAttr())
> +        return NoAlias;
> +  }
The GEP logic here is effectively doing (a subset of) what
getUnderlyingObject does. It would be better to move these checks
below the getUnderlyingObject calls just below so that they can
use the results from those calls instead.

And instead of checking for a no-alias argument, this code could
use isIdentifiedObject instead, following my comment above.

Dan
>   // Figure out what objects these things are pointing to if we can.
>   const Value *O1 = V1->getUnderlyingObject();
>   const Value *O2 = V2->getUnderlyingObject();
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Dan Gohman wrote:
> On Nov 4, 2009, at 6:43 AM, Hans Wennborg wrote:
> 
>> Here is another change I'd like to suggest to the
BasicAliasAnalysis.
>>
>> LLVM fails to remove the dead store in the following code:
>>
>> %t = type { i32 }
>>
>> define void @f(%t* noalias nocapture %stuff ) {
>>    %p = getelementptr inbounds %t* %stuff, i32 0, i32 0
>>
>>    store i32 1, i32* %p; <-- This store is dead
>>
>>    %x = load i32* inttoptr (i32 12345 to i32*)
>>    store i32 %x, i32* %p
>>    ret void
>> }
>>
>>
>> when run through
>> ./llvm-as -o - test2.ll | ./opt -O3 -o - | ./llvm-dis -o -
>>
>>
>> The problem is that the alias analysis is unsure about whether %p and
12345 may alias. But since %p is derived from %stuff, which has the noalias
attribute, and 12345 is a constant and therefore cannot be derived from %stuff,
they cannot alias.
> 
> This sounds right. And actually, it's not limited to noalias;
> isIdentifiedObject objects don't alias inttoptr-casted integer
> literals either. I have a few comments on the patch below.
> 
>> I'm attaching a patch which implements this. Please comment on
whether this is sane, and if my code is the right way of doing it.
>>
>>
>> / Hans
>> Index: lib/Analysis/BasicAliasAnalysis.cpp
>>
==================================================================>> ---
lib/Analysis/BasicAliasAnalysis.cpp	(revision 86023)
>> +++ lib/Analysis/BasicAliasAnalysis.cpp	(working copy)
>> @@ -643,6 +643,23 @@
>>   if (!isa<PointerType>(V1->getType()) ||
!isa<PointerType>(V2->getType()))
>>     return NoAlias;  // Scalars cannot alias each other
>>
>> +  // Constant ptr cannot alias with a noalias attribute
>> +  if (isa<Constant>(V1) &&
isa<PointerType>(V2->getType())) {
>> +    while (const GEPOperator *g = dyn_cast<GEPOperator>(V2))
>> +      V2 = g->getOperand(0);
>> +
>> +    if (const Argument *A = dyn_cast<Argument>(V2))
>> +      if (A->hasNoAliasAttr())
>> +        return NoAlias;
>> +  } else if (isa<Constant>(V2) &&
isa<PointerType>(V1->getType())) {
>> +    while (const GEPOperator *g = dyn_cast<GEPOperator>(V1))
>> +      V1 = g->getOperand(0);
>> +
>> +    if (const Argument *A = dyn_cast<Argument>(V1))
>> +      if (A->hasNoAliasAttr())
>> +        return NoAlias;
>> +  }
> 
> The GEP logic here is effectively doing (a subset of) what
> getUnderlyingObject does. It would be better to move these checks
> below the getUnderlyingObject calls just below so that they can
> use the results from those calls instead.
> 
> And instead of checking for a no-alias argument, this code could
> use isIdentifiedObject instead, following my comment above.
Thank you for the input, this certainly made things nicer. I have 
attached a patch that does this together with a test case.

/ Hans
> 
> Dan
> 
>>   // Figure out what objects these things are pointing to if we can.
>>   const Value *O1 = V1->getUnderlyingObject();
>>   const Value *O2 = V2->getUnderlyingObject();
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BasicAliasAnalysis.patch
Type: text/x-patch
Size: 2180 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091110/e2f41ca9/attachment.bin>