This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Gimple loop splitting v2
- From: Richard Biener <richard dot guenther at gmail dot com>
- To: Andrew Pinski <pinskia at gmail dot com>
- Cc: Michael Matz <matz at suse dot de>, Jeff Law <law at redhat dot com>, GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Wed, 27 Jul 2016 10:10:58 +0200
- Subject: Re: Gimple loop splitting v2
- Authentication-results: sourceware.org; auth=none
- References: <alpine.LSU.2.20.1511121734040.11029@wotan.suse.de> <5645083A.5070607@redhat.com> <alpine.LSU.2.20.1511161453390.11029@wotan.suse.de> <564A6648.6000002@redhat.com> <alpine.LSU.2.20.1512011711210.13533@wotan.suse.de> <565E25E7.7050202@redhat.com> <alpine.LSU.2.20.1512021420420.13533@wotan.suse.de> <CA+=Sn1nmqsGAOf0JFPNRPRs2KwNTihAFzck9mgyCEHzzrUEHog@mail.gmail.com> <CAFiYyc3jot+fyn_fPZiZoXHU7y4hE=81MdePq66+uo_vwssN8w@mail.gmail.com> <CA+=Sn1kfciVvp-KOTotW-r9j396pzudNpV6ATj-9RMxCipGpVA@mail.gmail.com>
On Wed, Jul 27, 2016 at 8:17 AM, Andrew Pinski <pinskia@gmail.com> wrote:
> On Tue, Jul 26, 2016 at 4:32 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> 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)?!
>
> The iterator with flags of 0 does not visit the the root. So the way
> to fix this is change 0 (which is the flags) with LI_INCLUDE_ROOT so
> we zero out the root too.
Or not set ->aux on the root in the first place.
Richard.
> Thanks,
> Andrew
>
>>
>>>
>>> /* 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" } } */