BasicAliasAnalysis: Null pointers do not alias with anything

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

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

patch.patch (766 Bytes)

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,

/ 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,

/ 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,

/ 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

Yes, thanks.

Dan

Dan Gohman wrote:

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?)

Yes, thanks.

Ok, patch with test case attached.

/ Hans

BasicAliasAnalysis.diff (1.47 KB)

Applied, thanks!

Dan