spirv: Rewrite CFG construction

This commit completely rewrites the way we extract a structured CFG from
SPIR-V.  The new approach is different in a few ways:

 1. It does a breadth-first search instead of depth-first.  This means
    that we've visited the merge node for a construct before we visit
    any of the nodes inside the construct.  This makes it easier to
    validate things like loop and switch nesting.

 2. We record more information in the CFG.  Earlier commits added a
    parent pointer to vtn_cf_node but we now record all of the merge and
    other special blocks for each CFG node.  This lets us validate
    things more precisely.

 3. It makes heavy use of merge blocks for walking the CFG.  Previously,
    we sort of used them as hints for trying to guess the CFG structure
    but things got dicey whenever a merge was missing.  We had some
    heuristics for how to handle short-circuiting if statements but it
    was a bunch of special cases.

    Now, we make them a fundamental part of walking the CFG.  When we
    encounter a control-flow construct, we add the body components of
    the construct to the BFS work list and then jump to the merge block
    if one exists to continue scanning the current CFG nesting level.
    If no merge block exists, we assume that means that control-flow
    never re-converges in a normal way and that the only way to get back
    to normality is with a direct jump such as a loop break or continue.
    This should make things far more robust when trying to deal with the
    more creative placement (or lack thereof) of merge instructions.

Reviewed-by: Alan Baker <alanbaker@google.com>
Reviewed-by: Caio Marcelo de Oliveira Filho <caio.oliveira@intel.com>
Tested-by: Marge Bot <mesa/mesa!3820>
Closes: #2760
Acked-by: Samuel Pitoiset <samuel.pitoiset@gmail.com>
Part-of: <mesa/mesa!4446>
49 jobs for !4446 with review/spirv-cfg-merge in 12 minutes and 44 seconds (queued for 6 seconds)
detached
Status Job ID Name Coverage
  Container
passed #2432541
aarch64
arm_build

00:00:20

passed #2432543
aarch64
arm_test

00:00:20

passed #2432545
windows shell 1809 mesa
windows_build_vs2019

00:00:14

passed #2432535
x86_build

00:00:23

passed #2432540
x86_build_old

00:00:23

passed #2432537
x86_test-gl

00:00:18

passed #2432538
x86_test-vk

00:00:21

 
  Meson X86 64
passed #2432550
meson-clang

00:05:56

passed #2432549
meson-classic

00:02:48

passed #2432551
meson-clover

00:04:49

passed #2432552
meson-clover-old-llvm

00:03:40

passed #2432548
meson-gallium

00:05:20

passed #2432547
meson-testing

00:04:38

passed #2432553
meson-vulkan

00:05:02

 
  Scons
passed #2432554
scons-win64

00:09:35

 
  Meson Misc
passed #2432556
aarch64
meson-arm64

00:01:51

passed #2432557
aarch64
meson-arm64-build-test

00:01:51

passed #2432555
aarch64
meson-armhf

00:01:54

passed #2432559
meson-i386

00:04:53

passed #2432562
meson-mingw32-x86_64

00:04:45

passed #2432561
kvm
meson-ppc64el

00:03:18

passed #2432560
kvm
meson-s390x

00:04:27

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

00:08:22

 
  Llvmpipe
passed #2432566
llvmpipe-gles2

00:03:14

passed #2432567
llvmpipe-traces

00:00:27

passed #2432564
piglit-glslparser

00:03:26

passed #2432563
piglit-quick_gl

00:07:40

passed #2432565
piglit-quick_shader

00:05:23

 
  Softpipe
passed #2432568
softpipe-gles2

00:01:17

passed #2432571
softpipe-gles31 1/4

00:03:19

passed #2432569
softpipe-gles3 1/2

00:05:04

passed #2432572
softpipe-gles31 2/4

00:04:26

passed #2432573
softpipe-gles31 3/4

00:05:15

passed #2432574
softpipe-gles31 4/4

00:02:38

passed #2432570
softpipe-gles3 2/2

00:05:12

 
  Freedreno
passed #2432578
google-freedreno-db410c
arm64_a306_gles2

00:08:04

passed #2432579
google-freedreno-db820c
arm64_a530_gles2

00:08:53

passed #2432575
mesa-cheza
arm64_a630_gles2

00:01:32

passed #2432577
mesa-cheza
arm64_a630_gles3

00:06:18

passed #2432576
mesa-cheza
arm64_a630_gles31

00:04:10

 
  Panfrost
passed #2432580
mesa-ci-aarch64-lava-collabora
panfrost-t720-gles2:arm64

00:08:50

passed #2432581
mesa-ci-aarch64-lava-collabora
panfrost-t760-gles2:armhf

00:05:23

passed #2432582
mesa-ci-aarch64-lava-collabora
panfrost-t860-gles2:arm64

00:05:17

passed #2432583
mesa-ci-aarch64-lava-collabora
panfrost-t860-gles3:arm64

00:05:12

 
  Radv
passed #2432584
radv-fossils

00:06:36

 
  Virgl
passed #2432585
virgl-gles2

00:03:27

passed #2432586
virgl-gles3

00:04:00

passed #2432587
virgl-gles31

00:02:28

passed #2432588
virgl-traces

00:00:28