summaryrefslogtreecommitdiffstats
path: root/src/mesa
diff options
context:
space:
mode:
authorFrancisco Jerez <[email protected]>2016-08-16 00:01:31 -0700
committerFrancisco Jerez <[email protected]>2016-08-18 20:05:00 -0700
commitb295d7ca32bbab94d4038c5684a38fd8f3dc4373 (patch)
tree1473429afd815d54e421f2f5d74a5a0efe7e65c8 /src/mesa
parentb2b621a0ec57f08586b9afcf666c0eadc0993ca0 (diff)
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 <[email protected]>
Diffstat (limited to 'src/mesa')
-rw-r--r--src/mesa/drivers/dri/i965/brw_schedule_instructions.cpp25
1 files 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);
}