summaryrefslogtreecommitdiff
path: root/gcc/loop-unroll.c
diff options
context:
space:
mode:
authorhubicka <hubicka@138bc75d-0d04-0410-961f-82ee72b054a4>2014-10-15 08:02:06 +0000
committerhubicka <hubicka@138bc75d-0d04-0410-961f-82ee72b054a4>2014-10-15 08:02:06 +0000
commitc836de3fcd856e4a526169d0c7eec8ab65b0eb8f (patch)
treee4fe1dea885c050d43cd384f86a97b01f26934e9 /gcc/loop-unroll.c
parent0601876c5e29df9cfc1dd6380bd3df6b00cf3f67 (diff)
downloadgcc-c836de3fcd856e4a526169d0c7eec8ab65b0eb8f.tar.gz
* 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. * gcc.dg/gcc.dg/unroll_1.c: Update. * gcc.dg/gcc.dg/unroll_2.c: Update. * gcc.dg/gcc.dg/unroll_3.c: Update. * gcc.dg/gcc.dg/unroll_4.c: Update. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@216238 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'gcc/loop-unroll.c')
-rw-r--r--gcc/loop-unroll.c570
1 files changed, 63 insertions, 507 deletions
diff --git a/gcc/loop-unroll.c b/gcc/loop-unroll.c
index 2e35cb1672a..2abb2f4d8d8 100644
--- a/gcc/loop-unroll.c
+++ b/gcc/loop-unroll.c
@@ -1,4 +1,4 @@
-/* Loop unrolling and peeling.
+/* Loop unrolling.
Copyright (C) 2002-2014 Free Software Foundation, Inc.
This file is part of GCC.
@@ -34,8 +34,8 @@ along with GCC; see the file COPYING3. If not see
#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
+/* 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
@@ -44,12 +44,6 @@ along with GCC; see the file COPYING3. If not see
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
@@ -62,7 +56,7 @@ along with GCC; see the file COPYING3. If not see
appropriate function below.
There is a lot of parameters (defined and described in params.def) that
- control how much we unroll/peel.
+ 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
@@ -170,17 +164,11 @@ struct opt_info
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 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 *);
@@ -197,15 +185,13 @@ static void combine_var_copies_in_loop_exit (struct var_to_expand *,
basic_block);
static rtx get_expansion (struct var_to_expand *);
-/* Emit a message summarizing the unroll or peel that will be
+/* Emit a message summarizing the unroll that will be
performed for LOOP, along with the loop's location LOCUS, if
appropriate given the dump or -fopt-info settings. */
static void
-report_unroll_peel (struct loop *loop, location_t locus)
+report_unroll (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)
@@ -214,169 +200,20 @@ report_unroll_peel (struct loop *loop, location_t locus)
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);
+ 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",
+ " (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;
-
- /* 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 (loop, LI_FROM_INNERMOST)
- {
- /* 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;
- break;
- case LPT_UNROLL_RUNTIME:
- unroll_loop_runtime_iterations (loop);
- changed = true;
- break;
- case LPT_UNROLL_STUPID:
- unroll_loop_stupid (loop);
- changed = true;
- break;
- case LPT_NONE:
- break;
- default:
- gcc_unreachable ();
- }
- }
-
- if (changed)
- {
- calculate_dominance_info (CDI_DOMINATORS);
- fix_loop_structure (NULL);
- }
-
- iv_analysis_done ();
-}
-
-/* Check whether exit of the LOOP is at the end of loop body. */
-
-static bool
-loop_exit_at_end_p (struct loop *loop)
-{
- struct niter_desc *desc = get_simple_loop_desc (loop);
- rtx_insn *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;
- bool changed = false;
-
- /* Scan the loops, the inner ones first. */
- FOR_EACH_LOOP (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. */
+/* Decide whether unroll loops and how much. */
static void
-decide_unrolling_and_peeling (int flags)
+decide_unrolling (int flags)
{
struct loop *loop;
@@ -389,7 +226,7 @@ decide_unrolling_and_peeling (int flags)
if (dump_enabled_p ())
dump_printf_loc (TDF_RTL, locus,
";; *** Considering loop %d at BB %d for "
- "unrolling and peeling ***\n",
+ "unrolling ***\n",
loop->num, loop->header->index);
/* Do not peel cold areas. */
@@ -428,204 +265,77 @@ decide_unrolling_and_peeling (int flags)
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);
+ report_unroll (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)
+/* Unroll LOOPS. */
+void
+unroll_loops (int flags)
{
- 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);
+ struct loop *loop;
+ bool changed = false;
- /* 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;
- }
+ /* Now decide rest of unrolling. */
+ decide_unrolling (flags);
- if (desc->niter > npeel - 1)
+ /* Scan the loops, inner ones first. */
+ FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
{
- if (dump_file)
+ /* And perform the appropriate transformations. */
+ switch (loop->lpt_decision.decision)
{
- fprintf (dump_file,
- ";; Not peeling loop completely, rolls too much (");
- fprintf (dump_file, "%"PRId64, desc->niter);
- fprintf (dump_file, " iterations > %d [maximum peelings])\n", npeel);
+ case LPT_UNROLL_CONSTANT:
+ unroll_loop_constant_iterations (loop);
+ changed = true;
+ break;
+ case LPT_UNROLL_RUNTIME:
+ unroll_loop_runtime_iterations (loop);
+ changed = true;
+ break;
+ case LPT_UNROLL_STUPID:
+ unroll_loop_stupid (loop);
+ changed = true;
+ break;
+ case LPT_NONE:
+ break;
+ default:
+ gcc_unreachable ();
}
- 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:
+ if (changed)
+ {
+ calculate_dominance_info (CDI_DOMINATORS);
+ fix_loop_structure (NULL);
+ }
- for (i = 0; i < 4; i++)
- body;
+ iv_analysis_done ();
+}
- ==>
+/* Check whether exit of the LOOP is at the end of loop body. */
- i = 0;
- body; i++;
- body; i++;
- body; i++;
- body; i++;
- */
-static void
-peel_loop_completely (struct loop *loop)
+static bool
+loop_exit_at_end_p (struct loop *loop)
{
- sbitmap wont_exit;
- unsigned HOST_WIDE_INT npeel;
- unsigned i;
- 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);
-
- auto_vec<edge> remove_edges;
- 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);
+ rtx_insn *insn;
- free (wont_exit);
+ /* We should never have conditional in latch block. */
+ gcc_assert (desc->in_edge->dest != loop->header);
- if (opt_info)
- {
- apply_opt_in_copies (opt_info, npeel, false, true);
- free_opt_info (opt_info);
- }
+ if (desc->in_edge->dest != loop->latch)
+ return false;
- /* Remove the exit edges. */
- FOR_EACH_VEC_ELT (remove_edges, i, ein)
- remove_path (ein);
+ /* Check that the latch is empty. */
+ FOR_BB_INSNS (loop->latch, insn)
+ {
+ if (INSN_P (insn) && active_insn_p (insn))
+ return false;
}
- 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);
+ return true;
}
/* Decide whether to unroll LOOP iterating constant number of times
@@ -1372,160 +1082,6 @@ unroll_loop_runtime_iterations (struct loop *loop)
max_unroll, num_loop_insns (loop));
}
-/* Decide whether to simply peel LOOP and how much. */
-static void
-decide_peel_simple (struct loop *loop, int flags)
-{
- unsigned npeel;
- widest_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_for_fn (cfun) != 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 (wi::leu_p (npeel, iterations))
- {
- if (dump_file)
- {
- fprintf (dump_file, ";; Not peeling loop, rolls too much (");
- fprintf (dump_file, "%"PRId64,
- (int64_t) (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)
- && wi::ltu_p (iterations, 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)