/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992, 93, 94, 95, 97, 1998 Free Software Foundation, Inc.
+ Copyright (C) 1992, 1993, 1994, 1995, 1997, 1998, 1999, 2000, 2001
+ Free Software Foundation, Inc.
Contributed by James E. Wilson, Cygnus Support/UC Berkeley.
This file is part of GNU CC.
int iterations = (len + 1) >> 1;
int i;
for (p; p < q; p++, q--;)
- {
- tmp = *q;
- *q = *p;
- *p = tmp;
- }
+ {
+ tmp = *q;
+ *q = *p;
+ *p = tmp;
+ }
}
Note that:
start value = p = &buffer + current_iteration
#define NUM_FACTORS 4
-struct _factor { int factor, count; } factors[NUM_FACTORS]
- = { {2, 0}, {3, 0}, {5, 0}, {7, 0}};
-
+struct _factor { int factor, count; }
+factors[NUM_FACTORS] = { {2, 0}, {3, 0}, {5, 0}, {7, 0}};
+
/* Describes the different types of loop unrolling performed. */
-enum unroll_types { UNROLL_COMPLETELY, UNROLL_MODULO, UNROLL_NAIVE };
+enum unroll_types
+{
+ UNROLL_COMPLETELY,
+ UNROLL_MODULO,
+ UNROLL_NAIVE
+};
#include "config.h"
#include "system.h"
#include "rtl.h"
+#include "tm_p.h"
#include "insn-config.h"
#include "integrate.h"
#include "regs.h"
#include "recog.h"
#include "flags.h"
+#include "function.h"
#include "expr.h"
#include "loop.h"
#include "toplev.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "predict.h"
/* This controls which loops are unrolled, and by how much we unroll
them. */
/* Forward declarations. */
-static void init_reg_map PROTO((struct inline_remap *, int));
-static rtx calculate_giv_inc PROTO((rtx, rtx, int));
-static rtx initial_reg_note_copy PROTO((rtx, struct inline_remap *));
-static void final_reg_note_copy PROTO((rtx, struct inline_remap *));
-static void copy_loop_body PROTO((rtx, rtx, struct inline_remap *, rtx, int,
- enum unroll_types, rtx, rtx, rtx, rtx));
-static void iteration_info PROTO((rtx, rtx *, rtx *, rtx, rtx));
-static int find_splittable_regs PROTO((enum unroll_types, rtx, rtx, rtx, int,
- unsigned HOST_WIDE_INT));
-static int find_splittable_givs PROTO((struct iv_class *, enum unroll_types,
- rtx, rtx, rtx, int));
-static int reg_dead_after_loop PROTO((rtx, rtx, rtx));
-static rtx fold_rtx_mult_add PROTO((rtx, rtx, rtx, enum machine_mode));
-static int verify_addresses PROTO((struct induction *, rtx, int));
-static rtx remap_split_bivs PROTO((rtx));
+static void init_reg_map PARAMS ((struct inline_remap *, int));
+static rtx calculate_giv_inc PARAMS ((rtx, rtx, unsigned int));
+static rtx initial_reg_note_copy PARAMS ((rtx, struct inline_remap *));
+static void final_reg_note_copy PARAMS ((rtx *, struct inline_remap *));
+static void copy_loop_body PARAMS ((struct loop *, rtx, rtx,
+ struct inline_remap *, rtx, int,
+ enum unroll_types, rtx, rtx, rtx, rtx));
+static int find_splittable_regs PARAMS ((const struct loop *,
+ enum unroll_types, int));
+static int find_splittable_givs PARAMS ((const struct loop *,
+ struct iv_class *, enum unroll_types,
+ rtx, int));
+static int reg_dead_after_loop PARAMS ((const struct loop *, rtx));
+static rtx fold_rtx_mult_add PARAMS ((rtx, rtx, rtx, enum machine_mode));
+static int verify_addresses PARAMS ((struct induction *, rtx, int));
+static rtx remap_split_bivs PARAMS ((struct loop *, rtx));
+static rtx find_common_reg_term PARAMS ((rtx, rtx));
+static rtx subtract_reg_term PARAMS ((rtx, rtx));
+static rtx loop_find_equiv_value PARAMS ((const struct loop *, rtx));
+static rtx ujump_to_loop_cont PARAMS ((rtx, rtx));
/* Try to unroll one loop and split induction variables in the loop.
- The loop is described by the arguments LOOP_END, INSN_COUNT, and
- LOOP_START. END_INSERT_BEFORE indicates where insns should be added
- which need to be executed when the loop falls through. STRENGTH_REDUCTION_P
- indicates whether information generated in the strength reduction pass
- is available.
+ The loop is described by the arguments LOOP and INSN_COUNT.
+ STRENGTH_REDUCTION_P indicates whether information generated in the
+ strength reduction pass is available.
This function is intended to be called from within `strength_reduce'
in loop.c. */
void
-unroll_loop (loop_end, insn_count, loop_start, end_insert_before,
- loop_info, strength_reduce_p)
- rtx loop_end;
+unroll_loop (loop, insn_count, strength_reduce_p)
+ struct loop *loop;
int insn_count;
- rtx loop_start;
- rtx end_insert_before;
- struct loop_info *loop_info;
int strength_reduce_p;
{
- int i, j, temp;
+ struct loop_info *loop_info = LOOP_INFO (loop);
+ struct loop_ivs *ivs = LOOP_IVS (loop);
+ int i, j;
+ unsigned int r;
+ unsigned HOST_WIDE_INT temp;
int unroll_number = 1;
rtx copy_start, copy_end;
rtx insn, sequence, pattern, tem;
int max_labelno, max_insnno;
rtx insert_before;
struct inline_remap *map;
- char *local_label;
+ char *local_label = NULL;
char *local_regno;
- int maxregnum;
- int new_maxregnum;
+ unsigned int max_local_regnum;
+ unsigned int maxregnum;
rtx exit_label = 0;
rtx start_label;
struct iv_class *bl;
int splitting_not_safe = 0;
- enum unroll_types unroll_type;
+ enum unroll_types unroll_type = UNROLL_NAIVE;
int loop_preconditioned = 0;
rtx safety_label;
/* This points to the last real insn in the loop, which should be either
a JUMP_INSN (for conditional jumps) or a BARRIER (for unconditional
jumps). */
rtx last_loop_insn;
+ rtx loop_start = loop->start;
+ rtx loop_end = loop->end;
/* Don't bother unrolling huge loops. Since the minimum factor is
two, loops greater than one half of MAX_UNROLLED_INSNS will never
block_begins++;
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
block_ends++;
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
+ || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
+ {
+ /* Note, would be nice to add code to unroll EH
+ regions, but until that time, we punt (don't
+ unroll). For the proper way of doing it, see
+ expand_inline_function. */
+
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Unrolling failure: cannot unroll EH regions.\n");
+ return;
+ }
}
}
if (loop_dump_stream && loop_info->n_iterations > 0)
{
fputs ("Loop unrolling: ", loop_dump_stream);
- fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
loop_info->n_iterations);
fputs (" iterations.\n", loop_dump_stream);
}
if (loop_info->n_iterations == 1)
{
+ /* Handle the case where the loop begins with an unconditional
+ jump to the loop condition. Make sure to delete the jump
+ insn, otherwise the loop body will never execute. */
+
+ rtx ujump = ujump_to_loop_cont (loop->start, loop->cont);
+ if (ujump)
+ delete_insn (ujump);
+
/* If number of iterations is exactly 1, then eliminate the compare and
branch at the end of the loop since they will never be taken.
Then return, since no other action is needed here. */
else if (GET_CODE (last_loop_insn) == JUMP_INSN)
{
#ifdef HAVE_cc0
- /* The immediately preceding insn is a compare which must be
- deleted. */
- delete_insn (last_loop_insn);
- delete_insn (PREV_INSN (last_loop_insn));
-#else
- /* The immediately preceding insn may not be the compare, so don't
- delete it. */
+ rtx prev = PREV_INSN (last_loop_insn);
+#endif
delete_insn (last_loop_insn);
+#ifdef HAVE_cc0
+ /* The immediately preceding insn may be a compare which must be
+ deleted. */
+ if (sets_cc0_p (prev))
+ delete_insn (prev);
#endif
}
+
+ /* Remove the loop notes since this is no longer a loop. */
+ if (loop->vtop)
+ delete_insn (loop->vtop);
+ if (loop->cont)
+ delete_insn (loop->cont);
+ if (loop_start)
+ delete_insn (loop_start);
+ if (loop_end)
+ delete_insn (loop_end);
+
return;
}
else if (loop_info->n_iterations > 0
- && loop_info->n_iterations * insn_count < MAX_UNROLLED_INSNS)
+ /* Avoid overflow in the next expression. */
+ && loop_info->n_iterations < MAX_UNROLLED_INSNS
+ && loop_info->n_iterations * insn_count < MAX_UNROLLED_INSNS)
{
unroll_number = loop_info->n_iterations;
unroll_type = UNROLL_COMPLETELY;
if (unroll_number == 1)
{
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: No factors found.\n");
+ fprintf (loop_dump_stream, "Loop unrolling: No factors found.\n");
}
else
unroll_type = UNROLL_MODULO;
}
-
/* Default case, calculate number of times to unroll loop based on its
size. */
- if (unroll_number == 1)
+ if (unroll_type == UNROLL_NAIVE)
{
if (8 * insn_count < MAX_UNROLLED_INSNS)
unroll_number = 8;
unroll_number = 4;
else
unroll_number = 2;
-
- unroll_type = UNROLL_NAIVE;
}
/* Now we know how many times to unroll the loop. */
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Unrolling loop %d times.\n", unroll_number);
-
+ fprintf (loop_dump_stream, "Unrolling loop %d times.\n", unroll_number);
if (unroll_type == UNROLL_COMPLETELY || unroll_type == UNROLL_MODULO)
{
copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
else if (GET_CODE (last_loop_insn) == JUMP_INSN)
{
+ copy_end = PREV_INSN (last_loop_insn);
#ifdef HAVE_cc0
- /* The instruction immediately before the JUMP_INSN is a compare
+ /* The instruction immediately before the JUMP_INSN may be a compare
instruction which we do not want to copy. */
- copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
-#else
- /* The instruction immediately before the JUMP_INSN may not be the
- compare, so we must copy it. */
- copy_end = PREV_INSN (last_loop_insn);
+ if (sets_cc0_p (PREV_INSN (copy_end)))
+ copy_end = PREV_INSN (copy_end);
#endif
}
else
}
else if (GET_CODE (last_loop_insn) == JUMP_INSN)
{
+ insert_before = last_loop_insn;
#ifdef HAVE_cc0
- /* The instruction immediately before the JUMP_INSN is a compare
+ /* The instruction immediately before the JUMP_INSN may be a compare
instruction which we do not want to copy or delete. */
- insert_before = PREV_INSN (last_loop_insn);
- copy_end = PREV_INSN (insert_before);
-#else
- /* The instruction immediately before the JUMP_INSN may not be the
- compare, so we must copy it. */
- insert_before = last_loop_insn;
- copy_end = PREV_INSN (last_loop_insn);
+ if (sets_cc0_p (PREV_INSN (insert_before)))
+ insert_before = PREV_INSN (insert_before);
#endif
+ copy_end = PREV_INSN (insert_before);
}
else
{
if (unroll_type == UNROLL_NAIVE
&& GET_CODE (last_loop_insn) == BARRIER
+ && GET_CODE (PREV_INSN (last_loop_insn)) == JUMP_INSN
&& start_label != JUMP_LABEL (PREV_INSN (last_loop_insn)))
{
/* In this case, we must copy the jump and barrier, because they will
max_labelno = max_label_num ();
max_insnno = get_max_uid ();
- map = (struct inline_remap *) alloca (sizeof (struct inline_remap));
+ /* Various paths through the unroll code may reach the "egress" label
+ without initializing fields within the map structure.
- map->integrating = 0;
+ To be safe, we use xcalloc to zero the memory. */
+ map = (struct inline_remap *) xcalloc (1, sizeof (struct inline_remap));
/* Allocate the label map. */
if (max_labelno > 0)
{
- map->label_map = (rtx *) alloca (max_labelno * sizeof (rtx));
+ map->label_map = (rtx *) xmalloc (max_labelno * sizeof (rtx));
- local_label = (char *) alloca (max_labelno);
- bzero (local_label, max_labelno);
+ local_label = (char *) xcalloc (max_labelno, sizeof (char));
}
- else
- map->label_map = 0;
/* Search the loop and mark all local labels, i.e. the ones which have to
be distinct labels when copied. For all labels which might be
for (i = 0; i < len; i++)
{
label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
- set_label_in_map (map,
- CODE_LABEL_NUMBER (label),
- label);
+ set_label_in_map (map, CODE_LABEL_NUMBER (label), label);
}
}
}
- else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)))
+ if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)))
set_label_in_map (map, CODE_LABEL_NUMBER (XEXP (note, 0)),
XEXP (note, 0));
}
/* Allocate space for the insn map. */
- map->insn_map = (rtx *) alloca (max_insnno * sizeof (rtx));
+ map->insn_map = (rtx *) xmalloc (max_insnno * sizeof (rtx));
/* Set this to zero, to indicate that we are doing loop unrolling,
not function inlining. */
/* The preconditioning code may allocate two new pseudo registers. */
maxregnum = max_reg_num ();
+ /* local_regno is only valid for regnos < max_local_regnum. */
+ max_local_regnum = maxregnum;
+
/* Allocate and zero out the splittable_regs and addr_combined_regs
arrays. These must be zeroed here because they will be used if
loop preconditioning is performed, and must be zero for that case.
preconditioning code and find_splittable_regs will never be used
to access the splittable_regs[] and addr_combined_regs[] arrays. */
- splittable_regs = (rtx *) alloca (maxregnum * sizeof (rtx));
- bzero ((char *) splittable_regs, maxregnum * sizeof (rtx));
- splittable_regs_updates = (int *) alloca (maxregnum * sizeof (int));
- bzero ((char *) splittable_regs_updates, maxregnum * sizeof (int));
+ splittable_regs = (rtx *) xcalloc (maxregnum, sizeof (rtx));
+ splittable_regs_updates = (int *) xcalloc (maxregnum, sizeof (int));
addr_combined_regs
- = (struct induction **) alloca (maxregnum * sizeof (struct induction *));
- bzero ((char *) addr_combined_regs, maxregnum * sizeof (struct induction *));
- /* We must limit it to max_reg_before_loop, because only these pseudo
- registers have valid regno_first_uid info. Any register created after
- that is unlikely to be local to the loop anyways. */
- local_regno = (char *) alloca (max_reg_before_loop);
- bzero (local_regno, max_reg_before_loop);
+ = (struct induction **) xcalloc (maxregnum, sizeof (struct induction *));
+ local_regno = (char *) xcalloc (maxregnum, sizeof (char));
/* Mark all local registers, i.e. the ones which are referenced only
inside the loop. */
if (INSN_UID (copy_end) < max_uid_for_loop)
- {
- int copy_start_luid = INSN_LUID (copy_start);
- int copy_end_luid = INSN_LUID (copy_end);
-
- /* If a register is used in the jump insn, we must not duplicate it
- since it will also be used outside the loop. */
- if (GET_CODE (copy_end) == JUMP_INSN)
- copy_end_luid--;
- /* If copy_start points to the NOTE that starts the loop, then we must
- use the next luid, because invariant pseudo-regs moved out of the loop
- have their lifetimes modified to start here, but they are not safe
- to duplicate. */
- if (copy_start == loop_start)
- copy_start_luid++;
-
- /* If a pseudo's lifetime is entirely contained within this loop, then we
- can use a different pseudo in each unrolled copy of the loop. This
- results in better code. */
- for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; ++j)
- if (REGNO_FIRST_UID (j) > 0 && REGNO_FIRST_UID (j) <= max_uid_for_loop
- && uid_luid[REGNO_FIRST_UID (j)] >= copy_start_luid
- && REGNO_LAST_UID (j) > 0 && REGNO_LAST_UID (j) <= max_uid_for_loop
- && uid_luid[REGNO_LAST_UID (j)] <= copy_end_luid)
- {
- /* However, we must also check for loop-carried dependencies.
- If the value the pseudo has at the end of iteration X is
- used by iteration X+1, then we can not use a different pseudo
- for each unrolled copy of the loop. */
- /* A pseudo is safe if regno_first_uid is a set, and this
- set dominates all instructions from regno_first_uid to
- regno_last_uid. */
- /* ??? This check is simplistic. We would get better code if
- this check was more sophisticated. */
- if (set_dominates_use (j, REGNO_FIRST_UID (j), REGNO_LAST_UID (j),
- copy_start, copy_end))
- local_regno[j] = 1;
+ {
+ int copy_start_luid = INSN_LUID (copy_start);
+ int copy_end_luid = INSN_LUID (copy_end);
- if (loop_dump_stream)
- {
- if (local_regno[j])
- fprintf (loop_dump_stream, "Marked reg %d as local\n", j);
- else
- fprintf (loop_dump_stream, "Did not mark reg %d as local\n",
- j);
- }
- }
- }
+ /* If a register is used in the jump insn, we must not duplicate it
+ since it will also be used outside the loop. */
+ if (GET_CODE (copy_end) == JUMP_INSN)
+ copy_end_luid--;
+
+ /* If we have a target that uses cc0, then we also must not duplicate
+ the insn that sets cc0 before the jump insn, if one is present. */
+#ifdef HAVE_cc0
+ if (GET_CODE (copy_end) == JUMP_INSN
+ && sets_cc0_p (PREV_INSN (copy_end)))
+ copy_end_luid--;
+#endif
+
+ /* If copy_start points to the NOTE that starts the loop, then we must
+ use the next luid, because invariant pseudo-regs moved out of the loop
+ have their lifetimes modified to start here, but they are not safe
+ to duplicate. */
+ if (copy_start == loop_start)
+ copy_start_luid++;
+
+ /* If a pseudo's lifetime is entirely contained within this loop, then we
+ can use a different pseudo in each unrolled copy of the loop. This
+ results in better code. */
+ /* We must limit the generic test to max_reg_before_loop, because only
+ these pseudo registers have valid regno_first_uid info. */
+ for (r = FIRST_PSEUDO_REGISTER; r < max_reg_before_loop; ++r)
+ if (REGNO_FIRST_UID (r) > 0 && REGNO_FIRST_UID (r) <= max_uid_for_loop
+ && REGNO_FIRST_LUID (r) >= copy_start_luid
+ && REGNO_LAST_UID (r) > 0 && REGNO_LAST_UID (r) <= max_uid_for_loop
+ && REGNO_LAST_LUID (r) <= copy_end_luid)
+ {
+ /* However, we must also check for loop-carried dependencies.
+ If the value the pseudo has at the end of iteration X is
+ used by iteration X+1, then we can not use a different pseudo
+ for each unrolled copy of the loop. */
+ /* A pseudo is safe if regno_first_uid is a set, and this
+ set dominates all instructions from regno_first_uid to
+ regno_last_uid. */
+ /* ??? This check is simplistic. We would get better code if
+ this check was more sophisticated. */
+ if (set_dominates_use (r, REGNO_FIRST_UID (r), REGNO_LAST_UID (r),
+ copy_start, copy_end))
+ local_regno[r] = 1;
+
+ if (loop_dump_stream)
+ {
+ if (local_regno[r])
+ fprintf (loop_dump_stream, "Marked reg %d as local\n", r);
+ else
+ fprintf (loop_dump_stream, "Did not mark reg %d as local\n",
+ r);
+ }
+ }
+ }
/* If this loop requires exit tests when unrolled, check to see if we
can precondition the loop so as to make the exit tests unnecessary.
rtx initial_value, final_value, increment;
enum machine_mode mode;
- if (precondition_loop_p (loop_start, loop_info,
+ if (precondition_loop_p (loop,
&initial_value, &final_value, &increment,
&mode))
{
- register rtx diff ;
+ register rtx diff;
rtx *labels;
int abs_inc, neg_inc;
- map->reg_map = (rtx *) alloca (maxregnum * sizeof (rtx));
+ map->reg_map = (rtx *) xmalloc (maxregnum * sizeof (rtx));
- map->const_equiv_map = (rtx *) alloca (maxregnum * sizeof (rtx));
- map->const_age_map = (unsigned *) alloca (maxregnum
- * sizeof (unsigned));
- map->const_equiv_map_size = maxregnum;
- global_const_equiv_map = map->const_equiv_map;
- global_const_equiv_map_size = maxregnum;
+ VARRAY_CONST_EQUIV_INIT (map->const_equiv_varray, maxregnum,
+ "unroll_loop_precondition");
+ global_const_equiv_varray = map->const_equiv_varray;
init_reg_map (map, maxregnum);
abs_inc = INTVAL (increment);
if (abs_inc < 0)
{
- abs_inc = - abs_inc;
+ abs_inc = -abs_inc;
neg_inc = 1;
}
/* Calculate the difference between the final and initial values.
Final value may be a (plus (reg x) (const_int 1)) rtx.
Let the following cse pass simplify this if initial value is
- a constant.
+ a constant.
We must copy the final and initial values here to avoid
improperly shared rtl. */
/* Now emit a sequence of branches to jump to the proper precond
loop entry point. */
- labels = (rtx *) alloca (sizeof (rtx) * unroll_number);
+ labels = (rtx *) xmalloc (sizeof (rtx) * unroll_number);
for (i = 0; i < unroll_number; i++)
labels[i] = gen_label_rtx ();
if (loop_info->comparison_code != NE)
{
- emit_cmp_insn (initial_value, final_value, neg_inc ? LE : GE,
- NULL_RTX, mode, 0, 0);
- if (neg_inc)
- emit_jump_insn (gen_ble (labels[1]));
- else
- emit_jump_insn (gen_bge (labels[1]));
+ emit_cmp_and_jump_insns (initial_value, final_value,
+ neg_inc ? LE : GE,
+ NULL_RTX, mode, 0, 0, labels[1]);
+ predict_insn_def (get_last_insn (), PRED_LOOP_CONDITION, NOT_TAKEN);
JUMP_LABEL (get_last_insn ()) = labels[1];
LABEL_NUSES (labels[1])++;
}
cmp_code = LE;
}
- emit_cmp_insn (diff, GEN_INT (abs_inc * cmp_const),
- cmp_code, NULL_RTX, mode, 0, 0);
-
- if (i == 0)
- emit_jump_insn (gen_beq (labels[i]));
- else if (neg_inc)
- emit_jump_insn (gen_bge (labels[i]));
- else
- emit_jump_insn (gen_ble (labels[i]));
+ emit_cmp_and_jump_insns (diff, GEN_INT (abs_inc * cmp_const),
+ cmp_code, NULL_RTX, mode, 0, 0,
+ labels[i]);
JUMP_LABEL (get_last_insn ()) = labels[i];
LABEL_NUSES (labels[i])++;
+ predict_insn (get_last_insn (), PRED_LOOP_PRECONDITIONING,
+ REG_BR_PROB_BASE / (unroll_number - i));
}
/* If the increment is greater than one, then we need another branch,
For the negative increment case, the branch here could easily
be merged with the `0' case branch above. For the positive
increment case, it is not clear how this can be simplified. */
-
+
if (abs_inc != 1)
{
int cmp_const;
cmp_code = GE;
}
- emit_cmp_insn (diff, GEN_INT (cmp_const), cmp_code, NULL_RTX,
- mode, 0, 0);
-
- if (neg_inc)
- emit_jump_insn (gen_ble (labels[0]));
- else
- emit_jump_insn (gen_bge (labels[0]));
+ emit_cmp_and_jump_insns (diff, GEN_INT (cmp_const), cmp_code,
+ NULL_RTX, mode, 0, 0, labels[0]);
JUMP_LABEL (get_last_insn ()) = labels[0];
LABEL_NUSES (labels[0])++;
}
sequence = gen_sequence ();
end_sequence ();
- emit_insn_before (sequence, loop_start);
-
+ loop_insn_hoist (loop, sequence);
+
/* Only the last copy of the loop body here needs the exit
test, so set copy_end to exclude the compare/branch here,
and then reset it inside the loop when get to the last
copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
else if (GET_CODE (last_loop_insn) == JUMP_INSN)
{
-#ifdef HAVE_cc0
- /* The immediately preceding insn is a compare which we do not
- want to copy. */
- copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
-#else
- /* The immediately preceding insn may not be a compare, so we
- must copy it. */
copy_end = PREV_INSN (last_loop_insn);
+#ifdef HAVE_cc0
+ /* The immediately preceding insn may be a compare which
+ we do not want to copy. */
+ if (sets_cc0_p (PREV_INSN (copy_end)))
+ copy_end = PREV_INSN (copy_end);
#endif
}
else
emit_label_after (labels[unroll_number - i],
PREV_INSN (loop_start));
- bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
- bzero ((char *) map->const_equiv_map, maxregnum * sizeof (rtx));
- bzero ((char *) map->const_age_map,
- maxregnum * sizeof (unsigned));
+ memset ((char *) map->insn_map, 0, max_insnno * sizeof (rtx));
+ memset ((char *) &VARRAY_CONST_EQUIV (map->const_equiv_varray, 0),
+ 0, (VARRAY_SIZE (map->const_equiv_varray)
+ * sizeof (struct const_equiv_data)));
map->const_age = 0;
for (j = 0; j < max_labelno; j++)
if (local_label[j])
set_label_in_map (map, j, gen_label_rtx ());
- for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
- if (local_regno[j])
+ for (r = FIRST_PSEUDO_REGISTER; r < max_local_regnum; r++)
+ if (local_regno[r])
{
- map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));
- record_base_value (REGNO (map->reg_map[j]),
- regno_reg_rtx[j], 0);
+ map->reg_map[r]
+ = gen_reg_rtx (GET_MODE (regno_reg_rtx[r]));
+ record_base_value (REGNO (map->reg_map[r]),
+ regno_reg_rtx[r], 0);
}
/* The last copy needs the compare/branch insns at the end,
so reset copy_end here if the loop ends with a conditional
/* None of the copies are the `last_iteration', so just
pass zero for that parameter. */
- copy_loop_body (copy_start, copy_end, map, exit_label, 0,
+ copy_loop_body (loop, copy_start, copy_end, map, exit_label, 0,
unroll_type, start_label, loop_end,
loop_start, copy_end);
}
}
else
{
-#ifdef HAVE_cc0
- /* The immediately preceding insn is a compare which we do not
- want to copy. */
- insert_before = PREV_INSN (last_loop_insn);
- copy_end = PREV_INSN (insert_before);
-#else
- /* The immediately preceding insn may not be a compare, so we
- must copy it. */
insert_before = last_loop_insn;
- copy_end = PREV_INSN (last_loop_insn);
+#ifdef HAVE_cc0
+ /* The instruction immediately before the JUMP_INSN may
+ be a compare instruction which we do not want to copy
+ or delete. */
+ if (sets_cc0_p (PREV_INSN (insert_before)))
+ insert_before = PREV_INSN (insert_before);
#endif
+ copy_end = PREV_INSN (insert_before);
}
/* Set unroll type to MODULO now. */
unroll_type = UNROLL_MODULO;
loop_preconditioned = 1;
+
+ /* Clean up. */
+ free (labels);
}
}
if (unroll_type == UNROLL_NAIVE && ! flag_unroll_all_loops)
{
if (loop_dump_stream)
- fprintf (loop_dump_stream, "Unrolling failure: Naive unrolling not being done.\n");
- return;
+ fprintf (loop_dump_stream,
+ "Unrolling failure: Naive unrolling not being done.\n");
+ goto egress;
}
/* At this point, we are guaranteed to unroll the loop. */
/* Keep track of the unroll factor for the loop. */
- if (unroll_type == UNROLL_COMPLETELY)
- loop_info->unroll_number = -1;
- else
- loop_info->unroll_number = unroll_number;
-
+ loop_info->unroll_number = unroll_number;
/* For each biv and giv, determine whether it can be safely split into
a different variable for each unrolled copy of the loop body.
if (splitting_not_safe)
temp = 0;
else
- temp = find_splittable_regs (unroll_type, loop_start, loop_end,
- end_insert_before, unroll_number,
- loop_info->n_iterations);
+ temp = find_splittable_regs (loop, unroll_type, unroll_number);
/* find_splittable_regs may have created some new registers, so must
reallocate the reg_map with the new larger size, and must realloc
the constant maps also. */
maxregnum = max_reg_num ();
- map->reg_map = (rtx *) alloca (maxregnum * sizeof (rtx));
+ map->reg_map = (rtx *) xmalloc (maxregnum * sizeof (rtx));
init_reg_map (map, maxregnum);
- /* Space is needed in some of the map for new registers, so new_maxregnum
- is an (over)estimate of how many registers will exist at the end. */
- new_maxregnum = maxregnum + (temp * unroll_number * 2);
-
- /* Must realloc space for the constant maps, because the number of registers
- may have changed. */
-
- map->const_equiv_map = (rtx *) alloca (new_maxregnum * sizeof (rtx));
- map->const_age_map = (unsigned *) alloca (new_maxregnum * sizeof (unsigned));
-
- map->const_equiv_map_size = new_maxregnum;
- global_const_equiv_map = map->const_equiv_map;
- global_const_equiv_map_size = new_maxregnum;
+ if (map->const_equiv_varray == 0)
+ VARRAY_CONST_EQUIV_INIT (map->const_equiv_varray,
+ maxregnum + temp * unroll_number * 2,
+ "unroll_loop");
+ global_const_equiv_varray = map->const_equiv_varray;
/* Search the list of bivs and givs to find ones which need to be remapped
when split, and set their reg_map entry appropriately. */
- for (bl = loop_iv_list; bl; bl = bl->next)
+ for (bl = ivs->list; bl; bl = bl->next)
{
if (REGNO (bl->biv->src_reg) != bl->regno)
map->reg_map[bl->regno] = bl->biv->src_reg;
}
/* Use our current register alignment and pointer flags. */
- map->regno_pointer_flag = regno_pointer_flag;
- map->regno_pointer_align = regno_pointer_align;
+ map->regno_pointer_align = cfun->emit->regno_pointer_align;
+ map->x_regno_reg_rtx = cfun->emit->x_regno_reg_rtx;
/* If the loop is being partially unrolled, and the iteration variables
are being split, and are being renamed for the split, then must fix up
{
insn = NEXT_INSN (copy_end);
if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
- PATTERN (insn) = remap_split_bivs (PATTERN (insn));
+ PATTERN (insn) = remap_split_bivs (loop, PATTERN (insn));
}
- /* For unroll_number - 1 times, make a copy of each instruction
+ /* For unroll_number times, make a copy of each instruction
between copy_start and copy_end, and insert these new instructions
before the end of the loop. */
for (i = 0; i < unroll_number; i++)
{
- bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
- bzero ((char *) map->const_equiv_map, new_maxregnum * sizeof (rtx));
- bzero ((char *) map->const_age_map, new_maxregnum * sizeof (unsigned));
+ memset ((char *) map->insn_map, 0, max_insnno * sizeof (rtx));
+ memset ((char *) &VARRAY_CONST_EQUIV (map->const_equiv_varray, 0), 0,
+ VARRAY_SIZE (map->const_equiv_varray) * sizeof (struct const_equiv_data));
map->const_age = 0;
for (j = 0; j < max_labelno; j++)
if (local_label[j])
set_label_in_map (map, j, gen_label_rtx ());
- for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
- if (local_regno[j])
+ for (r = FIRST_PSEUDO_REGISTER; r < max_local_regnum; r++)
+ if (local_regno[r])
{
- map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));
- record_base_value (REGNO (map->reg_map[j]),
- regno_reg_rtx[j], 0);
+ map->reg_map[r] = gen_reg_rtx (GET_MODE (regno_reg_rtx[r]));
+ record_base_value (REGNO (map->reg_map[r]),
+ regno_reg_rtx[r], 0);
}
/* If loop starts with a branch to the test, then fix it so that
{
insn = PREV_INSN (copy_start);
pattern = PATTERN (insn);
-
+
tem = get_label_from_map (map,
CODE_LABEL_NUMBER
(XEXP (SET_SRC (pattern), 0)));
LABEL_NUSES (tem)++;
}
- copy_loop_body (copy_start, copy_end, map, exit_label,
+ copy_loop_body (loop, copy_start, copy_end, map, exit_label,
i == unroll_number - 1, unroll_type, start_label,
loop_end, insert_before, insert_before);
}
else
safety_label = emit_label_after (gen_label_rtx (), copy_end);
- /* Delete all of the original loop instructions. Don't delete the
+ /* Delete all of the original loop instructions. Don't delete the
LOOP_BEG note, or the first code label in the loop. */
insn = NEXT_INSN (copy_start);
while (insn != safety_label)
{
- if (insn != start_label)
+ /* ??? Don't delete named code labels. They will be deleted when the
+ jump that references them is deleted. Otherwise, we end up deleting
+ them twice, which causes them to completely disappear instead of turn
+ into NOTE_INSN_DELETED_LABEL notes. This in turn causes aborts in
+ dwarfout.c/dwarf2out.c. We could perhaps fix the dwarf*out.c files
+ to handle deleted labels instead. Or perhaps fix DECL_RTL of the
+ associated LABEL_DECL to point to one of the new label instances. */
+ /* ??? Likewise, we can't delete a NOTE_INSN_DELETED_LABEL note. */
+ if (insn != start_label
+ && ! (GET_CODE (insn) == CODE_LABEL && LABEL_NAME (insn))
+ && ! (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED_LABEL))
insn = delete_insn (insn);
else
insn = NEXT_INSN (insn);
not taken. */
if (exit_label)
emit_label_after (exit_label, loop_end);
+
+ egress:
+ if (unroll_type == UNROLL_COMPLETELY)
+ {
+ /* Remove the loop notes since this is no longer a loop. */
+ if (loop->vtop)
+ delete_insn (loop->vtop);
+ if (loop->cont)
+ delete_insn (loop->cont);
+ if (loop_start)
+ delete_insn (loop_start);
+ if (loop_end)
+ delete_insn (loop_end);
+ }
+
+ if (map->const_equiv_varray)
+ VARRAY_FREE (map->const_equiv_varray);
+ if (map->label_map)
+ {
+ free (map->label_map);
+ free (local_label);
+ }
+ free (map->insn_map);
+ free (splittable_regs);
+ free (splittable_regs_updates);
+ free (addr_combined_regs);
+ free (local_regno);
+ if (map->reg_map)
+ free (map->reg_map);
+ free (map);
}
\f
/* Return true if the loop can be safely, and profitably, preconditioned
/* ??? If the loop is known to be executed very many times, or the machine
has a very cheap divide instruction, then preconditioning is a win even
when the increment is not a power of 2. Use RTX_COST to compute
- whether divide is cheap. */
+ whether divide is cheap.
+ ??? A divide by constant doesn't actually need a divide, look at
+ expand_divmod. The reduced cost of this optimized modulo is not
+ reflected in RTX_COST. */
int
-precondition_loop_p (loop_start, loop_info,
- initial_value, final_value, increment, mode)
- rtx loop_start;
- struct loop_info *loop_info;
+precondition_loop_p (loop, initial_value, final_value, increment, mode)
+ const struct loop *loop;
rtx *initial_value, *final_value, *increment;
enum machine_mode *mode;
{
+ rtx loop_start = loop->start;
+ struct loop_info *loop_info = LOOP_INFO (loop);
if (loop_info->n_iterations > 0)
{
return 1;
}
- if (loop_info->initial_value == 0)
+ if (loop_info->iteration_var == 0)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Preconditioning: Could not find iteration variable.\n");
+ return 0;
+ }
+ else if (loop_info->initial_value == 0)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
return 0;
}
else if ((exact_log2 (INTVAL (loop_info->increment)) < 0)
- && (exact_log2 (- INTVAL (loop_info->increment)) < 0))
+ && (exact_log2 (-INTVAL (loop_info->increment)) < 0))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
return 0;
}
- /* Must ensure that final_value is invariant, so call invariant_p to
- check. Before doing so, must check regno against max_reg_before_loop
- to make sure that the register is in the range covered by invariant_p.
- If it isn't, then it is most likely a biv/giv which by definition are
- not invariant. */
+ /* Must ensure that final_value is invariant, so call
+ loop_invariant_p to check. Before doing so, must check regno
+ against max_reg_before_loop to make sure that the register is in
+ the range covered by loop_invariant_p. If it isn't, then it is
+ most likely a biv/giv which by definition are not invariant. */
if ((GET_CODE (loop_info->final_value) == REG
&& REGNO (loop_info->final_value) >= max_reg_before_loop)
|| (GET_CODE (loop_info->final_value) == PLUS
&& REGNO (XEXP (loop_info->final_value, 0)) >= max_reg_before_loop)
- || ! invariant_p (loop_info->final_value))
+ || ! loop_invariant_p (loop, loop_info->final_value))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
/* Fail if loop_info->iteration_var is not live before loop_start,
since we need to test its value in the preconditioning code. */
- if (uid_luid[REGNO_FIRST_UID (REGNO (loop_info->iteration_var))]
+ if (REGNO_FIRST_LUID (REGNO (loop_info->iteration_var))
> INSN_LUID (loop_start))
{
if (loop_dump_stream)
return 0;
}
- /* ??? Note that if iteration_info is modifed to allow GIV iterators
- such as "while (i-- > 0)", the initial value will be one too small.
- In this case, loop_iteration_var could be used to determine
- the correct initial value, provided the loop has not been reversed.
-
+ /* Note that loop_iterations biases the initial value for GIV iterators
+ such as "while (i-- > 0)" so that we can calculate the number of
+ iterations just like for BIV iterators.
+
Also note that the absolute values of initial_value and
final_value are unimportant as only their difference is used for
calculating the number of loop iterations. */
< GET_MODE_SIZE (GET_MODE (*initial_value))))
*mode = GET_MODE (*initial_value);
- /* Success! */
+ /* Success! */
if (loop_dump_stream)
fprintf (loop_dump_stream, "Preconditioning: Successful.\n");
return 1;
}
-
/* All pseudo-registers must be mapped to themselves. Two hard registers
must be mapped, VIRTUAL_STACK_VARS_REGNUM and VIRTUAL_INCOMING_ARGS_
REGNUM, to avoid function-inlining specific conversions of these
static rtx
calculate_giv_inc (pattern, src_insn, regno)
rtx pattern, src_insn;
- int regno;
+ unsigned int regno;
{
rtx increment;
rtx increment_total = 0;
pattern = PATTERN (src_insn);
if (GET_CODE (SET_SRC (pattern)) != PLUS)
abort ();
-
+
/* The last insn emitted is not needed, so delete it to avoid confusing
the second cse pass. This insn sets the giv unnecessarily. */
delete_insn (get_last_insn ());
/* Some ports store large constants in memory and add a REG_EQUAL
note to the store insn. */
else if (GET_CODE (increment) == MEM)
- {
- rtx note = find_reg_note (src_insn, REG_EQUAL, 0);
- if (note)
- increment = XEXP (note, 0);
- }
+ {
+ rtx note = find_reg_note (src_insn, REG_EQUAL, 0);
+ if (note)
+ increment = XEXP (note, 0);
+ }
else if (GET_CODE (increment) == IOR
|| GET_CODE (increment) == ASHIFT
if (GET_CODE (increment) != CONST_INT)
abort ();
-
+
/* The insn loading the constant into a register is no longer needed,
so delete it. */
delete_insn (get_last_insn ());
return 0;
copy = rtx_alloc (GET_CODE (notes));
- PUT_MODE (copy, GET_MODE (notes));
+ PUT_REG_NOTE_KIND (copy, REG_NOTE_KIND (notes));
if (GET_CODE (notes) == EXPR_LIST)
- XEXP (copy, 0) = copy_rtx_and_substitute (XEXP (notes, 0), map);
+ XEXP (copy, 0) = copy_rtx_and_substitute (XEXP (notes, 0), map, 0);
else if (GET_CODE (notes) == INSN_LIST)
/* Don't substitute for these yet. */
- XEXP (copy, 0) = XEXP (notes, 0);
+ XEXP (copy, 0) = copy_rtx (XEXP (notes, 0));
else
abort ();
/* Fixup insn references in copied REG_NOTES. */
static void
-final_reg_note_copy (notes, map)
- rtx notes;
+final_reg_note_copy (notesp, map)
+ rtx *notesp;
struct inline_remap *map;
{
- rtx note;
+ while (*notesp)
+ {
+ rtx note = *notesp;
+
+ if (GET_CODE (note) == INSN_LIST)
+ {
+ /* Sometimes, we have a REG_WAS_0 note that points to a
+ deleted instruction. In that case, we can just delete the
+ note. */
+ if (REG_NOTE_KIND (note) == REG_WAS_0)
+ {
+ *notesp = XEXP (note, 1);
+ continue;
+ }
+ else
+ {
+ rtx insn = map->insn_map[INSN_UID (XEXP (note, 0))];
+
+ /* If we failed to remap the note, something is awry. */
+ if (!insn)
+ abort ();
- for (note = notes; note; note = XEXP (note, 1))
- if (GET_CODE (note) == INSN_LIST)
- XEXP (note, 0) = map->insn_map[INSN_UID (XEXP (note, 0))];
+ XEXP (note, 0) = insn;
+ }
+ }
+
+ notesp = &XEXP (note, 1);
+ }
}
/* Copy each instruction in the loop, substituting from map as appropriate.
This is very similar to a loop in expand_inline_function. */
-
+
static void
-copy_loop_body (copy_start, copy_end, map, exit_label, last_iteration,
+copy_loop_body (loop, copy_start, copy_end, map, exit_label, last_iteration,
unroll_type, start_label, loop_end, insert_before,
copy_notes_from)
+ struct loop *loop;
rtx copy_start, copy_end;
struct inline_remap *map;
rtx exit_label;
enum unroll_types unroll_type;
rtx start_label, loop_end, insert_before, copy_notes_from;
{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
rtx insn, pattern;
- rtx set, tem, copy;
+ rtx set, tem, copy = NULL_RTX;
int dest_reg_was_split, i;
#ifdef HAVE_cc0
rtx cc0_insn = 0;
if (! last_iteration)
{
final_label = gen_label_rtx ();
- set_label_in_map (map, CODE_LABEL_NUMBER (start_label),
- final_label);
+ set_label_in_map (map, CODE_LABEL_NUMBER (start_label), final_label);
}
else
set_label_in_map (map, CODE_LABEL_NUMBER (start_label), start_label);
start_sequence ();
-
+
+ /* Emit a NOTE_INSN_DELETED to force at least two insns onto the sequence.
+ Else gen_sequence could return a raw pattern for a jump which we pass
+ off to emit_insn_before (instead of emit_jump_insn_before) which causes
+ a variety of losing behaviors later. */
+ emit_note (0, NOTE_INSN_DELETED);
+
insn = copy_start;
do
{
insn = NEXT_INSN (insn);
-
+
map->orig_asm_operands_vector = 0;
-
+
switch (GET_CODE (insn))
{
case INSN:
pattern = PATTERN (insn);
copy = 0;
giv_inc = 0;
-
+
/* Check to see if this is a giv that has been combined with
- some split address givs. (Combined in the sense that
+ some split address givs. (Combined in the sense that
`combine_givs' in loop.c has put two givs in the same register.)
In this case, we must search all givs based on the same biv to
find the address givs. Then split the address givs.
Do this before splitting the giv, since that may map the
SET_DEST to a new register. */
-
+
if ((set = single_set (insn))
&& GET_CODE (SET_DEST (set)) == REG
&& addr_combined_regs[REGNO (SET_DEST (set))])
{
struct iv_class *bl;
struct induction *v, *tv;
- int regno = REGNO (SET_DEST (set));
-
+ unsigned int regno = REGNO (SET_DEST (set));
+
v = addr_combined_regs[REGNO (SET_DEST (set))];
- bl = reg_biv_class[REGNO (v->src_reg)];
-
+ bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
+
/* Although the giv_inc amount is not needed here, we must call
calculate_giv_inc here since it might try to delete the
last insn emitted. If we wait until later to call it,
if (tv->mult_val != v->mult_val)
this_giv_inc = (this_giv_inc / INTVAL (v->mult_val)
* INTVAL (tv->mult_val));
-
+
tv->dest_reg = plus_constant (tv->dest_reg, this_giv_inc);
*tv->location = tv->dest_reg;
-
+
if (last_iteration && unroll_type != UNROLL_COMPLETELY)
{
/* Must emit an insn to increment the split address
giv. Add in the const_adjust field in case there
was a constant eliminated from the address. */
rtx value, dest_reg;
-
+
/* tv->dest_reg will be either a bare register,
or else a register plus a constant. */
if (GET_CODE (tv->dest_reg) == REG)
dest_reg = tv->dest_reg;
else
dest_reg = XEXP (tv->dest_reg, 0);
-
+
/* Check for shared address givs, and avoid
incrementing the shared pseudo reg more than
once. */
value = plus_constant (tv->dest_reg,
tv->const_adjust);
- /* The constant could be too large for an add
- immediate, so can't directly emit an insn
- here. */
- emit_unrolled_add (dest_reg, XEXP (value, 0),
- XEXP (value, 1));
+ if (GET_CODE (value) == PLUS)
+ {
+ /* The constant could be too large for an add
+ immediate, so can't directly emit an insn
+ here. */
+ emit_unrolled_add (dest_reg, XEXP (value, 0),
+ XEXP (value, 1));
+ }
}
-
+
/* Reset the giv to be just the register again, in case
it is used after the set we have just emitted.
We must subtract the const_adjust factor added in
above. */
tv->dest_reg = plus_constant (dest_reg,
- - tv->const_adjust);
+ -tv->const_adjust);
*tv->location = tv->dest_reg;
}
}
}
-
+
/* If this is a setting of a splittable variable, then determine
how to split the variable, create a new set based on this split,
and set up the reg_map so that later uses of the variable will
use the new split variable. */
-
+
dest_reg_was_split = 0;
-
+
if ((set = single_set (insn))
&& GET_CODE (SET_DEST (set)) == REG
&& splittable_regs[REGNO (SET_DEST (set))])
{
- int regno = REGNO (SET_DEST (set));
-
+ unsigned int regno = REGNO (SET_DEST (set));
+ unsigned int src_regno;
+
dest_reg_was_split = 1;
-
+
+ giv_dest_reg = SET_DEST (set);
+ giv_src_reg = giv_dest_reg;
/* Compute the increment value for the giv, if it wasn't
already computed above. */
-
if (giv_inc == 0)
giv_inc = calculate_giv_inc (set, insn, regno);
- giv_dest_reg = SET_DEST (set);
- giv_src_reg = SET_DEST (set);
+
+ src_regno = REGNO (giv_src_reg);
if (unroll_type == UNROLL_COMPLETELY)
{
/* Completely unrolling the loop. Set the induction
variable to a known constant value. */
-
+
/* The value in splittable_regs may be an invariant
value, so we must use plus_constant here. */
splittable_regs[regno]
- = plus_constant (splittable_regs[regno], INTVAL (giv_inc));
+ = plus_constant (splittable_regs[src_regno],
+ INTVAL (giv_inc));
if (GET_CODE (splittable_regs[regno]) == PLUS)
{
be a constant plus the original register. Except
on the last iteration, when the result has to
go back into the original iteration var register. */
-
+
/* Handle bivs which must be mapped to a new register
when split. This happens for bivs which need their
final value set before loop entry. The new register
for the biv was stored in the biv's first struct
induction entry by find_splittable_regs. */
- if (regno < max_reg_before_loop
- && reg_iv_type[regno] == BASIC_INDUCT)
+ if (regno < ivs->n_regs
+ && REG_IV_TYPE (ivs, regno) == BASIC_INDUCT)
{
- giv_src_reg = reg_biv_class[regno]->biv->src_reg;
+ giv_src_reg = REG_IV_CLASS (ivs, regno)->biv->src_reg;
giv_dest_reg = giv_src_reg;
}
-
+
#if 0
/* If non-reduced/final-value givs were split, then
this would have to remap those givs also. See
find_splittable_regs. */
#endif
-
+
splittable_regs[regno]
- = GEN_INT (INTVAL (giv_inc)
- + INTVAL (splittable_regs[regno]));
+ = simplify_gen_binary (PLUS, GET_MODE (giv_src_reg),
+ giv_inc,
+ splittable_regs[src_regno]);
giv_inc = splittable_regs[regno];
-
+
/* Now split the induction variable by changing the dest
of this insn to a new register, and setting its
reg_map entry to point to this new register.
}
else
{
- pattern = copy_rtx_and_substitute (pattern, map);
+ pattern = copy_rtx_and_substitute (pattern, map, 0);
copy = emit_insn (pattern);
}
REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
-
+
#ifdef HAVE_cc0
/* If this insn is setting CC0, it may need to look at
the insn that uses CC0 to see what type of insn it is.
settings which would invalidate this. */
if (dest_reg_was_split)
{
- int regno = REGNO (SET_DEST (pattern));
+ int regno = REGNO (SET_DEST (set));
- if (regno < map->const_equiv_map_size
- && map->const_age_map[regno] == map->const_age)
- map->const_age_map[regno] = -1;
+ if ((size_t) regno < VARRAY_SIZE (map->const_equiv_varray)
+ && (VARRAY_CONST_EQUIV (map->const_equiv_varray, regno).age
+ == map->const_age))
+ VARRAY_CONST_EQUIV (map->const_equiv_varray, regno).age = -1;
}
break;
-
+
case JUMP_INSN:
- pattern = copy_rtx_and_substitute (PATTERN (insn), map);
+ pattern = copy_rtx_and_substitute (PATTERN (insn), map, 0);
copy = emit_jump_insn (pattern);
REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
if (JUMP_LABEL (insn) == start_label && insn == copy_end
&& ! last_iteration)
{
+ /* Update JUMP_LABEL make invert_jump work correctly. */
+ JUMP_LABEL (copy) = get_label_from_map (map,
+ CODE_LABEL_NUMBER
+ (JUMP_LABEL (insn)));
+ LABEL_NUSES (JUMP_LABEL (copy))++;
+
/* This is a branch to the beginning of the loop; this is the
last insn being copied; and this is not the last iteration.
In this case, we want to change the original fall through
case to be a branch past the end of the loop, and the
original jump label case to fall_through. */
- if (invert_exp (pattern, copy))
- {
- if (! redirect_exp (&pattern,
- get_label_from_map (map,
- CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))),
- exit_label, copy))
- abort ();
- }
- else
+ if (!invert_jump (copy, exit_label, 0))
{
rtx jmp;
rtx lab = gen_label_rtx ();
jmp = emit_barrier_after (jmp);
emit_label_after (lab, jmp);
LABEL_NUSES (lab) = 0;
- if (! redirect_exp (&pattern,
- get_label_from_map (map,
- CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))),
- lab, copy))
+ if (!redirect_jump (copy, lab, 0))
abort ();
}
}
-
+
#ifdef HAVE_cc0
if (cc0_insn)
try_constants (cc0_insn, map);
for a switch statement. This label must have been mapped,
so just use the label_map to get the new jump label. */
JUMP_LABEL (copy)
- = get_label_from_map (map,
- CODE_LABEL_NUMBER (JUMP_LABEL (insn)));
+ = get_label_from_map (map,
+ CODE_LABEL_NUMBER (JUMP_LABEL (insn)));
}
-
+
/* If this is a non-local jump, then must increase the label
use count so that the label will not be deleted when the
original jump is deleted. */
/* If this used to be a conditional jump insn but whose branch
direction is now known, we must do something special. */
- if (condjump_p (insn) && !simplejump_p (insn) && map->last_pc_value)
+ if (any_condjump_p (insn) && onlyjump_p (insn) && map->last_pc_value)
{
#ifdef HAVE_cc0
- /* The previous insn set cc0 for us. So delete it. */
- delete_insn (PREV_INSN (copy));
+ /* If the previous insn set cc0 for us, delete it. */
+ if (sets_cc0_p (PREV_INSN (copy)))
+ delete_insn (PREV_INSN (copy));
#endif
/* If this is now a no-op, delete it. */
emit_barrier ();
}
break;
-
+
case CALL_INSN:
- pattern = copy_rtx_and_substitute (PATTERN (insn), map);
+ pattern = copy_rtx_and_substitute (PATTERN (insn), map, 0);
copy = emit_call_insn (pattern);
REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
/* Because the USAGE information potentially contains objects other
than hard registers, we need to copy it. */
CALL_INSN_FUNCTION_USAGE (copy)
- = copy_rtx_and_substitute (CALL_INSN_FUNCTION_USAGE (insn), map);
+ = copy_rtx_and_substitute (CALL_INSN_FUNCTION_USAGE (insn),
+ map, 0);
#ifdef HAVE_cc0
if (cc0_insn)
/* Be lazy and assume CALL_INSNs clobber all hard registers. */
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- map->const_equiv_map[i] = 0;
+ VARRAY_CONST_EQUIV (map->const_equiv_varray, i).rtx = 0;
break;
-
+
case CODE_LABEL:
/* If this is the loop start label, then we don't need to emit a
copy of this label since no one will use it. */
map->const_age++;
}
break;
-
+
case BARRIER:
copy = emit_barrier ();
break;
-
+
case NOTE:
- /* VTOP notes are valid only before the loop exit test. If placed
- anywhere else, loop may generate bad code. */
-
+ /* VTOP and CONT notes are valid only before the loop exit test.
+ If placed anywhere else, loop may generate bad code. */
+ /* BASIC_BLOCK notes exist to stabilize basic block structures with
+ the associated rtl. We do not want to share the structure in
+ this new block. */
+
if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED
- && (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_VTOP
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED_LABEL
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
+ && ((NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_VTOP
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_CONT)
|| (last_iteration && unroll_type != UNROLL_COMPLETELY)))
copy = emit_note (NOTE_SOURCE_FILE (insn),
NOTE_LINE_NUMBER (insn));
else
copy = 0;
break;
-
+
default:
abort ();
- break;
}
-
+
map->insn_map[INSN_UID (insn)] = copy;
}
while (insn != copy_end);
-
+
/* Now finish coping the REG_NOTES. */
insn = copy_start;
do
if ((GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
|| GET_CODE (insn) == CALL_INSN)
&& map->insn_map[INSN_UID (insn)])
- final_reg_note_copy (REG_NOTES (map->insn_map[INSN_UID (insn)]), map);
+ final_reg_note_copy (®_NOTES (map->insn_map[INSN_UID (insn)]), map);
}
while (insn != copy_end);
{
for (insn = copy_notes_from; insn != loop_end; insn = NEXT_INSN (insn))
{
+ /* VTOP notes are valid only before the loop exit test.
+ If placed anywhere else, loop may generate bad code.
+ There is no need to test for NOTE_INSN_LOOP_CONT notes
+ here, since COPY_NOTES_FROM will be at most one or two (for cc0)
+ instructions before the last insn in the loop, and if the
+ end test is that short, there will be a VTOP note between
+ the CONT note and the test. */
if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED)
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_VTOP)
emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
}
}
tem = gen_sequence ();
end_sequence ();
- emit_insn_before (tem, insert_before);
+ loop_insn_emit_before (loop, 0, insert_before, tem);
}
\f
/* Emit an insn, using the expand_binop to ensure that a valid insn is
emit_move_insn (dest_reg, result);
}
\f
-/* Searches the insns between INSN and LOOP_END. Returns 1 if there
+/* Searches the insns between INSN and LOOP->END. Returns 1 if there
is a backward branch in that range that branches to somewhere between
- LOOP_START and INSN. Returns 0 otherwise. */
+ LOOP->START and INSN. Returns 0 otherwise. */
/* ??? This is quadratic algorithm. Could be rewritten to be linear.
In practice, this is not a problem, because this function is seldom called,
and uses a negligible amount of CPU time on average. */
int
-back_branch_in_range_p (insn, loop_start, loop_end)
+back_branch_in_range_p (loop, insn)
+ const struct loop *loop;
rtx insn;
- rtx loop_start, loop_end;
{
rtx p, q, target_insn;
- rtx orig_loop_end = loop_end;
+ rtx loop_start = loop->start;
+ rtx loop_end = loop->end;
+ rtx orig_loop_end = loop->end;
/* Stop before we get to the backward branch at the end of the loop. */
loop_end = prev_nonnote_insn (loop_end);
if (GET_CODE (p) == JUMP_INSN)
{
target_insn = JUMP_LABEL (p);
-
+
/* Search from loop_start to insn, to see if one of them is
the target_insn. We can't use INSN_LUID comparisons here,
since insn may not have an LUID entry. */
Returns the increment value as an rtx, simplified as much as possible,
if it can be calculated. Otherwise, returns 0. */
-rtx
-biv_total_increment (bl, loop_start, loop_end)
- struct iv_class *bl;
- rtx loop_start, loop_end;
+rtx
+biv_total_increment (bl)
+ const struct iv_class *bl;
{
struct induction *v;
rtx result;
for (v = bl->biv; v; v = v->next_iv)
{
if (v->always_computable && v->mult_val == const1_rtx
- && ! back_branch_in_range_p (v->insn, loop_start, loop_end))
+ && ! v->maybe_multiple)
result = fold_rtx_mult_add (result, const1_rtx, v->add_val, v->mode);
else
return 0;
return result;
}
-/* Determine the initial value of the iteration variable, and the amount
- that it is incremented each loop. Use the tables constructed by
- the strength reduction pass to calculate these values.
-
- Initial_value and/or increment are set to zero if their values could not
- be calculated. */
-
-static void
-iteration_info (iteration_var, initial_value, increment, loop_start, loop_end)
- rtx iteration_var, *initial_value, *increment;
- rtx loop_start, loop_end;
-{
- struct iv_class *bl;
-#if 0
- struct induction *v;
-#endif
-
- /* Clear the result values, in case no answer can be found. */
- *initial_value = 0;
- *increment = 0;
-
- /* The iteration variable can be either a giv or a biv. Check to see
- which it is, and compute the variable's initial value, and increment
- value if possible. */
-
- /* If this is a new register, can't handle it since we don't have any
- reg_iv_type entry for it. */
- if (REGNO (iteration_var) >= max_reg_before_loop)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: No reg_iv_type entry for iteration var.\n");
- return;
- }
-
- /* Reject iteration variables larger than the host wide int size, since they
- could result in a number of iterations greater than the range of our
- `unsigned HOST_WIDE_INT' variable loop_info->n_iterations. */
- else if ((GET_MODE_BITSIZE (GET_MODE (iteration_var))
- > HOST_BITS_PER_WIDE_INT))
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Iteration var rejected because mode too large.\n");
- return;
- }
- else if (GET_MODE_CLASS (GET_MODE (iteration_var)) != MODE_INT)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Iteration var not an integer.\n");
- return;
- }
- else if (reg_iv_type[REGNO (iteration_var)] == BASIC_INDUCT)
- {
- /* Grab initial value, only useful if it is a constant. */
- bl = reg_biv_class[REGNO (iteration_var)];
- *initial_value = bl->initial_value;
-
- *increment = biv_total_increment (bl, loop_start, loop_end);
- }
- else if (reg_iv_type[REGNO (iteration_var)] == GENERAL_INDUCT)
- {
-#if 1
- /* ??? The code below does not work because the incorrect number of
- iterations is calculated when the biv is incremented after the giv
- is set (which is the usual case). This can probably be accounted
- for by biasing the initial_value by subtracting the amount of the
- increment that occurs between the giv set and the giv test. However,
- a giv as an iterator is very rare, so it does not seem worthwhile
- to handle this. */
- /* ??? An example failure is: i = 6; do {;} while (i++ < 9). */
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Giv iterators are not handled.\n");
- return;
-#else
- /* Initial value is mult_val times the biv's initial value plus
- add_val. Only useful if it is a constant. */
- v = reg_iv_info[REGNO (iteration_var)];
- bl = reg_biv_class[REGNO (v->src_reg)];
- *initial_value = fold_rtx_mult_add (v->mult_val, bl->initial_value,
- v->add_val, v->mode);
-
- /* Increment value is mult_val times the increment value of the biv. */
-
- *increment = biv_total_increment (bl, loop_start, loop_end);
- if (*increment)
- *increment = fold_rtx_mult_add (v->mult_val, *increment, const0_rtx,
- v->mode);
-#endif
- }
- else
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Not basic or general induction var.\n");
- return;
- }
-}
-
-
/* For each biv and giv, determine whether it can be safely split into
a different variable for each unrolled copy of the loop body. If it
is safe to split, then indicate that by saving some useful info
times, since multiplies by small integers (1,2,3,4) are very cheap. */
static int
-find_splittable_regs (unroll_type, loop_start, loop_end, end_insert_before,
- unroll_number, n_iterations)
+find_splittable_regs (loop, unroll_type, unroll_number)
+ const struct loop *loop;
enum unroll_types unroll_type;
- rtx loop_start, loop_end;
- rtx end_insert_before;
int unroll_number;
- unsigned HOST_WIDE_INT n_iterations;
{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
struct induction *v;
rtx increment, tem;
int biv_splittable;
int result = 0;
- for (bl = loop_iv_list; bl; bl = bl->next)
+ for (bl = ivs->list; bl; bl = bl->next)
{
/* Biv_total_increment must return a constant value,
otherwise we can not calculate the split values. */
- increment = biv_total_increment (bl, loop_start, loop_end);
+ increment = biv_total_increment (bl);
if (! increment || GET_CODE (increment) != CONST_INT)
continue;
biv_splittable = 1;
biv_final_value = 0;
if (unroll_type != UNROLL_COMPLETELY
- && (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
- || unroll_type == UNROLL_NAIVE)
- && (uid_luid[REGNO_LAST_UID (bl->regno)] >= INSN_LUID (loop_end)
+ && (loop->exit_count || unroll_type == UNROLL_NAIVE)
+ && (REGNO_LAST_LUID (bl->regno) >= INSN_LUID (loop->end)
|| ! bl->init_insn
|| INSN_UID (bl->init_insn) >= max_uid_for_loop
- || (uid_luid[REGNO_FIRST_UID (bl->regno)]
+ || (REGNO_FIRST_LUID (bl->regno)
< INSN_LUID (bl->init_insn))
|| reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
- && ! (biv_final_value = final_biv_value (bl, loop_start, loop_end,
- n_iterations)))
+ && ! (biv_final_value = final_biv_value (loop, bl)))
biv_splittable = 0;
/* If any of the insns setting the BIV don't do so with a simple
if (GET_CODE (bl->initial_value) == REG
&& (REGNO (bl->initial_value) == bl->regno
|| REGNO (bl->initial_value) < FIRST_PSEUDO_REGISTER
- || ! invariant_p (bl->initial_value)))
+ || ! loop_invariant_p (loop, bl->initial_value)))
{
rtx tem = gen_reg_rtx (bl->biv->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
- emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
- loop_start);
+ loop_insn_hoist (loop,
+ gen_move_insn (tem, bl->biv->src_reg));
if (loop_dump_stream)
- fprintf (loop_dump_stream, "Biv %d initial value remapped to %d.\n",
+ fprintf (loop_dump_stream,
+ "Biv %d initial value remapped to %d.\n",
bl->regno, REGNO (tem));
splittable_regs[bl->regno] = tem;
depend on it may be splittable if the biv is live outside the
loop, and the givs aren't. */
- result += find_splittable_givs (bl, unroll_type, loop_start, loop_end,
- increment, unroll_number);
+ result += find_splittable_givs (loop, bl, unroll_type, increment,
+ unroll_number);
/* If final value is non-zero, then must emit an instruction which sets
the value of the biv to the proper value. This is done after
loop to ensure that it will always be executed no matter
how the loop exits. Otherwise emit the insn after the loop,
since this is slightly more efficient. */
- if (! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
- emit_insn_before (gen_move_insn (bl->biv->src_reg,
- biv_final_value),
- end_insert_before);
+ if (! loop->exit_count)
+ loop_insn_sink (loop, gen_move_insn (bl->biv->src_reg,
+ biv_final_value));
else
{
/* Create a new register to hold the value of the biv, and then
rtx tem = gen_reg_rtx (bl->biv->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
- emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
- loop_start);
- emit_insn_before (gen_move_insn (bl->biv->src_reg,
- biv_final_value),
- loop_start);
+ loop_insn_hoist (loop, gen_move_insn (tem, bl->biv->src_reg));
+ loop_insn_hoist (loop, gen_move_insn (bl->biv->src_reg,
+ biv_final_value));
if (loop_dump_stream)
fprintf (loop_dump_stream, "Biv %d mapped to %d for split.\n",
Return the number of instructions that set splittable registers. */
static int
-find_splittable_givs (bl, unroll_type, loop_start, loop_end, increment,
- unroll_number)
+find_splittable_givs (loop, bl, unroll_type, increment, unroll_number)
+ const struct loop *loop;
struct iv_class *bl;
enum unroll_types unroll_type;
- rtx loop_start, loop_end;
rtx increment;
int unroll_number;
{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
struct induction *v, *v2;
rtx final_value;
rtx tem;
won't reach here if they aren't. */
if (v->giv_type != DEST_ADDR
&& (! v->always_computable
- || back_branch_in_range_p (v->insn, loop_start, loop_end)))
+ || back_branch_in_range_p (loop, v->insn)))
continue;
-
+
/* The giv increment value must be a constant. */
giv_inc = fold_rtx_mult_add (v->mult_val, increment, const0_rtx,
v->mode);
the loop, or else the final value of the giv must be known.
Otherwise, it is not safe to split the giv since it may not have the
proper value on loop exit. */
-
+
/* The used outside loop test will fail for DEST_ADDR givs. They are
never used outside the loop anyways, so it is always safe to split a
DEST_ADDR giv. */
final_value = 0;
if (unroll_type != UNROLL_COMPLETELY
- && (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
- || unroll_type == UNROLL_NAIVE)
+ && (loop->exit_count || unroll_type == UNROLL_NAIVE)
&& v->giv_type != DEST_ADDR
/* The next part is true if the pseudo is used outside the loop.
We assume that this is true for any pseudo created after loop
|| (REGNO_FIRST_UID (REGNO (v->dest_reg))
!= INSN_UID (XEXP (tem, 0)))))
/* Line above always fails if INSN was moved by loop opt. */
- || (uid_luid[REGNO_LAST_UID (REGNO (v->dest_reg))]
- >= INSN_LUID (loop_end)))
+ || (REGNO_LAST_LUID (REGNO (v->dest_reg))
+ >= INSN_LUID (loop->end)))
&& ! (final_value = v->final_value))
continue;
to its final value before loop start to ensure that this insn
will always be executed, no matter how we exit. */
tem = gen_reg_rtx (v->mode);
- emit_insn_before (gen_move_insn (tem, v->dest_reg), loop_start);
- emit_insn_before (gen_move_insn (v->dest_reg, final_value),
- loop_start);
-
+ loop_insn_hoist (loop, gen_move_insn (tem, v->dest_reg));
+ loop_insn_hoist (loop, gen_move_insn (v->dest_reg, final_value));
+
if (loop_dump_stream)
fprintf (loop_dump_stream, "Giv %d mapped to %d for split.\n",
REGNO (v->dest_reg), REGNO (tem));
-
+
v->src_reg = tem;
}
#endif
rtx tem = gen_reg_rtx (bl->biv->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
- emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
- loop_start);
+ loop_insn_hoist (loop, gen_move_insn (tem, bl->biv->src_reg));
biv_initial_value = tem;
}
+ biv_initial_value = extend_value_for_giv (v, biv_initial_value);
value = fold_rtx_mult_add (v->mult_val, biv_initial_value,
v->add_val, v->mode);
}
{
rtx tem = gen_reg_rtx (v->mode);
record_base_value (REGNO (tem), v->add_val, 0);
- emit_iv_add_mult (bl->initial_value, v->mult_val,
- v->add_val, tem, loop_start);
+ loop_iv_add_mult_hoist (loop, bl->initial_value, v->mult_val,
+ v->add_val, tem);
value = tem;
}
-
+
splittable_regs[REGNO (v->new_reg)] = value;
}
else
To share a register here, the values must be
equal. */
&& rtx_equal_p (v->same->mult_val, v->mult_val)
- && rtx_equal_p (v->same->add_val, v->add_val))
-
+ && rtx_equal_p (v->same->add_val, v->add_val)
+ /* If the memory references have different modes,
+ then the address may not be valid and we must
+ not share registers. */
+ && verify_addresses (v, giv_inc, unroll_number))
{
v->dest_reg = v->same->dest_reg;
v->shared = 1;
Emit insn to initialize its value before loop start. */
rtx tem = gen_reg_rtx (v->mode);
+ struct induction *same = v->same;
+ rtx new_reg = v->new_reg;
record_base_value (REGNO (tem), v->add_val, 0);
/* If the address giv has a constant in its new_reg value,
then this constant can be pulled out and put in value,
instead of being part of the initialization code. */
-
- if (GET_CODE (v->new_reg) == PLUS
- && GET_CODE (XEXP (v->new_reg, 1)) == CONST_INT)
+
+ if (GET_CODE (new_reg) == PLUS
+ && GET_CODE (XEXP (new_reg, 1)) == CONST_INT)
{
v->dest_reg
- = plus_constant (tem, INTVAL (XEXP (v->new_reg,1)));
+ = plus_constant (tem, INTVAL (XEXP (new_reg, 1)));
/* Only succeed if this will give valid addresses.
Try to validate both the first and the last
/* Save the negative of the eliminated const, so
that we can calculate the dest_reg's increment
value later. */
- v->const_adjust = - INTVAL (XEXP (v->new_reg, 1));
+ v->const_adjust = -INTVAL (XEXP (new_reg, 1));
- v->new_reg = XEXP (v->new_reg, 0);
+ new_reg = XEXP (new_reg, 0);
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Eliminating constant from giv %d\n",
}
else
v->dest_reg = tem;
-
+
/* If the address hasn't been checked for validity yet, do so
now, and fail completely if either the first or the last
unrolled copy of the address is not a valid address
INSN_UID (v->insn));
continue;
}
-
+
+ v->new_reg = new_reg;
+ v->same = same;
+
/* We set this after the address check, to guarantee that
the register will be initialized. */
v->unrolled = 1;
instruction on machines with complex addressing modes.
If we can't recognize it, then delete it and emit insns
to calculate the value from scratch. */
- emit_insn_before (gen_rtx_SET (VOIDmode, tem,
- copy_rtx (v->new_reg)),
- loop_start);
- if (recog_memoized (PREV_INSN (loop_start)) < 0)
+ loop_insn_hoist (loop, gen_rtx_SET (VOIDmode, tem,
+ copy_rtx (v->new_reg)));
+ if (recog_memoized (PREV_INSN (loop->start)) < 0)
{
rtx sequence, ret;
/* We can't use bl->initial_value to compute the initial
value, because the loop may have been preconditioned.
- We must calculate it from NEW_REG. Try using
- force_operand instead of emit_iv_add_mult. */
- delete_insn (PREV_INSN (loop_start));
+ We must calculate it from NEW_REG. */
+ delete_insn (PREV_INSN (loop->start));
start_sequence ();
ret = force_operand (v->new_reg, tem);
emit_move_insn (tem, ret);
sequence = gen_sequence ();
end_sequence ();
- emit_insn_before (sequence, loop_start);
+ loop_insn_hoist (loop, sequence);
if (loop_dump_stream)
fprintf (loop_dump_stream,
else
{
v->dest_reg = value;
-
+
/* Check the resulting address for validity, and fail
if the resulting address would be invalid. */
if (! verify_addresses (v, giv_inc, unroll_number))
continue;
}
}
-
+
/* Store the value of dest_reg into the insn. This sharing
will not be a problem as this insn will always be copied
later. */
-
+
*v->location = v->dest_reg;
-
+
/* If this address giv is combined with a dest reg giv, then
save the base giv's induction pointer so that we will be
able to handle this address giv properly. The base giv
itself does not have to be splittable. */
-
+
if (v->same && v->same->giv_type == DEST_REG)
addr_combined_regs[REGNO (v->same->new_reg)] = v->same;
-
+
if (GET_CODE (v->new_reg) == REG)
{
/* This giv maybe hasn't been combined with any others.
Make sure that it's giv is marked as splittable here. */
-
+
splittable_regs[REGNO (v->new_reg)] = value;
-
+
/* Make it appear to depend upon itself, so that the
giv will be properly split in the main loop above. */
if (! v->same)
it makes sense to reduce&split givs when possible, as this will
result in simpler instructions, and will not require that a reg
be live across loop iterations. */
-
+
splittable_regs[REGNO (v->dest_reg)] = value;
fprintf (stderr, "Giv %d at insn %d not reduced\n",
REGNO (v->dest_reg), INSN_UID (v->insn));
continue;
#endif
}
-
+
/* Unreduced givs are only updated once by definition. Reduced givs
are updated as many times as their biv is. Mark it so if this is
a splittable register. Don't need to do anything for address givs
{
int count = 1;
if (! v->ignore)
- count = reg_biv_class[REGNO (v->src_reg)]->biv_count;
+ count = REG_IV_CLASS (ivs, REGNO (v->src_reg))->biv_count;
splittable_regs_updates[REGNO (v->new_reg)] = count;
}
result++;
-
+
if (loop_dump_stream)
{
int regnum;
-
+
if (GET_CODE (v->dest_reg) == CONST_INT)
regnum = -1;
else if (GET_CODE (v->dest_reg) != REG)
it can search past if statements and other similar structures. */
static int
-reg_dead_after_loop (reg, loop_start, loop_end)
- rtx reg, loop_start, loop_end;
+reg_dead_after_loop (loop, reg)
+ const struct loop *loop;
+ rtx reg;
{
rtx insn, label;
enum rtx_code code;
int jump_count = 0;
int label_count = 0;
- int this_loop_num = uid_loop_num[INSN_UID (loop_start)];
/* In addition to checking all exits of this loop, we must also check
all exits of inner nested loops that would exit this loop. We don't
have any way to identify those, so we just give up if there are any
such inner loop exits. */
-
- for (label = loop_number_exit_labels[this_loop_num]; label;
- label = LABEL_NEXTREF (label))
+
+ for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
label_count++;
- if (label_count != loop_number_exit_count[this_loop_num])
+ if (label_count != loop->exit_count)
return 0;
/* HACK: Must also search the loop fall through exit, create a label_ref
- here which points to the loop_end, and append the loop_number_exit_labels
+ here which points to the loop->end, and append the loop_number_exit_labels
list to it. */
- label = gen_rtx_LABEL_REF (VOIDmode, loop_end);
- LABEL_NEXTREF (label) = loop_number_exit_labels[this_loop_num];
+ label = gen_rtx_LABEL_REF (VOIDmode, loop->end);
+ LABEL_NEXTREF (label) = loop->exit_labels;
- for ( ; label; label = LABEL_NEXTREF (label))
+ for (; label; label = LABEL_NEXTREF (label))
{
/* Succeed if find an insn which sets the biv or if reach end of
function. Fail if find an insn that uses the biv, or if come to
{
if (GET_CODE (PATTERN (insn)) == RETURN)
break;
- else if (! simplejump_p (insn)
+ else if (!any_uncondjump_p (insn)
/* Prevent infinite loop following infinite loops. */
|| jump_count++ > 20)
return 0;
/* Try to calculate the final value of the biv, the value it will have at
the end of the loop. If we can do it, return that value. */
-
+
rtx
-final_biv_value (bl, loop_start, loop_end, n_iterations)
+final_biv_value (loop, bl)
+ const struct loop *loop;
struct iv_class *bl;
- rtx loop_start, loop_end;
- unsigned HOST_WIDE_INT n_iterations;
{
+ unsigned HOST_WIDE_INT n_iterations = LOOP_INFO (loop)->n_iterations;
rtx increment, tem;
/* ??? This only works for MODE_INT biv's. Reject all others for now. */
return 0;
/* The final value for reversed bivs must be calculated differently than
- for ordinary bivs. In this case, there is already an insn after the
+ for ordinary bivs. In this case, there is already an insn after the
loop which sets this biv's final value (if necessary), and there are
no other loop exits, so we can return any value. */
if (bl->reversed)
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Final biv value for %d, reversed biv.\n", bl->regno);
-
+
return const0_rtx;
}
value of the biv must be invariant. */
if (n_iterations != 0
- && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
- && invariant_p (bl->initial_value))
+ && ! loop->exit_count
+ && loop_invariant_p (loop, bl->initial_value))
{
- increment = biv_total_increment (bl, loop_start, loop_end);
-
- if (increment && invariant_p (increment))
+ increment = biv_total_increment (bl);
+
+ if (increment && loop_invariant_p (loop, increment))
{
/* Can calculate the loop exit value, emit insns after loop
end to calculate this value into a temporary register in
tem = gen_reg_rtx (bl->biv->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
- /* Make sure loop_end is not the last insn. */
- if (NEXT_INSN (loop_end) == 0)
- emit_note_after (NOTE_INSN_DELETED, loop_end);
- emit_iv_add_mult (increment, GEN_INT (n_iterations),
- bl->initial_value, tem, NEXT_INSN (loop_end));
+ loop_iv_add_mult_sink (loop, increment, GEN_INT (n_iterations),
+ bl->initial_value, tem);
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Final biv value for %d, calculated.\n", bl->regno);
-
+
return tem;
}
}
/* Check to see if the biv is dead at all loop exits. */
- if (reg_dead_after_loop (bl->biv->src_reg, loop_start, loop_end))
+ if (reg_dead_after_loop (loop, bl->biv->src_reg))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
the end of the loop. If we can do it, return that value. */
rtx
-final_giv_value (v, loop_start, loop_end, n_iterations)
+final_giv_value (loop, v)
+ const struct loop *loop;
struct induction *v;
- rtx loop_start, loop_end;
- unsigned HOST_WIDE_INT n_iterations;
{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
rtx insn;
rtx increment, tem;
- rtx insert_before, seq;
+ rtx seq;
+ rtx loop_end = loop->end;
+ unsigned HOST_WIDE_INT n_iterations = LOOP_INFO (loop)->n_iterations;
- bl = reg_biv_class[REGNO (v->src_reg)];
+ bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
/* The final value for givs which depend on reversed bivs must be calculated
differently than for ordinary givs. In this case, there is already an
/* Try to calculate the final value as a function of the biv it depends
upon. The only exit from the loop must be the fall through at the bottom
(otherwise it may not have its final value when the loop exits). */
-
+
/* ??? Can calculate the final giv value by subtracting off the
extra biv increments times the giv's mult_val. The loop must have
only one exit for this to work, but the loop iterations does not need
to be known. */
if (n_iterations != 0
- && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
+ && ! loop->exit_count)
{
/* ?? It is tempting to use the biv's value here since these insns will
be put after the loop, and hence the biv will have its final value
sure that bl->initial_value is still valid then. It will still
be valid if it is invariant. */
- increment = biv_total_increment (bl, loop_start, loop_end);
+ increment = biv_total_increment (bl);
- if (increment && invariant_p (increment)
- && invariant_p (bl->initial_value))
+ if (increment && loop_invariant_p (loop, increment)
+ && loop_invariant_p (loop, bl->initial_value))
{
/* Can calculate the loop exit value of its biv as
(n_iterations * increment) + initial_value */
-
+
/* The loop exit value of the giv is then
(final_biv_value - extra increments) * mult_val + add_val.
The extra increments are any increments to the biv which
We must search from the insn that sets the giv to the end
of the loop to calculate this value. */
- insert_before = NEXT_INSN (loop_end);
-
/* Put the final biv value in tem. */
- tem = gen_reg_rtx (bl->biv->mode);
+ tem = gen_reg_rtx (v->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
- emit_iv_add_mult (increment, GEN_INT (n_iterations),
- bl->initial_value, tem, insert_before);
+ loop_iv_add_mult_sink (loop, extend_value_for_giv (v, increment),
+ GEN_INT (n_iterations),
+ extend_value_for_giv (v, bl->initial_value),
+ tem);
/* Subtract off extra increments as we find them. */
for (insn = NEXT_INSN (v->insn); insn != loop_end;
OPTAB_LIB_WIDEN);
seq = gen_sequence ();
end_sequence ();
- emit_insn_before (seq, insert_before);
+ loop_insn_sink (loop, seq);
}
}
-
+
/* Now calculate the giv's final value. */
- emit_iv_add_mult (tem, v->mult_val, v->add_val, tem,
- insert_before);
-
+ loop_iv_add_mult_sink (loop, tem, v->mult_val, v->add_val, tem);
+
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Final giv value for %d, calc from biv's value.\n",
abort ();
/* Check to see if the biv is dead at all loop exits. */
- if (reg_dead_after_loop (v->dest_reg, loop_start, loop_end))
+ if (reg_dead_after_loop (loop, v->dest_reg))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
return 0;
}
-
-/* Look back before LOOP_START for then insn that sets REG and return
+/* Look back before LOOP->START for then insn that sets REG and return
the equivalent constant if there is a REG_EQUAL note otherwise just
the SET_SRC of REG. */
static rtx
-loop_find_equiv_value (loop_start, reg)
- rtx loop_start;
+loop_find_equiv_value (loop, reg)
+ const struct loop *loop;
rtx reg;
{
+ rtx loop_start = loop->start;
rtx insn, set;
rtx ret;
-
+
ret = reg;
- for (insn = PREV_INSN (loop_start); insn ; insn = PREV_INSN (insn))
+ for (insn = PREV_INSN (loop_start); insn; insn = PREV_INSN (insn))
{
if (GET_CODE (insn) == CODE_LABEL)
break;
-
- else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
- && reg_set_p (reg, insn))
+
+ else if (INSN_P (insn) && reg_set_p (reg, insn))
{
/* We found the last insn before the loop that sets the register.
If it sets the entire register, and has a REG_EQUAL note,
then use the value of the REG_EQUAL note. */
if ((set = single_set (insn))
- && (SET_DEST (set) == reg))
+ && (SET_DEST (set) == reg))
{
rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
-
+
/* Only use the REG_EQUAL note if it is a constant.
Other things, divide in particular, will cause
problems later if we use them. */
ret = XEXP (note, 0);
else
ret = SET_SRC (set);
+
+ /* We cannot do this if it changes between the
+ assignment and loop start though. */
+ if (modified_between_p (ret, insn, loop_start))
+ ret = reg;
}
break;
}
return ret;
}
+/* Return a simplified rtx for the expression OP - REG.
+
+ REG must appear in OP, and OP must be a register or the sum of a register
+ and a second term.
-/* Calculate the number of loop iterations. Returns the exact number of loop
- iterations if it can be calculated, otherwise returns zero. */
+ Thus, the return value must be const0_rtx or the second term.
+
+ The caller is responsible for verifying that REG appears in OP and OP has
+ the proper form. */
+
+static rtx
+subtract_reg_term (op, reg)
+ rtx op, reg;
+{
+ if (op == reg)
+ return const0_rtx;
+ if (GET_CODE (op) == PLUS)
+ {
+ if (XEXP (op, 0) == reg)
+ return XEXP (op, 1);
+ else if (XEXP (op, 1) == reg)
+ return XEXP (op, 0);
+ }
+ /* OP does not contain REG as a term. */
+ abort ();
+}
+
+/* Find and return register term common to both expressions OP0 and
+ OP1 or NULL_RTX if no such term exists. Each expression must be a
+ REG or a PLUS of a REG. */
+
+static rtx
+find_common_reg_term (op0, op1)
+ rtx op0, op1;
+{
+ if ((GET_CODE (op0) == REG || GET_CODE (op0) == PLUS)
+ && (GET_CODE (op1) == REG || GET_CODE (op1) == PLUS))
+ {
+ rtx op00;
+ rtx op01;
+ rtx op10;
+ rtx op11;
+
+ if (GET_CODE (op0) == PLUS)
+ op01 = XEXP (op0, 1), op00 = XEXP (op0, 0);
+ else
+ op01 = const0_rtx, op00 = op0;
+
+ if (GET_CODE (op1) == PLUS)
+ op11 = XEXP (op1, 1), op10 = XEXP (op1, 0);
+ else
+ op11 = const0_rtx, op10 = op1;
+
+ /* Find and return common register term if present. */
+ if (REG_P (op00) && (op00 == op10 || op00 == op11))
+ return op00;
+ else if (REG_P (op01) && (op01 == op10 || op01 == op11))
+ return op01;
+ }
+
+ /* No common register term found. */
+ return NULL_RTX;
+}
+
+/* Determine the loop iterator and calculate the number of loop
+ iterations. Returns the exact number of loop iterations if it can
+ be calculated, otherwise returns zero. */
unsigned HOST_WIDE_INT
-loop_iterations (loop_start, loop_end, loop_info)
- rtx loop_start, loop_end;
- struct loop_info *loop_info;
+loop_iterations (loop)
+ struct loop *loop;
{
+ struct loop_info *loop_info = LOOP_INFO (loop);
+ struct loop_ivs *ivs = LOOP_IVS (loop);
rtx comparison, comparison_value;
rtx iteration_var, initial_value, increment, final_value;
enum rtx_code comparison_code;
- HOST_WIDE_INT abs_inc;
+ HOST_WIDE_INT inc;
+ unsigned HOST_WIDE_INT abs_inc;
unsigned HOST_WIDE_INT abs_diff;
int off_by_one;
int increment_dir;
int unsigned_p, compare_dir, final_larger;
rtx last_loop_insn;
+ rtx reg_term;
+ struct iv_class *bl;
loop_info->n_iterations = 0;
loop_info->initial_value = 0;
loop_info->increment = 0;
loop_info->iteration_var = 0;
loop_info->unroll_number = 1;
+ loop_info->iv = 0;
- /* First find the iteration variable. If the last insn is a conditional
- branch, and the insn before tests a register value, make that the
- iteration variable. */
-
/* We used to use prev_nonnote_insn here, but that fails because it might
accidentally get the branch for a contained loop if the branch for this
loop was deleted. We can only trust branches immediately before the
loop_end. */
- last_loop_insn = PREV_INSN (loop_end);
+ last_loop_insn = PREV_INSN (loop->end);
- comparison = get_condition_for_loop (last_loop_insn);
- if (comparison == 0)
+ /* ??? We should probably try harder to find the jump insn
+ at the end of the loop. The following code assumes that
+ the last loop insn is a jump to the top of the loop. */
+ if (GET_CODE (last_loop_insn) != JUMP_INSN)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
return 0;
}
+ /* If there is a more than a single jump to the top of the loop
+ we cannot (easily) determine the iteration count. */
+ if (LABEL_NUSES (JUMP_LABEL (last_loop_insn)) > 1)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Loop has multiple back edges.\n");
+ return 0;
+ }
+
+ /* Find the iteration variable. If the last insn is a conditional
+ branch, and the insn before tests a register value, make that the
+ iteration variable. */
+
+ comparison = get_condition_for_loop (loop, last_loop_insn);
+ if (comparison == 0)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: No final comparison found.\n");
+ return 0;
+ }
+
/* ??? Get_condition may switch position of induction variable and
invariant register when it canonicalizes the comparison. */
return 0;
}
- /* Loop iterations is always called before any new registers are created
- now, so this should never occur. */
+ /* The only new registers that are created before loop iterations
+ are givs made from biv increments or registers created by
+ load_mems. In the latter case, it is possible that try_copy_prop
+ will propagate a new pseudo into the old iteration register but
+ this will be marked by having the REG_USERVAR_P bit set. */
- if (REGNO (iteration_var) >= max_reg_before_loop)
+ if ((unsigned) REGNO (iteration_var) >= ivs->n_regs
+ && ! REG_USERVAR_P (iteration_var))
abort ();
- iteration_info (iteration_var, &initial_value, &increment,
- loop_start, loop_end);
+ /* Determine the initial value of the iteration variable, and the amount
+ that it is incremented each loop. Use the tables constructed by
+ the strength reduction pass to calculate these values. */
+
+ /* Clear the result values, in case no answer can be found. */
+ initial_value = 0;
+ increment = 0;
+
+ /* The iteration variable can be either a giv or a biv. Check to see
+ which it is, and compute the variable's initial value, and increment
+ value if possible. */
+
+ /* If this is a new register, can't handle it since we don't have any
+ reg_iv_type entry for it. */
+ if ((unsigned) REGNO (iteration_var) >= ivs->n_regs)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: No reg_iv_type entry for iteration var.\n");
+ return 0;
+ }
+
+ /* Reject iteration variables larger than the host wide int size, since they
+ could result in a number of iterations greater than the range of our
+ `unsigned HOST_WIDE_INT' variable loop_info->n_iterations. */
+ else if ((GET_MODE_BITSIZE (GET_MODE (iteration_var))
+ > HOST_BITS_PER_WIDE_INT))
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Iteration var rejected because mode too large.\n");
+ return 0;
+ }
+ else if (GET_MODE_CLASS (GET_MODE (iteration_var)) != MODE_INT)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Iteration var not an integer.\n");
+ return 0;
+ }
+ else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
+ {
+ if (REGNO (iteration_var) >= ivs->n_regs)
+ abort ();
+
+ /* Grab initial value, only useful if it is a constant. */
+ bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
+ initial_value = bl->initial_value;
+ if (!bl->biv->always_executed || bl->biv->maybe_multiple)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Basic induction var not set once in each iteration.\n");
+ return 0;
+ }
+
+ increment = biv_total_increment (bl);
+ }
+ else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
+ {
+ HOST_WIDE_INT offset = 0;
+ struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
+ rtx biv_initial_value;
+
+ if (REGNO (v->src_reg) >= ivs->n_regs)
+ abort ();
+
+ if (!v->always_executed || v->maybe_multiple)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: General induction var not set once in each iteration.\n");
+ return 0;
+ }
+
+ bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
+
+ /* Increment value is mult_val times the increment value of the biv. */
+
+ increment = biv_total_increment (bl);
+ if (increment)
+ {
+ struct induction *biv_inc;
+
+ increment = fold_rtx_mult_add (v->mult_val,
+ extend_value_for_giv (v, increment),
+ const0_rtx, v->mode);
+ /* The caller assumes that one full increment has occured at the
+ first loop test. But that's not true when the biv is incremented
+ after the giv is set (which is the usual case), e.g.:
+ i = 6; do {;} while (i++ < 9) .
+ Therefore, we bias the initial value by subtracting the amount of
+ the increment that occurs between the giv set and the giv test. */
+ for (biv_inc = bl->biv; biv_inc; biv_inc = biv_inc->next_iv)
+ {
+ if (loop_insn_first_p (v->insn, biv_inc->insn))
+ offset -= INTVAL (biv_inc->add_val);
+ }
+ }
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Giv iterator, initial value bias %ld.\n",
+ (long) offset);
+
+ /* Initial value is mult_val times the biv's initial value plus
+ add_val. Only useful if it is a constant. */
+ biv_initial_value = extend_value_for_giv (v, bl->initial_value);
+ initial_value
+ = fold_rtx_mult_add (v->mult_val,
+ plus_constant (biv_initial_value, offset),
+ v->add_val, v->mode);
+ }
+ else
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Not basic or general induction var.\n");
+ return 0;
+ }
+
if (initial_value == 0)
- /* iteration_info already printed a message. */
return 0;
unsigned_p = 0;
its value from the insns before the start of the loop. */
final_value = comparison_value;
- if (GET_CODE (comparison_value) == REG && invariant_p (comparison_value))
+ if (GET_CODE (comparison_value) == REG
+ && loop_invariant_p (loop, comparison_value))
{
- final_value = loop_find_equiv_value (loop_start, comparison_value);
+ final_value = loop_find_equiv_value (loop, comparison_value);
+
/* If we don't get an invariant final value, we are better
off with the original register. */
- if (!invariant_p (final_value))
+ if (! loop_invariant_p (loop, final_value))
final_value = comparison_value;
}
/* Save the calculated values describing this loop's bounds, in case
precondition_loop_p will need them later. These values can not be
recalculated inside precondition_loop_p because strength reduction
- optimizations may obscure the loop's structure.
+ optimizations may obscure the loop's structure.
These values are only required by precondition_loop_p and insert_bct
whenever the number of iterations cannot be computed at compile time.
loop_info->increment = increment;
loop_info->iteration_var = iteration_var;
loop_info->comparison_code = comparison_code;
+ loop_info->iv = bl;
- if (REG_P (initial_value))
- {
- rtx temp = final_value;
+ /* Try to determine the iteration count for loops such
+ as (for i = init; i < init + const; i++). When running the
+ loop optimization twice, the first pass often converts simple
+ loops into this form. */
- /* initial_value = reg1, final_value = reg2 + const, where reg1
- != reg2. Try to find what reg1 is equivalent to. Hopefully
- it will either be reg2 or reg2 plus a constant. */
- if (GET_CODE (temp) == PLUS)
- temp = XEXP (temp, 0);
- if (REG_P (temp) && REGNO (temp) != REGNO (initial_value))
- initial_value = loop_find_equiv_value (loop_start, initial_value);
- }
-
- /* If have initial_value = reg + const1 and final_value = reg +
- const2, then replace initial_value with const1 and final_value
- with const2. This should be safe since we are protected by the
- initial comparison before entering the loop. */
- if ((GET_CODE (initial_value) == REG || GET_CODE (initial_value) == PLUS)
- && (GET_CODE (final_value) == REG || GET_CODE (final_value) == PLUS))
+ if (REG_P (initial_value))
{
- rtx init_op0;
- rtx fini_op0;
- rtx init_op1;
- rtx fini_op1;
-
- if (GET_CODE (initial_value) == PLUS)
- init_op1 = XEXP (initial_value, 1), init_op0 = XEXP (initial_value, 0);
- else
- init_op1 = const0_rtx, init_op0 = initial_value;
+ rtx reg1;
+ rtx reg2;
+ rtx const2;
+ reg1 = initial_value;
if (GET_CODE (final_value) == PLUS)
- fini_op1 = XEXP (final_value, 1), fini_op0 = XEXP (final_value, 0);
+ reg2 = XEXP (final_value, 0), const2 = XEXP (final_value, 1);
else
- fini_op1 = const0_rtx, fini_op0 = final_value;
+ reg2 = final_value, const2 = const0_rtx;
- /* Remove register common factor if present. */
- if (REG_P (init_op0) && init_op0 == fini_op0)
- {
- initial_value = init_op1;
- final_value = fini_op1;
- }
- else if (REG_P (init_op0) && init_op0 == fini_op1)
- {
- initial_value = init_op1;
- final_value = fini_op0;
- }
- else if (REG_P (init_op1) && init_op1 == fini_op0)
+ /* Check for initial_value = reg1, final_value = reg2 + const2,
+ where reg1 != reg2. */
+ if (REG_P (reg2) && reg2 != reg1)
{
- initial_value = init_op0;
- final_value = fini_op1;
+ rtx temp;
+
+ /* Find what reg1 is equivalent to. Hopefully it will
+ either be reg2 or reg2 plus a constant. */
+ temp = loop_find_equiv_value (loop, reg1);
+
+ if (find_common_reg_term (temp, reg2))
+ initial_value = temp;
+ else
+ {
+ /* Find what reg2 is equivalent to. Hopefully it will
+ either be reg1 or reg1 plus a constant. Let's ignore
+ the latter case for now since it is not so common. */
+ temp = loop_find_equiv_value (loop, reg2);
+
+ if (temp == loop_info->iteration_var)
+ temp = initial_value;
+ if (temp == reg1)
+ final_value = (const2 == const0_rtx)
+ ? reg1 : gen_rtx_PLUS (GET_MODE (reg1), reg1, const2);
+ }
}
- else if (REG_P (init_op1) && init_op1 == fini_op1)
+ else if (loop->vtop && GET_CODE (reg2) == CONST_INT)
{
- initial_value = init_op0;
- final_value = fini_op0;
+ rtx temp;
+
+ /* When running the loop optimizer twice, check_dbra_loop
+ further obfuscates reversible loops of the form:
+ for (i = init; i < init + const; i++). We often end up with
+ final_value = 0, initial_value = temp, temp = temp2 - init,
+ where temp2 = init + const. If the loop has a vtop we
+ can replace initial_value with const. */
+
+ temp = loop_find_equiv_value (loop, reg1);
+
+ if (GET_CODE (temp) == MINUS && REG_P (XEXP (temp, 0)))
+ {
+ rtx temp2 = loop_find_equiv_value (loop, XEXP (temp, 0));
+
+ if (GET_CODE (temp2) == PLUS
+ && XEXP (temp2, 0) == XEXP (temp, 1))
+ initial_value = XEXP (temp2, 1);
+ }
}
}
+
+ /* If have initial_value = reg + const1 and final_value = reg +
+ const2, then replace initial_value with const1 and final_value
+ with const2. This should be safe since we are protected by the
+ initial comparison before entering the loop if we have a vtop.
+ For example, a + b < a + c is not equivalent to b < c for all a
+ when using modulo arithmetic.
+
+ ??? Without a vtop we could still perform the optimization if we check
+ the initial and final values carefully. */
+ if (loop->vtop
+ && (reg_term = find_common_reg_term (initial_value, final_value)))
+ {
+ initial_value = subtract_reg_term (initial_value, reg_term);
+ final_value = subtract_reg_term (final_value, reg_term);
+ }
+
loop_info->initial_equiv_value = initial_value;
loop_info->final_equiv_value = final_value;
-
+
+ /* For EQ comparison loops, we don't have a valid final value.
+ Check this now so that we won't leave an invalid value if we
+ return early for any other reason. */
+ if (comparison_code == EQ)
+ loop_info->final_equiv_value = loop_info->final_value = 0;
+
if (increment == 0)
{
if (loop_dump_stream)
if (GET_CODE (increment) != CONST_INT)
{
- increment = loop_find_equiv_value (loop_start, increment);
+ /* If we have a REG, check to see if REG holds a constant value. */
+ /* ??? Other RTL, such as (neg (reg)) is possible here, but it isn't
+ clear if it is worthwhile to try to handle such RTL. */
+ if (GET_CODE (increment) == REG || GET_CODE (increment) == SUBREG)
+ increment = loop_find_equiv_value (loop, increment);
if (GET_CODE (increment) != CONST_INT)
{
{
fprintf (loop_dump_stream,
"Loop iterations: Increment value not constant ");
- print_rtl (loop_dump_stream, increment);
+ print_simple_rtl (loop_dump_stream, increment);
fprintf (loop_dump_stream, ".\n");
}
return 0;
{
fprintf (loop_dump_stream,
"Loop iterations: Initial value not constant ");
- print_rtl (loop_dump_stream, initial_value);
+ print_simple_rtl (loop_dump_stream, initial_value);
fprintf (loop_dump_stream, ".\n");
}
return 0;
else if (comparison_code == EQ)
{
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop iterations: EQ comparison loop.\n");
+ fprintf (loop_dump_stream, "Loop iterations: EQ comparison loop.\n");
return 0;
}
else if (GET_CODE (final_value) != CONST_INT)
{
fprintf (loop_dump_stream,
"Loop iterations: Final value not constant ");
- print_rtl (loop_dump_stream, final_value);
+ print_simple_rtl (loop_dump_stream, final_value);
fprintf (loop_dump_stream, ".\n");
}
return 0;
will overflow before the loop exits), 4 infinite loop cases, and 15
immediate exit (0 or 1 iteration depending on loop type) cases.
Only try to optimize the normal cases. */
-
+
/* (compare_dir/final_larger/increment_dir)
Normal cases: (0/-1/-1), (0/1/1), (-1/-1/-1), (1/1/1)
Reverse cases: (0/-1/1), (0/1/-1), (-1/-1/1), (1/1/-1)
else
{
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop iterations: Not normal loop.\n");
+ fprintf (loop_dump_stream, "Loop iterations: Not normal loop.\n");
return 0;
}
so correct for that. Note that abs_diff and n_iterations are
unsigned, because they can be as large as 2^n - 1. */
- abs_inc = INTVAL (increment);
- if (abs_inc > 0)
- abs_diff = INTVAL (final_value) - INTVAL (initial_value);
- else if (abs_inc < 0)
+ inc = INTVAL (increment);
+ if (inc > 0)
+ {
+ abs_diff = INTVAL (final_value) - INTVAL (initial_value);
+ abs_inc = inc;
+ }
+ else if (inc < 0)
{
abs_diff = INTVAL (initial_value) - INTVAL (final_value);
- abs_inc = -abs_inc;
+ abs_inc = -inc;
}
else
abort ();
+ /* Given that iteration_var is going to iterate over its own mode,
+ not HOST_WIDE_INT, disregard higher bits that might have come
+ into the picture due to sign extension of initial and final
+ values. */
+ abs_diff &= ((unsigned HOST_WIDE_INT)1
+ << (GET_MODE_BITSIZE (GET_MODE (iteration_var)) - 1)
+ << 1) - 1;
+
/* For NE tests, make sure that the iteration variable won't miss
the final value. If abs_diff mod abs_incr is not zero, then the
iteration variable will overflow before the loop exits, and we
return loop_info->n_iterations;
}
-
/* Replace uses of split bivs with their split pseudo register. This is
for original instructions which remain after loop unrolling without
copying. */
static rtx
-remap_split_bivs (x)
+remap_split_bivs (loop, x)
+ struct loop *loop;
rtx x;
{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
register enum rtx_code code;
register int i;
- register char *fmt;
+ register const char *fmt;
if (x == 0)
return x;
/* If non-reduced/final-value givs were split, then this would also
have to remap those givs also. */
#endif
- if (REGNO (x) < max_reg_before_loop
- && reg_iv_type[REGNO (x)] == BASIC_INDUCT)
- return reg_biv_class[REGNO (x)]->biv->src_reg;
+ if (REGNO (x) < ivs->n_regs
+ && REG_IV_TYPE (ivs, REGNO (x)) == BASIC_INDUCT)
+ return REG_IV_CLASS (ivs, REGNO (x))->biv->src_reg;
break;
-
+
default:
break;
}
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
- XEXP (x, i) = remap_split_bivs (XEXP (x, i));
- if (fmt[i] == 'E')
+ XEXP (x, i) = remap_split_bivs (loop, XEXP (x, i));
+ else if (fmt[i] == 'E')
{
register int j;
for (j = 0; j < XVECLEN (x, i); j++)
- XVECEXP (x, i, j) = remap_split_bivs (XVECEXP (x, i, j));
+ XVECEXP (x, i, j) = remap_split_bivs (loop, XVECEXP (x, i, j));
}
}
return x;
while (INSN_UID (p) != first_uid)
{
if (GET_CODE (p) == JUMP_INSN)
- passed_jump= 1;
+ passed_jump = 1;
/* Could not find FIRST_UID. */
if (p == copy_end)
return 0;
}
/* Verify that FIRST_UID is an insn that entirely sets REGNO. */
- if (GET_RTX_CLASS (GET_CODE (p)) != 'i'
- || ! dead_or_set_regno_p (p, regno))
+ if (! INSN_P (p) || ! dead_or_set_regno_p (p, regno))
return 0;
/* FIRST_UID is always executed. */
/* FIRST_UID is always executed if LAST_UID is executed. */
return 1;
}
+
+/* This routine is called when the number of iterations for the unrolled
+ loop is one. The goal is to identify a loop that begins with an
+ unconditional branch to the loop continuation note (or a label just after).
+ In this case, the unconditional branch that starts the loop needs to be
+ deleted so that we execute the single iteration. */
+
+static rtx
+ujump_to_loop_cont (loop_start, loop_cont)
+ rtx loop_start;
+ rtx loop_cont;
+{
+ rtx x, label, label_ref;
+
+ /* See if loop start, or the next insn is an unconditional jump. */
+ loop_start = next_nonnote_insn (loop_start);
+
+ x = pc_set (loop_start);
+ if (!x)
+ return NULL_RTX;
+
+ label_ref = SET_SRC (x);
+ if (!label_ref)
+ return NULL_RTX;
+
+ /* Examine insn after loop continuation note. Return if not a label. */
+ label = next_nonnote_insn (loop_cont);
+ if (label == 0 || GET_CODE (label) != CODE_LABEL)
+ return NULL_RTX;
+
+ /* Return the loop start if the branch label matches the code label. */
+ if (CODE_LABEL_NUMBER (label) == CODE_LABEL_NUMBER (XEXP (label_ref, 0)))
+ return loop_start;
+ else
+ return NULL_RTX;
+}
OSDN Git Service
