On 30 October 2013 10:10, Matt Turner <matts...@gmail.com> wrote: > On Wed, Oct 30, 2013 at 9:30 AM, Paul Berry <stereotype...@gmail.com> > wrote: > > On 28 October 2013 11:31, Matt Turner <matts...@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. > > > 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@lists.freedesktop.org > >> http://lists.freedesktop.org/mailman/listinfo/mesa-dev > > > > >
_______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev