This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Allow more loops in check_ext_dependent_givs
- From: Ulrich Weigand <weigand at i1 dot informatik dot uni-erlangen dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 16 Jul 2003 19:21:47 +0200 (MET DST)
- Subject: [PATCH] Allow more loops in check_ext_dependent_givs
Hello,
on 64-bit platforms, in many cases strength reduction is not performed
due to the problem that the induction variable will have a smaller
bitsize than a derived GIV (e.g. 'int' indexing into an array).
There is currently support to handle these situations in the routine
check_ext_dependent_givs, but only for compile-time constant loop
bounds. The routine carries a ??? comment suggesting to extend
support to loops with increment +/- 1 and 'friendly' exit tests,
where it is provable that overflow cannot happen.
This patch implements this suggestion by allowing loops with
increment +1 and exit test < against a loop-invariant value,
and likewise loops with increment -1 and exit test > invariant.
Bootstrapped/regtested on s390-ibm-linux and s390x-ibm-linux.
OK?
ChangeLog:
* loop.c (check_ext_dependent_givs): Pass const struct loop *
instead of struct loop_info * as argument. Accept BIVs with
increment +/- 1 provided there is a friendly exit test against
a loop-invariant value.
(strength_reduce): Adapt call to check_ext_dependent_givs.
Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.463
diff -c -p -r1.463 loop.c
*** gcc/loop.c 11 Jul 2003 06:44:40 -0000 1.463
--- gcc/loop.c 16 Jul 2003 14:08:15 -0000
*************** static void record_giv (const struct loo
*** 293,299 ****
rtx, rtx, rtx, rtx, int, enum g_types, int, int,
rtx *);
static void update_giv_derive (const struct loop *, rtx);
! static void check_ext_dependent_givs (struct iv_class *, struct loop_info *);
static int basic_induction_var (const struct loop *, rtx, enum machine_mode,
rtx, rtx, rtx *, rtx *, rtx **);
static rtx simplify_giv_expr (const struct loop *, rtx, rtx *, int *);
--- 293,299 ----
rtx, rtx, rtx, rtx, int, enum g_types, int, int,
rtx *);
static void update_giv_derive (const struct loop *, rtx);
! static void check_ext_dependent_givs (const struct loop *, struct iv_class *);
static int basic_induction_var (const struct loop *, rtx, enum machine_mode,
rtx, rtx, rtx *, rtx *, rtx **);
static rtx simplify_giv_expr (const struct loop *, rtx, rtx *, int *);
*************** strength_reduce (struct loop *loop, int
*** 5143,5149 ****
/* Check each extension dependent giv in this class to see if its
root biv is safe from wrapping in the interior mode. */
! check_ext_dependent_givs (bl, loop_info);
/* Combine all giv's for this iv_class. */
combine_givs (regs, bl);
--- 5143,5149 ----
/* Check each extension dependent giv in this class to see if its
root biv is safe from wrapping in the interior mode. */
! check_ext_dependent_givs (loop, bl);
/* Combine all giv's for this iv_class. */
combine_givs (regs, bl);
*************** combine_givs_p (struct induction *g1, st
*** 7286,7293 ****
make the giv illegal. */
static void
! check_ext_dependent_givs (struct iv_class *bl, struct loop_info *loop_info)
{
int ze_ok = 0, se_ok = 0, info_ok = 0;
enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
HOST_WIDE_INT start_val;
--- 7286,7294 ----
make the giv illegal. */
static void
! check_ext_dependent_givs (const struct loop *loop, struct iv_class *bl)
{
+ struct loop_info *loop_info = LOOP_INFO (loop);
int ze_ok = 0, se_ok = 0, info_ok = 0;
enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
HOST_WIDE_INT start_val;
*************** check_ext_dependent_givs (struct iv_clas
*** 7298,7306 ****
/* Make sure the iteration data is available. We must have
constants in order to be certain of no overflow. */
- /* ??? An unknown iteration count with an increment of +-1
- combined with friendly exit tests of against an invariant
- value is also amenable to optimization. Not implemented. */
if (loop_info->n_iterations > 0
&& bl->initial_value
&& GET_CODE (bl->initial_value) == CONST_INT
--- 7299,7304 ----
*************** check_ext_dependent_givs (struct iv_clas
*** 7367,7372 ****
--- 7365,7401 ----
}
}
+ /* If we know the BIV is compared at run-time against an
+ invariant value, and the increment is +/- 1, we may also
+ be able to prove that the BIV cannot overflow. */
+ else if (bl->biv->src_reg == loop_info->iteration_var
+ && loop_info->comparison_value
+ && loop_invariant_p (loop, loop_info->comparison_value)
+ && (incr = biv_total_increment (bl))
+ && GET_CODE (incr) == CONST_INT)
+ {
+ /* If the increment is +1, and the exit test is a <,
+ the BIV cannot overflow. (For <=, we have the
+ problematic case that the comparison value might
+ be the maximum value of the range.) */
+ if (INTVAL (incr) == 1)
+ {
+ if (loop_info->comparison_code == LT)
+ se_ok = ze_ok = 1;
+ else if (loop_info->comparison_code == LTU)
+ ze_ok = 1;
+ }
+
+ /* Likewise for increment -1 and exit test >. */
+ if (INTVAL (incr) == -1)
+ {
+ if (loop_info->comparison_code == GT)
+ se_ok = ze_ok = 1;
+ else if (loop_info->comparison_code == GTU)
+ ze_ok = 1;
+ }
+ }
+
/* Invalidate givs that fail the tests. */
for (v = bl->giv; v; v = v->next_iv)
if (v->ext_dependent)
*************** check_ext_dependent_givs (struct iv_clas
*** 7388,7395 ****
signed or unsigned, so to safely truncate we must satisfy
both. The initial check here verifies the BIV itself;
once that is successful we may check its range wrt the
! derived GIV. */
! if (se_ok && ze_ok)
{
enum machine_mode outer_mode = GET_MODE (v->ext_dependent);
unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
--- 7417,7425 ----
signed or unsigned, so to safely truncate we must satisfy
both. The initial check here verifies the BIV itself;
once that is successful we may check its range wrt the
! derived GIV. This works only if we were able to determine
! constant start and end values above. */
! if (se_ok && ze_ok && info_ok)
{
enum machine_mode outer_mode = GET_MODE (v->ext_dependent);
unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
--
Dr. Ulrich Weigand
weigand@informatik.uni-erlangen.de