This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Unsafe givs & check_ext_dependent_givs


This patch splits out code from check_ext_dependent_givs so that
I can reuse it in a follow-up.

While doing this, I noticed that c_e_d_g only checks the value of
a biv at the start of an iteration.  For example:

  unsigned char i;
  int j;

  i = 0x10;
  for (j = 0; j < 0x10; j++)
    {
      i += 0xe8;
      x[i] = 0;
      i -= 0xe7;
    }

At the beginning of the loop body, "i" ranges from 0x10...0x1f.
But at the time "i" is used in x[i], it ranges from 0xf8...0x07.
Since c_e_d_g only checks the former, it thinks x[i] is a safe giv.

I couldn't decide which was better: reject the optimisation for
non-monotonic bivs, or try to handle them.  Patches for both attached.
The second is relative to the first.

Both versions were bootstrapped & regression tested on i686-pc-linux-gnu
and various mips targets.  They fix the test case on i686-pc-linux-gnu.
OK to install?

Richard

	* loop.c (get_monotonic_increment, biased_biv_fits_mode_p,
	biv_fits_mode_p, extension_within_bounds_p): New functions.
	(check_ext_dependent_givs): Use them.

Index: loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.470
diff -c -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.470 loop.c
*** loop.c	7 Sep 2003 05:21:35 -0000	1.470
--- loop.c	18 Sep 2003 11:28:25 -0000
*************** static void record_giv (const struct loo
*** 293,298 ****
--- 293,306 ----
  			rtx, rtx, rtx, rtx, int, enum g_types, int, int,
  			rtx *);
  static void update_giv_derive (const struct loop *, rtx);
+ static HOST_WIDE_INT get_monotonic_increment (struct iv_class *);
+ static bool biased_biv_fits_mode_p (const struct loop *, struct iv_class *,
+ 				    HOST_WIDE_INT, enum machine_mode,
+ 				    unsigned HOST_WIDE_INT);
+ static bool biv_fits_mode_p (const struct loop *, struct iv_class *,
+ 			     HOST_WIDE_INT, enum machine_mode, bool);
+ static bool extension_within_bounds_p (const struct loop *, struct iv_class *,
+ 				       HOST_WIDE_INT, 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 **);
*************** combine_givs_p (struct induction *g1, st
*** 7303,7308 ****
--- 7311,7483 ----
    return NULL_RTX;
  }
  
+ /* See if BL is monotonic and has a constant per-iteration increment.
+    Return the increment if so, otherwise return 0.  */
+ 
+ static HOST_WIDE_INT
+ get_monotonic_increment (struct iv_class *bl)
+ {
+   struct induction *v;
+   rtx incr;
+ 
+   /* Get the total increment and check that it is constant.  */
+   incr = biv_total_increment (bl);
+   if (incr == 0 || GET_CODE (incr) != CONST_INT)
+     return 0;
+ 
+   for (v = bl->biv; v != 0; v = v->next_iv)
+     {
+       if (GET_CODE (v->add_val) != CONST_INT)
+ 	return 0;
+ 
+       if (INTVAL (v->add_val) < 0 && INTVAL (incr) >= 0)
+ 	return 0;
+ 
+       if (INTVAL (v->add_val) > 0 && INTVAL (incr) <= 0)
+ 	return 0;
+     }
+   return INTVAL (incr);
+ }
+ 
+ 
+ /* Subroutine of biv_fits_mode_p.  Return true if biv BL, when biased by
+    BIAS, will never exceed the unsigned range of MODE.  LOOP is the loop
+    to which the biv belongs and INCR is its per-iteration increment.  */
+ 
+ static bool
+ biased_biv_fits_mode_p (const struct loop *loop, struct iv_class *bl,
+ 			HOST_WIDE_INT incr, enum machine_mode mode,
+ 			unsigned HOST_WIDE_INT bias)
+ {
+   unsigned HOST_WIDE_INT initial, maximum, span, delta;
+ 
+   /* We need to be able to manipulate MODE-size constants.  */
+   if (HOST_BITS_PER_WIDE_INT < GET_MODE_BITSIZE (mode))
+     return false;
+ 
+   /* The number of loop iterations must be constant.  */
+   if (LOOP_INFO (loop)->n_iterations == 0)
+     return false;
+ 
+   /* So must the biv's initial value.  */
+   if (bl->initial_value == 0 || GET_CODE (bl->initial_value) != CONST_INT)
+     return false;
+ 
+   initial = bias + INTVAL (bl->initial_value);
+   maximum = GET_MODE_MASK (mode);
+ 
+   /* Make sure that the initial value is within range.  */
+   if (initial > maximum)
+     return false;
+ 
+   /* Set up DELTA and SPAN such that the number of iterations * DELTA
+      (calculated to arbitrary precision) must be <= SPAN.  */
+   if (incr < 0)
+     {
+       delta = -incr;
+       span = initial;
+     }
+   else
+     {
+       delta = incr;
+       /* Handle the special case in which MAXIMUM is the largest
+ 	 unsigned HOST_WIDE_INT and INITIAL is 0.  */
+       if (maximum + 1 == initial)
+ 	span = LOOP_INFO (loop)->n_iterations * delta;
+       else
+ 	span = maximum + 1 - initial;
+     }
+   return (span / LOOP_INFO (loop)->n_iterations >= delta);
+ }
+ 
+ 
+ /* Return true if biv BL will never exceed the bounds of MODE.  LOOP is
+    the loop to which BL belongs and INCR is its per-iteration increment.
+    UNSIGNEDP is true if the biv should be treated as unsigned.  */
+ 
+ static bool
+ biv_fits_mode_p (const struct loop *loop, struct iv_class *bl,
+ 		 HOST_WIDE_INT incr, enum machine_mode mode, bool unsignedp)
+ {
+   struct loop_info *loop_info;
+   unsigned HOST_WIDE_INT bias;
+ 
+   /* A biv's value will always be limited to its natural mode.
+      Larger modes will observe the same wrap-around.  */
+   if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (bl->biv->src_reg)))
+     mode = GET_MODE (bl->biv->src_reg);
+ 
+   loop_info = LOOP_INFO (loop);
+ 
+   bias = (unsignedp ? 0 : (GET_MODE_MASK (mode) >> 1) + 1);
+   if (biased_biv_fits_mode_p (loop, bl, incr, mode, bias))
+     return true;
+ 
+   if (mode == GET_MODE (bl->biv->src_reg)
+       && bl->biv->src_reg == loop_info->iteration_var
+       && loop_info->comparison_value
+       && loop_invariant_p (loop, loop_info->comparison_value))
+     {
+       /* 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 (incr == 1)
+ 	{
+ 	  if (loop_info->comparison_code == LT)
+ 	    return true;
+ 	  if (loop_info->comparison_code == LTU && unsignedp)
+ 	    return true;
+ 	}
+ 
+       /* Likewise for increment -1 and exit test >.  */
+       if (incr == -1)
+ 	{
+ 	  if (loop_info->comparison_code == GT)
+ 	    return true;
+ 	  if (loop_info->comparison_code == GTU && unsignedp)
+ 	    return true;
+ 	}
+     }
+   return false;
+ }
+ 
+ 
+ /* Given that X is an extension or truncation of BL, return true
+    if it is unaffected by overflow.  LOOP is the loop to which
+    BL belongs and INCR is its per-iteration increment.  */
+ 
+ static bool
+ extension_within_bounds_p (const struct loop *loop, struct iv_class *bl,
+ 			   HOST_WIDE_INT incr, rtx x)
+ {
+   enum machine_mode mode;
+   bool signedp, unsignedp;
+ 
+   switch (GET_CODE (x))
+     {
+     case SIGN_EXTEND:
+     case ZERO_EXTEND:
+       mode = GET_MODE (XEXP (x, 0));
+       signedp = (GET_CODE (x) == SIGN_EXTEND);
+       unsignedp = (GET_CODE (x) == ZERO_EXTEND);
+       break;
+ 
+     case TRUNCATE:
+       /* We don't know whether this value is being used as signed
+ 	 or unsigned, so check the conditions for both.  */
+       mode = GET_MODE (x);
+       signedp = unsignedp = true;
+       break;
+ 
+     default:
+       abort ();
+     }
+ 
+   return ((!signedp || biv_fits_mode_p (loop, bl, incr, mode, false))
+ 	  && (!unsignedp || biv_fits_mode_p (loop, bl, incr, mode, true)));
+ }
+ 
+ 
  /* Check each extension dependent giv in this class to see if its
     root biv is safe from wrapping in the interior mode, which would
     make the giv illegal.  */
*************** combine_givs_p (struct induction *g1, st
*** 7310,7494 ****
  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;
-   unsigned HOST_WIDE_INT u_end_val = 0;
-   unsigned HOST_WIDE_INT u_start_val = 0;
-   rtx incr = pc_rtx;
    struct induction *v;
  
!   /* Make sure the iteration data is available.  We must have
!      constants in order to be certain of no overflow.  */
!   if (loop_info->n_iterations > 0
!       && bl->initial_value
!       && GET_CODE (bl->initial_value) == CONST_INT
!       && (incr = biv_total_increment (bl))
!       && GET_CODE (incr) == CONST_INT
!       /* Make sure the host can represent the arithmetic.  */
!       && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
!     {
!       unsigned HOST_WIDE_INT abs_incr, total_incr;
!       HOST_WIDE_INT s_end_val;
!       int neg_incr;
! 
!       info_ok = 1;
!       start_val = INTVAL (bl->initial_value);
!       u_start_val = start_val;
! 
!       neg_incr = 0, abs_incr = INTVAL (incr);
!       if (INTVAL (incr) < 0)
! 	neg_incr = 1, abs_incr = -abs_incr;
!       total_incr = abs_incr * loop_info->n_iterations;
! 
!       /* Check for host arithmetic overflow.  */
!       if (total_incr / loop_info->n_iterations == abs_incr)
! 	{
! 	  unsigned HOST_WIDE_INT u_max;
! 	  HOST_WIDE_INT s_max;
! 
! 	  u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
! 	  s_end_val = u_end_val;
! 	  u_max = GET_MODE_MASK (biv_mode);
! 	  s_max = u_max >> 1;
! 
! 	  /* Check zero extension of biv ok.  */
! 	  if (start_val >= 0
! 	      /* Check for host arithmetic overflow.  */
! 	      && (neg_incr
! 		  ? u_end_val < u_start_val
! 		  : u_end_val > u_start_val)
! 	      /* Check for target arithmetic overflow.  */
! 	      && (neg_incr
! 		  ? 1 /* taken care of with host overflow */
! 		  : u_end_val <= u_max))
! 	    {
! 	      ze_ok = 1;
! 	    }
! 
! 	  /* Check sign extension of biv ok.  */
! 	  /* ??? While it is true that overflow with signed and pointer
! 	     arithmetic is undefined, I fear too many programmers don't
! 	     keep this fact in mind -- myself included on occasion.
! 	     So leave alone with the signed overflow optimizations.  */
! 	  if (start_val >= -s_max - 1
! 	      /* Check for host arithmetic overflow.  */
! 	      && (neg_incr
! 		  ? s_end_val < start_val
! 		  : s_end_val > start_val)
! 	      /* Check for target arithmetic overflow.  */
! 	      && (neg_incr
! 		  ? s_end_val >= -s_max - 1
! 		  : s_end_val <= s_max))
! 	    {
! 	      se_ok = 1;
! 	    }
! 	}
!     }
! 
!   /* 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)
        {
! 	enum rtx_code code = GET_CODE (v->ext_dependent);
! 	int ok = 0;
! 
! 	switch (code)
! 	  {
! 	  case SIGN_EXTEND:
! 	    ok = se_ok;
! 	    break;
! 	  case ZERO_EXTEND:
! 	    ok = ze_ok;
! 	    break;
! 
! 	  case TRUNCATE:
! 	    /* We don't know whether this value is being used as either
! 	       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;
! 
! 		/* We know from the above that both endpoints are nonnegative,
! 		   and that there is no wrapping.  Verify that both endpoints
! 		   are within the (signed) range of the outer mode.  */
! 		if (u_start_val <= max && u_end_val <= max)
! 		  ok = 1;
! 	      }
! 	    break;
! 
! 	  default:
! 	    abort ();
! 	  }
! 
! 	if (ok)
  	  {
  	    if (loop_dump_stream)
! 	      {
! 		fprintf (loop_dump_stream,
! 			 "Verified ext dependent giv at %d of reg %d\n",
! 			 INSN_UID (v->insn), bl->regno);
! 	      }
  	  }
  	else
  	  {
  	    if (loop_dump_stream)
! 	      {
! 		const char *why;
! 
! 		if (info_ok)
! 		  why = "biv iteration values overflowed";
! 		else
! 		  {
! 		    if (incr == pc_rtx)
! 		      incr = biv_total_increment (bl);
! 		    if (incr == const1_rtx)
! 		      why = "biv iteration info incomplete; incr by 1";
! 		    else
! 		      why = "biv iteration info incomplete";
! 		  }
  
- 		fprintf (loop_dump_stream,
- 			 "Failed ext dependent giv at %d, %s\n",
- 			 INSN_UID (v->insn), why);
- 	      }
  	    v->ignore = 1;
  	    bl->all_reduced = 0;
  	  }
--- 7485,7514 ----
  static void
  check_ext_dependent_givs (const struct loop *loop, struct iv_class *bl)
  {
    struct induction *v;
+   HOST_WIDE_INT incr;
  
!   incr = get_monotonic_increment (bl);
  
    /* Invalidate givs that fail the tests.  */
    for (v = bl->giv; v; v = v->next_iv)
      if (v->ext_dependent)
        {
! 	if (incr != 0
! 	    && extension_within_bounds_p (loop, bl, incr, v->ext_dependent))
  	  {
  	    if (loop_dump_stream)
! 	      fprintf (loop_dump_stream,
! 		       "Verified ext dependent giv at %d of reg %d\n",
! 		       INSN_UID (v->insn), bl->regno);
  	  }
  	else
  	  {
  	    if (loop_dump_stream)
! 	      fprintf (loop_dump_stream,
! 		       "Failed ext dependent giv at %d\n",
! 		       INSN_UID (v->insn));
  
  	    v->ignore = 1;
  	    bl->all_reduced = 0;
  	  }
*** /dev/null	Tue Jun 17 23:06:41 2003
--- testsuite/gcc.c-torture/execute/20030916-1.c	Thu Sep 18 09:52:03 2003
***************
*** 0 ****
--- 1,35 ----
+ /* "i" overflows in f().  Check that x[i] is not treated as a giv.  */
+ #include <limits.h>
+ 
+ #if CHAR_BIT == 8
+ 
+ void f (unsigned int *x)
+ {
+   unsigned char i;
+   int j;
+ 
+   i = 0x10;
+   for (j = 0; j < 0x10; j++)
+     {
+       i += 0xe8;
+       x[i] = 0;
+       i -= 0xe7;
+     }
+ }
+ 
+ int main ()
+ {
+   unsigned int x[256];
+   int i;
+ 
+   for (i = 0; i < 256; i++)
+     x[i] = 1;
+   f (x);
+   for (i = 0; i < 256; i++)
+     if (x[i] != (i >= 0x08 && i < 0xf8))
+       abort ();
+   exit (0);
+ }
+ #else
+ int main () { exit (0); }
+ #endif
*** /dev/null	Tue Jun 17 23:06:41 2003
--- testsuite/gcc.c-torture/execute/20030916-1.x	Thu Sep 18 09:52:03 2003
***************
*** 0 ****
--- 1,2 ----
+ set additional_flags "-freduce-all-givs"
+ return 0
	* loop.c (get_add_bounds, biased_biv_fits_mode_p, biv_fits_mode_p,
	extension_within_bounds_p): New functions.
	(check_ext_dependent_givs): Use them.

--- loop.c.monotonic	Thu Sep 18 13:10:20 2003
+++ loop.c	Fri Sep 19 08:23:46 2003
@@ -232,6 +232,27 @@
 };
 
 
+/* In general, a biv can be incremented by several instructions within the
+   loop.  If each instruction executes exactly once per iteration, and each
+   increment is by a constant amount, then the total per-iteration increment
+   (INCR) is also constant.
+
+   However, we sometimes want to know how much the biv could vary within
+   the loop body.  It would be easy to calculate this exactly if we knew
+   in which order the increments were applied.  Unfortunately, our
+   current data structures don't tell us this, so we need to assume
+   that the increments could be applied in any order.
+
+   Summing up all the negative increments (TOTAL_NEGATIVE) and all the
+   positive increments (TOTAL_POSITIVE) gives us a conservative bound on
+   the variation within a loop.  If the biv has value X at the start of
+   an iteration, it can never stray outside the range [TOTAL_NEGATIVE + X,
+   X + TOTAL_POSITIVE] within that iteration.  */
+struct biv_add_bounds {
+  HOST_WIDE_INT incr, total_negative, total_positive;
+};
+
+
 FILE *loop_dump_stream;
 
 /* Forward declarations.  */
@@ -293,14 +314,15 @@
 			rtx, rtx, rtx, rtx, int, enum g_types, int, int,
 			rtx *);
 static void update_giv_derive (const struct loop *, rtx);
-static HOST_WIDE_INT get_monotonic_increment (struct iv_class *);
+static bool get_biv_add_bounds (struct iv_class *, struct biv_add_bounds *);
 static bool biased_biv_fits_mode_p (const struct loop *, struct iv_class *,
-				    HOST_WIDE_INT, enum machine_mode,
-				    unsigned HOST_WIDE_INT);
+				    const struct biv_add_bounds *,
+				    enum machine_mode, unsigned HOST_WIDE_INT);
 static bool biv_fits_mode_p (const struct loop *, struct iv_class *,
-			     HOST_WIDE_INT, enum machine_mode, bool);
+			     const struct biv_add_bounds *, enum machine_mode,
+			     bool);
 static bool extension_within_bounds_p (const struct loop *, struct iv_class *,
-				       HOST_WIDE_INT, rtx);
+				       const struct biv_add_bounds *, 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 **);
@@ -7311,11 +7333,11 @@
   return NULL_RTX;
 }
 
-/* See if BL is monotonic and has a constant per-iteration increment.
-   Return the increment if so, otherwise return 0.  */
+/* Try to calculate constant bounds on BL's increment value.  Return true
+   on success, storing the information in B.  */
 
-static HOST_WIDE_INT
-get_monotonic_increment (struct iv_class *bl)
+static bool
+get_biv_add_bounds (struct iv_class *bl, struct biv_add_bounds *b)
 {
   struct induction *v;
   rtx incr;
@@ -7323,33 +7345,48 @@
   /* Get the total increment and check that it is constant.  */
   incr = biv_total_increment (bl);
   if (incr == 0 || GET_CODE (incr) != CONST_INT)
-    return 0;
+    return false;
+
+  b->incr = INTVAL (incr);
 
+  /* Add up the positive and negative incremenets.  Fail if there
+     are any non-constant increments or if one of the totals overflows.  */
+  b->total_negative = b->total_positive = 0;
   for (v = bl->biv; v != 0; v = v->next_iv)
     {
-      if (GET_CODE (v->add_val) != CONST_INT)
-	return 0;
+      HOST_WIDE_INT add_val;
 
-      if (INTVAL (v->add_val) < 0 && INTVAL (incr) >= 0)
-	return 0;
+      if (GET_CODE (v->add_val) != CONST_INT)
+	return false;
 
-      if (INTVAL (v->add_val) > 0 && INTVAL (incr) <= 0)
-	return 0;
+      add_val = INTVAL (v->add_val);
+      if (add_val < 0)
+	{
+	  if (INTTYPE_MINIMUM (HOST_WIDE_INT) - add_val > b->total_negative)
+	    return false;
+	  b->total_negative += add_val;
+	}
+      else
+	{
+	  if (INTTYPE_MAXIMUM (HOST_WIDE_INT) - add_val < b->total_positive)
+	    return false;
+	  b->total_positive += add_val;
+	}
     }
-  return INTVAL (incr);
+  return true;
 }
 
 
 /* Subroutine of biv_fits_mode_p.  Return true if biv BL, when biased by
    BIAS, will never exceed the unsigned range of MODE.  LOOP is the loop
-   to which the biv belongs and INCR is its per-iteration increment.  */
+   to which the biv belongs and B is its bounds information.  */
 
 static bool
 biased_biv_fits_mode_p (const struct loop *loop, struct iv_class *bl,
-			HOST_WIDE_INT incr, enum machine_mode mode,
-			unsigned HOST_WIDE_INT bias)
+			const struct biv_add_bounds *b,
+			enum machine_mode mode, unsigned HOST_WIDE_INT bias)
 {
-  unsigned HOST_WIDE_INT initial, maximum, span, delta;
+  unsigned HOST_WIDE_INT initial, minimum, maximum, span, delta;
 
   /* We need to be able to manipulate MODE-size constants.  */
   if (HOST_BITS_PER_WIDE_INT < GET_MODE_BITSIZE (mode))
@@ -7364,22 +7401,33 @@
     return false;
 
   initial = bias + INTVAL (bl->initial_value);
+  minimum = 0;
   maximum = GET_MODE_MASK (mode);
 
+  /* If the biv is sometimes incremented and sometimes decremented,
+     adjust the bounds to account for the worst possible wobble.  */
+  if (b->total_negative < 0 && b->total_positive > 0)
+    {
+      minimum -= b->total_negative;
+      maximum -= b->total_positive;
+      if (minimum > GET_MODE_MASK (mode) || maximum > GET_MODE_MASK (mode))
+	return false;
+    }
+
   /* Make sure that the initial value is within range.  */
-  if (initial > maximum)
+  if (initial < minimum || initial > maximum)
     return false;
 
   /* Set up DELTA and SPAN such that the number of iterations * DELTA
      (calculated to arbitrary precision) must be <= SPAN.  */
-  if (incr < 0)
+  if (b->incr < 0)
     {
-      delta = -incr;
-      span = initial;
+      delta = -b->incr;
+      span = initial - minimum;
     }
   else
     {
-      delta = incr;
+      delta = b->incr;
       /* Handle the special case in which MAXIMUM is the largest
 	 unsigned HOST_WIDE_INT and INITIAL is 0.  */
       if (maximum + 1 == initial)
@@ -7392,12 +7440,13 @@
 
 
 /* Return true if biv BL will never exceed the bounds of MODE.  LOOP is
-   the loop to which BL belongs and INCR is its per-iteration increment.
+   the loop to which BL belongs and B is its bounds information.
    UNSIGNEDP is true if the biv should be treated as unsigned.  */
 
 static bool
 biv_fits_mode_p (const struct loop *loop, struct iv_class *bl,
-		 HOST_WIDE_INT incr, enum machine_mode mode, bool unsignedp)
+		 const struct biv_add_bounds *b, enum machine_mode mode,
+		 bool unsignedp)
 {
   struct loop_info *loop_info;
   unsigned HOST_WIDE_INT bias;
@@ -7410,7 +7459,7 @@
   loop_info = LOOP_INFO (loop);
 
   bias = (unsignedp ? 0 : (GET_MODE_MASK (mode) >> 1) + 1);
-  if (biased_biv_fits_mode_p (loop, bl, incr, mode, bias))
+  if (biased_biv_fits_mode_p (loop, bl, b, mode, bias))
     return true;
 
   if (mode == GET_MODE (bl->biv->src_reg)
@@ -7421,7 +7470,7 @@
       /* 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 (incr == 1)
+      if (b->incr == 1 && b->total_negative == 0)
 	{
 	  if (loop_info->comparison_code == LT)
 	    return true;
@@ -7430,7 +7479,7 @@
 	}
 
       /* Likewise for increment -1 and exit test >.  */
-      if (incr == -1)
+      if (b->incr == -1 && b->total_positive == 0)
 	{
 	  if (loop_info->comparison_code == GT)
 	    return true;
@@ -7444,11 +7493,11 @@
 
 /* Given that X is an extension or truncation of BL, return true
    if it is unaffected by overflow.  LOOP is the loop to which
-   BL belongs and INCR is its per-iteration increment.  */
+   BL belongs and B is its bounds information.  */
 
 static bool
 extension_within_bounds_p (const struct loop *loop, struct iv_class *bl,
-			   HOST_WIDE_INT incr, rtx x)
+			   const struct biv_add_bounds *b, rtx x)
 {
   enum machine_mode mode;
   bool signedp, unsignedp;
@@ -7473,8 +7522,8 @@
       abort ();
     }
 
-  return ((!signedp || biv_fits_mode_p (loop, bl, incr, mode, false))
-	  && (!unsignedp || biv_fits_mode_p (loop, bl, incr, mode, true)));
+  return ((!signedp || biv_fits_mode_p (loop, bl, b, mode, false))
+	  && (!unsignedp || biv_fits_mode_p (loop, bl, b, mode, true)));
 }
 
 
@@ -7485,17 +7534,18 @@
 static void
 check_ext_dependent_givs (const struct loop *loop, struct iv_class *bl)
 {
+  struct biv_add_bounds bounds;
   struct induction *v;
-  HOST_WIDE_INT incr;
+  bool bounds_ok;
 
-  incr = get_monotonic_increment (bl);
+  bounds_ok = get_biv_add_bounds (bl, &bounds);
 
   /* Invalidate givs that fail the tests.  */
   for (v = bl->giv; v; v = v->next_iv)
     if (v->ext_dependent)
       {
-	if (incr != 0
-	    && extension_within_bounds_p (loop, bl, incr, v->ext_dependent))
+	if (bounds_ok
+	    && extension_within_bounds_p (loop, bl, &bounds, v->ext_dependent))
 	  {
 	    if (loop_dump_stream)
 	      fprintf (loop_dump_stream,

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]