Add a loop versioning pass

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.

2018-12-17  Richard Sandiford  <richard.sandiford@arm.com>
	    Ramana Radhakrishnan  <ramana.radhakrishnan@arm.com>
	    Kyrylo Tkachov  <kyrylo.tkachov@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.

From-SVN: r267197

1 files changed, 15 insertions, 3 deletions

diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index 1f3ccaf..8225ebe 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -1154,6 +1154,10 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
 
 
 /* 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
@@ -1170,16 +1174,24 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
    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.