diff options
author | obrien <obrien@FreeBSD.org> | 2002-02-01 18:16:02 +0000 |
---|---|---|
committer | obrien <obrien@FreeBSD.org> | 2002-02-01 18:16:02 +0000 |
commit | c9ab9ae440a8066b2c2b85b157b1fdadcf09916a (patch) | |
tree | 086d9d6c8fbd4fc8fe4495059332f66bc0f8d12b /contrib/gcc/doloop.c | |
parent | 2ecfd8bd04b63f335c1ec6295740a4bfd97a4fa6 (diff) | |
download | FreeBSD-src-c9ab9ae440a8066b2c2b85b157b1fdadcf09916a.zip FreeBSD-src-c9ab9ae440a8066b2c2b85b157b1fdadcf09916a.tar.gz |
Enlist the FreeBSD-CURRENT users as testers of what is to become Gcc 3.1.0.
These bits are taken from the FSF anoncvs repo on 1-Feb-2002 08:20 PST.
Diffstat (limited to 'contrib/gcc/doloop.c')
-rw-r--r-- | contrib/gcc/doloop.c | 907 |
1 files changed, 907 insertions, 0 deletions
diff --git a/contrib/gcc/doloop.c b/contrib/gcc/doloop.c new file mode 100644 index 0000000..6c0185c --- /dev/null +++ b/contrib/gcc/doloop.c @@ -0,0 +1,907 @@ +/* Perform doloop optimizations + Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc. + Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz) + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#include "config.h" +#include "system.h" +#include "rtl.h" +#include "flags.h" +#include "expr.h" +#include "loop.h" +#include "hard-reg-set.h" +#include "basic-block.h" +#include "toplev.h" +#include "tm_p.h" + + +/* This module is used to modify loops with a determinable number of + iterations to use special low-overhead looping instructions. + + It first validates whether the loop is well behaved and has a + determinable number of iterations (either at compile or run-time). + It then modifies the loop to use a low-overhead looping pattern as + follows: + + 1. A pseudo register is allocated as the loop iteration counter. + + 2. The number of loop iterations is calculated and is stored + in the loop counter. + + 3. At the end of the loop, the jump insn is replaced by the + doloop_end pattern. The compare must remain because it might be + used elsewhere. If the loop-variable or condition register are + used elsewhere, they will be eliminated by flow. + + 4. An optional doloop_begin pattern is inserted at the top of the + loop. +*/ + + +#ifdef HAVE_doloop_end + +static rtx doloop_condition_get + PARAMS ((rtx)); +static unsigned HOST_WIDE_INT doloop_iterations_max + PARAMS ((const struct loop_info *, enum machine_mode, int)); +static int doloop_valid_p + PARAMS ((const struct loop *, rtx)); +static int doloop_modify + PARAMS ((const struct loop *, rtx, rtx, rtx, rtx, rtx)); +static int doloop_modify_runtime + PARAMS ((const struct loop *, rtx, rtx, rtx, enum machine_mode, rtx)); + + +/* Return the loop termination condition for PATTERN or zero + if it is not a decrement and branch jump insn. */ +static rtx +doloop_condition_get (pattern) + rtx pattern; +{ + rtx cmp; + rtx inc; + rtx reg; + rtx condition; + + /* The canonical doloop pattern we expect is: + + (parallel [(set (pc) (if_then_else (condition) + (label_ref (label)) + (pc))) + (set (reg) (plus (reg) (const_int -1))) + (additional clobbers and uses)]) + + Some machines (IA-64) make the decrement conditional on + the condition as well, so we don't bother verifying the + actual decrement. In summary, the branch must be the + first entry of the parallel (also required by jump.c), + and the second entry of the parallel must be a set of + the loop counter register. */ + + if (GET_CODE (pattern) != PARALLEL) + return 0; + + cmp = XVECEXP (pattern, 0, 0); + inc = XVECEXP (pattern, 0, 1); + + /* Check for (set (reg) (something)). */ + if (GET_CODE (inc) != SET || ! REG_P (SET_DEST (inc))) + return 0; + + /* Extract loop counter register. */ + reg = SET_DEST (inc); + + /* Check for (set (pc) (if_then_else (condition) + (label_ref (label)) + (pc))). */ + if (GET_CODE (cmp) != SET + || SET_DEST (cmp) != pc_rtx + || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE + || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF + || XEXP (SET_SRC (cmp), 2) != pc_rtx) + return 0; + + /* Extract loop termination condition. */ + condition = XEXP (SET_SRC (cmp), 0); + + if ((GET_CODE (condition) != GE && GET_CODE (condition) != NE) + || GET_CODE (XEXP (condition, 1)) != CONST_INT) + return 0; + + if (XEXP (condition, 0) == reg) + return condition; + + if (GET_CODE (XEXP (condition, 0)) == PLUS + && XEXP (XEXP (condition, 0), 0) == reg) + return condition; + + /* ??? If a machine uses a funny comparison, we could return a + canonicalised form here. */ + + return 0; +} + + +/* Return an estimate of the maximum number of loop iterations for the + loop specified by LOOP or zero if the loop is not normal. + MODE is the mode of the iteration count and NONNEG is non-zero if + the iteration count has been proved to be non-negative. */ +static unsigned HOST_WIDE_INT +doloop_iterations_max (loop_info, mode, nonneg) + const struct loop_info *loop_info; + enum machine_mode mode; + int nonneg; +{ + unsigned HOST_WIDE_INT n_iterations_max; + enum rtx_code code; + rtx min_value; + rtx max_value; + HOST_WIDE_INT abs_inc; + int neg_inc; + + neg_inc = 0; + abs_inc = INTVAL (loop_info->increment); + if (abs_inc < 0) + { + abs_inc = -abs_inc; + neg_inc = 1; + } + + if (neg_inc) + { + code = swap_condition (loop_info->comparison_code); + min_value = loop_info->final_equiv_value; + max_value = loop_info->initial_equiv_value; + } + else + { + code = loop_info->comparison_code; + min_value = loop_info->initial_equiv_value; + max_value = loop_info->final_equiv_value; + } + + /* Since the loop has a VTOP, we know that the initial test will be + true and thus the value of max_value should be greater than the + value of min_value. Thus the difference should always be positive + and the code must be LT, LE, LTU, LEU, or NE. Otherwise the loop is + not normal, e.g., `for (i = 0; i < 10; i--)'. */ + switch (code) + { + case LTU: + case LEU: + { + unsigned HOST_WIDE_INT umax; + unsigned HOST_WIDE_INT umin; + + if (GET_CODE (min_value) == CONST_INT) + umin = INTVAL (min_value); + else + umin = 0; + + if (GET_CODE (max_value) == CONST_INT) + umax = INTVAL (max_value); + else + umax = ((unsigned) 2 << (GET_MODE_BITSIZE (mode) - 1)) - 1; + + n_iterations_max = umax - umin; + break; + } + + case LT: + case LE: + { + HOST_WIDE_INT smax; + HOST_WIDE_INT smin; + + if (GET_CODE (min_value) == CONST_INT) + smin = INTVAL (min_value); + else + smin = -((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)); + + if (GET_CODE (max_value) == CONST_INT) + smax = INTVAL (max_value); + else + smax = ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)) - 1; + + n_iterations_max = smax - smin; + break; + } + + case NE: + if (GET_CODE (min_value) == CONST_INT + && GET_CODE (max_value) == CONST_INT) + n_iterations_max = INTVAL (max_value) - INTVAL (min_value); + else + /* We need to conservatively assume that we might have the maximum + number of iterations without any additional knowledge. */ + n_iterations_max = ((unsigned) 2 << (GET_MODE_BITSIZE (mode) - 1)) - 1; + break; + + default: + return 0; + } + + n_iterations_max /= abs_inc; + + /* If we know that the iteration count is non-negative then adjust + n_iterations_max if it is so large that it appears negative. */ + if (nonneg + && n_iterations_max > ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1))) + n_iterations_max = ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)) - 1; + + return n_iterations_max; +} + + +/* Return non-zero if the loop specified by LOOP is suitable for + the use of special low-overhead looping instructions. */ +static int +doloop_valid_p (loop, jump_insn) + const struct loop *loop; + rtx jump_insn; +{ + const struct loop_info *loop_info = LOOP_INFO (loop); + + /* The loop must have a conditional jump at the end. */ + if (! any_condjump_p (jump_insn) + || ! onlyjump_p (jump_insn)) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Invalid jump at loop end.\n"); + return 0; + } + + /* Give up if a loop has been completely unrolled. */ + if (loop_info->n_iterations == loop_info->unroll_number) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Loop completely unrolled.\n"); + return 0; + } + + /* The loop must have a single exit target. A break or return + statement within a loop will generate multiple loop exits. + Another example of a loop that currently generates multiple exit + targets is for (i = 0; i < (foo ? 8 : 4); i++) { }. */ + if (loop_info->has_multiple_exit_targets || loop->exit_count) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Loop has multiple exit targets.\n"); + return 0; + } + + /* An indirect jump may jump out of the loop. */ + if (loop_info->has_indirect_jump) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Indirect jump in function.\n"); + return 0; + } + + /* A called function may clobber any special registers required for + low-overhead looping. */ + if (loop_info->has_call) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Function call in loop.\n"); + return 0; + } + + /* Some targets (eg, PPC) use the count register for branch on table + instructions. ??? This should be a target specific check. */ + if (loop_info->has_tablejump) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Computed branch in the loop.\n"); + return 0; + } + + if (! loop_info->increment) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Could not determine iteration info.\n"); + return 0; + } + + if (GET_CODE (loop_info->increment) != CONST_INT) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Increment not an integer constant.\n"); + return 0; + } + + /* There is no guarantee that a NE loop will terminate if the + absolute increment is not unity. ??? We could compute this + condition at run-time and have an additional jump around the loop + to ensure an infinite loop. */ + if (loop_info->comparison_code == NE + && INTVAL (loop_info->increment) != -1 + && INTVAL (loop_info->increment) != 1) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: NE loop with non-unity increment.\n"); + return 0; + } + + /* Check for loops that may not terminate under special conditions. */ + if (! loop_info->n_iterations + && ((loop_info->comparison_code == LEU + && INTVAL (loop_info->increment) > 0) + || (loop_info->comparison_code == GEU + && INTVAL (loop_info->increment) < 0) + || (loop_info->comparison_code == LTU + && INTVAL (loop_info->increment) > 1) + || (loop_info->comparison_code == GTU + && INTVAL (loop_info->increment) < -1))) + { + /* If the comparison is LEU and the comparison value is UINT_MAX + then the loop will not terminate. Similarly, if the + comparison code is GEU and the initial value is 0, the loop + will not terminate. + + If the absolute increment is not 1, the loop can be infinite + even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2) + + Note that with LE and GE, the loop behaviour is undefined + (C++ standard section 5 clause 5) if an overflow occurs, say + between INT_MAX and INT_MAX + 1. We thus don't have to worry + about these two cases. + + ??? We could compute these conditions at run-time and have a + additional jump around the loop to ensure an infinite loop. + However, it is very unlikely that this is the intended + behaviour of the loop and checking for these rare boundary + conditions would pessimize all other code. + + If the loop is executed only a few times an extra check to + restart the loop could use up most of the benefits of using a + count register loop. Note however, that normally, this + restart branch would never execute, so it could be predicted + well by the CPU. We should generate the pessimistic code by + default, and have an option, e.g. -funsafe-loops that would + enable count-register loops in this case. */ + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Possible infinite iteration case ignored.\n"); + } + + return 1; +} + + +/* Modify the loop to use the low-overhead looping insn where LOOP + describes the loop, ITERATIONS is an RTX containing the desired + number of loop iterations, ITERATIONS_MAX is a CONST_INT specifying + the maximum number of loop iterations, and DOLOOP_INSN is the + low-overhead looping insn to emit at the end of the loop. This + returns non-zero if it was successful. */ +static int +doloop_modify (loop, iterations, iterations_max, + doloop_seq, start_label, condition) + const struct loop *loop; + rtx iterations; + rtx iterations_max; + rtx doloop_seq; + rtx start_label; + rtx condition; +{ + rtx counter_reg; + rtx count; + rtx sequence; + rtx jump_insn; + int nonneg = 0; + int decrement_count; + + jump_insn = prev_nonnote_insn (loop->end); + + if (loop_dump_stream) + { + fprintf (loop_dump_stream, "Doloop: Inserting doloop pattern ("); + if (GET_CODE (iterations) == CONST_INT) + fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, + INTVAL (iterations)); + else + fputs ("runtime", loop_dump_stream); + fputs (" iterations).", loop_dump_stream); + } + + /* Emit the label that will delimit the top of the loop. + This has to be done before the delete_insn call below, to prevent + delete_insn from deleting too much. */ + emit_label_after (start_label, loop->top ? loop->top : loop->start); + LABEL_NUSES (start_label)++; + + /* Discard original jump to continue loop. The original compare + result may still be live, so it cannot be discarded explicitly. */ + delete_related_insns (jump_insn); + + counter_reg = XEXP (condition, 0); + if (GET_CODE (counter_reg) == PLUS) + counter_reg = XEXP (counter_reg, 0); + + start_sequence (); + + count = iterations; + decrement_count = 0; + switch (GET_CODE (condition)) + { + case NE: + /* Currently only NE tests against zero and one are supported. */ + if (XEXP (condition, 1) == const0_rtx) + decrement_count = 1; + else if (XEXP (condition, 1) != const1_rtx) + abort (); + break; + + case GE: + /* Currently only GE tests against zero are supported. */ + if (XEXP (condition, 1) != const0_rtx) + abort (); + + /* The iteration count needs decrementing for a GE test. */ + decrement_count = 1; + + /* Determine if the iteration counter will be non-negative. + Note that the maximum value loaded is iterations_max - 1. */ + if ((unsigned HOST_WIDE_INT) INTVAL (iterations_max) + <= ((unsigned) 1 << (GET_MODE_BITSIZE (GET_MODE (counter_reg)) - 1))) + nonneg = 1; + break; + + /* Abort if an invalid doloop pattern has been generated. */ + default: + abort (); + } + + if (decrement_count) + { + if (GET_CODE (count) == CONST_INT) + count = GEN_INT (INTVAL (count) - 1); + else + count = expand_simple_binop (GET_MODE (counter_reg), MINUS, + count, GEN_INT (1), + 0, 0, OPTAB_LIB_WIDEN); + } + + /* Insert initialization of the count register into the loop header. */ + convert_move (counter_reg, count, 1); + sequence = gen_sequence (); + end_sequence (); + emit_insn_before (sequence, loop->start); + + /* Some targets (eg, C4x) need to initialize special looping + registers. */ +#ifdef HAVE_doloop_begin + { + rtx init; + + init = gen_doloop_begin (counter_reg, + GET_CODE (iterations) == CONST_INT + ? iterations : const0_rtx, iterations_max, + GEN_INT (loop->level)); + if (init) + { + start_sequence (); + emit_insn (init); + sequence = gen_sequence (); + end_sequence (); + emit_insn_after (sequence, loop->start); + } + } +#endif + + /* Insert the new low-overhead looping insn. */ + emit_jump_insn_before (doloop_seq, loop->end); + jump_insn = prev_nonnote_insn (loop->end); + JUMP_LABEL (jump_insn) = start_label; + + /* Add a REG_NONNEG note if the actual or estimated maximum number + of iterations is non-negative. */ + if (nonneg) + { + REG_NOTES (jump_insn) + = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX, REG_NOTES (jump_insn)); + } + return 1; +} + + +/* Handle the more complex case, where the bounds are not known at + compile time. In this case we generate a run_time calculation of + the number of iterations. We rely on the existence of a run-time + guard to ensure that the loop executes at least once, i.e., + initial_value obeys the loop comparison condition. If a guard is + not present, we emit one. The loop to modify is described by LOOP. + ITERATIONS_MAX is a CONST_INT specifying the estimated maximum + number of loop iterations. DOLOOP_INSN is the low-overhead looping + insn to insert. Returns non-zero if loop successfully modified. */ +static int +doloop_modify_runtime (loop, iterations_max, + doloop_seq, start_label, mode, condition) + const struct loop *loop; + rtx iterations_max; + rtx doloop_seq; + rtx start_label; + enum machine_mode mode; + rtx condition; +{ + const struct loop_info *loop_info = LOOP_INFO (loop); + HOST_WIDE_INT abs_inc; + int neg_inc; + rtx diff; + rtx sequence; + rtx iterations; + rtx initial_value; + rtx final_value; + rtx increment; + int unsigned_p; + enum rtx_code comparison_code; + + increment = loop_info->increment; + initial_value = loop_info->initial_value; + final_value = loop_info->final_value; + + neg_inc = 0; + abs_inc = INTVAL (increment); + if (abs_inc < 0) + { + abs_inc = -abs_inc; + neg_inc = 1; + } + + comparison_code = loop_info->comparison_code; + unsigned_p = (comparison_code == LTU + || comparison_code == LEU + || comparison_code == GTU + || comparison_code == GEU + || comparison_code == NE); + + /* The number of iterations (prior to any loop unrolling) is given by: + + n = (abs (final - initial) + abs_inc - 1) / abs_inc. + + However, it is possible for the summation to overflow, and a + safer method is: + + n = abs (final - initial) / abs_inc; + n += (abs (final - initial) % abs_inc) != 0; + + If the loop has been unrolled, then the loop body has been + preconditioned to iterate a multiple of unroll_number times. If + abs_inc is != 1, the full calculation is + + t1 = abs_inc * unroll_number; + n = abs (final - initial) / t1; + n += (abs (final - initial) % t1) > t1 - abs_inc; + + The division and modulo operations can be avoided by requiring + that the increment is a power of 2 (precondition_loop_p enforces + this requirement). Nevertheless, the RTX_COSTS should be checked + to see if a fast divmod is available. */ + + start_sequence (); + /* abs (final - initial) */ + diff = expand_simple_binop (mode, MINUS, + copy_rtx (neg_inc ? initial_value : final_value), + copy_rtx (neg_inc ? final_value : initial_value), + NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN); + + /* Some code transformations can result in code akin to + + tmp = i + 1; + ... + goto scan_start; + top: + tmp = tmp + 1; + scan_start: + i = tmp; + if (i < n) goto top; + + We'll have already detected this form of loop in scan_loop, + and set loop->top and loop->scan_start appropriately. + + In this situation, we skip the increment the first time through + the loop, which results in an incorrect estimate of the number + of iterations. Adjust the difference to compensate. */ + /* ??? Logically, it would seem this belongs in loop_iterations. + However, this causes regressions e.g. on x86 execute/20011008-3.c, + so I do not believe we've properly characterized the exact nature + of the problem. In the meantime, this fixes execute/20011126-2.c + on ia64 and some Ada front end miscompilation on ppc. */ + + if (loop->scan_start) + { + rtx iteration_var = loop_info->iteration_var; + struct loop_ivs *ivs = LOOP_IVS (loop); + struct iv_class *bl; + + if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT) + bl = REG_IV_CLASS (ivs, REGNO (iteration_var)); + else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT) + { + struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var)); + bl = REG_IV_CLASS (ivs, REGNO (v->src_reg)); + } + else + /* Iteration var must be an induction variable to get here. */ + abort (); + + if (INSN_UID (bl->biv->insn) < max_uid_for_loop + && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start)) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Basic induction var skips initial incr.\n"); + + diff = expand_simple_binop (mode, PLUS, diff, increment, diff, + unsigned_p, OPTAB_LIB_WIDEN); + } + } + + if (abs_inc * loop_info->unroll_number != 1) + { + int shift_count; + rtx extra; + rtx label; + unsigned HOST_WIDE_INT limit; + + shift_count = exact_log2 (abs_inc * loop_info->unroll_number); + if (shift_count < 0) + abort (); + + /* abs (final - initial) / (abs_inc * unroll_number) */ + iterations = expand_simple_binop (GET_MODE (diff), LSHIFTRT, + diff, GEN_INT (shift_count), + NULL_RTX, 1, + OPTAB_LIB_WIDEN); + + if (abs_inc != 1) + { + /* abs (final - initial) % (abs_inc * unroll_number) */ + rtx count = GEN_INT (abs_inc * loop_info->unroll_number - 1); + extra = expand_simple_binop (GET_MODE (iterations), AND, + diff, count, NULL_RTX, 1, + OPTAB_LIB_WIDEN); + + /* If (abs (final - initial) % (abs_inc * unroll_number) + <= abs_inc * (unroll - 1)), + jump past following increment instruction. */ + label = gen_label_rtx (); + limit = abs_inc * (loop_info->unroll_number - 1); + emit_cmp_and_jump_insns (extra, GEN_INT (limit), + limit == 0 ? EQ : LEU, NULL_RTX, + GET_MODE (extra), 0, label); + JUMP_LABEL (get_last_insn ()) = label; + LABEL_NUSES (label)++; + + /* Increment the iteration count by one. */ + iterations = expand_simple_binop (GET_MODE (iterations), PLUS, + iterations, GEN_INT (1), + iterations, 1, + OPTAB_LIB_WIDEN); + + emit_label (label); + } + } + else + iterations = diff; + + /* If there is a NOTE_INSN_LOOP_VTOP, we have a `for' or `while' + style loop, with a loop exit test at the start. Thus, we can + assume that the loop condition was true when the loop was + entered. + + `do-while' loops require special treatment since the exit test is + not executed before the start of the loop. We need to determine + if the loop will terminate after the first pass and to limit the + iteration count to one if necessary. */ + if (! loop->vtop) + { + rtx label; + + if (loop_dump_stream) + fprintf (loop_dump_stream, "Doloop: Do-while loop.\n"); + + /* A `do-while' loop must iterate at least once. If the + iteration count is bogus, we set the iteration count to 1. + Note that if the loop has been unrolled, then the loop body + is guaranteed to execute at least once. */ + if (loop_info->unroll_number == 1) + { + /* Emit insns to test if the loop will immediately + terminate and to set the iteration count to 1 if true. */ + label = gen_label_rtx(); + emit_cmp_and_jump_insns (copy_rtx (initial_value), + copy_rtx (loop_info->comparison_value), + comparison_code, NULL_RTX, mode, 0, + label); + JUMP_LABEL (get_last_insn ()) = label; + LABEL_NUSES (label)++; + emit_move_insn (iterations, const1_rtx); + emit_label (label); + } + } + + sequence = gen_sequence (); + end_sequence (); + emit_insn_before (sequence, loop->start); + + return doloop_modify (loop, iterations, iterations_max, doloop_seq, + start_label, condition); +} + + +/* This is the main entry point. Process loop described by LOOP + validating that the loop is suitable for conversion to use a low + overhead looping instruction, replacing the jump insn where + suitable. We distinguish between loops with compile-time bounds + and those with run-time bounds. Information from LOOP is used to + compute the number of iterations and to determine whether the loop + is a candidate for this optimization. Returns non-zero if loop + successfully modified. */ +int +doloop_optimize (loop) + const struct loop *loop; +{ + struct loop_info *loop_info = LOOP_INFO (loop); + rtx initial_value; + rtx final_value; + rtx increment; + rtx jump_insn; + enum machine_mode mode; + unsigned HOST_WIDE_INT n_iterations; + unsigned HOST_WIDE_INT n_iterations_max; + rtx doloop_seq, doloop_pat, doloop_reg; + rtx iterations; + rtx iterations_max; + rtx start_label; + rtx condition; + + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Processing loop %d, enclosed levels %d.\n", + loop->num, loop->level); + + jump_insn = prev_nonnote_insn (loop->end); + + /* Check that loop is a candidate for a low-overhead looping insn. */ + if (! doloop_valid_p (loop, jump_insn)) + return 0; + + /* Determine if the loop can be safely, and profitably, + preconditioned. While we don't precondition the loop in a loop + unrolling sense, this test ensures that the loop is well behaved + and that the increment is a constant integer. */ + if (! precondition_loop_p (loop, &initial_value, &final_value, + &increment, &mode)) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Cannot precondition loop.\n"); + return 0; + } + + /* Determine or estimate the maximum number of loop iterations. */ + n_iterations = loop_info->n_iterations; + if (n_iterations) + { + /* This is the simple case where the initial and final loop + values are constants. */ + n_iterations_max = n_iterations; + } + else + { + int nonneg = find_reg_note (jump_insn, REG_NONNEG, 0) != 0; + + /* This is the harder case where the initial and final loop + values may not be constants. */ + n_iterations_max = doloop_iterations_max (loop_info, mode, nonneg); + + if (! n_iterations_max) + { + /* We have something like `for (i = 0; i < 10; i--)'. */ + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Not normal loop.\n"); + return 0; + } + } + + /* Account for loop unrolling in the iteration count. This will + have no effect if loop_iterations could not determine the number + of iterations. */ + n_iterations /= loop_info->unroll_number; + n_iterations_max /= loop_info->unroll_number; + + if (n_iterations && n_iterations < 3) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Too few iterations (%ld) to be profitable.\n", + (long int) n_iterations); + return 0; + } + + iterations = GEN_INT (n_iterations); + iterations_max = GEN_INT (n_iterations_max); + + /* Generate looping insn. If the pattern FAILs then give up trying + to modify the loop since there is some aspect the back-end does + not like. */ + start_label = gen_label_rtx (); + doloop_reg = gen_reg_rtx (mode); + doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max, + GEN_INT (loop->level), start_label); + if (! doloop_seq && mode != word_mode) + { + PUT_MODE (doloop_reg, word_mode); + doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max, + GEN_INT (loop->level), start_label); + } + if (! doloop_seq) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Target unwilling to use doloop pattern!\n"); + return 0; + } + + /* A raw define_insn may yield a plain pattern. If a sequence + was involved, the last must be the jump instruction. */ + if (GET_CODE (doloop_seq) == SEQUENCE) + { + doloop_pat = XVECEXP (doloop_seq, 0, XVECLEN (doloop_seq, 0) - 1); + if (GET_CODE (doloop_pat) == JUMP_INSN) + doloop_pat = PATTERN (doloop_pat); + else + doloop_pat = NULL_RTX; + } + else + doloop_pat = doloop_seq; + + if (! doloop_pat + || ! (condition = doloop_condition_get (doloop_pat))) + { + if (loop_dump_stream) + fprintf (loop_dump_stream, + "Doloop: Unrecognizable doloop pattern!\n"); + return 0; + } + + if (n_iterations != 0) + /* Handle the simpler case, where we know the iteration count at + compile time. */ + return doloop_modify (loop, iterations, iterations_max, doloop_seq, + start_label, condition); + else + /* Handle the harder case, where we must add additional runtime tests. */ + return doloop_modify_runtime (loop, iterations_max, doloop_seq, + start_label, mode, condition); +} + +#endif /* HAVE_doloop_end */ |