[RFC] Add TargetTransformInfo::isAllocaPtrValueNonZero and let ValueTracking depend on TargetTransformInfo

Some optimizations depend on whether alloca instruction always has non-zero value. Currently, this checking is done by isKnownNonZero() in ValueTracking, and it assumes alloca in address space 0 always has non-zero value but alloca in non-zero address spaces does not always have non-zero value.

However, this assumption is incorrect for certain targets. For example, amdgcn—amdgiz target has alloca in address space 5, and its alloca always has non-zero value. This assumption causes some optimizations disabled for amdgcn—amdgiz target.

After discussions at https://reviews.llvm.org/D40670, I propose to introduce TargetTransformInfo::isAllocaPtrValueNonZero for representing whether alloca instruction always has non-zero value, and add a TargetTransformInfo argument to ValueTracking functions e.g. isKnownNonZero().

As a result, passes using ValueTracking will require TargetTransformInfo.

Comments are welcome.

Thanks.

Sam

Hi, Sam,

Our general design has been that TTI is for cost modeling, not for providing semantic information. This piece of information can go in DataLayout, and I think we should put it there. Especially given that this affects our canonicalization process, or preference should be to avoid TTI. The more than TTI affects our canonical form, the more fragmented it becomes, and the harder it is to understand. Putting it in DataLayout also prevents us from having to propagate TTI into a bunch of ValueTracking functions (and maximally retains our ability to process IR without backends compiled in).

Thanks again,
Hal

Hal,

Thanks for your suggestion. I think that makes sense.

Currently, non-zero alloca address space is already represented by data layout, e.g., the last component of the data layout of amdgcn—amdgiz target is -A5, which means alloca is in address space 5. How about adding a letter z to -A5 to indicate alloca may have zero value? i.e. -A5 means alloca is in address space 5 and always has non-zero value, -A5z means alloca is in address space 5 and may have zero value.

Then we can add function DataLayout::isAllocaPtrValueNonZero() to check whether alloca always has non-zero value.

Sam

I believe that we should phrase this in a way not directly connected to alloca, but to dereferenceability. We currently assume that dereferenceable pointers can’t be null in address space 0, but we don’t make that assumption about other address spaces (where null might be a valid address). I think that we should address this problem, and then simply apply the result to alloca. We currently have, for address spaces: How about we allow the addition of ‘n’ (for non-zero) after the address-space number. This, implied by default for address space zero but not others, will imply that dereferenceable address are non-null. We can then apply this in isKnownNonZero in the places where we currently check for address space zero. Would that address your use case? Or can you have null dereferenceable pointers in that address space, just not ones from alloca? -Hal

This should work for me. I will check with Nuno Lopes whether this works for him.

Thanks.

Sam

I would like to clarify what “null” means exactly. One related thing I would like in the future is for the DataLayout to specify what numeric value is the invalid, non-dereferencalbe pointer. i.e. the invalid pointer does is a some non-0 bit pattern like -1.

-Matt

Okay. That’s certainly a separate discussion. For the purpose of this question I mean null as zero. Can you have dereferenceable pointers, with a value of zero when converted to an integer, in that address space? Or are you interested only in saying that alloca never produces pointers with a value of zero when converted to an integer? Thanks again, Hal

FWIW on Pixel Visual Core, we have on-chip memories for which the pointer with numerical value zero is a valid location (and it is natural to model these as allocas).

As I’ve come to learn, it’s actually difficult for the hardware folks to make 0 not be valid since the address decoders selecting which word from a memory should be read out naturally take 0 to N as input. (I.e. at the end of the day everything is actually a natural 0-based index into an array)

The only case I can think of where it is convenient to make 0 be invalid is when you are dealing with a relatively sparsely populated memory map (either virtual or hardcoded as in a microcontroller) and you can simply avoid putting something at 0. But that’s more about the logic that looks at the high bits of the address to determine which mapping in the memory map is being accessed.

So I assume that it most of the time when you have explicitly addressed memories that are not part of a larger linear memory map, the numerically 0 pointer will actually be valid. On-chip scratchpad memories on accelerators are probably going to be a common case of this (such as the AMDGPU LDS in this thread I presume).

– Sean Silva

Certainly. I can imagine, however, cases where zero is a valid address in general, but will never be a stack-allocated address (e.g., because your stack grows down, so 0 is the very last byte of the possible stack in that address space, and the stack just can’t grow that far because there’s other data there). -Hal

I think this is the problem we actually want to be solving. On AMDGPU the stack grows up and naturally begins at 0. 0 is a valid, dereferencable pointer. We have a workaround now where we won’t allocate a user object at offset 0, but that’s mostly just because before when alloca had to be in the default address space this was required. I would rather not do the work to push this back in that direction. The point of this patch originally I thought was to fix tests which are comparing against null pointers. We really want them to be checking against the true invalid pointer value.

-Matt