[LLVMdev] BasicAliasAnalysis: constant does not alias with noalias parameter

[Hans Wennborg]

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>