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

[Dan Gohman]

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>