[Mesa-dev] [PATCH 3/3] ra: optimistically color only one node at a time
Connor Abbott
cwabbott0 at gmail.com
Tue Jul 29 17:53:36 PDT 2014
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.
Also, consider all the spillable registers as canidates for spilling,
including the ones that were successfully given a color. The old
behavior was incompatible with the new way of doing optimistic coloring,
so while we're modifying this code let's make it do something more
sensible as well.
shader-db results:
helped: shaders/csgo/1376.shader_test SIMD8: 450 -> 445 (-1.11%)
helped: shaders/csgo/1435.shader_test SIMD8: 469 -> 433 (-7.68%)
HURT: shaders/steam/dungeon-defenders/5008.shader_test SIMD8: 434 -> 439 (1.15%)
LOST: shaders/steam/left-4-dead-2/low/2484.shader_test SIMD16
LOST: shaders/steam/left-4-dead-2/low/831.shader_test SIMD16
LOST: shaders/steam/left-4-dead-2/medium/2484.shader_test SIMD16
LOST: shaders/steam/left-4-dead-2/medium/831.shader_test SIMD16
LOST: shaders/warsow/139.shader_test SIMD16
LOST: shaders/xcom-enemy-unknown/203.shader_test SIMD16
GAINED: shaders/csgo/1344.shader_test SIMD16
GAINED: shaders/csgo/1370.shader_test SIMD16
GAINED: shaders/csgo/1382.shader_test SIMD16
GAINED: shaders/csgo/1403.shader_test SIMD16
GAINED: shaders/csgo/1430.shader_test SIMD16
GAINED: shaders/csgo/1431.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/1501.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/1548.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/1606.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/1703.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/1853.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/1904.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/1973.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/1985.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/2163.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/2394.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/2432.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/2546.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/2591.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/2725.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/3012.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/3121.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/3292.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/3351.shader_test SIMD16
GAINED: shaders/steam/brutal-legend/4086.shader_test SIMD16
GAINED: shaders/steam/costume-quest/2349.shader_test SIMD16
GAINED: shaders/steam/costume-quest/2358.shader_test SIMD16
GAINED: shaders/steam/costume-quest/2720.shader_test SIMD16
GAINED: shaders/steam/dota-2/8579.shader_test SIMD16
GAINED: shaders/steam/dota-2/973.shader_test SIMD16
GAINED: shaders/steam/dungeon-defenders/5004.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/high/3776.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/high/3791.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/high/3792.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/high/3811.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/high/3812.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/high/3832.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/1012.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/1090.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/1345.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/1445.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/1501.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/1839.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/2084.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/2148.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/2491.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/3669.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/3706.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/low/629.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/1012.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/1090.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/1345.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/1445.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/1501.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/1839.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/2084.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/2148.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/2491.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/3669.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/3706.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/medium/629.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3771.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3777.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3778.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3779.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3792.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3793.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3812.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3813.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3836.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3871.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3916.shader_test SIMD16
GAINED: shaders/steam/left-4-dead-2/very-high/3917.shader_test SIMD16
GAINED: shaders/steam/portal-2/high/2655.shader_test SIMD16
GAINED: shaders/steam/portal-2/high/881.shader_test SIMD16
GAINED: shaders/steam/portal-2/low/3501.shader_test SIMD16
GAINED: shaders/steam/portal-2/low/881.shader_test SIMD16
GAINED: shaders/steam/portal-2/medium/2655.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/high/1508.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/high/1531.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/high/1545.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/high/1601.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/high/1615.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/low/781.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/low/831.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/low/876.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/medium/1733.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/medium/1795.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/medium/1886.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/medium/1899.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/medium/1940.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/medium/1949.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/ultra/1498.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/ultra/1525.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/ultra/1541.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/ultra/1601.shader_test SIMD16
GAINED: shaders/steam/serious-sam-3/ultra/1685.shader_test SIMD16
GAINED: shaders/steam/stacking/2645.shader_test SIMD16
GAINED: shaders/steam/stacking/4806.shader_test SIMD16
GAINED: shaders/steam/stacking/5100.shader_test SIMD16
GAINED: shaders/steam/stacking/5578.shader_test SIMD16
GAINED: shaders/steam/team-fortress-2/1142.shader_test SIMD16
GAINED: shaders/steam/team-fortress-2/1803.shader_test SIMD16
GAINED: shaders/steam/team-fortress-2/1940.shader_test SIMD16
GAINED: shaders/steam/team-fortress-2/2296.shader_test SIMD16
GAINED: shaders/steam/team-fortress-2/2338.shader_test SIMD16
GAINED: shaders/steam/team-fortress-2/5033.shader_test SIMD16
GAINED: shaders/steam/the-cave/2429.shader_test SIMD16
GAINED: shaders/steam/the-cave/2492.shader_test SIMD16
GAINED: shaders/steam/the-cave/2661.shader_test SIMD16
GAINED: shaders/steam/the-cave/3089.shader_test SIMD16
GAINED: shaders/steam/the-cave/3145.shader_test SIMD16
GAINED: shaders/steam/the-cave/3362.shader_test SIMD16
GAINED: shaders/steam/trine-2/fp-254.shader_test SIMD16
GAINED: shaders/steam/trine-2/fp-274.shader_test SIMD16
GAINED: shaders/steam/trine-2/fp-318.shader_test SIMD16
GAINED: shaders/steam/trine-2/fp-338.shader_test SIMD16
GAINED: shaders/steam/trine-2/fp-350.shader_test SIMD16
GAINED: shaders/steam/trine-2/fp-370.shader_test SIMD16
GAINED: shaders/steam/trine-2/fp-382.shader_test SIMD16
GAINED: shaders/steam/trine-2/fp-402.shader_test SIMD16
GAINED: shaders/witcher2/141.shader_test SIMD16
GAINED: shaders/xcom-enemy-unknown/441.shader_test SIMD16
GAINED: shaders/xcom-enemy-unknown/617.shader_test SIMD16
total instructions in shared programs: 4545447 -> 4545411 (-0.00%)
instructions in affected programs: 1353 -> 1317 (-2.66%)
GAINED: 124
LOST: 6
Signed-off-by: Connor Abbott <connor.abbott at intel.com>
---
src/mesa/program/register_allocate.c | 111 +++++++++--------------------------
1 file changed, 29 insertions(+), 82 deletions(-)
diff --git a/src/mesa/program/register_allocate.c b/src/mesa/program/register_allocate.c
index d5732a7..e0ee46b 100644
--- a/src/mesa/program/register_allocate.c
+++ b/src/mesa/program/register_allocate.c
@@ -168,16 +168,6 @@ struct ra_graph {
unsigned int *stack;
unsigned int stack_count;
-
- /**
- * Tracks the start of the set of optimistically-colored registers in the
- * stack.
- *
- * Along with any registers not in the stack (if one called ra_simplify()
- * and didn't do optimistic coloring), these need to be considered for
- * spilling.
- */
- unsigned int stack_optimistic_start;
};
/**
@@ -454,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;
@@ -466,6 +457,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)
@@ -477,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;
+ }
}
}
+
+ 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;
+ }
}
-
- for (i = 0; i < g->count; i++) {
- if (!g->nodes[i].in_stack && g->nodes[i].reg == -1)
- return false;
- }
-
- return true;
}
/**
@@ -542,35 +543,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;
-
- g->stack_optimistic_start = g->stack_count;
- 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);
}
@@ -633,51 +609,22 @@ ra_get_best_spill_node(struct ra_graph *g)
{
unsigned int best_node = -1;
float best_benefit = 0.0;
- unsigned int n, i;
-
- /* For any registers not in the stack to be colored, consider them for
- * spilling. This will mostly collect nodes that were being optimistally
- * colored as part of ra_allocate() if we didn't successfully
- * optimistically color.
- *
- * It also includes nodes not trivially colorable by ra_simplify() if it
- * was used directly instead of as part of ra_allocate().
- */
- for (n = 0; n < g->count; n++) {
- float cost = g->nodes[n].spill_cost;
- float benefit;
-
- if (cost <= 0.0)
- continue;
-
- if (g->nodes[n].in_stack)
- continue;
-
- benefit = ra_get_spill_benefit(g, n);
-
- if (benefit / cost > best_benefit) {
- best_benefit = benefit / cost;
- best_node = n;
- }
- }
+ unsigned int i;
- /* Also consider spilling any nodes that were set up to be optimistically
- * colored that we couldn't manage to color in ra_select().
- */
- for (i = g->stack_optimistic_start; i < g->stack_count; i++) {
+ /* Consider spilling any nodes with a spill cost set */
+ for (i = 0; i < g->count; i++) {
float cost, benefit;
- n = g->stack[i];
- cost = g->nodes[n].spill_cost;
+ cost = g->nodes[i].spill_cost;
if (cost <= 0.0)
continue;
- benefit = ra_get_spill_benefit(g, n);
+ benefit = ra_get_spill_benefit(g, i);
if (benefit / cost > best_benefit) {
best_benefit = benefit / cost;
- best_node = n;
+ best_node = i;
}
}
--
1.9.3
More information about the mesa-dev
mailing list