-/* Loop unrolling and peeling.
- Copyright (C) 2002-2013 Free Software Foundation, Inc.
+/* Loop unrolling.
+ Copyright (C) 2002-2016 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
+#include "target.h"
#include "rtl.h"
#include "tree.h"
-#include "hard-reg-set.h"
-#include "obstack.h"
-#include "basic-block.h"
+#include "cfghooks.h"
+#include "optabs.h"
+#include "emit-rtl.h"
+#include "recog.h"
+#include "profile.h"
+#include "cfgrtl.h"
#include "cfgloop.h"
#include "params.h"
+#include "dojump.h"
#include "expr.h"
-#include "hash-table.h"
-#include "recog.h"
-#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
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
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
struct iv_to_split
{
- rtx insn; /* The insn in that the induction variable occurs. */
+ rtx_insn *insn; /* The insn in that the induction variable occurs. */
rtx orig_var; /* The variable (register) for the IV before split. */
rtx base_var; /* The variable on that the values in the further
iterations are based. */
rtx step; /* Step of the induction variable. */
struct iv_to_split *next; /* Next entry in walking order. */
- unsigned n_loc;
- unsigned loc[3]; /* Location where the definition of the induction
- variable occurs in the insn. For example if
- N_LOC is 2, the expression is located at
- XEXP (XEXP (single_set, loc[0]), loc[1]). */
};
/* Information about accumulators to expand. */
struct var_to_expand
{
- rtx insn; /* The insn in that the variable expansion occurs. */
+ rtx_insn *insn; /* The insn in that the variable expansion occurs. */
rtx reg; /* The accumulator which is expanded. */
vec<rtx> var_expansions; /* The copies of the accumulator which is expanded. */
struct var_to_expand *next; /* Next entry in walking order. */
/* Hashtable helper for iv_to_split. */
-struct iv_split_hasher : typed_free_remove <iv_to_split>
+struct iv_split_hasher : free_ptr_hash <iv_to_split>
{
- typedef iv_to_split value_type;
- typedef iv_to_split compare_type;
- static inline hashval_t hash (const value_type *);
- static inline bool equal (const value_type *, const compare_type *);
+ static inline hashval_t hash (const iv_to_split *);
+ static inline bool equal (const iv_to_split *, const iv_to_split *);
};
/* A hash function for information about insns to split. */
inline hashval_t
-iv_split_hasher::hash (const value_type *ivts)
+iv_split_hasher::hash (const iv_to_split *ivts)
{
return (hashval_t) INSN_UID (ivts->insn);
}
/* An equality functions for information about insns to split. */
inline bool
-iv_split_hasher::equal (const value_type *i1, const compare_type *i2)
+iv_split_hasher::equal (const iv_to_split *i1, const iv_to_split *i2)
{
return i1->insn == i2->insn;
}
/* Hashtable helper for iv_to_split. */
-struct var_expand_hasher : typed_free_remove <var_to_expand>
+struct var_expand_hasher : free_ptr_hash <var_to_expand>
{
- typedef var_to_expand value_type;
- typedef var_to_expand compare_type;
- static inline hashval_t hash (const value_type *);
- static inline bool equal (const value_type *, const compare_type *);
+ static inline hashval_t hash (const var_to_expand *);
+ static inline bool equal (const var_to_expand *, const var_to_expand *);
};
/* Return a hash for VES. */
inline hashval_t
-var_expand_hasher::hash (const value_type *ves)
+var_expand_hasher::hash (const var_to_expand *ves)
{
return (hashval_t) INSN_UID (ves->insn);
}
/* Return true if I1 and I2 refer to the same instruction. */
inline bool
-var_expand_hasher::equal (const value_type *i1, const compare_type *i2)
+var_expand_hasher::equal (const var_to_expand *i1, const var_to_expand *i2)
{
return i1->insn == i2->insn;
}
struct opt_info
{
- hash_table <iv_split_hasher> insns_to_split; /* A hashtable of insns to
+ hash_table<iv_split_hasher> *insns_to_split; /* A hashtable of insns to
split. */
struct iv_to_split *iv_to_split_head; /* The first iv to split. */
struct iv_to_split **iv_to_split_tail; /* Pointer to the tail of the list. */
- hash_table <var_expand_hasher> insns_with_var_to_expand; /* A hashtable of
+ hash_table<var_expand_hasher> *insns_with_var_to_expand; /* A hashtable of
insns with accumulators to expand. */
struct var_to_expand *var_to_expand_head; /* The first var to expand. */
struct var_to_expand **var_to_expand_tail; /* Pointer to the tail of the list. */
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 *);
static void opt_info_start_duplication (struct opt_info *);
static void apply_opt_in_copies (struct opt_info *, unsigned, bool, bool);
static void free_opt_info (struct opt_info *);
-static struct var_to_expand *analyze_insn_to_expand_var (struct loop*, rtx);
+static struct var_to_expand *analyze_insn_to_expand_var (struct loop*, rtx_insn *);
static bool referenced_in_one_insn_in_loop_p (struct loop *, rtx, int *);
-static struct iv_to_split *analyze_iv_to_split_insn (rtx);
-static void expand_var_during_unrolling (struct var_to_expand *, rtx);
+static struct iv_to_split *analyze_iv_to_split_insn (rtx_insn *);
+static void expand_var_during_unrolling (struct var_to_expand *, rtx_insn *);
static void insert_var_expansion_initialization (struct var_to_expand *,
basic_block);
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)
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;
-
- 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. */
+/* Decide whether unroll loops and how much. */
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. */
-static void
-decide_unrolling_and_peeling (int flags)
+decide_unrolling (int flags)
{
struct loop *loop;
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. */
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, HOST_WIDEST_INT_PRINT_DEC, 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;
+ rtx_insn *insn;
- npeel = desc->niter;
+ /* We should never have conditional in latch block. */
+ gcc_assert (desc->in_edge->dest != loop->header);
- 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);
-
- free (wont_exit);
-
- 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
{
unsigned nunroll, nunroll_by_av, best_copies, best_unroll = 0, n_copies, i;
struct niter_desc *desc;
- double_int iterations;
+ widest_int iterations;
if (!(flags & UAP_UNROLL))
{
if (desc->niter < 2 * nunroll
|| ((get_estimated_loop_iterations (loop, &iterations)
|| get_max_loop_iterations (loop, &iterations))
- && iterations.ult (double_int::from_shwi (2 * nunroll))))
+ && wi::ltu_p (iterations, 2 * nunroll)))
{
if (dump_file)
fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
desc->noloop_assumptions = NULL_RTX;
desc->niter -= exit_mod;
- loop->nb_iterations_upper_bound -= double_int::from_uhwi (exit_mod);
+ loop->nb_iterations_upper_bound -= exit_mod;
if (loop->any_estimate
- && double_int::from_uhwi (exit_mod).ule
- (loop->nb_iterations_estimate))
- loop->nb_iterations_estimate -= double_int::from_uhwi (exit_mod);
+ && wi::leu_p (exit_mod, loop->nb_iterations_estimate))
+ loop->nb_iterations_estimate -= exit_mod;
else
loop->any_estimate = false;
}
apply_opt_in_copies (opt_info, exit_mod + 1, false, false);
desc->niter -= exit_mod + 1;
- loop->nb_iterations_upper_bound -= double_int::from_uhwi (exit_mod + 1);
+ loop->nb_iterations_upper_bound -= exit_mod + 1;
if (loop->any_estimate
- && double_int::from_uhwi (exit_mod + 1).ule
- (loop->nb_iterations_estimate))
- loop->nb_iterations_estimate -= double_int::from_uhwi (exit_mod + 1);
+ && wi::leu_p (exit_mod + 1, loop->nb_iterations_estimate))
+ loop->nb_iterations_estimate -= exit_mod + 1;
else
loop->any_estimate = false;
desc->noloop_assumptions = NULL_RTX;
desc->niter /= max_unroll + 1;
loop->nb_iterations_upper_bound
- = loop->nb_iterations_upper_bound.udiv (double_int::from_uhwi (max_unroll
- + 1),
- TRUNC_DIV_EXPR);
+ = wi::udiv_trunc (loop->nb_iterations_upper_bound, max_unroll + 1);
if (loop->any_estimate)
loop->nb_iterations_estimate
- = loop->nb_iterations_estimate.udiv (double_int::from_uhwi (max_unroll
- + 1),
- TRUNC_DIV_EXPR);
+ = wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
desc->niter_expr = GEN_INT (desc->niter);
/* Remove the edges. */
{
unsigned nunroll, nunroll_by_av, i;
struct niter_desc *desc;
- double_int iterations;
+ widest_int iterations;
if (!(flags & UAP_UNROLL))
{
/* Check whether the loop rolls. */
if ((get_estimated_loop_iterations (loop, &iterations)
|| get_max_loop_iterations (loop, &iterations))
- && iterations.ult (double_int::from_shwi (2 * nunroll)))
+ && wi::ltu_p (iterations, 2 * nunroll))
{
if (dump_file)
fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
and NULL is returned instead. */
basic_block
-split_edge_and_insert (edge e, rtx insns)
+split_edge_and_insert (edge e, rtx_insn *insns)
{
basic_block bb;
CFG. For this purpose we used to set the BB_SUPERBLOCK flag on BB
and call break_superblocks when going out of cfglayout mode. But it
turns out that this never happens; and that if it does ever happen,
- the TODO_verify_flow at the end of the RTL loop passes would fail.
+ the verify_flow_info at the end of the RTL loop passes would fail.
There are two reasons why we expected we could have control flow insns
in INSNS. The first is when a comparison has to be done in parts, and
return bb;
}
+/* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
+ true, with probability PROB. If CINSN is not NULL, it is the insn to copy
+ in order to create a jump. */
+
+static rtx_insn *
+compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp,
+ rtx_code_label *label, int prob, rtx_insn *cinsn)
+{
+ rtx_insn *seq;
+ rtx_jump_insn *jump;
+ rtx cond;
+ machine_mode mode;
+
+ mode = GET_MODE (op0);
+ if (mode == VOIDmode)
+ mode = GET_MODE (op1);
+
+ start_sequence ();
+ if (GET_MODE_CLASS (mode) == MODE_CC)
+ {
+ /* A hack -- there seems to be no easy generic way how to make a
+ conditional jump from a ccmode comparison. */
+ gcc_assert (cinsn);
+ cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
+ gcc_assert (GET_CODE (cond) == comp);
+ gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
+ gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
+ emit_jump_insn (copy_insn (PATTERN (cinsn)));
+ jump = as_a <rtx_jump_insn *> (get_last_insn ());
+ JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
+ LABEL_NUSES (JUMP_LABEL (jump))++;
+ redirect_jump (jump, label, 0);
+ }
+ else
+ {
+ gcc_assert (!cinsn);
+
+ op0 = force_operand (op0, NULL_RTX);
+ op1 = force_operand (op1, NULL_RTX);
+ do_compare_rtx_and_jump (op0, op1, comp, 0,
+ mode, NULL_RTX, NULL, label, -1);
+ jump = as_a <rtx_jump_insn *> (get_last_insn ());
+ jump->set_jump_target (label);
+ LABEL_NUSES (label)++;
+ }
+ add_int_reg_note (jump, REG_BR_PROB, prob);
+
+ seq = get_insns ();
+ end_sequence ();
+
+ return seq;
+}
+
/* Unroll LOOP for which we are able to count number of iterations in runtime
LOOP->LPT_DECISION.TIMES times. The transformation does this (with some
extra care for case n < 0):
static void
unroll_loop_runtime_iterations (struct loop *loop)
{
- rtx old_niter, niter, init_code, branch_code, tmp;
+ rtx old_niter, niter, tmp;
+ rtx_insn *init_code, *branch_code;
unsigned i, j, p;
basic_block preheader, *body, swtch, ezc_swtch;
sbitmap wont_exit;
preheader = split_edge (loop_preheader_edge (loop));
branch_code = compare_and_jump_seq (copy_rtx (niter), GEN_INT (j), EQ,
block_label (preheader), p,
- NULL_RTX);
+ NULL);
/* We rely on the fact that the compare and jump cannot be optimized out,
and hence the cfg we create is correct. */
preheader = split_edge (loop_preheader_edge (loop));
branch_code = compare_and_jump_seq (copy_rtx (niter), const0_rtx, EQ,
block_label (preheader), p,
- NULL_RTX);
+ NULL);
gcc_assert (branch_code != NULL_RTX);
swtch = split_edge_and_insert (single_succ_edge (swtch), branch_code);
simplify_gen_binary (UDIV, desc->mode, old_niter,
gen_int_mode (max_unroll + 1, desc->mode));
loop->nb_iterations_upper_bound
- = loop->nb_iterations_upper_bound.udiv (double_int::from_uhwi (max_unroll
- + 1),
- TRUNC_DIV_EXPR);
+ = wi::udiv_trunc (loop->nb_iterations_upper_bound, max_unroll + 1);
if (loop->any_estimate)
loop->nb_iterations_estimate
- = loop->nb_iterations_estimate.udiv (double_int::from_uhwi (max_unroll
- + 1),
- TRUNC_DIV_EXPR);
+ = wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
if (exit_at_end)
{
desc->niter_expr =
desc->noloop_assumptions = NULL_RTX;
--loop->nb_iterations_upper_bound;
if (loop->any_estimate
- && loop->nb_iterations_estimate != double_int_zero)
+ && loop->nb_iterations_estimate != 0)
--loop->nb_iterations_estimate;
else
loop->any_estimate = false;
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;
- 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_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 (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)
{
unsigned nunroll, nunroll_by_av, i;
struct niter_desc *desc;
- double_int iterations;
+ widest_int iterations;
if (!(flags & UAP_UNROLL_ALL))
{
/* Check whether the loop rolls. */
if ((get_estimated_loop_iterations (loop, &iterations)
|| get_max_loop_iterations (loop, &iterations))
- && iterations.ult (double_int::from_shwi (2 * nunroll)))
+ && wi::ltu_p (iterations, 2 * nunroll))
{
if (dump_file)
fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
Set *DEBUG_USES to the number of debug insns that reference the
variable. */
-bool
+static bool
referenced_in_one_insn_in_loop_p (struct loop *loop, rtx reg,
int *debug_uses)
{
basic_block *body, bb;
unsigned i;
int count_ref = 0;
- rtx insn;
+ rtx_insn *insn;
body = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
basic_block *body, bb;
unsigned i;
- rtx insn;
+ rtx_insn *insn;
body = get_loop_body (loop);
for (i = 0; debug_uses && i < loop->num_nodes; i++)
*/
static struct var_to_expand *
-analyze_insn_to_expand_var (struct loop *loop, rtx insn)
+analyze_insn_to_expand_var (struct loop *loop, rtx_insn *insn)
{
rtx set, dest, src;
struct var_to_expand *ves;
pointer to it. */
static struct iv_to_split *
-analyze_iv_to_split_insn (rtx insn)
+analyze_iv_to_split_insn (rtx_insn *insn)
{
rtx set, dest;
struct rtx_iv iv;
ivts->base_var = NULL_RTX;
ivts->step = iv.step;
ivts->next = NULL;
- ivts->n_loc = 1;
- ivts->loc[0] = 1;
return ivts;
}
basic_block *body, bb;
unsigned i;
struct opt_info *opt_info = XCNEW (struct opt_info);
- rtx insn;
+ rtx_insn *insn;
struct iv_to_split *ivts = NULL;
struct var_to_expand *ves = NULL;
iv_to_split **slot1;
if (flag_split_ivs_in_unroller)
{
- opt_info->insns_to_split.create (5 * loop->num_nodes);
+ opt_info->insns_to_split
+ = new hash_table<iv_split_hasher> (5 * loop->num_nodes);
opt_info->iv_to_split_head = NULL;
opt_info->iv_to_split_tail = &opt_info->iv_to_split_head;
}
if (flag_variable_expansion_in_unroller
&& can_apply)
{
- opt_info->insns_with_var_to_expand.create (5 * loop->num_nodes);
+ opt_info->insns_with_var_to_expand
+ = new hash_table<var_expand_hasher> (5 * loop->num_nodes);
opt_info->var_to_expand_head = NULL;
opt_info->var_to_expand_tail = &opt_info->var_to_expand_head;
}
if (!INSN_P (insn))
continue;
- if (opt_info->insns_to_split.is_created ())
+ if (opt_info->insns_to_split)
ivts = analyze_iv_to_split_insn (insn);
if (ivts)
{
- slot1 = opt_info->insns_to_split.find_slot (ivts, INSERT);
+ slot1 = opt_info->insns_to_split->find_slot (ivts, INSERT);
gcc_assert (*slot1 == NULL);
*slot1 = ivts;
*opt_info->iv_to_split_tail = ivts;
continue;
}
- if (opt_info->insns_with_var_to_expand.is_created ())
+ if (opt_info->insns_with_var_to_expand)
ves = analyze_insn_to_expand_var (loop, insn);
if (ves)
{
- slot2 = opt_info->insns_with_var_to_expand.find_slot (ves, INSERT);
+ slot2 = opt_info->insns_with_var_to_expand->find_slot (ves, INSERT);
gcc_assert (*slot2 == NULL);
*slot2 = ves;
*opt_info->var_to_expand_tail = ves;
}
}
-/* Locate in EXPR the expression corresponding to the location recorded
- in IVTS, and return a pointer to the RTX for this location. */
-
-static rtx *
-get_ivts_expr (rtx expr, struct iv_to_split *ivts)
-{
- unsigned i;
- rtx *ret = &expr;
-
- for (i = 0; i < ivts->n_loc; i++)
- ret = &XEXP (*ret, ivts->loc[i]);
-
- return ret;
-}
-
/* Allocate basic variable for the induction variable chain. */
static void
allocate_basic_variable (struct iv_to_split *ivts)
{
- rtx expr = *get_ivts_expr (single_set (ivts->insn), ivts);
+ rtx expr = SET_SRC (single_set (ivts->insn));
ivts->base_var = gen_reg_rtx (GET_MODE (expr));
}
the initial value from INSN. */
static void
-insert_base_initialization (struct iv_to_split *ivts, rtx insn)
+insert_base_initialization (struct iv_to_split *ivts, rtx_insn *insn)
{
- rtx expr = copy_rtx (*get_ivts_expr (single_set (insn), ivts));
- rtx seq;
+ rtx expr = copy_rtx (SET_SRC (single_set (insn)));
+ rtx_insn *seq;
start_sequence ();
expr = force_operand (expr, ivts->base_var);
by base variable + DELTA * step. */
static void
-split_iv (struct iv_to_split *ivts, rtx insn, unsigned delta)
+split_iv (struct iv_to_split *ivts, rtx_insn *insn, unsigned delta)
{
- rtx expr, *loc, seq, incr, var;
- enum machine_mode mode = GET_MODE (ivts->base_var);
+ rtx expr, *loc, incr, var;
+ rtx_insn *seq;
+ machine_mode mode = GET_MODE (ivts->base_var);
rtx src, dest, set;
/* Construct base + DELTA * step. */
}
/* Figure out where to do the replacement. */
- loc = get_ivts_expr (single_set (insn), ivts);
+ loc = &SET_SRC (single_set (insn));
/* If we can make the replacement right away, we're done. */
if (validate_change (insn, loc, expr, 0))
with a new register. */
static void
-expand_var_during_unrolling (struct var_to_expand *ve, rtx insn)
+expand_var_during_unrolling (struct var_to_expand *ve, rtx_insn *insn)
{
rtx new_reg, set;
bool really_new_expansion = false;
insert_var_expansion_initialization (struct var_to_expand *ve,
basic_block place)
{
- rtx seq, var, zero_init;
+ rtx_insn *seq;
+ rtx var, zero_init;
unsigned i;
- enum machine_mode mode = GET_MODE (ve->reg);
+ machine_mode mode = GET_MODE (ve->reg);
bool honor_signed_zero_p = HONOR_SIGNED_ZEROS (mode);
if (ve->var_expansions.length () == 0)
combine_var_copies_in_loop_exit (struct var_to_expand *ve, basic_block place)
{
rtx sum = ve->reg;
- rtx expr, seq, var, insn;
+ rtx expr, var;
+ rtx_insn *seq, *insn;
unsigned i;
if (ve->var_expansions.length () == 0)
any notes attached to them. So resort to old techniques... */
static void
-maybe_strip_eq_note_for_split_iv (struct opt_info *opt_info, rtx insn)
+maybe_strip_eq_note_for_split_iv (struct opt_info *opt_info, rtx_insn *insn)
{
struct iv_to_split *ivts;
rtx note = find_reg_equal_equiv_note (insn);
{
unsigned i, delta;
basic_block bb, orig_bb;
- rtx insn, orig_insn, next;
+ rtx_insn *insn, *orig_insn, *next;
struct iv_to_split ivts_templ, *ivts;
struct var_to_expand ve_templ, *ves;
gcc_assert (!unrolling || rewrite_original_loop);
/* Allocate the basic variables (i0). */
- if (opt_info->insns_to_split.is_created ())
+ if (opt_info->insns_to_split)
for (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next)
allocate_basic_variable (ivts);
ve_templ.insn = orig_insn;
/* Apply splitting iv optimization. */
- if (opt_info->insns_to_split.is_created ())
+ if (opt_info->insns_to_split)
{
maybe_strip_eq_note_for_split_iv (opt_info, insn);
- ivts = opt_info->insns_to_split.find (&ivts_templ);
+ ivts = opt_info->insns_to_split->find (&ivts_templ);
if (ivts)
{
}
}
/* Apply variable expansion optimization. */
- if (unrolling && opt_info->insns_with_var_to_expand.is_created ())
+ if (unrolling && opt_info->insns_with_var_to_expand)
{
ves = (struct var_to_expand *)
- opt_info->insns_with_var_to_expand.find (&ve_templ);
+ opt_info->insns_with_var_to_expand->find (&ve_templ);
if (ves)
{
gcc_assert (GET_CODE (PATTERN (insn))
/* Initialize the variable expansions in the loop preheader
and take care of combining them at the loop exit. */
- if (opt_info->insns_with_var_to_expand.is_created ())
+ if (opt_info->insns_with_var_to_expand)
{
for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
insert_var_expansion_initialization (ves, opt_info->loop_preheader);
continue;
ivts_templ.insn = orig_insn;
- if (opt_info->insns_to_split.is_created ())
+ if (opt_info->insns_to_split)
{
maybe_strip_eq_note_for_split_iv (opt_info, orig_insn);
ivts = (struct iv_to_split *)
- opt_info->insns_to_split.find (&ivts_templ);
+ opt_info->insns_to_split->find (&ivts_templ);
if (ivts)
{
if (!delta)
static void
free_opt_info (struct opt_info *opt_info)
{
- if (opt_info->insns_to_split.is_created ())
- opt_info->insns_to_split.dispose ();
- if (opt_info->insns_with_var_to_expand.is_created ())
+ delete opt_info->insns_to_split;
+ opt_info->insns_to_split = NULL;
+ if (opt_info->insns_with_var_to_expand)
{
struct var_to_expand *ves;
for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
ves->var_expansions.release ();
- opt_info->insns_with_var_to_expand.dispose ();
+ delete opt_info->insns_with_var_to_expand;
+ opt_info->insns_with_var_to_expand = NULL;
}
free (opt_info);
}
projects / gcc.git / blobdiff