Add a loop versioning pass
Richard Sandiford
richard.sandiford@arm.com
Wed Oct 24 13:41:00 GMT 2018
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.
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.
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.
Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install?
Richard
2018-10-24 Richard Sandiford <richard.sandiford@arm.com>
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.
+
@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.
+
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);
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);
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<assert_info> &);
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
+<http://www.gnu.org/licenses/>. */
+
+#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<tree> unity_names;
+
+ /* The set of SSA_NAMEs in UNITY_NAMES, keyed off the SSA_NAME_VERSION. */
+ bitmap_head unity_name_ids;
+ };
+
+ /* 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<loop_info> m_loops;
+
+ /* The list of loops that we've decided to version. */
+ auto_vec<struct loop *> 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 <gassign *> (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 <gcall *> (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");
+ 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);
+ }
+
+ 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))
+ {
+ /* 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 <gphi *> (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;
+ }
+
+ /* 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 <gassign *> (stmt))
+ {
+ if (gimple_assign_single_p (assign)
+ && is_gimple_lvalue (gimple_assign_rhs1 (assign)))
+ continue;
+
+ unlikely = expr;
+ }
+
+ /* Things like calls don't really tell us anything. */
+ }
+
+ 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;
+ }
+
+ /* 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;
+ }
+
+ *step_if_innermost = get_step_if_innermost (step, factor);
+ 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)
+{
+ 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<tree, MAX_NSPLIT> 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). */
+ 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))
+ 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)
+{
+ 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)
+ {
+ 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)
+{
+ 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. */
+ 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)
+{
+ 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);
+}
+
+/* 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;
+ 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);
+
+ return m_num_conditions != 0;
+}
+
+/* Use the ranges in VRS to remove impossible versioning conditions from
+ LOOP. */
+
+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;
+ }
+ }
+}
+
+/* Remove any scheduled loop version conditions that will never be true.
+ Return true if any remain. */
+
+bool
+loop_versioning::prune_conditions ()
+{
+ calculate_dominance_info (CDI_DOMINATORS);
+ lv_dom_walker dom_walker (*this);
+ dom_walker.walk (ENTRY_BLOCK_PTR_FOR_FN (m_fn));
+ return m_num_conditions != 0;
+}
+
+/* Merge the version checks for INNER into immediately-enclosing loop
+ OUTER. */
+
+void
+loop_versioning::merge_loop_info (struct loop *outer, struct loop *inner)
+{
+ loop_info &inner_li = get_loop_info (inner);
+ loop_info &outer_li = get_loop_info (outer);
+
+ tree name;
+ unsigned int i;
+ FOR_EACH_VEC_ELT (inner_li.unity_names, i, name)
+ if (bitmap_set_bit (&outer_li.unity_name_ids, SSA_NAME_VERSION (name)))
+ {
+ outer_li.unity_names.safe_push (name);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, ";; Hoisting check that ");
+ print_generic_expr (dump_file, name, TDF_SLIM);
+ fprintf (dump_file, " == 1 from loop %d (depth %d) to loop %d\n",
+ inner->num, loop_depth (inner), outer->num);
+ }
+ }
+
+ if (loop_depth (outer_li.outermost) < loop_depth (inner_li.outermost))
+ outer_li.outermost = inner_li.outermost;
+}
+
+/* Add LOOP to the queue of loops to version. */
+
+void
+loop_versioning::add_loop_to_queue (struct loop *loop)
+{
+ loop_info &li = get_loop_info (loop);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ";; Queuing loop %d (depth %d) for versioning\n",
+ loop->num, loop_depth (loop));
+ m_loops_to_version.safe_push (loop);
+
+ /* Don't try to version superloops. */
+ li.rejected_p = true;
+}
+
+/* Decide whether the cost model would allow us to version LOOP,
+ either directly or as part of a parent loop, and return true if so.
+ This does not imply that the loop is actually worth versioning in its
+ own right, just that it would be valid to version it if something
+ benefited.
+
+ We have already made this decision for all inner loops of LOOP. */
+
+bool
+loop_versioning::decide_whether_loop_is_versionable (struct loop *loop)
+{
+ loop_info &li = get_loop_info (loop);
+
+ if (li.rejected_p)
+ return false;
+
+ /* Examine the decisions made for inner loops. */
+ for (struct loop *inner = loop->inner; inner; inner = inner->next)
+ {
+ loop_info &inner_li = get_loop_info (inner);
+ if (inner_li.rejected_p)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ";; Not versioning loop %d (depth %d)"
+ " because inner loop %d should not be versioned\n",
+ loop->num, loop_depth (loop), inner->num);
+ return false;
+ }
+
+ if (inner_li.worth_versioning_p ())
+ li.subloops_benefit_p = true;
+
+ /* Accumulate the number of instructions from subloops that are not
+ the innermost, or that don't benefit from versioning. Only the
+ instructions from innermost loops that benefit from versioning
+ should be weighed against loop-versioning-max-inner-insns;
+ everything else should be weighed against
+ loop-versioning-max-outer-insns. */
+ if (!inner_li.worth_versioning_p () || inner->inner)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ";; Counting %d instructions from"
+ " loop %d (depth %d) against parent loop %d\n",
+ inner_li.num_insns, inner->num, loop_depth (inner),
+ loop->num);
+ li.num_insns += inner_li.num_insns;
+ }
+ }
+
+ /* Enforce the size limits. */
+ if (li.worth_versioning_p ())
+ {
+ unsigned int max_num_insns = max_insns_for_loop (loop);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ";; Loop %d (depth %d) has %d instructions,"
+ " against a limit of %d\n", loop->num, loop_depth (loop),
+ li.num_insns, max_num_insns);
+ if (li.num_insns > max_num_insns)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ";; Not versioning loop %d (depth %d)"
+ " because it is too big\n", loop->num, loop_depth (loop));
+ return false;
+ }
+ }
+
+ /* Hoist all version checks for subloops to this loop. */
+ for (struct loop *subloop = loop->inner; subloop; subloop = subloop->next)
+ merge_loop_info (loop, subloop);
+
+ return true;
+}
+
+/* Decide which loops to version and add them to the versioning queue.
+ Return true if there are any loops to version. */
+
+bool
+loop_versioning::make_versioning_decisions ()
+{
+ struct loop *loop;
+ FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
+ {
+ loop_info &linfo = get_loop_info (loop);
+ if (decide_whether_loop_is_versionable (loop))
+ {
+ /* Commit to versioning LOOP directly if we can't hoist the
+ version checks any further. */
+ if (linfo.worth_versioning_p ()
+ && (loop_depth (loop) == 1 || linfo.outermost == loop))
+ add_loop_to_queue (loop);
+ }
+ else
+ {
+ /* We can't version this loop, so individually version any
+ subloops that would benefit and haven't been versioned yet. */
+ linfo.rejected_p = true;
+ for (struct loop *subloop = loop->inner; subloop;
+ subloop = subloop->next)
+ if (get_loop_info (subloop).worth_versioning_p ())
+ add_loop_to_queue (subloop);
+ }
+ }
+
+ return !m_loops_to_version.is_empty ();
+}
+
+/* Attempt to implement loop versioning for LOOP, using the information
+ cached in the associated loop_info. Return true on success. */
+
+bool
+loop_versioning::version_loop (struct loop *loop)
+{
+ loop_info &li = get_loop_info (loop);
+
+ /* Not protected by TDF_DETAILS since this is the main piece of
+ information. */
+ if (dump_file)
+ fprintf (dump_file, ";; Versioning loop %d (depth %d)\n",
+ loop->num, loop_depth (loop));
+
+ /* Build up a condition that selects the original loop instead of
+ the simplified loop. */
+ tree cond = boolean_false_node;
+ tree name;
+ unsigned int i;
+ FOR_EACH_VEC_ELT (li.unity_names, i, name)
+ {
+ tree ne_one = fold_build2 (NE_EXPR, boolean_type_node, name,
+ build_one_cst (TREE_TYPE (name)));
+ cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, cond, ne_one);
+ }
+
+ /* Convert the condition into a suitable gcond. */
+ gimple_seq stmts = NULL;
+ cond = force_gimple_operand_1 (cond, &stmts, is_gimple_condexpr, NULL_TREE);
+
+ /* Version the loop. */
+ initialize_original_copy_tables ();
+ basic_block cond_bb;
+ struct loop *else_loop
+ = loop_version (loop, cond, &cond_bb,
+ profile_probability::unlikely (),
+ profile_probability::likely (),
+ profile_probability::unlikely (),
+ profile_probability::likely (), true);
+ free_original_copy_tables ();
+ if (!else_loop)
+ {
+ if (dump_file)
+ fprintf (dump_file, ";; Versioning of loop %d failed\n", loop->num);
+ return false;
+ }
+
+ /* Insert the statements that feed COND. */
+ if (stmts)
+ {
+ gimple_stmt_iterator gsi = gsi_last_bb (cond_bb);
+ gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
+ }
+
+ /* Simplify the new loop, which is used when COND is false. */
+ name_prop (li).substitute_and_fold (else_loop->header);
+ return true;
+}
+
+/* Attempt to version all loops in the versioning queue. Return true
+ if we succeeded for at least one loop. */
+
+bool
+loop_versioning::implement_versioning_decisions ()
+{
+ bool any_succeeded_p = false;
+
+ struct loop *loop;
+ unsigned int i;
+ FOR_EACH_VEC_ELT (m_loops_to_version, i, loop)
+ if (version_loop (loop))
+ any_succeeded_p = true;
+
+ return any_succeeded_p;
+}
+
+/* Run the pass and return a set of TODO_* flags. */
+
+unsigned int
+loop_versioning::run ()
+{
+ gcc_assert (scev_initialized_p ());
+
+ if (!analyze_blocks ()
+ || !prune_conditions ()
+ || !make_versioning_decisions ()
+ || !implement_versioning_decisions ())
+ return 0;
+
+ return TODO_update_ssa;
+}
+
+/* Loop versioningting pass. */
+
+namespace {
+
+const pass_data pass_data_loop_versioning =
+{
+ GIMPLE_PASS, /* type */
+ "lversion", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ TV_LOOP_VERSIONING, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_loop_versioning : public gimple_opt_pass
+{
+public:
+ pass_loop_versioning (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_loop_versioning, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_version_loops_for_strides; }
+ virtual unsigned int execute (function *);
+};
+
+unsigned int
+pass_loop_versioning::execute (function *fn)
+{
+ if (number_of_loops (fn) <= 1)
+ return 0;
+
+ return loop_versioning (fn).run ();
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_loop_versioning (gcc::context *ctxt)
+{
+ return new pass_loop_versioning (ctxt);
+}
Index: gcc/testsuite/gcc.dg/loop-versioning-1.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-1.c 2018-10-24 14:02:15.184152693 +0100
@@ -0,0 +1,20 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* The simplest IV case. */
+
+void
+f1 (double *x, int stepx, int n)
+{
+ for (int i = 0; i < n; ++i)
+ x[stepx * i] = 100;
+}
+
+void
+f2 (double *x, int stepx, int limit)
+{
+ for (int i = 0; i < limit; i += stepx)
+ x[i] = 100;
+}
+
+/* { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 1\)} 2 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Versioning loop} 2 "lversion" } } */
Index: gcc/testsuite/gcc.dg/loop-versioning-10.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-10.c 2018-10-24 14:02:15.184152693 +0100
@@ -0,0 +1,17 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* Test that we can version a gather-like operation in which a variable
+ stride is applied to the index. */
+
+int
+f1 (int *x, int *index, int step, int n)
+{
+ int res = 0;
+ for (int i = 0; i < n; ++i)
+ res += x[index[i] * step];
+ return res;
+}
+
+/* { dg-final { scan-tree-dump-times {Address[^\n]*invariant} 1 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 1\)} 1 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Versioning loop} 1 "lversion" } } */
Index: gcc/testsuite/gcc.dg/loop-versioning-11.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-11.c 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,29 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* Test that we don't try to version for something that is never 1. */
+
+void
+f1 (double *x, int stepx, int n)
+{
+ if (stepx == 1)
+ for (int i = 0; i < n; ++i)
+ x[i] = 100;
+ else
+ for (int i = 0; i < n; ++i)
+ x[stepx * i] = 100;
+}
+
+void
+f2 (double *x, int stepx, int n)
+{
+ if (stepx <= 1)
+ for (int i = 0; i < n; ++i)
+ x[i] = 100;
+ else
+ for (int i = 0; i < n; ++i)
+ x[stepx * i] = 100;
+}
+
+/* { dg-final { scan-tree-dump-times {Want to version loop} 2 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {can never be 1} 2 "lversion" } } */
+/* { dg-final { scan-tree-dump-not {Versioning loop} "lversion" } } */
Index: gcc/testsuite/gcc.dg/loop-versioning-2.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-2.c 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,39 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* Versioning these loops allows loop interchange. */
+
+void
+f1 (double x[][100], int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[j * step][i] = 100;
+}
+
+void
+f2 (double x[][100], int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[j][i * step] = 100;
+}
+
+void
+f3 (double x[][100], int step, int limit)
+{
+ for (int i = 0; i < 100; ++i)
+ for (int j = 0; j < limit; j += step)
+ x[j][i] = 100;
+}
+
+void
+f4 (double x[][100], int step, int limit)
+{
+ for (int i = 0; i < limit; i += step)
+ for (int j = 0; j < 100; ++j)
+ x[j][i] = 100;
+}
+
+/* { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 2\)} 4 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Hoisting check} 4 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Versioning loop [0-9]+ \(depth 1\)} 4 "lversion" } } */
Index: gcc/testsuite/gcc.dg/loop-versioning-3.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-3.c 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,24 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* Versioning these loops for when both steps are 1 allows loop
+ interchange. */
+
+void
+f1 (double x[][100], int step1, int step2, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[j * step1][i * step2] = 100;
+}
+
+void
+f2 (double x[][100], int step1, int step2, int limit)
+{
+ for (int i = 0; i < limit; i += step1)
+ for (int j = 0; j < limit; j += step2)
+ x[j][i] = 100;
+}
+
+/* { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 2\)} 4 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Hoisting check} 4 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Versioning loop} 2 "lversion" } } */
Index: gcc/testsuite/gcc.dg/loop-versioning-4.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-4.c 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,38 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* These shouldn't be versioned; it's extremely likely that the code
+ is emulating two-dimensional arrays. */
+
+void
+f1 (double *x, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[i * step + j] = 100;
+}
+
+void
+f2 (double *x, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[j * step + i] = 100;
+}
+
+void
+f3 (double *x, int *offsets, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[i * step + j + offsets[i]] = 100;
+}
+
+void
+f4 (double *x, int *offsets, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[j * step + i + offsets[i]] = 100;
+}
+
+/* { dg-final { scan-tree-dump-not {Versioning loop} "lversion" } } */
Index: gcc/testsuite/gcc.dg/loop-versioning-5.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-5.c 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,17 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* There's no information about whether STEP1 or STEP2 is innermost,
+ so we should assume the code is sensible and version for the inner
+ evolution, i.e. when STEP2 is 1. */
+
+void
+f1 (double *x, int step1, int step2, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[i * step1 + j * step2] = 100;
+}
+
+/* { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 2\) for when step2} 1 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Want to version loop} 1 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Versioning loop} 1 "lversion" } } */
Index: gcc/testsuite/gcc.dg/loop-versioning-6.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-6.c 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,30 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* The read from y in f1 will be hoisted to the outer loop. In general
+ it's not worth versioning outer loops when the inner loops don't also
+ benefit.
+
+ This test is meant to be a slight counterexample, since versioning
+ does lead to cheaper outer-loop vectorization. However, the benefit
+ isn't enough to justify the cost. */
+
+void
+f1 (double *restrict x, double *restrict y, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[i + j] = y[i * step];
+}
+
+/* A similar example in which the read can't be hoisted, but could
+ for example be handled by vectorizer alias checks. */
+
+void
+f2 (double *x, double *y, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[i + j] = y[i * step];
+}
+
+/* { dg-final { scan-tree-dump-not {Versioning loop} "lversion" } } */
Index: gcc/testsuite/gcc.dg/loop-versioning-7.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-7.c 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,32 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* Check that versioning can handle arrays of structures. */
+
+struct foo {
+ int a, b, c;
+};
+
+void
+f1 (struct foo *x, int stepx, int n)
+{
+ for (int i = 0; i < n; ++i)
+ {
+ x[stepx * i].a = 1;
+ x[stepx * i].b = 2;
+ x[stepx * i].c = 3;
+ }
+}
+
+void
+f2 (struct foo *x, int stepx, int limit)
+{
+ for (int i = 0; i < limit; i += stepx)
+ {
+ x[i].a = 1;
+ x[i].b = 2;
+ x[i].c = 3;
+ }
+}
+
+/* { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 1\)} 2 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Versioning loop} 2 "lversion" } } */
Index: gcc/testsuite/gcc.dg/loop-versioning-8.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-8.c 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,44 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* Check that versioning can handle arrays of structures that wrap
+ subarrays. */
+
+struct foo {
+ int a[100];
+};
+
+void
+f1 (struct foo *x, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[j * step].a[i] = 100;
+}
+
+void
+f2 (struct foo *x, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < n; ++j)
+ x[j].a[i * step] = 100;
+}
+
+void
+f3 (struct foo *x, int step, int limit)
+{
+ for (int i = 0; i < 100; ++i)
+ for (int j = 0; j < limit; j += step)
+ x[j].a[i] = 100;
+}
+
+void
+f4 (struct foo *x, int step, int limit)
+{
+ for (int i = 0; i < limit; i += step)
+ for (int j = 0; j < 100; ++j)
+ x[j].a[i] = 100;
+}
+
+/* { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 2\)} 4 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Hoisting check} 4 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Versioning loop [0-9]+ \(depth 1\)} 4 "lversion" } } */
Index: gcc/testsuite/gcc.dg/loop-versioning-9.c
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gcc.dg/loop-versioning-9.c 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,48 @@
+/* { dg-options "-O3 -fdump-tree-lversion-details" } */
+
+/* Check that versioning can handle small groups of accesses. */
+
+void
+f1 (int *x, int *y, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ x[i] = y[i * step * 2] + y[i * step * 2 + 1];
+}
+
+void
+f2 (int *x, int *y, __INTPTR_TYPE__ step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ x[i] = y[i * step * 2] + y[i * step * 2 + 1];
+}
+
+void
+f3 (int *x, int *y, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ x[i] = y[i * step * 3] + y[i * step * 3 + 2];
+}
+
+void
+f4 (int *x, int *y, __INTPTR_TYPE__ step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ x[i] = y[i * step * 3] + y[i * step * 3 + 2];
+}
+
+void
+f5 (int *x, int *y, int step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ x[i] = y[i * step * 4] + y[i * step * 4 + 3];
+}
+
+void
+f6 (int *x, int *y, __INTPTR_TYPE__ step, int n)
+{
+ for (int i = 0; i < n; ++i)
+ x[i] = y[i * step * 4] + y[i * step * 4 + 3];
+}
+
+/* { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 1\)} 6 "lversion" } } */
+/* { dg-final { scan-tree-dump-times {Versioning loop} 6 "lversion" } } */
Index: gcc/testsuite/gfortran.dg/loop_versioning_1.f90
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gfortran.dg/loop_versioning_1.f90 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,28 @@
+! { dg-options "-O3 -fdump-tree-lversion-details" }
+
+! The simplest IV case.
+
+subroutine f1(x)
+ real :: x(:)
+ x(:) = 100
+end subroutine f1
+
+subroutine f2(x, n, step)
+ integer :: n, step
+ real :: x(n * step)
+ do i = 1, n
+ x(i * step) = 100
+ end do
+end subroutine f2
+
+subroutine f3(x, limit, step)
+ integer :: limit, step
+ real :: x(limit)
+ do i = 1, limit, step
+ x(i) = 100
+ end do
+end subroutine f3
+
+! { dg-final { scan-tree-dump-times {likely to be innermost dimension} 1 "lversion" } }
+! { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 1\)} 3 "lversion" } }
+! { dg-final { scan-tree-dump-times {Versioning loop} 3 "lversion" } }
Index: gcc/testsuite/gfortran.dg/loop_versioning_2.f90
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gfortran.dg/loop_versioning_2.f90 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,38 @@
+! { dg-options "-O3 -fdump-tree-lversion-details -fno-frontend-loop-interchange" }
+
+! We could version the loop for when the first dimension has a stride
+! of 1, but at present there's no real benefit. The gimple loop
+! interchange pass couldn't handle the versioned loop, and interchange
+! is instead done by the frontend (but disabled by the options above).
+
+subroutine f1(x)
+ real :: x(:, :)
+ do i = lbound(x, 1), ubound(x, 1)
+ do j = lbound(x, 2), ubound(x, 2)
+ x(i, j) = 100
+ end do
+ end do
+end subroutine f1
+
+subroutine f2(x, n, step)
+ integer :: n, step
+ real :: x(100, 100)
+ do i = 1, n
+ do j = 1, n
+ x(i * step, j) = 100
+ end do
+ end do
+end subroutine f2
+
+subroutine f3(x, n, step)
+ integer :: n, step
+ real :: x(n * step, n)
+ do i = 1, n
+ do j = 1, n
+ x(i * step, j) = 100
+ end do
+ end do
+end subroutine f3
+
+! { dg-final { scan-tree-dump-times {likely to be innermost dimension} 1 "lversion" } }
+! { dg-final { scan-tree-dump-not {Versioning loop} "lversion" } }
Index: gcc/testsuite/gfortran.dg/loop_versioning_3.f90
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gfortran.dg/loop_versioning_3.f90 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,29 @@
+! { dg-options "-O3 -fdump-tree-lversion-details -fno-frontend-loop-interchange" }
+
+! Test a case in which the outer loop iterates over the inner dimension.
+! The options above prevent the frontend from interchanging the loops.
+
+subroutine f1(x, limit, step, n)
+ integer :: limit, step, n
+ real :: x(limit, n)
+ do i = 1, limit, step
+ do j = 1, n
+ x(i, j) = 100
+ end do
+ end do
+end subroutine f1
+
+subroutine f2(x, n, limit, step)
+ integer :: n, limit, step
+ real :: x(limit, n)
+ do i = 1, n
+ do j = 1, limit, step
+ x(j, i) = 100
+ end do
+ end do
+end subroutine f2
+
+! FIXME: The frontend doesn't give us enough information to tell which loop
+! is iterating over the innermost dimension, so we optimistically
+! assume the inner one is.
+! { dg-final { scan-tree-dump-not {Versioning loop} "lversion" { xfail *-*-* } } }
Index: gcc/testsuite/gfortran.dg/loop_versioning_4.f90
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gfortran.dg/loop_versioning_4.f90 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,52 @@
+! { dg-options "-O3 -fdump-tree-lversion-details -fno-frontend-loop-interchange" }
+
+! Test cases in which versioning is useful for a two-dimensional array.
+
+subroutine f1(x)
+ real :: x(:, :)
+ x(:, :) = 100
+end subroutine f1
+
+subroutine f2(x)
+ real :: x(:, :)
+ do i = lbound(x, 1), ubound(x, 1)
+ do j = lbound(x, 2), ubound(x, 2)
+ x(j, i) = 100
+ end do
+ end do
+end subroutine f2
+
+subroutine f3(x, n, step)
+ integer :: n, step
+ real :: x(100, 100)
+ do i = 1, n
+ do j = 1, n
+ x(j * step, i) = 100
+ end do
+ end do
+end subroutine f3
+
+subroutine f4(x, n, step)
+ integer :: n, step
+ real :: x(n * step, n)
+ do i = 1, n
+ do j = 1, n
+ x(j * step, i) = 100
+ end do
+ end do
+end subroutine f4
+
+subroutine f5(x, n, limit, step)
+ integer :: n, limit, step
+ real :: x(limit, n)
+ do i = 1, n
+ do j = 1, limit, step
+ x(j, i) = 100
+ end do
+ end do
+end subroutine f5
+
+! { dg-final { scan-tree-dump-times {likely to be innermost dimension} 2 "lversion" } }
+! { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 2\)} 5 "lversion" } }
+! { dg-final { scan-tree-dump-times {Hoisting check} 5 "lversion" } }
+! { dg-final { scan-tree-dump-times {Versioning loop [0-9]+ \(depth 1\)} 5 "lversion" } }
Index: gcc/testsuite/gfortran.dg/loop_versioning_5.f90
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gfortran.dg/loop_versioning_5.f90 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,56 @@
+! { dg-options "-O3 -fdump-tree-lversion-details -fno-frontend-loop-interchange" }
+
+! Make sure that in a "badly nested" loop, we don't treat the inner loop
+! as iterating over the inner dimension with a variable stride.
+
+subroutine f1(x, n)
+ integer :: n
+ real :: x(100, 100)
+ do i = 1, n
+ do j = 1, n
+ x(i, j) = 100
+ end do
+ end do
+end subroutine f1
+
+subroutine f2(x, n, step)
+ integer :: n, step
+ real :: x(100, 100)
+ do i = 1, n
+ do j = 1, n
+ x(i, j * step) = 100
+ end do
+ end do
+end subroutine f2
+
+subroutine f3(x, n)
+ integer :: n
+ real :: x(n, n)
+ do i = 1, n
+ do j = 1, n
+ x(i, j) = 100
+ end do
+ end do
+end subroutine f3
+
+subroutine f4(x, n, step)
+ integer :: n, step
+ real :: x(n, n * step)
+ do i = 1, n
+ do j = 1, n
+ x(i, j * step) = 100
+ end do
+ end do
+end subroutine f4
+
+subroutine f5(x, n, limit, step)
+ integer :: n, limit, step
+ real :: x(n, limit)
+ do i = 1, n
+ do j = 1, limit, step
+ x(i, j) = 100
+ end do
+ end do
+end subroutine f5
+
+! { dg-final { scan-tree-dump-not {Versioning loop} "lversion" } }
Index: gcc/testsuite/gfortran.dg/loop_versioning_6.f90
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gfortran.dg/loop_versioning_6.f90 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,93 @@
+! { dg-options "-O3 -fdump-tree-lversion-details" }
+
+! Check that versioning can handle small groups of accesses.
+
+subroutine f1(x)
+ real :: x(:)
+ do i = lbound(x, 1), ubound(x, 1) / 2
+ x(i * 2) = 100
+ x(i * 2 + 1) = 101
+ end do
+end subroutine f1
+
+subroutine f2(x, n, step)
+ integer :: n, step
+ real :: x(n * step * 2)
+ do i = 1, n
+ x(i * step * 2) = 100
+ x(i * step * 2 + 1) = 101
+ end do
+end subroutine f2
+
+subroutine f3(x, limit, step)
+ integer :: limit, step
+ real :: x(limit * 2)
+ do i = 1, limit, step
+ x(i * 2) = 100
+ x(i * 2 + 1) = 101
+ end do
+end subroutine f3
+
+subroutine f4(x)
+ real :: x(:)
+ do i = lbound(x, 1), ubound(x, 1) / 3
+ x(i * 3) = 100
+ x(i * 3 + 1) = 101
+ x(i * 3 + 2) = 102
+ end do
+end subroutine f4
+
+subroutine f5(x, n, step)
+ integer :: n, step
+ real :: x(n * step * 3)
+ do i = 1, n
+ x(i * step * 3) = 100
+ x(i * step * 3 + 1) = 101
+ x(i * step * 3 + 2) = 102
+ end do
+end subroutine f5
+
+subroutine f6(x, limit, step)
+ integer :: limit, step
+ real :: x(limit * 3)
+ do i = 1, limit, step
+ x(i * 3) = 100
+ x(i * 3 + 1) = 101
+ x(i * 3 + 2) = 102
+ end do
+end subroutine f6
+
+subroutine f7(x)
+ real :: x(:)
+ do i = lbound(x, 1), ubound(x, 1) / 4
+ x(i * 4) = 100
+ x(i * 4 + 1) = 101
+ x(i * 4 + 2) = 102
+ x(i * 4 + 3) = 103
+ end do
+end subroutine f7
+
+subroutine f8(x, n, step)
+ integer :: n, step
+ real :: x(n * step * 4)
+ do i = 1, n
+ x(i * step * 4) = 100
+ x(i * step * 4 + 1) = 101
+ x(i * step * 4 + 2) = 102
+ x(i * step * 4 + 3) = 103
+ end do
+end subroutine f8
+
+subroutine f9(x, limit, step)
+ integer :: limit, step
+ real :: x(limit * 4)
+ do i = 1, limit, step
+ x(i * 4) = 100
+ x(i * 4 + 1) = 101
+ x(i * 4 + 2) = 102
+ x(i * 4 + 3) = 103
+ end do
+end subroutine f9
+
+! { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 1\)} 9 "lversion" } }
+! { dg-final { scan-tree-dump-times {Versioning loop} 9 "lversion" } }
Index: gcc/testsuite/gfortran.dg/loop_versioning_7.f90
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gfortran.dg/loop_versioning_7.f90 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,67 @@
+! { dg-options "-O3 -fdump-tree-lversion-details" }
+
+! Check that versioning can handle small groups of accesses, with the
+! group being a separate array dimension.
+
+subroutine f1(x, n, step)
+ integer :: n, step
+ real :: x(2, n * step)
+ do i = 1, n
+ x(1, i * step) = 100
+ x(2, i * step) = 101
+ end do
+end subroutine f1
+
+subroutine f2(x, limit, step)
+ integer :: limit, step
+ real :: x(2, limit)
+ do i = 1, limit, step
+ x(1, i) = 100
+ x(2, i) = 101
+ end do
+end subroutine f2
+
+subroutine f3(x, n, step)
+ integer :: n, step
+ real :: x(3, n * step)
+ do i = 1, n
+ x(1, i * step) = 100
+ x(2, i * step) = 101
+ x(3, i * step) = 102
+ end do
+end subroutine f3
+
+subroutine f4(x, limit, step)
+ integer :: limit, step
+ real :: x(3, limit)
+ do i = 1, limit, step
+ x(1, i) = 100
+ x(2, i) = 101
+ x(3, i) = 102
+ end do
+end subroutine f4
+
+subroutine f5(x, n, step)
+ integer :: n, step
+ real :: x(4, n * step)
+ do i = 1, n
+ x(1, i * step) = 100
+ x(2, i * step) = 101
+ x(3, i * step) = 102
+ x(4, i * step) = 103
+ end do
+end subroutine f5
+
+subroutine f6(x, limit, step)
+ integer :: limit, step
+ real :: x(4, limit)
+ do i = 1, limit, step
+ x(1, i) = 100
+ x(2, i) = 101
+ x(3, i) = 102
+ x(4, i) = 103
+ end do
+end subroutine f6
+
+! { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 1\)} 6 "lversion" } }
+! { dg-final { scan-tree-dump-times {Versioning loop} 6 "lversion" } }
Index: gcc/testsuite/gfortran.dg/loop_versioning_8.f90
===================================================================
--- /dev/null 2018-09-14 11:16:31.122530289 +0100
+++ gcc/testsuite/gfortran.dg/loop_versioning_8.f90 2018-10-24 14:02:15.188152659 +0100
@@ -0,0 +1,13 @@
+! { dg-options "-O3 -fdump-tree-lversion-details" }
+
+! Check that versioning is applied to a gather-like reduction operation.
+
+function f(x, index, n)
+ integer :: n
+ real :: x(:)
+ integer :: index(n)
+ f = sum(x(index(:)))
+end function f
+
+! { dg-final { scan-tree-dump-times {Want to version loop [0-9]+ \(depth 1\)} 1 "lversion" } }
+! { dg-final { scan-tree-dump-times {Versioning loop} 1 "lversion" } }
More information about the Gcc-patches
mailing list