Hi Richard, On 30/10/18 10:10, Richard Biener wrote: > > (sorry for breaking threading -- I composed a review mail offline but > gmail has no way of nicely sending that neither has it a way to bounce > messages...) > While Richard is away I've attempted to address some of your comments. I've tackled the simpler ones as I was not involved in the design and benchmarking of this pass and don't have experience with some of the APIs used (scalar evolution, in particular). Nevertheless, hopefully this cleans up some of the simpler concerns before close of stage 1 (though I hope Richard will address the more complex ones once he's back). > > This patch adds a pass that versions loops with variable index strides > > for the case in which the stride is 1. E.g.: > > > > for (int i = 0; i < n; ++i) > > x[i * stride] = ...; > > > > becomes: > > > > if (stepx == 1) > > for (int i = 0; i < n; ++i) > > x[i] = ...; > > else > > for (int i = 0; i < n; ++i) > > x[i * stride] = ...; > > > > This is useful for both vector code and scalar code, and in some cases > > can enable further optimisations like loop interchange or pattern > > recognition. > > > > The pass gives a 7.6% improvement on Cortex-A72 for 554.roms_r at -O3 > > and a 2.4% improvement for 465.tonto. I haven't found any SPEC tests > > that regress. > > > > Sizewise, there's a 10% increase in .text for both 554.roms_r and > > 465.tonto. That's obviously a lot, but in tonto's case it's because > > the whole program is written using assumed-shape arrays and pointers, > > so a large number of functions really do benefit from versioning. > > roms likewise makes heavy use of assumed-shape arrays, and that > > improvement in performance IMO justifies the code growth. > > Ouch. I know that at least with LTO IPA-CP can do "quite" some > propagation of constant strides. Not sure if we're aggressive > enough in actually doing the cloning for all cases we figure out > strides though. But my question is how we can avoid doing the > versioning for loops in the copy that did not have the IPA-CPed > stride of one? Ideally we'd be able to mark individual references > as {definitely,likely,unlikely,not}-unit-stride? > > > The next biggest .text increase is 4.5% for 548.exchange2_r. I did see > > a small (0.4%) speed improvement there, but although both 3-iteration runs > > produced stable results, that might still be noise. There was a slightly > > larger (non-noise) improvement for a 256-bit SVE model. > > > > 481.wrf and 521.wrf_r .text grew by 2.8% and 2.5% respectively, but > > without any noticeable improvement in performance. No other test grew > > by more than 2%. > > > > Although the main SPEC beneficiaries are all Fortran tests, the > > benchmarks we use for SVE also include some C and C++ tests that > > benefit. > > Did you see any slowdown, for example because versioning was forced > to be on an innermost loop? I'm thinking of the testcase in > PR87561 where we do have strided accesses in the innermost loop. > > Since you cite performance numbers how did you measure them? > I assume -Ofast -march=native but did you check with -flto? > > > Using -frepack-arrays gives the same benefits in many Fortran cases. > > The problem is that using that option inappropriately can force a full > > array copy for arguments that the function only reads once, and so it > > isn't really something we can turn on by default. The new pass is > > supposed to give most of the benefits of -frepack-arrays without > > the risk of unnecessary repacking. > > > > The patch therefore enables the pass by default at -O3. > > I think that's reasonable. > > One possible enhancement would be to add a value-profile for the > strides so we can guide this optimization better. > > The pass falls foul of C++ class make small methods of everything. > That makes following the code very hard. Please inline single-used > methods in callers wherever possible to make the code read > more like GCC code (using GCC API). I've inlined the two single-use methods you pointed out. > > The pass contains an awful lot of heuristics :/ Like last year > with the interchange pass I would suggest to rip most of it out > and first lay infrastructure with the cases you can positively > identify without applying heuristics or "hacks" like stripping > semantically required casts. That makes it also clear which > testcases test which code-path. That said, all the analyze > multiplications/plusses/factors stuff was extremely hard to review > and I have no overall picture why this is all so complicated or > necessary. > > > Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? > > > > Richard > > > > > > 2018-10-24 Richard Sandiford > > > > gcc/ > > * doc/invoke.texi (-fversion-loops-for-strides): Document > > (loop-versioning-group-size, loop-versioning-max-inner-insns) > > (loop-versioning-max-outer-insns): Document new --params. > > * Makefile.in (OBJS): Add gimple-loop-versioning.o. > > * common.opt (fversion-loops-for-strides): New option. > > * opts.c (default_options_table): Enable fversion-loops-for-strides > > at -O3. > > * params.def (PARAM_LOOP_VERSIONING_GROUP_SIZE) > > (PARAM_LOOP_VERSIONING_MAX_INNER_INSNS) > > (PARAM_LOOP_VERSIONING_MAX_OUTER_INSNS): New parameters. > > * passes.def: Add pass_loop_versioning. > > * timevar.def (TV_LOOP_VERSIONING): New time variable. > > * tree-ssa-propagate.h > > (substitute_and_fold_engine::substitute_and_fold): Add an optional > > block parameter. > > * tree-ssa-propagate.c > > (substitute_and_fold_engine::substitute_and_fold): Likewise. > > When passed, only walk blocks dominated by that block. > > * tree-vrp.h (range_includes_p): Declare. > > (range_includes_zero_p): Turn into an inline wrapper around > > range_includes_p. > > * tree-vrp.c (range_includes_p): New function, generalizing... > > (range_includes_zero_p): ...this. > > * tree-pass.h (make_pass_loop_versioning): Declare. > > * gimple-loop-versioning.cc: New file. > > > > gcc/testsuite/ > > * gcc.dg/loop-versioning-1.c: New test. > > * gcc.dg/loop-versioning-10.c: Likewise. > > * gcc.dg/loop-versioning-11.c: Likewise. > > * gcc.dg/loop-versioning-2.c: Likewise. > > * gcc.dg/loop-versioning-3.c: Likewise. > > * gcc.dg/loop-versioning-4.c: Likewise. > > * gcc.dg/loop-versioning-5.c: Likewise. > > * gcc.dg/loop-versioning-6.c: Likewise. > > * gcc.dg/loop-versioning-7.c: Likewise. > > * gcc.dg/loop-versioning-8.c: Likewise. > > * gcc.dg/loop-versioning-9.c: Likewise. > > * gfortran.dg/loop_versioning_1.f90: Likewise. > > * gfortran.dg/loop_versioning_2.f90: Likewise. > > * gfortran.dg/loop_versioning_3.f90: Likewise. > > * gfortran.dg/loop_versioning_4.f90: Likewise. > > * gfortran.dg/loop_versioning_5.f90: Likewise. > > * gfortran.dg/loop_versioning_6.f90: Likewise. > > * gfortran.dg/loop_versioning_7.f90: Likewise. > > * gfortran.dg/loop_versioning_8.f90: Likewise. > > > > Index: gcc/doc/invoke.texi > > =================================================================== > > --- gcc/doc/invoke.texi 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/doc/invoke.texi 2018-10-24 14:02:15.184152693 +0100 > > @@ -7934,7 +7934,8 @@ by @option{-O2} and also turns on the fo > > -fvect-cost-model @gol > > -ftree-partial-pre @gol > > -fpeel-loops @gol > > --fipa-cp-clone} > > +-fipa-cp-clone @gol > > +-fversion-loops-for-strides} > > > > @item -O0 > > @opindex O0 > > @@ -10358,6 +10359,29 @@ for one side of the iteration space and > > Move branches with loop invariant conditions out of the loop, with duplicates > > of the loop on both branches (modified according to result of the condition). > > > > +@item -fversion-loops-for-strides > > +@opindex fversion-loops-for-strides > > +If a loop iterates over an array with a variable stride, create another > > +version of the loop that assumes the stride is always 1. For example: > > + > > +@smallexample > > +for (int i = 0; i < n; ++i) > > + x[i * stride] = @dots{}; > > +@end smallexample > > + > > +becomes: > > + > > +@smallexample > > +if (stride == 1) > > + for (int i = 0; i < n; ++i) > > + x[i] = @dots{}; > > +else > > + for (int i = 0; i < n; ++i) > > + x[i * stride] = @dots{}; > > +@end smallexample > > + > > +This is particularly useful for assumed-shape arrays in Fortran. > > "where it allows better vectorization assuming contiguous accesses." > Done. > > + > > @item -ffunction-sections > > @itemx -fdata-sections > > @opindex ffunction-sections > > @@ -11567,6 +11591,20 @@ Hardware autoprefetcher scheduler model > > Number of lookahead cycles the model looks into; at ' > > ' only enable instruction sorting heuristic. > > > > +@item loop-versioning-group-size > > +Make the loop versioning pass optimize @samp{a[i * index * @var{N}]} > > +in the same way as it would optimize @samp{a[i * index]} when @var{N} > > +is less than or equal to this value. > > + > > +@item loop-versioning-max-inner-insns > > +The maximum number of instructions that an inner loop can have > > +before the loop versioning pass considers it too big to copy. > > + > > +@item loop-versioning-max-outer-insns > > +The maximum number of instructions that an outer loop can have > > +before the loop versioning pass considers it too big to copy, > > +discounting any instructions in inner loops that directly benefit > > +from versioning. > > > > @end table > > @end table > > Index: gcc/Makefile.in > > =================================================================== > > --- gcc/Makefile.in 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/Makefile.in 2018-10-24 14:02:15.180152727 +0100 > > @@ -1312,6 +1312,7 @@ OBJS = \ > > gimple-laddress.o \ > > gimple-loop-interchange.o \ > > gimple-loop-jam.o \ > > + gimple-loop-versioning.o \ > > gimple-low.o \ > > gimple-pretty-print.o \ > > gimple-ssa-backprop.o \ > > Index: gcc/common.opt > > =================================================================== > > --- gcc/common.opt 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/common.opt 2018-10-24 14:02:15.180152727 +0100 > > @@ -2712,6 +2712,10 @@ fsplit-loops > > Common Report Var(flag_split_loops) Optimization > > Perform loop splitting. > > > > +fversion-loops-for-strides > > +Common Report Var(flag_version_loops_for_strides) Optimization > > +Version loops based on whether indices have a stride of 1. > > stride of one. > Done. > > + > > funwind-tables > > Common Report Var(flag_unwind_tables) Optimization > > Just generate unwind tables for exception handling. > > Index: gcc/opts.c > > =================================================================== > > --- gcc/opts.c 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/opts.c 2018-10-24 14:02:15.184152693 +0100 > > @@ -544,6 +544,7 @@ static const struct default_options defa > > { OPT_LEVELS_3_PLUS, OPT_fipa_cp_clone, NULL, 1 }, > > { OPT_LEVELS_3_PLUS, OPT_ftree_partial_pre, NULL, 1 }, > > { OPT_LEVELS_3_PLUS, OPT_fpeel_loops, NULL, 1 }, > > + { OPT_LEVELS_3_PLUS, OPT_fversion_loops_for_strides, NULL, 1 }, > > > > /* -Ofast adds optimizations to -O3. */ > > { OPT_LEVELS_FAST, OPT_ffast_math, NULL, 1 }, > > Index: gcc/params.def > > =================================================================== > > --- gcc/params.def 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/params.def 2018-10-24 14:02:15.184152693 +0100 > > @@ -1360,6 +1360,25 @@ DEFPARAM(PARAM_AVOID_FMA_MAX_BITS, > > "Maximum number of bits for which we avoid creating FMAs.", > > 0, 0, 512) > > > > +DEFPARAM(PARAM_LOOP_VERSIONING_GROUP_SIZE, > > + "loop-versioning-group-size", > > + "The maximum constant N for which accesses of the form x[N * step]" > > + " are worth versioning for the case in which step is 1", > > + 4, 1, 0) > > + > > +DEFPARAM(PARAM_LOOP_VERSIONING_MAX_INNER_INSNS, > > + "loop-versioning-max-inner-insns", > > + "The maximum number of instructions in an inner loop that is being" > > + " considered for versioning", > > + 200, 0, 0) > > + > > +DEFPARAM(PARAM_LOOP_VERSIONING_MAX_OUTER_INSNS, > > + "loop-versioning-max-outer-insns", > > + "The maximum number of instructions in an outer loop that is being" > > + " considered for versioning, on top of the instructions in inner" > > + " loops", > > + 100, 0, 0) > > + > > /* > > > > Local variables: > > Index: gcc/passes.def > > =================================================================== > > --- gcc/passes.def 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/passes.def 2018-10-24 14:02:15.184152693 +0100 > > @@ -260,6 +260,7 @@ along with GCC; see the file COPYING3. > > NEXT_PASS (pass_tree_loop); > > PUSH_INSERT_PASSES_WITHIN (pass_tree_loop) > > NEXT_PASS (pass_tree_loop_init); > > + NEXT_PASS (pass_loop_versioning); > > I think neither of the following visible passes benefit from the > versioning but they might need to duplicate work (and code). > pass_loop_jam benefits because it needs to do dependence analysis. > Can you move the pass after loop splitting please? Done. > > > NEXT_PASS (pass_tree_unswitch); > > NEXT_PASS (pass_scev_cprop); > > NEXT_PASS (pass_loop_split); > > Index: gcc/timevar.def > > =================================================================== > > --- gcc/timevar.def 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/timevar.def 2018-10-24 14:02:15.188152659 +0100 > > @@ -234,6 +234,7 @@ DEFTIMEVAR (TV_DSE1 , " > > DEFTIMEVAR (TV_DSE2 , "dead store elim2") > > DEFTIMEVAR (TV_LOOP , "loop analysis") > > DEFTIMEVAR (TV_LOOP_INIT , "loop init") > > +DEFTIMEVAR (TV_LOOP_VERSIONING , "loop versioning") > > DEFTIMEVAR (TV_LOOP_MOVE_INVARIANTS , "loop invariant motion") > > DEFTIMEVAR (TV_LOOP_UNROLL , "loop unrolling") > > DEFTIMEVAR (TV_LOOP_DOLOOP , "loop doloop") > > Index: gcc/tree-ssa-propagate.h > > =================================================================== > > --- gcc/tree-ssa-propagate.h 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/tree-ssa-propagate.h 2018-10-24 14:02:15.188152659 +0100 > > @@ -104,7 +104,7 @@ extern void propagate_tree_value_into_st > > virtual bool fold_stmt (gimple_stmt_iterator *) { return false; } > > virtual tree get_value (tree) { return NULL_TREE; } > > > > - bool substitute_and_fold (void); > > + bool substitute_and_fold (basic_block = NULL); > > I'm not sure I approve of your use of the SSA propagator but > at least dominance constrains the versioned loop body appropriately... > > > bool replace_uses_in (gimple *); > > bool replace_phi_args_in (gphi *); > > }; > > Index: gcc/tree-ssa-propagate.c > > =================================================================== > > --- gcc/tree-ssa-propagate.c 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/tree-ssa-propagate.c 2018-10-24 14:02:15.188152659 +0100 > > @@ -1152,6 +1152,10 @@ substitute_and_fold_dom_walker::before_d > > > > > > /* Perform final substitution and folding of propagated values. > > + Process the whole function if BLOCK is null, otherwise only > > + process the blocks that BLOCK dominates. In the latter case, > > + it is the caller's responsibility to ensure that dominator > > + information is available and up-to-date. > > > > PROP_VALUE[I] contains the single value that should be substituted > > at every use of SSA name N_I. If PROP_VALUE is NULL, no values are > > @@ -1168,16 +1172,24 @@ substitute_and_fold_dom_walker::before_d > > Return TRUE when something changed. */ > > > > bool > > -substitute_and_fold_engine::substitute_and_fold (void) > > +substitute_and_fold_engine::substitute_and_fold (basic_block block) > > { > > if (dump_file && (dump_flags & TDF_DETAILS)) > > fprintf (dump_file, "\nSubstituting values and folding statements\n\n"); > > > > memset (&prop_stats, 0, sizeof (prop_stats)); > > > > - calculate_dominance_info (CDI_DOMINATORS); > > + /* Don't call calculate_dominance_info when iterating over a subgraph. > > + Callers that are using the interface this way are likely to want to > > + iterate over several disjoint subgraphs, and it would be expensive > > + in enable-checking builds to revalidate the whole dominance tree > > + each time. */ > > + if (block) > > + gcc_assert (dom_info_state (CDI_DOMINATORS)); > > + else > > + calculate_dominance_info (CDI_DOMINATORS); > > substitute_and_fold_dom_walker walker (CDI_DOMINATORS, this); > > - walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); > > + walker.walk (block ? block : ENTRY_BLOCK_PTR_FOR_FN (cfun)); > > > > /* We cannot remove stmts during the BB walk, especially not release > > SSA names there as that destroys the lattice of our callers. > > Index: gcc/tree-vrp.h > > =================================================================== > > --- gcc/tree-vrp.h 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/tree-vrp.h 2018-10-24 14:02:15.188152659 +0100 > > @@ -86,7 +86,7 @@ extern void register_edge_assert_for (tr > > tree, tree, vec &); > > extern bool stmt_interesting_for_vrp (gimple *); > > extern void set_value_range_to_varying (value_range *); > > -extern bool range_includes_zero_p (const value_range *); > > +extern bool range_includes_p (const value_range *, HOST_WIDE_INT); > > extern bool infer_value_range (gimple *, tree, tree_code *, tree *); > > > > extern void set_value_range_to_nonnull (value_range *, tree); > > @@ -122,4 +122,13 @@ extern int value_inside_range (tree, tre > > extern tree get_single_symbol (tree, bool *, tree *); > > extern void maybe_set_nonzero_bits (edge, tree); > > extern value_range_type determine_value_range (tree, wide_int *, wide_int *); > > + > > +/* Return TRUE if *VR includes the value zero. */ > > + > > +inline bool > > +range_includes_zero_p (const value_range *vr) > > +{ > > + return range_includes_p (vr, 0); > > +} > > + > > #endif /* GCC_TREE_VRP_H */ > > Index: gcc/tree-vrp.c > > =================================================================== > > --- gcc/tree-vrp.c 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/tree-vrp.c 2018-10-24 14:02:15.188152659 +0100 > > @@ -844,10 +844,10 @@ value_inside_range (tree val, tree min, > > } > > > > > > -/* Return TRUE if *VR includes the value zero. */ > > +/* Return TRUE if *VR includes the value X. */ > > > > bool > > -range_includes_zero_p (const value_range *vr) > > +range_includes_p (const value_range *vr, HOST_WIDE_INT x) > > { > > if (vr->type == VR_VARYING) > > return true; > > @@ -856,13 +856,13 @@ range_includes_zero_p (const value_range > > if (vr->type == VR_UNDEFINED) > > return true; > > > > - tree zero = build_int_cst (TREE_TYPE (vr->min), 0); > > + tree x_cst = build_int_cst (TREE_TYPE (vr->min), x); > > if (vr->type == VR_ANTI_RANGE) > > { > > - int res = value_inside_range (zero, vr->min, vr->max); > > + int res = value_inside_range (x_cst, vr->min, vr->max); > > return res == 0 || res == -2; > > } > > - return value_inside_range (zero, vr->min, vr->max) != 0; > > + return value_inside_range (x_cst, vr->min, vr->max) != 0; > > } > > > > /* If *VR has a value rante that is a single constant value return that, > > Index: gcc/tree-pass.h > > =================================================================== > > --- gcc/tree-pass.h 2018-10-24 14:02:14.000000000 +0100 > > +++ gcc/tree-pass.h 2018-10-24 14:02:15.188152659 +0100 > > @@ -362,6 +362,7 @@ extern gimple_opt_pass *make_pass_fix_lo > > extern gimple_opt_pass *make_pass_tree_loop (gcc::context *ctxt); > > extern gimple_opt_pass *make_pass_tree_no_loop (gcc::context *ctxt); > > extern gimple_opt_pass *make_pass_tree_loop_init (gcc::context *ctxt); > > +extern gimple_opt_pass *make_pass_loop_versioning (gcc::context *ctxt); > > extern gimple_opt_pass *make_pass_lim (gcc::context *ctxt); > > extern gimple_opt_pass *make_pass_linterchange (gcc::context *ctxt); > > extern gimple_opt_pass *make_pass_tree_unswitch (gcc::context *ctxt); > > Index: gcc/gimple-loop-versioning.cc > > =================================================================== > > --- /dev/null 2018-09-14 11:16:31.122530289 +0100 > > +++ gcc/gimple-loop-versioning.cc 2018-10-24 14:02:15.184152693 +0100 > > @@ -0,0 +1,1417 @@ > > +/* Loop versioning pass. > > + Copyright (C) 2018 Free Software Foundation, Inc. > > + > > +This file is part of GCC. > > + > > +GCC is free software; you can redistribute it and/or modify it > > +under the terms of the GNU General Public License as published by the > > +Free Software Foundation; either version 3, or (at your option) any > > +later version. > > + > > +GCC is distributed in the hope that it will be useful, but WITHOUT > > +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or > > +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License > > +for more details. > > + > > +You should have received a copy of the GNU General Public License > > +along with GCC; see the file COPYING3. If not see > > +. */ > > + > > +#include "config.h" > > +#include "system.h" > > +#include "coretypes.h" > > +#include "backend.h" > > +#include "tree.h" > > +#include "gimple.h" > > +#include "gimple-iterator.h" > > +#include "tree-pass.h" > > +#include "gimplify-me.h" > > +#include "cfgloop.h" > > +#include "tree-ssa-loop.h" > > +#include "ssa.h" > > +#include "tree-scalar-evolution.h" > > +#include "tree-chrec.h" > > +#include "tree-ssa-loop-ivopts.h" > > +#include "fold-const.h" > > +#include "tree-ssa-propagate.h" > > +#include "tree-inline.h" > > +#include "domwalk.h" > > +#include "alloc-pool.h" > > +#include "vr-values.h" > > +#include "gimple-ssa-evrp-analyze.h" > > +#include "gimple-pretty-print.h" > > +#include "params.h" > > + > > +/* This pass looks for loops that could be simplified if certain loop > > + invariant conditions were true. It is effectively a form of loop > > + splitting in which the pass produces the split conditions itself, > > + instead of using ones that are already present in the IL. > > + > > + Versioning for when strides are 1 > > + --------------------------------- > > + > > + At the moment the only thing the pass looks for are memory references > > + like: > > + > > + for (auto i : ...) > > + ...x[i * stride]... > > + > > + It considers changing such loops to: > > + > > + if (stride == 1) > > + for (auto i : ...) [A] > > + ...x[i]... > > + else > > + for (auto i : ...) [B] > > + ...x[i * stride]... > > + > > + This can have several benefits: > > + > > + (1) [A] is often easier or cheaper to vectorize than [B]. > > + > > + (2) The scalar code in [A] is simpler than the scalar code in [B] > > + (if the loops cannot be vectorized or need an epilogue loop). > > + > > + (3) We might recognize [A] as a pattern, such as a memcpy or memset. > > + > > + (4) [A] has simpler address evolutions, which can help other passes > > + like loop interchange. > > + > > + The optimization is particularly useful for assumed-shape arrays in > > + Fortran, where the stride of the innermost dimension depends on the > > + array descriptor but is often equal to 1 in practice. For example: > > + > > + subroutine f1(x) > > + real :: x(:) > > + x(:) = 100 > > + end subroutine f1 > > + > > + generates the equivalent of: > > + > > + raw_stride = *x.dim[0].stride; > > + stride = raw_stride != 0 ? raw_stride : 1; > > + x_base = *x.data; > > + ... > > + tmp1 = stride * S; > > + tmp2 = tmp1 - stride; > > + *x_base[tmp2] = 1.0e+2; > > + > > + but in the common case that stride == 1, the last three statements > > + simplify to: > > + > > + tmp3 = S + -1; > > + *x_base[tmp3] = 1.0e+2; > > + > > + The optimization is in principle very simple. The difficult parts are: > > + > > + (a) deciding which parts of a general address calculation correspond > > + to the inner dimension of an array, since this usually isn't explicit > > + in the IL, and for C often isn't even explicit in the source code > > + > > + (b) estimating when the transformation is worthwhile > > + > > + Structure > > + --------- > > + > > + The pass has four phases: > > + > > + (1) Walk through the statements looking for and recording potential > > + versioning opportunities. Stop if there are none. > > + > > + (2) Use context-sensitive range information to see whether any versioning > > + conditions are impossible in practice. Remove them if so, and stop > > + if no opportunities remain. > > + > > + (We do this only after (1) to keep compile time down when no > > + versioning opportunities exist.) > > + > > + (3) Apply the cost model. Decide which versioning opportunities are > > + worthwhile and at which nesting level they should be applied. > > + > > + (4) Attempt to version all the loops selected by (3), so that: > > + > > + for (...) > > + ... > > + > > + becomes: > > + > > + if (!cond) > > + for (...) // Original loop > > + ... > > + else > > + for (...) // New loop > > + ... > > + > > + Use the version condition COND to simplify the new loop. */ > > +class loop_versioning { > > +public: > > + loop_versioning (function *); > > + ~loop_versioning (); > > + unsigned int run (); > > + > > +private: > > + /* Information about the versioning we'd like to apply to a loop. */ > > + struct loop_info { > > + bool worth_versioning_p () const; > > + > > + /* True if we've decided not to version this loop. The remaining > > + fields are meaningless if so. */ > > + bool rejected_p; > > + > > + /* True if at least one subloop of this loop benefits from versioning. */ > > + bool subloops_benefit_p; > > + > > + /* An estimate of the total number of instructions in the loop, > > + excluding those in subloops that benefit from versioning. */ > > + unsigned int num_insns; > > + > > + /* The outermost loop that can handle all the version checks > > + described below. */ > > + struct loop *outermost; > > + > > + /* We'd like to version the loop for the case in which these > > + SSA_NAMEs are all equal to 1 at runtime. */ > > + vec unity_names; > > + > > + /* The set of SSA_NAMEs in UNITY_NAMES, keyed off the SSA_NAME_VERSION. */ > > + bitmap_head unity_name_ids; > > I wonder why you need both, a vector and a bitmap since you can > cheaply iterate over the bitmap and get the SSA name via ssa_name (version)? > > > + }; > > + > > + /* Used to walk the dominator tree to find loop versioning conditions > > + that are always false. */ > > + class lv_dom_walker : public dom_walker > > + { > > + public: > > + lv_dom_walker (loop_versioning &); > > + > > + edge before_dom_children (basic_block) FINAL OVERRIDE; > > + void after_dom_children (basic_block) FINAL OVERRIDE; > > + > > + private: > > + /* The parent pass. */ > > + loop_versioning &m_lv; > > + > > + /* Used to build context-dependent range information. */ > > + evrp_range_analyzer m_range_analyzer; > > + }; > > + > > + /* Used to simplify statements based on conditions that are established > > + by the version checks. */ > > + class name_prop : public substitute_and_fold_engine > > + { > > + public: > > + name_prop (loop_info &li) : m_li (li) {} > > + tree get_value (tree) FINAL OVERRIDE; > > + > > + private: > > + /* Information about the versioning we've performed on the loop. */ > > + loop_info &m_li; > > + }; > > + > > + loop_info &get_loop_info (struct loop *loop) { return m_loops[loop->num]; } > > + > > + unsigned int max_insns_for_loop (struct loop *); > > + bool expensive_stmt_p (gimple *); > > + > > + void version_for_unity (struct loop *, tree); > > + bool acceptable_scale_p (tree, poly_uint64); > > + tree get_step_if_innermost (tree, poly_uint64); > > + tree extract_step (tree, poly_uint64, tree *); > > + void analyze_evolution (struct loop *, tree, poly_uint64); > > + bool analyze_product (struct loop *, gassign *, poly_uint64); > > + bool analyze_sum_of_products (struct loop *, tree, poly_uint64); > > + void analyze_pointer (struct loop *, tree, tree); > > + void analyze_expr (struct loop *, tree); > > + void analyze_stmt (gimple *); > > + void analyze_block (basic_block); > > + bool analyze_blocks (); > > + > > + void prune_loop_conditions (struct loop *, vr_values *); > > + bool prune_conditions (); > > + > > + void merge_loop_info (struct loop *, struct loop *); > > + void add_loop_to_queue (struct loop *); > > + bool decide_whether_loop_is_versionable (struct loop *); > > + bool make_versioning_decisions (); > > + > > + bool version_loop (struct loop *); > > + bool implement_versioning_decisions (); > > + > > + /* The function we're optimizing. */ > > + function *m_fn; > > + > > + /* The obstack to use for all pass-specific bitmaps. */ > > + bitmap_obstack m_obstack; > > + > > + /* The number of loops in the function. */ > > + unsigned int m_nloops; > > + > > + /* The total number of loop version conditions we've found. */ > > + unsigned int m_num_conditions; > > + > > + /* Information about each loop. */ > > + auto_vec m_loops; > > + > > + /* The list of loops that we've decided to version. */ > > + auto_vec m_loops_to_version; > > +}; > > + > > +/* If EXPR is an SSA name and not a default definition, return the > > + defining statement, otherwise return null. */ > > + > > +static gimple * > > +maybe_get_stmt (tree expr) > > +{ > > + if (TREE_CODE (expr) == SSA_NAME && !SSA_NAME_IS_DEFAULT_DEF (expr)) > > + return SSA_NAME_DEF_STMT (expr); > > + return NULL; > > +} > > + > > +/* Like maybe_get_stmt, but also return null if the defining > > + statement isn't an assignment. */ > > + > > +static gassign * > > +maybe_get_assign (tree expr) > > +{ > > + return safe_dyn_cast (maybe_get_stmt (expr)); > > +} > > + > > +/* If EXPR is an SSA name, look through any casts to see whether the > > + unconverted value is defined in LOOP by a gassign. Return the > > + gassign if so, otherwise return null. */ > > + > > +gassign * > > +maybe_get_assign_strip_casts (struct loop *loop, tree expr) > > +{ > > + const unsigned int MAX_NITERS = 4; > > + > > + tree type = TREE_TYPE (expr); > > + for (unsigned int niters = 0; niters < MAX_NITERS; ++niters) > > + { > > + gassign *assign = maybe_get_assign (expr); > > + if (!assign || gimple_bb (assign)->loop_father != loop) > > + return NULL; > > + expr = gimple_assign_rhs1 (assign); > > + if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (assign)) > > + && INTEGRAL_TYPE_P (TREE_TYPE (expr)) == INTEGRAL_TYPE_P (type) > > + && POINTER_TYPE_P (TREE_TYPE (expr)) == POINTER_TYPE_P (type)) > > + ; > > + else > > + return assign; > > + } > > + return NULL; > > +} > > + > > +/* Strip all conversions of integers from EXPR, regardless of whether > > + the conversions are nops. This is useful in the context of this pass > > + because we're not trying to fold or simulate the expression; we just > > + want to see how it's structured. */ > > + > > +static tree > > +strip_casts (tree expr) > > +{ > > + while (CONVERT_EXPR_P (expr) > > + && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))) > > + expr = TREE_OPERAND (expr, 0); > > + return expr; > > +} > > + > > +/* Return true if we want to version the loop, i.e. if we have a > > + specific reason for doing so and no specific reason not to. */ > > + > > +bool > > +loop_versioning::loop_info::worth_versioning_p () const > > +{ > > + return !rejected_p && (!unity_names.is_empty () || subloops_benefit_p); > > +} > > + > > +loop_versioning::lv_dom_walker::lv_dom_walker (loop_versioning &lv) > > + : dom_walker (CDI_DOMINATORS), m_lv (lv) > > +{ > > +} > > + > > +/* Process BB before processing the blocks it dominates. */ > > + > > +edge > > +loop_versioning::lv_dom_walker::before_dom_children (basic_block bb) > > +{ > > + m_range_analyzer.enter (bb); > > + > > + if (bb == bb->loop_father->header) > > + m_lv.prune_loop_conditions (bb->loop_father, > > + m_range_analyzer.get_vr_values ()); > > + > > + for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); > > + gsi_next (&si)) > > + m_range_analyzer.record_ranges_from_stmt (gsi_stmt (si), false); > > + > > + return NULL; > > +} > > + > > +/* Process BB after processing the blocks it dominates. */ > > + > > +void > > +loop_versioning::lv_dom_walker::after_dom_children (basic_block bb) > > +{ > > + m_range_analyzer.leave (bb); > > +} > > + > > +/* Decide whether to replace VAL with a new value in a versioned loop. > > + Return the new value if so, otherwise return null. */ > > + > > +tree > > +loop_versioning::name_prop::get_value (tree val) > > +{ > > + if (TREE_CODE (val) == SSA_NAME > > + && bitmap_bit_p (&m_li.unity_name_ids, SSA_NAME_VERSION (val))) > > + return build_one_cst (TREE_TYPE (val)); > > + return NULL_TREE; > > +} > > + > > +/* Initialize the structure to optimize FN. */ > > + > > +loop_versioning::loop_versioning (function *fn) > > + : m_fn (fn), > > + m_nloops (number_of_loops (fn)), > > + m_num_conditions (0) > > +{ > > + bitmap_obstack_initialize (&m_obstack); > > + > > + m_loops.safe_grow_cleared (m_nloops); > > + for (unsigned int i = 0; i < m_nloops; ++i) > > + { > > + m_loops[i].outermost = get_loop (m_fn, 0); > > + bitmap_initialize (&m_loops[i].unity_name_ids, &m_obstack); > > + } > > +} > > + > > +loop_versioning::~loop_versioning () > > +{ > > + for (unsigned int i = 0; i < m_nloops; ++i) > > + m_loops[i].unity_names.release (); > > + bitmap_obstack_release (&m_obstack); > > +} > > + > > +/* Return the maximum number of instructions allowed in LOOP before > > + it becomes too big for versioning. > > + > > + There are separate limits for inner and outer loops. The limit for > > + inner loops applies only to loops that benefit directly from versioning. > > + The limit for outer loops applies to all code in the outer loop and > > + its subloops that *doesn't* benefit directly from versioning; such code > > + would be "taken along for the ride". The idea is that if the cost of > > + the latter is small, it is better to version outer loops rather than > > + inner loops, both to reduce the number of repeated checks and to enable > > + more of the loop nest to be optimized as a natural nest (e.g. by loop > > + interchange or outer-loop vectorization). */ > > + > > +unsigned int > > +loop_versioning::max_insns_for_loop (struct loop *loop) > > +{ > > + return (loop->inner > > + ? PARAM_VALUE (PARAM_LOOP_VERSIONING_MAX_OUTER_INSNS) > > + : PARAM_VALUE (PARAM_LOOP_VERSIONING_MAX_INNER_INSNS)); > > +} > > + > > +/* Return true if for cost reasons we should avoid versioning any loop > > + that contains STMT. > > + > > + Note that we don't need to check whether versioning is invalid for > > + correctness reasons, since the versioning process does that for us. > > + The conditions involved are too rare to be worth duplicating here. */ > > + > > +bool > > +loop_versioning::expensive_stmt_p (gimple *stmt) > > +{ > > + if (gcall *call = dyn_cast (stmt)) > > + /* Assume for now that the time spent in an "expensive" call would > > + overwhelm any saving from versioning. */ > > + return !gimple_inexpensive_call_p (call); > > + return false; > > +} > > + > > +/* Record that we want to version LOOP for the case in which SSA name NAME > > + is equal to 1. We already know that NAME is invariant in LOOP. */ > > + > > +void > > +loop_versioning::version_for_unity (struct loop *loop, tree name) > > +{ > > + loop_info &li = get_loop_info (loop); > > + > > + if (bitmap_set_bit (&li.unity_name_ids, SSA_NAME_VERSION (name))) > > + { > > + /* This is the first time we've wanted to version LOOP for NAME. */ > > + li.unity_names.safe_push (name); > > + > > + /* Keep track of the outermost loop that can handle all versioning > > + checks in LI. */ > > + struct loop *outermost > > + = outermost_invariant_loop_for_expr (loop, name); > > + if (loop_depth (li.outermost) < loop_depth (outermost)) > > + li.outermost = outermost; > > + > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + { > > + fprintf (dump_file, ";; Want to version loop %d (depth %d)" > > + " for when ", loop->num, loop_depth (loop)); > > + print_generic_expr (dump_file, name, TDF_SLIM); > > + fprintf (dump_file, " == 1"); > > Since you are writing a new pass you want to use the new dump interface. > > if (dump_enabled_p ()) > dump_printf (MSG_NOTE, ";; Want to version loop %d (depth %d)" > " for when %E == 1", loop->num, loop_depth (loop), name); > ... > > it's much nicer to be able to use %E/%G than separate calls for the > tree parts. Done. I've used the new dump interface throughout the new file, it is much cleaner and more pleasant to use. I've used %T for printing tree operands. > > > + if (outermost == loop) > > + fprintf (dump_file, "; cannot hoist check further"); > > + else > > + { > > + fprintf (dump_file, "; could hoist check to loop %d (depth %d)", > > + outermost->num, loop_depth (outermost)); > > + if (loop_depth (li.outermost) > loop_depth (outermost)) > > + fprintf (dump_file, ", but that's further than" > > + " other checks allow"); > > + } > > + fprintf (dump_file, "\n"); > > + } > > + > > + m_num_conditions += 1; > > + } > > + else > > + { > > + /* This is a duplicate request. */ > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + { > > + fprintf (dump_file, ";; Already want to version loop for when "); > > + print_generic_expr (dump_file, name, TDF_SLIM); > > + fprintf (dump_file, " == 1\n"); > > + } > > + } > > +} > > + > > +/* Return true if in principle it is worth versioning an index fragment of > > + the form: > > + > > + (i * b * SCALE) / FACTOR > > + > > + for the case in which b == 1. */ > > + > > +bool > > +loop_versioning::acceptable_scale_p (tree scale, poly_uint64 factor) > > +{ > > + /* See whether SCALE is a constant multiple of FACTOR, and if the > > + multiple is small enough for us to treat it as a potential grouped > > + access. For example: > > + > > + for (auto i : ...) > > + y[i] = f (x[4 * i * stride], > > + x[4 * i * stride + 1], > > + x[4 * i * stride + 2]); > > + > > + would benefit from versioning for the case in which stride == 1. > > + High multiples of i * stride are less likely to benefit, and could > > + indicate a simulated multi-dimensional array. > > + > > + This is just a heuristic, to avoid having to do expensive group > > + analysis of the data references in a loop. */ > > + poly_uint64 const_scale; > > + unsigned int multiple; > > + if (poly_int_tree_p (scale, &const_scale) > > + && constant_multiple_p (const_scale, factor, &multiple)) > > + { > > + unsigned int maxval = PARAM_VALUE (PARAM_LOOP_VERSIONING_GROUP_SIZE); > > + return IN_RANGE (multiple, 1, maxval); > > Hmm. So you _do_ want to version sth like > > struct X { int i; int j; } a[2048]; > > for (int i = start; i < end; ++i) > a[i*s].i = 1; > > ? That is, even with s == 1 the accesses will not become contiguous? > OK, I suppose that's because you are looking at a stmt in isolation > and another stmt may access a[i*s].j here. > > That is, would it be a future improvement to run sth like the > vectorizers group access analysis on the references and perform > this check on whole groups then, possibly better being able to > constrain what is now the magic parameter PARAM_LOOP_VERSIONING_GROUP_SIZE? > > I guess you tried to constrain it to the stmts access size but of course > that fails short of handling later SLP vectorized cases. > > > + } > > + > > + return false; > > +} > > + > > +/* Decide whether an index fragment of the form: > > + > > + (i * STEP) / FACTOR > > + > > + is likely to be for an innermost dimension. If we think it is, > > + return one of the constant values that it could have (returning 1 if > > + that's a possibility). If think it isn't, return null. Otherwise > > + return STEP, to indicate that it might or might not be an inner > > + dimension. */ > > + > > +tree > > +loop_versioning::get_step_if_innermost (tree step, poly_uint64 factor) > > +{ > > + const unsigned int MAX_NITERS = 8; > > + > > + tree likely = NULL_TREE; > > + tree unlikely = NULL_TREE; > > + tree worklist[MAX_NITERS]; > > + unsigned int length = 0; > > + worklist[length++] = step; > > + for (unsigned int i = 0; i < length; ++i) > > + { > > + tree expr = worklist[i]; > > + > > + if (TREE_CONSTANT (expr)) > > ? CONSTANT_CLASS_P (expr)? I've done that and it seems to work fine. > > > + { > > + /* See if multiplying by EXPR applies a scale that would be > > + consistent with an individual access or a small grouped > > + access. */ > > + if (acceptable_scale_p (expr, factor)) > > + { > > + likely = expr; > > + if (integer_onep (expr)) > > + break; > > + } > > + else > > + unlikely = expr; > > + continue; > > + } > > + > > + /* Otherwise we can only handle SSA names. */ > > + gimple *stmt = maybe_get_stmt (expr); > > + if (!stmt) > > + continue; > > + > > + /* If EXPR is set by a PHI node, queue its arguments in case > > + we find one that is consistent with an inner dimension. > > + > > + An important instance of this is the Fortran handling of array > > + descriptors, which calculates the stride of the inner dimension > > + using a PHI equivalent of: > > + > > + raw_stride = a.dim[0].stride; > > + stride = raw_stride != 0 ? raw_stride : 1; > > + > > + (Strides for outer dimensions do not treat 0 specially.) */ > > + if (gphi *phi = dyn_cast (stmt)) > > + { > > + unsigned int nargs = gimple_phi_num_args (phi); > > + for (unsigned int j = 0; j < nargs && length < MAX_NITERS; ++j) > > + worklist[length++] = gimple_phi_arg_def (phi, j); > > + continue; > > + } > > So only PHIs seed the worklist. > > > + /* If the value is set by an assignment, expect it to be read from > > + memory (such as an array descriptor) rather than be calculated. */ > > + if (gassign *assign = dyn_cast (stmt)) > > + { > > + if (gimple_assign_single_p (assign) > > + && is_gimple_lvalue (gimple_assign_rhs1 (assign))) > > Please do not use is_gimple_lvalue, that's supposed to be a gimplifier-only > predicate. Do you want to use gimple_assign_load_p here? gimple_assign_load_p works fine here. I've used that. > > > + continue; > > + > > + unlikely = expr; > > + } > > + > > + /* Things like calls don't really tell us anything. */ > > + } > > So I don't understand the above fully but it looks like plain > function arguments STEP will never be 'likely'? > > That is, I'd appreciate some more comments of what SSA def > chains we walk and what we look for in the end. > > > + if (likely) > > + { > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + fprintf (dump_file, "likely to be innermost dimension\n"); > > + return likely; > > + } > > + > > + if (unlikely) > > + { > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + fprintf (dump_file, "probably not innermost dimension\n"); > > + return NULL_TREE; > > + } > > + > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + { > > + if (maybe_ne (factor, 1U)) > > + fprintf (dump_file, "didn't find expected scaling factor\n"); > > + else > > + fprintf (dump_file, "no information about value\n"); > > + } > > + return step; > > +} > > + > > +/* STEP appears in an index fragment of the form: > > + > > + {..., +, STEP}_n / FACTOR > > + > > + Remove any conversions and grouping or scaling factors from STEP and > > + return the underlying index step. Set *STEP_IF_INNERMOST to the value > > + returned by get_step_if_innermost. */ > > + > > +tree > > +loop_versioning::extract_step (tree step, poly_uint64 factor, > > + tree *step_if_innermost) > > +{ > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + { > > + fprintf (dump_file, ";; step "); > > + print_generic_expr (dump_file, step, TDF_SLIM); > > + fprintf (dump_file, ": "); > > + } > > + > > + step = strip_casts (step); > > + > > + /* Peel any scaling, which generally happens after conversion to > > + pointer width. For example, on LP64 systems: > > + > > + int *x, i, stride; > > + ... x[4 * i * stride] ...; > > + > > + multiplies i * stride by 4 using ints, then widens the result > > + to pointer width before multiplying by sizeof (int). */ > > + poly_uint64 scale; > > + if (TREE_CODE (step) == MULT_EXPR > > + && poly_int_tree_p (TREE_OPERAND (step, 1), &scale) > > + && known_eq (scale, factor)) > > + { > > + step = strip_casts (TREE_OPERAND (step, 0)); > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + fprintf (dump_file, "scaled, "); > > + factor = 1; > > + } > > So I think the extra constant scale may or may not be in CHREC_RIGHT > depending on whether the expression was hoisted out of the loop as > invariant or implicit in sth like an ARRAY_REF. > > > + /* Peel any grouping multiple; see acceptable_scale_p for details. */ > > + if (TREE_CODE (step) == MULT_EXPR > > + && acceptable_scale_p (TREE_OPERAND (step, 1), factor)) > > + { > > + step = strip_casts (TREE_OPERAND (step, 0)); > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + fprintf (dump_file, "%sgrouped, ", > > + maybe_ne (factor, 1U) ? "scaled, " : ""); > > + factor = 1; > > + } > > Which means I'm not sure why there are (only) two MULTs being > looked for and only one has acceptable_scale_p applied... > > > + *step_if_innermost = get_step_if_innermost (step, factor); > > I know some people like to factor things but get_step_if_innermost > is called once if I see correctly - it makes understanding and > review harder to dissect things :/ > > > + return step; > > +} > > + > > +/* Analyze the evolution of index fragment EXPR / FACTOR in LOOP and its > > + containing loops to see whether any part of it could be simplified > > + by versioning. Register the versioning opportunities if so. */ > > + > > +void > > +loop_versioning::analyze_evolution (struct loop *loop, tree expr, > > + poly_uint64 factor) > > I find the name of this function confusing given it's nearly > the same as analyze_scalar_evolution. I've renamed it to analyze_index_evolution (though not sure if it's a much better name, naming things is notoriously hard). > > > +{ > > + const unsigned int MAX_NSPLIT = 8; > > + > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + { > > + fprintf (dump_file, ";; Analyzing use of "); > > + print_generic_expr (dump_file, expr, TDF_SLIM); > > + if (maybe_ne (factor, 1U)) > > + { > > + fprintf (dump_file, " (which addresses "); > > + print_dec (factor, dump_file); > > + fprintf (dump_file, " bytes)"); > > + } > > + fprintf (dump_file, " in loop %d (depth %d)\n", > > + loop->num, loop_depth (loop)); > > + } > > + > > + /* The main problem we have here is that we cannot assume that the > > + innermost loop iterates over the innermost dimension of an array. > > + Accidentally adding versioning checks for outer dimensions would > > + cause the version condition to be false, which as well as bloating > > + the code would defeat loop versioning benefits for other accesses. > > + > > + Unfortunately all we usually see at this stage is general address > > + arithmetic, with no positive way of identifying how many dimensions > > + an array access has and which multiplication factors in the address > > + expression correspond to which array dimensions. In C code this is > > + often not even explicit in the source, since variable-sized multi- > > + dimensional arrays are often simulated using one-dimensional arrays. > > + > > + The three main ways in which we deal with this are: > > + > > + - use heuristics that positively identify steps that are likely > > + to represent the inner dimension. > > + > > + - use heuristics that positively identify steps that are unlikely > > + to represent the inner dimension. > > + > > + - if a part of EXPR is invariant in LOOP, analyze its evolution in > > + the outer loops to see whether we can positively identify any of > > + it as iterating over the inner dimension. */ > > + tree best_step = NULL_TREE; > > + auto_vec worklist; > > + worklist.quick_push (expr); > > + unsigned int nsplit = 0; > > + while (!worklist.is_empty ()) > > + { > > + expr = strip_casts (worklist.pop ()); > > + tree_code code = TREE_CODE (expr); > > + > > + if (code == POLYNOMIAL_CHREC) > > + { > > + /* Analyze the CHREC_RIGHT as the step in an index fragment. */ > > + tree step_if_innermost; > > + tree step = extract_step (CHREC_RIGHT (expr), factor, > > + &step_if_innermost); > > + if (!best_step) > > + { > > + /* This is the outermost chrec for the original expression. > > + It's not worth carrying on if the step isn't versionable, > > + or if we're pretty sure it's not for the inner dimension. */ > > + if (!step_if_innermost > > + || TREE_CODE (step) != SSA_NAME > > + || !expr_invariant_in_loop_p (loop, step)) > > + return; > > + > > + best_step = step; > > + > > + /* We should version for STEP == 1 if we know that that can be > > + true under some circumstances. */ > > + if (integer_onep (step_if_innermost)) > > + break; > > + > > + /* Bail out if this appears to be the step for the innermost > > + dimension, but isn't likely to be 1. > > + > > + ??? We could instead version for when it equals > > + STEP_IF_INNERMOST, but it's not likely to have as much > > + benefit as versioning for 1. */ > > + if (step_if_innermost != step) > > + return; > > + } > > + else > > + { > > + /* This is an inner chrec. If it looks like it iterates over > > + the innermost dimension, abort any attempt to version for > > + the outermost chrec (which if we reach here wasn't itself > > + obviously iterating over the innermost dimension). */ > > + if (step_if_innermost && TREE_CONSTANT (step_if_innermost)) > > + return; > > + } > > + worklist.quick_push (CHREC_LEFT (expr)); > > + continue; > > + } > > + > > + /* Analyze parts of a queued CHREC_LEFT. This is better than just > > + analyzing the evolution of the whole expression since the value > > + could include a mixture of analyzable and unanalyzable elements. > > + Use NSPLIT to count cases in which we add more expressions to > > + analyze, as opposed to just simplifying the existing one. */ > > + if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR || code == MINUS_EXPR) > > + { > > + worklist.quick_push (TREE_OPERAND (expr, 0)); > > + if (nsplit++ < MAX_NSPLIT) > > + worklist.quick_push (TREE_OPERAND (expr, 1)); > > + continue; > > + } > > + if (code == MULT_EXPR) > > + { > > + tree op0 = strip_casts (TREE_OPERAND (expr, 0)); > > + tree op1 = TREE_OPERAND (expr, 1); > > + if (TREE_CODE (op0) == PLUS_EXPR || TREE_CODE (op0) == MINUS_EXPR) > > + { > > + tree type = TREE_TYPE (expr); > > + tree op00 = fold_convert (type, TREE_OPERAND (op0, 0)); > > + worklist.quick_push (fold_build2 (MULT_EXPR, type, op00, op1)); > > + if (nsplit++ < MAX_NSPLIT) > > + { > > + tree op01 = fold_convert (type, TREE_OPERAND (op0, 1)); > > + worklist.quick_push (fold_build2 (MULT_EXPR, type, > > + op01, op1)); > > + } > > + continue; > > + } > > + } > > + > > + /* If EXPR is invariant in LOOP, analyze it wrt the innermost loop > > + for which it could evolve (i.e. the loop containing the outermost > > + one for which EXPR is invariant). */ > > This isn't how analyze_scalar_evolution works - you _always_ have to > feed the innermost loop that the expression is used in (the context). > Then you instantiate the result in the outermost loop of the nest you > are interested in. Otherwise you get garbage. > > It looks like you are re-analyzing SSA names in the evolution - that's > odd and shouldn't be necessary (but you forget to instantiate, so...). > > I suggest to move the analyze_scalar_evolution part out of the worklist > loop where you are sure you have an SSA name. > > > + struct loop *wrt_loop = outermost_invariant_loop_for_expr (loop, expr); > > + if (wrt_loop) > > + { > > + wrt_loop = loop_outer (wrt_loop); > > + if (!wrt_loop) > > + continue; > > + } > > + else > > + wrt_loop = loop; > > + tree evolution = analyze_scalar_evolution (wrt_loop, expr); > > + tree chrec = strip_casts (evolution); > > + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) > > + { > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + { > > + fprintf (dump_file, ";; evolution of "); > > + print_generic_expr (dump_file, expr, TDF_SLIM); > > + fprintf (dump_file, " in loop %d (depth %d): ", > > + wrt_loop->num, loop_depth (wrt_loop)); > > + print_generic_expr (dump_file, evolution, TDF_SLIM); > > + fprintf (dump_file, "\n"); > > + } > > + worklist.quick_push (chrec); > > + } > > + else > > + { > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + { > > + fprintf (dump_file, ";; cannot analyze "); > > + print_generic_expr (dump_file, expr, TDF_SLIM); > > + fprintf (dump_file, " any further\n"); > > + } > > + } > > + } > > + if (best_step) > > + version_for_unity (loop, best_step); > > +} > > + > > +/* Analyze multiplication MULT to see whether we can identify "gather-like" > > + versioning opportunities such as: > > + > > + for (int i = 0; i < n; ++i) > > + res += a[index[i] * stride]; > > + > > + Return true if there was a versioning opportunity. > > + > > + LOOP is the loop that contains MULT. Dividing the value of MULT > > + by FACTOR converts it into an element index. */ > > + > > +bool > > +loop_versioning::analyze_product (struct loop *loop, gassign *mult, > > + poly_uint64 factor) > > +{ > > + /* Record the original LHS for the dump message below. */ > > + tree lhs = gimple_assign_lhs (mult); > > + > > + /* Peel any scaling, which generally happens after conversion to > > + pointer width. For example, on LP64 systems: > > + > > + int *x, i, stride; > > + ... x[4 * i * stride] ...; > > + > > + multiplies i * stride by 4 using ints, then widens the result > > + to pointer width before multiplying by sizeof (int). */ > > + poly_uint64 scale; > > + if (poly_int_tree_p (gimple_assign_rhs2 (mult), &scale) > > + && known_eq (scale, factor)) > > + { > > + mult = maybe_get_assign_strip_casts (loop, gimple_assign_rhs1 (mult)); > > + if (!mult || gimple_assign_rhs_code (mult) != MULT_EXPR) > > + return false; > > + factor = 1; > > + } > > + > > + /* Peel any grouping multiple; see acceptable_scale_p for details. */ > > + if (acceptable_scale_p (gimple_assign_rhs2 (mult), factor)) > > + { > > + mult = maybe_get_assign_strip_casts (loop, gimple_assign_rhs1 (mult)); > > + if (!mult || gimple_assign_rhs_code (mult) != MULT_EXPR) > > + return false; > > + } > > + else if (maybe_ne (factor, 1U)) > > + /* We expect to see a scaling multiplication when FACTOR is > 1. */ > > + return false; > > + > > + /* See whether this multiplication involves a loop-invariant SSA name > > + and a non-invariant SSA name. */ > > + tree op1 = gimple_assign_rhs1 (mult); > > + tree op2 = gimple_assign_rhs2 (mult); > > + if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME) > > + return false; > > + > > + bool invariant1_p = expr_invariant_in_loop_p (loop, op1); > > + bool invariant2_p = expr_invariant_in_loop_p (loop, op2); > > + if (invariant1_p == invariant2_p) > > + return false; > > + > > + /* Make sure that the invariant is OP1 and the other operand is OP2. */ > > + if (invariant2_p) > > + std::swap (op1, op2); > > + > > + /* Bail out if OP2 can be analyzed as an evolution; we want to use > > + analyze_evolution in that case instead. There's no point trying > > + hard to avoid repeating the call to analyze_scalar_evolution since > > + that function does its own caching. */ > > + if (tree_contains_chrecs (analyze_scalar_evolution (loop, op2), NULL)) > > Don't you want !chrec_contains_undetermined (...) instead? I wonder what > is missing to allow all interesting expressions to be analyzed by > SCEV? I've tried that and with !chrec_contains_undetermined we fail to version the loop-versioning-10.c testcase: for (int i = 0; i < n; ++i) res += x[index[i] * step]; > > > + return false; > > + > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + { > > + fprintf (dump_file, ";; Address fragment "); > > + print_generic_expr (dump_file, lhs, TDF_SLIM); > > + fprintf (dump_file, " multiplies invariant "); > > + print_generic_expr (dump_file, op1, TDF_SLIM); > > + fprintf (dump_file, " by "); > > + print_generic_expr (dump_file, op2, TDF_SLIM); > > + fprintf (dump_file, ", which isn't a scalar evolution\n"); > > + } > > + > > + version_for_unity (loop, op1); > > + return true; > > +} > > + > > +/* Treat EXPR as a sum of products and apply analyze_product to each of the > > + products. Return true if one of the products provides a versioning > > + opportunity. FACTOR is as for analyze_product. */ > > + > > +bool > > +loop_versioning::analyze_sum_of_products (struct loop *loop, tree expr, > > + poly_uint64 factor) > > +{ > > This looks awfully close to what tree-affine.c does apart from more > aggressively stripping conversions? I see all the analysis parts > are limited and thus "O(1)" but still there's going to be a lot of > redundancy involved for repeated use of (derived) "IVs"? Wouldn't > it be good to have a bitmap of already handled SSA_NAMEs to stop > processing early? I've used a bitmap of SSA names to limit this. > > > + const unsigned int MAX_NITERS = 8; > > + > > + tree worklist[MAX_NITERS]; > > + unsigned int length = 0; > > + worklist[length++] = expr; > > + for (unsigned int i = 0; i < length; ++i) > > + { > > + expr = worklist[i]; > > + gassign *assign = maybe_get_assign_strip_casts (loop, expr); > > + if (!assign) > > + continue; > > + > > + tree_code code = gimple_assign_rhs_code (assign); > > + if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR || code == MINUS_EXPR) > > POINTER_MINUS_EXPR? > > > + { > > + if (length < MAX_NITERS) > > + worklist[length++] = gimple_assign_rhs1 (assign); > > + if (length < MAX_NITERS) > > + worklist[length++] = gimple_assign_rhs2 (assign); > > + } > > + else if (code == MULT_EXPR && analyze_product (loop, assign, factor)) > > + return true; > > + } > > + return false; > > +} > > + > > +/* Analyze pointer expression EXPR, which occurs in loop LOOP and which > > + is used to address a value of type TYPE. */ > > + > > +void > > +loop_versioning::analyze_pointer (struct loop *loop, tree expr, tree type) > > +{ > > Inline into single caller Done. > > > + poly_uint64 factor; > > + if (poly_int_tree_p (TYPE_SIZE_UNIT (type), &factor)) > > + { > > + if (!analyze_sum_of_products (loop, expr, factor)) > > + analyze_evolution (loop, expr, factor); > > + } > > +} > > + > > +/* Analyze expression EXPR, which occurs in loop LOOP. */ > > + > > +void > > +loop_versioning::analyze_expr (struct loop *loop, tree expr) > > +{ > > + while (handled_component_p (expr)) > > + { > > + /* See whether we can use versioning to avoid a multiplication > > + in the array index. */ > > + if (TREE_CODE (expr) == ARRAY_REF) > > + { > > + if (!analyze_sum_of_products (loop, TREE_OPERAND (expr, 1), 1)) > > + analyze_evolution (loop, TREE_OPERAND (expr, 1), 1); > > + } > > + expr = TREE_OPERAND (expr, 0); > > + } > > + > > + if (TREE_CODE (expr) == MEM_REF) > > + { > > + tree addr = TREE_OPERAND (expr, 0); > > + /* See whether we can use versioning to avoid a multiplication > > + in the pointer calculation. This is generally only worth > > + doing if the multiplication occurs in this loop rather than > > + an outer loop. */ > > Why's that so here but not above for ARRAY_REF? That is, what is > the difference between a[i] and ptr = &a[i]; *ptr? > > > + if (!expr_invariant_in_loop_p (loop, addr)) > > + analyze_pointer (loop, addr, TREE_TYPE (expr)); > > + } > > + > > + /* These would be easy to handle if they existed at this stage. */ > > + gcc_checking_assert (TREE_CODE (expr) != TARGET_MEM_REF); > > +} > > + > > +/* Analyze STMT looking for useful version checks. */ > > + > > +void > > +loop_versioning::analyze_stmt (gimple *stmt) > > +{ > > Please inline into single caller to make flow easily visible. Done. > > > + struct loop *loop = gimple_bb (stmt)->loop_father; > > + > > + unsigned int nops = gimple_num_ops (stmt); > > + for (unsigned int i = 0; i < nops; ++i) > > + if (tree op = gimple_op (stmt, i)) > > + analyze_expr (loop, op); > > I think you instead want to use gimple_walk_load_store_ops (). Do you mean walk_stmt_load_store_ops ? Doing that was a bit awkward as analyze_expr is a member function and I couldn't find a neat way of passing a callback to walk_stmt_load_store_ops with the appropriate object state. Maybe my C++ is lacking here, but this loop looks easier to read IMO. > > > +} > > + > > +/* Analyze all the statements in BB looking for useful version checks. */ > > + > > +void > > +loop_versioning::analyze_block (basic_block bb) > > +{ > > + struct loop *loop = bb->loop_father; > > + loop_info &li = get_loop_info (loop); > > + if (li.rejected_p) > > + return; > > + > > + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); > > + gsi_next (&gsi)) > > + { > > + gimple *stmt = gsi_stmt (gsi); > > + if (expensive_stmt_p (stmt)) > > + { > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + { > > + struct loop *loop = gimple_bb (stmt)->loop_father; > > + fprintf (dump_file, ";; Loop %d (depth %d) contains expensive" > > + " stmt: ", loop->num, loop_depth (loop)); > > + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); > > + } > > + li.rejected_p = true; > > I assume that once a loop is rejected this or another way there's > no reason to look at any outer loop of it, thus ... > > > + break; > > + } > > + > > + /* Only look for direct versioning opportunities in inner loops > > + since the benefit tends to be much smaller for outer loops. */ > > + if (!loop->inner) > > + analyze_stmt (stmt); > > + > > + /* The point of the instruction limit is to prevent excessive > > + code growth, so this is a size-based estimate even though > > + the optimization is aimed at speed. */ > > + li.num_insns += estimate_num_insns (stmt, &eni_size_weights); > > + } > > +} > > + > > +/* Analyze all the blocks in the function looking for useful version checks. > > + Return true if we found one. */ > > + > > +bool > > +loop_versioning::analyze_blocks () > > +{ > > + /* For now we don't try to version the whole function, although > > + versioning at that level could be useful in some cases. */ > > + get_loop_info (get_loop (m_fn, 0)).rejected_p = true; > > + > > + basic_block bb; > > + FOR_EACH_BB_FN (bb, m_fn) > > + if (loop_outer (bb->loop_father)) > > + analyze_block (bb); > > .... I'd structure this as a > > FOR_EACH_LOOP (... LI_FROM_INNERMOST) > look at loop body, only analyze stmts belonging to loop (not subloops) > > walk eventually even open-coding this as recursion so you can quickly > finish off outer loop processing once an inner loop got disabled. > > > + > > + return m_num_conditions != 0; > > +} > > + > > +/* Use the ranges in VRS to remove impossible versioning conditions from > > + LOOP. */ > > Does it actually happen to make it worthwhile? ;) > > > + > > +void > > +loop_versioning::prune_loop_conditions (struct loop *loop, vr_values *vrs) > > +{ > > + loop_info &li = get_loop_info (loop); > > + > > + unsigned int i = li.unity_names.length (); > > + while (i > 0) > > + { > > + i -= 1; > > + tree name = li.unity_names[i]; > > + value_range *vr = vrs->get_value_range (name); > > + if (vr && !range_includes_p (vr, 1)) > > + { > > + if (dump_file && (dump_flags & TDF_DETAILS)) > > + { > > + fprintf (dump_file, ";; "); > > + print_generic_expr (dump_file, name, TDF_SLIM); > > + fprintf (dump_file, " can never be 1 in loop %d\n", loop->num); > > + } > > + > > + li.unity_names.unordered_remove (i); > > + bitmap_clear_bit (&li.unity_name_ids, SSA_NAME_VERSION (name)); > > + m_num_conditions -= 1; > > + } > > + } > > +} 2018-11-08 Richard Sandiford Ramana Radhakrishnan Kyrylo Tkachov gcc/ * Makefile.in (OBJS): Add gimple-loop-versioning.o. * common.opt (fversion-loops-for-strides): New option. * opts.c (default_options_table): Enable fversion-loops-for-strides at -O3. * params.def (PARAM_LOOP_VERSIONING_GROUP_SIZE) (PARAM_LOOP_VERSIONING_MAX_INNER_INSNS) (PARAM_LOOP_VERSIONING_MAX_OUTER_INSNS): New parameters. * passes.def: Add pass_loop_versioning. * timevar.def (TV_LOOP_VERSIONING): New time variable. * tree-ssa-propagate.h (substitute_and_fold_engine::substitute_and_fold): Add an optional block parameter. * tree-ssa-propagate.c (substitute_and_fold_engine::substitute_and_fold): Likewise. When passed, only walk blocks dominated by that block. * tree-vrp.h (range_includes_p): Declare. (range_includes_zero_p): Turn into an inline wrapper around range_includes_p. * tree-vrp.c (range_includes_p): New function, generalizing... (range_includes_zero_p): ...this. * tree-pass.h (make_pass_loop_versioning): Declare. * gimple-loop-versioning.cc: New file. gcc/testsuite/ * gcc.dg/loop-versioning-1.c: New test. * gcc.dg/loop-versioning-10.c: Likewise. * gcc.dg/loop-versioning-11.c: Likewise. * gcc.dg/loop-versioning-2.c: Likewise. * gcc.dg/loop-versioning-3.c: Likewise. * gcc.dg/loop-versioning-4.c: Likewise. * gcc.dg/loop-versioning-5.c: Likewise. * gcc.dg/loop-versioning-6.c: Likewise. * gcc.dg/loop-versioning-7.c: Likewise. * gcc.dg/loop-versioning-8.c: Likewise. * gcc.dg/loop-versioning-9.c: Likewise. * gfortran.dg/loop_versioning_1.f90: Likewise. * gfortran.dg/loop_versioning_2.f90: Likewise. * gfortran.dg/loop_versioning_3.f90: Likewise. * gfortran.dg/loop_versioning_4.f90: Likewise. * gfortran.dg/loop_versioning_5.f90: Likewise. * gfortran.dg/loop_versioning_6.f90: Likewise. * gfortran.dg/loop_versioning_7.f90: Likewise. * gfortran.dg/loop_versioning_8.f90: Likewise.