1/*
2 * Copyright (C) 2018 Rob Clark <robclark@freedesktop.org>
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21 * SOFTWARE.
22 *
23 * Authors:
24 *    Rob Clark <robclark@freedesktop.org>
25 */
26
27
28#include "util/u_math.h"
29
30#include "ir3.h"
31
32/*
33 * A simple pass to do Sethi–Ullman numbering, as described in "Generalizations
34 * of the Sethi-Ullman algorithm for register allocation"[1].  This is used by
35 * the scheduler pass.
36 *
37 * TODO this could probably be more clever about flow control, ie. if a src
38 * is computed in multiple paths into a block, I think we should only have to
39 * consider the worst-case.
40 *
41 * [1] https://pdfs.semanticscholar.org/ae53/6010b214612c2571f483354c264b0b39c545.pdf
42 */
43
44static unsigned
45number_instr(struct ir3_instruction *instr)
46{
47	if (ir3_instr_check_mark(instr))
48		return instr->sun;
49
50	struct ir3_instruction *src;
51	const unsigned n = __ssa_src_cnt(instr);
52	unsigned a[n];
53	unsigned b[n];
54	unsigned i = 0;
55
56	/* TODO I think including false-deps in the calculation is the right
57	 * thing to do:
58	 */
59	foreach_ssa_src_n(src, n, instr) {
60		if (__is_false_dep(instr, n))
61			continue;
62		if (src->block != instr->block) {
63			a[i] = 1;
64		} else {
65			a[i] = number_instr(src);
66		}
67		b[i] = dest_regs(src);
68		i++;
69	}
70
71	/*
72	 * Rπ = max(aπ(1), bπ(1) + max(aπ(2), bπ(2) + max(..., bπ(k−1) + max(aπ(k), bπ(k)))...):
73	 */
74	unsigned last_r = 0;
75
76	for (int k = i - 1; k >= 0; k--) {
77		unsigned r = MAX2(a[k], b[k] + last_r);
78
79		if (k > 0)
80			r += b[k-1];
81
82		last_r = r;
83	}
84
85	last_r = MAX2(last_r, dest_regs(instr));
86
87	instr->sun = last_r;
88
89	return instr->sun;
90}
91
92void
93ir3_sun(struct ir3 *ir)
94{
95	unsigned max = 0;
96
97	ir3_clear_mark(ir);
98
99	for (unsigned i = 0; i < ir->noutputs; i++)
100		if (ir->outputs[i])
101			max = MAX2(max, number_instr(ir->outputs[i]));
102
103	list_for_each_entry (struct ir3_block, block, &ir->block_list, node) {
104		for (unsigned i = 0; i < block->keeps_count; i++)
105			max = MAX2(max, number_instr(block->keeps[i]));
106		if (block->condition)
107			max = MAX2(max, number_instr(block->condition));
108	}
109
110	ir->max_sun = max;
111}
112