[Mesa-dev] [PATCH 3/5] i965/sched: Calculate the critical path of scheduling nodes non-recursively.

[Jason Ekstrand]

Reviewed-by: Jason Ekstrand <jason at jlekstrand.net>

On Tue, Aug 16, 2016 at 1:54 PM, Francisco Jerez <currojerez at riseup.net>
wrote:

> 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.
> ---
>  .../drivers/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 8afdc25..19d9ec1 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.9.0
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20160816/dc285a13/attachment.html>