[Mesa-dev] [PATCH 09/15] i965/fs: New peephole optimization to generate SEL.
Paul Berry
stereotype441 at gmail.com
Wed Oct 30 18:45:50 CET 2013
On 30 October 2013 10:23, Paul Berry <stereotype441 at gmail.com> wrote:
> On 30 October 2013 10:10, Matt Turner <mattst88 at gmail.com> wrote:
>
>> On Wed, Oct 30, 2013 at 9:30 AM, Paul Berry <stereotype441 at gmail.com>
>> wrote:
>> > On 28 October 2013 11:31, Matt Turner <mattst88 at gmail.com> wrote:
>> >>
>> >> fs_visitor::try_replace_with_sel optimizes only if statements whose
>> >> "then" and "else" bodies contain a single MOV instruction. It also did
>> >> could not handle constant arguments, since they cause an extra MOV
>> >
>> >
>> > s/did could not/could not/
>> >
>> >>
>> >> immediate to be generated (since we haven't run constant propagation,
>> >> there are more than the single MOV).
>> >>
>> >> This peephole fixes both of these and operates as a normal optimization
>> >> pass.
>> >>
>> >> fs_visitor::try_replace_with_sel is still arguably necessary, since it
>> >> runs before pull constant loads are lowered.
>> >>
>> >> total instructions in shared programs: 1547180 -> 1545254 (-0.12%)
>> >> instructions in affected programs: 96585 -> 94659 (-1.99%)
>> >> ---
>> >> src/mesa/drivers/dri/i965/Makefile.sources | 1 +
>> >> src/mesa/drivers/dri/i965/brw_fs.cpp | 1 +
>> >> src/mesa/drivers/dri/i965/brw_fs.h | 1 +
>> >> src/mesa/drivers/dri/i965/brw_fs_sel_peephole.cpp | 245
>> >> ++++++++++++++++++++++
>> >> 4 files changed, 248 insertions(+)
>> >> create mode 100644 src/mesa/drivers/dri/i965/brw_fs_sel_peephole.cpp
>> >>
>> >> diff --git a/src/mesa/drivers/dri/i965/Makefile.sources
>> >> b/src/mesa/drivers/dri/i965/Makefile.sources
>> >> index c4d689e..5ddb421 100644
>> >> --- a/src/mesa/drivers/dri/i965/Makefile.sources
>> >> +++ b/src/mesa/drivers/dri/i965/Makefile.sources
>> >> @@ -59,6 +59,7 @@ i965_FILES = \
>> >> brw_fs_fp.cpp \
>> >> brw_fs_generator.cpp \
>> >> brw_fs_live_variables.cpp \
>> >> + brw_fs_sel_peephole.cpp \
>> >> brw_fs_reg_allocate.cpp \
>> >> brw_fs_vector_splitting.cpp \
>> >> brw_fs_visitor.cpp \
>> >> diff --git a/src/mesa/drivers/dri/i965/brw_fs.cpp
>> >> b/src/mesa/drivers/dri/i965/brw_fs.cpp
>> >> index 28d369a..d3d2e44 100644
>> >> --- a/src/mesa/drivers/dri/i965/brw_fs.cpp
>> >> +++ b/src/mesa/drivers/dri/i965/brw_fs.cpp
>> >> @@ -3131,6 +3131,7 @@ fs_visitor::run()
>> >> progress = opt_algebraic() || progress;
>> >> progress = opt_cse() || progress;
>> >> progress = opt_copy_propagate() || progress;
>> >> + progress = opt_peephole_sel() || progress;
>> >> progress = dead_code_eliminate() || progress;
>> >> progress = dead_code_eliminate_local() || progress;
>> >> progress = register_coalesce() || progress;
>> >> diff --git a/src/mesa/drivers/dri/i965/brw_fs.h
>> >> b/src/mesa/drivers/dri/i965/brw_fs.h
>> >> index dff6ec1..a67ef86 100644
>> >> --- a/src/mesa/drivers/dri/i965/brw_fs.h
>> >> +++ b/src/mesa/drivers/dri/i965/brw_fs.h
>> >> @@ -361,6 +361,7 @@ public:
>> >> bool try_emit_saturate(ir_expression *ir);
>> >> bool try_emit_mad(ir_expression *ir, int mul_arg);
>> >> void try_replace_with_sel();
>> >> + bool opt_peephole_sel();
>> >> void emit_bool_to_cond_code(ir_rvalue *condition);
>> >> void emit_if_gen6(ir_if *ir);
>> >> void emit_unspill(fs_inst *inst, fs_reg reg, uint32_t spill_offset,
>> >> diff --git a/src/mesa/drivers/dri/i965/brw_fs_sel_peephole.cpp
>> >> b/src/mesa/drivers/dri/i965/brw_fs_sel_peephole.cpp
>> >> new file mode 100644
>> >> index 0000000..11c3677
>> >> --- /dev/null
>> >> +++ b/src/mesa/drivers/dri/i965/brw_fs_sel_peephole.cpp
>> >> @@ -0,0 +1,245 @@
>> >> +/*
>> >> + * Copyright © 2013 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_fs.h"
>> >> +#include "brw_cfg.h"
>> >> +
>> >> +/** @file brw_fs_sel_peephole.cpp
>> >> + *
>> >> + * This file contains the opt_peephole_sel() optimization pass that
>> >> replaces
>> >> + * MOV instructions to the same destination in the "then" and "else"
>> >> bodies of
>> >> + * an if statement with SEL instructions.
>> >> + */
>> >> +
>> >> +#define MAX_MOVS 8 /**< The maximum number of MOVs to attempt to
>> match.
>> >> */
>> >
>> >
>> > Why 8 and not 4? Just general caution? Or have you found shaders that
>> > require 8?
>>
>> Four seems to be pretty typical, so I picked the next power of two in
>> the hopes that it would handle almost anything possible in a single
>> pass.
>>
>> >>
>> >> +
>> >> +/**
>> >> + * Scans backwards from an ENDIF counting MOV instructions with common
>> >> + * destinations inside the "then" and "else" blocks of the if
>> statement.
>> >> + *
>> >> + * A pointer to the fs_inst* for ENDIF is passed as the <match>
>> argument.
>> >> The
>> >> + * function stores pointers to the MOV instructions in the <then_mov>
>> and
>> >> + * <else_mov> arrays. If the function is successful, the <match>
>> points
>> >> to the
>> >> + * fs_inst* pointing to the IF instruction at the beginning of the
>> block.
>> >> + *
>> >> + * \return the number of MOVs to a common destination found in the two
>> >> branches
>> >> + * or zero if an error occurred.
>> >
>> >
>> > This comment makes it sound like the function verifies that the set of
>> > destinations in the "then" and "else" blocks is the same. It
>> > doesn't--that's done by fs_visitor::opt_peephole_sel().
>>
>> That's true -- and was a mistake I made when cleaning up the comments.
>> I originally had (and I'll change it to)
>>
>> + * \return the minimum number of MOVs found in the two branches or zero
>> if
>> + * an error occurred.
>>
>> >>
>> >> + *
>> >> + * E.g.:
>> >> + * match = IF ...
>> >> + * then_mov[1] = MOV g4, ...
>> >> + * then_mov[0] = MOV g5, ...
>> >> + * ELSE ...
>> >> + * else_mov[1] = MOV g4, ...
>> >> + * else_mov[0] = MOV g5, ...
>> >> + * ENDIF
>> >> + * returns 2.
>> >> + */
>> >> +static int
>> >> +match_movs_from_endif(fs_inst *then_mov[MAX_MOVS], fs_inst
>> >> *else_mov[MAX_MOVS],
>> >> + fs_inst **match)
>> >> +{
>> >> + fs_inst *m = *match;
>> >> +
>> >> + assert(m->opcode == BRW_OPCODE_ENDIF);
>> >> + m = (fs_inst *) m->prev;
>> >> +
>> >> + int else_movs = 0;
>> >> + while (else_movs < MAX_MOVS && m->opcode == BRW_OPCODE_MOV) {
>> >> + else_mov[else_movs] = m;
>> >> + m = (fs_inst *) m->prev;
>> >> + else_movs++;
>> >> + }
>> >> +
>> >> + if (m->opcode != BRW_OPCODE_ELSE)
>> >> + return 0;
>> >> + m = (fs_inst *) m->prev;
>> >> +
>> >> + int then_movs = 0;
>> >> + while (then_movs < MAX_MOVS && m->opcode == BRW_OPCODE_MOV) {
>> >> + then_mov[then_movs] = m;
>> >> + m = (fs_inst *) m->prev;
>> >> + then_movs++;
>> >> + }
>> >> +
>> >> + if (m->opcode != BRW_OPCODE_IF)
>> >> + return 0;
>> >> +
>> >> + *match = m;
>> >> + return MIN2(then_movs, else_movs);
>> >> +}
>> >> +
>> >> +/**
>> >> + * Try to replace IF/MOV+/ELSE/MOV+/ENDIF with SEL.
>> >> + *
>> >> + * Many GLSL shaders contain the following pattern:
>> >> + *
>> >> + * x = condition ? foo : bar
>> >> + *
>> >> + * or
>> >> + *
>> >> + * if (...) a.xyzw = foo.xyzw;
>> >> + * else a.xyzw = bar.xyzw;
>> >> + *
>> >> + * The compiler emits an ir_if tree for this, since each subexpression
>> >> might be
>> >> + * a complex tree that could have side-effects or short-circuit logic.
>> >> + *
>> >> + * However, the common case is to simply select one of two constants
>> or
>> >> + * variable values---which is exactly what SEL is for. In this case,
>> the
>> >> + * assembly looks like:
>> >> + *
>> >> + * (+f0) IF
>> >> + * ...
>> >> + * MOV dst src0
>> >> + * ELSE
>> >> + * ...
>> >> + * MOV dst src1
>> >> + * ENDIF
>> >> + *
>> >> + * where each pair of MOVs to a common destination and can be easily
>> >> translated
>> >> + * into
>> >> + *
>> >> + * (+f0) SEL dst src0 src1
>> >> + *
>> >> + * If src0 is an immediate value, we promote it to a temporary GRF.
>> >> + */
>> >> +bool
>> >> +fs_visitor::opt_peephole_sel()
>> >> +{
>> >> + bool progress = false;
>> >> +
>> >> + cfg_t cfg(this);
>> >> +
>> >> + for (int b = 0; b < cfg.num_blocks; b++) {
>> >> + bblock_t *block = cfg.blocks[b];
>> >> +
>> >> + int movs;
>> >> + fs_inst *if_inst, *endif_inst;
>> >> + fs_inst *start;
>> >> + fs_inst *else_mov[MAX_MOVS] = { NULL };
>> >> + fs_inst *then_mov[MAX_MOVS] = { NULL };
>> >> + bool bb_progress = false;
>> >> +
>> >> + /* IF and ENDIF instructions, by definition, can only be found
>> at
>> >> the
>> >> + * ends of basic blocks.
>> >> + */
>> >> + start = (fs_inst *) block->end;
>> >> + if (start->opcode == BRW_OPCODE_ENDIF) {
>> >> + fs_inst *match = endif_inst = start;
>> >> +
>> >> + /* Find MOVs to a common destination. */
>> >> + movs = match_movs_from_endif(then_mov, else_mov, &match);
>> >> + if (movs == 0)
>> >> + continue;
>> >> +
>> >> + if_inst = match;
>> >> + } else {
>> >> + continue;
>> >> + }
>> >> +
>> >> + assert(if_inst && endif_inst);
>> >> +
>> >> + fs_inst *sel_inst[MAX_MOVS] = { NULL };
>> >> + fs_inst *mov_imm_inst[MAX_MOVS] = { NULL };
>> >> +
>> >> + /* Generate SEL instructions for pairs of MOVs to a common
>> >> destination. */
>> >> + for (int i = 0; i < movs; i++) {
>> >> + if (!then_mov[i] || !else_mov[i])
>> >> + break;
>> >> +
>> >> + /* Check that the MOVs are the right form. */
>> >> + if (!then_mov[i]->dst.equals(else_mov[i]->dst) ||
>> >> + then_mov[i]->is_partial_write() ||
>> >> + else_mov[i]->is_partial_write()) {
>> >> + bb_progress = false;
>> >
>> >
>> > I found bb_progress difficult to follow, because we set it to true at
>> the
>> > bottom of this loop (before we've definitively made progress) and then
>> reset
>> > it to false here if there's a malformed MOV. How about if instead we
>> make a
>> > boolean called "malformed_mov_found", which starts off false and gets
>> set to
>> > true here.
>>
>> That is nicer. Will do.
>>
>> >>
>> >> + break;
>> >> + }
>> >> +
>> >> + /* Only the last source register can be a constant, so if the
>> >> MOV in
>> >> + * the "then" clause uses a constant, we need to put it in a
>> >> + * temporary.
>> >> + */
>> >> + fs_reg src0(then_mov[i]->src[0]);
>> >> + if (src0.file == IMM) {
>> >> + src0 = fs_reg(this, glsl_type::float_type);
>> >> + src0.type = then_mov[i]->src[0].type;
>> >> + mov_imm_inst[i] = MOV(src0, then_mov[i]->src[0]);
>> >> + }
>> >> +
>> >> + sel_inst[i] = SEL(then_mov[i]->dst, src0,
>> else_mov[i]->src[0]);
>> >> +
>> >> + if (brw->gen == 6 && if_inst->conditional_mod) {
>> >> + /* For Sandybridge with IF with embedded comparison */
>> >> + sel_inst[i]->predicate = BRW_PREDICATE_NORMAL;
>> >> + } else {
>> >> + /* Separate CMP and IF instructions */
>> >> + sel_inst[i]->predicate = if_inst->predicate;
>> >> + sel_inst[i]->predicate_inverse =
>> if_inst->predicate_inverse;
>> >> + }
>> >> +
>> >> + bb_progress = true;
>> >> + }
>> >> +
>> >> + if (bb_progress) {
>> >
>> >
>> > Then this would simply be "if (!malformed_mov_found)"
>> >
>> >>
>> >> + fs_inst *cmp_inst;
>> >> + if (brw->gen == 6 && if_inst->conditional_mod) {
>> >> + cmp_inst = CMP(reg_null_d, if_inst->src[0],
>> if_inst->src[1],
>> >> + if_inst->conditional_mod);
>> >> + } else {
>> >> + /* Separate CMP and IF instructions. Find instruction that
>> >> wrote
>> >> + * the flag register.
>> >> + */
>> >> + fs_inst *m;
>> >> + for (m = (fs_inst *) if_inst->prev; !m->writes_flag();
>> >> + m = (fs_inst *) m->prev);
>> >> +
>> >> + cmp_inst = new(mem_ctx) fs_inst(m);
>> >> + }
>> >
>> >
>> > This seems like a problem because in the non-gen6 case, we'll search
>> back
>> > arbitrarily far to find the instruction that wrote to the flag register;
>> > it's not necessarily safe to copy that instruction to after the ENDIF
>> block.
>> > For example, if the input code is:
>> >
>> > CMP null, a, b
>> > MOV a, c
>> > IF
>> > MOV d, e
>> > ELSE
>> > MOV d, f
>> > ENDIF
>> >
>> > Then we'll incorrectly optimize it to:
>> >
>> > CMP null, a, b # will later be dead code eliminated
>> > MOV a, c
>> > IF # will later be dead code eliminated
>> > ELSE # will later be dead code eliminated
>> > ENDIF # will later be dead code eliminated
>> > CMP null, a, b # incorrect! a has changed.
>> > SEL d, e, f
>>
>> Yeah, that is probably true.
>>
>> > I think what we want to do instead is emit the SEL instructions before
>> the
>> > IF; that way the condition flag will still be valid, so we don't have to
>> > make a copy of the CMP instruction and we can just optimize to:
>>
>> The next patches do this. I should have written a better cover letter.
>>
>> This patch optimizes only equal number of MOVs in the then and else
>> blocks, only if it can optimize out all of the MOVs. It searches
>> backward from the ENDIF, inserting SEL instructions after the ENDIF.
>>
>> Two patches later (10.5/15) I extend this to handle causes where a set
>> of matching MOVs is found by searching back from ENDIF but some other
>> non-matching MOV is found.
>> 11/15 inserts MOVs instead of SELs when the sources are the same.
>> 12/15 extends the pass to also search forwards from an IF instruction,
>> and inserts SELs above the IF.
>>
>
> Ok, I'm just starting to read through patch 12.
>
>
>>
>> > CMP null, a, b
>> > MOV a, c
>> > SEL d, e, f
>> > IF # will later be dead code eliminated
>> > ELSE # will later be dead code eliminated
>> > ENDIF # will later be dead code eliminated
>>
>> When the structure of the if block is if/4 movs/else/4 movs/endif and
>> all of the destinations match, it doesn't matter whether we search
>> forwards from IF or backwards from ENDIF, but I think there's a bunch
>> of code that actually does computations in the then/else and has MOVs
>> at the end of the block that we couldn't handle by inserting
>> instructions before the IF.
>>
>
> Ah, ok. I failed to notice that patch 10.5 also changed
> match_movs_from_endif so that it handles if/else blocks that contain
> non-MOV instructions before the final MOVs.
>
>
>>
>> Off hand, I'm not sure what the best way of preserving or regenerating
>> the flag state is across the IF statement is. Maybe just literally
>> save the flag with a MOV.
>>
>
> Yeah, that seems reasonable.
>
In fact, now that I think about it more, this seems essential, since patch
10.5 makes it possible to optimize code like this:
CMP null, a, b
IF
...other instructions that modify a and b
MOV c, d
ELSE
...other instructions that modify a and b
MOV c, e
ENDIF
in which case there's no choice but to save the flag with a MOV, because
you can't reliably reconstruct the condition after you've executed other
instructions that modify a and b.
>
>
>>
>> > A side bonus of this approach is that we produce fewer instructions that
>> > dead code elimination has to reclaim.
>> >
>> >>
>> >> +
>> >> + /* Insert flag-writing instruction immediately after the
>> ENDIF,
>> >> and
>> >> + * SEL and MOV imm instructions after that.
>> >> + */
>> >> + if (start->opcode == BRW_OPCODE_ENDIF) {
>> >> + endif_inst->insert_after(cmp_inst);
>> >> +
>> >> + for (int i = 0; i < movs; i++) {
>> >> + cmp_inst->insert_after(sel_inst[i]);
>> >> + if (mov_imm_inst[i])
>> >> + cmp_inst->insert_after(mov_imm_inst[i]);
>> >> +
>> >> + then_mov[i]->remove();
>> >> + else_mov[i]->remove();
>> >> + }
>> >> +
>> >> + /* Appending an instruction may have changed our bblock
>> end.
>> >> */
>> >> + block->end = sel_inst[0];
>> >> + }
>> >>
>> >> + }
>> >> + progress = progress || bb_progress;
>> >
>> >
>> > I think it would read slightly better to simply do
>> >
>> > progress = true;
>> >
>> > inside the "if (bb_progress)" block (or inside the "if
>> > (!malformed_mov_found)" block, if you take my suggestion about
>> > malformed_mov_found above). But it's not a big deal.
>>
>> Yes, sounds good.
>>
>> > My only critical concern is about the non-gen6 code path leading to
>> > incorrect optimizations.
>> >
>> >>
>> >> + }
>> >> +
>> >> + if (progress)
>> >> + invalidate_live_intervals();
>> >> +
>> >> + return progress;
>> >> +}
>> >> --
>> >> 1.8.3.2
>> >>
>> >> _______________________________________________
>> >> mesa-dev mailing list
>> >> mesa-dev at lists.freedesktop.org
>> >> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>> >
>> >
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20131030/16492ac7/attachment-0001.html>
More information about the mesa-dev
mailing list