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

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>

After discussing with Nick Lewycky in the IRC channel, here comes a less 
aggressive patch.

We were worried that a constant pointer could alias with a GlobalValue.
Also, if one pointer could be a GlobalValue and the other a GlobalAlias 
with the GlobalValue as aliasee.
However, I was not able to produce a test where this happens wihout the 
getUnderlyingObject() returning the same value.

It would be nice if someone could produce such a test case, or dismiss 
the possibility of this happening.


Anyway, saying that a Constant does not alias with a non-const 
isIdentifiedObject object seems safe.

/ Hans


Hans Wennborg wrote:
> 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
>>
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> 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: BasicAliasAnalysis2.patch
Type: text/x-patch
Size: 1996 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091112/23e81267/attachment.bin>

On Nov 12, 2009, at 1:05 AM, Hans Wennborg wrote:
> After discussing with Nick Lewycky in the IRC channel, here comes a less
aggressive patch.
> 
> We were worried that a constant pointer could alias with a GlobalValue.
It can. You can have a GetElementPtr ConstantExpr which aliases a
GlobalValue, for example. What problem does this cause though?
> Also, if one pointer could be a GlobalValue and the other a GlobalAlias
with the GlobalValue as aliasee.
> However, I was not able to produce a test where this happens wihout the
getUnderlyingObject() returning the same value.
AliasAnalysis::isIdentifiedObject knows that GlobalAlias and ConstantExpr
values are not "identified objects", so I don't see the trouble
here. Also,
getUnderlyingObject() knows how to look through (non-weak) GlobalAliases.

Dan
> It would be nice if someone could produce such a test case, or dismiss the
possibility of this happening.
> 
> 
> Anyway, saying that a Constant does not alias with a non-const
isIdentifiedObject object seems safe.
> 
> / Hans
>

Hello Hans,

This patch looks fine. I've now talked with Nick on IRC and I've gone
re-read your previous patch and found what I was confused about.
Your original email talked about inttoptr-casted integer constants,
and I missed that the patch itself was using isa<Constant> instead,
which covers a lot of other kinds of things.

So while it's true that constants don't alias non-constant identified
objects and your new patch is fine, it's also true that the special
case of inttoptr-casted constant ints don't alias *any* identified
objects, in case you're interested in that too.

Dan

On Nov 12, 2009, at 1:05 AM, Hans Wennborg wrote:
> After discussing with Nick Lewycky in the IRC channel, here comes a less
aggressive patch.
> 
> We were worried that a constant pointer could alias with a GlobalValue.
> Also, if one pointer could be a GlobalValue and the other a GlobalAlias
with the GlobalValue as aliasee.
> However, I was not able to produce a test where this happens wihout the
getUnderlyingObject() returning the same value.
> 
> It would be nice if someone could produce such a test case, or dismiss the
possibility of this happening.
> 
> 
> Anyway, saying that a Constant does not alias with a non-const
isIdentifiedObject object seems safe.
> 
> / Hans
> 
> 
> Hans Wennborg wrote:
>> 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
>>> 
>>
------------------------------------------------------------------------
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> <BasicAliasAnalysis2.patch>

Hans Wennborg wrote:
> After discussing with Nick Lewycky in the IRC channel, here comes a less 
> aggressive patch.
> 
> We were worried that a constant pointer could alias with a GlobalValue.
> Also, if one pointer could be a GlobalValue and the other a GlobalAlias 
> with the GlobalValue as aliasee.
> However, I was not able to produce a test where this happens wihout the 
> getUnderlyingObject() returning the same value.
> 
> It would be nice if someone could produce such a test case, or dismiss 
> the possibility of this happening.
My bad, it seems that while I wasn't looking, someone taught 
getUnderlyingObject to look through GlobalAliases and return what they 
point to!

However the previous patch was wrong given code like:

   @gv = global i32 0
   define void @test() {
     store i16 1, i16* inttoptr(i64 add(i64 ptrtoint(i32* @gv to i64), 
i64 1) to i16*) ; ; Not dead
     store i32 2, i32* @gv
     ret void
   }
> Anyway, saying that a Constant does not alias with a non-const 
> isIdentifiedObject object seems safe.
Yup!

Please remove the tailing ; on the lines where they aren't needed in 
your tests. Besides that, your patch looks great! Thanks!

Nick
> / Hans
> 
> 
> Hans Wennborg wrote:
>> 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
>>>
>>
>>
------------------------------------------------------------------------
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev