diff options
| -rw-r--r-- | gcc/ChangeLog | 26 | ||||
| -rw-r--r-- | gcc/basic-block.h | 3 | ||||
| -rw-r--r-- | gcc/hard-reg-set.h | 4 | ||||
| -rw-r--r-- | gcc/loop.c | 323 | ||||
| -rw-r--r-- | gcc/loop.h | 12 | ||||
| -rw-r--r-- | gcc/unroll.c | 86 |
6 files changed, 297 insertions, 157 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 3258113..bcdb2ba 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,31 @@ 2001-01-07 Michael Hayes <mhayes@redhat.com> + * hard-reg-set.h: Add multiple include guard. + * basic-block.h (struct loop): Add `sink' field. + * loop.h: Include sbitmap.h, hard-reg-set.h, and basic-block.h. + (emit_iv_add_mult): Delete. + (loop_iv_add_mult_hoist, loop_iv_add_mult_sink): Define. + (loop_iv_add_mult_emit_before, loop_insn_sink): Define. + (unroll_loop): Remove end_insert_before argument. + * loop.c (loop_givs_rescan): Remove end_insert_before argument. + (maybe_eliminate_biv_1): Likewise. + (emit_iv_add_mult): Delete. + (gen_add_mult, loop_regs_update): New. + (loop_insn_emit_after, loop_insn_emit_before): New. + (loop_insn_sink, loop_insn_sink_or_swim): New. + (emit_iv_add_mult): Delete. + (scan_loop): Set loop->sink. + (loop_givs_reduce): Use loop_insn_sink and its ilk. + (loop_givs_rescan, strength_reduce, check_dbra_loop): Likewise. + (maybe_eliminate_biv_1): Likewise. + (maybe_eliminate_biv_1): Add basic block argument. + * unroll.c (unroll_loop): Remove end_insert_before argument. + (find_splittable_regs): Likewise. + (find_splittable_regs): Use loop_insn_sink and its ilk. + (find_splittable_givs, final_biv_value, final_giv_value): Likewise. + +2001-01-07 Michael Hayes <mhayes@redhat.com> + * loop.h (loop_insn_hoist): New prototype. * loop.c (loop_insn_hoist, loop_insn_emit_before): New. (move_movables, loop_givs_rescan): Use loop_insn_hoist. diff --git a/gcc/basic-block.h b/gcc/basic-block.h index a34dbb8..f86ff3c 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -365,6 +365,9 @@ struct loop /* Place in the loop where control enters. */ rtx scan_start; + /* The position where to sink insns out of the loop. */ + rtx sink; + /* List of all LABEL_REFs which refer to code labels outside the loop. Used by routines that need to know all loop exits, such as final_biv_value and final_giv_value. diff --git a/gcc/hard-reg-set.h b/gcc/hard-reg-set.h index 4a305ef..57ab2860 100644 --- a/gcc/hard-reg-set.h +++ b/gcc/hard-reg-set.h @@ -18,6 +18,8 @@ along with GNU CC; see the file COPYING. If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ +#ifndef _HARD_REG_SET_H +#define _HARD_REG_SET_H 1 /* Define the type of a set of hard registers. */ @@ -472,3 +474,5 @@ extern int n_non_fixed_regs; /* Vector indexed by hardware reg giving its name. */ extern const char * reg_names[FIRST_PSEUDO_REGISTER]; + +#endif /* _HARD_REG_SET_H */ @@ -188,7 +188,7 @@ static int loop_giv_reduce_benefit PARAMS((struct loop *, struct iv_class *, static void loop_givs_dead_check PARAMS((struct loop *, struct iv_class *)); static void loop_givs_reduce PARAMS((struct loop *, struct iv_class *)); static void loop_givs_rescan PARAMS((struct loop *, struct iv_class *, - rtx *, rtx)); + rtx *)); static void loop_ivs_free PARAMS((struct loop *)); static void strength_reduce PARAMS ((struct loop *, int, int)); static void find_single_use_in_loop PARAMS ((struct loop_regs *, rtx, rtx)); @@ -225,7 +225,8 @@ static int product_cheap_p PARAMS ((rtx, rtx)); static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *, int, int, int)); static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx, - struct iv_class *, int, rtx)); + struct iv_class *, int, + basic_block, rtx)); static int last_use_this_basic_block PARAMS ((rtx, rtx)); static void record_initial PARAMS ((rtx, rtx, void *)); static void update_reg_last_use PARAMS ((rtx, rtx)); @@ -244,10 +245,15 @@ static void try_swap_copy_prop PARAMS ((const struct loop *, rtx, static int replace_label PARAMS ((rtx *, void *)); static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int)); static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int)); +static rtx gen_add_mult PARAMS ((rtx, rtx, rtx, rtx)); +static void loop_regs_update PARAMS ((const struct loop *, rtx)); static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx)); +static rtx loop_insn_emit_after PARAMS((const struct loop *, basic_block, + rtx, rtx)); static rtx loop_insn_emit_before PARAMS((const struct loop *, basic_block, rtx, rtx)); +static rtx loop_insn_sink_or_swim PARAMS((const struct loop *, rtx)); static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int)); void debug_biv PARAMS ((const struct induction *)); @@ -568,6 +574,15 @@ scan_loop (loop, flags) loop->scan_start = p; + /* If loop end is the end of the current function, then emit a + NOTE_INSN_DELETED after loop_end and set loop->sink to the dummy + note insn. This is the position we use when sinking insns out of + the loop. */ + if (NEXT_INSN (loop->end) != 0) + loop->sink = NEXT_INSN (loop->end); + else + loop->sink = emit_note_after (NOTE_INSN_DELETED, loop->end); + /* Set up variables describing this loop. */ prescan_loop (loop); threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs); @@ -3908,20 +3923,22 @@ loop_givs_reduce (loop, bl) insert_before = v->insn; if (tv->mult_val == const1_rtx) - emit_iv_add_mult (tv->add_val, v->mult_val, - v->new_reg, v->new_reg, insert_before); + loop_iv_add_mult_emit_before (loop, tv->add_val, v->mult_val, + v->new_reg, v->new_reg, + 0, insert_before); else /* tv->mult_val == const0_rtx */ /* A multiply is acceptable here since this is presumed to be seldom executed. */ - emit_iv_add_mult (tv->add_val, v->mult_val, - v->add_val, v->new_reg, insert_before); + loop_iv_add_mult_emit_before (loop, tv->add_val, v->mult_val, + v->add_val, v->new_reg, + 0, insert_before); } /* Add code at loop start to initialize giv's reduced reg. */ - emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value), - v->mult_val, v->add_val, v->new_reg, - loop->start); + loop_iv_add_mult_hoist (loop, + extend_value_for_giv (v, bl->initial_value), + v->mult_val, v->add_val, v->new_reg); } } } @@ -3959,11 +3976,10 @@ loop_givs_dead_check (loop, bl) static void -loop_givs_rescan (loop, bl, reg_map, end_insert_before) +loop_givs_rescan (loop, bl, reg_map) struct loop *loop; struct iv_class *bl; rtx *reg_map; - rtx end_insert_before; { struct induction *v; @@ -4042,22 +4058,12 @@ loop_givs_rescan (loop, bl, reg_map, end_insert_before) not replaceable. The correct final value is the same as the value that the giv starts the reversed loop with. */ if (bl->reversed && ! v->replaceable) - emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value), - v->mult_val, v->add_val, v->dest_reg, - end_insert_before); + loop_iv_add_mult_sink (loop, + extend_value_for_giv (v, bl->initial_value), + v->mult_val, v->add_val, v->dest_reg); else if (v->final_value) - { - /* If the loop has multiple exits, emit the insn before the - 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->exit_count) - loop_insn_hoist (loop, - gen_move_insn (v->dest_reg, v->final_value)); - else - emit_insn_before (gen_move_insn (v->dest_reg, v->final_value), - end_insert_before); - } + loop_insn_sink_or_swim (loop, + gen_move_insn (v->dest_reg, v->final_value)); if (loop_dump_stream) { @@ -4207,24 +4213,11 @@ strength_reduce (loop, insn_count, flags) /* Map of pseudo-register replacements. */ rtx *reg_map = NULL; int reg_map_size; - rtx end_insert_before; int unrolled_insn_copies = 0; rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1); addr_placeholder = gen_reg_rtx (Pmode); - /* Save insn immediately after the loop_end. Insns inserted after loop_end - must be put before this insn, so that they will appear in the right - order (i.e. loop order). - - If loop_end is the end of the current function, then emit a - NOTE_INSN_DELETED after loop_end and set end_insert_before to the - dummy note insn. */ - if (NEXT_INSN (loop->end) != 0) - end_insert_before = NEXT_INSN (loop->end); - else - end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop->end); - ivs->n_regs = max_reg_before_loop; ivs->regs = (struct iv *) xcalloc (ivs->n_regs, sizeof (struct iv)); @@ -4237,7 +4230,7 @@ strength_reduce (loop, insn_count, flags) /* Can still unroll the loop anyways, but indicate that there is no strength reduction info available. */ if (flags & LOOP_UNROLL) - unroll_loop (loop, insn_count, end_insert_before, 0); + unroll_loop (loop, insn_count, 0); loop_ivs_free (loop); return; @@ -4366,7 +4359,7 @@ strength_reduce (loop, insn_count, flags) For each giv register that can be reduced now: if replaceable, substitute reduced reg wherever the old giv occurs; else add new move insn "giv_reg = reduced_reg". */ - loop_givs_rescan (loop, bl, reg_map, end_insert_before); + loop_givs_rescan (loop, bl, reg_map); /* All the givs based on the biv bl have been reduced if they merit it. */ @@ -4420,22 +4413,8 @@ strength_reduce (loop, insn_count, flags) value, so we don't need another one. We can't calculate the proper final value for such a biv here anyways. */ if (bl->final_value && ! bl->reversed) - { - rtx insert_before; - - /* If the loop has multiple exits, emit the insn before the - 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->exit_count) - insert_before = loop->start; - else - insert_before = end_insert_before; - - emit_insn_before (gen_move_insn (bl->biv->dest_reg, - bl->final_value), - end_insert_before); - } + loop_insn_sink_or_swim (loop, gen_move_insn + (bl->biv->dest_reg, bl->final_value)); if (loop_dump_stream) fprintf (loop_dump_stream, "Reg %d: biv eliminated\n", @@ -4489,7 +4468,7 @@ strength_reduce (loop, insn_count, flags) if ((flags & LOOP_UNROLL) || (loop_info->n_iterations > 0 && unrolled_insn_copies <= insn_count)) - unroll_loop (loop, insn_count, end_insert_before, 1); + unroll_loop (loop, insn_count, 1); #ifdef HAVE_doloop_end if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg) @@ -6863,40 +6842,38 @@ restart: free (can_combine); } -/* EMIT code before INSERT_BEFORE to set REG = B * M + A. */ +/* Generate sequence for REG = B * M + A. */ -void -emit_iv_add_mult (b, m, a, reg, insert_before) +static rtx +gen_add_mult (b, m, a, reg) rtx b; /* initial value of basic induction variable */ rtx m; /* multiplicative constant */ rtx a; /* additive constant */ rtx reg; /* destination register */ - rtx insert_before; { rtx seq; rtx result; - /* Prevent unexpected sharing of these rtx. */ - a = copy_rtx (a); - b = copy_rtx (b); - - /* Increase the lifetime of any invariants moved further in code. */ - update_reg_last_use (a, insert_before); - update_reg_last_use (b, insert_before); - update_reg_last_use (m, insert_before); - start_sequence (); + /* Use unsigned arithmetic. */ result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1); if (reg != result) emit_move_insn (reg, result); seq = gen_sequence (); end_sequence (); - emit_insn_before (seq, insert_before); + return seq; +} + + +/* Update registers created in insn sequence SEQ. */ - /* It is entirely possible that the expansion created lots of new - registers. Iterate over the sequence we just created and - record them all. */ +static void +loop_regs_update (loop, seq) + const struct loop *loop ATTRIBUTE_UNUSED; + rtx seq; +{ + /* Update register info for alias analysis. */ if (GET_CODE (seq) == SEQUENCE) { @@ -6916,8 +6893,99 @@ emit_iv_add_mult (b, m, a, reg, insert_before) } } -/* Similar to emit_iv_add_mult, but compute cost rather than emitting - insns. */ + +/* EMIT code before BEFORE_BB/BEFORE_INSN to set REG = B * M + A. */ + +void +loop_iv_add_mult_emit_before (loop, b, m, a, reg, before_bb, before_insn) + const struct loop *loop; + rtx b; /* initial value of basic induction variable */ + rtx m; /* multiplicative constant */ + rtx a; /* additive constant */ + rtx reg; /* destination register */ + basic_block before_bb; + rtx before_insn; +{ + rtx seq; + + if (! before_insn) + { + loop_iv_add_mult_hoist (loop, b, m, a, reg); + return; + } + + /* Use copy_rtx to prevent unexpected sharing of these rtx. */ + seq = gen_add_mult (copy_rtx (b), m, copy_rtx (a), reg); + + /* Increase the lifetime of any invariants moved further in code. */ + update_reg_last_use (a, before_insn); + update_reg_last_use (b, before_insn); + update_reg_last_use (m, before_insn); + + loop_insn_emit_before (loop, before_bb, before_insn, seq); + + /* It is possible that the expansion created lots of new registers. + Iterate over the sequence we just created and record them all. */ + loop_regs_update (loop, seq); +} + + +/* Emit insns in loop pre-header to set REG = B * M + A. */ + +void +loop_iv_add_mult_sink (loop, b, m, a, reg) + const struct loop *loop; + rtx b; /* initial value of basic induction variable */ + rtx m; /* multiplicative constant */ + rtx a; /* additive constant */ + rtx reg; /* destination register */ +{ + rtx seq; + + /* Use copy_rtx to prevent unexpected sharing of these rtx. */ + seq = gen_add_mult (copy_rtx (b), m, copy_rtx (a), reg); + + /* Increase the lifetime of any invariants moved further in code. + ???? Is this really necessary? */ + update_reg_last_use (a, loop->sink); + update_reg_last_use (b, loop->sink); + update_reg_last_use (m, loop->sink); + + loop_insn_sink (loop, seq); + + /* It is possible that the expansion created lots of new registers. + Iterate over the sequence we just created and record them all. */ + loop_regs_update (loop, seq); +} + + +/* Emit insns after loop to set REG = B * M + A. */ + +void +loop_iv_add_mult_hoist (loop, b, m, a, reg) + const struct loop *loop; + rtx b; /* initial value of basic induction variable */ + rtx m; /* multiplicative constant */ + rtx a; /* additive constant */ + rtx reg; /* destination register */ +{ + rtx seq; + + /* Use copy_rtx to prevent unexpected sharing of these rtx. */ + seq = gen_add_mult (copy_rtx (b), m, copy_rtx (a), reg); + + loop_insn_hoist (loop, seq); + + /* It is possible that the expansion created lots of new registers. + Iterate over the sequence we just created and record them all. */ + loop_regs_update (loop, seq); +} + + + +/* Similar to gen_add_mult, but compute cost rather than generating + sequence. */ + static int iv_add_mult_cost (b, m, a, reg) rtx b; /* initial value of basic induction variable */ @@ -6929,7 +6997,7 @@ iv_add_mult_cost (b, m, a, reg) rtx last, result; start_sequence (); - result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0); + result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1); if (reg != result) emit_move_insn (reg, result); last = get_last_insn (); @@ -7517,8 +7585,7 @@ check_dbra_loop (loop, insn_count) if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare)) || ! bl->init_insn || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn)) - emit_insn_after (gen_move_insn (reg, final_value), - loop_end); + loop_insn_sink (loop, gen_move_insn (reg, final_value)); /* Delete compare/branch at end of loop. */ delete_insn (PREV_INSN (loop_end)); @@ -7630,17 +7697,16 @@ maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count) { struct loop_ivs *ivs = LOOP_IVS (loop); rtx reg = bl->biv->dest_reg; - rtx loop_start = loop->start; - rtx loop_end = loop->end; rtx p; /* Scan all insns in the loop, stopping if we find one that uses the biv in a way that we cannot eliminate. */ - for (p = loop_start; p != loop_end; p = NEXT_INSN (p)) + for (p = loop->start; p != loop->end; p = NEXT_INSN (p)) { enum rtx_code code = GET_CODE (p); - rtx where = threshold >= insn_count ? loop_start : p; + basic_block where_bb = 0; + rtx where_insn = threshold >= insn_count ? 0 : p; /* If this is a libcall that sets a giv, skip ahead to its end. */ if (GET_RTX_CLASS (code) == 'i') @@ -7666,7 +7732,7 @@ maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count) if ((code == INSN || code == JUMP_INSN || code == CALL_INSN) && reg_mentioned_p (reg, PATTERN (p)) && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl, - eliminate_p, where)) + eliminate_p, where_bb, where_insn)) { if (loop_dump_stream) fprintf (loop_dump_stream, @@ -7676,7 +7742,7 @@ maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count) } } - if (p == loop_end) + if (p == loop->end) { if (loop_dump_stream) fprintf (loop_dump_stream, "biv %d %s eliminated.\n", @@ -7748,18 +7814,20 @@ biv_elimination_giv_has_0_offset (biv, giv, insn) If BIV does not appear in X, return 1. - If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates - where extra insns should be added. Depending on how many items have been - moved out of the loop, it will either be before INSN or at the start of - the loop. */ + If ELIMINATE_P is non-zero, actually do the elimination. + WHERE_INSN/WHERE_BB indicate where extra insns should be added. + Depending on how many items have been moved out of the loop, it + will either be before INSN (when WHERE_INSN is non-zero) or at the + start of the loop (when WHERE_INSN is zero). */ static int -maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where) +maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where_bb, where_insn) const struct loop *loop; rtx x, insn; struct iv_class *bl; int eliminate_p; - rtx where; + basic_block where_bb; + rtx where_insn; { enum rtx_code code = GET_CODE (x); rtx reg = bl->biv->dest_reg; @@ -7870,7 +7938,7 @@ maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where) tem = gen_reg_rtx (GET_MODE (v->new_reg)); emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)), - where); + where_insn); /* Substitute the new register for its invariant value in the compare expression. */ @@ -7936,7 +8004,9 @@ maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where) { /* Otherwise, load it into a register. */ tem = gen_reg_rtx (mode); - emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where); + loop_iv_add_mult_emit_before (loop, arg, + v->mult_val, v->add_val, + tem, where_bb, where_insn); validate_change (insn, &XEXP (x, arg_operand), tem, 1); } if (apply_change_group ()) @@ -7969,7 +8039,9 @@ maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where) v->new_reg, 1); /* Compute value to compare against. */ - emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where); + loop_iv_add_mult_emit_before (loop, arg, + v->mult_val, v->add_val, + tem, where_bb, where_insn); /* Use it in this insn. */ validate_change (insn, &XEXP (x, arg_operand), tem, 1); if (apply_change_group ()) @@ -8005,8 +8077,9 @@ maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where) v->new_reg, 1); /* Compute value to compare against. */ - emit_iv_add_mult (arg, v->mult_val, v->add_val, - tem, where); + loop_iv_add_mult_emit_before (loop, arg, + v->mult_val, v->add_val, + tem, where_bb, where_insn); validate_change (insn, &XEXP (x, arg_operand), tem, 1); if (apply_change_group ()) return 1; @@ -8087,14 +8160,14 @@ maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where) { case 'e': if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl, - eliminate_p, where)) + eliminate_p, where_bb, where_insn)) return 0; break; case 'E': for (j = XVECLEN (x, i) - 1; j >= 0; j--) if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl, - eliminate_p, where)) + eliminate_p, where_bb, where_insn)) return 0; break; } @@ -8152,7 +8225,7 @@ record_initial (dest, set, data) /* If any of the registers in X are "old" and currently have a last use earlier than INSN, update them to have a last use of INSN. Their actual last use will be the previous insn but it will not have a valid uid_luid so we can't - use it. */ + use it. X must be a source expression only. */ static void update_reg_last_use (x, insn) @@ -8162,11 +8235,15 @@ update_reg_last_use (x, insn) /* Check for the case where INSN does not have a valid luid. In this case, there is no need to modify the regno_last_uid, as this can only happen when code is inserted after the loop_end to set a pseudo's final value, - and hence this insn will never be the last use of x. */ + and hence this insn will never be the last use of x. + ???? This comment is not correct. See for example loop_givs_reduce. + This may insert an insn before another new insn. */ if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop && INSN_UID (insn) < max_uid_for_loop && REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn)) - REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn); + { + REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn); + } else { register int i, j; @@ -9360,6 +9437,20 @@ replace_label (x, data) return 0; } +/* Emit insn for PATTERN after WHERE_INSN in basic block WHERE_BB + (ignored in the interim). */ + +static rtx +loop_insn_emit_after (loop, where_bb, where_insn, pattern) + const struct loop *loop ATTRIBUTE_UNUSED; + basic_block where_bb ATTRIBUTE_UNUSED; + rtx where_insn; + rtx pattern; +{ + return emit_insn_after (pattern, where_insn); +} + + /* If WHERE_INSN is non-zero emit insn for PATTERN before WHERE_INSN in basic block WHERE_BB (ignored in the interim) within the loop otherwise hoist PATTERN into the loop pre-header. */ @@ -9386,6 +9477,34 @@ loop_insn_hoist (loop, pattern) { return loop_insn_emit_before (loop, 0, loop->start, pattern); } + + +/* Sink insn for PATTERN after the loop end. */ + +rtx +loop_insn_sink (loop, pattern) + const struct loop *loop; + rtx pattern; +{ + return loop_insn_emit_before (loop, 0, loop->sink, pattern); +} + + +/* If the loop has multiple exits, emit insn for PATTERN before the + loop to ensure that it will always be executed no matter how the + loop exits. Otherwise, emit the insn for PATTERN after the loop, + since this is slightly more efficient. */ + +static rtx +loop_insn_sink_or_swim (loop, pattern) + const struct loop *loop; + rtx pattern; +{ + if (loop->exit_count) + return loop_insn_hoist (loop, pattern); + else + return loop_insn_sink (loop, pattern); +} static void loop_biv_dump (v, file, verbose) @@ -19,6 +19,9 @@ the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include "bitmap.h" +#include "sbitmap.h" +#include "hard-reg-set.h" +#include "basic-block.h" /* Flags passed to loop_optimize. */ #define LOOP_UNROLL 1 @@ -386,11 +389,15 @@ extern FILE *loop_dump_stream; unroll.c. */ int loop_invariant_p PARAMS ((const struct loop *, rtx)); rtx get_condition_for_loop PARAMS ((const struct loop *, rtx)); -void emit_iv_add_mult PARAMS ((rtx, rtx, rtx, rtx, rtx)); +void loop_iv_add_mult_hoist PARAMS ((const struct loop *, rtx, rtx, rtx, rtx)); +void loop_iv_add_mult_sink PARAMS ((const struct loop *, rtx, rtx, rtx, rtx)); +void loop_iv_add_mult_emit_before PARAMS ((const struct loop *, rtx, + rtx, rtx, rtx, + basic_block, rtx)); rtx express_from PARAMS ((struct induction *, struct induction *)); rtx extend_value_for_giv PARAMS ((struct induction *, rtx)); -void unroll_loop PARAMS ((struct loop *, int, rtx, int)); +void unroll_loop PARAMS ((struct loop *, int, int)); rtx biv_total_increment PARAMS ((struct iv_class *)); unsigned HOST_WIDE_INT loop_iterations PARAMS ((struct loop *)); int precondition_loop_p PARAMS ((const struct loop *, @@ -404,6 +411,7 @@ int back_branch_in_range_p PARAMS ((const struct loop *, rtx)); int loop_insn_first_p PARAMS ((rtx, rtx)); typedef rtx (*loop_insn_callback) PARAMS ((struct loop *, rtx, int, int)); void for_each_insn_in_loop PARAMS ((struct loop *, loop_insn_callback)); +rtx loop_insn_sink PARAMS((const struct loop *, rtx)); rtx loop_insn_hoist PARAMS((const struct loop *, rtx)); /* Forward declarations for non-static functions declared in doloop.c. */ diff --git a/gcc/unroll.c b/gcc/unroll.c index bdd6cb4..fbd5224 100644 --- a/gcc/unroll.c +++ b/gcc/unroll.c @@ -206,7 +206,7 @@ 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, rtx, int)); + enum unroll_types, int)); static int find_splittable_givs PARAMS ((const struct loop *, struct iv_class *, enum unroll_types, rtx, int)); @@ -222,19 +222,16 @@ 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 and INSN_COUNT. - 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. + 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, insn_count, end_insert_before, strength_reduce_p) +unroll_loop (loop, insn_count, strength_reduce_p) struct loop *loop; int insn_count; - rtx end_insert_before; int strength_reduce_p; { struct loop_info *loop_info = LOOP_INFO (loop); @@ -1045,7 +1042,7 @@ unroll_loop (loop, insn_count, end_insert_before, strength_reduce_p) 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, @@ -1163,8 +1160,7 @@ unroll_loop (loop, insn_count, end_insert_before, strength_reduce_p) if (splitting_not_safe) temp = 0; else - temp = find_splittable_regs (loop, unroll_type, - end_insert_before, unroll_number); + 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 @@ -2431,10 +2427,9 @@ biv_total_increment (bl) times, since multiplies by small integers (1,2,3,4) are very cheap. */ static int -find_splittable_regs (loop, unroll_type, end_insert_before, unroll_number) +find_splittable_regs (loop, unroll_type, unroll_number) const struct loop *loop; enum unroll_types unroll_type; - rtx end_insert_before; int unroll_number; { struct loop_ivs *ivs = LOOP_IVS (loop); @@ -2444,8 +2439,6 @@ find_splittable_regs (loop, unroll_type, end_insert_before, unroll_number) rtx biv_final_value; int biv_splittable; int result = 0; - rtx loop_start = loop->start; - rtx loop_end = loop->end; for (bl = ivs->list; bl; bl = bl->next) { @@ -2469,7 +2462,7 @@ find_splittable_regs (loop, unroll_type, end_insert_before, unroll_number) biv_final_value = 0; if (unroll_type != UNROLL_COMPLETELY && (loop->exit_count || unroll_type == UNROLL_NAIVE) - && (REGNO_LAST_LUID (bl->regno) >= INSN_LUID (loop_end) + && (REGNO_LAST_LUID (bl->regno) >= INSN_LUID (loop->end) || ! bl->init_insn || INSN_UID (bl->init_insn) >= max_uid_for_loop || (REGNO_FIRST_LUID (bl->regno) @@ -2512,8 +2505,8 @@ find_splittable_regs (loop, unroll_type, end_insert_before, unroll_number) 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, @@ -2558,9 +2551,8 @@ find_splittable_regs (loop, unroll_type, end_insert_before, unroll_number) how the loop exits. Otherwise emit the insn after the loop, since this is slightly more efficient. */ if (! loop->exit_count) - emit_insn_before (gen_move_insn (bl->biv->src_reg, - biv_final_value), - end_insert_before); + 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 @@ -2571,11 +2563,9 @@ find_splittable_regs (loop, unroll_type, end_insert_before, unroll_number) 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", @@ -2717,9 +2707,8 @@ find_splittable_givs (loop, bl, unroll_type, increment, unroll_number) 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", @@ -2752,8 +2741,7 @@ find_splittable_givs (loop, bl, unroll_type, increment, unroll_number) 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); @@ -2795,8 +2783,8 @@ find_splittable_givs (loop, bl, unroll_type, increment, unroll_number) { 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; } @@ -2923,17 +2911,15 @@ find_splittable_givs (loop, bl, unroll_type, increment, unroll_number) 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); + 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. */ + We must calculate it from NEW_REG. */ delete_insn (PREV_INSN (loop->start)); start_sequence (); @@ -2942,7 +2928,7 @@ find_splittable_givs (loop, bl, unroll_type, increment, unroll_number) 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, @@ -3140,7 +3126,6 @@ final_biv_value (loop, bl) const struct loop *loop; struct iv_class *bl; { - rtx loop_end = loop->end; unsigned HOST_WIDE_INT n_iterations = LOOP_INFO (loop)->n_iterations; rtx increment, tem; @@ -3182,11 +3167,8 @@ final_biv_value (loop, bl) 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, @@ -3222,7 +3204,7 @@ final_giv_value (loop, v) 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; @@ -3279,15 +3261,13 @@ final_giv_value (loop, v) 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 (v->mode); record_base_value (REGNO (tem), bl->biv->add_val, 0); - emit_iv_add_mult (extend_value_for_giv (v, increment), - GEN_INT (n_iterations), - extend_value_for_giv (v, 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; @@ -3304,12 +3284,12 @@ final_giv_value (loop, v) 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, |