This is an archive of the discontinued LLVM Phabricator instance.

RegAlloc: Allow targets to split register allocation
ClosedPublic

Authored by arsenm on Dec 4 2018, 4:24 PM.

Details

Summary

AMDGPU normally spills SGPRs to VGPRs. Previously, since all register
classes are handled at the same time, this was problematic. We don't
know ahead of time how many registers will be needed to be reserved to
handle the spilling. If no VGPRs were left for spilling, we would have
to try to spill to memory. If the spilled SGPRs were required for exec
mask manipulation, it is highly problematic because the lanes active
at the point of spill are not necessarily the same as at the restore
point.

Avoid this problem by fully allocating SGPRs in a separate regalloc
run from VGPRs. This way we know the exact number of VGPRs needed, and
can reserve them for a second run. This fixes the most serious
issues, but it is still possible using inline asm to make all VGPRs
unavailable. Start erroring in the case where we ever would require
memory for an SGPR spill.

This is implemented by giving each regalloc pass a callback which
reports if a register class should be handled or not. A few passes
need some small changes to deal with leftover virtual registers.

In the AMDGPU implementation, a new pass is introduced to take the
place of PrologEpilogInserter for SGPR spills emitted during the first
run.

One disadvantage of this is currently StackSlotColoring is no longer
used for SGPR spills. It would need to be run again, which will
require more work.

Error if the standard -regalloc option is used. Introduce new separate
-sgpr-regalloc and -vgpr-regalloc flags, so the two runs can be
controlled individually. PBQB is not currently supported, so this also
prevents using the unhandled allocator.

Diff Detail

Event Timeline

arsenm created this revision.Dec 4 2018, 4:24 PM

Hi Matt,

Have you tried to use combined V+S register classes?
By describing such classes, when a S or V register would be split, they would eventually have constraints in that "super" class. Thus, inside of spilling, the splitting mechanism would naturally insert copies of the form [V|S] = copy V+S or V+S = copy [V|S], which seem to be what you are trying to achieve. The advantage of such approach is that we would not have to effectively split the allocation.

Cheers,
-Quentin

arsenm added a comment.Dec 6 2018, 9:24 AM

Hi Matt,

Have you tried to use combined V+S register classes?
By describing such classes, when a S or V register would be split, they would eventually have constraints in that "super" class. Thus, inside of spilling, the splitting mechanism would naturally insert copies of the form [V|S] = copy V+S or V+S = copy [V|S], which seem to be what you are trying to achieve. The advantage of such approach is that we would not have to effectively split the allocation.

Cheers,
-Quentin

I'm not sure I follow this. These aren't spilled with ordinary copies. This uses cross lane instructions to read/write SGPRs into the various lane VGPRs (i.e 64 SGPRs can be spilled to each lane in the wave's VGPR). We also can't legally copy from V to S. Having virtual registers with the combined class doesn't really conceptually make sense for us either (and would probably break every single place that we need to consider these)

This also wouldn't allow us to change the set of reserved registers in the middle of allocation, which is part of the problem.

rampitec added inline comments.Dec 6 2018, 5:26 PM
lib/Target/AMDGPU/AMDGPUTargetMachine.cpp
75 ↗(On Diff #176729)

!isSGPRClass() to catch [potentially] remaining strange register classes.

1064 ↗(On Diff #176729)

You need to pass filter to PreRewrite as well.

I'm not sure I follow this. These aren't spilled with ordinary copies

I would expect that you could use ordinary copies + subreg here and do the proper expansion in the later expand post RA pass like every other copy.

This uses cross lane instructions to read/write SGPRs into the various lane VGPRs (i.e 64 SGPRs can be spilled to each lane in the wave's VGPR). We also can't legally copy from V to S. Having virtual registers with the combined class doesn't really conceptually make sense for us either (and would probably break every single place that we need to consider these)

That wouldn't appear in elsewhere than tablegen. That's just something to tell RA that the biggest unconstrained class is V+S.

This also wouldn't allow us to change the set of reserved registers in the middle of allocation, which is part of the problem.

I missed that part, but I also don't get why this is a problem. IIRC we can always narrow the set of available registers for each virtual register.

Anyhow, the changes on the generic parts looks mostly good to me. Comments inlined.

include/llvm/CodeGen/RegAllocCommon.h
23 ↗(On Diff #176729)

Please add doxygen comment.

lib/CodeGen/RegAllocGreedy.cpp
615 ↗(On Diff #176729)

Why do we need both constructors?

707 ↗(On Diff #176729)

Removing this assert is worrisome. Why do we need that?

lib/CodeGen/TargetFrameLoweringImpl.cpp
21 ↗(On Diff #176729)

Why do we need this change?

I'm not sure I follow this. These aren't spilled with ordinary copies

I would expect that you could use ordinary copies + subreg here and do the proper expansion in the later expand post RA pass like every other copy.

We don't model different lanes as subregisters, and trying to would be a pretty radical change. I can almost see a way to hack it to work, but it would involve adding an enormous number of new subregister indexes. Unless you mean using some kind of RMW copy (since the old single lane view of the register's value needs to be preserved)

arsenm updated this revision to Diff 178990.Dec 19 2018, 4:10 PM
arsenm marked 5 inline comments as done.

Remove leftover changes and add comment

ping

Pass the filter to PreRewrite.

Hi Matt,

Couple of nitpicks inline.
My online remaining concern is exposing ClearVirtRegs.

Cheers,
-Quentin

lib/CodeGen/RegAllocBase.cpp
179 ↗(On Diff #178990)

For debugging purposes, add a DEBUG statement for each case.

lib/CodeGen/RegAllocFast.cpp
73 ↗(On Diff #178990)

Should this be const RegClassFilterFunc & everywhere?

78 ↗(On Diff #178990)

It feels dangerous to expose the ClearVirtRegs to me.
Could we deduce what has to be cleared based on what we allocate instead of exposing this?

1350 ↗(On Diff #178990)

Could we have just one createFastRegisterAllocator with default arguments?
(Also ClearVirtReg should disappear per my other comment IMO).

lib/CodeGen/RegAllocGreedy.cpp
603 ↗(On Diff #178990)

Ditto: Just one createXXX method.

arsenm marked 2 inline comments as done.Feb 13 2019, 9:18 AM
arsenm added inline comments.
lib/CodeGen/RegAllocFast.cpp
78 ↗(On Diff #178990)

The problem is somewhere needs to set NoVRegs property. The same parameter is added to createVirtRegRewriter, but fastregalloc does the assignment itself.

I don't think this can be inferred, and the target needs to say when it's done allocating register classes. For example it would be possible to have a degenerate function where all SGPRs are allocated in the first run, and there happen to be no VGPR vregs. Intervening passes may want to introduce new vregs to be taken care of by the later runs, but that won't work if the earlier pass decided to infer that all registers were taken care of

arsenm marked an inline comment as done.Feb 13 2019, 9:22 AM
arsenm added inline comments.
lib/CodeGen/RegAllocFast.cpp
78 ↗(On Diff #178990)

Actually I stopped creating new virtual registers at some point in the current implementation, but I still may want to do so in the future

arsenm marked an inline comment as done.Feb 13 2019, 9:29 AM

ping

Pass the filter to PreRewrite.

I'm not sure what good that would do as it doesn't do anything now

lib/CodeGen/RegAllocFast.cpp
1350 ↗(On Diff #178990)

The RegAllocRegistry requires the type to be the no-argument function pass constructor. I could change that, but then all would have the ClearVirtRegs argument or not

arsenm updated this revision to Diff 186692.Feb 13 2019, 10:12 AM

Partially address comments.

This also probably needs some more test fixes, but the fast regalloc rewrite patches need rebasing first

Is this still alive?

Is this still alive?

Yes, but it depends on the fastregalloc rewrite patches (which I need to rrebase the tests for, for the 100th time which takes forever)

but it depends on the fastregalloc rewrite patches

Which ones?

but it depends on the fastregalloc rewrite patches

Which ones?

D54368 and D52010. I started rebasing the tests a few months ago but didn't finish; I think I got distracted by regressed loop spills vs. last time I rebased

Thanks for the pointers, I'll try to look into reviewing D52010 next week.

Herald added a project: Restricted Project. · View Herald TranscriptDec 22 2020, 5:54 PM
rampitec added inline comments.Dec 23 2020, 10:29 AM
llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp
1369

GCNRegBankReassign also works with SGPRs. Which means you need a pre-rewriter here, which needs to have a different subset of passes and an RC filter.

llvm/lib/Target/AMDGPU/SIFrameLowering.cpp
1152

It can be saddr with flat scratch. It seems it needs to be fixed in a separate patch first.

rampitec added inline comments.Dec 23 2020, 10:48 AM
llvm/lib/Target/AMDGPU/SIFrameLowering.cpp
1152

Never mind, this is one of SI_SPILL opcodes, not real instruction yet.

Since GCNRegBanksReassign is removed this is LGTM.

qcolombet accepted this revision.May 12 2021, 1:43 PM

LGTM.
Disclaimer: I didn't really look at the AMDGPU changes.

This revision is now accepted and ready to land.May 12 2021, 1:43 PM
rampitec accepted this revision.May 12 2021, 1:45 PM

LGTM.
Disclaimer: I didn't really look at the AMDGPU changes.

I did. Thanks!

@arsenm it is a good idea to run PSDB before this change.

lkail added a subscriber: lkail.Sep 14 2021, 5:08 AM