llvm dev - Nov 2009 - [LLVMdev] BasicAliasAnalysis: Null pointers do not alias with anything

This is the first patch I've sent to this project. Please be gentle :)

LLVM fails to remove the dead load in the following code when running
$./llvm-as -o - test.ll | ./opt -O3 -o - | ./llvm-dis -o -


%t = type { i32 }
declare void @foo(i8*)

define void @f(%t* noalias nocapture %stuff ) {
     %p = getelementptr inbounds %t* %stuff, i32 0, i32 0
     %before = load i32* %p

     call void @foo(i8* null)

     %after = load i32* %p ; <--- This should be removed!
     %sum = add i32 %before, %after;

     store i32 %sum, i32* %p
     ret void
}


The reason is that it is unsure whether the null pointer which is passed 
in the call to @foo may alias with %t. Obviously, a null pointer doesn't 
alias with anything, because it's not legal to read or write through it 
(right?).

The attached patch adds this check to BasicAliasAnalysis, and makes the 
dead load go away in my test.

Does this seem reasonable, and is my patch doing it the right way?


/ Hans
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.patch
Type: text/x-patch
Size: 766 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091104/8298ee32/attachment.bin>

On Wed, Nov 4, 2009 at 4:51 AM, Hans Wennborg <hans at hanshq.net> wrote:
>
>
> The reason is that it is unsure whether the null pointer which is passed in
> the call to @foo may alias with %t. Obviously, a null pointer doesn't
alias
> with anything, because it's not legal to read or write through it
(right?).
I don't remember whether LLVM's language spec says anything different,
but whether null may alias anything is generally platform dependent.

On some platforms, null may actually point to things and be
dereferenced legally.

(This is often used to speculatively executive conditionals involving
pointer-derefs)

On Nov 4, 2009, at 7:19 AM, Daniel Berlin wrote:
> On Wed, Nov 4, 2009 at 4:51 AM, Hans Wennborg <hans at hanshq.net>
wrote:
>
>>
>>
>> The reason is that it is unsure whether the null pointer which is  
>> passed in
>> the call to @foo may alias with %t. Obviously, a null pointer  
>> doesn't alias
>> with anything, because it's not legal to read or write through it  
>> (right?).
>
> I don't remember whether LLVM's language spec says anything
different,
> but whether null may alias anything is generally platform dependent.
>
> On some platforms, null may actually point to things and be
> dereferenced legally.
>
> (This is often used to speculatively executive conditionals involving
> pointer-derefs)
Our current policy is to disallow dereferences of the null pointer,  
unless they are in the non-default address space.

-Chris

Hello,

On Nov 4, 2009, at 1:51 AM, Hans Wennborg wrote:
> 
> 
> / Hans
> Index: lib/Analysis/BasicAliasAnalysis.cpp
> ==================================================================> ---
lib/Analysis/BasicAliasAnalysis.cpp	(revision 86023)
> +++ lib/Analysis/BasicAliasAnalysis.cpp	(working copy)
> @@ -633,6 +633,15 @@
> AliasAnalysis::AliasResult
> BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size,
>                                const Value *V2, unsigned V2Size) {
> +  // Null pointers do not alias with anything
> +  if (const Constant *C = dyn_cast<Constant>(V1))
> +    if (C->isNullValue())
> +      return NoAlias;
> +
> +  if (const Constant *C = dyn_cast<Constant>(V2))
> +    if (C->isNullValue())
> +      return NoAlias;
> +
As Chris mentioned, for consistency with what the rest of LLVM is doing,
this should check whether the pointers are in the default address space
(0).

Also, this could be generalized by checking the results from 
getUnderlyingObject, since it's not valid to do arithmetic from null to
reach an LLVM identified object either.

Dan

Dan Gohman wrote:
> Hello,
> 
> On Nov 4, 2009, at 1:51 AM, Hans Wennborg wrote:
>>
>> / Hans
>> Index: lib/Analysis/BasicAliasAnalysis.cpp
>>
==================================================================>> ---
lib/Analysis/BasicAliasAnalysis.cpp	(revision 86023)
>> +++ lib/Analysis/BasicAliasAnalysis.cpp	(working copy)
>> @@ -633,6 +633,15 @@
>> AliasAnalysis::AliasResult
>> BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size,
>>                                const Value *V2, unsigned V2Size) {
>> +  // Null pointers do not alias with anything
>> +  if (const Constant *C = dyn_cast<Constant>(V1))
>> +    if (C->isNullValue())
>> +      return NoAlias;
>> +
>> +  if (const Constant *C = dyn_cast<Constant>(V2))
>> +    if (C->isNullValue())
>> +      return NoAlias;
>> +
> 
> As Chris mentioned, for consistency with what the rest of LLVM is doing,
> this should check whether the pointers are in the default address space
> (0).
> 
> Also, this could be generalized by checking the results from 
> getUnderlyingObject, since it's not valid to do arithmetic from null to
> reach an LLVM identified object either.
Also, you can just test for "isa<ConstantPointerNull>(V1)"
directly
instead of casting to Constant then asking isNullValue (assuming the 
types of V1 and V2 are going to be PointerTy which I believe they always 
will be, without looking at the code).

Nick

Dan Gohman wrote:
> Hello,
> 
> On Nov 4, 2009, at 1:51 AM, Hans Wennborg wrote:
>>
>> / Hans
>> Index: lib/Analysis/BasicAliasAnalysis.cpp
>>
==================================================================>> ---
lib/Analysis/BasicAliasAnalysis.cpp	(revision 86023)
>> +++ lib/Analysis/BasicAliasAnalysis.cpp	(working copy)
>> @@ -633,6 +633,15 @@
>> AliasAnalysis::AliasResult
>> BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size,
>>                                const Value *V2, unsigned V2Size) {
>> +  // Null pointers do not alias with anything
>> +  if (const Constant *C = dyn_cast<Constant>(V1))
>> +    if (C->isNullValue())
>> +      return NoAlias;
>> +
>> +  if (const Constant *C = dyn_cast<Constant>(V2))
>> +    if (C->isNullValue())
>> +      return NoAlias;
>> +
> 
> As Chris mentioned, for consistency with what the rest of LLVM is doing,
> this should check whether the pointers are in the default address space
> (0).
> 
> Also, this could be generalized by checking the results from 
> getUnderlyingObject, since it's not valid to do arithmetic from null to
> reach an LLVM identified object either.
I'm not sure what you mean by generalizing.
Do you mean I should do the check on O1 and O2, which are the results of 
calls to getUnderlyingObject?

Something like:

if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
	if (CPN->getType()->getAddressSpace() == 0)
		return NoAlias;

and the same for O2 (maybe extract it into a function?)

/ Hans


> 
> Dan
>