This is an archive of the discontinued LLVM Phabricator instance.

[NVPTX] Implement NVPTX AliasAnalysis
ClosedPublic

Authored by asavonic on May 2 2022, 10:55 AM.

Details

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.

Diff Detail

Event Timeline

asavonic created this revision.May 2 2022, 10:55 AM
asavonic requested review of this revision.May 2 2022, 10:55 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 2 2022, 10:55 AM
tra added a subscriber: asbirlea.May 2 2022, 2:09 PM

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
asavonic updated this revision to Diff 440337.Jun 27 2022, 11:33 AM
asavonic added inline comments.
llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp
65

Done.

72

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

tra added a subscriber: nikic.Jun 27 2022, 12:33 PM

@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.

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

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 updated this revision to Diff 466570.Oct 10 2022, 11:38 AM
  • Rebased
  • Removed calls to AAResultBase and the extra check for GV->isConstant.

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

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

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 updated this revision to Diff 481649.Dec 9 2022, 7:32 AM
asavonic edited the summary of this revision. (Show Details)
  • Rebased.
  • Replaced pointsToConstantMemory with getModRefInfoMask due to the API change.
  • Removed DataLayout variable that was unused.

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

tra accepted this revision.Dec 9 2022, 11:09 AM

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

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

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

This revision is now accepted and ready to land.Dec 9 2022, 11:09 AM
asavonic added inline comments.Dec 12 2022, 7:39 AM
llvm/test/CodeGen/NVPTX/nvptx-aa.ll
82

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 updated this revision to Diff 482126.Dec 12 2022, 7:43 AM
  • param pointers may alias global pointers.
  • added more test cases for param.
tra added inline comments.Dec 12 2022, 11:16 AM
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
82

.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 added inline comments.Jan 25 2023, 4:44 PM
llvm/test/CodeGen/NVPTX/nvptx-aa.ll
82

Ok, to summarize:

  1. NVPTXLowerArgs does not allow any writes or pointer copies of param pointers by redirecting them to a local copy.
  1. 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 updated this revision to Diff 493640.Jan 31 2023, 8:58 AM
  • Rolled back changes for param address space: treat it as constant memory until cvta.param is supported.
  • Changed tests to use opaque pointers.

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

tra accepted this revision.Jan 31 2023, 10:51 AM

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 updated this revision to Diff 493701.Jan 31 2023, 12:04 PM
  • 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 accepted this revision.Jan 31 2023, 12:19 PM
tra added inline comments.
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.

This revision was automatically updated to reflect the committed changes.