This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Make simple loop peeling to happen at gimple level
- From: Jan Hubicka <hubicka at ucw dot cz>
- To: gcc-patches at gcc dot gnu dot org, rguenther at suse dot de
- Date: Tue, 19 Nov 2013 13:42:06 +0100
- Subject: Make simple loop peeling to happen at gimple level
- Authentication-results: sourceware.org; auth=none
Hi,
this is update of my 2012 patch to move rtl loop peeling (the one based on
profile feedback) to tree level. Peeling expose new optimization oppurtunities
and it is good idea to have gimple passes to see them. Moreover we probably
want to hook in a new heuristic that use value histograms of loop counts.
The patch also removes simple peeling at RTL level that is mostly obsoleted by
gimple level (in few cases in our testsuite the RTL code is able to determine
loop bounds better than gimple code, but these seems to be just weird cases that
should be handled independently at gimple level)
I re-profiled-bootstrapped/regtested the patch on x86_64-linux and
benchmarked SPEC2000 with quite neutral results (smaller code overall).
(-Werror needs to be disabled or I get bogus overflow warnings both with
and without the patch)
* loop-unroll.c: (decide_unrolling_and_peeling): Rename to
(decide_unrolling): ... this one.
(peel_loops_completely): Remove.
(decide_peel_simple): Remove.
(decide_peel_once_rolling): Remove.
(decide_peel_completely): Remove.
(peel_loop_simple): Remove.
(peel_loop_completely): Remove.
(unroll_and_peel_loops): Rename to ...
(unroll_loops): ... this one; handle only unrolling.
* cfgloop.h (lpt_dec): Remove LPT_PEEL_COMPLETELY and
LPT_PEEL_SIMPLE.
(UAP_PEEL): Remove.
(unroll_and_peel_loops): Remove.
(unroll_loops): New.
* passes.def: Replace
pass_rtl_unroll_and_peel_loops by pass_rtl_unroll_loops.
* loop-init.c (gate_rtl_unroll_and_peel_loops,
rtl_unroll_and_peel_loops): Rename to ...
(gate_rtl_unroll_loops, rtl_unroll_loops): ... these; update.
(pass_rtl_unroll_and_peel_loops): Rename to ...
(pass_rtl_unroll_loops): ... this one.
* tree-pass.h (make_pass_rtl_unroll_and_peel_loops): Remove.
(make_pass_rtl_unroll_loops): New.
* tree-ssa-loop-ivcanon.c: (estimated_peeled_sequence_size, try_peel_loop): New.
(canonicalize_loop_induction_variables): Update.
* gcc.dg/tree-prof/peel-1.c: Update.
* gcc.dg/tree-prof/unroll-1.c: Update.
Index: tree-pass.h
===================================================================
*** tree-pass.h (revision 205015)
--- tree-pass.h (working copy)
*************** extern rtl_opt_pass *make_pass_loop2 (gc
*** 506,512 ****
extern rtl_opt_pass *make_pass_rtl_loop_init (gcc::context *ctxt);
extern rtl_opt_pass *make_pass_rtl_move_loop_invariants (gcc::context *ctxt);
extern rtl_opt_pass *make_pass_rtl_unswitch (gcc::context *ctxt);
! extern rtl_opt_pass *make_pass_rtl_unroll_and_peel_loops (gcc::context *ctxt);
extern rtl_opt_pass *make_pass_rtl_doloop (gcc::context *ctxt);
extern rtl_opt_pass *make_pass_rtl_loop_done (gcc::context *ctxt);
--- 506,512 ----
extern rtl_opt_pass *make_pass_rtl_loop_init (gcc::context *ctxt);
extern rtl_opt_pass *make_pass_rtl_move_loop_invariants (gcc::context *ctxt);
extern rtl_opt_pass *make_pass_rtl_unswitch (gcc::context *ctxt);
! extern rtl_opt_pass *make_pass_rtl_unroll_loops (gcc::context *ctxt);
extern rtl_opt_pass *make_pass_rtl_doloop (gcc::context *ctxt);
extern rtl_opt_pass *make_pass_rtl_loop_done (gcc::context *ctxt);
Index: testsuite/gcc.dg/tree-prof/peel-1.c
===================================================================
*** testsuite/gcc.dg/tree-prof/peel-1.c (revision 205015)
--- testsuite/gcc.dg/tree-prof/peel-1.c (working copy)
***************
*** 1,4 ****
! /* { dg-options "-O3 -fdump-rtl-loop2_unroll -fno-unroll-loops -fpeel-loops" } */
void abort();
int a[1000];
--- 1,4 ----
! /* { dg-options "-O3 -fdump-tree-cunroll-details -fno-unroll-loops -fpeel-loops" } */
void abort();
int a[1000];
Index: passes.def
===================================================================
*** passes.def (revision 205015)
--- passes.def (working copy)
*************** along with GCC; see the file COPYING3.
*** 337,343 ****
NEXT_PASS (pass_rtl_loop_init);
NEXT_PASS (pass_rtl_move_loop_invariants);
NEXT_PASS (pass_rtl_unswitch);
! NEXT_PASS (pass_rtl_unroll_and_peel_loops);
NEXT_PASS (pass_rtl_doloop);
NEXT_PASS (pass_rtl_loop_done);
TERMINATE_PASS_LIST ()
--- 337,343 ----
NEXT_PASS (pass_rtl_loop_init);
NEXT_PASS (pass_rtl_move_loop_invariants);
NEXT_PASS (pass_rtl_unswitch);
! NEXT_PASS (pass_rtl_unroll_loops);
NEXT_PASS (pass_rtl_doloop);
NEXT_PASS (pass_rtl_loop_done);
TERMINATE_PASS_LIST ()
Index: loop-init.c
===================================================================
*** loop-init.c (revision 205015)
--- loop-init.c (working copy)
*************** gate_handle_loop2 (void)
*** 300,306 ****
if (optimize > 0
&& (flag_move_loop_invariants
|| flag_unswitch_loops
- || flag_peel_loops
|| flag_unroll_loops
#ifdef HAVE_doloop_end
|| (flag_branch_on_count_reg && HAVE_doloop_end)
--- 300,305 ----
*************** make_pass_rtl_unswitch (gcc::context *ct
*** 578,590 ****
/* Loop unswitching for RTL. */
static bool
! gate_rtl_unroll_and_peel_loops (void)
{
! return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
}
static unsigned int
! rtl_unroll_and_peel_loops (void)
{
if (number_of_loops (cfun) > 1)
{
--- 577,589 ----
/* Loop unswitching for RTL. */
static bool
! gate_rtl_unroll_loops (void)
{
! return (flag_unroll_loops || flag_unroll_all_loops);
}
static unsigned int
! rtl_unroll_loops (void)
{
if (number_of_loops (cfun) > 1)
{
*************** rtl_unroll_and_peel_loops (void)
*** 592,612 ****
if (dump_file)
df_dump (dump_file);
- if (flag_peel_loops)
- flags |= UAP_PEEL;
if (flag_unroll_loops)
flags |= UAP_UNROLL;
if (flag_unroll_all_loops)
flags |= UAP_UNROLL_ALL;
! unroll_and_peel_loops (flags);
}
return 0;
}
namespace {
! const pass_data pass_data_rtl_unroll_and_peel_loops =
{
RTL_PASS, /* type */
"loop2_unroll", /* name */
--- 591,609 ----
if (dump_file)
df_dump (dump_file);
if (flag_unroll_loops)
flags |= UAP_UNROLL;
if (flag_unroll_all_loops)
flags |= UAP_UNROLL_ALL;
! unroll_loops (flags);
}
return 0;
}
namespace {
! const pass_data pass_data_rtl_unroll_loops =
{
RTL_PASS, /* type */
"loop2_unroll", /* name */
*************** const pass_data pass_data_rtl_unroll_and
*** 621,645 ****
TODO_verify_rtl_sharing, /* todo_flags_finish */
};
! class pass_rtl_unroll_and_peel_loops : public rtl_opt_pass
{
public:
! pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
! : rtl_opt_pass (pass_data_rtl_unroll_and_peel_loops, ctxt)
{}
/* opt_pass methods: */
! bool gate () { return gate_rtl_unroll_and_peel_loops (); }
! unsigned int execute () { return rtl_unroll_and_peel_loops (); }
! }; // class pass_rtl_unroll_and_peel_loops
} // anon namespace
rtl_opt_pass *
! make_pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
{
! return new pass_rtl_unroll_and_peel_loops (ctxt);
}
--- 618,642 ----
TODO_verify_rtl_sharing, /* todo_flags_finish */
};
! class pass_rtl_unroll_loops : public rtl_opt_pass
{
public:
! pass_rtl_unroll_loops (gcc::context *ctxt)
! : rtl_opt_pass (pass_data_rtl_unroll_loops, ctxt)
{}
/* opt_pass methods: */
! bool gate () { return gate_rtl_unroll_loops (); }
! unsigned int execute () { return rtl_unroll_loops (); }
! }; // class pass_rtl_unroll_loops
} // anon namespace
rtl_opt_pass *
! make_pass_rtl_unroll_loops (gcc::context *ctxt)
{
! return new pass_rtl_unroll_loops (ctxt);
}
Index: tree-ssa-loop-ivcanon.c
===================================================================
*** tree-ssa-loop-ivcanon.c (revision 205015)
--- tree-ssa-loop-ivcanon.c (working copy)
*************** along with GCC; see the file COPYING3.
*** 28,36 ****
variables. In that case the created optimization possibilities are likely
to pay up.
! Additionally in case we detect that it is beneficial to unroll the
! loop completely, we do it right here to expose the optimization
! possibilities to the following passes. */
#include "config.h"
#include "system.h"
--- 28,39 ----
variables. In that case the created optimization possibilities are likely
to pay up.
! We also perform
! - complette unrolling (or peeling) when the loops is rolling few enough
! times
! - simple peeling (i.e. copying few initial iterations prior the loop)
! when number of iteration estimate is known (typically by the profile
! info). */
#include "config.h"
#include "system.h"
*************** try_unroll_loop_completely (struct loop
*** 649,655 ****
HOST_WIDE_INT maxiter,
location_t locus)
{
! unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
gimple cond;
struct loop_size size;
bool n_unroll_found = false;
--- 652,658 ----
HOST_WIDE_INT maxiter,
location_t locus)
{
! unsigned HOST_WIDE_INT n_unroll = 0, ninsns, max_unroll, unr_insns;
gimple cond;
struct loop_size size;
bool n_unroll_found = false;
*************** try_unroll_loop_completely (struct loop
*** 894,899 ****
--- 897,1029 ----
return true;
}
+ /* Return number of instructions after peeling. */
+ static unsigned HOST_WIDE_INT
+ estimated_peeled_sequence_size (struct loop_size *size,
+ unsigned HOST_WIDE_INT npeel)
+ {
+ return MAX (npeel * (HOST_WIDE_INT) (size->overall
+ - size->eliminated_by_peeling), 1);
+ }
+
+ /* If the loop is expected to iterate N times and is
+ small enough, duplicate the loop body N+1 times before
+ the loop itself. This way the hot path will never
+ enter the loop.
+ Parameters are the same as for try_unroll_loops_completely */
+
+ static bool
+ try_peel_loop (struct loop *loop,
+ edge exit, tree niter,
+ HOST_WIDE_INT maxiter)
+ {
+ int npeel;
+ struct loop_size size;
+ int peeled_size;
+ sbitmap wont_exit;
+ unsigned i;
+ vec<edge> to_remove = vNULL;
+ edge e;
+
+ /* If the iteration bound is known and large, then we can safely eliminate
+ the check in peeled copies. */
+ if (TREE_CODE (niter) != INTEGER_CST)
+ exit = NULL;
+
+ if (!flag_peel_loops || PARAM_VALUE (PARAM_MAX_PEEL_TIMES) <= 0)
+ return false;
+
+ /* Peel only innermost loops. */
+ if (loop->inner)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Not peeling: outer loop\n");
+ return false;
+ }
+
+ if (!optimize_loop_for_speed_p (loop))
+ {
+ if (dump_file)
+ fprintf (dump_file, "Not peeling: cold loop\n");
+ return false;
+ }
+
+ /* Check if there is an estimate on the number of iterations. */
+ npeel = estimated_loop_iterations_int (loop);
+ if (npeel < 0)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Not peeling: number of iterations is not "
+ "estimated\n");
+ return false;
+ }
+ if (maxiter >= 0 && maxiter <= npeel)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Not peeling: upper bound is known so can "
+ "unroll complettely\n");
+ return false;
+ }
+
+ /* We want to peel estimated number of iterations + 1 (so we never
+ enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
+ and be sure to avoid overflows. */
+ if (npeel > PARAM_VALUE (PARAM_MAX_PEEL_TIMES) - 1)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Not peeling: rolls too much "
+ "(%i + 1 > --param max-peel-times)\n", npeel);
+ return false;
+ }
+ npeel++;
+
+ /* Check peeled loops size. */
+ tree_estimate_loop_size (loop, exit, NULL, &size,
+ PARAM_VALUE (PARAM_MAX_PEELED_INSNS));
+ if ((peeled_size = estimated_peeled_sequence_size (&size, npeel))
+ > PARAM_VALUE (PARAM_MAX_PEELED_INSNS))
+ {
+ if (dump_file)
+ fprintf (dump_file, "Not peeling: peeled sequence size is too large "
+ "(%i insns > --param max-peel-insns)", peeled_size);
+ return false;
+ }
+
+ /* Duplicate possibly eliminating the exits. */
+ initialize_original_copy_tables ();
+ wont_exit = sbitmap_alloc (npeel + 1);
+ bitmap_ones (wont_exit);
+ bitmap_clear_bit (wont_exit, 0);
+ if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
+ npeel, wont_exit,
+ exit, &to_remove,
+ DLTHE_FLAG_UPDATE_FREQ
+ | DLTHE_FLAG_COMPLETTE_PEEL))
+ {
+ free_original_copy_tables ();
+ free (wont_exit);
+ return false;
+ }
+ FOR_EACH_VEC_ELT (to_remove, i, e)
+ {
+ bool ok = remove_path (e);
+ gcc_assert (ok);
+ }
+ free (wont_exit);
+ free_original_copy_tables ();
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Peeled loop %d, %i times.\n",
+ loop->num, npeel);
+ }
+ if (loop->any_upper_bound)
+ loop->nb_iterations_upper_bound -= double_int::from_uhwi (npeel);
+ loop->nb_iterations_estimate = double_int_zero;
+ /* Make sure to mark loop cold so we do not try to peel it more. */
+ scale_loop_profile (loop, 1, 0);
+ loop->header->count = 0;
+ return true;
+ }
/* Adds a canonical induction variable to LOOP if suitable.
CREATE_IV is true if we may create a new iv. UL determines
which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
*************** canonicalize_loop_induction_variables (s
*** 973,978 ****
--- 1103,1111 ----
&& exit && just_once_each_iteration_p (loop, exit->src))
create_canonical_iv (loop, exit, niter);
+ if (ul == UL_ALL)
+ modified |= try_peel_loop (loop, exit, niter, maxiter);
+
return modified;
}
Index: loop-unroll.c
===================================================================
*** loop-unroll.c (revision 205015)
--- loop-unroll.c (working copy)
*************** along with GCC; see the file COPYING3.
*** 34,41 ****
#include "target.h"
#include "dumpfile.h"
! /* This pass performs loop unrolling and peeling. We only perform these
! optimizations on innermost loops (with single exception) because
the impact on performance is greatest here, and we want to avoid
unnecessary code size growth. The gain is caused by greater sequentiality
of code, better code to optimize for further passes and in some cases
--- 34,41 ----
#include "target.h"
#include "dumpfile.h"
! /* This pass performs loop unrolling. We only perform this
! optimization on innermost loops (with single exception) because
the impact on performance is greatest here, and we want to avoid
unnecessary code size growth. The gain is caused by greater sequentiality
of code, better code to optimize for further passes and in some cases
*************** along with GCC; see the file COPYING3.
*** 44,55 ****
What we do:
- -- complete peeling of once-rolling loops; this is the above mentioned
- exception, as this causes loop to be cancelled completely and
- does not cause code growth
- -- complete peeling of loops that roll (small) constant times.
- -- simple peeling of first iterations of loops that do not roll much
- (according to profile feedback)
-- unrolling of loops that roll constant times; this is almost always
win, as we get rid of exit condition tests.
-- unrolling of loops that roll number of times that we can compute
--- 44,49 ----
*************** along with GCC; see the file COPYING3.
*** 62,68 ****
appropriate function below.
There is a lot of parameters (defined and described in params.def) that
! control how much we unroll/peel.
??? A great problem is that we don't have a good way how to determine
how many times we should unroll the loop; the experiments I have made
--- 56,62 ----
appropriate function below.
There is a lot of parameters (defined and described in params.def) that
! control how much we unroll.
??? A great problem is that we don't have a good way how to determine
how many times we should unroll the loop; the experiments I have made
*************** struct opt_info
*** 175,191 ****
basic_block loop_preheader; /* The loop preheader basic block. */
};
- static void decide_unrolling_and_peeling (int);
- static void peel_loops_completely (int);
- static void decide_peel_simple (struct loop *, int);
- static void decide_peel_once_rolling (struct loop *, int);
- static void decide_peel_completely (struct loop *, int);
static void decide_unroll_stupid (struct loop *, int);
static void decide_unroll_constant_iterations (struct loop *, int);
static void decide_unroll_runtime_iterations (struct loop *, int);
- static void peel_loop_simple (struct loop *);
- static void peel_loop_completely (struct loop *);
static void unroll_loop_stupid (struct loop *);
static void unroll_loop_constant_iterations (struct loop *);
static void unroll_loop_runtime_iterations (struct loop *);
static struct opt_info *analyze_insns_in_loop (struct loop *);
--- 169,179 ----
basic_block loop_preheader; /* The loop preheader basic block. */
};
static void decide_unroll_stupid (struct loop *, int);
static void decide_unroll_constant_iterations (struct loop *, int);
static void decide_unroll_runtime_iterations (struct loop *, int);
static void unroll_loop_stupid (struct loop *);
+ static void decide_unrolling (int);
static void unroll_loop_constant_iterations (struct loop *);
static void unroll_loop_runtime_iterations (struct loop *);
static struct opt_info *analyze_insns_in_loop (struct loop *);
*************** static rtx get_expansion (struct var_to_
*** 207,216 ****
appropriate given the dump or -fopt-info settings. */
static void
! report_unroll_peel (struct loop *loop, location_t locus)
{
- struct niter_desc *desc;
- int niters = 0;
int report_flags = MSG_OPTIMIZED_LOCATIONS | TDF_RTL | TDF_DETAILS;
if (loop->lpt_decision.decision == LPT_NONE)
--- 195,202 ----
appropriate given the dump or -fopt-info settings. */
static void
! report_unroll (struct loop *loop, location_t locus)
{
int report_flags = MSG_OPTIMIZED_LOCATIONS | TDF_RTL | TDF_DETAILS;
if (loop->lpt_decision.decision == LPT_NONE)
*************** report_unroll_peel (struct loop *loop, l
*** 219,282 ****
if (!dump_enabled_p ())
return;
! /* In the special case where the loop never iterated, emit
! a different message so that we don't report an unroll by 0.
! This matches the equivalent message emitted during tree unrolling. */
! if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY
! && !loop->lpt_decision.times)
! {
! dump_printf_loc (report_flags, locus,
! "loop turned into non-loop; it never loops.\n");
! return;
! }
!
! desc = get_simple_loop_desc (loop);
!
! if (desc->const_iter)
! niters = desc->niter;
! else if (loop->header->count)
! niters = expected_loop_iterations (loop);
!
! if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
! dump_printf_loc (report_flags, locus,
! "loop with %d iterations completely unrolled",
! loop->lpt_decision.times + 1);
! else
! dump_printf_loc (report_flags, locus,
! "loop %s %d times",
! (loop->lpt_decision.decision == LPT_PEEL_SIMPLE
! ? "peeled" : "unrolled"),
! loop->lpt_decision.times);
if (profile_info)
dump_printf (report_flags,
! " (header execution count %d",
(int)loop->header->count);
- if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
- dump_printf (report_flags,
- "%s%s iterations %d)",
- profile_info ? ", " : " (",
- desc->const_iter ? "const" : "average",
- niters);
- else if (profile_info)
- dump_printf (report_flags, ")");
dump_printf (report_flags, "\n");
}
/* Unroll and/or peel (depending on FLAGS) LOOPS. */
void
! unroll_and_peel_loops (int flags)
{
struct loop *loop;
bool changed = false;
loop_iterator li;
- /* First perform complete loop peeling (it is almost surely a win,
- and affects parameters for further decision a lot). */
- peel_loops_completely (flags);
-
/* Now decide rest of unrolling and peeling. */
! decide_unrolling_and_peeling (flags);
/* Scan the loops, inner ones first. */
FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
--- 205,231 ----
if (!dump_enabled_p ())
return;
! dump_printf_loc (report_flags, locus,
! "loop unrolled %d times",
! loop->lpt_decision.times);
if (profile_info)
dump_printf (report_flags,
! " (header execution count %d)",
(int)loop->header->count);
dump_printf (report_flags, "\n");
}
/* Unroll and/or peel (depending on FLAGS) LOOPS. */
void
! unroll_loops (int flags)
{
struct loop *loop;
bool changed = false;
loop_iterator li;
/* Now decide rest of unrolling and peeling. */
! decide_unrolling (flags);
/* Scan the loops, inner ones first. */
FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
*************** unroll_and_peel_loops (int flags)
*** 284,296 ****
/* And perform the appropriate transformations. */
switch (loop->lpt_decision.decision)
{
- case LPT_PEEL_COMPLETELY:
- /* Already done. */
- gcc_unreachable ();
- case LPT_PEEL_SIMPLE:
- peel_loop_simple (loop);
- changed = true;
- break;
case LPT_UNROLL_CONSTANT:
unroll_loop_constant_iterations (loop);
changed = true;
--- 233,238 ----
*************** loop_exit_at_end_p (struct loop *loop)
*** 327,389 ****
struct niter_desc *desc = get_simple_loop_desc (loop);
rtx insn;
if (desc->in_edge->dest != loop->latch)
return false;
/* Check that the latch is empty. */
FOR_BB_INSNS (loop->latch, insn)
{
! if (NONDEBUG_INSN_P (insn))
return false;
}
return true;
}
! /* Depending on FLAGS, check whether to peel loops completely and do so. */
! static void
! peel_loops_completely (int flags)
! {
! struct loop *loop;
! loop_iterator li;
! bool changed = false;
!
! /* Scan the loops, the inner ones first. */
! FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
! {
! loop->lpt_decision.decision = LPT_NONE;
! location_t locus = get_loop_location (loop);
!
! if (dump_enabled_p ())
! dump_printf_loc (TDF_RTL, locus,
! ";; *** Considering loop %d at BB %d for "
! "complete peeling ***\n",
! loop->num, loop->header->index);
!
! loop->ninsns = num_loop_insns (loop);
!
! decide_peel_once_rolling (loop, flags);
! if (loop->lpt_decision.decision == LPT_NONE)
! decide_peel_completely (loop, flags);
!
! if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
! {
! report_unroll_peel (loop, locus);
! peel_loop_completely (loop);
! changed = true;
! }
! }
!
! if (changed)
! {
! calculate_dominance_info (CDI_DOMINATORS);
! fix_loop_structure (NULL);
! }
! }
!
! /* Decide whether unroll or peel loops (depending on FLAGS) and how much. */
static void
! decide_unrolling_and_peeling (int flags)
{
struct loop *loop;
loop_iterator li;
--- 269,293 ----
struct niter_desc *desc = get_simple_loop_desc (loop);
rtx insn;
+ /* We should never have conditional in latch block. */
+ gcc_assert (desc->in_edge->dest != loop->header);
+
if (desc->in_edge->dest != loop->latch)
return false;
/* Check that the latch is empty. */
FOR_BB_INSNS (loop->latch, insn)
{
! if (INSN_P (insn) && active_insn_p (insn))
return false;
}
return true;
}
! /* Decide whether unroll loops (depending on FLAGS) and how much. */
static void
! decide_unrolling (int flags)
{
struct loop *loop;
loop_iterator li;
*************** decide_unrolling_and_peeling (int flags)
*** 397,406 ****
if (dump_enabled_p ())
dump_printf_loc (TDF_RTL, locus,
";; *** Considering loop %d at BB %d for "
! "unrolling and peeling ***\n",
loop->num, loop->header->index);
! /* Do not peel cold areas. */
if (optimize_loop_for_size_p (loop))
{
if (dump_file)
--- 301,310 ----
if (dump_enabled_p ())
dump_printf_loc (TDF_RTL, locus,
";; *** Considering loop %d at BB %d for "
! "unrolling ***\n",
loop->num, loop->header->index);
! /* Do not unroll cold areas. */
if (optimize_loop_for_size_p (loop))
{
if (dump_file)
*************** decide_unrolling_and_peeling (int flags)
*** 436,642 ****
decide_unroll_runtime_iterations (loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
decide_unroll_stupid (loop, flags);
- if (loop->lpt_decision.decision == LPT_NONE)
- decide_peel_simple (loop, flags);
-
- report_unroll_peel (loop, locus);
- }
- }
-
- /* Decide whether the LOOP is once rolling and suitable for complete
- peeling. */
- static void
- decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED)
- {
- struct niter_desc *desc;
-
- if (dump_file)
- fprintf (dump_file, "\n;; Considering peeling once rolling loop\n");
-
- /* Is the loop small enough? */
- if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS) < loop->ninsns)
- {
- if (dump_file)
- fprintf (dump_file, ";; Not considering loop, is too big\n");
- return;
- }
-
- /* Check for simple loops. */
- desc = get_simple_loop_desc (loop);
! /* Check number of iterations. */
! if (!desc->simple_p
! || desc->assumptions
! || desc->infinite
! || !desc->const_iter
! || (desc->niter != 0
! && get_max_loop_iterations_int (loop) != 0))
! {
! if (dump_file)
! fprintf (dump_file,
! ";; Unable to prove that the loop rolls exactly once\n");
! return;
}
-
- /* Success. */
- loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
- }
-
- /* Decide whether the LOOP is suitable for complete peeling. */
- static void
- decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED)
- {
- unsigned npeel;
- struct niter_desc *desc;
-
- if (dump_file)
- fprintf (dump_file, "\n;; Considering peeling completely\n");
-
- /* Skip non-innermost loops. */
- if (loop->inner)
- {
- if (dump_file)
- fprintf (dump_file, ";; Not considering loop, is not innermost\n");
- return;
- }
-
- /* Do not peel cold areas. */
- if (optimize_loop_for_size_p (loop))
- {
- if (dump_file)
- fprintf (dump_file, ";; Not considering loop, cold area\n");
- return;
- }
-
- /* Can the loop be manipulated? */
- if (!can_duplicate_loop_p (loop))
- {
- if (dump_file)
- fprintf (dump_file,
- ";; Not considering loop, cannot duplicate\n");
- return;
- }
-
- /* npeel = number of iterations to peel. */
- npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS) / loop->ninsns;
- if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES))
- npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
-
- /* Is the loop small enough? */
- if (!npeel)
- {
- if (dump_file)
- fprintf (dump_file, ";; Not considering loop, is too big\n");
- return;
- }
-
- /* Check for simple loops. */
- desc = get_simple_loop_desc (loop);
-
- /* Check number of iterations. */
- if (!desc->simple_p
- || desc->assumptions
- || !desc->const_iter
- || desc->infinite)
- {
- if (dump_file)
- fprintf (dump_file,
- ";; Unable to prove that the loop iterates constant times\n");
- return;
- }
-
- if (desc->niter > npeel - 1)
- {
- if (dump_file)
- {
- fprintf (dump_file,
- ";; Not peeling loop completely, rolls too much (");
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter);
- fprintf (dump_file, " iterations > %d [maximum peelings])\n", npeel);
- }
- return;
- }
-
- /* Success. */
- loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
- }
-
- /* Peel all iterations of LOOP, remove exit edges and cancel the loop
- completely. The transformation done:
-
- for (i = 0; i < 4; i++)
- body;
-
- ==>
-
- i = 0;
- body; i++;
- body; i++;
- body; i++;
- body; i++;
- */
- static void
- peel_loop_completely (struct loop *loop)
- {
- sbitmap wont_exit;
- unsigned HOST_WIDE_INT npeel;
- unsigned i;
- vec<edge> remove_edges;
- edge ein;
- struct niter_desc *desc = get_simple_loop_desc (loop);
- struct opt_info *opt_info = NULL;
-
- npeel = desc->niter;
-
- if (npeel)
- {
- bool ok;
-
- wont_exit = sbitmap_alloc (npeel + 1);
- bitmap_ones (wont_exit);
- bitmap_clear_bit (wont_exit, 0);
- if (desc->noloop_assumptions)
- bitmap_clear_bit (wont_exit, 1);
-
- remove_edges.create (0);
-
- if (flag_split_ivs_in_unroller)
- opt_info = analyze_insns_in_loop (loop);
-
- opt_info_start_duplication (opt_info);
- ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
- npeel,
- wont_exit, desc->out_edge,
- &remove_edges,
- DLTHE_FLAG_UPDATE_FREQ
- | DLTHE_FLAG_COMPLETTE_PEEL
- | (opt_info
- ? DLTHE_RECORD_COPY_NUMBER : 0));
- gcc_assert (ok);
-
- free (wont_exit);
-
- if (opt_info)
- {
- apply_opt_in_copies (opt_info, npeel, false, true);
- free_opt_info (opt_info);
- }
-
- /* Remove the exit edges. */
- FOR_EACH_VEC_ELT (remove_edges, i, ein)
- remove_path (ein);
- remove_edges.release ();
- }
-
- ein = desc->in_edge;
- free_simple_loop_desc (loop);
-
- /* Now remove the unreachable part of the last iteration and cancel
- the loop. */
- remove_path (ein);
-
- if (dump_file)
- fprintf (dump_file, ";; Peeled loop completely, %d times\n", (int) npeel);
}
/* Decide whether to unroll LOOP iterating constant number of times
--- 340,348 ----
decide_unroll_runtime_iterations (loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
decide_unroll_stupid (loop, flags);
! report_unroll (loop, locus);
}
}
/* Decide whether to unroll LOOP iterating constant number of times
*************** unroll_loop_runtime_iterations (struct l
*** 1342,1501 ****
dom_bbs.release ();
}
- /* Decide whether to simply peel LOOP and how much. */
- static void
- decide_peel_simple (struct loop *loop, int flags)
- {
- unsigned npeel;
- double_int iterations;
-
- if (!(flags & UAP_PEEL))
- {
- /* We were not asked to, just return back silently. */
- return;
- }
-
- if (dump_file)
- fprintf (dump_file, "\n;; Considering simply peeling loop\n");
-
- /* npeel = number of iterations to peel. */
- npeel = PARAM_VALUE (PARAM_MAX_PEELED_INSNS) / loop->ninsns;
- if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES))
- npeel = PARAM_VALUE (PARAM_MAX_PEEL_TIMES);
-
- /* Skip big loops. */
- if (!npeel)
- {
- if (dump_file)
- fprintf (dump_file, ";; Not considering loop, is too big\n");
- return;
- }
-
- /* Do not simply peel loops with branches inside -- it increases number
- of mispredicts.
- Exception is when we do have profile and we however have good chance
- to peel proper number of iterations loop will iterate in practice.
- TODO: this heuristic needs tunning; while for complette unrolling
- the branch inside loop mostly eliminates any improvements, for
- peeling it is not the case. Also a function call inside loop is
- also branch from branch prediction POV (and probably better reason
- to not unroll/peel). */
- if (num_loop_branches (loop) > 1
- && profile_status != PROFILE_READ)
- {
- if (dump_file)
- fprintf (dump_file, ";; Not peeling, contains branches\n");
- return;
- }
-
- /* If we have realistic estimate on number of iterations, use it. */
- if (get_estimated_loop_iterations (loop, &iterations))
- {
- if (double_int::from_shwi (npeel).ule (iterations))
- {
- if (dump_file)
- {
- fprintf (dump_file, ";; Not peeling loop, rolls too much (");
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
- (HOST_WIDEST_INT) (iterations.to_shwi () + 1));
- fprintf (dump_file, " iterations > %d [maximum peelings])\n",
- npeel);
- }
- return;
- }
- npeel = iterations.to_shwi () + 1;
- }
- /* If we have small enough bound on iterations, we can still peel (completely
- unroll). */
- else if (get_max_loop_iterations (loop, &iterations)
- && iterations.ult (double_int::from_shwi (npeel)))
- npeel = iterations.to_shwi () + 1;
- else
- {
- /* For now we have no good heuristics to decide whether loop peeling
- will be effective, so disable it. */
- if (dump_file)
- fprintf (dump_file,
- ";; Not peeling loop, no evidence it will be profitable\n");
- return;
- }
-
- /* Success. */
- loop->lpt_decision.decision = LPT_PEEL_SIMPLE;
- loop->lpt_decision.times = npeel;
- }
-
- /* Peel a LOOP LOOP->LPT_DECISION.TIMES times. The transformation does this:
-
- while (cond)
- body;
-
- ==> (LOOP->LPT_DECISION.TIMES == 3)
-
- if (!cond) goto end;
- body;
- if (!cond) goto end;
- body;
- if (!cond) goto end;
- body;
- while (cond)
- body;
- end: ;
- */
- static void
- peel_loop_simple (struct loop *loop)
- {
- sbitmap wont_exit;
- unsigned npeel = loop->lpt_decision.times;
- struct niter_desc *desc = get_simple_loop_desc (loop);
- struct opt_info *opt_info = NULL;
- bool ok;
-
- if (flag_split_ivs_in_unroller && npeel > 1)
- opt_info = analyze_insns_in_loop (loop);
-
- wont_exit = sbitmap_alloc (npeel + 1);
- bitmap_clear (wont_exit);
-
- opt_info_start_duplication (opt_info);
-
- ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
- npeel, wont_exit, NULL,
- NULL, DLTHE_FLAG_UPDATE_FREQ
- | (opt_info
- ? DLTHE_RECORD_COPY_NUMBER
- : 0));
- gcc_assert (ok);
-
- free (wont_exit);
-
- if (opt_info)
- {
- apply_opt_in_copies (opt_info, npeel, false, false);
- free_opt_info (opt_info);
- }
-
- if (desc->simple_p)
- {
- if (desc->const_iter)
- {
- desc->niter -= npeel;
- desc->niter_expr = GEN_INT (desc->niter);
- desc->noloop_assumptions = NULL_RTX;
- }
- else
- {
- /* We cannot just update niter_expr, as its value might be clobbered
- inside loop. We could handle this by counting the number into
- temporary just like we do in runtime unrolling, but it does not
- seem worthwhile. */
- free_simple_loop_desc (loop);
- }
- }
- if (dump_file)
- fprintf (dump_file, ";; Peeling loop %d times\n", npeel);
- }
-
/* Decide whether to unroll LOOP stupidly and how much. */
static void
decide_unroll_stupid (struct loop *loop, int flags)
--- 1048,1053 ----
Index: cfgloop.h
===================================================================
*** cfgloop.h (revision 205015)
--- cfgloop.h (working copy)
*************** along with GCC; see the file COPYING3.
*** 29,36 ****
enum lpt_dec
{
LPT_NONE,
- LPT_PEEL_COMPLETELY,
- LPT_PEEL_SIMPLE,
LPT_UNROLL_CONSTANT,
LPT_UNROLL_RUNTIME,
LPT_UNROLL_STUPID
--- 29,34 ----
*************** extern void unswitch_loops (void);
*** 707,718 ****
enum
{
! UAP_PEEL = 1, /* Enables loop peeling. */
! UAP_UNROLL = 2, /* Enables unrolling of loops if it seems profitable. */
! UAP_UNROLL_ALL = 4 /* Enables unrolling of all loops. */
};
! extern void unroll_and_peel_loops (int);
extern void doloop_optimize_loops (void);
extern void move_loop_invariants (void);
extern void scale_loop_profile (struct loop *loop, int scale, gcov_type iteration_bound);
--- 705,715 ----
enum
{
! UAP_UNROLL = 1, /* Enables unrolling of loops if it seems profitable. */
! UAP_UNROLL_ALL = 2 /* Enables unrolling of all loops. */
};
! extern void unroll_loops (int);
extern void doloop_optimize_loops (void);
extern void move_loop_invariants (void);
extern void scale_loop_profile (struct loop *loop, int scale, gcov_type iteration_bound);