From de7c3fe31a7b88a5392dceee3b13b45ed78cdeae Mon Sep 17 00:00:00 2001 From: Ian Romanick Date: Fri, 27 Aug 2010 13:59:49 -0700 Subject: [PATCH] glsl2: Add module to perform simple loop unrolling --- src/glsl/Makefile | 1 + src/glsl/Makefile.am | 3 +- src/glsl/glsl_parser_extras.cpp | 1 + src/glsl/loop_analysis.h | 14 +++++ src/glsl/loop_controls.cpp | 4 +- src/glsl/loop_unroll.cpp | 100 ++++++++++++++++++++++++++++++++ src/glsl/main.cpp | 3 +- 7 files changed, 123 insertions(+), 3 deletions(-) create mode 100644 src/glsl/loop_unroll.cpp diff --git a/src/glsl/Makefile b/src/glsl/Makefile index ed1453b14b5..eb621126748 100644 --- a/src/glsl/Makefile +++ b/src/glsl/Makefile @@ -74,6 +74,7 @@ CXX_SOURCES = \ link_functions.cpp \ loop_analysis.cpp \ loop_controls.cpp \ + loop_unroll.cpp \ s_expression.cpp LIBS = \ diff --git a/src/glsl/Makefile.am b/src/glsl/Makefile.am index 0811ffbff1f..7ff0cb05b58 100644 --- a/src/glsl/Makefile.am +++ b/src/glsl/Makefile.am @@ -64,7 +64,8 @@ glsl_SOURCES = \ ir_vec_index_to_swizzle.cpp \ linker.cpp \ loop_analysis.cpp \ - loop_controls.cpp + loop_controls.cpp \ + loop_unroll.cpp BUILT_SOURCES = glsl_parser.h glsl_parser.cpp glsl_lexer.cpp CLEANFILES = $(BUILT_SOURCES) diff --git a/src/glsl/glsl_parser_extras.cpp b/src/glsl/glsl_parser_extras.cpp index 2d045ac9c7a..390d1f0af05 100644 --- a/src/glsl/glsl_parser_extras.cpp +++ b/src/glsl/glsl_parser_extras.cpp @@ -742,6 +742,7 @@ do_common_optimization(exec_list *ir, bool linked) loop_state *ls = analyze_loop_variables(ir); progress = set_loop_controls(ir, ls) || progress; + progress = unroll_loops(ir, ls) || progress; delete ls; return progress; diff --git a/src/glsl/loop_analysis.h b/src/glsl/loop_analysis.h index f5c5a04be81..893dd46db04 100644 --- a/src/glsl/loop_analysis.h +++ b/src/glsl/loop_analysis.h @@ -56,6 +56,10 @@ extern bool set_loop_controls(exec_list *instructions, loop_state *ls); +extern bool +unroll_loops(exec_list *instructions, loop_state *ls); + + /** * Tracking for all variables used in a loop */ @@ -104,6 +108,15 @@ public: */ hash_table *var_hash; + /** + * Maximum number of loop iterations. + * + * If this value is negative, then the loop may be infinite. This actually + * means that analysis was unable to determine an upper bound on the number + * of loop iterations. + */ + int max_iterations; + /** * Number of ir_loop_jump instructions that operate on this loop */ @@ -111,6 +124,7 @@ public: loop_variable_state() { + this->max_iterations = -1; this->num_loop_jumps = 0; this->var_hash = hash_table_ctor(0, hash_table_pointer_hash, hash_table_pointer_compare); diff --git a/src/glsl/loop_controls.cpp b/src/glsl/loop_controls.cpp index f2e1ecb904d..d6a1e33fdb5 100644 --- a/src/glsl/loop_controls.cpp +++ b/src/glsl/loop_controls.cpp @@ -182,7 +182,7 @@ loop_control_visitor::visit_leave(ir_loop *ir) * i is a loop induction variable, c is a constant, and < is any relative * operator. */ - int max_iterations = INT_MAX; + int max_iterations = (ls->max_iterations < 0) ? INT_MAX : ls->max_iterations; foreach_list(node, &ls->terminators) { loop_terminator *t = (loop_terminator *) node; ir_if *if_stmt = t->ir; @@ -276,6 +276,8 @@ loop_control_visitor::visit_leave(ir_loop *ir) */ if (max_iterations == 0) ir->remove(); + else + ls->max_iterations = max_iterations; return visit_continue; } diff --git a/src/glsl/loop_unroll.cpp b/src/glsl/loop_unroll.cpp new file mode 100644 index 00000000000..e204251e9cc --- /dev/null +++ b/src/glsl/loop_unroll.cpp @@ -0,0 +1,100 @@ +/* + * 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. + */ + +#include "glsl_types.h" +#include "loop_analysis.h" +#include "ir_hierarchical_visitor.h" + +class loop_unroll_visitor : public ir_hierarchical_visitor { +public: + loop_unroll_visitor(loop_state *state) + { + this->state = state; + this->progress = false; + } + + virtual ir_visitor_status visit_leave(ir_loop *ir); + + loop_state *state; + + bool progress; +}; + + +ir_visitor_status +loop_unroll_visitor::visit_leave(ir_loop *ir) +{ + loop_variable_state *const ls = this->state->get(ir); + + /* If we've entered a loop that hasn't been analyzed, something really, + * really bad has happened. + */ + if (ls == NULL) { + assert(ls != NULL); + return visit_continue; + } + + /* Don't try to unroll loops where the number of iterations is not known + * at compile-time. + */ + if (ls->max_iterations < 0) + return visit_continue; + + /* Don't try to unroll loops that have zillions of iterations either. + */ + if (ls->max_iterations > 32) + return visit_continue; + + if (ls->num_loop_jumps > 0) + return visit_continue; + + void *const mem_ctx = talloc_parent(ir); + + for (int i = 0; i < ls->max_iterations; i++) { + exec_list copy_list; + + copy_list.make_empty(); + clone_ir_list(mem_ctx, ©_list, &ir->body_instructions); + + ir->insert_before(©_list); + } + + /* The loop has been replaced by the unrolled copies. Remove the original + * loop from the IR sequence. + */ + ir->remove(); + + this->progress = true; + return visit_continue; +} + + +bool +unroll_loops(exec_list *instructions, loop_state *ls) +{ + loop_unroll_visitor v(ls); + + v.run(instructions); + + return v.progress; +} diff --git a/src/glsl/main.cpp b/src/glsl/main.cpp index 411bc08983d..30f11a5a440 100644 --- a/src/glsl/main.cpp +++ b/src/glsl/main.cpp @@ -177,7 +177,8 @@ compile_shader(struct gl_shader *shader) progress = do_swizzle_swizzle(shader->ir) || progress; loop_state *ls = analyze_loop_variables(shader->ir); - set_loop_controls(shader->ir, ls); + progress = set_loop_controls(shader->ir, ls) || progress; + progress = unroll_loops(shader->ir, ls) || progress; delete ls; } while (progress); -- 2.30.2