intel: Use a better algorithm in brw_nir_analyze_ubo_ranges

Shader-db results with iris on ICL (without Deux Ex: Mankind Divided):

    total instructions in shared programs: 14478207 -> 14445391 (-0.23%)
    instructions in affected programs: 1378208 -> 1345392 (-2.38%)
    helped: 6019
    HURT: 37
    helped stats (abs) min: 3 max: 45 x̄: 5.51 x̃: 3
    helped stats (rel) min: 0.22% max: 13.64% x̄: 3.07% x̃: 2.64%
    HURT stats (abs)   min: 3 max: 28 x̄: 9.65 x̃: 7
    HURT stats (rel)   min: 0.12% max: 1.20% x̄: 0.60% x̃: 0.56%
    95% mean confidence interval for instructions value: -5.52 -5.31
    95% mean confidence interval for instructions %-change: -3.10% -3.01%
    Instructions are helped.

    total cycles in shared programs: 205710790 -> 205130459 (-0.28%)
    cycles in affected programs: 116902116 -> 116321785 (-0.50%)
    helped: 16184
    HURT: 12006
    helped stats (abs) min: 1 max: 8471 x̄: 60.81 x̃: 11
    helped stats (rel) min: <.01% max: 52.21% x̄: 5.26% x̃: 1.25%
    HURT stats (abs)   min: 1 max: 12746 x̄: 33.64 x̃: 6
    HURT stats (rel)   min: <.01% max: 44.95% x̄: 2.26% x̃: 0.81%
    95% mean confidence interval for cycles value: -22.88 -18.29
    95% mean confidence interval for cycles %-change: -2.15% -1.97%
    Cycles are helped.

    total spills in shared programs: 5641 -> 5698 (1.01%)
    spills in affected programs: 1341 -> 1398 (4.25%)
    helped: 0
    HURT: 27

    total fills in shared programs: 5296 -> 5356 (1.13%)
    fills in affected programs: 2262 -> 2322 (2.65%)
    helped: 0
    HURT: 27

    total sends in shared programs: 711474 -> 700416 (-1.55%)
    sends in affected programs: 65458 -> 54400 (-16.89%)
    helped: 6046
    HURT: 10
    helped stats (abs) min: 1 max: 15 x̄: 1.83 x̃: 1
    helped stats (rel) min: 0.70% max: 75.00% x̄: 21.97% x̃: 20.00%
    HURT stats (abs)   min: 1 max: 1 x̄: 1.00 x̃: 1
    HURT stats (rel)   min: 5.88% max: 5.88% x̄: 5.88% x̃: 5.88%
    95% mean confidence interval for sends value: -1.86 -1.79
    95% mean confidence interval for sends %-change: -22.22% -21.62%
    Sends are helped.

    LOST:   19
    GAINED: 3

All of the programs with additional spilling in this group are dolphin
ubershaders.

Shader-db results for Deux Ex: Mankind Divided with iris on ICL:

    total instructions in shared programs: 1567968 -> 1579413 (0.73%)
    instructions in affected programs: 920802 -> 932247 (1.24%)
    helped: 586
    HURT: 307
    helped stats (abs) min: 3 max: 36 x̄: 9.09 x̃: 7
    helped stats (rel) min: 0.15% max: 9.15% x̄: 2.87% x̃: 2.54%
    HURT stats (abs)   min: 2 max: 160 x̄: 54.63 x̃: 34
    HURT stats (rel)   min: 0.07% max: 8.35% x̄: 2.61% x̃: 1.65%
    95% mean confidence interval for instructions value: 10.09 15.54
    95% mean confidence interval for instructions %-change: -1.20% -0.77%
    Inconclusive result (value mean confidence interval and %-change mean confidence interval disagree).

    total cycles in shared programs: 131965209 -> 130752603 (-0.92%)
    cycles in affected programs: 113877187 -> 112664581 (-1.06%)
    helped: 801
    HURT: 256
    helped stats (abs) min: 1 max: 13821 x̄: 2202.44 x̃: 208
    helped stats (rel) min: <.01% max: 35.05% x̄: 6.25% x̃: 3.11%
    HURT stats (abs)   min: 1 max: 107410 x̄: 2154.50 x̃: 35
    HURT stats (rel)   min: <.01% max: 54.38% x̄: 2.61% x̃: 0.96%
    95% mean confidence interval for cycles value: -1460.19 -834.24
    95% mean confidence interval for cycles %-change: -4.57% -3.65%
    Cycles are helped.

    total spills in shared programs: 3783 -> 6507 (72.01%)
    spills in affected programs: 2048 -> 4772 (133.01%)
    helped: 0
    HURT: 307

    total fills in shared programs: 5248 -> 8135 (55.01%)
    fills in affected programs: 2950 -> 5837 (97.86%)
    helped: 0
    HURT: 307

    total sends in shared programs: 102946 -> 100242 (-2.63%)
    sends in affected programs: 67112 -> 64408 (-4.03%)
    helped: 893
    HURT: 0
    helped stats (abs) min: 1 max: 12 x̄: 3.03 x̃: 3
    helped stats (rel) min: 0.62% max: 42.86% x̄: 11.64% x̃: 8.33%
    95% mean confidence interval for sends value: -3.15 -2.90
    95% mean confidence interval for sends %-change: -12.34% -10.95%
    Sends are helped.

    LOST:   4
    GAINED: 0

Vulkan pipeline database results on ICL:

    Instructions in all programs: 263116462 -> 263804361 (+0.3%)
    SENDs in all programs: 15040610 -> 13478032 (-10.4%)
    Loops in all programs: 149659 -> 149659 (+0.0%)
    Cycles in all programs: 84774512196 -> 82686247050 (-2.5%)
    Spills in all programs: 243416 -> 313386 (+28.7%)
    Fills in all programs: 340691 -> 415867 (+22.1%)
23 jobs for !4438 with review/ubo-push-ranges in 7 minutes and 51 seconds (queued for 2 seconds)
latest detached
Status Job ID Name Coverage
  Container
passed #2204667
aarch64
arm_build

00:00:21

passed #2204669
aarch64
arm_test

00:00:22

passed #2204671
windows shell 1809 mesa
windows_build_vs2019

00:00:09

passed #2204661
x86_build

00:00:17

passed #2204665
x86_build_old

00:00:17

passed #2204662
x86_test-gl

00:00:16

passed #2204664
x86_test-vk

00:00:16

 
  Meson X86 64
passed #2204679
meson-clang

00:07:31

passed #2204677
meson-classic

00:01:07

passed #2204680
meson-clover

00:06:04

passed #2204682
meson-clover-old-llvm

00:03:23

passed #2204675
meson-gallium

00:04:50

passed #2204674
meson-testing

00:05:46

passed #2204683
meson-vulkan

00:04:37

 
  Scons
passed #2204685
scons-win64

00:06:24

 
  Meson Misc
passed #2204689
aarch64
meson-arm64

00:00:56

passed #2204691
aarch64
meson-arm64-build-test

00:01:47

passed #2204687
aarch64
meson-armhf

00:01:44

passed #2204696
meson-i386

00:06:15

passed #2204701
meson-mingw32-x86_64

00:05:06

passed #2204699
kvm
meson-ppc64el

00:02:41

passed #2204697
kvm
meson-s390x

00:03:08

passed #2204693
windows docker 1809 mesa
meson-windows-vs2019

00:05:47