ir3/ra: allocate shared collects dst over its srcs when possible

Currently, when allocating the dst of shared collects, the registers of its srcs would only be reused if they are killed. This results in a lot of needless moves due to suboptimal register allocation.

This commit addresses this generically: allow unavailable registers to be used for a new dst iff it shares a merge set with, and has the same offset as, the currently live value.

shaderdb results:

main shader

total instructions in shared programs: 4101717 -> 4102366 (0.02%)
instructions in affected programs: 410258 -> 410907 (0.16%)
helped: 111
HURT: 105
helped stats (abs) min: 1 max: 80 x̄: 15.21 x̃: 5
helped stats (rel) min: 0.06% max: 5.56% x̄: 1.28% x̃: 0.55%
HURT stats (abs)   min: 1 max: 86 x̄: 22.26 x̃: 10
HURT stats (rel)   min: 0.03% max: 6.95% x̄: 1.73% x̃: 1.14%
95% mean confidence interval for instructions value: -0.80 6.81
95% mean confidence interval for instructions %-change: -0.12% 0.48%
Inconclusive result (value mean confidence interval includes 0).
total nops in shared programs: 796043 -> 796543 (0.06%)
nops in affected programs: 138668 -> 139168 (0.36%)
helped: 106
HURT: 104
helped stats (abs) min: 1 max: 80 x̄: 15.50 x̃: 7
helped stats (rel) min: 0.03% max: 33.33% x̄: 4.89% x̃: 2.32%
HURT stats (abs)   min: 1 max: 84 x̄: 20.61 x̃: 9
HURT stats (rel)   min: 0.06% max: 33.33% x̄: 6.54% x̃: 2.65%
95% mean confidence interval for nops value: -1.35 6.11
95% mean confidence interval for nops %-change: -0.49% 2.03%
Inconclusive result (value mean confidence interval includes 0).
total non-nops in shared programs: 3305674 -> 3305823 (<.01%)
non-nops in affected programs: 162537 -> 162686 (0.09%)
helped: 32
HURT: 41
helped stats (abs) min: 1 max: 34 x̄: 9.22 x̃: 6
helped stats (rel) min: 0.04% max: 2.84% x̄: 0.61% x̃: 0.29%
HURT stats (abs)   min: 1 max: 50 x̄: 10.83 x̃: 4
HURT stats (rel)   min: 0.05% max: 2.02% x̄: 0.58% x̃: 0.29%
95% mean confidence interval for non-nops value: -1.79 5.87
95% mean confidence interval for non-nops %-change: -0.15% 0.26%
Inconclusive result (value mean confidence interval includes 0).
total mov in shared programs: 247657 -> 247799 (0.06%)
mov in affected programs: 13634 -> 13776 (1.04%)
helped: 34
HURT: 41
helped stats (abs) min: 1 max: 36 x̄: 8.41 x̃: 5
helped stats (rel) min: 0.52% max: 27.27% x̄: 5.93% x̃: 2.85%
HURT stats (abs)   min: 1 max: 50 x̄: 10.44 x̃: 4
HURT stats (rel)   min: 0.54% max: 41.32% x̄: 8.36% x̃: 2.82%
95% mean confidence interval for mov value: -1.74 5.53
95% mean confidence interval for mov %-change: -0.82% 4.58%
Inconclusive result (value mean confidence interval includes 0).
total cov in shared programs: 89506 -> 89513 (<.01%)
cov in affected programs: 678 -> 685 (1.03%)
helped: 0
HURT: 7
HURT stats (abs)   min: 1 max: 1 x̄: 1.00 x̃: 1
HURT stats (rel)   min: 0.88% max: 1.79% x̄: 1.13% x̃: 0.89%
95% mean confidence interval for cov value: 1.00 1.00
95% mean confidence interval for cov %-change: 0.74% 1.53%
Cov are HURT.
total dwords in shared programs: 8731110 -> 8716084 (-0.17%)
dwords in affected programs: 1111040 -> 1096014 (-1.35%)
helped: 719
HURT: 25
helped stats (abs) min: 2 max: 120 x̄: 22.20 x̃: 26
helped stats (rel) min: <.01% max: 46.88% x̄: 3.89% x̃: 1.85%
HURT stats (abs)   min: 4 max: 96 x̄: 37.36 x̃: 32
HURT stats (rel)   min: 0.04% max: 2.94% x̄: 0.87% x̃: 0.34%
95% mean confidence interval for dwords value: -21.82 -18.57
95% mean confidence interval for dwords %-change: -4.15% -3.30%
Dwords are helped.
total last-baryf in shared programs: 119552 -> 119712 (0.13%)
last-baryf in affected programs: 14 -> 174 (1142.86%)
helped: 0
HURT: 2
total last-helper in shared programs: 1155945 -> 1156252 (0.03%)
last-helper in affected programs: 188866 -> 189173 (0.16%)
helped: 27
HURT: 46
helped stats (abs) min: 1 max: 70 x̄: 19.70 x̃: 18
helped stats (rel) min: 0.07% max: 7.31% x̄: 0.96% x̃: 0.48%
HURT stats (abs)   min: 1 max: 52 x̄: 18.24 x̃: 19
HURT stats (rel)   min: 0.05% max: 13.89% x̄: 1.05% x̃: 0.55%
95% mean confidence interval for last-helper value: -1.41 9.82
95% mean confidence interval for last-helper %-change: -0.17% 0.79%
Inconclusive result (value mean confidence interval includes 0).
total half in shared programs: 0 -> 0
half in affected programs: 0 -> 0
helped: 0
HURT: 0
total full in shared programs: 261436 -> 261364 (-0.03%)
full in affected programs: 144 -> 72 (-50.00%)
helped: 3
HURT: 0
helped stats (abs) min: 24 max: 24 x̄: 24.00 x̃: 24
helped stats (rel) min: 50.00% max: 50.00% x̄: 50.00% x̃: 50.00%
total constlen in shared programs: 573812 -> 573812 (0.00%)
constlen in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat0 in shared programs: 888085 -> 888587 (0.06%)
cat0 in affected programs: 148751 -> 149253 (0.34%)
helped: 104
HURT: 104
helped stats (abs) min: 1 max: 80 x̄: 15.77 x̃: 7
helped stats (rel) min: 0.03% max: 30.77% x̄: 4.70% x̃: 2.39%
HURT stats (abs)   min: 1 max: 84 x̄: 20.60 x̃: 9
HURT stats (rel)   min: 0.05% max: 28.57% x̄: 6.14% x̃: 2.54%
95% mean confidence interval for cat0 value: -1.35 6.18
95% mean confidence interval for cat0 %-change: -0.47% 1.90%
Inconclusive result (value mean confidence interval includes 0).
total cat1 in shared programs: 338439 -> 338586 (0.04%)
cat1 in affected programs: 18973 -> 19120 (0.77%)
helped: 32
HURT: 41
helped stats (abs) min: 1 max: 34 x̄: 9.00 x̃: 6
helped stats (rel) min: 0.37% max: 27.27% x̄: 5.09% x̃: 2.38%
HURT stats (abs)   min: 1 max: 50 x̄: 10.61 x̃: 4
HURT stats (rel)   min: 0.51% max: 20.92% x̄: 5.11% x̃: 2.21%
95% mean confidence interval for cat1 value: -1.75 5.78
95% mean confidence interval for cat1 %-change: -1.23% 2.51%
Inconclusive result (value mean confidence interval includes 0).
total cat2 in shared programs: 1498141 -> 1498141 (0.00%)
cat2 in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat3 in shared programs: 1193698 -> 1193698 (0.00%)
cat3 in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat4 in shared programs: 84032 -> 84032 (0.00%)
cat4 in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat5 in shared programs: 45976 -> 45976 (0.00%)
cat5 in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat6 in shared programs: 49579 -> 49579 (0.00%)
cat6 in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat7 in shared programs: 3767 -> 3767 (0.00%)
cat7 in affected programs: 0 -> 0
helped: 0
HURT: 0
total stp in shared programs: 2478 -> 2478 (0.00%)
stp in affected programs: 0 -> 0
helped: 0
HURT: 0
total ldp in shared programs: 601 -> 601 (0.00%)
ldp in affected programs: 0 -> 0
helped: 0
HURT: 0
total sstall in shared programs: 359543 -> 359334 (-0.06%)
sstall in affected programs: 55650 -> 55441 (-0.38%)
helped: 70
HURT: 54
helped stats (abs) min: 1 max: 30 x̄: 7.23 x̃: 6
helped stats (rel) min: 0.12% max: 60.00% x̄: 5.46% x̃: 1.32%
HURT stats (abs)   min: 1 max: 35 x̄: 5.50 x̃: 2
HURT stats (rel)   min: 0.00% max: 30.00% x̄: 4.78% x̃: 1.33%
95% mean confidence interval for sstall value: -3.37 0.00
95% mean confidence interval for sstall %-change: -3.11% 1.11%
Inconclusive result (value mean confidence interval includes 0).
total (ss) in shared programs: 92190 -> 92214 (0.03%)
(ss) in affected programs: 9773 -> 9797 (0.25%)
helped: 44
HURT: 58
helped stats (abs) min: 1 max: 4 x̄: 1.55 x̃: 1
helped stats (rel) min: 0.53% max: 33.33% x̄: 4.08% x̃: 1.27%
HURT stats (abs)   min: 1 max: 6 x̄: 1.59 x̃: 1
HURT stats (rel)   min: 0.37% max: 50.00% x̄: 5.59% x̃: 1.67%
95% mean confidence interval for (ss) value: -0.13 0.61
95% mean confidence interval for (ss) %-change: -0.67% 3.50%
Inconclusive result (value mean confidence interval includes 0).
total systall in shared programs: 650451 -> 650898 (0.07%)
systall in affected programs: 100757 -> 101204 (0.44%)
helped: 78
HURT: 58
helped stats (abs) min: 1 max: 64 x̄: 11.24 x̃: 3
helped stats (rel) min: 0.04% max: 26.67% x̄: 4.06% x̃: 3.19%
HURT stats (abs)   min: 1 max: 122 x̄: 22.83 x̃: 11
HURT stats (rel)   min: 0.12% max: 600.00% x̄: 25.78% x̃: 5.18%
95% mean confidence interval for systall value: -1.53 8.10
95% mean confidence interval for systall %-change: -0.74% 18.08%
Inconclusive result (value mean confidence interval includes 0).
total (sy) in shared programs: 35875 -> 35908 (0.09%)
(sy) in affected programs: 1458 -> 1491 (2.26%)
helped: 17
HURT: 33
helped stats (abs) min: 1 max: 2 x̄: 1.12 x̃: 1
helped stats (rel) min: 1.82% max: 10.00% x̄: 3.92% x̃: 3.23%
HURT stats (abs)   min: 1 max: 5 x̄: 1.58 x̃: 1
HURT stats (rel)   min: 2.44% max: 100.00% x̄: 14.68% x̃: 4.17%
95% mean confidence interval for (sy) value: 0.23 1.09
95% mean confidence interval for (sy) %-change: 1.48% 15.23%
(sy) are HURT.
total waves in shared programs: 628660 -> 628666 (<.01%)
waves in affected programs: 6 -> 12 (100.00%)
helped: 3
HURT: 0
helped stats (abs) min: 2 max: 2 x̄: 2.00 x̃: 2
helped stats (rel) min: 100.00% max: 100.00% x̄: 100.00% x̃: 100.00%
total loops in shared programs: 1025 -> 1025 (0.00%)
loops in affected programs: 0 -> 0
helped: 0
HURT: 0
LOST:   0
GAINED: 0
Total CPU time (seconds): 1578.68 -> 1587.72 (0.57%)

Preamble stats collected using !32002.

preamble

total instructions in shared programs: 1104431 -> 1095825 (-0.78%)
instructions in affected programs: 285062 -> 276456 (-3.02%)
helped: 1118
HURT: 23
helped stats (abs) min: 1 max: 54 x̄: 7.93 x̃: 5
helped stats (rel) min: 0.24% max: 33.33% x̄: 6.45% x̃: 4.97%
HURT stats (abs)   min: 1 max: 28 x̄: 11.22 x̃: 7
HURT stats (rel)   min: 0.26% max: 2.41% x̄: 1.26% x̃: 1.32%
95% mean confidence interval for instructions value: -8.00 -7.08
95% mean confidence interval for instructions %-change: -6.63% -5.96%
Instructions are helped.
total nops in shared programs: 181872 -> 180193 (-0.92%)
nops in affected programs: 35759 -> 34080 (-4.70%)
helped: 596
HURT: 175
helped stats (abs) min: 1 max: 27 x̄: 3.49 x̃: 3
helped stats (rel) min: 1.41% max: 75.00% x̄: 8.85% x̃: 5.88%
HURT stats (abs)   min: 1 max: 13 x̄: 2.28 x̃: 1
HURT stats (rel)   min: 0.93% max: 100.00% x̄: 17.46% x̃: 8.33%
95% mean confidence interval for nops value: -2.46 -1.90
95% mean confidence interval for nops %-change: -4.03% -1.72%
Nops are helped.
total non-nops in shared programs: 922559 -> 915632 (-0.75%)
non-nops in affected programs: 216108 -> 209181 (-3.21%)
helped: 1069
HURT: 14
helped stats (abs) min: 2 max: 53 x̄: 6.72 x̃: 4
helped stats (rel) min: 0.59% max: 35.00% x̄: 7.41% x̃: 6.19%
HURT stats (abs)   min: 6 max: 35 x̄: 18.57 x̃: 7
HURT stats (rel)   min: 0.65% max: 3.54% x̄: 1.89% x̃: 0.67%
95% mean confidence interval for non-nops value: -6.81 -5.99
95% mean confidence interval for non-nops %-change: -7.68% -6.91%
Non-nops are helped.
total mov in shared programs: 164155 -> 157234 (-4.22%)
mov in affected programs: 41641 -> 34720 (-16.62%)
helped: 1075
HURT: 14
helped stats (abs) min: 1 max: 53 x̄: 6.67 x̃: 4
helped stats (rel) min: 0.31% max: 100.00% x̄: 30.57% x̃: 26.76%
HURT stats (abs)   min: 7 max: 31 x̄: 18.14 x̃: 9
HURT stats (rel)   min: 5.33% max: 13.72% x̄: 9.02% x̃: 6.03%
95% mean confidence interval for mov value: -6.75 -5.96
95% mean confidence interval for mov %-change: -31.36% -28.76%
Mov are helped.
total cov in shared programs: 58945 -> 58979 (0.06%)
cov in affected programs: 4608 -> 4642 (0.74%)
helped: 10
HURT: 30
helped stats (abs) min: 2 max: 2 x̄: 2.00 x̃: 2
helped stats (rel) min: 1.42% max: 4.76% x̄: 2.76% x̃: 1.42%
HURT stats (abs)   min: 1 max: 4 x̄: 1.80 x̃: 1
HURT stats (rel)   min: 0.82% max: 2.76% x̄: 1.42% x̃: 1.11%
95% mean confidence interval for cov value: 0.22 1.48
95% mean confidence interval for cov %-change: -0.29% 1.05%
Inconclusive result (%-change mean confidence interval includes 0).
total dwords in shared programs: 8731110 -> 8716084 (-0.17%)
dwords in affected programs: 1111040 -> 1096014 (-1.35%)
helped: 719
HURT: 25
helped stats (abs) min: 2 max: 120 x̄: 22.20 x̃: 26
helped stats (rel) min: <.01% max: 46.88% x̄: 3.89% x̃: 1.85%
HURT stats (abs)   min: 4 max: 96 x̄: 37.36 x̃: 32
HURT stats (rel)   min: 0.04% max: 2.94% x̄: 0.87% x̃: 0.34%
95% mean confidence interval for dwords value: -21.82 -18.57
95% mean confidence interval for dwords %-change: -4.15% -3.30%
Dwords are helped.
total last-baryf in shared programs: 265474 -> 262272 (-1.21%)
last-baryf in affected programs: 54251 -> 51049 (-5.90%)
helped: 388
HURT: 5
helped stats (abs) min: 1 max: 44 x̄: 8.37 x̃: 5
helped stats (rel) min: 0.24% max: 33.33% x̄: 10.47% x̃: 9.09%
HURT stats (abs)   min: 1 max: 20 x̄: 9.00 x̃: 2
HURT stats (rel)   min: 0.72% max: 1.75% x̄: 1.37% x̃: 1.33%
95% mean confidence interval for last-baryf value: -8.86 -7.44
95% mean confidence interval for last-baryf %-change: -10.93% -9.70%
Last-baryf are helped.
total last-helper in shared programs: 194398 -> 191753 (-1.36%)
last-helper in affected programs: 50176 -> 47531 (-5.27%)
helped: 314
HURT: 5
helped stats (abs) min: 1 max: 44 x̄: 8.57 x̃: 5
helped stats (rel) min: 0.24% max: 21.05% x̄: 9.18% x̃: 8.63%
HURT stats (abs)   min: 1 max: 20 x̄: 9.00 x̃: 2
HURT stats (rel)   min: 0.72% max: 1.75% x̄: 1.37% x̃: 1.33%
95% mean confidence interval for last-helper value: -9.06 -7.52
95% mean confidence interval for last-helper %-change: -9.63% -8.39%
Last-helper are helped.
total half in shared programs: 0 -> 0
half in affected programs: 0 -> 0
helped: 0
HURT: 0
total full in shared programs: 261436 -> 261364 (-0.03%)
full in affected programs: 144 -> 72 (-50.00%)
helped: 3
HURT: 0
helped stats (abs) min: 24 max: 24 x̄: 24.00 x̃: 24
helped stats (rel) min: 50.00% max: 50.00% x̄: 50.00% x̃: 50.00%
total constlen in shared programs: 573812 -> 573812 (0.00%)
constlen in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat0 in shared programs: 292978 -> 291299 (-0.57%)
cat0 in affected programs: 38308 -> 36629 (-4.38%)
helped: 596
HURT: 175
helped stats (abs) min: 1 max: 27 x̄: 3.49 x̃: 3
helped stats (rel) min: 1.35% max: 54.55% x̄: 7.61% x̃: 5.56%
HURT stats (abs)   min: 1 max: 13 x̄: 2.28 x̃: 1
HURT stats (rel)   min: 0.90% max: 57.14% x̄: 10.88% x̃: 6.90%
95% mean confidence interval for cat0 value: -2.46 -1.90
95% mean confidence interval for cat0 %-change: -4.16% -2.66%
Cat0 are helped.
total cat1 in shared programs: 225740 -> 218813 (-3.07%)
cat1 in affected programs: 55731 -> 48804 (-12.43%)
helped: 1069
HURT: 14
helped stats (abs) min: 2 max: 53 x̄: 6.72 x̃: 4
helped stats (rel) min: 1.60% max: 100.00% x̄: 25.54% x̃: 20.00%
HURT stats (abs)   min: 6 max: 35 x̄: 18.57 x̃: 7
HURT stats (rel)   min: 2.03% max: 9.43% x̄: 5.53% x̃: 4.32%
95% mean confidence interval for cat1 value: -6.81 -5.99
95% mean confidence interval for cat1 %-change: -26.40% -23.88%
Cat1 are helped.
total cat2 in shared programs: 341080 -> 341080 (0.00%)
cat2 in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat3 in shared programs: 66292 -> 66292 (0.00%)
cat3 in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat4 in shared programs: 16504 -> 16504 (0.00%)
cat4 in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat5 in shared programs: 655 -> 655 (0.00%)
cat5 in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat6 in shared programs: 161182 -> 161182 (0.00%)
cat6 in affected programs: 0 -> 0
helped: 0
HURT: 0
total cat7 in shared programs: 0 -> 0
cat7 in affected programs: 0 -> 0
helped: 0
HURT: 0
total stp in shared programs: 2478 -> 2478 (0.00%)
stp in affected programs: 0 -> 0
helped: 0
HURT: 0
total ldp in shared programs: 601 -> 601 (0.00%)
ldp in affected programs: 0 -> 0
helped: 0
HURT: 0
total sstall in shared programs: 665041 -> 662439 (-0.39%)
sstall in affected programs: 138178 -> 135576 (-1.88%)
helped: 644
HURT: 392
helped stats (abs) min: 1 max: 63 x̄: 9.27 x̃: 7
helped stats (rel) min: 0.24% max: 60.00% x̄: 10.09% x̃: 7.10%
HURT stats (abs)   min: 1 max: 113 x̄: 8.59 x̃: 6
HURT stats (rel)   min: 0.19% max: 61.11% x̄: 10.65% x̃: 8.22%
95% mean confidence interval for sstall value: -3.30 -1.73
95% mean confidence interval for sstall %-change: -3.09% -1.39%
Sstall are helped.
total (ss) in shared programs: 170121 -> 169549 (-0.34%)
(ss) in affected programs: 23130 -> 22558 (-2.47%)
helped: 553
HURT: 221
helped stats (abs) min: 1 max: 10 x̄: 1.80 x̃: 1
helped stats (rel) min: 1.90% max: 40.00% x̄: 8.81% x̃: 6.20%
HURT stats (abs)   min: 1 max: 19 x̄: 1.90 x̃: 1
HURT stats (rel)   min: 1.59% max: 60.00% x̄: 11.64% x̃: 7.69%
95% mean confidence interval for (ss) value: -0.91 -0.56
95% mean confidence interval for (ss) %-change: -3.83% -2.11%
(ss) are helped.
total systall in shared programs: 633845 -> 635510 (0.26%)
systall in affected programs: 110087 -> 111752 (1.51%)
helped: 396
HURT: 291
helped stats (abs) min: 1 max: 68 x̄: 14.27 x̃: 12
helped stats (rel) min: 0.31% max: 60.00% x̄: 16.61% x̃: 15.38%
HURT stats (abs)   min: 1 max: 104 x̄: 25.14 x̃: 20
HURT stats (rel)   min: 0.65% max: 96.36% x̄: 26.27% x̃: 6.85%
95% mean confidence interval for systall value: 0.47 4.37
95% mean confidence interval for systall %-change: -0.88% 4.00%
Inconclusive result (%-change mean confidence interval includes 0).
total (sy) in shared programs: 61585 -> 61615 (0.05%)
(sy) in affected programs: 2341 -> 2371 (1.28%)
helped: 139
HURT: 134
helped stats (abs) min: 1 max: 3 x̄: 1.22 x̃: 1
helped stats (rel) min: 3.33% max: 33.33% x̄: 17.27% x̃: 20.00%
HURT stats (abs)   min: 1 max: 3 x̄: 1.49 x̃: 1
HURT stats (rel)   min: 6.25% max: 50.00% x̄: 25.60% x̃: 20.00%
95% mean confidence interval for (sy) value: -0.07 0.29
95% mean confidence interval for (sy) %-change: 0.91% 6.63%
Inconclusive result (value mean confidence interval includes 0).
total waves in shared programs: 628660 -> 628666 (<.01%)
waves in affected programs: 6 -> 12 (100.00%)
helped: 3
HURT: 0
helped stats (abs) min: 2 max: 2 x̄: 2.00 x̃: 2
helped stats (rel) min: 100.00% max: 100.00% x̄: 100.00% x̃: 100.00%
total loops in shared programs: 1025 -> 1025 (0.00%)
loops in affected programs: 0 -> 0
helped: 0
HURT: 0
LOST:   0
GAINED: 0
Total CPU time (seconds): 1607.61 -> 1590.46 (-1.07%)