From 784695442c415cf0be882434a25671ecfb635d34 Mon Sep 17 00:00:00 2001 From: Eric Anholt Date: Fri, 30 Jul 2010 17:04:49 -0700 Subject: [PATCH] glsl2: Add new tree grafting optimization pass. --- src/glsl/Makefile | 1 + src/glsl/ir_optimization.h | 1 + src/glsl/ir_tree_grafting.cpp | 356 ++++++++++++++++++++++++++++++++ src/glsl/linker.cpp | 1 + src/glsl/main.cpp | 1 + src/mesa/program/ir_to_mesa.cpp | 1 + 6 files changed, 361 insertions(+) create mode 100644 src/glsl/ir_tree_grafting.cpp diff --git a/src/glsl/Makefile b/src/glsl/Makefile index aa1922f3bec..0254fec756b 100644 --- a/src/glsl/Makefile +++ b/src/glsl/Makefile @@ -56,6 +56,7 @@ CXX_SOURCES = \ ir_print_visitor.cpp \ ir_reader.cpp \ ir_swizzle_swizzle.cpp \ + ir_tree_grafting.cpp \ ir_validate.cpp \ ir_variable.cpp \ ir_variable_refcount.cpp \ diff --git a/src/glsl/ir_optimization.h b/src/glsl/ir_optimization.h index 5dbb025d357..55ec3271936 100644 --- a/src/glsl/ir_optimization.h +++ b/src/glsl/ir_optimization.h @@ -44,5 +44,6 @@ bool do_if_to_cond_assign(exec_list *instructions); bool do_mat_op_to_vec(exec_list *instructions); bool do_mod_to_fract(exec_list *instructions); bool do_swizzle_swizzle(exec_list *instructions); +bool do_tree_grafting(exec_list *instructions); bool do_vec_index_to_cond_assign(exec_list *instructions); bool do_vec_index_to_swizzle(exec_list *instructions); diff --git a/src/glsl/ir_tree_grafting.cpp b/src/glsl/ir_tree_grafting.cpp new file mode 100644 index 00000000000..6f62de758b2 --- /dev/null +++ b/src/glsl/ir_tree_grafting.cpp @@ -0,0 +1,356 @@ +/* + * Copyright © 2010 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +/** + * \file ir_tree_grafting.cpp + * + * Takes assignments to variables that are dereferenced only once and + * pastes the RHS expression into where the variable is dereferenced. + * + * In the process of various operations like function inlining and + * tertiary op handling, we'll end up with our expression trees having + * been chopped up into a series of assignments of short expressions + * to temps. Other passes like ir_algebraic.cpp would prefer to see + * the deepest expression trees they can to try to optimize them. + * + * This is a lot like copy propagaton. In comparison, copy + * propagation only acts on plain copies, not arbitrary expressions on + * the RHS. Generally, we wouldn't want to go pasting some + * complicated expression everywhere it got used, though, so we don't + * handle expressions in that pass. + * + * The hard part is making sure we don't move an expression across + * some other assignments that would change the value of the + * expression. So we split this into two passes: First, find the + * variables in our scope which are written to once and read once, and + * then go through basic blocks seeing if we find an opportunity to + * move those expressions safely. + */ + +#include "ir.h" +#include "ir_visitor.h" +#include "ir_variable_refcount.h" +#include "ir_basic_block.h" +#include "ir_optimization.h" +#include "glsl_types.h" + +static bool debug = false; + +class ir_tree_grafting_visitor : public ir_hierarchical_visitor { +public: + ir_tree_grafting_visitor(ir_assignment *graft_assign, + ir_variable *graft_var) + { + this->progress = false; + this->graft_assign = graft_assign; + this->graft_var = graft_var; + } + + virtual ir_visitor_status visit_leave(class ir_assignment *); + virtual ir_visitor_status visit_enter(class ir_call *); + virtual ir_visitor_status visit_enter(class ir_expression *); + virtual ir_visitor_status visit_enter(class ir_function *); + virtual ir_visitor_status visit_enter(class ir_function_signature *); + virtual ir_visitor_status visit_enter(class ir_if *); + virtual ir_visitor_status visit_enter(class ir_loop *); + virtual ir_visitor_status visit_enter(class ir_swizzle *); + virtual ir_visitor_status visit_enter(class ir_texture *); + + bool do_graft(ir_rvalue **rvalue); + + bool progress; + ir_variable *graft_var; + ir_assignment *graft_assign; +}; + +struct find_deref_info { + ir_variable *var; + bool found; +}; + +void +dereferences_variable_callback(ir_instruction *ir, void *data) +{ + struct find_deref_info *info = (struct find_deref_info *)data; + + if (ir == info->var) + info->found = true; +} + +static bool +dereferences_variable(ir_instruction *ir, ir_variable *var) +{ + struct find_deref_info info; + + info.var = var; + info.found = false; + + visit_tree(ir, dereferences_variable_callback, &info); + + return info.found; +} + +bool +ir_tree_grafting_visitor::do_graft(ir_rvalue **rvalue) +{ + if (!*rvalue) + return false; + + ir_dereference_variable *deref = (*rvalue)->as_dereference_variable(); + + if (!deref || deref->var != this->graft_var) + return false; + + if (debug) { + printf("GRAFTING:\n"); + this->graft_assign->rhs->print(); + printf("\n"); + printf("TO:\n"); + (*rvalue)->print(); + printf("\n"); + } + + this->graft_assign->remove(); + *rvalue = this->graft_assign->rhs; + + this->progress = true; + return true; +} + +ir_visitor_status +ir_tree_grafting_visitor::visit_enter(ir_loop *ir) +{ + (void)ir; + /* Do not traverse into the body of the loop since that is a + * different basic block. + */ + return visit_stop; +} + +ir_visitor_status +ir_tree_grafting_visitor::visit_leave(ir_assignment *ir) +{ + if (do_graft(&ir->rhs) || + do_graft(&ir->condition)) + return visit_stop; + + /* If this assignment updates a variable used in the assignment + * we're trying to graft, then we're done. + */ + if (dereferences_variable(this->graft_assign->rhs, + ir->lhs->variable_referenced())) { + if (debug) { + printf("graft killed by: "); + ir->print(); + printf("\n"); + } + return visit_stop; + } + + return visit_continue; +} + +ir_visitor_status +ir_tree_grafting_visitor::visit_enter(ir_function *ir) +{ + (void) ir; + return visit_continue_with_parent; +} + +ir_visitor_status +ir_tree_grafting_visitor::visit_enter(ir_function_signature *ir) +{ + (void)ir; + return visit_continue_with_parent; +} + +ir_visitor_status +ir_tree_grafting_visitor::visit_enter(ir_call *ir) +{ + /* Reminder: iterating ir_call iterates its parameters. */ + foreach_iter(exec_list_iterator, iter, *ir) { + ir_rvalue *ir = (ir_rvalue *)iter.get(); + ir_rvalue *new_ir = ir; + + if (do_graft(&new_ir)) { + ir->replace_with(new_ir); + return visit_stop; + } + } + + return visit_continue; +} + +ir_visitor_status +ir_tree_grafting_visitor::visit_enter(ir_expression *ir) +{ + for (unsigned int i = 0; i < ir->get_num_operands(); i++) { + if (do_graft(&ir->operands[i])) + return visit_stop; + } + + return visit_continue; +} + +ir_visitor_status +ir_tree_grafting_visitor::visit_enter(ir_if *ir) +{ + if (do_graft(&ir->condition)) + return visit_stop; + + /* Do not traverse into the body of the if-statement since that is a + * different basic block. + */ + return visit_continue_with_parent; +} + +ir_visitor_status +ir_tree_grafting_visitor::visit_enter(ir_swizzle *ir) +{ + if (do_graft(&ir->val)) + return visit_stop; + + return visit_continue; +} + +ir_visitor_status +ir_tree_grafting_visitor::visit_enter(ir_texture *ir) +{ + if (do_graft(&ir->coordinate) || + do_graft(&ir->projector) || + do_graft(&ir->shadow_comparitor)) + return visit_stop; + + switch (ir->op) { + case ir_tex: + break; + case ir_txb: + if (do_graft(&ir->lod_info.bias)) + return visit_stop; + break; + case ir_txf: + case ir_txl: + if (do_graft(&ir->lod_info.lod)) + return visit_stop; + break; + case ir_txd: + if (do_graft(&ir->lod_info.grad.dPdx) || + do_graft(&ir->lod_info.grad.dPdy)) + return visit_stop; + break; + } + + return visit_continue; +} + +struct tree_grafting_info { + ir_variable_refcount_visitor *refs; + bool progress; +}; + +static bool +try_tree_grafting(ir_assignment *start, + ir_variable *lhs_var, + ir_instruction *bb_last) +{ + ir_tree_grafting_visitor v(start, lhs_var); + + if (debug) { + printf("trying to graft: "); + lhs_var->print(); + printf("\n"); + } + + for (ir_instruction *ir = (ir_instruction *)start->next; + ir != bb_last->next; + ir = (ir_instruction *)ir->next) { + + if (debug) { + printf("- "); + ir->print(); + printf("\n"); + } + + ir_visitor_status s = ir->accept(&v); + if (s == visit_stop) + return v.progress; + } + + return false; +} + +static void +tree_grafting_basic_block(ir_instruction *bb_first, + ir_instruction *bb_last, + void *data) +{ + struct tree_grafting_info *info = (struct tree_grafting_info *)data; + ir_instruction *ir, *next; + + for (ir = bb_first, next = (ir_instruction *)ir->next; + ir != bb_last->next; + ir = next, next = (ir_instruction *)ir->next) { + ir_assignment *assign = ir->as_assignment(); + + if (!assign) + continue; + + ir_variable *lhs_var = assign->lhs->whole_variable_referenced(); + if (!lhs_var) + continue; + + struct variable_entry *entry = info->refs->get_variable_entry(lhs_var); + + if (!entry->declaration || + entry->assigned_count != 1 || + entry->referenced_count != 2) + continue; + + assert(assign == entry->assign); + + /* Found a possibly graftable assignment. Now, walk through the + * rest of the BB seeing if the deref is here, and if nothing interfered with + * pasting its expression's values in between. + */ + info->progress |= try_tree_grafting(assign, lhs_var, bb_last); + } +} + +/** + * Does a copy propagation pass on the code present in the instruction stream. + */ +bool +do_tree_grafting(exec_list *instructions) +{ + ir_variable_refcount_visitor refs; + struct tree_grafting_info info; + + info.progress = false; + info.refs = &refs; + + visit_list_elements(info.refs, instructions); + + call_for_basic_blocks(instructions, tree_grafting_basic_block, &info); + + return info.progress; +} diff --git a/src/glsl/linker.cpp b/src/glsl/linker.cpp index e9daad28ecf..9b47e4788fc 100644 --- a/src/glsl/linker.cpp +++ b/src/glsl/linker.cpp @@ -1286,6 +1286,7 @@ link_shaders(struct gl_shader_program *prog) progress = do_copy_propagation(ir) || progress; progress = do_dead_code_local(ir) || progress; progress = do_dead_code(ir) || progress; + progress = do_tree_grafting(ir) || progress; progress = do_constant_variable_unlinked(ir) || progress; progress = do_constant_folding(ir) || progress; progress = do_if_return(ir) || progress; diff --git a/src/glsl/main.cpp b/src/glsl/main.cpp index 08b133f124e..d557dcc4933 100644 --- a/src/glsl/main.cpp +++ b/src/glsl/main.cpp @@ -163,6 +163,7 @@ compile_shader(struct gl_shader *shader) progress = do_copy_propagation(shader->ir) || progress; progress = do_dead_code_local(shader->ir) || progress; progress = do_dead_code_unlinked(shader->ir) || progress; + progress = do_tree_grafting(shader->ir) || progress; progress = do_constant_variable_unlinked(shader->ir) || progress; progress = do_constant_folding(shader->ir) || progress; progress = do_algebraic(shader->ir) || progress; diff --git a/src/mesa/program/ir_to_mesa.cpp b/src/mesa/program/ir_to_mesa.cpp index e62395a3b90..9274723eb73 100644 --- a/src/mesa/program/ir_to_mesa.cpp +++ b/src/mesa/program/ir_to_mesa.cpp @@ -2485,6 +2485,7 @@ _mesa_glsl_compile_shader(GLcontext *ctx, struct gl_shader *shader) progress = do_copy_propagation(shader->ir) || progress; progress = do_dead_code_local(shader->ir) || progress; progress = do_dead_code_unlinked(shader->ir) || progress; + progress = do_tree_grafting(shader->ir) || progress; progress = do_constant_variable_unlinked(shader->ir) || progress; progress = do_constant_folding(shader->ir) || progress; progress = do_algebraic(shader->ir) || progress; -- 2.30.2