This is an archive of the discontinued LLVM Phabricator instance.

Differential D108578

RegAllocGreedy: Account for reserved registers in num regs heuristic
ClosedPublic

Authored by arsenm on Aug 23 2021, 1:10 PM.

Details

Reviewers
qcolombet
kparzysz
foad
rampitec
Summary

This simple heuristic uses the estimated live range length combined
with the number of registers in the class to switch which heuristic to
use. This was taking the raw number of registers in the class, even
though not all of them may be available. AMDGPU heavily relies on
dynamically reserved numbers of registers based on user attributes to
satisfy occupancy constraints, so the raw number is highly misleading.




There are still a few problems here. In the original testcase that

made me notice this, the live range size is incorrect after the

scheduler rearranges instructions, since the instructions don't have

the original InstrDist offsets. Additionally, I think it would be more

appropriate to use the number of disjointly allocatable registers in

the class. For the AMDGPU register tuples, there are a large number of

registers in each tuple class, but only a small fraction can actually

be allocated at the same time since they all overlap with each

other. It seems we do not have a query that corresponds to the number

of independently allocatable registers. Relatedly, I'm still debugging

some allocation failures where overlapping tuples seem to not be

handled correctly.






The test changes are mostly noise. There are a handful of x86 tests

that look like regressions with an additional spill, and a handful

that now avoid a spill. The worst looking regression is likely

test/Thumb2/mve-vld4.ll which introduces a few additional

spills. test/CodeGen/AMDGPU/soft-clause-exceeds-register-budget.ll

shows a massive improvement by completely eliminating a large number

of spills inside a loop.
Diff Detail
Event Timeline
arsenm created this revision.Aug 23 2021, 1:10 PM
Herald added subscribers: frasercrmck, kerbowa, luismarques and 31 others.  ·  View Herald TranscriptAug 23 2021, 1:10 PM
arsenm requested review of this revision.Aug 23 2021, 1:10 PM
Herald added a project: Restricted Project.  ·  View Herald TranscriptAug 23 2021, 1:10 PM
Herald added subscribers: MaskRay, wdng.  ·  View Herald Transcript
Harbormaster completed remote builds in B120855: Diff 368192.Aug 23 2021, 1:11 PM
rampitec added a comment.Aug 23 2021, 1:15 PM
The change itself looks reasonable to me.
dmgreen added a comment.Aug 24 2021, 12:10 AM
The worst looking regression is likely test/Thumb2/mve-vld4.ll



We likely get the register pressure very wrong, and it looks like less code in total. I have no objections to this patch from an Arm point of view.



Arm MVE has 32 scalar FP S regs, 4 (aligned) of which make up the 8 vector Q regs (so q0=s0-s1-s2-s3, q1=s4-s5-s6-s7 etc).

4 potentially unaligned Q registers make up a QQQQPR reg (q0-q1-q2-q3, q1-q2-q3-q4, q2-q3-q4-q5, q3-q4-q5-q6 and q4-q5-q6-q7)

So we have "5" QQQQPR registers, only 2 of which are actually allocatable at once.



Additionally, I think it would be more appropriate to use the number of disjointly allocatable registers in the class. For the AMDGPU register tuples, there are a large number of registers in each tuple class, but only a small fraction can actually be allocated at the same time since they all overlap with each other. It seems we do not have a query that corresponds to the number of independently allocatable registers.



That sounds very useful.
arsenm added a comment.Sep 13 2021, 6:14 AM
ping
lkail added a subscriber: lkail.Sep 13 2021, 7:08 AM
qcolombet accepted this revision.Sep 14 2021, 1:28 PM
This revision is now accepted and ready to land.Sep 14 2021, 1:28 PM
arsenm closed this revision.Sep 14 2021, 6:01 PM
4a36e96c3fc2a9128097bfc4f907ccebc5dc66af
paklui added a subscriber: paklui.Sep 15 2021, 11:56 AM
Large Diff
This large diff affects 152 files. Files without inline comments have been collapsed. Expand All Files
Revision Contents
PathSize
llvm/
lib/
CodeGen/
2 lines
test/
CodeGen/
AMDGPU/
GlobalISel/
201 lines
160 lines
1278 lines
124 lines
2146 lines
422 lines
452 lines
1470 lines
28 lines
34 lines
56 lines
250 lines
244 lines
262 lines
2255 lines
1469 lines
46 lines
32 lines
72 lines
353 lines
32 lines
ARM/
60 lines
80 lines
82 lines
Hexagon/
2 lines
Mips/
cconv/
106 lines
PowerPC/
60 lines
50 lines
48 lines
RISCV/
rvv/
32 lines
16 lines
694 lines
114 lines
Thumb2/
36 lines
156 lines
20 lines
X86/
40 lines
14 lines
22 lines
88 lines
72 lines
32 lines
28 lines
136 lines
16 lines
42 lines
14 lines
16 lines
22 lines
30 lines
192 lines
192 lines
10 lines
80 lines
22 lines
47 lines
14 lines
201 lines
12 lines
228 lines
174 lines
208 lines
254 lines
163 lines
58 lines
52 lines
28 lines
46 lines
10 lines
90 lines
18 lines
10 lines
200 lines
52 lines
12 lines
72 lines
164 lines
234 lines
172 lines
523 lines
69 lines
24 lines
38 lines
24 lines
18 lines
6 lines
536 lines
8 lines
61 lines
28 lines
22 lines
28 lines
10 lines
16 lines
16 lines
44 lines
54 lines
147 lines
72 lines
396 lines
256 lines
76 lines
51 lines
105 lines
262 lines
90 lines
42 lines
156 lines
102 lines
26 lines
16 lines
16 lines
16 lines
52 lines
10 lines
26 lines
38 lines
76 lines
51 lines
249 lines
113 lines
139 lines
16 lines
284 lines
20 lines
65 lines
26 lines
352 lines
36 lines
144 lines
18 lines
27 lines
44 lines
96 lines
32 lines
26 lines
32 lines
26 lines
40 lines
72 lines
132 lines
26 lines
60 lines
42 lines
36 lines
28 lines
60 lines
22 lines
12 lines
148 lines
43 lines
Diff 368192
llvm/lib/CodeGen/RegAllocGreedy.cpp
llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement-stack-lower.ll
llvm/test/CodeGen/AMDGPU/GlobalISel/mul.ll
llvm/test/CodeGen/AMDGPU/GlobalISel/sdiv.i64.ll
llvm/test/CodeGen/AMDGPU/GlobalISel/sdivrem.ll
llvm/test/CodeGen/AMDGPU/GlobalISel/srem.i64.ll
llvm/test/CodeGen/AMDGPU/GlobalISel/udiv.i64.ll
llvm/test/CodeGen/AMDGPU/GlobalISel/urem.i64.ll
llvm/test/CodeGen/AMDGPU/amdgpu-codegenprepare-idiv.ll
llvm/test/CodeGen/AMDGPU/copy-illegal-type.ll
llvm/test/CodeGen/AMDGPU/cvt_f32_ubyte.ll
llvm/test/CodeGen/AMDGPU/frem.ll
llvm/test/CodeGen/AMDGPU/greedy-global-heuristic.mir
llvm/test/CodeGen/AMDGPU/half.ll
llvm/test/CodeGen/AMDGPU/llvm.round.f64.ll
llvm/test/CodeGen/AMDGPU/load-constant-i16.ll
llvm/test/CodeGen/AMDGPU/load-global-i16.ll
llvm/test/CodeGen/AMDGPU/sdiv64.ll
llvm/test/CodeGen/AMDGPU/shl.ll
llvm/test/CodeGen/AMDGPU/soft-clause-exceeds-register-budget.ll
llvm/test/CodeGen/AMDGPU/splitkit-copy-live-lanes.mir
llvm/test/CodeGen/AMDGPU/srl.ll
llvm/test/CodeGen/ARM/fptosi-sat-scalar.ll
llvm/test/CodeGen/ARM/srem-seteq-illegal-types.ll
llvm/test/CodeGen/ARM/umulo-128-legalisation-lowering.ll
llvm/test/CodeGen/Hexagon/reg-scavengebug-2.ll
llvm/test/CodeGen/Mips/cconv/vector.ll
llvm/test/CodeGen/PowerPC/ppc-fpclass.ll
llvm/test/CodeGen/PowerPC/srem-vector-lkk.ll
llvm/test/CodeGen/PowerPC/urem-vector-lkk.ll
llvm/test/CodeGen/RISCV/rvv/fixed-vectors-bitreverse.ll
llvm/test/CodeGen/RISCV/rvv/fixed-vectors-bswap.ll
llvm/test/CodeGen/RISCV/rvv/fixed-vectors-cttz.ll
llvm/test/CodeGen/RISCV/stack-store-check.ll
llvm/test/CodeGen/Thumb2/mve-simple-arith.ll
llvm/test/CodeGen/Thumb2/mve-vld4.ll
llvm/test/CodeGen/Thumb2/srem-seteq-illegal-types.ll
llvm/test/CodeGen/X86/2007-10-12-SpillerUnfold1.ll
llvm/test/CodeGen/X86/2008-04-16-ReMatBug.ll
llvm/test/CodeGen/X86/64-bit-shift-by-32-minus-y.ll
llvm/test/CodeGen/X86/abs.ll
llvm/test/CodeGen/X86/avx512-calling-conv.ll
llvm/test/CodeGen/X86/avx512-regcall-NoMask.ll
llvm/test/CodeGen/X86/avx512-select.ll
llvm/test/CodeGen/X86/avx512bw-intrinsics-upgrade.ll
llvm/test/CodeGen/X86/avx512bwvl-intrinsics-upgrade.ll
llvm/test/CodeGen/X86/bitreverse.ll
llvm/test/CodeGen/X86/bool-vector.ll
llvm/test/CodeGen/X86/bswap.ll
llvm/test/CodeGen/X86/build-vector-128.ll
llvm/test/CodeGen/X86/combine-sbb.ll
llvm/test/CodeGen/X86/div-rem-pair-recomposition-signed.ll
llvm/test/CodeGen/X86/div-rem-pair-recomposition-unsigned.ll
llvm/test/CodeGen/X86/fp128-cast.ll
llvm/test/CodeGen/X86/fptosi-sat-scalar.ll
llvm/test/CodeGen/X86/funnel-shift-rot.ll
llvm/test/CodeGen/X86/funnel-shift.ll
llvm/test/CodeGen/X86/gather-addresses.ll
llvm/test/CodeGen/X86/hoist-and-by-const-from-lshr-in-eqcmp-zero.ll
llvm/test/CodeGen/X86/hoist-and-by-const-from-shl-in-eqcmp-zero.ll
llvm/test/CodeGen/X86/horizontal-reduce-smax.ll
llvm/test/CodeGen/X86/horizontal-reduce-smin.ll
llvm/test/CodeGen/X86/horizontal-reduce-umax.ll
llvm/test/CodeGen/X86/horizontal-reduce-umin.ll
llvm/test/CodeGen/X86/i128-mul.ll
llvm/test/CodeGen/X86/i128-sdiv.ll
llvm/test/CodeGen/X86/i256-add.ll
llvm/test/CodeGen/X86/i64-to-float.ll
llvm/test/CodeGen/X86/illegal-bitfield-loadstore.ll
llvm/test/CodeGen/X86/known-signbits-vector.ll
llvm/test/CodeGen/X86/legalize-shl-vec.ll
llvm/test/CodeGen/X86/load-combine.ll
llvm/test/CodeGen/X86/masked_gather_scatter.ll
llvm/test/CodeGen/X86/memcmp-more-load-pairs.ll
llvm/test/CodeGen/X86/merge-consecutive-stores-nt.ll
llvm/test/CodeGen/X86/mmx-arith.ll
llvm/test/CodeGen/X86/mul-constant-i64.ll
llvm/test/CodeGen/X86/mul-constant-result.ll
llvm/test/CodeGen/X86/mul-i1024.ll
llvm/test/CodeGen/X86/mul-i256.ll
llvm/test/CodeGen/X86/mul-i512.ll
llvm/test/CodeGen/X86/mul128.ll
llvm/test/CodeGen/X86/neg-abs.ll
llvm/test/CodeGen/X86/nontemporal.ll
llvm/test/CodeGen/X86/nosse-vector.ll
llvm/test/CodeGen/X86/overflow.ll
llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll
llvm/test/CodeGen/X86/popcnt.ll
llvm/test/CodeGen/X86/pr31088.ll
llvm/test/CodeGen/X86/pr32284.ll
llvm/test/CodeGen/X86/pr32329.ll
llvm/test/CodeGen/X86/pr32610.ll
llvm/test/CodeGen/X86/pr34080-2.ll
llvm/test/CodeGen/X86/pr46527.ll
llvm/test/CodeGen/X86/sadd_sat.ll
llvm/test/CodeGen/X86/sadd_sat_plus.ll
llvm/test/CodeGen/X86/scheduler-backtracking.ll
llvm/test/CodeGen/X86/sdiv_fix.ll
llvm/test/CodeGen/X86/sdiv_fix_sat.ll
llvm/test/CodeGen/X86/select.ll
llvm/test/CodeGen/X86/setcc-wide-types.ll
llvm/test/CodeGen/X86/shrink_vmul.ll
llvm/test/CodeGen/X86/smax.ll
llvm/test/CodeGen/X86/smin.ll
llvm/test/CodeGen/X86/smul_fix.ll
llvm/test/CodeGen/X86/smul_fix_sat.ll
llvm/test/CodeGen/X86/smulo-128-legalisation-lowering.ll
llvm/test/CodeGen/X86/sse-intrinsics-fast-isel.ll
llvm/test/CodeGen/X86/sse2-intrinsics-fast-isel.ll
llvm/test/CodeGen/X86/sshl_sat.ll
llvm/test/CodeGen/X86/sshl_sat_vec.ll
llvm/test/CodeGen/X86/ssub_sat.ll
llvm/test/CodeGen/X86/ssub_sat_plus.ll
llvm/test/CodeGen/X86/stack-align-memcpy.ll
llvm/test/CodeGen/X86/statepoint-vreg-unlimited-tied-opnds.ll
llvm/test/CodeGen/X86/subvector-broadcast.ll
llvm/test/CodeGen/X86/uadd_sat.ll
llvm/test/CodeGen/X86/udiv_fix_sat.ll
llvm/test/CodeGen/X86/umax.ll
llvm/test/CodeGen/X86/umin.ll
llvm/test/CodeGen/X86/umul-with-overflow.ll
llvm/test/CodeGen/X86/umul_fix.ll
llvm/test/CodeGen/X86/umul_fix_sat.ll
llvm/test/CodeGen/X86/umulo-64-legalisation-lowering.ll
llvm/test/CodeGen/X86/unfold-masked-merge-vector-variablemask.ll
llvm/test/CodeGen/X86/ushl_sat.ll
llvm/test/CodeGen/X86/ushl_sat_vec.ll
llvm/test/CodeGen/X86/usub_sat.ll
llvm/test/CodeGen/X86/vec-strict-cmp-128.ll
llvm/test/CodeGen/X86/vec-strict-cmp-sub128.ll
llvm/test/CodeGen/X86/vec-strict-fptoint-256.ll
llvm/test/CodeGen/X86/vec-strict-inttofp-512.ll
llvm/test/CodeGen/X86/vec_shift4.ll
llvm/test/CodeGen/X86/vec_smulo.ll
llvm/test/CodeGen/X86/vec_umulo.ll
llvm/test/CodeGen/X86/vector-fshl-128.ll
llvm/test/CodeGen/X86/vector-fshl-rot-128.ll
llvm/test/CodeGen/X86/vector-fshr-128.ll
llvm/test/CodeGen/X86/vector-fshr-rot-128.ll
llvm/test/CodeGen/X86/vector-gep.ll
llvm/test/CodeGen/X86/vector-idiv-v2i32.ll
llvm/test/CodeGen/X86/vector-lzcnt-128.ll
llvm/test/CodeGen/X86/vector-rotate-128.ll
llvm/test/CodeGen/X86/vector-sext.ll
llvm/test/CodeGen/X86/vector-shift-lshr-256.ll
llvm/test/CodeGen/X86/vector-shift-shl-256.ll
llvm/test/CodeGen/X86/vector-trunc-ssat.ll
llvm/test/CodeGen/X86/vector-tzcnt-128.ll
llvm/test/CodeGen/X86/vshift-6.ll
llvm/test/CodeGen/X86/widen_cast-4.ll
llvm/test/CodeGen/X86/x86-fpclass.ll
llvm/test/CodeGen/X86/xmulo.ll