[Mesa-dev] [PATCH 1/4] i965/vec4: Add basic common subexpression elimination.

[Kenneth Graunke]

On Monday, June 30, 2014 12:06:56 PM Matt Turner wrote:
> On Mon, Jun 30, 2014 at 11:49 AM, Ian Romanick <idr at freedesktop.org> wrote:
> > On 06/25/2014 02:12 PM, Matt Turner wrote:
> >> From: Kenneth Graunke <kenneth at whitecape.org>
> >> 
> >> [mattst88]: Modified to perform CSE on instructions with
> >> 
> >>             the same writemask. Offered no improvement before.
> >> 
> >> total instructions in shared programs: 1995633 -> 1995185 (-0.02%)
> >> instructions in affected programs:     14410 -> 13962 (-3.11%)
> >> 
> >> Reviewed-by: Matt Turner <mattst88 at gmail.com>
> >> Signed-off-by: Kenneth Graunke <kenneth at whitecape.org>
> >> ---
> >> 
> >>  src/mesa/drivers/dri/i965/Makefile.sources |   1 +
> >>  src/mesa/drivers/dri/i965/brw_vec4.cpp     |   1 +
> >>  src/mesa/drivers/dri/i965/brw_vec4.h       |   2 +
> >>  src/mesa/drivers/dri/i965/brw_vec4_cse.cpp | 237
> >>  +++++++++++++++++++++++++++++ 4 files changed, 241 insertions(+)
> >>  create mode 100644 src/mesa/drivers/dri/i965/brw_vec4_cse.cpp
> >> 
> >> diff --git a/src/mesa/drivers/dri/i965/Makefile.sources
> >> b/src/mesa/drivers/dri/i965/Makefile.sources index 2570059..8f1d272
> >> 100644
> >> --- a/src/mesa/drivers/dri/i965/Makefile.sources
> >> +++ b/src/mesa/drivers/dri/i965/Makefile.sources
> >> @@ -102,6 +102,7 @@ i965_FILES = \
> >> 
> >>       brw_util.c \
> >>       brw_vec4.cpp \
> >>       brw_vec4_copy_propagation.cpp \
> >> 
> >> +     brw_vec4_cse.cpp \
> >> 
> >>       brw_vec4_generator.cpp \
> >>       brw_vec4_gs.c \
> >>       brw_vec4_gs_visitor.cpp \
> >> 
> >> diff --git a/src/mesa/drivers/dri/i965/brw_vec4.cpp
> >> b/src/mesa/drivers/dri/i965/brw_vec4.cpp index 24903f9..0d57399 100644
> >> --- a/src/mesa/drivers/dri/i965/brw_vec4.cpp
> >> +++ b/src/mesa/drivers/dri/i965/brw_vec4.cpp
> >> @@ -1747,6 +1747,7 @@ vec4_visitor::run()
> >> 
> >>        progress = dead_control_flow_eliminate(this) || progress;
> >>        progress = opt_copy_propagation() || progress;
> >>        progress = opt_algebraic() || progress;
> >> 
> >> +      progress = opt_cse() || progress;
> >> 
> >>        progress = opt_register_coalesce() || progress;
> >>     
> >>     } while (progress);
> >> 
> >> diff --git a/src/mesa/drivers/dri/i965/brw_vec4.h
> >> b/src/mesa/drivers/dri/i965/brw_vec4.h index 366198c..4a8eabb 100644
> >> --- a/src/mesa/drivers/dri/i965/brw_vec4.h
> >> +++ b/src/mesa/drivers/dri/i965/brw_vec4.h
> >> 
> >> @@ -426,6 +426,8 @@ public:
> >>     bool dead_code_eliminate();
> >>     bool virtual_grf_interferes(int a, int b);
> >>     bool opt_copy_propagation();
> >> 
> >> +   bool opt_cse_local(bblock_t *, exec_list *);
> >> +   bool opt_cse();
> >> 
> >>     bool opt_algebraic();
> >>     bool opt_register_coalesce();
> >>     void opt_set_dependency_control();
> >> 
> >> diff --git a/src/mesa/drivers/dri/i965/brw_vec4_cse.cpp
> >> b/src/mesa/drivers/dri/i965/brw_vec4_cse.cpp new file mode 100644
> >> index 0000000..33c7430
> >> --- /dev/null
> >> +++ b/src/mesa/drivers/dri/i965/brw_vec4_cse.cpp
> >> @@ -0,0 +1,237 @@
> >> +/*
> >> + * Copyright © 2012, 2013, 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.
> >> + */
> >> +
> >> +#include "brw_vec4.h"
> >> +#include "brw_cfg.h"
> >> +
> >> +using namespace brw;
> >> +
> >> +/** @file brw_vec4_cse.cpp
> >> + *
> >> + * Support for local common subexpression elimination.
> >> + *
> >> + * See Muchnick's Advanced Compiler Design and Implementation, section
> >> + * 13.1 (p378).
> >> + */
> >> +
> >> +namespace {
> >> +struct aeb_entry : public exec_node {
> >> +   /** The instruction that generates the expression value. */
> >> +   vec4_instruction *generator;
> >> +
> >> +   /** The temporary where the value is stored. */
> >> +   src_reg tmp;
> >> +};
> >> +}
> >> +
> >> +static bool
> >> +is_expression(const vec4_instruction *const inst)
> > 
> > is_expression seems like a weird name for this.  It's not obvious to a
> > noob what this is doing.
> 
> Yeah, sort of is. I'd like to change this one and the fs CSE
> implementation in sync.
> 
> Not sure what else to call it. can_cse_inst, something else?

I suppose is_cse_candidate() might be clearer than is_expression(), but it 
doesn't seem that strange to me.  CSE eliminates expressions.  It doesn't work 
on other instructions like flow control, or statements such as scratch writes, 
or raw MOVs (which just move data between locations, but don't compute new 
values).

I suppose is_expression could be a more general concept, rather than 
"expression" defined in a way that makes sense for the CSE pass.  It is local 
to the file, though...*shrug*.

is_cse_candidate would be my suggestion if you want to rename it.

--Ken
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20140630/f6cf2f59/attachment.sig>