This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Gimple loop splitting v2


On Mon, Jul 25, 2016 at 10:57 PM, Andrew Pinski <pinskia@gmail.com> wrote:
> On Wed, Dec 2, 2015 at 5:23 AM, Michael Matz <matz@suse.de> wrote:
>> Hi,
>>
>> On Tue, 1 Dec 2015, Jeff Law wrote:
>>
>>> > So, okay for trunk?
>>> -ENOPATCH
>>
>> Sigh :)
>> Here it is.
>
>
> I found one problem with it.
> Take:
> void f(int *a, int M, int *b)
> {
>   for(int i = 0; i <= M; i++)
>     {
>        if (i < M)
>         a[i] = i;
>     }
> }
> ---- CUT ---
> There are two issues with the code as below.  The outer most loop's
> aux is still set which causes the vectorizer not to vector the loop.
> The other issue is I need to run pass_scev_cprop after pass_loop_split
> to get the induction variable usage after the loop gone so the
> vectorizer will work.

I think scev_cprop needs to be re-written to an utility so that the vectorizer
itself can (within its own cost-model) eliminate an induction using it.

Richard.

> Something like (note this is copy and paste from a terminal):
> diff --git a/gcc/passes.def b/gcc/passes.def
> index c327900..e8d6ea6 100644
> --- a/gcc/passes.def
> +++ b/gcc/passes.def
> @@ -262,8 +262,8 @@ along with GCC; see the file COPYING3.  If not see
>           NEXT_PASS (pass_copy_prop);
>           NEXT_PASS (pass_dce);
>           NEXT_PASS (pass_tree_unswitch);
> -         NEXT_PASS (pass_scev_cprop);
>           NEXT_PASS (pass_loop_split);
> +         NEXT_PASS (pass_scev_cprop);
>           NEXT_PASS (pass_record_bounds);
>           NEXT_PASS (pass_loop_distribution);
>           NEXT_PASS (pass_copy_prop);
> diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c
> index 5411530..e72ef19 100644
> --- a/gcc/tree-ssa-loop-split.c
> +++ b/gcc/tree-ssa-loop-split.c
> @@ -592,7 +592,11 @@ tree_ssa_split_loops (void)
>
>    gcc_assert (scev_initialized_p ());
>    FOR_EACH_LOOP (loop, 0)
> -    loop->aux = NULL;
> +    {
> +      loop->aux = NULL;
> +      if (loop_outer (loop))
> +       loop_outer (loop)->aux = NULL;
> +    }

How does the iterator not visit loop_outer (loop)?!

>
>    /* Go through all loops starting from innermost.  */
>    FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
> @@ -631,7 +635,11 @@ tree_ssa_split_loops (void)
>      }
>
>    FOR_EACH_LOOP (loop, 0)
> -    loop->aux = NULL;
> +    {
> +      loop->aux = NULL;
> +      if (loop_outer (loop))
> +       loop_outer (loop)->aux = NULL;
> +    }
>
>    if (changed)
>      return TODO_cleanup_cfg;
> -----  CUT -----
>
> Thanks,
> Andrew
>
>
>>
>>
>> Ciao,
>> Michael.
>>         * common.opt (-fsplit-loops): New flag.
>>         * passes.def (pass_loop_split): Add.
>>         * opts.c (default_options_table): Add OPT_fsplit_loops entry at -O3.
>>         (enable_fdo_optimizations): Add loop splitting.
>>         * timevar.def (TV_LOOP_SPLIT): Add.
>>         * tree-pass.h (make_pass_loop_split): Declare.
>>         * tree-ssa-loop-manip.h (rewrite_into_loop_closed_ssa_1): Declare.
>>         * tree-ssa-loop-unswitch.c: Include tree-ssa-loop-manip.h,
>>         * tree-ssa-loop-split.c: New file.
>>         * Makefile.in (OBJS): Add tree-ssa-loop-split.o.
>>         * doc/invoke.texi (fsplit-loops): Document.
>>         * doc/passes.texi (Loop optimization): Add paragraph about loop
>>         splitting.
>>
>> testsuite/
>>         * gcc.dg/loop-split.c: New test.
>>
>> Index: common.opt
>> ===================================================================
>> --- common.opt  (revision 231115)
>> +++ common.opt  (working copy)
>> @@ -2453,6 +2457,10 @@ funswitch-loops
>>  Common Report Var(flag_unswitch_loops) Optimization
>>  Perform loop unswitching.
>>
>> +fsplit-loops
>> +Common Report Var(flag_split_loops) Optimization
>> +Perform loop splitting.
>> +
>>  funwind-tables
>>  Common Report Var(flag_unwind_tables) Optimization
>>  Just generate unwind tables for exception handling.
>> Index: passes.def
>> ===================================================================
>> --- passes.def  (revision 231115)
>> +++ passes.def  (working copy)
>> @@ -252,6 +252,7 @@ along with GCC; see the file COPYING3.
>>           NEXT_PASS (pass_dce);
>>           NEXT_PASS (pass_tree_unswitch);
>>           NEXT_PASS (pass_scev_cprop);
>> +         NEXT_PASS (pass_loop_split);
>>           NEXT_PASS (pass_record_bounds);
>>           NEXT_PASS (pass_loop_distribution);
>>           NEXT_PASS (pass_copy_prop);
>> Index: opts.c
>> ===================================================================
>> --- opts.c      (revision 231115)
>> +++ opts.c      (working copy)
>> @@ -532,6 +532,7 @@ static const struct default_options defa
>>         regardless of them being declared inline.  */
>>      { OPT_LEVELS_3_PLUS_AND_SIZE, OPT_finline_functions, NULL, 1 },
>>      { OPT_LEVELS_1_PLUS_NOT_DEBUG, OPT_finline_functions_called_once, NULL, 1 },
>> +    { OPT_LEVELS_3_PLUS, OPT_fsplit_loops, NULL, 1 },
>>      { OPT_LEVELS_3_PLUS, OPT_funswitch_loops, NULL, 1 },
>>      { OPT_LEVELS_3_PLUS, OPT_fgcse_after_reload, NULL, 1 },
>>      { OPT_LEVELS_3_PLUS, OPT_ftree_loop_vectorize, NULL, 1 },
>> @@ -1411,6 +1412,8 @@ enable_fdo_optimizations (struct gcc_opt
>>      opts->x_flag_ipa_cp_alignment = value;
>>    if (!opts_set->x_flag_predictive_commoning)
>>      opts->x_flag_predictive_commoning = value;
>> +  if (!opts_set->x_flag_split_loops)
>> +    opts->x_flag_split_loops = value;
>>    if (!opts_set->x_flag_unswitch_loops)
>>      opts->x_flag_unswitch_loops = value;
>>    if (!opts_set->x_flag_gcse_after_reload)
>> Index: timevar.def
>> ===================================================================
>> --- timevar.def (revision 231115)
>> +++ timevar.def (working copy)
>> @@ -182,6 +182,7 @@ DEFTIMEVAR (TV_LIM                   , "
>>  DEFTIMEVAR (TV_TREE_LOOP_IVCANON     , "tree canonical iv")
>>  DEFTIMEVAR (TV_SCEV_CONST            , "scev constant prop")
>>  DEFTIMEVAR (TV_TREE_LOOP_UNSWITCH    , "tree loop unswitching")
>> +DEFTIMEVAR (TV_LOOP_SPLIT            , "loop splitting")
>>  DEFTIMEVAR (TV_COMPLETE_UNROLL       , "complete unrolling")
>>  DEFTIMEVAR (TV_TREE_PARALLELIZE_LOOPS, "tree parallelize loops")
>>  DEFTIMEVAR (TV_TREE_VECTORIZATION    , "tree vectorization")
>> Index: tree-pass.h
>> ===================================================================
>> --- tree-pass.h (revision 231115)
>> +++ tree-pass.h (working copy)
>> @@ -370,6 +370,7 @@ extern gimple_opt_pass *make_pass_tree_n
>>  extern gimple_opt_pass *make_pass_tree_loop_init (gcc::context *ctxt);
>>  extern gimple_opt_pass *make_pass_lim (gcc::context *ctxt);
>>  extern gimple_opt_pass *make_pass_tree_unswitch (gcc::context *ctxt);
>> +extern gimple_opt_pass *make_pass_loop_split (gcc::context *ctxt);
>>  extern gimple_opt_pass *make_pass_predcom (gcc::context *ctxt);
>>  extern gimple_opt_pass *make_pass_iv_canon (gcc::context *ctxt);
>>  extern gimple_opt_pass *make_pass_scev_cprop (gcc::context *ctxt);
>> Index: tree-ssa-loop-manip.h
>> ===================================================================
>> --- tree-ssa-loop-manip.h       (revision 231115)
>> +++ tree-ssa-loop-manip.h       (working copy)
>> @@ -24,6 +24,8 @@ typedef void (*transform_callback)(struc
>>
>>  extern void create_iv (tree, tree, tree, struct loop *, gimple_stmt_iterator *,
>>                        bool, tree *, tree *);
>> +extern void rewrite_into_loop_closed_ssa_1 (bitmap, unsigned, int,
>> +                                           struct loop *);
>>  extern void rewrite_into_loop_closed_ssa (bitmap, unsigned);
>>  extern void rewrite_virtuals_into_loop_closed_ssa (struct loop *);
>>  extern void verify_loop_closed_ssa (bool);
>> Index: Makefile.in
>> ===================================================================
>> --- Makefile.in (revision 231115)
>> +++ Makefile.in (working copy)
>> @@ -1474,6 +1474,7 @@ OBJS = \
>>         tree-ssa-loop-manip.o \
>>         tree-ssa-loop-niter.o \
>>         tree-ssa-loop-prefetch.o \
>> +       tree-ssa-loop-split.o \
>>         tree-ssa-loop-unswitch.o \
>>         tree-ssa-loop.o \
>>         tree-ssa-math-opts.o \
>> Index: tree-ssa-loop-split.c
>> ===================================================================
>> --- tree-ssa-loop-split.c       (revision 0)
>> +++ tree-ssa-loop-split.c       (working copy)
>> @@ -0,0 +1,686 @@
>> +/* Loop splitting.
>> +   Copyright (C) 2015 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 "tree-pass.h"
>> +#include "ssa.h"
>> +#include "fold-const.h"
>> +#include "tree-cfg.h"
>> +#include "tree-ssa.h"
>> +#include "tree-ssa-loop-niter.h"
>> +#include "tree-ssa-loop.h"
>> +#include "tree-ssa-loop-manip.h"
>> +#include "tree-into-ssa.h"
>> +#include "cfgloop.h"
>> +#include "tree-scalar-evolution.h"
>> +#include "gimple-iterator.h"
>> +#include "gimple-pretty-print.h"
>> +#include "cfghooks.h"
>> +#include "gimple-fold.h"
>> +#include "gimplify-me.h"
>> +
>> +/* This file implements loop splitting, i.e. transformation of loops like
>> +
>> +   for (i = 0; i < 100; i++)
>> +     {
>> +       if (i < 50)
>> +         A;
>> +       else
>> +         B;
>> +     }
>> +
>> +   into:
>> +
>> +   for (i = 0; i < 50; i++)
>> +     {
>> +       A;
>> +     }
>> +   for (; i < 100; i++)
>> +     {
>> +       B;
>> +     }
>> +
>> +   */
>> +
>> +/* Return true when BB inside LOOP is a potential iteration space
>> +   split point, i.e. ends with a condition like "IV < comp", which
>> +   is true on one side of the iteration space and false on the other,
>> +   and the split point can be computed.  If so, also return the border
>> +   point in *BORDER and the comparison induction variable in IV.  */
>> +
>> +static tree
>> +split_at_bb_p (struct loop *loop, basic_block bb, tree *border, affine_iv *iv)
>> +{
>> +  gimple *last;
>> +  gcond *stmt;
>> +  affine_iv iv2;
>> +
>> +  /* BB must end in a simple conditional jump.  */
>> +  last = last_stmt (bb);
>> +  if (!last || gimple_code (last) != GIMPLE_COND)
>> +    return NULL_TREE;
>> +  stmt = as_a <gcond *> (last);
>> +
>> +  enum tree_code code = gimple_cond_code (stmt);
>> +
>> +  /* Only handle relational comparisons, for equality and non-equality
>> +     we'd have to split the loop into two loops and a middle statement.  */
>> +  switch (code)
>> +    {
>> +      case LT_EXPR:
>> +      case LE_EXPR:
>> +      case GT_EXPR:
>> +      case GE_EXPR:
>> +       break;
>> +      default:
>> +       return NULL_TREE;
>> +    }
>> +
>> +  if (loop_exits_from_bb_p (loop, bb))
>> +    return NULL_TREE;
>> +
>> +  tree op0 = gimple_cond_lhs (stmt);
>> +  tree op1 = gimple_cond_rhs (stmt);
>> +
>> +  if (!simple_iv (loop, loop, op0, iv, false))
>> +    return NULL_TREE;
>> +  if (!simple_iv (loop, loop, op1, &iv2, false))
>> +    return NULL_TREE;
>> +
>> +  /* Make it so, that the first argument of the condition is
>> +     the looping one (only swap.  */
>> +  if (!integer_zerop (iv2.step))
>> +    {
>> +      std::swap (op0, op1);
>> +      std::swap (*iv, iv2);
>> +      code = swap_tree_comparison (code);
>> +      gimple_cond_set_condition (stmt, code, op0, op1);
>> +      update_stmt (stmt);
>> +    }
>> +  else if (integer_zerop (iv->step))
>> +    return NULL_TREE;
>> +  if (!integer_zerop (iv2.step))
>> +    return NULL_TREE;
>> +
>> +  if (dump_file && (dump_flags & TDF_DETAILS))
>> +    {
>> +      fprintf (dump_file, "Found potential split point: ");
>> +      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
>> +      fprintf (dump_file, " { ");
>> +      print_generic_expr (dump_file, iv->base, TDF_SLIM);
>> +      fprintf (dump_file, " + I*");
>> +      print_generic_expr (dump_file, iv->step, TDF_SLIM);
>> +      fprintf (dump_file, " } %s ", get_tree_code_name (code));
>> +      print_generic_expr (dump_file, iv2.base, TDF_SLIM);
>> +      fprintf (dump_file, "\n");
>> +    }
>> +
>> +  *border = iv2.base;
>> +  return op0;
>> +}
>> +
>> +/* Given a GUARD conditional stmt inside LOOP, which we want to make always
>> +   true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL
>> +   (a post-increment IV) and NEWBOUND (the comparator) adjust the loop
>> +   exit test statement to loop back only if the GUARD statement will
>> +   also be true/false in the next iteration.  */
>> +
>> +static void
>> +patch_loop_exit (struct loop *loop, gcond *guard, tree nextval, tree newbound,
>> +                bool initial_true)
>> +{
>> +  edge exit = single_exit (loop);
>> +  gcond *stmt = as_a <gcond *> (last_stmt (exit->src));
>> +  gimple_cond_set_condition (stmt, gimple_cond_code (guard),
>> +                            nextval, newbound);
>> +  update_stmt (stmt);
>> +
>> +  edge stay = single_pred_edge (loop->latch);
>> +
>> +  exit->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
>> +  stay->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
>> +
>> +  if (initial_true)
>> +    {
>> +      exit->flags |= EDGE_FALSE_VALUE;
>> +      stay->flags |= EDGE_TRUE_VALUE;
>> +    }
>> +  else
>> +    {
>> +      exit->flags |= EDGE_TRUE_VALUE;
>> +      stay->flags |= EDGE_FALSE_VALUE;
>> +    }
>> +}
>> +
>> +/* Give an induction variable GUARD_IV, and its affine descriptor IV,
>> +   find the loop phi node in LOOP defining it directly, or create
>> +   such phi node.  Return that phi node.  */
>> +
>> +static gphi *
>> +find_or_create_guard_phi (struct loop *loop, tree guard_iv, affine_iv * /*iv*/)
>> +{
>> +  gimple *def = SSA_NAME_DEF_STMT (guard_iv);
>> +  gphi *phi;
>> +  if ((phi = dyn_cast <gphi *> (def))
>> +      && gimple_bb (phi) == loop->header)
>> +    return phi;
>> +
>> +  /* XXX Create the PHI instead.  */
>> +  return NULL;
>> +}
>> +
>> +/* This function updates the SSA form after connect_loops made a new
>> +   edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate
>> +   conditional).  I.e. the second loop can now be entered either
>> +   via the original entry or via NEW_E, so the entry values of LOOP2
>> +   phi nodes are either the original ones or those at the exit
>> +   of LOOP1.  Insert new phi nodes in LOOP2 pre-header reflecting
>> +   this.  */
>> +
>> +static void
>> +connect_loop_phis (struct loop *loop1, struct loop *loop2, edge new_e)
>> +{
>> +  basic_block rest = loop_preheader_edge (loop2)->src;
>> +  gcc_assert (new_e->dest == rest);
>> +  edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e);
>> +
>> +  edge firste = loop_preheader_edge (loop1);
>> +  edge seconde = loop_preheader_edge (loop2);
>> +  edge firstn = loop_latch_edge (loop1);
>> +  gphi_iterator psi_first, psi_second;
>> +  for (psi_first = gsi_start_phis (loop1->header),
>> +       psi_second = gsi_start_phis (loop2->header);
>> +       !gsi_end_p (psi_first);
>> +       gsi_next (&psi_first), gsi_next (&psi_second))
>> +    {
>> +      tree init, next, new_init;
>> +      use_operand_p op;
>> +      gphi *phi_first = psi_first.phi ();
>> +      gphi *phi_second = psi_second.phi ();
>> +
>> +      init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste);
>> +      next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn);
>> +      op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde);
>> +      gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
>> +
>> +      /* Prefer using original variable as a base for the new ssa name.
>> +        This is necessary for virtual ops, and useful in order to avoid
>> +        losing debug info for real ops.  */
>> +      if (TREE_CODE (next) == SSA_NAME
>> +         && useless_type_conversion_p (TREE_TYPE (next),
>> +                                       TREE_TYPE (init)))
>> +       new_init = copy_ssa_name (next);
>> +      else if (TREE_CODE (init) == SSA_NAME
>> +              && useless_type_conversion_p (TREE_TYPE (init),
>> +                                            TREE_TYPE (next)))
>> +       new_init = copy_ssa_name (init);
>> +      else if (useless_type_conversion_p (TREE_TYPE (next),
>> +                                         TREE_TYPE (init)))
>> +       new_init = make_temp_ssa_name (TREE_TYPE (next), NULL,
>> +                                      "unrinittmp");
>> +      else
>> +       new_init = make_temp_ssa_name (TREE_TYPE (init), NULL,
>> +                                      "unrinittmp");
>> +
>> +      gphi * newphi = create_phi_node (new_init, rest);
>> +      add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION);
>> +      add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION);
>> +      SET_USE (op, new_init);
>> +    }
>> +}
>> +
>> +/* The two loops LOOP1 and LOOP2 were just created by loop versioning,
>> +   they are still equivalent and placed in two arms of a diamond, like so:
>> +
>> +               .------if (cond)------.
>> +               v                     v
>> +             pre1                   pre2
>> +              |                      |
>> +        .--->h1                     h2<----.
>> +        |     |                      |     |
>> +        |    ex1---.            .---ex2    |
>> +        |    /     |            |     \    |
>> +        '---l1     X            |     l2---'
>> +                   |            |
>> +                   |            |
>> +                   '--->join<---'
>> +
>> +   This function transforms the program such that LOOP1 is conditionally
>> +   falling through to LOOP2, or skipping it.  This is done by splitting
>> +   the ex1->join edge at X in the diagram above, and inserting a condition
>> +   whose one arm goes to pre2, resulting in this situation:
>> +
>> +               .------if (cond)------.
>> +               v                     v
>> +             pre1       .---------->pre2
>> +              |         |            |
>> +        .--->h1         |           h2<----.
>> +        |     |         |            |     |
>> +        |    ex1---.    |       .---ex2    |
>> +        |    /     v    |       |     \    |
>> +        '---l1   skip---'       |     l2---'
>> +                   |            |
>> +                   |            |
>> +                   '--->join<---'
>> +
>> +
>> +   The condition used is the exit condition of LOOP1, which effectively means
>> +   that when the first loop exits (for whatever reason) but the real original
>> +   exit expression is still false the second loop will be entered.
>> +   The function returns the new edge cond->pre2.
>> +
>> +   This doesn't update the SSA form, see connect_loop_phis for that.  */
>> +
>> +static edge
>> +connect_loops (struct loop *loop1, struct loop *loop2)
>> +{
>> +  edge exit = single_exit (loop1);
>> +  basic_block skip_bb = split_edge (exit);
>> +  gcond *skip_stmt;
>> +  gimple_stmt_iterator gsi;
>> +  edge new_e, skip_e;
>> +
>> +  gimple *stmt = last_stmt (exit->src);
>> +  skip_stmt = gimple_build_cond (gimple_cond_code (stmt),
>> +                                gimple_cond_lhs (stmt),
>> +                                gimple_cond_rhs (stmt),
>> +                                NULL_TREE, NULL_TREE);
>> +  gsi = gsi_last_bb (skip_bb);
>> +  gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT);
>> +
>> +  skip_e = EDGE_SUCC (skip_bb, 0);
>> +  skip_e->flags &= ~EDGE_FALLTHRU;
>> +  new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0);
>> +  if (exit->flags & EDGE_TRUE_VALUE)
>> +    {
>> +      skip_e->flags |= EDGE_TRUE_VALUE;
>> +      new_e->flags |= EDGE_FALSE_VALUE;
>> +    }
>> +  else
>> +    {
>> +      skip_e->flags |= EDGE_FALSE_VALUE;
>> +      new_e->flags |= EDGE_TRUE_VALUE;
>> +    }
>> +
>> +  new_e->count = skip_bb->count;
>> +  new_e->probability = PROB_LIKELY;
>> +  new_e->count = apply_probability (skip_e->count, PROB_LIKELY);
>> +  skip_e->count -= new_e->count;
>> +  skip_e->probability = inverse_probability (PROB_LIKELY);
>> +
>> +  return new_e;
>> +}
>> +
>> +/* This returns the new bound for iterations given the original iteration
>> +   space in NITER, an arbitrary new bound BORDER, assumed to be some
>> +   comparison value with a different IV, the initial value GUARD_INIT of
>> +   that other IV, and the comparison code GUARD_CODE that compares
>> +   that other IV with BORDER.  We return an SSA name, and place any
>> +   necessary statements for that computation into *STMTS.
>> +
>> +   For example for such a loop:
>> +
>> +     for (i = beg, j = guard_init; i < end; i++, j++)
>> +       if (j < border)  // this is supposed to be true/false
>> +         ...
>> +
>> +   we want to return a new bound (on j) that makes the loop iterate
>> +   as long as the condition j < border stays true.  We also don't want
>> +   to iterate more often than the original loop, so we have to introduce
>> +   some cut-off as well (via min/max), effectively resulting in:
>> +
>> +     newend = min (end+guard_init-beg, border)
>> +     for (i = beg; j = guard_init; j < newend; i++, j++)
>> +       if (j < c)
>> +         ...
>> +
>> +   Depending on the direction of the IVs and if the exit tests
>> +   are strict or non-strict we need to use MIN or MAX,
>> +   and add or subtract 1.  This routine computes newend above.  */
>> +
>> +static tree
>> +compute_new_first_bound (gimple_seq *stmts, struct tree_niter_desc *niter,
>> +                        tree border,
>> +                        enum tree_code guard_code, tree guard_init)
>> +{
>> +  /* The niter structure contains the after-increment IV, we need
>> +     the loop-enter base, so subtract STEP once.  */
>> +  tree controlbase = force_gimple_operand (niter->control.base,
>> +                                          stmts, true, NULL_TREE);
>> +  tree controlstep = niter->control.step;
>> +  tree enddiff;
>> +  if (POINTER_TYPE_P (TREE_TYPE (controlbase)))
>> +    {
>> +      controlstep = gimple_build (stmts, NEGATE_EXPR,
>> +                                 TREE_TYPE (controlstep), controlstep);
>> +      enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
>> +                             TREE_TYPE (controlbase),
>> +                             controlbase, controlstep);
>> +    }
>> +  else
>> +    enddiff = gimple_build (stmts, MINUS_EXPR,
>> +                           TREE_TYPE (controlbase),
>> +                           controlbase, controlstep);
>> +
>> +  /* Compute beg-guard_init.  */
>> +  if (POINTER_TYPE_P (TREE_TYPE (enddiff)))
>> +    {
>> +      tree tem = gimple_convert (stmts, sizetype, guard_init);
>> +      tem = gimple_build (stmts, NEGATE_EXPR, sizetype, tem);
>> +      enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
>> +                             TREE_TYPE (enddiff),
>> +                             enddiff, tem);
>> +    }
>> +  else
>> +    enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff),
>> +                           enddiff, guard_init);
>> +
>> +  /* Compute end-(beg-guard_init).  */
>> +  gimple_seq stmts2;
>> +  tree newbound = force_gimple_operand (niter->bound, &stmts2,
>> +                                       true, NULL_TREE);
>> +  gimple_seq_add_seq_without_update (stmts, stmts2);
>> +
>> +  if (POINTER_TYPE_P (TREE_TYPE (enddiff))
>> +      || POINTER_TYPE_P (TREE_TYPE (newbound)))
>> +    {
>> +      enddiff = gimple_convert (stmts, sizetype, enddiff);
>> +      enddiff = gimple_build (stmts, NEGATE_EXPR, sizetype, enddiff);
>> +      newbound = gimple_build (stmts, POINTER_PLUS_EXPR,
>> +                              TREE_TYPE (newbound),
>> +                              newbound, enddiff);
>> +    }
>> +  else
>> +    newbound = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff),
>> +                            newbound, enddiff);
>> +
>> +  /* Depending on the direction of the IVs the new bound for the first
>> +     loop is the minimum or maximum of old bound and border.
>> +     Also, if the guard condition isn't strictly less or greater,
>> +     we need to adjust the bound.  */
>> +  int addbound = 0;
>> +  enum tree_code minmax;
>> +  if (niter->cmp == LT_EXPR)
>> +    {
>> +      /* GT and LE are the same, inverted.  */
>> +      if (guard_code == GT_EXPR || guard_code == LE_EXPR)
>> +       addbound = -1;
>> +      minmax = MIN_EXPR;
>> +    }
>> +  else
>> +    {
>> +      gcc_assert (niter->cmp == GT_EXPR);
>> +      if (guard_code == GE_EXPR || guard_code == LT_EXPR)
>> +       addbound = 1;
>> +      minmax = MAX_EXPR;
>> +    }
>> +
>> +  if (addbound)
>> +    {
>> +      tree type2 = TREE_TYPE (newbound);
>> +      if (POINTER_TYPE_P (type2))
>> +       type2 = sizetype;
>> +      newbound = gimple_build (stmts,
>> +                              POINTER_TYPE_P (TREE_TYPE (newbound))
>> +                              ? POINTER_PLUS_EXPR : PLUS_EXPR,
>> +                              TREE_TYPE (newbound),
>> +                              newbound,
>> +                              build_int_cst (type2, addbound));
>> +    }
>> +
>> +  tree newend = gimple_build (stmts, minmax, TREE_TYPE (border),
>> +                             border, newbound);
>> +  return newend;
>> +}
>> +
>> +/* Checks if LOOP contains an conditional block whose condition
>> +   depends on which side in the iteration space it is, and if so
>> +   splits the iteration space into two loops.  Returns true if the
>> +   loop was split.  NITER must contain the iteration descriptor for the
>> +   single exit of LOOP.  */
>> +
>> +static bool
>> +split_loop (struct loop *loop1, struct tree_niter_desc *niter)
>> +{
>> +  basic_block *bbs;
>> +  unsigned i;
>> +  bool changed = false;
>> +  tree guard_iv;
>> +  tree border;
>> +  affine_iv iv;
>> +
>> +  bbs = get_loop_body (loop1);
>> +
>> +  /* Find a splitting opportunity.  */
>> +  for (i = 0; i < loop1->num_nodes; i++)
>> +    if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv)))
>> +      {
>> +       /* Handling opposite steps is not implemented yet.  Neither
>> +          is handling different step sizes.  */
>> +       if ((tree_int_cst_sign_bit (iv.step)
>> +            != tree_int_cst_sign_bit (niter->control.step))
>> +           || !tree_int_cst_equal (iv.step, niter->control.step))
>> +         continue;
>> +
>> +       /* Find a loop PHI node that defines guard_iv directly,
>> +          or create one doing that.  */
>> +       gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv);
>> +       if (!phi)
>> +         continue;
>> +       gcond *guard_stmt = as_a<gcond *> (last_stmt (bbs[i]));
>> +       tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi,
>> +                                                loop_preheader_edge (loop1));
>> +       enum tree_code guard_code = gimple_cond_code (guard_stmt);
>> +
>> +       /* Loop splitting is implemented by versioning the loop, placing
>> +          the new loop after the old loop, make the first loop iterate
>> +          as long as the conditional stays true (or false) and let the
>> +          second (new) loop handle the rest of the iterations.
>> +
>> +          First we need to determine if the condition will start being true
>> +          or false in the first loop.  */
>> +       bool initial_true;
>> +       switch (guard_code)
>> +         {
>> +           case LT_EXPR:
>> +           case LE_EXPR:
>> +             initial_true = !tree_int_cst_sign_bit (iv.step);
>> +             break;
>> +           case GT_EXPR:
>> +           case GE_EXPR:
>> +             initial_true = tree_int_cst_sign_bit (iv.step);
>> +             break;
>> +           default:
>> +             gcc_unreachable ();
>> +         }
>> +
>> +       /* Build a condition that will skip the first loop when the
>> +          guard condition won't ever be true (or false).  */
>> +       gimple_seq stmts2;
>> +       border = force_gimple_operand (border, &stmts2, true, NULL_TREE);
>> +       if (stmts2)
>> +         gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
>> +                                           stmts2);
>> +       tree cond = build2 (guard_code, boolean_type_node, guard_init, border);
>> +       if (!initial_true)
>> +         cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
>> +
>> +       /* Now version the loop, placing loop2 after loop1 connecting
>> +          them, and fix up SSA form for that.  */
>> +       initialize_original_copy_tables ();
>> +       basic_block cond_bb;
>> +       struct loop *loop2 = loop_version (loop1, cond, &cond_bb,
>> +                                          REG_BR_PROB_BASE, REG_BR_PROB_BASE,
>> +                                          REG_BR_PROB_BASE, true);
>> +       gcc_assert (loop2);
>> +       update_ssa (TODO_update_ssa);
>> +
>> +       edge new_e = connect_loops (loop1, loop2);
>> +       connect_loop_phis (loop1, loop2, new_e);
>> +
>> +       /* The iterations of the second loop is now already
>> +          exactly those that the first loop didn't do, but the
>> +          iteration space of the first loop is still the original one.
>> +          Compute the new bound for the guarding IV and patch the
>> +          loop exit to use it instead of original IV and bound.  */
>> +       gimple_seq stmts = NULL;
>> +       tree newend = compute_new_first_bound (&stmts, niter, border,
>> +                                              guard_code, guard_init);
>> +       if (stmts)
>> +         gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
>> +                                           stmts);
>> +       tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1));
>> +       patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true);
>> +
>> +       /* Finally patch out the two copies of the condition to be always
>> +          true/false (or opposite).  */
>> +       gcond *force_true = as_a<gcond *> (last_stmt (bbs[i]));
>> +       gcond *force_false = as_a<gcond *> (last_stmt (get_bb_copy (bbs[i])));
>> +       if (!initial_true)
>> +         std::swap (force_true, force_false);
>> +       gimple_cond_make_true (force_true);
>> +       gimple_cond_make_false (force_false);
>> +       update_stmt (force_true);
>> +       update_stmt (force_false);
>> +
>> +       free_original_copy_tables ();
>> +
>> +       /* We destroyed LCSSA form above.  Eventually we might be able
>> +          to fix it on the fly, for now simply punt and use the helper.  */
>> +       rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1);
>> +
>> +       changed = true;
>> +       if (dump_file && (dump_flags & TDF_DETAILS))
>> +         fprintf (dump_file, ";; Loop split.\n");
>> +
>> +       /* Only deal with the first opportunity.  */
>> +       break;
>> +      }
>> +
>> +  free (bbs);
>> +  return changed;
>> +}
>> +
>> +/* Main entry point.  Perform loop splitting on all suitable loops.  */
>> +
>> +static unsigned int
>> +tree_ssa_split_loops (void)
>> +{
>> +  struct loop *loop;
>> +  bool changed = false;
>> +
>> +  gcc_assert (scev_initialized_p ());
>> +  FOR_EACH_LOOP (loop, 0)
>> +    loop->aux = NULL;
>> +
>> +  /* Go through all loops starting from innermost.  */
>> +  FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
>> +    {
>> +      struct tree_niter_desc niter;
>> +      if (loop->aux)
>> +       {
>> +         /* If any of our inner loops was split, don't split us,
>> +            and mark our containing loop as having had splits as well.  */
>> +         loop_outer (loop)->aux = loop;
>> +         continue;
>> +       }
>> +
>> +      if (single_exit (loop)
>> +         /* ??? We could handle non-empty latches when we split
>> +            the latch edge (not the exit edge), and put the new
>> +            exit condition in the new block.  OTOH this executes some
>> +            code unconditionally that might have been skipped by the
>> +            original exit before.  */
>> +         && empty_block_p (loop->latch)
>> +         && !optimize_loop_for_size_p (loop)
>> +         && number_of_iterations_exit (loop, single_exit (loop), &niter,
>> +                                       false, true)
>> +         && niter.cmp != ERROR_MARK
>> +         /* We can't yet handle loops controlled by a != predicate.  */
>> +         && niter.cmp != NE_EXPR)
>> +       {
>> +         if (split_loop (loop, &niter))
>> +           {
>> +             /* Mark our containing loop as having had some split inner
>> +                loops.  */
>> +             loop_outer (loop)->aux = loop;
>> +             changed = true;
>> +           }
>> +       }
>> +    }
>> +
>> +  FOR_EACH_LOOP (loop, 0)
>> +    loop->aux = NULL;
>> +
>> +  if (changed)
>> +    return TODO_cleanup_cfg;
>> +  return 0;
>> +}
>> +
>> +/* Loop splitting pass.  */
>> +
>> +namespace {
>> +
>> +const pass_data pass_data_loop_split =
>> +{
>> +  GIMPLE_PASS, /* type */
>> +  "lsplit", /* name */
>> +  OPTGROUP_LOOP, /* optinfo_flags */
>> +  TV_LOOP_SPLIT, /* tv_id */
>> +  PROP_cfg, /* properties_required */
>> +  0, /* properties_provided */
>> +  0, /* properties_destroyed */
>> +  0, /* todo_flags_start */
>> +  0, /* todo_flags_finish */
>> +};
>> +
>> +class pass_loop_split : public gimple_opt_pass
>> +{
>> +public:
>> +  pass_loop_split (gcc::context *ctxt)
>> +    : gimple_opt_pass (pass_data_loop_split, ctxt)
>> +  {}
>> +
>> +  /* opt_pass methods: */
>> +  virtual bool gate (function *) { return flag_split_loops != 0; }
>> +  virtual unsigned int execute (function *);
>> +
>> +}; // class pass_loop_split
>> +
>> +unsigned int
>> +pass_loop_split::execute (function *fun)
>> +{
>> +  if (number_of_loops (fun) <= 1)
>> +    return 0;
>> +
>> +  return tree_ssa_split_loops ();
>> +}
>> +
>> +} // anon namespace
>> +
>> +gimple_opt_pass *
>> +make_pass_loop_split (gcc::context *ctxt)
>> +{
>> +  return new pass_loop_split (ctxt);
>> +}
>> Index: doc/invoke.texi
>> ===================================================================
>> --- doc/invoke.texi     (revision 231115)
>> +++ doc/invoke.texi     (working copy)
>> @@ -446,7 +446,7 @@ Objective-C and Objective-C++ Dialects}.
>>  -fselective-scheduling -fselective-scheduling2 @gol
>>  -fsel-sched-pipelining -fsel-sched-pipelining-outer-loops @gol
>>  -fsemantic-interposition -fshrink-wrap -fsignaling-nans @gol
>> --fsingle-precision-constant -fsplit-ivs-in-unroller @gol
>> +-fsingle-precision-constant -fsplit-ivs-in-unroller -fsplit-loops@gol
>>  -fsplit-paths @gol
>>  -fsplit-wide-types -fssa-backprop -fssa-phiopt @gol
>>  -fstack-protector -fstack-protector-all -fstack-protector-strong @gol
>> @@ -10197,6 +10197,11 @@ Enabled with @option{-fprofile-use}.
>>  Enables the loop invariant motion pass in the RTL loop optimizer.  Enabled
>>  at level @option{-O1}
>>
>> +@item -fsplit-loops
>> +@opindex fsplit-loops
>> +Split a loop into two if it contains a condition that's always true
>> +for one side of the iteration space and false for the other.
>> +
>>  @item -funswitch-loops
>>  @opindex funswitch-loops
>>  Move branches with loop invariant conditions out of the loop, with duplicates
>> Index: doc/passes.texi
>> ===================================================================
>> --- doc/passes.texi     (revision 231115)
>> +++ doc/passes.texi     (working copy)
>> @@ -484,6 +484,12 @@ out of the loops.  To achieve this, a du
>>  each possible outcome of conditional jump(s).  The pass is implemented in
>>  @file{tree-ssa-loop-unswitch.c}.
>>
>> +Loop splitting.  If a loop contains a conditional statement that is
>> +always true for one part of the iteration space and false for the other
>> +this pass splits the loop into two, one dealing with one side the other
>> +only with the other, thereby removing one inner-loop conditional.  The
>> +pass is implemented in @file{tree-ssa-loop-split.c}.
>> +
>>  The optimizations also use various utility functions contained in
>>  @file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and
>>  @file{cfgloopmanip.c}.
>> Index: testsuite/gcc.dg/loop-split.c
>> ===================================================================
>> --- testsuite/gcc.dg/loop-split.c       (revision 0)
>> +++ testsuite/gcc.dg/loop-split.c       (working copy)
>> @@ -0,0 +1,147 @@
>> +/* { dg-do run } */
>> +/* { dg-options "-O2 -fsplit-loops -fdump-tree-lsplit-details" } */
>> +
>> +#ifdef __cplusplus
>> +extern "C" int printf (const char *, ...);
>> +extern "C" void abort (void);
>> +#else
>> +extern int printf (const char *, ...);
>> +extern void abort (void);
>> +#endif
>> +
>> +/* Define TRACE to 1 or 2 to get detailed tracing.
>> +   Define SINGLE_TEST to 1 or 2 to get a simple routine with
>> +   just one loop, called only one time or with multiple parameters,
>> +   to make debugging easier.  */
>> +#ifndef TRACE
>> +#define TRACE 0
>> +#endif
>> +
>> +#define loop(beg,step,beg2,cond1,cond2) \
>> +    do \
>> +      { \
>> +       sum = 0; \
>> +        for (i = (beg), j = (beg2); (cond1); i+=(step),j+=(step)) \
>> +          { \
>> +            if (cond2) { \
>> +             if (TRACE > 1) printf ("a: %d %d\n", i, j); \
>> +              sum += a[i]; \
>> +           } else { \
>> +             if (TRACE > 1) printf ("b: %d %d\n", i, j); \
>> +              sum += b[i]; \
>> +           } \
>> +          } \
>> +       if (TRACE > 0) printf ("sum: %d\n", sum); \
>> +       check = check * 47 + sum; \
>> +      } while (0)
>> +
>> +#ifndef SINGLE_TEST
>> +unsigned __attribute__((noinline, noclone)) dotest (int beg, int end, int step,
>> +                                              int c, int *a, int *b, int beg2)
>> +{
>> +  unsigned check = 0;
>> +  int sum;
>> +  int i, j;
>> +  loop (beg, 1, beg2, i < end, j < c);
>> +  loop (beg, 1, beg2, i <= end, j < c);
>> +  loop (beg, 1, beg2, i < end, j <= c);
>> +  loop (beg, 1, beg2, i <= end, j <= c);
>> +  loop (beg, 1, beg2, i < end, j > c);
>> +  loop (beg, 1, beg2, i <= end, j > c);
>> +  loop (beg, 1, beg2, i < end, j >= c);
>> +  loop (beg, 1, beg2, i <= end, j >= c);
>> +  beg2 += end-beg;
>> +  loop (end, -1, beg2, i >= beg, j >= c);
>> +  loop (end, -1, beg2, i >= beg, j > c);
>> +  loop (end, -1, beg2, i > beg, j >= c);
>> +  loop (end, -1, beg2, i > beg, j > c);
>> +  loop (end, -1, beg2, i >= beg, j <= c);
>> +  loop (end, -1, beg2, i >= beg, j < c);
>> +  loop (end, -1, beg2, i > beg, j <= c);
>> +  loop (end, -1, beg2, i > beg, j < c);
>> +  return check;
>> +}
>> +
>> +#else
>> +
>> +int __attribute__((noinline, noclone)) f (int beg, int end, int step,
>> +                                         int c, int *a, int *b, int beg2)
>> +{
>> +  int sum = 0;
>> +  int i, j;
>> +  //for (i = beg, j = beg2; i < end; i += 1, j++ /*step*/)
>> +  for (i = end, j = beg2 + (end-beg); i > beg; i += -1, j-- /*step*/)
>> +    {
>> +      // i - j == X --> i = X + j
>> +      // --> i < end == X+j < end == j < end - X
>> +      // --> newend = end - (i_init - j_init)
>> +      // j < end-X && j < c --> j < min(end-X,c)
>> +      // j < end-X && j <= c --> j <= min(end-X-1,c) or j < min(end-X,c+1{OF!})
>> +      //if (j < c)
>> +      if (j >= c)
>> +       printf ("a: %d %d\n", i, j);
>> +      /*else
>> +       printf ("b: %d %d\n", i, j);*/
>> +       /*sum += a[i];
>> +      else
>> +       sum += b[i];*/
>> +    }
>> +  return sum;
>> +}
>> +
>> +int __attribute__((noinline, noclone)) f2 (int *beg, int *end, int step,
>> +                                         int *c, int *a, int *b, int *beg2)
>> +{
>> +  int sum = 0;
>> +  int *i, *j;
>> +  for (i = beg, j = beg2; i < end; i += 1, j++ /*step*/)
>> +    {
>> +      if (j <= c)
>> +       printf ("%d %d\n", i - beg, j - beg);
>> +       /*sum += a[i];
>> +      else
>> +       sum += b[i];*/
>> +    }
>> +  return sum;
>> +}
>> +#endif
>> +
>> +extern int printf (const char *, ...);
>> +
>> +int main ()
>> +{
>> +  int a[] = {0,0,0,0,0, 1,2,3,4,5,6,7,8,9,          0,0,0,0,0};
>> +  int b[] = {0,0,0,0,0, -1,-2,-3,-4,-5,-6,-7,-8,-9, 0,0,0,0,0,};
>> +  int c;
>> +  int diff = 0;
>> +  unsigned check = 0;
>> +#if defined(SINGLE_TEST) && (SINGLE_TEST == 1)
>> +  //dotest (0, 9, 1, -1, a+5, b+5, -1);
>> +  //return 0;
>> +  f (0, 9, 1, 5, a+5, b+5, -1);
>> +  return 0;
>> +#endif
>> +  for (diff = -5; diff <= 5; diff++)
>> +    {
>> +      for (c = -1; c <= 10; c++)
>> +       {
>> +#ifdef SINGLE_TEST
>> +         int s = f (0, 9, 1, c, a+5, b+5, diff);
>> +         //int s = f2 (a+0, a+9, 1, a+c, a+5, b+5, a+diff);
>> +         printf ("%d ", s);
>> +#else
>> +         if (TRACE > 0)
>> +           printf ("check %d %d\n", c, diff);
>> +         check = check * 51 + dotest (0, 9, 1, c, a+5, b+5, diff);
>> +#endif
>> +       }
>> +      //printf ("\n");
>> +    }
>> +  //printf ("%u\n", check);
>> +  if (check != 3213344948)
>> +    abort ();
>> +  return 0;
>> +}
>> +
>> +/* All 16 loops in dotest should be split.  */
>> +/* { dg-final { scan-tree-dump-times "Loop split" 16 "lsplit" } } */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]