<div dir="ltr"><div class="gmail_extra"><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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">This adds a bit of metadata to schedule_node that will be used to<br>
compare available nodes in the scheduling heuristic code based on<br>
which of them unblocks the earliest successor exit node. Note that<br>
assigning exit nodes wouldn't be necessary in a bottom-up scheduler<br>
because we could achieve the same effect by scheduling the exit nodes<br>
themselves appropriately.<br></blockquote><div><br></div><div>Hopefully we can actually make that switch soon.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
---<br>
.../drivers/dri/i965/brw_sche<wbr>dule_instructions.cpp | 59 ++++++++++++++++++++++<br>
1 file changed, 59 insertions(+)<br>
<br>
diff --git a/src/mesa/drivers/dri/i965/br<wbr>w_schedule_instructions.cpp b/src/mesa/drivers/dri/i965/br<wbr>w_schedule_instructions.cpp<br>
index 19d9ec1..96562cf 100644<br>
--- a/src/mesa/drivers/dri/i965/br<wbr>w_schedule_instructions.cpp<br>
+++ b/src/mesa/drivers/dri/i965/br<wbr>w_schedule_instructions.cpp<br>
@@ -86,8 +86,34 @@ public:<br>
* its children, or just the issue_time if it's a leaf node.<br>
*/<br>
int delay;<br>
+<br>
+ /**<br>
+ * Preferred exit node among the (direct or indirect) successors of this<br>
+ * node. Among the scheduler nodes blocked by this node, this will be the<br>
+ * one that may cause earliest program termination, or NULL if none of the<br>
+ * successors is an exit node.<br>
+ */<br>
+ schedule_node *exit;<br>
};<br>
<br>
+/**<br>
+ * Lower bound of the scheduling time after which one of the instructions<br>
+ * blocked by this node may lead to program termination.<br>
+ *<br>
+ * exit_unblocked_time() determines a strict partial ordering relation '«' on<br>
+ * the set of scheduler nodes as follows:<br>
+ *<br>
+ * n « m <-> exit_unblocked_time(n) < exit_unblocked_time(m)<br>
+ *<br>
+ * which can be used to heuristically order nodes according to how early they<br>
+ * can unblock an exit node and lead to program termination.<br>
+ */<br>
+static inline int<br>
+exit_unblocked_time(const schedule_node *n)<br>
+{<br>
+ return n->exit ? n->exit->unblocked_time : INT_MAX;<br>
+}<br>
+<br>
void<br>
schedule_node::set_latency_ge<wbr>n4()<br>
{<br>
@@ -460,6 +486,7 @@ public:<br>
void run(cfg_t *cfg);<br>
void add_insts_from_block(bblock_t *block);<br>
void compute_delays();<br>
+ void compute_exits();<br>
virtual void calculate_deps() = 0;<br>
virtual schedule_node *choose_instruction_to_schedul<wbr>e() = 0;<br>
<br>
@@ -772,6 +799,7 @@ schedule_node::schedule_node(b<wbr>ackend_instruction *inst,<br>
this->unblocked_time = 0;<br>
this->cand_generation = 0;<br>
this->delay = 0;<br>
+ this->exit = NULL;<br>
<br>
/* We can't measure Gen6 timings directly but expect them to be much<br>
* closer to Gen7 than Gen4.<br>
@@ -812,6 +840,36 @@ instruction_scheduler::compute<wbr>_delays()<br>
}<br>
}<br>
<br>
+void<br>
+instruction_scheduler::comput<wbr>e_exits()<br>
+{<br>
+ /* Calculate a lower bound of the scheduling time of each node in the<br>
+ * graph. This is analogous to the node's critical path but calculated<br>
+ * from the top instead of from the bottom of the block.<br>
+ */<br>
+ foreach_in_list(schedule_<wbr>node, n, &instructions) {<br>
+ for (int i = 0; i < n->child_count; i++) {<br>
+ n->children[i]->unblocked_<wbr>time =<br>
+ MAX2(n->children[i]->unblocked<wbr>_time,<br>
+ n->unblocked_time + issue_time(n->inst) + n->child_latency[i]);<br>
+ }<br>
+ }<br></blockquote><div><br></div><div>Dos this calculation affect scheduling later on? I don't think it will since we're effectively setting n->unblocked_time to the lowest possible based on a dependency DFS. Later uses *shouldn't* set it to anything less. Should be easy enough to check with shader-db.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+<br>
+ /* Calculate the exit of each node by induction based on the exit nodes of<br>
+ * its children. The preferred exit of a node is the one among the exit<br>
+ * nodes of its children which can be unblocked first according to the<br>
+ * optimistic unblocked time estimate calculated above.<br>
+ */<br>
+ foreach_in_list_reverse(sched<wbr>ule_node, n, &instructions) {<br>
+ n->exit = (n->inst->opcode == FS_OPCODE_DISCARD_JUMP ? n : NULL);<br>
+<br>
+ for (int i = 0; i < n->child_count; i++) {<br>
+ if (exit_unblocked_time(n->childr<wbr>en[i]) < exit_unblocked_time(n))<br></blockquote><div><br></div><div>It strikes me as a bit odd that we compare n->children[i] with n rather than n->exit, but the next line means it's equivalent.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+ n->exit = n->children[i]->exit;<br>
+ }<br>
+ }<br>
+}<br></blockquote><div><br></div><div>Assuming this patch *doesn't* change scheduling in any way,<br><br></div><div>Reviewed-by: Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+<br>
/**<br>
* Add a dependency between two instruction nodes.<br>
*<br>
@@ -1631,6 +1689,7 @@ instruction_scheduler::run(cfg<wbr>_t *cfg)<br>
calculate_deps();<br>
<br>
compute_delays();<br>
+ compute_exits();<br>
<br>
schedule_instructions(block);<br>
}<br>
<span><font color="#888888">--<br>
2.9.0<br>
<br>
______________________________<wbr>_________________<br>
mesa-dev mailing list<br>
<a href="mailto:mesa-dev@lists.freedesktop.org" target="_blank">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></div>