<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Feb 16, 2015 at 11:39 AM, Francisco Jerez <span dir="ltr"><<a href="mailto:currojerez@riseup.net" target="_blank">currojerez@riseup.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">The round-robin allocation strategy is expected to decrease the amount<br>
of false dependencies created by the register allocator and give the<br>
post-RA scheduling pass more freedom to move instructions around. On<br>
the other hand it has the disadvantage of increasing fragmentation and<br>
decreasing the number of equally-colored nearby nodes, what increases<br>
the likelihood of failure in presence of optimistically colorable<br>
nodes.<br>
<br>
This patch disables the round-robin strategy for optimistically<br>
colorable nodes. These typically arise in situations of high register<br>
pressure or for registers with large live intervals, in both cases the<br>
task of the instruction scheduler shouldn't be constrained excessively<br>
by the dense packing of those nodes, and a spill (or on Intel hardware<br>
a fall-back to SIMD8 mode) is invariably worse than a slightly less<br>
optimal scheduling.<br>
<br>
Shader-db results on the i965 driver:<br>
<br>
total instructions in shared programs: 5488539 -> 5488489 (-0.00%)<br>
instructions in affected programs: 1121 -> 1071 (-4.46%)<br>
helped: 1<br>
HURT: 0<br>
GAINED: 49<br>
LOST: 5<br>
---<br>
src/util/register_allocate.c | 22 +++++++++++++++++++++-<br>
1 file changed, 21 insertions(+), 1 deletion(-)<br>
<br>
diff --git a/src/util/register_allocate.c b/src/util/register_allocate.c<br>
index af7a20c..d63d8eb 100644<br>
--- a/src/util/register_allocate.c<br>
+++ b/src/util/register_allocate.c<br>
@@ -168,6 +168,12 @@ struct ra_graph {<br>
<br>
unsigned int *stack;<br>
unsigned int stack_count;<br>
+<br>
+ /**<br>
+ * Tracks the start of the set of optimistically-colored registers in the<br>
+ * stack.<br>
+ */<br>
+ unsigned int stack_optimistic_start;<br>
};<br>
<br>
/**<br>
@@ -454,6 +460,7 @@ static void<br>
ra_simplify(struct ra_graph *g)<br>
{<br>
bool progress = true;<br>
+ unsigned int stack_optimistic_start = ~0;<br></blockquote><div><br></div><div>UINT_MAX would be clearer than ~0<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
int i;<br>
<br>
while (progress) {<br>
@@ -483,12 +490,16 @@ ra_simplify(struct ra_graph *g)<br>
<br>
if (!progress && best_optimistic_node != ~0U) {<br></blockquote><div><br></div><div>I guess we're using ~0 other places... oh well...<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
decrement_q(g, best_optimistic_node);<br>
+ stack_optimistic_start =<br>
+ MIN2(stack_optimistic_start, g->stack_count);<br></blockquote><div><br></div><div>It might be clearer to explicitly use an if here instead of the MIN2 because what this really means is "if (stack_optimistic_start == ~0) stack_optimistic_start = g->stack_count;"<br><br></div><div>Other than that (and connor's comment), it looks fine to me.<br><br></div><div>--Jason<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
g->stack[g->stack_count] = best_optimistic_node;<br>
g->stack_count++;<br>
g->nodes[best_optimistic_node].in_stack = true;<br>
progress = true;<br>
}<br>
}<br>
+<br>
+ g->stack_optimistic_start = stack_optimistic_start;<br>
}<br>
<br>
/**<br>
@@ -542,7 +553,16 @@ ra_select(struct ra_graph *g)<br>
g->nodes[n].reg = r;<br>
g->stack_count--;<br>
<br>
- if (g->regs->round_robin)<br>
+ /* Rotate the starting point except for optimistically colorable nodes.<br>
+ * The likelihood that we will succeed at allocating optimistically<br>
+ * colorable nodes is highly dependent on the way that the previous<br>
+ * nodes popped off the stack are laid out. The round-robin strategy<br>
+ * increases the fragmentation of the register file and decreases the<br>
+ * number of nearby nodes assigned to the same color, what increases the<br>
+ * likelihood of spilling with respect to the dense packing strategy.<br>
+ */<br>
+ if (g->regs->round_robin &&<br>
+ g->stack_count <= g->stack_optimistic_start)<br>
start_search_reg = r + 1;<br>
}<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
2.1.3<br>
<br>
_______________________________________________<br>
mesa-dev mailing list<br>
<a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a><br>
<a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev" target="_blank">http://lists.freedesktop.org/mailman/listinfo/mesa-dev</a><br>
</font></span></blockquote></div><br></div></div>