| /* |
| * 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; |
| } |