Mesa (master): i965: Compute the node's delay time for scheduling.

[Eric Anholt]

Module: Mesa
Branch: master
Commit: 017361dd37b678efa44facc4a396784f4ce980bc
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=017361dd37b678efa44facc4a396784f4ce980bc

Author: Eric Anholt <eric at anholt.net>
Date:   Mon Oct 28 00:11:45 2013 -0700

i965: Compute the node's delay time for scheduling.

This is a step in doing scheduling as described in Muchnick (p538).  A
difference is that our latency function is only specific to one
instruction (it doesn't describe, for example, the different latency
between WAR of a send's arguments and RAW of a send's destination), but
that's changeable later.  We also don't separately compute the postorder
traversal of the graph, since we can use the setting of the delay field as
the "visited" flag.

Reviewed-by: Paul Berry <stereotype441 at gmail.com>

---

 .../drivers/dri/i965/brw_schedule_instructions.cpp |   28 ++++++++++++++++++++
 1 files changed, 28 insertions(+), 0 deletions(-)

diff --git a/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp b/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp
index 27de0e6..8437a4e 100644
--- a/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp
+++ b/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp
@@ -89,6 +89,12 @@ public:
    int child_array_size;
    int unblocked_time;
    int latency;
+
+   /**
+    * This is the sum of the instruction's latency plus the maximum delay of
+    * its children, or just the issue_time if it's a leaf node.
+    */
+   int delay;
 };
 
 void
@@ -365,6 +371,7 @@ public:
 
    void run(exec_list *instructions);
    void add_inst(backend_instruction *inst);
+   void compute_delay(schedule_node *node);
    virtual void calculate_deps() = 0;
    virtual schedule_node *choose_instruction_to_schedule() = 0;
 
@@ -439,6 +446,21 @@ instruction_scheduler::add_inst(backend_instruction *inst)
    instructions.push_tail(n);
 }
 
+/** Recursive computation of the delay member of a node. */
+void
+instruction_scheduler::compute_delay(schedule_node *n)
+{
+   if (!n->child_count) {
+      n->delay = issue_time(n->inst);
+   } else {
+      for (int i = 0; i < n->child_count; i++) {
+         if (!n->children[i]->delay)
+            compute_delay(n->children[i]);
+         n->delay = MAX2(n->delay, n->latency + n->children[i]->delay);
+      }
+   }
+}
+
 /**
  * Add a dependency between two instruction nodes.
  *
@@ -1118,6 +1140,12 @@ instruction_scheduler::run(exec_list *all_instructions)
 	    break;
       }
       calculate_deps();
+
+      foreach_list(node, &instructions) {
+         schedule_node *n = (schedule_node *)node;
+         compute_delay(n);
+      }
+
       schedule_instructions(next_block_header);
    }