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

[Hans Wennborg]

Attaching patch with unnecessary trailing ; removed from test case.

Thank you both for helping to straighten this out, and sorry about the 
confusion.


Hans


Nick Lewycky wrote:
> 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
> 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BasicAliasAnalysis3.patch
Type: text/x-patch
Size: 1993 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20091113/c5e63f56/attachment.bin>