From d6a9731d8f94c4ecaea69bed6034f8a605838b6d Mon Sep 17 00:00:00 2001 From: Francisco Jerez Date: Mon, 5 Aug 2019 17:36:40 -0700 Subject: intel/ir: Represent physical and logical subsets of the CFG. This represents two control flow graphs in the same cfg_t data structure: The physical CFG that will include all possible control flow paths the EU can physically take, and the logical CFG restricted to the control flow paths that exist in the original scalar program. The latter is a subset of the former because in case of divergence the SIMD vectorized program will take control flow paths that aren't part of the original scalar program. The bblock_link constructor and bblock_t::add_successor() now take a "kind" parameter that specifies whether the edge is purely physical or whether it's part of both the logical and physical CFGs (a logical edge is of course always guaranteed to be in the physical CFG as well). bblock_t::is_predecessor_of() and ::is_successor_of() also take a kind parameter specifying which CFG is being queried. The '~>' notation will be used now in order to represent purely physical edges in IR dumps. This commit doesn't actually add nor remove any edges from the CFG (the only edges marked as purely physical here are the two WHILE loop ones that already existed). Optimization passes should continue using the same (incomplete) physical CFG they were using before until they're fixed to do something smarter in a later commit, so this shouldn't lead to any functional changes. v2: Remove tabs from lines changed in this file (Caio). Reviewed-by: Jordan Justen Reviewed-by: Caio Marcelo de Oliveira Filho --- src/intel/compiler/brw_cfg.cpp | 78 +++++++++++++++++------------ src/intel/compiler/brw_cfg.h | 37 ++++++++++++-- src/intel/compiler/brw_predicated_break.cpp | 6 ++- 3 files changed, 81 insertions(+), 40 deletions(-) diff --git a/src/intel/compiler/brw_cfg.cpp b/src/intel/compiler/brw_cfg.cpp index 6c40889088d..0d6c6fc5f5b 100644 --- a/src/intel/compiler/brw_cfg.cpp +++ b/src/intel/compiler/brw_cfg.cpp @@ -44,9 +44,9 @@ pop_stack(exec_list *list) } static exec_node * -link(void *mem_ctx, bblock_t *block) +link(void *mem_ctx, bblock_t *block, enum bblock_link_kind kind) { - bblock_link *l = new(mem_ctx) bblock_link(block); + bblock_link *l = new(mem_ctx) bblock_link(block, kind); return &l->link; } @@ -59,17 +59,19 @@ bblock_t::bblock_t(cfg_t *cfg) : } void -bblock_t::add_successor(void *mem_ctx, bblock_t *successor) +bblock_t::add_successor(void *mem_ctx, bblock_t *successor, + enum bblock_link_kind kind) { - successor->parents.push_tail(::link(mem_ctx, this)); - children.push_tail(::link(mem_ctx, successor)); + successor->parents.push_tail(::link(mem_ctx, this, kind)); + children.push_tail(::link(mem_ctx, successor, kind)); } bool -bblock_t::is_predecessor_of(const bblock_t *block) const +bblock_t::is_predecessor_of(const bblock_t *block, + enum bblock_link_kind kind) const { foreach_list_typed_safe (bblock_link, parent, link, &block->parents) { - if (parent->block == this) { + if (parent->block == this && parent->kind <= kind) { return true; } } @@ -78,10 +80,11 @@ bblock_t::is_predecessor_of(const bblock_t *block) const } bool -bblock_t::is_successor_of(const bblock_t *block) const +bblock_t::is_successor_of(const bblock_t *block, + enum bblock_link_kind kind) const { foreach_list_typed_safe (bblock_link, child, link, &block->children) { - if (child->block == this) { + if (child->block == this && child->kind <= kind) { return true; } } @@ -185,8 +188,8 @@ cfg_t::cfg_t(exec_list *instructions) /* Push our information onto a stack so we can recover from * nested ifs. */ - if_stack.push_tail(link(mem_ctx, cur_if)); - else_stack.push_tail(link(mem_ctx, cur_else)); + if_stack.push_tail(link(mem_ctx, cur_if, bblock_link_logical)); + else_stack.push_tail(link(mem_ctx, cur_else, bblock_link_logical)); cur_if = cur; cur_else = NULL; @@ -196,7 +199,7 @@ cfg_t::cfg_t(exec_list *instructions) * instructions. */ next = new_block(); - cur_if->add_successor(mem_ctx, next); + cur_if->add_successor(mem_ctx, next, bblock_link_logical); set_next_block(&cur, next, ip); break; @@ -208,7 +211,7 @@ cfg_t::cfg_t(exec_list *instructions) next = new_block(); assert(cur_if != NULL); - cur_if->add_successor(mem_ctx, next); + cur_if->add_successor(mem_ctx, next, bblock_link_logical); set_next_block(&cur, next, ip); break; @@ -220,7 +223,7 @@ cfg_t::cfg_t(exec_list *instructions) } else { cur_endif = new_block(); - cur->add_successor(mem_ctx, cur_endif); + cur->add_successor(mem_ctx, cur_endif, bblock_link_logical); set_next_block(&cur, cur_endif, ip - 1); } @@ -228,10 +231,10 @@ cfg_t::cfg_t(exec_list *instructions) cur->instructions.push_tail(inst); if (cur_else) { - cur_else->add_successor(mem_ctx, cur_endif); + cur_else->add_successor(mem_ctx, cur_endif, bblock_link_logical); } else { assert(cur_if != NULL); - cur_if->add_successor(mem_ctx, cur_endif); + cur_if->add_successor(mem_ctx, cur_endif, bblock_link_logical); } assert(cur_if->end()->opcode == BRW_OPCODE_IF); @@ -246,8 +249,8 @@ cfg_t::cfg_t(exec_list *instructions) /* Push our information onto a stack so we can recover from * nested loops. */ - do_stack.push_tail(link(mem_ctx, cur_do)); - while_stack.push_tail(link(mem_ctx, cur_while)); + do_stack.push_tail(link(mem_ctx, cur_do, bblock_link_logical)); + while_stack.push_tail(link(mem_ctx, cur_while, bblock_link_logical)); /* Set up the block just after the while. Don't know when exactly * it will start, yet. @@ -260,7 +263,7 @@ cfg_t::cfg_t(exec_list *instructions) } else { cur_do = new_block(); - cur->add_successor(mem_ctx, cur_do); + cur->add_successor(mem_ctx, cur_do, bblock_link_logical); set_next_block(&cur, cur_do, ip - 1); } @@ -294,8 +297,8 @@ cfg_t::cfg_t(exec_list *instructions) * corruption. */ next = new_block(); - cur->add_successor(mem_ctx, next); - cur->add_successor(mem_ctx, cur_while); + cur->add_successor(mem_ctx, next, bblock_link_logical); + cur->add_successor(mem_ctx, cur_while, bblock_link_physical); set_next_block(&cur, next, ip); break; @@ -316,11 +319,11 @@ cfg_t::cfg_t(exec_list *instructions) * loop, the top of the loop again, into a use of the variable). */ assert(cur_do != NULL); - cur->add_successor(mem_ctx, cur_do->next()); + cur->add_successor(mem_ctx, cur_do->next(), bblock_link_logical); next = new_block(); if (inst->predicate) - cur->add_successor(mem_ctx, next); + cur->add_successor(mem_ctx, next, bblock_link_logical); set_next_block(&cur, next, ip); break; @@ -339,11 +342,11 @@ cfg_t::cfg_t(exec_list *instructions) * See the DO case for additional explanation. */ assert(cur_do != NULL); - cur->add_successor(mem_ctx, cur_do); + cur->add_successor(mem_ctx, cur_do, bblock_link_physical); next = new_block(); if (inst->predicate) - cur->add_successor(mem_ctx, next); + cur->add_successor(mem_ctx, next, bblock_link_logical); set_next_block(&cur, next, ip); break; @@ -362,8 +365,11 @@ cfg_t::cfg_t(exec_list *instructions) * channels, so we may skip over the divergence point at the top of * the loop to keep the CFG as unambiguous as possible. */ - cur->add_successor(mem_ctx, inst->predicate ? cur_do : - cur_do->next()); + if (inst->predicate) { + cur->add_successor(mem_ctx, cur_do, bblock_link_logical); + } else { + cur->add_successor(mem_ctx, cur_do->next(), bblock_link_logical); + } set_next_block(&cur, cur_while, ip); @@ -403,9 +409,11 @@ cfg_t::remove_block(bblock_t *block) /* Add removed-block's successors to its predecessors' successor lists. */ foreach_list_typed (bblock_link, successor, link, &block->children) { - if (!successor->block->is_successor_of(predecessor->block)) { + if (!successor->block->is_successor_of(predecessor->block, + successor->kind)) { predecessor->block->children.push_tail(link(mem_ctx, - successor->block)); + successor->block, + successor->kind)); } } } @@ -422,9 +430,11 @@ cfg_t::remove_block(bblock_t *block) /* Add removed-block's predecessors to its successors' predecessor lists. */ foreach_list_typed (bblock_link, predecessor, link, &block->parents) { - if (!predecessor->block->is_predecessor_of(successor->block)) { + if (!predecessor->block->is_predecessor_of(successor->block, + predecessor->kind)) { successor->block->parents.push_tail(link(mem_ctx, - predecessor->block)); + predecessor->block, + predecessor->kind)); } } } @@ -487,7 +497,8 @@ cfg_t::dump(backend_shader *s) fprintf(stderr, "START B%d IDOM(none)", block->num); foreach_list_typed(bblock_link, link, link, &block->parents) { - fprintf(stderr, " <-B%d", + fprintf(stderr, " <%cB%d", + link->kind == bblock_link_logical ? '-' : '~', link->block->num); } fprintf(stderr, "\n"); @@ -495,7 +506,8 @@ cfg_t::dump(backend_shader *s) block->dump(s); fprintf(stderr, "END B%d", block->num); foreach_list_typed(bblock_link, link, link, &block->children) { - fprintf(stderr, " ->B%d", + fprintf(stderr, " %c>B%d", + link->kind == bblock_link_logical ? '-' : '~', link->block->num); } fprintf(stderr, "\n"); diff --git a/src/intel/compiler/brw_cfg.h b/src/intel/compiler/brw_cfg.h index 0c5d1268f1a..7434b190660 100644 --- a/src/intel/compiler/brw_cfg.h +++ b/src/intel/compiler/brw_cfg.h @@ -32,18 +32,42 @@ struct bblock_t; +/** + * CFG edge types. + * + * A logical edge represents a potential control flow path of the original + * scalar program, while a physical edge represents a control flow path that + * may not have existed in the original program but was introduced during + * vectorization in order to implement divergent control flow of different + * shader invocations within the same SIMD thread. + * + * All logical edges in the CFG are considered to be physical edges but not + * the other way around -- I.e. the logical CFG is a subset of the physical + * one. + */ +enum bblock_link_kind { + bblock_link_logical = 0, + bblock_link_physical +}; + struct bblock_link { #ifdef __cplusplus DECLARE_RALLOC_CXX_OPERATORS(bblock_link) - bblock_link(bblock_t *block) - : block(block) + bblock_link(bblock_t *block, enum bblock_link_kind kind) + : block(block), kind(kind) { } #endif struct exec_node link; struct bblock_t *block; + + /* Type of this CFG edge. Because bblock_link_logical also implies + * bblock_link_physical, the proper way to test for membership of edge 'l' + * in CFG kind 'k' is 'l.kind <= k'. + */ + enum bblock_link_kind kind; }; struct backend_instruction; @@ -54,9 +78,12 @@ struct bblock_t { explicit bblock_t(cfg_t *cfg); - void add_successor(void *mem_ctx, bblock_t *successor); - bool is_predecessor_of(const bblock_t *block) const; - bool is_successor_of(const bblock_t *block) const; + void add_successor(void *mem_ctx, bblock_t *successor, + enum bblock_link_kind kind); + bool is_predecessor_of(const bblock_t *block, + enum bblock_link_kind kind) const; + bool is_successor_of(const bblock_t *block, + enum bblock_link_kind kind) const; bool can_combine_with(const bblock_t *that) const; void combine_with(bblock_t *that); void dump(backend_shader *s) const; diff --git a/src/intel/compiler/brw_predicated_break.cpp b/src/intel/compiler/brw_predicated_break.cpp index e60052f3608..0dcb5e50b73 100644 --- a/src/intel/compiler/brw_predicated_break.cpp +++ b/src/intel/compiler/brw_predicated_break.cpp @@ -100,13 +100,15 @@ opt_predicated_break(backend_shader *s) if (!earlier_block->ends_with_control_flow()) { earlier_block->children.make_empty(); - earlier_block->add_successor(s->cfg->mem_ctx, jump_block); + earlier_block->add_successor(s->cfg->mem_ctx, jump_block, + bblock_link_logical); } if (!later_block->starts_with_control_flow()) { later_block->parents.make_empty(); } - jump_block->add_successor(s->cfg->mem_ctx, later_block); + jump_block->add_successor(s->cfg->mem_ctx, later_block, + bblock_link_logical); if (earlier_block->can_combine_with(jump_block)) { earlier_block->combine_with(jump_block); -- cgit v1.2.3