nir/schedule: Add an option for a fallback scheduling algorithm

The current scheduling algorithm favors parallelism a bit too
aggressively and sometimes generates shaders that fail register
allocation. This happens even if the threshold is set to zero to force
it to always use the CSR instruction choosing algorithm.

This patch adds an option to use an even more aggressive fallback that
just always picks the instruction with the shortest maximum delay in the
hope that that will generate the least register pressure. The intention
is to use this as a last resort after register allocation fails in order
to at least have a working shader.

Reviewed-by: Alejandro Piñeiro <apinheiro@igalia.com>
Acked-by: Iago Toral Quiroga <itoral@igalia.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/5953>

2 files changed, 53 insertions, 1 deletions

diff --git a/src/compiler/nir/nir_schedule.c b/src/compiler/nir/nir_schedule.c
index 9082278d671..126c49ae8ca 100644
--- a/src/compiler/nir/nir_schedule.c
+++ b/src/compiler/nir/nir_schedule.c
@@ -584,6 +584,50 @@ nir_schedule_regs_freed(nir_schedule_scoreboard *scoreboard, nir_schedule_node *
 }
 
 /**
+ * Chooses an instruction that will minimise the register pressure as much as
+ * possible. This should only be used as a fallback when the regular scheduling
+ * generates a shader whose register allocation fails.
+ */
+static nir_schedule_node *
+nir_schedule_choose_instruction_fallback(nir_schedule_scoreboard *scoreboard)
+{
+   nir_schedule_node *chosen = NULL;
+
+   /* Find the leader in the ready (shouldn't-stall) set with the mininum
+    * cost.
+    */
+   list_for_each_entry(nir_schedule_node, n, &scoreboard->dag->heads, dag.link) {
+      if (scoreboard->time < n->ready_time)
+         continue;
+
+      if (!chosen || chosen->max_delay > n->max_delay)
+         chosen = n;
+   }
+   if (chosen) {
+      if (debug) {
+         fprintf(stderr, "chose (ready fallback):          ");
+         nir_print_instr(chosen->instr, stderr);
+         fprintf(stderr, "\n");
+      }
+
+      return chosen;
+   }
+
+   /* Otherwise, choose the leader with the minimum cost. */
+   list_for_each_entry(nir_schedule_node, n, &scoreboard->dag->heads, dag.link) {
+      if (!chosen || chosen->max_delay > n->max_delay)
+         chosen = n;
+   }
+   if (debug) {
+      fprintf(stderr, "chose (leader fallback):         ");
+      nir_print_instr(chosen->instr, stderr);
+      fprintf(stderr, "\n");
+   }
+
+   return chosen;
+}
+
+/**
  * Chooses an instruction to schedule using the Goodman/Hsu (1988) CSP (Code
  * Scheduling for Parallelism) heuristic.
  *
@@ -913,7 +957,9 @@ nir_schedule_instructions(nir_schedule_scoreboard *scoreboard, nir_block *block)
       }
 
       nir_schedule_node *chosen;
-      if (scoreboard->pressure < scoreboard->options->threshold)
+      if (scoreboard->options->fallback)
+         chosen = nir_schedule_choose_instruction_fallback(scoreboard);
+      else if (scoreboard->pressure < scoreboard->options->threshold)
          chosen = nir_schedule_choose_instruction_csp(scoreboard);
       else
          chosen = nir_schedule_choose_instruction_csr(scoreboard);
diff --git a/src/compiler/nir/nir_schedule.h b/src/compiler/nir/nir_schedule.h
index 98c92a6b46c..d9cf417e906 100644
--- a/src/compiler/nir/nir_schedule.h
+++ b/src/compiler/nir/nir_schedule.h
@@ -58,6 +58,12 @@ typedef struct nir_schedule_options {
     * will try to reduce register usage.
     */
    int threshold;
+   /* If set, instead of trying to optimise parallelism, the scheduler will try
+    * to always minimise register pressure. This can be used as a fallback when
+    * register allocation fails so that it can at least try to generate a
+    * working shader even if it’s inefficient.
+    */
+   bool fallback;
    /* Callback used to add custom dependencies on intrinsics. If it returns
     * true then a dependency should be added and dep is filled in to describe
     * it.