/* Perform doloop optimizations
- Copyright (C) 2004-2016 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 "rtl.h"
#include "tree.h"
#include "cfghooks.h"
+#include "memmodel.h"
#include "emit-rtl.h"
#include "dojump.h"
#include "expr.h"
#include "cfgloop.h"
#include "cfgrtl.h"
-#include "params.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.
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;
}
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 *insn;
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, 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_int_reg_note (jump, REG_BR_PROB, 0);
-
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,
+doloop_modify (class loop *loop, class niter_desc *desc,
rtx_insn *doloop_seq, rtx condition, rtx count)
{
rtx counter_reg;
int nonneg = 0;
bool increment_count;
basic_block loop_end = desc->out_edge->src;
- machine_mode mode;
- rtx true_prob_val;
+ scalar_int_mode mode;
widest_int iterations;
jump_insn = BB_END (loop_end);
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))
}
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)
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_int_reg_note (jump_insn, REG_BR_PROB, 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)
{
- machine_mode mode;
+ 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;
}
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));
+ = 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 (desc->const_iter)
- iterations = widest_int::from (std::make_pair (desc->niter_expr, mode),
+ iterations = widest_int::from (rtx_mode_t (desc->niter_expr, mode),
UNSIGNED);
else
iterations = 0;
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
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)
{
- struct loop *loop;
+ class loop *loop;
+
+ 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 ();
checking_verify_loop_structure ();
projects / thirdparty / gcc.git / blobdiff