freedreno/ir3: remove Sethi-Ullman numbering pass

We haven't used this for a while.

Signed-off-by: Rob Clark <[email protected]>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/5048>

5 files changed, 1 insertions, 125 deletions

diff --git a/src/freedreno/Makefile.sources b/src/freedreno/Makefile.sources
index 045d94ec6b7..43a8d2b5c1b 100644
--- a/src/freedreno/Makefile.sources
+++ b/src/freedreno/Makefile.sources
@@ -53,8 +53,7 @@ ir3_SOURCES := \
 	ir3/ir3_ra_regset.c \
 	ir3/ir3_sched.c \
 	ir3/ir3_shader.c \
-	ir3/ir3_shader.h \
-	ir3/ir3_sun.c
+	ir3/ir3_shader.h
 
 ir3_GENERATED_FILES := \
 	ir3/ir3_nir_trig.c \
diff --git a/src/freedreno/ir3/ir3.h b/src/freedreno/ir3/ir3.h
index 247dca19564..76fdcdf7a7d 100644
--- a/src/freedreno/ir3/ir3.h
+++ b/src/freedreno/ir3/ir3.h
@@ -324,7 +324,6 @@ struct ir3_instruction {
 	 */
 	struct set *uses;
 
-	int sun;            /* Sethi–Ullman number, used by sched */
 	int use_count;      /* currently just updated/used by cp */
 
 	/* Used during CP and RA stages.  For collect and shader inputs/
@@ -482,8 +481,6 @@ struct ir3 {
 	/* List of ir3_array's: */
 	struct list_head array_list;
 
-	unsigned max_sun;   /* max Sethi–Ullman number */
-
 #ifdef DEBUG
 	unsigned block_count, instr_count;
 #endif
@@ -1206,9 +1203,6 @@ void ir3_cp(struct ir3 *ir, struct ir3_shader_variant *so);
 /* group neighbors and insert mov's to resolve conflicts: */
 void ir3_group(struct ir3 *ir);
 
-/* Sethi–Ullman numbering: */
-void ir3_sun(struct ir3 *ir);
-
 /* scheduling: */
 void ir3_sched_add_deps(struct ir3 *ir);
 int ir3_sched(struct ir3 *ir);
diff --git a/src/freedreno/ir3/ir3_compiler_nir.c b/src/freedreno/ir3/ir3_compiler_nir.c
index 0bfdb7adf38..0f10e819b06 100644
--- a/src/freedreno/ir3/ir3_compiler_nir.c
+++ b/src/freedreno/ir3/ir3_compiler_nir.c
@@ -3583,9 +3583,6 @@ ir3_compile_shader_nir(struct ir3_compiler *compiler,
 
 	ir3_debug_print(ir, "AFTER DCE");
 
-	/* do Sethi–Ullman numbering before scheduling: */
-	ir3_sun(ir);
-
 	ret = ir3_sched(ir);
 	if (ret) {
 		DBG("SCHED failed!");
@@ -3748,8 +3745,6 @@ ir3_compile_shader_nir(struct ir3_compiler *compiler,
 	if (so->type == MESA_SHADER_FRAGMENT)
 		so->total_in = max_bary + 1;
 
-	so->max_sun = ir->max_sun;
-
 	/* Collect sampling instructions eligible for pre-dispatch. */
 	collect_tex_prefetches(ctx, ir);
 
diff --git a/src/freedreno/ir3/ir3_sun.c b/src/freedreno/ir3/ir3_sun.c
deleted file mode 100644
index e61df373064..00000000000
--- a/src/freedreno/ir3/ir3_sun.c
+++ /dev/null
@@ -1,111 +0,0 @@
-/*
- * Copyright (C) 2018 Rob Clark <[email protected]>
- *
- * Permission is hereby granted, free of charge, to any person obtaining a
- * copy of this software and associated documentation files (the "Software"),
- * to deal in the Software without restriction, including without limitation
- * the rights to use, copy, modify, merge, publish, distribute, sublicense,
- * and/or sell copies of the Software, and to permit persons to whom the
- * Software is furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice (including the next
- * paragraph) shall be included in all copies or substantial portions of the
- * Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
- * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- *
- * Authors:
- *    Rob Clark <[email protected]>
- */
-
-
-#include "util/u_math.h"
-
-#include "ir3.h"
-
-/*
- * A simple pass to do Sethi–Ullman numbering, as described in "Generalizations
- * of the Sethi-Ullman algorithm for register allocation"[1].  This is used by
- * the scheduler pass.
- *
- * TODO this could probably be more clever about flow control, ie. if a src
- * is computed in multiple paths into a block, I think we should only have to
- * consider the worst-case.
- *
- * [1] https://www.cs.princeton.edu/~appel/papers/sun.pdf
- */
-
-static unsigned
-number_instr(struct ir3_instruction *instr)
-{
-	if (ir3_instr_check_mark(instr))
-		return instr->sun;
-
-	struct ir3_instruction *src;
-	const unsigned n = __ssa_src_cnt(instr);
-	unsigned a[n];
-	unsigned b[n];
-	unsigned i = 0;
-
-	/* TODO I think including false-deps in the calculation is the right
-	 * thing to do:
-	 */
-	foreach_ssa_src_n (src, n, instr) {
-		if (__is_false_dep(instr, n))
-			continue;
-		if (src->block != instr->block) {
-			a[i] = 1;
-		} else {
-			a[i] = number_instr(src);
-		}
-		b[i] = dest_regs(src);
-		i++;
-	}
-
-	/*
-	 * Rπ = max(aπ(1), bπ(1) + max(aπ(2), bπ(2) + max(..., bπ(k−1) + max(aπ(k), bπ(k)))...):
-	 */
-	unsigned last_r = 0;
-
-	for (int k = i - 1; k >= 0; k--) {
-		unsigned r = MAX2(a[k], b[k] + last_r);
-
-		if (k > 0)
-			r += b[k-1];
-
-		last_r = r;
-	}
-
-	last_r = MAX2(last_r, dest_regs(instr));
-
-	instr->sun = last_r;
-
-	return instr->sun;
-}
-
-void
-ir3_sun(struct ir3 *ir)
-{
-	unsigned max = 0;
-
-	ir3_clear_mark(ir);
-
-	struct ir3_instruction *out;
-	foreach_output (out, ir)
-		max = MAX2(max, number_instr(out));
-
-	foreach_block (block, &ir->block_list) {
-		for (unsigned i = 0; i < block->keeps_count; i++)
-			max = MAX2(max, number_instr(block->keeps[i]));
-		if (block->condition)
-			max = MAX2(max, number_instr(block->condition));
-	}
-
-	ir->max_sun = max;
-}
diff --git a/src/freedreno/ir3/meson.build b/src/freedreno/ir3/meson.build
index 5299ecad744..44eee947e5c 100644
--- a/src/freedreno/ir3/meson.build
+++ b/src/freedreno/ir3/meson.build
@@ -98,7 +98,6 @@ libfreedreno_ir3_files = files(
   'ir3_sched.c',
   'ir3_shader.c',
   'ir3_shader.h',
-  'ir3_sun.c',
 )
 
 libfreedreno_ir3 = static_library(