Module: Mesa Branch: master Commit: e78a01d5e6f77e075fe667a0f0ccb10d89c0dd58 URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=e78a01d5e6f77e075fe667a0f0ccb10d89c0dd58
Author: Connor Abbott <[email protected]> Date: Thu Jul 31 18:57:23 2014 -0700 ra: optimistically color only one node at a time Before, when we encountered a situation where we had to optimistically color a node, we would immediately give up and push all the remaining nodes on the stack in the order of their index - which is a random, and potentially not optimal, order. Instead, choose one node to optimistically color in ra_select(), and then once we've optimistically colored it, keep on going as normal in the hopes that we've opened up more avenues for the normal select phase to make progress. In cases with high register pressure, this helps make the order we push things on the stack much better, and therefore increase the chance that we can allocate successfully. total instructions in shared programs: 4545447 -> 4545401 (-0.00%) instructions in affected programs: 1353 -> 1307 (-3.40%) GAINED: 124 LOST: 6 Signed-off-by: Connor Abbott <[email protected]> Reviewed-by: Eric Anholt <[email protected]> --- src/mesa/program/register_allocate.c | 57 +++++++++++++--------------------- 1 file changed, 22 insertions(+), 35 deletions(-) diff --git a/src/mesa/program/register_allocate.c b/src/mesa/program/register_allocate.c index 4c17de7..d81a47f 100644 --- a/src/mesa/program/register_allocate.c +++ b/src/mesa/program/register_allocate.c @@ -444,11 +444,12 @@ decrement_q(struct ra_graph *g, unsigned int n) * trivially-colorable nodes into a stack of nodes to be colored, * removing them from the graph, and rinsing and repeating. * - * Returns true if all nodes were removed from the graph. false - * means that either spilling will be required, or optimistic coloring - * should be applied. + * If we encounter a case where we can't push any nodes on the stack, then + * we optimistically choose a node and push it on the stack. We heuristically + * push the node with the lowest total q value, since it has the fewest + * neighbors and therefore is most likely to be allocated. */ -static bool +static void ra_simplify(struct ra_graph *g) { bool progress = true; @@ -457,6 +458,9 @@ ra_simplify(struct ra_graph *g) while (progress) { progress = false; + unsigned int best_optimistic_node = ~0; + unsigned int lowest_q_total = ~0; + for (i = g->count - 1; i >= 0; i--) { if (g->nodes[i].in_stack || g->nodes[i].reg != NO_REG) continue; @@ -467,16 +471,23 @@ ra_simplify(struct ra_graph *g) g->stack_count++; g->nodes[i].in_stack = true; progress = true; + } else { + unsigned int new_q_total = g->nodes[i].q_total; + if (new_q_total < lowest_q_total) { + best_optimistic_node = i; + lowest_q_total = new_q_total; + } } } - } - for (i = 0; i < g->count; i++) { - if (!g->nodes[i].in_stack && g->nodes[i].reg == -1) - return false; + if (!progress && best_optimistic_node != ~0) { + decrement_q(g, best_optimistic_node); + g->stack[g->stack_count] = best_optimistic_node; + g->stack_count++; + g->nodes[best_optimistic_node].in_stack = true; + progress = true; + } } - - return true; } /** @@ -537,34 +548,10 @@ ra_select(struct ra_graph *g) return true; } -/** - * Optimistic register coloring: Just push the remaining nodes - * on the stack. They'll be colored first in ra_select(), and - * if they succeed then the locally-colorable nodes are still - * locally-colorable and the rest of the register allocation - * will succeed. - */ -static void -ra_optimistic_color(struct ra_graph *g) -{ - unsigned int i; - - for (i = 0; i < g->count; i++) { - if (g->nodes[i].in_stack || g->nodes[i].reg != NO_REG) - continue; - - g->stack[g->stack_count] = i; - g->stack_count++; - g->nodes[i].in_stack = true; - } -} - bool ra_allocate(struct ra_graph *g) { - if (!ra_simplify(g)) { - ra_optimistic_color(g); - } + ra_simplify(g); return ra_select(g); } _______________________________________________ mesa-commit mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/mesa-commit
