/* Perform doloop optimizations
- Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
- Inc.
+ Copyright (C) 2004-2020 Free Software Foundation, Inc.
Based on code by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz)
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 "flags.h"
+#include "tree.h"
+#include "cfghooks.h"
+#include "memmodel.h"
+#include "emit-rtl.h"
+#include "dojump.h"
#include "expr.h"
-#include "hard-reg-set.h"
-#include "basic-block.h"
-#include "toplev.h"
-#include "tm_p.h"
#include "cfgloop.h"
-#include "output.h"
-#include "params.h"
-#include "target.h"
+#include "cfgrtl.h"
+#include "dumpfile.h"
+#include "loop-unroll.h"
+#include "regs.h"
+#include "df.h"
/* This module is used to modify loops with a determinable number of
iterations to use special low-overhead looping instructions.
register cannot be used for anything else but doloop -- ??? detect these
cases). */
-#ifdef HAVE_doloop_end
-
/* Return the loop termination condition for PATTERN or zero
if it is not a decrement and branch jump insn. */
rtx
-doloop_condition_get (rtx doloop_pat)
+doloop_condition_get (rtx_insn *doloop_pat)
{
rtx cmp;
rtx inc;
rtx inc_src;
rtx condition;
rtx pattern;
+ rtx cc_reg = NULL_RTX;
+ rtx reg_orig = NULL_RTX;
/* The canonical doloop pattern we expect has one of the following
forms:
2) (set (reg) (plus (reg) (const_int -1))
(set (pc) (if_then_else (reg != 0)
(label_ref (label))
- (pc))). */
+ (pc))).
+
+ Some targets (ARM) do the comparison before the branch, as in the
+ following form:
+
+ 3) (parallel [(set (cc) (compare ((plus (reg) (const_int -1), 0)))
+ (set (reg) (plus (reg) (const_int -1)))])
+ (set (pc) (if_then_else (cc == NE)
+ (label_ref (label))
+ (pc))) */
pattern = PATTERN (doloop_pat);
if (GET_CODE (pattern) != PARALLEL)
{
rtx cond;
+ rtx_insn *prev_insn = prev_nondebug_insn (doloop_pat);
+ rtx cmp_arg1, cmp_arg2;
+ rtx cmp_orig;
- /* We expect the decrement to immediately precede the branch. */
+ /* In case the pattern is not PARALLEL we expect two forms
+ of doloop which are cases 2) and 3) above: in case 2) the
+ decrement immediately precedes the branch, while in case 3)
+ the compare and decrement instructions immediately precede
+ the branch. */
- if ((PREV_INSN (doloop_pat) == NULL_RTX)
- || !INSN_P (PREV_INSN (doloop_pat)))
+ if (prev_insn == NULL_RTX || !INSN_P (prev_insn))
return 0;
cmp = pattern;
- inc = PATTERN (PREV_INSN (doloop_pat));
- /* We expect the condition to be of the form (reg != 0) */
- cond = XEXP (SET_SRC (cmp), 0);
- if (GET_CODE (cond) != NE || XEXP (cond, 1) != const0_rtx)
- return 0;
-
+ if (GET_CODE (PATTERN (prev_insn)) == PARALLEL)
+ {
+ /* The third case: the compare and decrement instructions
+ immediately precede the branch. */
+ cmp_orig = XVECEXP (PATTERN (prev_insn), 0, 0);
+ if (GET_CODE (cmp_orig) != SET)
+ return 0;
+ if (GET_CODE (SET_SRC (cmp_orig)) != COMPARE)
+ return 0;
+ cmp_arg1 = XEXP (SET_SRC (cmp_orig), 0);
+ cmp_arg2 = XEXP (SET_SRC (cmp_orig), 1);
+ if (cmp_arg2 != const0_rtx
+ || GET_CODE (cmp_arg1) != PLUS)
+ return 0;
+ reg_orig = XEXP (cmp_arg1, 0);
+ if (XEXP (cmp_arg1, 1) != GEN_INT (-1)
+ || !REG_P (reg_orig))
+ return 0;
+ cc_reg = SET_DEST (cmp_orig);
+
+ inc = XVECEXP (PATTERN (prev_insn), 0, 1);
+ }
+ else
+ inc = PATTERN (prev_insn);
+ if (GET_CODE (cmp) == SET && GET_CODE (SET_SRC (cmp)) == IF_THEN_ELSE)
+ {
+ /* We expect the condition to be of the form (reg != 0) */
+ cond = XEXP (SET_SRC (cmp), 0);
+ if (GET_CODE (cond) != NE || XEXP (cond, 1) != const0_rtx)
+ return 0;
+ }
}
else
{
return 0;
if ((XEXP (condition, 0) == reg)
+ /* For the third case: */
+ || ((cc_reg != NULL_RTX)
+ && (XEXP (condition, 0) == cc_reg)
+ && (reg_orig == reg))
|| (GET_CODE (XEXP (condition, 0)) == PLUS
- && XEXP (XEXP (condition, 0), 0) == reg))
+ && XEXP (XEXP (condition, 0), 0) == reg))
{
if (GET_CODE (pattern) != PARALLEL)
- /* The second form we expect:
+ /* For the second form we expect:
(set (reg) (plus (reg) (const_int -1))
(set (pc) (if_then_else (reg != 0)
(set (reg) (plus (reg) (const_int -1)))
(additional clobbers and uses)])
- So we return that form instead.
+ For the third form we expect:
+
+ (parallel [(set (cc) (compare ((plus (reg) (const_int -1)), 0))
+ (set (reg) (plus (reg) (const_int -1)))])
+ (set (pc) (if_then_else (cc == NE)
+ (label_ref (label))
+ (pc)))
+
+ which is equivalent to the following:
+
+ (parallel [(set (cc) (compare (reg, 1))
+ (set (reg) (plus (reg) (const_int -1)))
+ (set (pc) (if_then_else (NE == cc)
+ (label_ref (label))
+ (pc))))])
+
+ So we return the second form instead for the two cases.
+
*/
condition = gen_rtx_fmt_ee (NE, VOIDmode, inc_src, const1_rtx);
describes the number of iterations of the loop. */
static bool
-doloop_valid_p (struct loop *loop, struct niter_desc *desc)
+doloop_valid_p (class loop *loop, class niter_desc *desc)
{
basic_block *body = get_loop_body (loop), bb;
- rtx insn;
+ rtx_insn *insn;
unsigned i;
bool result = true;
static bool
add_test (rtx cond, edge *e, basic_block dest)
{
- rtx seq, jump, label;
- enum machine_mode mode;
+ rtx_insn *seq, *jump;
+ rtx_code_label *label;
+ machine_mode mode;
rtx op0 = XEXP (cond, 0), op1 = XEXP (cond, 1);
enum rtx_code code = GET_CODE (cond);
basic_block bb;
+ /* The jump is supposed to handle an unlikely special case. */
+ profile_probability prob = profile_probability::guessed_never ();
mode = GET_MODE (XEXP (cond, 0));
if (mode == VOIDmode)
op0 = force_operand (op0, NULL_RTX);
op1 = force_operand (op1, NULL_RTX);
label = block_label (dest);
- do_compare_rtx_and_jump (op0, op1, code, 0, mode, NULL_RTX, NULL_RTX, label);
+ do_compare_rtx_and_jump (op0, op1, code, 0, mode, NULL_RTX, NULL, label,
+ prob);
jump = get_last_insn ();
if (!jump || !JUMP_P (jump))
}
seq = get_insns ();
+ unshare_all_rtl_in_chain (seq);
end_sequence ();
/* There always is at least the jump insn in the sequence. */
JUMP_LABEL (jump) = label;
- /* The jump is supposed to handle an unlikely special case. */
- add_reg_note (jump, REG_BR_PROB, const0_rtx);
-
LABEL_NUSES (label)++;
- make_edge (bb, dest, (*e)->flags & ~EDGE_FALLTHRU);
+ edge e2 = make_edge (bb, dest, (*e)->flags & ~EDGE_FALLTHRU);
+ e2->probability = prob;
+ (*e)->probability = prob.invert ();
+ update_br_prob_note (e2->src);
return true;
}
describes the loop, DESC describes the number of iterations of the
loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the
end of the loop. CONDITION is the condition separated from the
- DOLOOP_SEQ. COUNT is the number of iterations of the LOOP.
- ZERO_EXTEND_P says to zero extend COUNT after the increment of it to
- word_mode from FROM_MODE. */
+ DOLOOP_SEQ. COUNT is the number of iterations of the LOOP. */
static void
-doloop_modify (struct loop *loop, struct niter_desc *desc,
- rtx doloop_seq, rtx condition, rtx count,
- bool zero_extend_p, enum machine_mode from_mode)
+doloop_modify (class loop *loop, class niter_desc *desc,
+ rtx_insn *doloop_seq, rtx condition, rtx count)
{
rtx counter_reg;
rtx tmp, noloop = NULL_RTX;
- rtx sequence;
- rtx jump_insn;
- rtx jump_label;
+ rtx_insn *sequence;
+ rtx_insn *jump_insn;
+ rtx_code_label *jump_label;
int nonneg = 0;
bool increment_count;
basic_block loop_end = desc->out_edge->src;
- enum machine_mode mode;
- rtx true_prob_val;
+ scalar_int_mode mode;
+ widest_int iterations;
jump_insn = BB_END (loop_end);
{
fprintf (dump_file, "Doloop: Inserting doloop pattern (");
if (desc->const_iter)
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter);
+ fprintf (dump_file, "%" PRId64, desc->niter);
else
fputs ("runtime", dump_file);
fputs (" iterations).\n", dump_file);
}
- /* Get the probability of the original branch. If it exists we would
- need to update REG_BR_PROB of the new jump_insn. */
- true_prob_val = find_reg_note (jump_insn, REG_BR_PROB, NULL_RTX);
-
/* Discard original jump to continue loop. The original compare
result may still be live, so it cannot be discarded explicitly. */
delete_insn (jump_insn);
counter_reg = XEXP (condition, 0);
if (GET_CODE (counter_reg) == PLUS)
counter_reg = XEXP (counter_reg, 0);
- mode = GET_MODE (counter_reg);
+ /* These patterns must operate on integer counters. */
+ mode = as_a <scalar_int_mode> (GET_MODE (counter_reg));
increment_count = false;
switch (GET_CODE (condition))
/* Determine if the iteration counter will be non-negative.
Note that the maximum value loaded is iterations_max - 1. */
- if (desc->niter_max
- <= ((unsigned HOST_WIDEST_INT) 1
- << (GET_MODE_BITSIZE (mode) - 1)))
+ if (get_max_loop_iterations (loop, &iterations)
+ && wi::leu_p (iterations,
+ wi::set_bit_in_zero <widest_int>
+ (GET_MODE_PRECISION (mode) - 1)))
nonneg = 1;
break;
}
if (increment_count)
- count = simplify_gen_binary (PLUS, from_mode, count, const1_rtx);
-
- if (zero_extend_p)
- count = simplify_gen_unary (ZERO_EXTEND, word_mode,
- count, from_mode);
+ count = simplify_gen_binary (PLUS, mode, count, const1_rtx);
/* Insert initialization of the count register into the loop header. */
start_sequence ();
+ /* count has been already copied through copy_rtx. */
+ reset_used_flags (count);
+ set_used_flags (condition);
tmp = force_operand (count, counter_reg);
convert_move (counter_reg, tmp, 1);
sequence = get_insns ();
+ unshare_all_rtl_in_chain (sequence);
end_sequence ();
emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
{
rtx ass = copy_rtx (desc->noloop_assumptions);
basic_block preheader = loop_preheader_edge (loop)->src;
- basic_block set_zero
- = split_edge (loop_preheader_edge (loop));
- basic_block new_preheader
- = split_edge (loop_preheader_edge (loop));
+ basic_block set_zero = split_edge (loop_preheader_edge (loop));
+ basic_block new_preheader = split_edge (loop_preheader_edge (loop));
edge te;
/* Expand the condition testing the assumptions and if it does not pass,
redirect_edge_and_branch_force (single_succ_edge (preheader), new_preheader);
set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader);
- set_zero->count = 0;
- set_zero->frequency = 0;
+ set_zero->count = profile_count::uninitialized ();
te = single_succ_edge (preheader);
for (; ass; ass = XEXP (ass, 1))
also be very hard to show that it is impossible, so we must
handle this case. */
set_zero->count = preheader->count;
- set_zero->frequency = preheader->frequency;
}
if (EDGE_COUNT (set_zero->preds) == 0)
/* Some targets (eg, C4x) need to initialize special looping
registers. */
-#ifdef HAVE_doloop_begin
- {
- rtx init;
- unsigned level = get_loop_level (loop) + 1;
- init = gen_doloop_begin (counter_reg,
- desc->const_iter ? desc->niter_expr : const0_rtx,
- GEN_INT (desc->niter_max),
- GEN_INT (level));
- if (init)
- {
- start_sequence ();
- emit_insn (init);
- sequence = get_insns ();
- end_sequence ();
- emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
- }
- }
-#endif
+ if (targetm.have_doloop_begin ())
+ if (rtx_insn *seq = targetm.gen_doloop_begin (counter_reg, doloop_seq))
+ emit_insn_after (seq, BB_END (loop_preheader_edge (loop)->src));
/* Insert the new low-overhead looping insn. */
emit_jump_insn_after (doloop_seq, BB_END (loop_end));
add_reg_note (jump_insn, REG_NONNEG, NULL_RTX);
/* Update the REG_BR_PROB note. */
- if (true_prob_val)
+ if (desc->in_edge->probability.initialized_p ())
+ add_reg_br_prob_note (jump_insn, desc->in_edge->probability);
+}
+
+/* Called through note_stores. */
+
+static void
+record_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
+{
+ bitmap mod = (bitmap)data;
+ if (REG_P (x))
{
- /* Seems safer to use the branch probability. */
- add_reg_note (jump_insn, REG_BR_PROB,
- GEN_INT (desc->in_edge->probability));
+ unsigned int regno = REGNO (x);
+ if (HARD_REGISTER_P (x))
+ {
+ unsigned int end_regno = end_hard_regno (GET_MODE (x), regno);
+ do
+ bitmap_set_bit (mod, regno);
+ while (++regno < end_regno);
+ }
+ else
+ bitmap_set_bit (mod, regno);
}
}
modified. */
static bool
-doloop_optimize (struct loop *loop)
+doloop_optimize (class loop *loop)
{
- enum machine_mode mode;
- rtx doloop_seq, doloop_pat, doloop_reg;
- rtx iterations, count;
- rtx iterations_max;
- rtx start_label;
+ scalar_int_mode mode;
+ rtx doloop_reg;
+ rtx count;
+ widest_int iterations, iterations_max;
+ rtx_code_label *start_label;
rtx condition;
- unsigned level, est_niter;
+ unsigned level;
+ HOST_WIDE_INT est_niter;
int max_cost;
- struct niter_desc *desc;
+ class niter_desc *desc;
unsigned word_mode_size;
unsigned HOST_WIDE_INT word_mode_max;
- bool zero_extend_p = false;
+ int entered_at_top;
if (dump_file)
fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
}
mode = desc->mode;
- est_niter = 3;
- if (desc->const_iter)
- est_niter = desc->niter;
- /* If the estimate on number of iterations is reliable (comes from profile
- feedback), use it. Do not use it normally, since the expected number
- of iterations of an unrolled loop is 2. */
- if (loop->header->count)
- est_niter = expected_loop_iterations (loop);
-
- if (est_niter < 3)
+ est_niter = get_estimated_loop_iterations_int (loop);
+ if (est_niter == -1)
+ est_niter = get_likely_max_loop_iterations_int (loop);
+
+ if (est_niter >= 0 && est_niter < 3)
{
if (dump_file)
fprintf (dump_file,
"Doloop: Too few iterations (%u) to be profitable.\n",
- est_niter);
+ (unsigned int)est_niter);
return false;
}
max_cost
- = COSTS_N_INSNS (PARAM_VALUE (PARAM_MAX_ITERATIONS_COMPUTATION_COST));
- if (rtx_cost (desc->niter_expr, SET, optimize_loop_for_speed_p (loop))
+ = COSTS_N_INSNS (param_max_iterations_computation_cost);
+ if (set_src_cost (desc->niter_expr, mode, optimize_loop_for_speed_p (loop))
> max_cost)
{
if (dump_file)
return false;
}
- count = copy_rtx (desc->niter_expr);
- iterations = desc->const_iter ? desc->niter_expr : const0_rtx;
- iterations_max = GEN_INT (desc->niter_max);
+ if (desc->const_iter)
+ iterations = widest_int::from (rtx_mode_t (desc->niter_expr, mode),
+ UNSIGNED);
+ else
+ iterations = 0;
+ if (!get_max_loop_iterations (loop, &iterations_max))
+ iterations_max = 0;
level = get_loop_level (loop) + 1;
+ entered_at_top = (loop->latch == desc->in_edge->dest
+ && contains_no_active_insn_p (loop->latch));
+ if (!targetm.can_use_doloop_p (iterations, iterations_max, level,
+ entered_at_top))
+ {
+ if (dump_file)
+ fprintf (dump_file, "Loop rejected by can_use_doloop_p.\n");
+ return false;
+ }
/* Generate looping insn. If the pattern FAILs then give up trying
to modify the loop since there is some aspect the back-end does
not like. */
+ count = copy_rtx (desc->niter_expr);
start_label = block_label (desc->in_edge->dest);
doloop_reg = gen_reg_rtx (mode);
- doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
- GEN_INT (level), start_label);
+ rtx_insn *doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label);
- word_mode_size = GET_MODE_BITSIZE (word_mode);
- word_mode_max
- = ((unsigned HOST_WIDE_INT) 1 << (word_mode_size - 1) << 1) - 1;
+ word_mode_size = GET_MODE_PRECISION (word_mode);
+ word_mode_max = (HOST_WIDE_INT_1U << (word_mode_size - 1) << 1) - 1;
if (! doloop_seq
&& mode != word_mode
/* Before trying mode different from the one in that # of iterations is
computed, we must be sure that the number of iterations fits into
the new mode. */
- && (word_mode_size >= GET_MODE_BITSIZE (mode)
- || desc->niter_max <= word_mode_max))
+ && (word_mode_size >= GET_MODE_PRECISION (mode)
+ || wi::leu_p (iterations_max, word_mode_max)))
{
- if (word_mode_size > GET_MODE_BITSIZE (mode))
- {
- zero_extend_p = true;
- iterations = simplify_gen_unary (ZERO_EXTEND, word_mode,
- iterations, mode);
- iterations_max = simplify_gen_unary (ZERO_EXTEND, word_mode,
- iterations_max, mode);
- }
+ if (word_mode_size > GET_MODE_PRECISION (mode))
+ count = simplify_gen_unary (ZERO_EXTEND, word_mode, count, mode);
else
- {
- count = lowpart_subreg (word_mode, count, mode);
- iterations = lowpart_subreg (word_mode, iterations, mode);
- iterations_max = lowpart_subreg (word_mode, iterations_max, mode);
- }
+ count = lowpart_subreg (word_mode, count, mode);
PUT_MODE (doloop_reg, word_mode);
- doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
- GEN_INT (level), start_label);
+ doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label);
}
if (! doloop_seq)
{
}
/* If multiple instructions were created, the last must be the
- jump instruction. Also, a raw define_insn may yield a plain
- pattern. */
- doloop_pat = doloop_seq;
- if (INSN_P (doloop_pat))
- {
- while (NEXT_INSN (doloop_pat) != NULL_RTX)
- doloop_pat = NEXT_INSN (doloop_pat);
- if (!JUMP_P (doloop_pat))
- doloop_pat = NULL_RTX;
- }
-
- if (! doloop_pat
- || ! (condition = doloop_condition_get (doloop_pat)))
+ jump instruction. */
+ rtx_insn *doloop_insn = doloop_seq;
+ while (NEXT_INSN (doloop_insn) != NULL_RTX)
+ doloop_insn = NEXT_INSN (doloop_insn);
+ if (!JUMP_P (doloop_insn)
+ || !(condition = doloop_condition_get (doloop_insn)))
{
if (dump_file)
fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n");
return false;
}
- doloop_modify (loop, desc, doloop_seq, condition, count,
- zero_extend_p, mode);
+ /* Ensure that the new sequence doesn't clobber a register that
+ is live at the end of the block. */
+ {
+ bitmap modified = BITMAP_ALLOC (NULL);
+
+ for (rtx_insn *i = doloop_seq; i != NULL; i = NEXT_INSN (i))
+ note_stores (i, record_reg_sets, modified);
+
+ basic_block loop_end = desc->out_edge->src;
+ bool fail = bitmap_intersect_p (df_get_live_out (loop_end), modified);
+ BITMAP_FREE (modified);
+
+ if (fail)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Doloop: doloop pattern clobbers live out\n");
+ return false;
+ }
+ }
+
+ doloop_modify (loop, desc, doloop_seq, condition, count);
return true;
}
void
doloop_optimize_loops (void)
{
- loop_iterator li;
- struct loop *loop;
+ class loop *loop;
- FOR_EACH_LOOP (li, loop, 0)
+ if (optimize == 1)
+ {
+ df_live_add_problem ();
+ df_live_set_all_dirty ();
+ }
+
+ FOR_EACH_LOOP (loop, 0)
{
doloop_optimize (loop);
}
+ if (optimize == 1)
+ df_remove_problem (df_live);
+
iv_analysis_done ();
-#ifdef ENABLE_CHECKING
- verify_dominators (CDI_DOMINATORS);
- verify_loop_structure ();
-#endif
+ checking_verify_loop_structure ();
}
-#endif /* HAVE_doloop_end */
-
projects / thirdparty / gcc.git / blobdiff