[Mesa-dev] [PATCH 00/30] pan/midgard: Implement out-of-order scheduler

[Alyssa Rosenzweig]

For each block, we compute an instruction dependency graph, which allows
us to maintain a worklist of instructions able to be scheduled (no
dependencies). We traverse this graph backwards, emitting instructions
backwards and reversing the block at the end, to allow conditionals and
writeout to be expressed naturally and to enable liveness tracking in
the future.

At the moment, we do not schedule for register pressure; we just aim to
minimize bundles (register pressure is capped here by a distance
metric). Scheduling for register pressure will be the next step as soon
as this series is finalized; at that point, we'll augment
mir_choose_instruction and mir_choose_bundle with pressure-aware
heuristics.

Overall, I'm quite happy with how this came out. Full stats below.
Highlight is a 10% reduction of cycle count for glmark shaders.

total instructions in shared programs: 3500 -> 3472 (-0.80%)
instructions in affected programs: 685 -> 657 (-4.09%)
helped: 15
HURT: 1
helped stats (abs) min: 1 max: 5 x̄: 1.93 x̃: 1
helped stats (rel) min: 1.49% max: 12.20% x̄: 4.65% x̃: 3.45%
HURT stats (abs)   min: 1 max: 1 x̄: 1.00 x̃: 1
HURT stats (rel)   min: 4.00% max: 4.00% x̄: 4.00% x̃: 4.00%
95% mean confidence interval for instructions value: -2.61 -0.89
95% mean confidence interval for instructions %-change: -6.03% -2.18%
Instructions are helped.

total bundles in shared programs: 2020 -> 1804 (-10.69%)
bundles in affected programs: 1343 -> 1127 (-16.08%)
helped: 45
HURT: 0
helped stats (abs) min: 1 max: 48 x̄: 4.80 x̃: 2
helped stats (rel) min: 5.56% max: 34.78% x̄: 13.50% x̃: 12.50%
95% mean confidence interval for bundles value: -7.15 -2.45
95% mean confidence interval for bundles %-change: -15.98% -11.03%
Bundles are helped.

total quadwords in shared programs: 3336 -> 3130 (-6.18%)
quadwords in affected programs: 2162 -> 1956 (-9.53%)
helped: 51
HURT: 0
helped stats (abs) min: 1 max: 17 x̄: 4.04 x̃: 2
helped stats (rel) min: 1.72% max: 22.92% x̄: 10.94% x̃: 11.11%
95% mean confidence interval for quadwords value: -5.32 -2.76
95% mean confidence interval for quadwords %-change: -12.47% -9.42%
Quadwords are helped.

total registers in shared programs: 343 -> 327 (-4.66%)
registers in affected programs: 123 -> 107 (-13.01%)
helped: 22
HURT: 5
helped stats (abs) min: 1 max: 1 x̄: 1.00 x̃: 1
helped stats (rel) min: 12.50% max: 33.33% x̄: 25.61% x̃: 25.00%
HURT stats (abs)   min: 1 max: 2 x̄: 1.20 x̃: 1
HURT stats (rel)   min: 8.33% max: 100.00% x̄: 37.00% x̃: 20.00%
95% mean confidence interval for registers value: -0.94 -0.24
95% mean confidence interval for registers %-change: -25.65% -2.38%
Registers are helped.

total threads in shared programs: 451 -> 459 (1.77%)
threads in affected programs: 8 -> 16 (100.00%)
helped: 4
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%
95% mean confidence interval for threads value: 2.00 2.00
95% mean confidence interval for threads %-change: 100.00% 100.00%

total spills in shared programs: 3 -> 3 (0.00%)
spills in affected programs: 0 -> 0
helped: 0
HURT: 0

total fills in shared programs: 5 -> 6 (20.00%)
fills in affected programs: 5 -> 6 (20.00%)
helped: 0
HURT: 1

Alyssa Rosenzweig (30):
  pan/midgard: Add missing parans in SWIZZLE definition
  pan/midgard: Fix component count handling for ldst
  pan/midgard: Squeeze indices before scheduling
  pan/midgard: Add flatten_mir helper
  pan/midgard: Calculate dependency graph
  pan/midgard: Initialize worklist
  pan/midgard: Add mir_choose_instruction stub
  pan/midgard: Add mir_update_worklist helper
  pan/midgard: Add mir_choose_bundle helper
  pan/midgard: Add mir_schedule_texture/ldst/alu helpers
  pan/midgard: Remove csel constant unit force
  pan/midgard: Add constant intersection filters
  pan/midgard: Add predicate->exclude
  pan/midgard: Implement predicate->unit
  pan/midgard: Add helpers for scheduling conditionals
  pan/midgard: Extend csel_swizzle to branches
  pan/midgard: Implement load/store pairing
  pan/midgard: Add mir_choose_alu helper
  pan/midgard: Add distance metric to choose_instruction
  pan/midgard: Use new scheduler
  pan/midgard: Don't double check SCALAR units
  pan/midgard: Extend choose_instruction for scalar units
  pan/midgard: Schedule to smul/sadd
  pan/midgard: Only one conditional per bundle allowed
  pan/midgard: Allow 6 instructions per bundle
  pan/midgard: Allow writeout to see into the future
  pan/midgard: Tightly pack 32-bit constants
  pan/midgard: Add mir_flip helper
  pan/midgard: Add csel invert optimization
  pan/midgard: Allow scheduling conditions with constants

 src/panfrost/midgard/compiler.h           |   27 +-
 src/panfrost/midgard/helpers.h            |   17 +-
 src/panfrost/midgard/midgard_compile.c    |  109 +-
 src/panfrost/midgard/midgard_opt_invert.c |   38 +-
 src/panfrost/midgard/midgard_schedule.c   | 1303 ++++++++++++++-------
 src/panfrost/midgard/mir.c                |   85 +-
 6 files changed, 965 insertions(+), 614 deletions(-)

-- 
2.23.0