Let Alloca treated as nonnull for any alloca addr space value

[yaxunl]

Summary

Alloca addr space value depends on target triple. No matter what alloca
addr space value is used, alloca instruction is still an alloca instruction
and should be treated equally.

Currently in ValueTracking.cpp, in function isKnownNonZero, only alloca
instruction with addr space 0 is treated as nonnull, which causes less
performant ISA for target amdgcn---amdgiz since its alloca addr space
is 5.

This patch fixes that.

[rampitec]

lib/Analysis/ValueTracking.cpp

1864

What was the original comment about? Is there a chance alloca can be used for malloc?

[arsenm]

lib/Analysis/ValueTracking.cpp

1864

No, the lifetime of the alloca ends when the function does which wouldn't work for malloc

[rampitec]

LGTM

lib/Analysis/ValueTracking.cpp

1864

So I assume the check and comment were misleading.

[nlopes]

This change is incorrect. null can be a valid pointer in a non-0 address space, and alloca may return it.
If your target's address space guarantees that alloca doesn't return null, then we can probably make this target-dependent. But we cannot simply make it unconditional; that's not correct.

[yaxunl]

In D40670#941244, @nlopes wrote:

This change is incorrect. null can be a valid pointer in a non-0 address space, and alloca may return it.
If your target's address space guarantees that alloca doesn't return null, then we can probably make this target-dependent. But we cannot simply make it unconditional; that's not correct.

If whether alloca inst can be zero depending on target, then we need to make it target dependent. I will see if I can add this to TargetTransformInfo.

[yaxunl]

In D40670#942232, @yaxunl wrote:

In D40670#941244, @nlopes wrote:

This change is incorrect. null can be a valid pointer in a non-0 address space, and alloca may return it.
If your target's address space guarantees that alloca doesn't return null, then we can probably make this target-dependent. But we cannot simply make it unconditional; that's not correct.

If whether alloca inst can be zero depending on target, then we need to make it target dependent. I will see if I can add this to TargetTransformInfo.

Well, this will incur lots of interface changes. Essentially all value tracking functions and passes relying on value tracking will require TargetTransformInfo. Do we want to do that?

On the other hand, on which specific target alloca inst could be null? As Matt said, alloca cannot be used to represent malloc, why alloca inst could be null?

[arsenm]

In D40670#942316, @yaxunl wrote:

In D40670#942232, @yaxunl wrote:

In D40670#941244, @nlopes wrote:

This change is incorrect. null can be a valid pointer in a non-0 address space, and alloca may return it.
If your target's address space guarantees that alloca doesn't return null, then we can probably make this target-dependent. But we cannot simply make it unconditional; that's not correct.

If whether alloca inst can be zero depending on target, then we need to make it target dependent. I will see if I can add this to TargetTransformInfo.

Well, this will incur lots of interface changes. Essentially all value tracking functions and passes relying on value tracking will require TargetTransformInfo. Do we want to do that?

On the other hand, on which specific target alloca inst could be null? As Matt said, alloca cannot be used to represent malloc, why alloca inst could be null?

AMDGPU currently has a workaround to avoid alloca ever returning 0. 0 is a valid pointer though. What we really want to represent is that alloca never returns an invalid pointer, not that it never has a 0 value

[yaxunl]

In D40670#942326, @arsenm wrote:

In D40670#942316, @yaxunl wrote:

In D40670#942232, @yaxunl wrote:

In D40670#941244, @nlopes wrote:

This change is incorrect. null can be a valid pointer in a non-0 address space, and alloca may return it.
If your target's address space guarantees that alloca doesn't return null, then we can probably make this target-dependent. But we cannot simply make it unconditional; that's not correct.

If whether alloca inst can be zero depending on target, then we need to make it target dependent. I will see if I can add this to TargetTransformInfo.

Well, this will incur lots of interface changes. Essentially all value tracking functions and passes relying on value tracking will require TargetTransformInfo. Do we want to do that?

On the other hand, on which specific target alloca inst could be null? As Matt said, alloca cannot be used to represent malloc, why alloca inst could be null?

AMDGPU currently has a workaround to avoid alloca ever returning 0. 0 is a valid pointer though. What we really want to represent is that alloca never returns an invalid pointer, not that it never has a 0 value

If the nullptr is not zero, Clang will generate proper instruction for comparing with non-zero nullptr value, so it is not an issue.

For the issue which this patch is trying to solve, we need to know if alloca can be zero to simplify icmp instruction. Knowing alloca inst is valid pointer is not sufficient to simplify icmp instruction.

So far, I do not see a specific target on which alloca inst could be zero. As an instruction used so extensively, I think it is reasonable to assume any alloca inst is non-zero, no matter what addr space it uses.

[yaxunl]

In D40670#942340, @yaxunl wrote:

In D40670#942326, @arsenm wrote:

In D40670#942316, @yaxunl wrote:

In D40670#942232, @yaxunl wrote:

In D40670#941244, @nlopes wrote:

This change is incorrect. null can be a valid pointer in a non-0 address space, and alloca may return it.
If your target's address space guarantees that alloca doesn't return null, then we can probably make this target-dependent. But we cannot simply make it unconditional; that's not correct.

If whether alloca inst can be zero depending on target, then we need to make it target dependent. I will see if I can add this to TargetTransformInfo.

Well, this will incur lots of interface changes. Essentially all value tracking functions and passes relying on value tracking will require TargetTransformInfo. Do we want to do that?

On the other hand, on which specific target alloca inst could be null? As Matt said, alloca cannot be used to represent malloc, why alloca inst could be null?

AMDGPU currently has a workaround to avoid alloca ever returning 0. 0 is a valid pointer though. What we really want to represent is that alloca never returns an invalid pointer, not that it never has a 0 value

If the nullptr is not zero, Clang will generate proper instruction for comparing with non-zero nullptr value, so it is not an issue.

For the issue which this patch is trying to solve, we need to know if alloca can be zero to simplify icmp instruction. Knowing alloca inst is valid pointer is not sufficient to simplify icmp instruction.

So far, I do not see a specific target on which alloca inst could be zero. As an instruction used so extensively, I think it is reasonable to assume any alloca inst is non-zero, no matter what addr space it uses.

David, do you have any suggestion? Is it OK to make value tracking depend on TargetTransformInfo? Thanks.

[silvas]

In D40670#942340, @yaxunl wrote:

In D40670#942326, @arsenm wrote:

In D40670#942316, @yaxunl wrote:

In D40670#942232, @yaxunl wrote:

In D40670#941244, @nlopes wrote:

This change is incorrect. null can be a valid pointer in a non-0 address space, and alloca may return it.
If your target's address space guarantees that alloca doesn't return null, then we can probably make this target-dependent. But we cannot simply make it unconditional; that's not correct.

If whether alloca inst can be zero depending on target, then we need to make it target dependent. I will see if I can add this to TargetTransformInfo.

Well, this will incur lots of interface changes. Essentially all value tracking functions and passes relying on value tracking will require TargetTransformInfo. Do we want to do that?

On the other hand, on which specific target alloca inst could be null? As Matt said, alloca cannot be used to represent malloc, why alloca inst could be null?

AMDGPU currently has a workaround to avoid alloca ever returning 0. 0 is a valid pointer though. What we really want to represent is that alloca never returns an invalid pointer, not that it never has a 0 value

If the nullptr is not zero, Clang will generate proper instruction for comparing with non-zero nullptr value, so it is not an issue.

For the issue which this patch is trying to solve, we need to know if alloca can be zero to simplify icmp instruction. Knowing alloca inst is valid pointer is not sufficient to simplify icmp instruction.

So far, I do not see a specific target on which alloca inst could be zero. As an instruction used so extensively, I think it is reasonable to assume any alloca inst is non-zero, no matter what addr space it uses.

FWIW I work on an out of tree target where an alloca can have a value that is numerically 0. I expect many accelerators are in the same situation.

Out of curiosity, does the OpenCL spec say anything about the numerical value of the address of __local declarations (which is the only thing where clang will generate an alloca with non-zero address space IIRC) (of course, clang isn't the only frontend but it is at least a useful sanity check).

[yaxunl]

In D40670#944760, @silvas wrote:

In D40670#942340, @yaxunl wrote:

In D40670#942326, @arsenm wrote:

In D40670#942316, @yaxunl wrote:

In D40670#942232, @yaxunl wrote:

In D40670#941244, @nlopes wrote:

This change is incorrect. null can be a valid pointer in a non-0 address space, and alloca may return it.
If your target's address space guarantees that alloca doesn't return null, then we can probably make this target-dependent. But we cannot simply make it unconditional; that's not correct.

If whether alloca inst can be zero depending on target, then we need to make it target dependent. I will see if I can add this to TargetTransformInfo.

Well, this will incur lots of interface changes. Essentially all value tracking functions and passes relying on value tracking will require TargetTransformInfo. Do we want to do that?

On the other hand, on which specific target alloca inst could be null? As Matt said, alloca cannot be used to represent malloc, why alloca inst could be null?

AMDGPU currently has a workaround to avoid alloca ever returning 0. 0 is a valid pointer though. What we really want to represent is that alloca never returns an invalid pointer, not that it never has a 0 value

If the nullptr is not zero, Clang will generate proper instruction for comparing with non-zero nullptr value, so it is not an issue.

For the issue which this patch is trying to solve, we need to know if alloca can be zero to simplify icmp instruction. Knowing alloca inst is valid pointer is not sufficient to simplify icmp instruction.

So far, I do not see a specific target on which alloca inst could be zero. As an instruction used so extensively, I think it is reasonable to assume any alloca inst is non-zero, no matter what addr space it uses.

FWIW I work on an out of tree target where an alloca can have a value that is numerically 0. I expect many accelerators are in the same situation.

Out of curiosity, does the OpenCL spec say anything about the numerical value of the address of __local declarations (which is the only thing where clang will generate an alloca with non-zero address space IIRC) (of course, clang isn't the only frontend but it is at least a useful sanity check).

The LLVM language manual (https://llvm.org/docs/LangRef.html#alloca-instruction) said:

The ‘alloca‘ instruction allocates memory on the stack frame of the currently executing function, to be automatically released when this function returns to its caller. The object is always allocated in the address space for allocas indicated in the datalayout.

Therefore alloca instruction is not supposed to be used for allocating memory other than private memory in OpenCL. The target datalayout specifies the address space used by alloca.

Also, non-zero alloca address space has already been used by amdgcn target in LLVM/clang trunk. For amdgcn---amdgiz triple, alloca address space is 5. amdgcn---amdgiz target uses 5 as alloca address space because it needs to use address space 0 as generic address space for better support C++-based kernel languages.

Non-zero alloca address space is no special from zero alloca address space. The alloca instruction in non-zero alloca address space still allocates memory on stack.

[yaxunl]

How about introduce nullptr value for each addr space in data layout? E.g., assume alloca addr space is 3 and nullptr value of addr space 3 is -1. alloca of addr space 3 could return 0, but never return -1.

Then this code

if (isa<AllocaInst>(V) && Q.DL.getAllocaAddrSpace() == 0)

can be changed as

if (isa<AllocaInst>(V) && Q.DL.getAllocaNullPointerValue() == 0)

This assumes that alloca never returns nullptr value.

Nuno, Sean, will this work for you?

Thanks.

[nlopes]

In D40670#947019, @yaxunl wrote:

How about introduce nullptr value for each addr space in data layout? E.g., assume alloca addr space is 3 and nullptr value of addr space 3 is -1. alloca of addr space 3 could return 0, but never return -1.

Then this code

if (isa<AllocaInst>(V) && Q.DL.getAllocaAddrSpace() == 0)

can be changed as

if (isa<AllocaInst>(V) && Q.DL.getAllocaNullPointerValue() == 0)

This assumes that alloca never returns nullptr value.

Nuno, Sean, will this work for you?

Thanks.

Sorry for the delay.
What if a target doesn't have an invalid pointer? This is not uncommon in embedded ISAs.

I don't particularly like the idea of mixing null pointers (which we define as having the value zero ATM), alloca not being able to return a null pointer, and the possibility of changing the value of null pointers to a non-zero value.

[yaxunl]

In D40670#952389, @nlopes wrote:

In D40670#947019, @yaxunl wrote:

How about introduce nullptr value for each addr space in data layout? E.g., assume alloca addr space is 3 and nullptr value of addr space 3 is -1. alloca of addr space 3 could return 0, but never return -1.

Then this code

if (isa<AllocaInst>(V) && Q.DL.getAllocaAddrSpace() == 0)

can be changed as

if (isa<AllocaInst>(V) && Q.DL.getAllocaNullPointerValue() == 0)

This assumes that alloca never returns nullptr value.

Nuno, Sean, will this work for you?

Thanks.

Sorry for the delay.
What if a target doesn't have an invalid pointer? This is not uncommon in embedded ISAs.

I don't particularly like the idea of mixing null pointers (which we define as having the value zero ATM), alloca not being able to return a null pointer, and the possibility of changing the value of null pointers to a non-zero value.

How about adding a hook TargetTransformInfo::isAllocaPtrValueNonZero which returns true if alloca inst value is always non-zero.

The drawback is that some ValueTracking functions will depend on TargetTransformInfo. As a result, those passes using ValueTrackign will require TargetTransformInfo.

What do you think?

Thanks.

[nlopes]

In D40670#954573, @yaxunl wrote:

In D40670#952389, @nlopes wrote:

In D40670#947019, @yaxunl wrote:

How about introduce nullptr value for each addr space in data layout? E.g., assume alloca addr space is 3 and nullptr value of addr space 3 is -1. alloca of addr space 3 could return 0, but never return -1.

Then this code

if (isa<AllocaInst>(V) && Q.DL.getAllocaAddrSpace() == 0)

can be changed as

if (isa<AllocaInst>(V) && Q.DL.getAllocaNullPointerValue() == 0)

This assumes that alloca never returns nullptr value.

Nuno, Sean, will this work for you?

Thanks.

Sorry for the delay.
What if a target doesn't have an invalid pointer? This is not uncommon in embedded ISAs.

I don't particularly like the idea of mixing null pointers (which we define as having the value zero ATM), alloca not being able to return a null pointer, and the possibility of changing the value of null pointers to a non-zero value.

How about adding a hook TargetTransformInfo::isAllocaPtrValueNonZero which returns true if alloca inst value is always non-zero.

The drawback is that some ValueTracking functions will depend on TargetTransformInfo. As a result, those passes using ValueTrackign will require TargetTransformInfo.

What do you think?

Thanks.

I like that solution!

[yaxunl]

In D40670#954590, @nlopes wrote:

In D40670#954573, @yaxunl wrote:

In D40670#952389, @nlopes wrote:

In D40670#947019, @yaxunl wrote:

How about introduce nullptr value for each addr space in data layout? E.g., assume alloca addr space is 3 and nullptr value of addr space 3 is -1. alloca of addr space 3 could return 0, but never return -1.

Then this code

if (isa<AllocaInst>(V) && Q.DL.getAllocaAddrSpace() == 0)

can be changed as

if (isa<AllocaInst>(V) && Q.DL.getAllocaNullPointerValue() == 0)

This assumes that alloca never returns nullptr value.

Nuno, Sean, will this work for you?

Thanks.

Sorry for the delay.
What if a target doesn't have an invalid pointer? This is not uncommon in embedded ISAs.

I don't particularly like the idea of mixing null pointers (which we define as having the value zero ATM), alloca not being able to return a null pointer, and the possibility of changing the value of null pointers to a non-zero value.

How about adding a hook TargetTransformInfo::isAllocaPtrValueNonZero which returns true if alloca inst value is always non-zero.

The drawback is that some ValueTracking functions will depend on TargetTransformInfo. As a result, those passes using ValueTrackign will require TargetTransformInfo.

What do you think?

Thanks.

I like that solution!

Since this may change quite a few files in llvm, I will post an RFC to llvm-dev.

[yaxunl]

RFC posted http://lists.llvm.org/pipermail/llvm-dev/2017-December/119724.html

[yaxunl]

@nlopes Hal Finkel proposed a solution which works for me http://lists.llvm.org/pipermail/llvm-dev/2017-December/119738.html . Can you take a look if it works for you? Thanks.

[arsenm]

We should add more holistic understanding of non-0 null address spaces to address this

lib/Analysis/ValueTracking.cpp

         if (rangeMetadataExcludesValue(Ranges, ZeroValue))
           return true;
       }
     }
   }
 
   // Check for pointer simplifications.
   if (V->getType()->isPointerTy()) {
-    // Alloca never returns null, malloc might.
-    if (isa<AllocaInst>(V) && Q.DL.getAllocaAddrSpace() == 0)
+    // Alloca never returns null.
+    if (isa<AllocaInst>(V))
       return true;
 
     // A byval, inalloca, or nonnull argument is never null.
     if (const Argument *A = dyn_cast<Argument>(V))
       if (A->hasByValOrInAllocaAttr() || A->hasNonNullAttr())
         return true;
 
     // A Load tagged with nonnull metadata is never null.

test/Analysis/ValueTracking/alloca-nonnull.ll

+; RUN: opt -S -instsimplify < %s | FileCheck %s
+
+target datalayout = "A5"
+
+; CHECK: ret i1 true
+define i1 @f()  {
+entry:
+  %a = alloca i32, align 4, addrspace(5)
+  %tobool = icmp ne i32 addrspace(5)* %a, null
+  ret i1 %tobool
+}