[Mesa-dev] [PATCH 2/7] i965/sched: use a critical path heuristic

[Connor Abbott]

This makes the schedule more aggressive about hiding latency, but being
able to dynamically switch to another strategy once our register
pressure increases beyond a certain point should help here.

total instructions in shared programs: 7460652 -> 7461304 (0.01%)
instructions in affected programs: 6055 -> 6707 (10.77%)
helped: 1
HURT: 8

total cycles in shared programs: 52874386 -> 50180046 (-5.10%)
cycles in affected programs: 50336130 -> 47641790 (-5.35%)
helped: 58987
HURT: 1004

LOST:   3
GAINED: 0
Signed-off-by: Connor Abbott <cwabbott0 at gmail.com>
---
 .../drivers/dri/i965/brw_schedule_instructions.cpp | 24 ++++++++++++++++------
 1 file changed, 18 insertions(+), 6 deletions(-)

diff --git a/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp b/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp
index a611dd1..3ae8c3f 100644
--- a/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp
+++ b/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp
@@ -1396,15 +1396,27 @@ fs_instruction_scheduler::choose_instruction_to_schedule()
    schedule_node *chosen = NULL;
 
    if (mode == SCHEDULE_PRE || mode == SCHEDULE_POST) {
-      int chosen_time = 0;
-
-      /* Of the instructions ready to execute or the closest to
-       * being ready, choose the oldest one.
+      int chosen_unblocked_time = 0, chosen_delay = 0;
+
+      /* First, find the earliest instruction we can possibly schedule. Then,
+       * if there are multiple instructions that we can schedule at the same
+       * time, choose the thing with the longest critical path. The idea here
+       * is to try not to lengthen already larger critical path lengths, but
+       * if we can, we should first schedule instructions that we can fit in
+       * before the instruction with the longest critical path. There might be
+       * some cases where we still bump the critical path instruction, but
+       * this seems unlikely, given that most instructions have the same issue
+       * time and most latencies are a multiple of the issue time.
        */
       foreach_in_list(schedule_node, n, &instructions) {
-         if (!chosen || n->unblocked_time < chosen_time) {
+         int unblocked_time = MAX2(n->unblocked_time, time);
+         if (!chosen ||
+             unblocked_time < chosen_unblocked_time ||
+             (unblocked_time == chosen_unblocked_time &&
+              n->delay > chosen_delay)) {
             chosen = n;
-            chosen_time = n->unblocked_time;
+            chosen_unblocked_time = unblocked_time;
+            chosen_delay = n->delay;
          }
       }
    } else {
-- 
2.4.3