<div dir="ltr">Reviewed-by: Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Aug 16, 2016 at 1:54 PM, 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 critical path of each node is calculated by induction based on the<br>
critical paths of its children, which can be done in a post-order<br>
depth-first traversal of the dependency graph.  The current code<br>
implements graph traversal by iterating over all nodes of the graph<br>
and then recursing into its children -- But it turns out that<br>
recursion is unnecessary because the lexical order of instructions in<br>
the block is already a good enough reverse post-order of the<br>
dependency graph (if it weren't a reverse post-order some instruction<br>
would have been located before one of its dependencies in the original<br>
ordering of the basic block, which is impossible), so we just need to<br>
walk the instruction list in reverse to achieve the same result more<br>
efficiently.<br>
<br>
No shader-db changes.<br>
---<br>
 .../drivers/dri/i965/brw_<wbr>schedule_instructions.cpp | 25 +++++++++++-----------<br>
 1 file changed, 12 insertions(+), 13 deletions(-)<br>
<br>
diff --git a/src/mesa/drivers/dri/i965/<wbr>brw_schedule_instructions.cpp b/src/mesa/drivers/dri/i965/<wbr>brw_schedule_instructions.cpp<br>
index 8afdc25..19d9ec1 100644<br>
--- a/src/mesa/drivers/dri/i965/<wbr>brw_schedule_instructions.cpp<br>
+++ b/src/mesa/drivers/dri/i965/<wbr>brw_schedule_instructions.cpp<br>
@@ -459,7 +459,7 @@ public:<br>
<br>
    void run(cfg_t *cfg);<br>
    void add_insts_from_block(bblock_t *block);<br>
-   void compute_delay(schedule_node *node);<br>
+   void compute_delays();<br>
    virtual void calculate_deps() = 0;<br>
    virtual schedule_node *choose_instruction_to_<wbr>schedule() = 0;<br>
<br>
@@ -796,17 +796,18 @@ instruction_scheduler::add_<wbr>insts_from_block(bblock_t *block)<br>
    this->instructions_to_schedule = block->end_ip - block->start_ip + 1;<br>
 }<br>
<br>
-/** Recursive computation of the delay member of a node. */<br>
+/** Computation of the delay member of each node. */<br>
 void<br>
-instruction_scheduler::<wbr>compute_delay(schedule_node *n)<br>
+instruction_scheduler::<wbr>compute_delays()<br>
 {<br>
-   if (!n->child_count) {<br>
-      n->delay = issue_time(n->inst);<br>
-   } else {<br>
-      for (int i = 0; i < n->child_count; i++) {<br>
-         if (!n->children[i]->delay)<br>
-            compute_delay(n->children[i]);<br>
-         n->delay = MAX2(n->delay, n->latency + n->children[i]->delay);<br>
+   foreach_in_list_reverse(<wbr>schedule_node, n, &instructions) {<br>
+      if (!n->child_count) {<br>
+         n->delay = issue_time(n->inst);<br>
+      } else {<br>
+         for (int i = 0; i < n->child_count; i++) {<br>
+            assert(n->children[i]->delay);<br>
+            n->delay = MAX2(n->delay, n->latency + n->children[i]->delay);<br>
+         }<br>
       }<br>
    }<br>
 }<br>
@@ -1629,9 +1630,7 @@ instruction_scheduler::run(<wbr>cfg_t *cfg)<br>
<br>
       calculate_deps();<br>
<br>
-      foreach_in_list(schedule_node, n, &instructions) {<br>
-         compute_delay(n);<br>
-      }<br>
+      compute_delays();<br>
<br>
       schedule_instructions(block);<br>
    }<br>
<span class="HOEnZb"><font color="#888888">--<br>
2.9.0<br>
<br>
______________________________<wbr>_________________<br>
mesa-dev mailing list<br>
<a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a><br>
<a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/<wbr>mailman/listinfo/mesa-dev</a><br>
</font></span></blockquote></div><br></div>