/* Perform doloop optimizations
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010
- 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 "diagnostic-core.h"
-#include "tm_p.h"
#include "cfgloop.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;
if (GET_CODE (pattern) != PARALLEL)
{
rtx cond;
- rtx prev_insn = prev_nondebug_insn (doloop_pat);
+ rtx_insn *prev_insn = prev_nondebug_insn (doloop_pat);
rtx cmp_arg1, cmp_arg2;
rtx cmp_orig;
}
else
inc = PATTERN (prev_insn);
- /* 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 (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
{
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, -1);
+ 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;
}
+/* Fold (add -1; zero_ext; add +1) operations to zero_ext if not wrapping. i.e:
+
+ 73: r145:SI=r123:DI#0-0x1
+ 74: r144:DI=zero_extend (r145:SI)
+ 75: r143:DI=r144:DI+0x1
+ ...
+ 31: r135:CC=cmp (r123:DI,0)
+ 72: {pc={(r143:DI!=0x1)?L70:pc};r143:DI=r143:DI-0x1;...}
+
+ r123:DI#0-0x1 is param count derived from loop->niter_expr equal to number of
+ loop iterations, if loop iterations expression doesn't overflow, then
+ (zero_extend (r123:DI#0-1))+1 can be simplified to zero_extend. */
+
+static rtx
+doloop_simplify_count (class loop *loop, scalar_int_mode mode, rtx count)
+{
+ widest_int iterations;
+ if (GET_CODE (count) == ZERO_EXTEND)
+ {
+ rtx extop0 = XEXP (count, 0);
+ if (GET_CODE (extop0) == PLUS)
+ {
+ rtx addop0 = XEXP (extop0, 0);
+ rtx addop1 = XEXP (extop0, 1);
+
+ if (get_max_loop_iterations (loop, &iterations)
+ && wi::ltu_p (iterations, GET_MODE_MASK (GET_MODE (addop0)))
+ && addop1 == constm1_rtx)
+ return simplify_gen_unary (ZERO_EXTEND, mode, addop0,
+ GET_MODE (addop0));
+ }
+ }
+
+ return simplify_gen_binary (PLUS, mode, count, const1_rtx);
+}
+
/* Modify the loop to use the low-overhead looping insn where LOOP
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
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)
+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_PRECISION (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, mode, count, const1_rtx);
+ count = doloop_simplify_count (loop, mode, count);
/* 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;
+ 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 (set_src_cost (desc->niter_expr, 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_PRECISION (word_mode);
- word_mode_max
- = ((unsigned HOST_WIDE_INT) 1 << (word_mode_size - 1) << 1) - 1;
+ 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_PRECISION (mode)
- || desc->niter_max <= word_mode_max))
+ || wi::leu_p (iterations_max, word_mode_max)))
{
if (word_mode_size > GET_MODE_PRECISION (mode))
- {
- count = simplify_gen_unary (ZERO_EXTEND, word_mode,
- count, mode);
- iterations = simplify_gen_unary (ZERO_EXTEND, word_mode,
- iterations, mode);
- iterations_max = simplify_gen_unary (ZERO_EXTEND, word_mode,
- iterations_max, 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;
}
+ /* 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;
+
+ if (optimize == 1)
+ {
+ df_live_add_problem ();
+ df_live_set_all_dirty ();
+ }
- FOR_EACH_LOOP (li, loop, 0)
+ FOR_EACH_LOOP (loop, 0)
{
doloop_optimize (loop);
}
+ if (optimize == 1)
+ df_remove_problem (df_live);
+
iv_analysis_done ();
-#ifdef ENABLE_CHECKING
- verify_loop_structure ();
-#endif
+ checking_verify_loop_structure ();
}
-#endif /* HAVE_doloop_end */
-
projects / thirdparty / gcc.git / blobdiff