From c2a7eababf568ecd23377408e5f837e3bb2e9943 Mon Sep 17 00:00:00 2001 From: Francisco Jerez Date: Wed, 9 Mar 2016 23:31:05 -0800 Subject: [PATCH] intel/compiler: Move idom tree calculation and related logic into analysis object This only does half of the work. The actual representation of the idom tree is left untouched, but the computation algorithm is moved into a separate analysis result class wrapped in a BRW_ANALYSIS object, along with the intersect() and dump_domtree() auxiliary functions in order to keep things tidy. Reviewed-by: Matt Turner Part-of: --- src/intel/compiler/brw_cfg.cpp | 44 +++++++++---------- src/intel/compiler/brw_cfg.h | 38 +++++++++++++--- .../compiler/brw_fs_combine_constants.cpp | 4 +- src/intel/compiler/brw_shader.cpp | 3 +- src/intel/compiler/brw_shader.h | 2 + 5 files changed, 59 insertions(+), 32 deletions(-) diff --git a/src/intel/compiler/brw_cfg.cpp b/src/intel/compiler/brw_cfg.cpp index 0432bd290ab..b71c36ed68b 100644 --- a/src/intel/compiler/brw_cfg.cpp +++ b/src/intel/compiler/brw_cfg.cpp @@ -34,6 +34,8 @@ * blocks with successor/predecessor edges connecting them. */ +using namespace brw; + static bblock_t * pop_stack(exec_list *list) { @@ -168,7 +170,6 @@ cfg_t::cfg_t(exec_list *instructions) block_list.make_empty(); blocks = NULL; num_blocks = 0; - idom_dirty = true; cycle_count = 0; bblock_t *cur = NULL; @@ -462,7 +463,6 @@ cfg_t::remove_block(bblock_t *block) this->blocks[this->num_blocks - 1]->num = this->num_blocks - 2; this->num_blocks--; - idom_dirty = true; } bblock_t * @@ -501,8 +501,7 @@ cfg_t::make_block_array() void cfg_t::dump(backend_shader *s) { - if (idom_dirty) - calculate_idom(); + const idom_tree *idom = (s ? &s->idom_analysis.require() : NULL); foreach_block (block, this) { if (block->idom) @@ -536,19 +535,18 @@ cfg_t::dump(backend_shader *s) * (less than 1000 nodes) that this algorithm is significantly faster than * others like Lengauer-Tarjan. */ -void -cfg_t::calculate_idom() +idom_tree::idom_tree(const backend_shader *s) { - foreach_block(block, this) { + foreach_block(block, s->cfg) { block->idom = NULL; } - blocks[0]->idom = blocks[0]; + s->cfg->blocks[0]->idom = s->cfg->blocks[0]; bool changed; do { changed = false; - foreach_block(block, this) { + foreach_block(block, s->cfg) { if (block->num == 0) continue; @@ -569,12 +567,10 @@ cfg_t::calculate_idom() } } } while (changed); - - idom_dirty = false; } bblock_t * -cfg_t::intersect(bblock_t *b1, bblock_t *b2) +idom_tree::intersect(bblock_t *b1, bblock_t *b2) const { /* Note, the comparisons here are the opposite of what the paper says * because we index blocks from beginning -> end (i.e. reverse post-order) @@ -591,26 +587,26 @@ cfg_t::intersect(bblock_t *b1, bblock_t *b2) } void -cfg_t::dump_cfg() +idom_tree::dump(const backend_shader *s) const { - printf("digraph CFG {\n"); - for (int b = 0; b < num_blocks; b++) { - bblock_t *block = this->blocks[b]; - - foreach_list_typed_safe (bblock_link, child, link, &block->children) { - printf("\t%d -> %d\n", b, child->block->num); + printf("digraph DominanceTree {\n"); + foreach_block(block, s->cfg) { + if (block->idom) { + printf("\t%d -> %d\n", block->idom->num, block->num); } } printf("}\n"); } void -cfg_t::dump_domtree() +cfg_t::dump_cfg() { - printf("digraph DominanceTree {\n"); - foreach_block(block, this) { - if (block->idom) { - printf("\t%d -> %d\n", block->idom->num, block->num); + printf("digraph CFG {\n"); + for (int b = 0; b < num_blocks; b++) { + bblock_t *block = this->blocks[b]; + + foreach_list_typed_safe (bblock_link, child, link, &block->children) { + printf("\t%d -> %d\n", b, child->block->num); } } printf("}\n"); diff --git a/src/intel/compiler/brw_cfg.h b/src/intel/compiler/brw_cfg.h index 851674a69fe..21431cd46d0 100644 --- a/src/intel/compiler/brw_cfg.h +++ b/src/intel/compiler/brw_cfg.h @@ -29,6 +29,9 @@ #define BRW_CFG_H #include "brw_ir.h" +#ifdef __cplusplus +#include "brw_ir_analysis.h" +#endif struct bblock_t; @@ -311,12 +314,9 @@ struct cfg_t { bblock_t *new_block(); void set_next_block(bblock_t **cur, bblock_t *block, int ip); void make_block_array(); - void calculate_idom(); - static bblock_t *intersect(bblock_t *b1, bblock_t *b2); void dump(backend_shader *s); void dump_cfg(); - void dump_domtree(); #endif void *mem_ctx; @@ -325,8 +325,6 @@ struct cfg_t { struct bblock_t **blocks; int num_blocks; - bool idom_dirty; - unsigned cycle_count; }; @@ -382,4 +380,34 @@ struct cfg_t { !__scan_inst->is_head_sentinel(); \ __scan_inst = (__type *)__scan_inst->prev) +#ifdef __cplusplus +namespace brw { + /** + * Immediate dominator tree analysis of a shader. + */ + struct idom_tree { + idom_tree(const backend_shader *s); + + bool + validate(const backend_shader *) const + { + /* FINISHME */ + return true; + } + + analysis_dependency_class + dependency_class() const + { + return DEPENDENCY_BLOCKS; + } + + bblock_t * + intersect(bblock_t *b1, bblock_t *b2) const; + + void + dump(const backend_shader *s) const; + }; +} +#endif + #endif /* BRW_CFG_H */ diff --git a/src/intel/compiler/brw_fs_combine_constants.cpp b/src/intel/compiler/brw_fs_combine_constants.cpp index ec48a74ba0b..e07d657db7a 100644 --- a/src/intel/compiler/brw_fs_combine_constants.cpp +++ b/src/intel/compiler/brw_fs_combine_constants.cpp @@ -360,7 +360,7 @@ fs_visitor::opt_combine_constants() table.len = 0; table.imm = ralloc_array(const_ctx, struct imm, table.size); - cfg->calculate_idom(); + const brw::idom_tree &idom = idom_analysis.require(); unsigned ip = -1; /* Make a pass through all instructions and count the number of times each @@ -395,7 +395,7 @@ fs_visitor::opt_combine_constants() struct imm *imm = find_imm(&table, data, size); if (imm) { - bblock_t *intersection = cfg_t::intersect(block, imm->block); + bblock_t *intersection = idom.intersect(block, imm->block); if (intersection != imm->block) imm->inst = NULL; imm->block = intersection; diff --git a/src/intel/compiler/brw_shader.cpp b/src/intel/compiler/brw_shader.cpp index ba95232e1ea..7752f33a132 100644 --- a/src/intel/compiler/brw_shader.cpp +++ b/src/intel/compiler/brw_shader.cpp @@ -703,7 +703,7 @@ backend_shader::backend_shader(const struct brw_compiler *compiler, nir(shader), stage_prog_data(stage_prog_data), mem_ctx(mem_ctx), - cfg(NULL), + cfg(NULL), idom_analysis(this), stage(shader->info.stage) { debug_enabled = INTEL_DEBUG & intel_debug_flag_for_shader_stage(stage); @@ -1248,6 +1248,7 @@ backend_shader::calculate_cfg() void backend_shader::invalidate_analysis(brw::analysis_dependency_class c) { + idom_analysis.invalidate(c); } extern "C" const unsigned * diff --git a/src/intel/compiler/brw_shader.h b/src/intel/compiler/brw_shader.h index 14230a10643..48f7cf65ba3 100644 --- a/src/intel/compiler/brw_shader.h +++ b/src/intel/compiler/brw_shader.h @@ -69,6 +69,8 @@ public: exec_list instructions; cfg_t *cfg; + BRW_ANALYSIS(idom_analysis, brw::idom_tree, + const backend_shader *) idom_analysis; gl_shader_stage stage; bool debug_enabled; -- 2.30.2