#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "flags.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"
#ifdef HAVE_doloop_end
static rtx
doloop_condition_get (rtx pattern)
{
rtx cmp;
rtx inc;
rtx reg;
rtx condition;
if (GET_CODE (pattern) != PARALLEL)
return 0;
cmp = XVECEXP (pattern, 0, 0);
inc = XVECEXP (pattern, 0, 1);
if (GET_CODE (inc) != SET || ! REG_P (SET_DEST (inc)))
return 0;
reg = SET_DEST (inc);
if (GET_CODE (cmp) != SET
|| SET_DEST (cmp) != pc_rtx
|| GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
|| GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
|| XEXP (SET_SRC (cmp), 2) != pc_rtx)
return 0;
condition = XEXP (SET_SRC (cmp), 0);
if ((GET_CODE (condition) != GE && GET_CODE (condition) != NE)
|| GET_CODE (XEXP (condition, 1)) != CONST_INT)
return 0;
if (XEXP (condition, 0) == reg)
return condition;
if (GET_CODE (XEXP (condition, 0)) == PLUS
&& XEXP (XEXP (condition, 0), 0) == reg)
return condition;
return 0;
}
static bool
doloop_valid_p (struct loop *loop, struct niter_desc *desc)
{
basic_block *body = get_loop_body (loop), bb;
rtx insn;
unsigned i;
bool result = true;
if (!desc->simple_p
|| desc->assumptions
|| desc->infinite)
{
if (dump_file)
fprintf (dump_file, "Doloop: Possible infinite iteration case.\n");
result = false;
goto cleanup;
}
for (i = 0; i < loop->num_nodes; i++)
{
bb = body[i];
for (insn = BB_HEAD (bb);
insn != NEXT_INSN (BB_END (bb));
insn = NEXT_INSN (insn))
{
if (CALL_P (insn))
{
if (dump_file)
fprintf (dump_file, "Doloop: Function call in loop.\n");
result = false;
goto cleanup;
}
if (JUMP_P (insn)
&& (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_VEC))
{
if (dump_file)
fprintf (dump_file, "Doloop: Computed branch in the loop.\n");
result = false;
goto cleanup;
}
}
}
result = true;
cleanup:
free (body);
return result;
}
static void
add_test (rtx cond, basic_block bb, basic_block dest)
{
rtx seq, jump, label;
enum machine_mode mode;
rtx op0 = XEXP (cond, 0), op1 = XEXP (cond, 1);
enum rtx_code code = GET_CODE (cond);
mode = GET_MODE (XEXP (cond, 0));
if (mode == VOIDmode)
mode = GET_MODE (XEXP (cond, 1));
start_sequence ();
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);
jump = get_last_insn ();
JUMP_LABEL (jump) = label;
REG_NOTES (jump)
= gen_rtx_EXPR_LIST (REG_BR_PROB,
const0_rtx, REG_NOTES (jump));
LABEL_NUSES (label)++;
seq = get_insns ();
end_sequence ();
emit_insn_after (seq, BB_END (bb));
}
static void
doloop_modify (struct loop *loop, struct niter_desc *desc,
rtx doloop_seq, rtx condition, rtx count)
{
rtx counter_reg;
rtx tmp, noloop = NULL_RTX;
rtx sequence;
rtx jump_insn;
rtx jump_label;
int nonneg = 0, irr;
bool increment_count;
basic_block loop_end = desc->out_edge->src;
enum machine_mode mode;
jump_insn = BB_END (loop_end);
if (dump_file)
{
fprintf (dump_file, "Doloop: Inserting doloop pattern (");
if (desc->const_iter)
fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter);
else
fputs ("runtime", dump_file);
fputs (" iterations).\n", dump_file);
}
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);
increment_count = false;
switch (GET_CODE (condition))
{
case NE:
if (XEXP (condition, 1) == const1_rtx)
{
increment_count = true;
noloop = const1_rtx;
}
else if (XEXP (condition, 1) == const0_rtx)
noloop = const0_rtx;
else
abort ();
break;
case GE:
if (XEXP (condition, 1) != const0_rtx)
abort ();
noloop = constm1_rtx;
increment_count = false;
if (desc->niter_max
<= ((unsigned HOST_WIDEST_INT) 1
<< (GET_MODE_BITSIZE (mode) - 1)))
nonneg = 1;
break;
default:
abort ();
}
if (increment_count)
count = simplify_gen_binary (PLUS, mode, count, const1_rtx);
start_sequence ();
tmp = force_operand (count, counter_reg);
convert_move (counter_reg, tmp, 1);
sequence = get_insns ();
end_sequence ();
emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
if (desc->noloop_assumptions)
{
rtx ass = copy_rtx (desc->noloop_assumptions);
basic_block preheader = loop_preheader_edge (loop)->src;
basic_block set_zero
= loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
basic_block new_preheader
= loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
basic_block bb;
edge te;
gcov_type cnt;
add_test (XEXP (ass, 0), preheader, set_zero);
EDGE_SUCC (preheader, 0)->flags &= ~EDGE_FALLTHRU;
cnt = EDGE_SUCC (preheader, 0)->count;
EDGE_SUCC (preheader, 0)->probability = 0;
EDGE_SUCC (preheader, 0)->count = 0;
irr = EDGE_SUCC (preheader, 0)->flags & EDGE_IRREDUCIBLE_LOOP;
te = make_edge (preheader, new_preheader, EDGE_FALLTHRU | irr);
te->probability = REG_BR_PROB_BASE;
te->count = cnt;
set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader);
set_zero->count = 0;
set_zero->frequency = 0;
for (ass = XEXP (ass, 1); ass; ass = XEXP (ass, 1))
{
bb = loop_split_edge_with (te, NULL_RTX);
te = EDGE_SUCC (bb, 0);
add_test (XEXP (ass, 0), bb, set_zero);
make_edge (bb, set_zero, irr);
}
start_sequence ();
convert_move (counter_reg, noloop, 0);
sequence = get_insns ();
end_sequence ();
emit_insn_after (sequence, BB_END (set_zero));
}
#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,
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
emit_jump_insn_after (doloop_seq, BB_END (loop_end));
jump_insn = BB_END (loop_end);
jump_label = block_label (desc->in_edge->dest);
JUMP_LABEL (jump_insn) = jump_label;
LABEL_NUSES (jump_label)++;
desc->in_edge->flags &= ~EDGE_FALLTHRU;
desc->out_edge->flags |= EDGE_FALLTHRU;
if (nonneg)
{
REG_NOTES (jump_insn)
= gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX, REG_NOTES (jump_insn));
}
}
static bool
doloop_optimize (struct loop *loop)
{
enum machine_mode mode;
rtx doloop_seq, doloop_pat, doloop_reg;
rtx iterations, count;
rtx iterations_max;
rtx start_label;
rtx condition;
unsigned level, est_niter;
struct niter_desc *desc;
unsigned word_mode_size;
unsigned HOST_WIDE_INT word_mode_max;
if (dump_file)
fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
if (loop->ninsns > (unsigned) PARAM_VALUE (PARAM_MAX_DOLOOP_INSNS))
{
if (dump_file)
fprintf (dump_file,
"Doloop: The loop is too large.\n");
return false;
}
iv_analysis_loop_init (loop);
desc = get_simple_loop_desc (loop);
if (!doloop_valid_p (loop, desc))
{
if (dump_file)
fprintf (dump_file,
"Doloop: The loop is not suitable.\n");
return false;
}
mode = desc->mode;
est_niter = 3;
if (desc->const_iter)
est_niter = desc->niter;
if (loop->header->count)
est_niter = expected_loop_iterations (loop);
if (est_niter < 3)
{
if (dump_file)
fprintf (dump_file,
"Doloop: Too few iterations (%u) to be profitable.\n",
est_niter);
return false;
}
count = copy_rtx (desc->niter_expr);
iterations = desc->const_iter ? desc->niter_expr : const0_rtx;
iterations_max = GEN_INT (desc->niter_max);
level = get_loop_level (loop) + 1;
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);
word_mode_size = GET_MODE_BITSIZE (word_mode);
word_mode_max
= ((unsigned HOST_WIDE_INT) 1 << (word_mode_size - 1) << 1) - 1;
if (! doloop_seq
&& mode != word_mode
&& (word_mode_size >= GET_MODE_BITSIZE (mode)
|| desc->niter_max <= word_mode_max))
{
if (word_mode_size > GET_MODE_BITSIZE (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);
}
else
{
count = lowpart_subreg (word_mode, count, mode);
iterations = lowpart_subreg (word_mode, iterations, mode);
iterations_max = lowpart_subreg (word_mode, iterations_max, mode);
}
PUT_MODE (doloop_reg, word_mode);
doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
GEN_INT (level), start_label);
}
if (! doloop_seq)
{
if (dump_file)
fprintf (dump_file,
"Doloop: Target unwilling to use doloop pattern!\n");
return false;
}
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 = PATTERN (doloop_pat);
else
doloop_pat = NULL_RTX;
}
if (! doloop_pat
|| ! (condition = doloop_condition_get (doloop_pat)))
{
if (dump_file)
fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n");
return false;
}
doloop_modify (loop, desc, doloop_seq, condition, count);
return true;
}
void
doloop_optimize_loops (struct loops *loops)
{
unsigned i;
struct loop *loop;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (!loop)
continue;
doloop_optimize (loop);
}
iv_analysis_done ();
#ifdef ENABLE_CHECKING
verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
#endif
}
#endif