Re: [Mesa-dev] [PATCH 1/9] glsl: Optimize min/max expression trees
On 08/14/2014 04:33 AM, Ian Romanick wrote: On 07/29/2014 02:36 AM, Petri Latvala wrote: Add an optimization pass that drops min/max expression operands that can be proven to not contribute to the final result. The algorithm is similar to alpha-beta pruning on a minmax search, from the field of AI. This optimization pass can optimize min/max expressions where operands are min/max expressions. Such code can appear in shaders by itself, or as the result of clamp() or AMD_shader_trinary_minmax functions. This optimization pass improves the generated code for piglit's AMD_shader_trinary_minmax tests as follows: total instructions in shared programs: 75 -> 67 (-10.67%) instructions in affected programs: 60 -> 52 (-13.33%) GAINED:0 LOST: 0 All tests (max3, min3, mid3) improved. And I assume no piglit regressions? Indeed no regressions, or new successes. I wrote that in the cover letter, I should have written it also in this patch's commit message... Also... have you tried this in combination with Abdiel's related work on saturates? Tested the combination now, after some fighting with shader-db. The results are the same, except : One shader from Dungeon Defenders is hurt by shader-db metrics (26 -> 28), because of dropping of a (constant float (0.0)) operand, which was compiled to a saturate modifier. This shader compiled into the same code with or without my patches. Talked with Abdiel about the combination, recapping here: Our changes are orthogonal and not conflicting, so we can both proceed at our own paces. Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=76861 Signed-off-by: Petri Latvala --- src/glsl/Makefile.sources | 1 + src/glsl/glsl_parser_extras.cpp | 1 + src/glsl/ir_optimization.h | 1 + src/glsl/opt_minmax.cpp | 395 4 files changed, 398 insertions(+) create mode 100644 src/glsl/opt_minmax.cpp diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources index b54eae7..1ee80a3 100644 --- a/src/glsl/Makefile.sources +++ b/src/glsl/Makefile.sources @@ -95,6 +95,7 @@ LIBGLSL_FILES = \ $(GLSL_SRCDIR)/opt_flip_matrices.cpp \ $(GLSL_SRCDIR)/opt_function_inlining.cpp \ $(GLSL_SRCDIR)/opt_if_simplification.cpp \ + $(GLSL_SRCDIR)/opt_minmax.cpp \ $(GLSL_SRCDIR)/opt_noop_swizzle.cpp \ $(GLSL_SRCDIR)/opt_rebalance_tree.cpp \ $(GLSL_SRCDIR)/opt_redundant_jumps.cpp \ diff --git a/src/glsl/glsl_parser_extras.cpp b/src/glsl/glsl_parser_extras.cpp index 890123a..9f57ef3 100644 --- a/src/glsl/glsl_parser_extras.cpp +++ b/src/glsl/glsl_parser_extras.cpp @@ -1561,6 +1561,7 @@ do_common_optimization(exec_list *ir, bool linked, else progress = do_constant_variable_unlinked(ir) || progress; progress = do_constant_folding(ir) || progress; + progress = do_minmax_prune(ir) || progress; progress = do_cse(ir) || progress; progress = do_rebalance_tree(ir) || progress; progress = do_algebraic(ir, native_integers, options) || progress; diff --git a/src/glsl/ir_optimization.h b/src/glsl/ir_optimization.h index b83c225..9d22585 100644 --- a/src/glsl/ir_optimization.h +++ b/src/glsl/ir_optimization.h @@ -98,6 +98,7 @@ bool opt_flatten_nested_if_blocks(exec_list *instructions); bool do_discard_simplification(exec_list *instructions); bool lower_if_to_cond_assign(exec_list *instructions, unsigned max_depth = 0); bool do_mat_op_to_vec(exec_list *instructions); +bool do_minmax_prune(exec_list *instructions); bool do_noop_swizzle(exec_list *instructions); bool do_structure_splitting(exec_list *instructions); bool do_swizzle_swizzle(exec_list *instructions); diff --git a/src/glsl/opt_minmax.cpp b/src/glsl/opt_minmax.cpp new file mode 100644 index 000..5656059 --- /dev/null +++ b/src/glsl/opt_minmax.cpp @@ -0,0 +1,395 @@ +/* + * Copyright © 2014 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 O
Re: [Mesa-dev] [PATCH 1/9] glsl: Optimize min/max expression trees
On Tue, Jul 29, 2014 at 2:36 AM, Petri Latvala wrote: > Add an optimization pass that drops min/max expression operands that > can be proven to not contribute to the final result. The algorithm is > similar to alpha-beta pruning on a minmax search, from the field of > AI. > > This optimization pass can optimize min/max expressions where operands > are min/max expressions. Such code can appear in shaders by itself, or > as the result of clamp() or AMD_shader_trinary_minmax functions. > > This optimization pass improves the generated code for piglit's > AMD_shader_trinary_minmax tests as follows: > > total instructions in shared programs: 75 -> 67 (-10.67%) > instructions in affected programs: 60 -> 52 (-13.33%) > GAINED:0 > LOST: 0 > > All tests (max3, min3, mid3) improved. > > A full shader-db run: > > total instructions in shared programs: 4293603 -> 4293575 (-0.00%) > instructions in affected programs: 1188 -> 1160 (-2.36%) > GAINED:0 > LOST: 0 > > Improvements happen in Guacamelee and Serious Sam 3. One shader from > Dungeon Defenders is hurt by shader-db metrics (26 -> 28), because of > dropping of a (constant float (0.0)) operand, which was > compiled to a saturate modifier. > > Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=76861 > Signed-off-by: Petri Latvala > --- > src/glsl/Makefile.sources | 1 + > src/glsl/glsl_parser_extras.cpp | 1 + > src/glsl/ir_optimization.h | 1 + > src/glsl/opt_minmax.cpp | 395 > > 4 files changed, 398 insertions(+) > create mode 100644 src/glsl/opt_minmax.cpp > > diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources > index b54eae7..1ee80a3 100644 > --- a/src/glsl/Makefile.sources > +++ b/src/glsl/Makefile.sources > @@ -95,6 +95,7 @@ LIBGLSL_FILES = \ > $(GLSL_SRCDIR)/opt_flip_matrices.cpp \ > $(GLSL_SRCDIR)/opt_function_inlining.cpp \ > $(GLSL_SRCDIR)/opt_if_simplification.cpp \ > + $(GLSL_SRCDIR)/opt_minmax.cpp \ > $(GLSL_SRCDIR)/opt_noop_swizzle.cpp \ > $(GLSL_SRCDIR)/opt_rebalance_tree.cpp \ > $(GLSL_SRCDIR)/opt_redundant_jumps.cpp \ > diff --git a/src/glsl/glsl_parser_extras.cpp b/src/glsl/glsl_parser_extras.cpp > index 890123a..9f57ef3 100644 > --- a/src/glsl/glsl_parser_extras.cpp > +++ b/src/glsl/glsl_parser_extras.cpp > @@ -1561,6 +1561,7 @@ do_common_optimization(exec_list *ir, bool linked, > else >progress = do_constant_variable_unlinked(ir) || progress; > progress = do_constant_folding(ir) || progress; > + progress = do_minmax_prune(ir) || progress; > progress = do_cse(ir) || progress; > progress = do_rebalance_tree(ir) || progress; > progress = do_algebraic(ir, native_integers, options) || progress; > diff --git a/src/glsl/ir_optimization.h b/src/glsl/ir_optimization.h > index b83c225..9d22585 100644 > --- a/src/glsl/ir_optimization.h > +++ b/src/glsl/ir_optimization.h > @@ -98,6 +98,7 @@ bool opt_flatten_nested_if_blocks(exec_list *instructions); > bool do_discard_simplification(exec_list *instructions); > bool lower_if_to_cond_assign(exec_list *instructions, unsigned max_depth = > 0); > bool do_mat_op_to_vec(exec_list *instructions); > +bool do_minmax_prune(exec_list *instructions); > bool do_noop_swizzle(exec_list *instructions); > bool do_structure_splitting(exec_list *instructions); > bool do_swizzle_swizzle(exec_list *instructions); > diff --git a/src/glsl/opt_minmax.cpp b/src/glsl/opt_minmax.cpp > new file mode 100644 > index 000..5656059 > --- /dev/null > +++ b/src/glsl/opt_minmax.cpp > @@ -0,0 +1,395 @@ > +/* > + * Copyright © 2014 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 o
Re: [Mesa-dev] [PATCH 1/9] glsl: Optimize min/max expression trees
On 14.08.2014 04:33, Ian Romanick wrote: > On 07/29/2014 02:36 AM, Petri Latvala wrote: >> Add an optimization pass that drops min/max expression operands that >> can be proven to not contribute to the final result. The algorithm is >> similar to alpha-beta pruning on a minmax search, from the field of >> AI. >> >> This optimization pass can optimize min/max expressions where operands >> are min/max expressions. Such code can appear in shaders by itself, or >> as the result of clamp() or AMD_shader_trinary_minmax functions. >> >> This optimization pass improves the generated code for piglit's >> AMD_shader_trinary_minmax tests as follows: >> >> total instructions in shared programs: 75 -> 67 (-10.67%) >> instructions in affected programs: 60 -> 52 (-13.33%) >> GAINED:0 >> LOST: 0 >> >> All tests (max3, min3, mid3) improved. > > And I assume no piglit regressions? > > Also... have you tried this in combination with Abdiel's related work on > saturates? > Petteri, What is your plan on this particular pass? I have a similar patch that drops the min/max expression but using a different approach. Do you want to push for this particular optimization or do you want to take over the series? ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [PATCH 1/9] glsl: Optimize min/max expression trees
On 07/29/2014 02:36 AM, Petri Latvala wrote: > Add an optimization pass that drops min/max expression operands that > can be proven to not contribute to the final result. The algorithm is > similar to alpha-beta pruning on a minmax search, from the field of > AI. > > This optimization pass can optimize min/max expressions where operands > are min/max expressions. Such code can appear in shaders by itself, or > as the result of clamp() or AMD_shader_trinary_minmax functions. > > This optimization pass improves the generated code for piglit's > AMD_shader_trinary_minmax tests as follows: > > total instructions in shared programs: 75 -> 67 (-10.67%) > instructions in affected programs: 60 -> 52 (-13.33%) > GAINED:0 > LOST: 0 > > All tests (max3, min3, mid3) improved. And I assume no piglit regressions? Also... have you tried this in combination with Abdiel's related work on saturates? > A full shader-db run: > > total instructions in shared programs: 4293603 -> 4293575 (-0.00%) > instructions in affected programs: 1188 -> 1160 (-2.36%) > GAINED:0 > LOST: 0 > > Improvements happen in Guacamelee and Serious Sam 3. One shader from > Dungeon Defenders is hurt by shader-db metrics (26 -> 28), because of > dropping of a (constant float (0.0)) operand, which was > compiled to a saturate modifier. > > Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=76861 > Signed-off-by: Petri Latvala > --- > src/glsl/Makefile.sources | 1 + > src/glsl/glsl_parser_extras.cpp | 1 + > src/glsl/ir_optimization.h | 1 + > src/glsl/opt_minmax.cpp | 395 > > 4 files changed, 398 insertions(+) > create mode 100644 src/glsl/opt_minmax.cpp > > diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources > index b54eae7..1ee80a3 100644 > --- a/src/glsl/Makefile.sources > +++ b/src/glsl/Makefile.sources > @@ -95,6 +95,7 @@ LIBGLSL_FILES = \ > $(GLSL_SRCDIR)/opt_flip_matrices.cpp \ > $(GLSL_SRCDIR)/opt_function_inlining.cpp \ > $(GLSL_SRCDIR)/opt_if_simplification.cpp \ > + $(GLSL_SRCDIR)/opt_minmax.cpp \ > $(GLSL_SRCDIR)/opt_noop_swizzle.cpp \ > $(GLSL_SRCDIR)/opt_rebalance_tree.cpp \ > $(GLSL_SRCDIR)/opt_redundant_jumps.cpp \ > diff --git a/src/glsl/glsl_parser_extras.cpp b/src/glsl/glsl_parser_extras.cpp > index 890123a..9f57ef3 100644 > --- a/src/glsl/glsl_parser_extras.cpp > +++ b/src/glsl/glsl_parser_extras.cpp > @@ -1561,6 +1561,7 @@ do_common_optimization(exec_list *ir, bool linked, > else >progress = do_constant_variable_unlinked(ir) || progress; > progress = do_constant_folding(ir) || progress; > + progress = do_minmax_prune(ir) || progress; > progress = do_cse(ir) || progress; > progress = do_rebalance_tree(ir) || progress; > progress = do_algebraic(ir, native_integers, options) || progress; > diff --git a/src/glsl/ir_optimization.h b/src/glsl/ir_optimization.h > index b83c225..9d22585 100644 > --- a/src/glsl/ir_optimization.h > +++ b/src/glsl/ir_optimization.h > @@ -98,6 +98,7 @@ bool opt_flatten_nested_if_blocks(exec_list *instructions); > bool do_discard_simplification(exec_list *instructions); > bool lower_if_to_cond_assign(exec_list *instructions, unsigned max_depth = > 0); > bool do_mat_op_to_vec(exec_list *instructions); > +bool do_minmax_prune(exec_list *instructions); > bool do_noop_swizzle(exec_list *instructions); > bool do_structure_splitting(exec_list *instructions); > bool do_swizzle_swizzle(exec_list *instructions); > diff --git a/src/glsl/opt_minmax.cpp b/src/glsl/opt_minmax.cpp > new file mode 100644 > index 000..5656059 > --- /dev/null > +++ b/src/glsl/opt_minmax.cpp > @@ -0,0 +1,395 @@ > +/* > + * Copyright © 2014 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 CONNECT
