Reviewed-by: Jason Ekstrand <ja...@jlekstrand.net>
On Tue, Aug 16, 2016 at 1:54 PM, Francisco Jerez <curroje...@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@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
