#include "config.h"
#include "system.h"
#include "rtl.h"
#include "flags.h"
#include "expr.h"
#include "loop.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "toplev.h"
#include "tm_p.h"
#ifdef HAVE_doloop_end
static rtx doloop_condition_get
PARAMS ((rtx));
static unsigned HOST_WIDE_INT doloop_iterations_max
PARAMS ((const struct loop_info *, enum machine_mode, int));
static int doloop_valid_p
PARAMS ((const struct loop *, rtx));
static int doloop_modify
PARAMS ((const struct loop *, rtx, rtx, rtx, rtx, rtx));
static int doloop_modify_runtime
PARAMS ((const struct loop *, rtx, rtx, rtx, enum machine_mode, rtx));
static rtx
doloop_condition_get (pattern)
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 unsigned HOST_WIDE_INT
doloop_iterations_max (loop_info, mode, nonneg)
const struct loop_info *loop_info;
enum machine_mode mode;
int nonneg;
{
unsigned HOST_WIDE_INT n_iterations_max;
enum rtx_code code;
rtx min_value;
rtx max_value;
HOST_WIDE_INT abs_inc;
int neg_inc;
neg_inc = 0;
abs_inc = INTVAL (loop_info->increment);
if (abs_inc < 0)
{
abs_inc = -abs_inc;
neg_inc = 1;
}
if (neg_inc)
{
code = swap_condition (loop_info->comparison_code);
min_value = loop_info->final_equiv_value;
max_value = loop_info->initial_equiv_value;
}
else
{
code = loop_info->comparison_code;
min_value = loop_info->initial_equiv_value;
max_value = loop_info->final_equiv_value;
}
switch (code)
{
case LTU:
case LEU:
{
unsigned HOST_WIDE_INT umax;
unsigned HOST_WIDE_INT umin;
if (GET_CODE (min_value) == CONST_INT)
umin = INTVAL (min_value);
else
umin = 0;
if (GET_CODE (max_value) == CONST_INT)
umax = INTVAL (max_value);
else
umax = ((unsigned) 2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
n_iterations_max = umax - umin;
break;
}
case LT:
case LE:
{
HOST_WIDE_INT smax;
HOST_WIDE_INT smin;
if (GET_CODE (min_value) == CONST_INT)
smin = INTVAL (min_value);
else
smin = -((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1));
if (GET_CODE (max_value) == CONST_INT)
smax = INTVAL (max_value);
else
smax = ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
n_iterations_max = smax - smin;
break;
}
case NE:
if (GET_CODE (min_value) == CONST_INT
&& GET_CODE (max_value) == CONST_INT)
n_iterations_max = INTVAL (max_value) - INTVAL (min_value);
else
n_iterations_max = ((unsigned) 2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
break;
default:
return 0;
}
n_iterations_max /= abs_inc;
if (nonneg
&& n_iterations_max > ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)))
n_iterations_max = ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
return n_iterations_max;
}
static int
doloop_valid_p (loop, jump_insn)
const struct loop *loop;
rtx jump_insn;
{
const struct loop_info *loop_info = LOOP_INFO (loop);
if (! any_condjump_p (jump_insn)
|| ! onlyjump_p (jump_insn))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Invalid jump at loop end.\n");
return 0;
}
if (loop_info->n_iterations == loop_info->unroll_number)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Loop completely unrolled.\n");
return 0;
}
if (loop_info->has_multiple_exit_targets || loop->exit_count)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Loop has multiple exit targets.\n");
return 0;
}
if (loop_info->has_indirect_jump)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Indirect jump in function.\n");
return 0;
}
if (loop_info->has_call)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Function call in loop.\n");
return 0;
}
if (loop_info->has_tablejump)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Computed branch in the loop.\n");
return 0;
}
if (! loop_info->increment)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Could not determine iteration info.\n");
return 0;
}
if (GET_CODE (loop_info->increment) != CONST_INT)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Increment not an integer constant.\n");
return 0;
}
if (loop_info->comparison_code == NE
&& !loop_info->preconditioned
&& INTVAL (loop_info->increment) != -1
&& INTVAL (loop_info->increment) != 1)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: NE loop with non-unity increment.\n");
return 0;
}
if (! loop_info->n_iterations
&& ((loop_info->comparison_code == LEU
&& INTVAL (loop_info->increment) > 0)
|| (loop_info->comparison_code == GEU
&& INTVAL (loop_info->increment) < 0)
|| (loop_info->comparison_code == LTU
&& INTVAL (loop_info->increment) > 1)
|| (loop_info->comparison_code == GTU
&& INTVAL (loop_info->increment) < -1)))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Possible infinite iteration case ignored.\n");
}
return 1;
}
static int
doloop_modify (loop, iterations, iterations_max,
doloop_seq, start_label, condition)
const struct loop *loop;
rtx iterations;
rtx iterations_max;
rtx doloop_seq;
rtx start_label;
rtx condition;
{
rtx counter_reg;
rtx count;
rtx sequence;
rtx jump_insn;
int nonneg = 0;
int decrement_count;
jump_insn = prev_nonnote_insn (loop->end);
if (loop_dump_stream)
{
fprintf (loop_dump_stream, "Doloop: Inserting doloop pattern (");
if (GET_CODE (iterations) == CONST_INT)
fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
INTVAL (iterations));
else
fputs ("runtime", loop_dump_stream);
fputs (" iterations).", loop_dump_stream);
}
emit_label_after (start_label, loop->top ? loop->top : loop->start);
LABEL_NUSES (start_label)++;
delete_related_insns (jump_insn);
counter_reg = XEXP (condition, 0);
if (GET_CODE (counter_reg) == PLUS)
counter_reg = XEXP (counter_reg, 0);
start_sequence ();
count = iterations;
decrement_count = 0;
switch (GET_CODE (condition))
{
case NE:
if (XEXP (condition, 1) == const0_rtx)
decrement_count = 1;
else if (XEXP (condition, 1) != const1_rtx)
abort ();
break;
case GE:
if (XEXP (condition, 1) != const0_rtx)
abort ();
decrement_count = 1;
if ((unsigned HOST_WIDE_INT) INTVAL (iterations_max)
<= ((unsigned) 1 << (GET_MODE_BITSIZE (GET_MODE (counter_reg)) - 1)))
nonneg = 1;
break;
default:
abort ();
}
if (decrement_count)
{
if (GET_CODE (count) == CONST_INT)
count = GEN_INT (INTVAL (count) - 1);
else
count = expand_simple_binop (GET_MODE (counter_reg), MINUS,
count, GEN_INT (1),
0, 0, OPTAB_LIB_WIDEN);
}
convert_move (counter_reg, count, 1);
sequence = get_insns ();
end_sequence ();
emit_insn_before (sequence, loop->start);
#ifdef HAVE_doloop_begin
{
rtx init;
init = gen_doloop_begin (counter_reg,
GET_CODE (iterations) == CONST_INT
? iterations : const0_rtx, iterations_max,
GEN_INT (loop->level));
if (init)
{
start_sequence ();
emit_insn (init);
sequence = get_insns ();
end_sequence ();
emit_insn_after (sequence, loop->start);
}
}
#endif
emit_jump_insn_before (doloop_seq, loop->end);
jump_insn = prev_nonnote_insn (loop->end);
JUMP_LABEL (jump_insn) = start_label;
if (nonneg)
{
REG_NOTES (jump_insn)
= gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX, REG_NOTES (jump_insn));
}
return 1;
}
static int
doloop_modify_runtime (loop, iterations_max,
doloop_seq, start_label, mode, condition)
const struct loop *loop;
rtx iterations_max;
rtx doloop_seq;
rtx start_label;
enum machine_mode mode;
rtx condition;
{
const struct loop_info *loop_info = LOOP_INFO (loop);
HOST_WIDE_INT abs_inc;
HOST_WIDE_INT abs_loop_inc;
int neg_inc;
rtx diff;
rtx sequence;
rtx iterations;
rtx initial_value;
rtx final_value;
rtx increment;
int unsigned_p;
enum rtx_code comparison_code;
increment = loop_info->increment;
initial_value = loop_info->initial_value;
final_value = loop_info->final_value;
neg_inc = 0;
abs_inc = INTVAL (increment);
if (abs_inc < 0)
{
abs_inc = -abs_inc;
neg_inc = 1;
}
comparison_code = loop_info->comparison_code;
unsigned_p = (comparison_code == LTU
|| comparison_code == LEU
|| comparison_code == GTU
|| comparison_code == GEU
|| comparison_code == NE);
start_sequence ();
diff = expand_simple_binop (mode, MINUS,
copy_rtx (neg_inc ? initial_value : final_value),
copy_rtx (neg_inc ? final_value : initial_value),
NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
if (loop->scan_start)
{
rtx iteration_var = loop_info->iteration_var;
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
{
struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
}
else
abort ();
if (INSN_UID (bl->biv->insn) < max_uid_for_loop
&& INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Basic induction var skips initial incr.\n");
diff = expand_simple_binop (mode, PLUS, diff, GEN_INT (abs_inc),
diff, unsigned_p, OPTAB_LIB_WIDEN);
}
}
abs_loop_inc = abs_inc * loop_info->unroll_number;
if (abs_loop_inc != 1)
{
int shift_count;
shift_count = exact_log2 (abs_loop_inc);
if (shift_count < 0)
abort ();
diff = expand_simple_binop (GET_MODE (diff), PLUS,
diff, GEN_INT (abs_loop_inc - 1),
diff, 1, OPTAB_LIB_WIDEN);
diff = expand_simple_binop (GET_MODE (diff), LSHIFTRT,
diff, GEN_INT (shift_count),
diff, 1, OPTAB_LIB_WIDEN);
}
iterations = diff;
if (! loop->vtop)
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "Doloop: Do-while loop.\n");
if (loop_info->unroll_number == 1 && comparison_code != NE)
{
rtx label;
label = gen_label_rtx();
emit_cmp_and_jump_insns (copy_rtx (initial_value),
copy_rtx (loop_info->comparison_value),
comparison_code, NULL_RTX, mode, 0,
label);
JUMP_LABEL (get_last_insn ()) = label;
LABEL_NUSES (label)++;
emit_move_insn (iterations, const1_rtx);
emit_label (label);
}
}
sequence = get_insns ();
end_sequence ();
emit_insn_before (sequence, loop->start);
return doloop_modify (loop, iterations, iterations_max, doloop_seq,
start_label, condition);
}
int
doloop_optimize (loop)
const struct loop *loop;
{
struct loop_info *loop_info = LOOP_INFO (loop);
rtx initial_value;
rtx final_value;
rtx increment;
rtx jump_insn;
enum machine_mode mode;
unsigned HOST_WIDE_INT n_iterations;
unsigned HOST_WIDE_INT n_iterations_max;
rtx doloop_seq, doloop_pat, doloop_reg;
rtx iterations;
rtx iterations_max;
rtx start_label;
rtx condition;
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Processing loop %d, enclosed levels %d.\n",
loop->num, loop->level);
jump_insn = prev_nonnote_insn (loop->end);
if (! doloop_valid_p (loop, jump_insn))
return 0;
if (! precondition_loop_p (loop, &initial_value, &final_value,
&increment, &mode))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Cannot precondition loop.\n");
return 0;
}
n_iterations = loop_info->n_iterations;
if (n_iterations)
{
n_iterations_max = n_iterations;
}
else
{
int nonneg = find_reg_note (jump_insn, REG_NONNEG, 0) != 0;
n_iterations_max = doloop_iterations_max (loop_info, mode, nonneg);
if (! n_iterations_max)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Not normal loop.\n");
return 0;
}
}
n_iterations /= loop_info->unroll_number;
n_iterations_max /= loop_info->unroll_number;
if (n_iterations && n_iterations < 3)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Too few iterations (%ld) to be profitable.\n",
(long int) n_iterations);
return 0;
}
iterations = GEN_INT (n_iterations);
iterations_max = GEN_INT (n_iterations_max);
start_label = gen_label_rtx ();
doloop_reg = gen_reg_rtx (mode);
doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
GEN_INT (loop->level), start_label);
if (! doloop_seq && mode != ABI_WORD_MODE)
{
PUT_MODE (doloop_reg, ABI_WORD_MODE);
doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
GEN_INT (loop->level), start_label);
}
if (! doloop_seq)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Target unwilling to use doloop pattern!\n");
return 0;
}
doloop_pat = doloop_seq;
if (INSN_P (doloop_pat))
{
while (NEXT_INSN (doloop_pat) != NULL_RTX)
doloop_pat = NEXT_INSN (doloop_pat);
if (GET_CODE (doloop_pat) == JUMP_INSN)
doloop_pat = PATTERN (doloop_pat);
else
doloop_pat = NULL_RTX;
}
if (! doloop_pat
|| ! (condition = doloop_condition_get (doloop_pat)))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Doloop: Unrecognizable doloop pattern!\n");
return 0;
}
if (n_iterations != 0)
return doloop_modify (loop, iterations, iterations_max, doloop_seq,
start_label, condition);
else
return doloop_modify_runtime (loop, iterations_max, doloop_seq,
start_label, mode, condition);
}
#endif