Message ID | CA+=Sn1nmqsGAOf0JFPNRPRs2KwNTihAFzck9mgyCEHzzrUEHog@mail.gmail.com |
---|---|
State | New |
Headers | show |
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" } } */
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. 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" } } */
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" } } */
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; + } /* 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;