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

[Nick Lewycky]

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