From b295d7ca32bbab94d4038c5684a38fd8f3dc4373 Mon Sep 17 00:00:00 2001 From: Francisco Jerez Date: Tue, 16 Aug 2016 00:01:31 -0700 Subject: [PATCH] i965/sched: Calculate the critical path of scheduling nodes non-recursively. The critical path of each node is calculated by induction based on the critical paths of its children, which can be done in a post-order depth-first traversal of the dependency graph. The current code implements graph traversal by iterating over all nodes of the graph and then recursing into its children -- But it turns out that recursion is unnecessary because the lexical order of instructions in the block is already a good enough reverse post-order of the dependency graph (if it weren't a reverse post-order some instruction would have been located before one of its dependencies in the original ordering of the basic block, which is impossible), so we just need to walk the instruction list in reverse to achieve the same result more efficiently. No shader-db changes. Reviewed-by: Jason Ekstrand --- .../dri/i965/brw_schedule_instructions.cpp | 25 +++++++++---------- 1 file changed, 12 insertions(+), 13 deletions(-) diff --git a/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp b/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp index 8afdc25c2c5..19d9ec10a73 100644 --- a/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp +++ b/src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp @@ -459,7 +459,7 @@ public: void run(cfg_t *cfg); void add_insts_from_block(bblock_t *block); - void compute_delay(schedule_node *node); + void compute_delays(); virtual void calculate_deps() = 0; virtual schedule_node *choose_instruction_to_schedule() = 0; @@ -796,17 +796,18 @@ instruction_scheduler::add_insts_from_block(bblock_t *block) this->instructions_to_schedule = block->end_ip - block->start_ip + 1; } -/** Recursive computation of the delay member of a node. */ +/** Computation of the delay member of each node. */ void -instruction_scheduler::compute_delay(schedule_node *n) +instruction_scheduler::compute_delays() { - 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); + foreach_in_list_reverse(schedule_node, n, &instructions) { + if (!n->child_count) { + n->delay = issue_time(n->inst); + } else { + for (int i = 0; i < n->child_count; i++) { + assert(n->children[i]->delay); + n->delay = MAX2(n->delay, n->latency + n->children[i]->delay); + } } } } @@ -1629,9 +1630,7 @@ instruction_scheduler::run(cfg_t *cfg) calculate_deps(); - foreach_in_list(schedule_node, n, &instructions) { - compute_delay(n); - } + compute_delays(); schedule_instructions(block); } -- 2.30.2