nir/algebraic: add patterns for a >> #b << #b and a << #b >> #b

nir/algebraic: add patterns for a >> #b << #b and a << #b >> #b

Commit 5476d181830 ("nir/algebraic: add patterns for a >> #b << #b")
added the ushr version, but it missed the ishr.  A bunch of compute
shaders with stores to shared storage generate the ishr pattern.

Enabling this optimization also enables the iadd/iand reassociation
(right after this hunk), and that enables merging of stores to shared
storage.  A couple shaders have spills and fills hurt on some
platforms.  These all occur in shaders that also have SENDs helped.
On Gen9 and Gen11, the helped SENDs more than makes up for the extra
spills and fills.

On Gen7 and Gen8, it's not as clear.  All of the shaders affected are
compute shaders in DiRT Rally 2 or Bioshock Inifinite.  The most
affected Bioshock shader on Broadwell looks like:

Before: CS SIMD8 shader: 1335 inst, 0 loops, 22411 cycles, 42:36 spills:fills, 159 sends, scheduled with mode lifo, Promoted 2 constants, compacted 21360 to 16528 bytes.

After:  CS SIMD8 shader: 1175 inst, 0 loops, 25916 cycles, 96:135 spills:fills, 72 sends, scheduled with mode lifo, Promoted 2 constants, compacted 18800 to 13648 bytes.

The results on Haswell and Ivy Bridge are similar.  Given that there
are only 2 promoted constants, MR !7698 won't have any effect.

There were no statistically significant changes on Gen9+ in Bioshock in
our performance CI.  Gen8 isn't in that CI, and DiRT Showdown 2 is also
not included in that CI.  It is possible that these shaders aren't used
in the settings or demos used in the CI.

The other pattern, which switches the order of the shifts, only helps a
couple shaders.  If I wasn't already adding another pattern, I
definitely wouldn't bother with that one.

v2: s/ishr/ushr/ in the replacement for the ushr pattern.  Noticed by
Rhys.

Reviewed-by: Rhys Perry <pendingchaos02@gmail.com>
Tiger Lake
total instructions in shared programs: 21052760 -> 21049269 (-0.02%)
instructions in affected programs: 59497 -> 56006 (-5.87%)
helped: 46
HURT: 0
helped stats (abs) min: 2 max: 552 x̄: 75.89 x̃: 53
helped stats (rel) min: 0.28% max: 43.43% x̄: 5.87% x̃: 4.10%
95% mean confidence interval for instructions value: -108.96 -42.82
95% mean confidence interval for instructions %-change: -8.38% -3.35%
Instructions are helped.

total cycles in shared programs: 855229761 -> 855148518 (<.01%)
cycles in affected programs: 8491373 -> 8410130 (-0.96%)
helped: 33
HURT: 15
helped stats (abs) min: 42 max: 26940 x̄: 6200.70 x̃: 4329
helped stats (rel) min: 0.09% max: 38.78% x̄: 7.97% x̃: 4.29%
HURT stats (abs)   min: 2 max: 18132 x̄: 8225.33 x̃: 7288
HURT stats (rel)   min: <.01% max: 13.37% x̄: 5.72% x̃: 4.53%
95% mean confidence interval for cycles value: -4331.52 946.40
95% mean confidence interval for cycles %-change: -6.78% -0.61%
Inconclusive result (value mean confidence interval includes 0).

total sends in shared programs: 989947 -> 989694 (-0.03%)
sends in affected programs: 523 -> 270 (-48.37%)
helped: 5
HURT: 0
helped stats (abs) min: 9 max: 87 x̄: 50.60 x̃: 37
helped stats (rel) min: 25.71% max: 54.72% x̄: 43.49% x̃: 42.53%
95% mean confidence interval for sends value: -93.95 -7.25
95% mean confidence interval for sends %-change: -58.48% -28.50%
Sends are helped.

Ice Lake and Skylake had similar results. (Ice Lake shown)
total instructions in shared programs: 20033498 -> 20030552 (-0.01%)
instructions in affected programs: 59220 -> 56274 (-4.97%)
helped: 48
HURT: 0
helped stats (abs) min: 1 max: 465 x̄: 61.38 x̃: 39
helped stats (rel) min: 0.03% max: 42.27% x̄: 5.19% x̃: 3.90%
95% mean confidence interval for instructions value: -89.57 -33.18
95% mean confidence interval for instructions %-change: -7.49% -2.89%
Instructions are helped.

total cycles in shared programs: 979993675 -> 979840773 (-0.02%)
cycles in affected programs: 6738454 -> 6585552 (-2.27%)
helped: 46
HURT: 0
helped stats (abs) min: 42 max: 6265 x̄: 3323.96 x̃: 3579
helped stats (rel) min: 0.09% max: 37.38% x̄: 4.34% x̃: 2.39%
95% mean confidence interval for cycles value: -3664.70 -2983.21
95% mean confidence interval for cycles %-change: -6.63% -2.06%
Cycles are helped.

total spills in shared programs: 10659 -> 10661 (0.02%)
spills in affected programs: 36 -> 38 (5.56%)
helped: 1
HURT: 1

total fills in shared programs: 11551 -> 11551 (0.00%)
fills in affected programs: 70 -> 70 (0.00%)
helped: 1
HURT: 1

total sends in shared programs: 1032117 -> 1031785 (-0.03%)
sends in affected programs: 711 -> 379 (-46.69%)
helped: 5
HURT: 0
helped stats (abs) min: 18 max: 87 x̄: 66.40 x̃: 74
helped stats (rel) min: 27.69% max: 54.72% x̄: 44.49% x̃: 44.31%
95% mean confidence interval for sends value: -101.79 -31.01
95% mean confidence interval for sends %-change: -58.42% -30.55%
Sends are helped.

Broadwell
total instructions in shared programs: 17865005 -> 17862757 (-0.01%)
instructions in affected programs: 66438 -> 64190 (-3.38%)
helped: 49
HURT: 0
helped stats (abs) min: 1 max: 266 x̄: 45.88 x̃: 39
helped stats (rel) min: 0.03% max: 11.99% x̄: 3.73% x̃: 3.92%
95% mean confidence interval for instructions value: -59.15 -32.61
95% mean confidence interval for instructions %-change: -4.35% -3.12%
Instructions are helped.

total cycles in shared programs: 1031298803 -> 1031219023 (<.01%)
cycles in affected programs: 7253602 -> 7173822 (-1.10%)
helped: 45
HURT: 2
helped stats (abs) min: 18 max: 7828 x̄: 1928.33 x̃: 1918
helped stats (rel) min: <.01% max: 10.51% x̄: 1.58% x̃: 1.31%
HURT stats (abs)   min: 3490 max: 3505 x̄: 3497.50 x̃: 3497
HURT stats (rel)   min: 15.56% max: 15.64% x̄: 15.60% x̃: 15.60%
95% mean confidence interval for cycles value: -2174.88 -1220.01
95% mean confidence interval for cycles %-change: -2.00% 0.30%
Inconclusive result (%-change mean confidence interval includes 0).

total spills in shared programs: 20799 -> 20924 (0.60%)
spills in affected programs: 843 -> 968 (14.83%)
helped: 0
HURT: 4

total fills in shared programs: 27110 -> 27334 (0.83%)
fills in affected programs: 1824 -> 2048 (12.28%)
helped: 1
HURT: 4

total sends in shared programs: 1017935 -> 1017603 (-0.03%)
sends in affected programs: 711 -> 379 (-46.69%)
helped: 5
HURT: 0
helped stats (abs) min: 18 max: 87 x̄: 66.40 x̃: 74
helped stats (rel) min: 27.69% max: 54.72% x̄: 44.49% x̃: 44.31%
95% mean confidence interval for sends value: -101.79 -31.01
95% mean confidence interval for sends %-change: -58.42% -30.55%
Sends are helped.

Haswell and Ivy Bridge had similar results. (Haswell shown)
total instructions in shared programs: 16397496 -> 16395411 (-0.01%)
instructions in affected programs: 59384 -> 57299 (-3.51%)
helped: 49
HURT: 0
helped stats (abs) min: 1 max: 208 x̄: 42.55 x̃: 39
helped stats (rel) min: 0.03% max: 8.18% x̄: 3.74% x̃: 3.91%
95% mean confidence interval for instructions value: -53.59 -31.51
95% mean confidence interval for instructions %-change: -4.24% -3.23%
Instructions are helped.

total cycles in shared programs: 1035483504 -> 1035397592 (<.01%)
cycles in affected programs: 9379739 -> 9293827 (-0.92%)
helped: 45
HURT: 4
helped stats (abs) min: 10 max: 5600 x̄: 2164.51 x̃: 2350
helped stats (rel) min: <.01% max: 11.61% x̄: 1.93% x̃: 1.56%
HURT stats (abs)   min: 2 max: 5756 x̄: 2872.75 x̃: 2866
HURT stats (rel)   min: <.01% max: 24.65% x̄: 12.29% x̃: 12.26%
95% mean confidence interval for cycles value: -2293.06 -1213.56
95% mean confidence interval for cycles %-change: -2.42% 0.88%
Inconclusive result (%-change mean confidence interval includes 0).

total spills in shared programs: 17672 -> 17803 (0.74%)
spills in affected programs: 364 -> 495 (35.99%)
helped: 2
HURT: 2

total fills in shared programs: 20752 -> 20937 (0.89%)
fills in affected programs: 656 -> 841 (28.20%)
helped: 2
HURT: 2

total sends in shared programs: 1044703 -> 1044450 (-0.02%)
sends in affected programs: 523 -> 270 (-48.37%)
helped: 5
HURT: 0
helped stats (abs) min: 9 max: 87 x̄: 50.60 x̃: 37
helped stats (rel) min: 25.71% max: 54.72% x̄: 43.49% x̃: 42.53%
95% mean confidence interval for sends value: -93.95 -7.25
95% mean confidence interval for sends %-change: -58.48% -28.50%
Sends are helped.

No changes on Gen6 or earlier GPUs.

Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/8852>