[NVPTX] Implement NVPTX AliasAnalysis

[asavonic]

Summary

NVPTXAliasAnalysis extends the default AA to take pointer address spaces
into account. The analysis assumes that pointers in different address
spaces do not alias, unless one of them is generic (flat) address
space.

The patch also implements pointsToConstantMemory (via getModRefInfoMask)
to expose semantic of the constant address space to the optimizer
as discussed in D112466.

[tra]

LGTM in general.

@asbirlea : Could you take a look and check if we've got all the right pieces for the pass for both new and old PM, please?

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

65

Nit. I'd rephrase it a bit and put alias() call closer to the condition check.

if (getAliasResult(AS1, AS2) != AliasResult::NoAlias) 
    return AAResultBase::alias(Loc1, Loc2, AAQI);
return  AliasResult::NoAlias;

Maybe, even fold it into a single return (...== NoAlias) ? NoAlias : alias();

72

Kernel parameters are also read-only: https://docs.nvidia.com/cuda/parallel-thread-execution/index.html#state-spaces

[asavonic]

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

65

Done.

72

Thanks! Added param space to the check and updated LIT tests.

[tra]

@nikic -- we could use your input here. The patch looks OK to me, but I'm not particularly familiar with AA machinery in general and could use a second opinion.

[tschuett]

Could that be a more general solution? You ask the target if address spaces A and B could alias?

[nikic]

Looks fine from a cursory look. To double check, this property also holds up in the presence of addrspacecasts? Note that AA will skip past those, so if you compare ptr addrspace(1) %x and addrspacecast (ptr addrspace(5) %y to ptr addrspace(1)), this will perform a comparison of ptr addrspace(1) %x and ptr addrspace(5) %y. I assume that the addrspacecast would just be considered illegal in the relevant cases?

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

65

Can't you just return getAliasResult(AS1, AS2) here? Calling AAResultBase methods is not necessary, it'll always return MayAlias (there are some confusing comments about this in other AA implemementations, but chaining of AA providers happens at a different level nowadays).

84

Shouldn't be necessary, as the BasicAA implementation already covers this.

[asavonic]

• Rebased
• Removed calls to AAResultBase and the extra check for GV->isConstant.

[asavonic]

This took a while, I'm sorry for not following up earlier.

In D124787#3614613, @nikic wrote:

Looks fine from a cursory look. To double check, this property also holds up in the presence of addrspacecasts? Note that AA will skip past those, so if you compare ptr addrspace(1) %x and addrspacecast (ptr addrspace(5) %y to ptr addrspace(1)), this will perform a comparison of ptr addrspace(1) %x and ptr addrspace(5) %y. I assume that the addrspacecast would just be considered illegal in the relevant cases?

Yes, pointers in different address spaces do not alias unless at least one of them is in generic (flat) address space. Address space casts can only cast from/to generic address space, otherwise they are invalid.

Note that AA will skip past those

This might be an opportunity to improve the analysis. When we skip addrspacecasts from two pointers, we may end up with pointers in generic address space, and the result is always MayAlias. We can get better results from original pointers if they are in different address spaces (e.g. local and global AS never alias).

In D124787#3613322, @tschuett wrote:

Could that be a more general solution? You ask the target if address spaces A and B could alias?

We can add a simple check to TTI, and integrate it to BasicAA, but I think the current interface is simple enough already. Having access to MemoryLocation can be important: we can traverse a chain of address space casts and make a better AA decision (see AMDGPU AA for example). Also, pointsToConstantMemory check is done via AA anyway, so we have to implement a target-specific AA to customize it.

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

65

Right, thank you!

84

Right, it is handled in BasicAA.

[asavonic]

• Rebased.
• Replaced pointsToConstantMemory with getModRefInfoMask due to the API change.
• Removed DataLayout variable that was unused.

[asavonic]

@nikic, @tra, please let me know if any other changes are needed.

[tra]

LGTM in general for LLVM as it is now. But...

llvm/test/CodeGen/NVPTX/nvptx-aa.ll

83

Looks like recently PTX grew ability to convert .param to generic AS:
https://docs.nvidia.com/cuda/parallel-thread-execution/index.html#data-movement-and-conversion-instructions-cvta

AFAICT, when that happens, the address *may* be converted into a global pointer:
https://docs.nvidia.com/cuda/parallel-thread-execution/index.html#generic-addressing says:

The Kernel Function Parameters (.param) window is contained within the .global window.

So, technically, a global pointer *may* alias with a param pointer on some GPUs via ASC(param->generic->global).

The good news is that we don't have cvta.param implemented yet, so as things stand, there's no aliasing between param and global, but that will likely change in the future. We may want to either conservatively make them "mayAlias" from now on, or keep them as "NoAlias" for now with a TODO to make sure we update it when we get to implement cvta.param in lib/Target/NVPTX/NVPTXIntrinsics.td

[asavonic]

llvm/test/CodeGen/NVPTX/nvptx-aa.ll

83

Hmm.. this is unfortunate. If param is a subset of global, then it also cannot be treated as constant memory. I'll update alias and getModRefInfoMask functions to handle this.

[asavonic]

• param pointers may alias global pointers.
• added more test cases for param.

[tra]

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

62

param->generic is not implemented yet, so this is overly conservative.

Do we have any way to check whether ASC(param->generic) is available? If we do, we could use it to determine if we should return MayAlias or NoAlias.

llvm/test/CodeGen/NVPTX/nvptx-aa.ll

83

.param AS is a bit special when it comes to constantness.

Param space should not ever be used in the user-provided IR. As far as the user IR is concerned, byval arguments live in generic AS and are writeable.

In order to make sure byval arguments are never written to, as required by PTX, we make a local copy, if one needs to store to it. From that point of view, AS should also consider param space as writable, even though we'll never generate actual writes to it and redirect them to a local copy.

[asavonic]

llvm/test/CodeGen/NVPTX/nvptx-aa.ll

83

Ok, to summarize:

1. NVPTXLowerArgs does not allow any writes or pointer copies of param pointers by redirecting them to a local copy.

2. cvta.param (PTX 7.7+ and SM_70+) is not implemented, and therefore we have no way to cast it to generic and avoid the redirect (1).

So while both these implementation details are true, param pointers point to "constant" memory (there are no writes to it), and do not alias with anything except for other param pointers.

I guess we can put a TODO explaining this for now. Once NVPTXLowerArgs is changed to support cvta.param we'll have to re-evaluate this.

[asavonic]

• Rolled back changes for param address space: treat it as constant memory until cvta.param is supported.
• Changed tests to use opaque pointers.

[asavonic]

@tra, can you please check if it is OK to merge this patch?

[tra]

Still LGTM with a couple of nits.

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

73

CtxI does not seem to be used. Do we need it?

91

IMO, the code would be more readable w/o the variable. Just do if (isConstOrParam(Loc.Ptr->getType()->getPointerAddressSpace())) directly here and below.

Having the variable makes me, as a reader, ask -- "what was the variable set to before?", "what else is this variable used for?" and that's just a distraction here.

[asavonic]

• Fixed code style issues.

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

73

It is a new parameter from D136512. We do not currently use it, so I guess it is better to drop it to avoid warnings.

91

Makes sense. Done.

[tra]

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

73

So, the intent is to match the signature of AAResultBase::alias()?
OK. I was thinking of getting rid of the argument altogether, but it looks like it's needed, after all.