This is an archive of the discontinued LLVM Phabricator instance.

[MachineScheduler] Track physical register dependencies per-regunit
ClosedPublic

Authored by foad on Jul 28 2023, 8:48 AM.

Details

Summary
Change the scheduler's physical register dependency tracking from
registers-and-their-aliases to regunits. This has a couple of advantages
when subregisters are used:

- The dependency tracking is more accurate and creates fewer useless
  edges in the dependency graph. An AMDGPU example, edited for clarity:

    SU(0): $vgpr1 = V_MOV_B32 $sgpr0
    SU(1): $vgpr1 = V_ADDC_U32 0, $vgpr1
    SU(2): $vgpr0_vgpr1 = FLAT_LOAD_DWORDX2 $vgpr0_vgpr1, 0, 0

  There is a data dependency on $vgpr1 from SU(0) to SU(1) and from
  SU(1) to SU(2). But the old dependency tracking code also added a
  useless edge from SU(0) to SU(2) because it thought that SU(0)'s def
  of $vgpr1 aliased with SU(2)'s use of $vgpr0_vgpr1.

- On targets like AMDGPU that make heavy use of subregisters, each
  register can have a huge number of aliases - it can be quadratic in
  the size of the largest defined register tuple. There is a much lower
  bound on the number of regunits per register, so iterating over
  regunits is faster than iterating over aliases.

The LLVM compile-time tracker shows a tiny overall improvement of 0.03%
on X86. I expect a larger compile-time improvement on targets like
AMDGPU.

Recommit after fixing AggressiveAntiDepBreaker in D156880.

Diff Detail

Event Timeline

foad created this revision.Jul 28 2023, 8:48 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 28 2023, 8:48 AM
foad requested review of this revision.Jul 28 2023, 8:48 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 28 2023, 8:48 AM
foad edited the summary of this revision. (Show Details)
arsenm added inline comments.Jul 28 2023, 9:57 AM
llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
225–226

liveins should really use regunits too

226–230

This can refine to check the lanemask too

251–252

Don't see why this isn't a reference anymore

foad updated this revision to Diff 545221.Jul 28 2023, 10:29 AM

Fix DefMIDesc.

foad marked 2 inline comments as done.Jul 28 2023, 10:30 AM
foad added inline comments.
llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
225–226

Not in this patch :)

226–230

Is there a neat way to iterate regunits for a RegisterMaskPair?

251–252

That was an oversight.

arsenm added inline comments.Jul 28 2023, 11:30 AM
llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
226–230

Not that I know off the top of my head. Should at least add a fixme here

arsenm added inline comments.Jul 28 2023, 11:33 AM
llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
226–230

I think you need to use MCRegUnitMaskIterator

kparzysz accepted this revision.Jul 28 2023, 1:27 PM

LGTM, thanks!

This revision is now accepted and ready to land.Jul 28 2023, 1:27 PM
This revision was landed with ongoing or failed builds.Jul 29 2023, 7:35 AM
This revision was automatically updated to reflect the committed changes.
foad marked 2 inline comments as done.
foad reopened this revision.Aug 2 2023, 5:24 AM
This revision is now accepted and ready to land.Aug 2 2023, 5:24 AM
foad updated this revision to Diff 546423.Aug 2 2023, 5:25 AM

Rebase on D156880.

arsenm accepted this revision.Aug 2 2023, 5:30 AM
This revision was landed with ongoing or failed builds.Aug 7 2023, 7:42 AM
This revision was automatically updated to reflect the committed changes.
bjope added a subscriber: bjope.Aug 7 2023, 2:29 PM
bjope added inline comments.
llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h
91

This should perhaps be renamed as RegUnit2SUnitsMap now when when spare set key is a RegUnit and not a Reg.

Caused me some head-ache downstream until I found out that

for (Reg2SUnitsMap::iterator I = DAG->Uses.find(*Subreg);
     I != DAG->Uses.end(); ++I) {

probably isn't working any longer unless I make some changes to use a RegUnit in that find call.

foad marked an inline comment as done.Aug 8 2023, 9:47 AM
foad added inline comments.
llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h
91