1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
/*
* Copyright (C) 2018 Rob Clark <robclark@freedesktop.org>
*
* 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 <robclark@freedesktop.org>
*/
#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;
}
|
