/* Perform doloop optimizations
- Copyright (C) 1999, 2000 Free Software Foundation, Inc.
+ 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 GNU CC.
+This file is part of GCC.
-GNU CC 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 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.
-GNU CC 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.
+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 GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+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 "loop.h"
#include "hard-reg-set.h"
#include "basic-block.h"
+#include "toplev.h"
#include "tm_p.h"
/* 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 the iteration count has been proved to be non-negative. */
+ 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;
if (GET_CODE (max_value) == CONST_INT)
umax = INTVAL (max_value);
else
- umax = ((unsigned)2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
+ umax = ((unsigned) 2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
n_iterations_max = umax - umin;
break;
if (GET_CODE (min_value) == CONST_INT)
smin = INTVAL (min_value);
else
- smin = -((unsigned)1 << (GET_MODE_BITSIZE (mode) - 1));
+ 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;
+ smax = ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
n_iterations_max = smax - smin;
break;
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;
+ n_iterations_max = ((unsigned) 2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
break;
default:
/* 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;
+ && 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;
}
|| ! onlyjump_p (jump_insn))
{
if (loop_dump_stream)
- fprintf (loop_dump_stream,
+ fprintf (loop_dump_stream,
"Doloop: Invalid jump at loop end.\n");
return 0;
}
return 0;
}
- /* Some targets (eg, PPC) use the count register for branch on table
- instructions. ??? This should be a target specific check. */
+ /* 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)
/* 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 a additional jump around the loop
+ 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
&& ((loop_info->comparison_code == LEU
&& INTVAL (loop_info->increment) > 0)
|| (loop_info->comparison_code == GEU
- && INTVAL (loop_info->increment) < 0)))
+ && 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.
- Note that with LE and GE, the loop behaviour can be
- implementation dependent if an overflow occurs, say between
- INT_MAX and INT_MAX + 1. We thus don't have to worry about
- these two cases.
+ 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. */
+ 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");
/* Discard original jump to continue loop. The original compare
result may still be live, so it cannot be discarded explicitly. */
- delete_insn (jump_insn);
+ delete_related_insns (jump_insn);
counter_reg = XEXP (condition, 0);
if (GET_CODE (counter_reg) == PLUS)
/* 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)))
+ <= ((unsigned) 1 << (GET_MODE_BITSIZE (GET_MODE (counter_reg)) - 1)))
nonneg = 1;
break;
/* Abort if an invalid doloop pattern has been generated. */
default:
- abort();
+ abort ();
}
if (decrement_count)
if (GET_CODE (count) == CONST_INT)
count = GEN_INT (INTVAL (count) - 1);
else
- count = expand_binop (GET_MODE (counter_reg), sub_optab,
- count, GEN_INT (1),
- 0, 0, OPTAB_LIB_WIDEN);
+ 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 ();
+ sequence = get_insns ();
end_sequence ();
emit_insn_before (sequence, loop->start);
{
start_sequence ();
emit_insn (init);
- sequence = gen_sequence ();
+ sequence = get_insns ();
end_sequence ();
emit_insn_after (sequence, loop->start);
}
|| comparison_code == NE);
/* The number of iterations (prior to any loop unrolling) is given by:
- (abs (final - initial) + abs_inc - 1) / abs_inc.
+
+ n = (abs (final - initial) + abs_inc - 1) / abs_inc.
However, it is possible for the summation to overflow, and a
safer method is:
- abs (final - initial) / abs_inc + (abs (final - initial) % abs_inc) != 0
+ 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.
- The number of iterations of the loop body is simply:
- abs (final - initial) / (abs_inc * unroll_number).
+ 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
start_sequence ();
/* abs (final - initial) */
- diff = expand_binop (mode, sub_optab,
- copy_rtx (neg_inc ? initial_value : final_value),
- copy_rtx (neg_inc ? final_value : initial_value),
- NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
-
- if (loop_info->unroll_number == 1)
+ 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)
{
- if (abs_inc != 1)
+ 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)
{
- int shift_count;
- rtx extra;
- rtx label;
-
- shift_count = exact_log2 (abs_inc);
- if (shift_count < 0)
- abort ();
-
- /* abs (final - initial) / abs_inc */
- iterations = expand_binop (GET_MODE (diff), lshr_optab,
- diff, GEN_INT (shift_count),
- NULL_RTX, 1,
- OPTAB_LIB_WIDEN);
-
- /* abs (final - initial) % abs_inc */
- extra = expand_binop (GET_MODE (iterations), and_optab,
- diff, GEN_INT (abs_inc - 1),
- NULL_RTX, 1,
- OPTAB_LIB_WIDEN);
-
- /* If (abs (final - initial) % abs_inc == 0) jump past
- following increment instruction. */
- label = gen_label_rtx();
- emit_cmp_and_jump_insns (extra, const0_rtx, EQ, NULL_RTX,
- GET_MODE (extra), 0, 0, label);
- JUMP_LABEL (get_last_insn ()) = label;
- LABEL_NUSES (label)++;
+ 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 ();
- /* Increment the iteration count by one. */
- iterations = expand_binop (GET_MODE (iterations), add_optab,
- iterations, GEN_INT (1),
- iterations, 1,
- OPTAB_LIB_WIDEN);
+ 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");
- emit_label (label);
+ diff = expand_simple_binop (mode, PLUS, diff, increment, diff,
+ unsigned_p, OPTAB_LIB_WIDEN);
}
- else
- iterations = diff;
}
- else
+
+ if (abs_inc * loop_info->unroll_number != 1)
{
int shift_count;
+ rtx extra;
+ rtx label;
+ unsigned HOST_WIDE_INT limit;
- /* precondition_loop_p has preconditioned the loop so that the
- iteration count of the loop body is always a power of 2.
- Since we won't get an overflow calculating the loop count,
- the code we emit is simpler. */
- shift_count = exact_log2 (loop_info->unroll_number * abs_inc);
+ shift_count = exact_log2 (abs_inc * loop_info->unroll_number);
if (shift_count < 0)
abort ();
- iterations = expand_binop (GET_MODE (diff), lshr_optab,
- diff, GEN_INT (shift_count),
- NULL_RTX, 1,
- OPTAB_LIB_WIDEN);
- }
+ /* 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
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, 0,
+ comparison_code, NULL_RTX, mode, 0,
label);
JUMP_LABEL (get_last_insn ()) = label;
LABEL_NUSES (label)++;
}
}
- sequence = gen_sequence ();
+ sequence = get_insns ();
end_sequence ();
emit_insn_before (sequence, loop->start);
&increment, &mode))
{
if (loop_dump_stream)
- fprintf (loop_dump_stream,
+ fprintf (loop_dump_stream,
"Doloop: Cannot precondition loop.\n");
return 0;
}
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)
+ /* If multiple instructions were created, the last must be the
+ jump instruction. Also, a raw define_insn may yield a plain
+ pattern. */
+ doloop_pat = doloop_seq;
+ if (INSN_P (doloop_pat) && NEXT_INSN (doloop_pat) != NULL_RTX)
{
- doloop_pat = XVECEXP (doloop_seq, 0, XVECLEN (doloop_seq, 0) - 1);
- if (GET_CODE (doloop_pat) == JUMP_INSN)
- doloop_pat = PATTERN (doloop_pat);
- else
+ while (NEXT_INSN (doloop_pat) != NULL_RTX)
+ doloop_pat = NEXT_INSN (doloop_pat);
+ if (GET_CODE (doloop_pat) != JUMP_INSN)
doloop_pat = NULL_RTX;
}
- else
- doloop_pat = doloop_seq;
if (! doloop_pat
|| ! (condition = doloop_condition_get (doloop_pat)))
OSDN Git Service
