2 * Copyright (C) 2018 Rob Clark <robclark@freedesktop.org>
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:
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
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
24 * Rob Clark <robclark@freedesktop.org>
28 #include "util/u_math.h"
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
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.
41 * [1] https://pdfs.semanticscholar.org/ae53/6010b214612c2571f483354c264b0b39c545.pdf
45 number_instr(struct ir3_instruction
*instr
)
47 if (ir3_instr_check_mark(instr
))
50 struct ir3_instruction
*src
;
51 const unsigned n
= __ssa_src_cnt(instr
);
56 /* TODO I think including false-deps in the calculation is the right
59 foreach_ssa_src_n(src
, n
, instr
) {
60 if (__is_false_dep(instr
, n
))
62 if (src
->block
!= instr
->block
) {
65 a
[i
] = number_instr(src
);
67 b
[i
] = dest_regs(src
);
72 * Rπ = max(aπ(1), bπ(1) + max(aπ(2), bπ(2) + max(..., bπ(k−1) + max(aπ(k), bπ(k)))...):
76 for (int k
= i
- 1; k
>= 0; k
--) {
77 unsigned r
= MAX2(a
[k
], b
[k
] + last_r
);
85 last_r
= MAX2(last_r
, dest_regs(instr
));
93 ir3_sun(struct ir3
*ir
)
99 for (unsigned i
= 0; i
< ir
->noutputs
; i
++)
101 max
= MAX2(max
, number_instr(ir
->outputs
[i
]));
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
));