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]

An attempt to improve the handling of promoted bivs


This patch tries to recognise more promoted registers as bivs.
If we have a loop such as:

    for (unsigned short i = 0; i < 0x100; i++)
      x[i] = 1234;

and 16-bit unsigned shorts are promoted to 32 bits, "i" will be
incremented by an add-and-extension sequence:

    (set (reg:SI temp) (plus:SI (reg:SI i) (const_int 1)))
    (set (reg:SI i) (extend:SI (subreg:HI (reg:SI temp))))

where "extend" can be either sign_extend or zero_extend, depending on
the definition of PROMOTE_MODE.

The patch tentatively treats such variables as bivs.  Once strength_reduce
knows (or thinks it knows) the number of iterations, it will invalidate any
bivs which might overflow the inner mode of an extension.

("thinks it knows" because the number of iterations might itself be based
on an unsafe biv.  If so, strength_reduce will get rid of both the biv and
the iteration information.)

----------------------------------------------------------------------

If a biv turns out to be safe, the patch will replace the biv increment
with a normal addition.  The rest of the sequence will usually be deleted
as dead.  This allows the do-while optimisations to kick in during the
second loop_optimize pass.

For example, "temp" above will be treated as an "i"-based giv.  But if
we increment "i" directly, remove temp, and reduce the x[i] giv, nothing
else will depend on "i".

...and there lies the rub.  At the moment, basic_induction_var will
unconditionally treat add-and-sign-extend sequences like any other
addition, on the basis that signed overflow is undefined.  But:

    1. We shy away from that during initial rtl generation.  That is,
       we still emit the sign extension, even though we know that it
       isn't strictly needed.

    2. We shy away from it when a giv involves a sign extension.
       Quoting from check_ext_dependent_givs:

	  /* ??? 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.  */

So when dealing with zero extensions, we have a nice clean distinction:
either (1) the variable is a biv, and we can remove the extension, or
(2) the variable isn't a biv, and we must keep the extension.

But for sign extensions, we seem to have this muddy inbetween where we
treat the variable as a biv but daren't remove the extension outright.

So, I'm afraid there's two patches again.  The first, my preferred one,
treats sign extension and zero extension in the same way.  It removes
extensions if it can prove there's no overflow, otherwise it doesn't
treat the extended variable as a biv at all.  The second (relative to
the first) tries to keep to the spirit of the existing behaviour.

----------------------------------------------------------------------

To give a mips example, the loop above used to be compiled as:

	move	$5,$0
	li	$6,1234			# 0x4d2
	.align	3
$L5:
	addiu	$2,$5,1
	sll	$3,$5,2
	andi	$5,$2,0xffff
	addu	$3,$3,$4
	sltu	$2,$5,100
	bne	$2,$0,$L5
	sw	$6,0($3)

	j	$31
	nop

After the patch, it is:

	li	$3,1234			# 0x4d2
	li	$2,99			# 0x63
	.align	3
$L5:
	addiu	$2,$2,-1
	sw	$3,0($4)
	bgez	$2,$L5
	addiu	$4,$4,4

	j	$31
	nop

----------------------------------------------------------------------

First patch has been bootstrapped & regression tested on i686-pc-linux-gnu
and various mips targets.  A slightly earlier version of the second patch
was too.  (I'd recheck it before applying, just to be sure.  The differences
are trivial though.)

The patches depend on:

  http://gcc.gnu.org/ml/gcc-patches/2003-09/msg01268.html

Richard


	* loop.h (clear_loop_iteration_info): Declare.
	* unroll.c (clear_loop_iteration_info): New function, split out from...
	(loop_iterations): ...here.
	* loop.c (basic_induction_var): Take a new extension argument.
	Allow sign- and zero-extended bivs, storing the extension in the
	new argument.  Update recursive calls.
	(record_biv): Add an extension argument.  Record it in ext_dependent.
	(check_insn_for_bivs): Update accordingly.
	(kill_ivs, biv_safe_extensions_p): New functions.
	(check_ext_dependent_bivs): New function.
	(strength_reduce): If the information calculcated by loop_iterations
	was based on an extended biv, check whether that biv is safe.  Clear
	the loop information if not.  Call check_ext_dependent_bivs.

Index: loop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.h,v
retrieving revision 1.68
diff -c -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.68 loop.h
*** loop.h	6 Jul 2003 09:56:04 -0000	1.68
--- loop.h	19 Sep 2003 13:42:31 -0000
*************** extern rtx extend_value_for_giv (struct 
*** 410,415 ****
--- 410,416 ----
  extern void unroll_loop (struct loop *, int, int);
  extern rtx biv_total_increment (const struct iv_class *);
  extern unsigned HOST_WIDE_INT loop_iterations (struct loop *);
+ extern void clear_loop_iteration_info (struct loop *loop);
  extern int precondition_loop_p (const struct loop *, rtx *, rtx *, rtx *,
  				enum machine_mode *mode);
  extern rtx final_biv_value (const struct loop *, struct iv_class *);
Index: unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
retrieving revision 1.201
diff -c -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.201 unroll.c
*** unroll.c	21 Jul 2003 16:52:36 -0000	1.201
--- unroll.c	19 Sep 2003 13:42:32 -0000
*************** find_common_reg_term (rtx op0, rtx op1)
*** 3239,3244 ****
--- 3239,3265 ----
    return NULL_RTX;
  }
  
+ /* Clear all the information in LOOP that was (or will be) calculcated by
+    loop_iterations.  */
+ 
+ void
+ clear_loop_iteration_info (struct loop *loop)
+ {
+   struct loop_info *loop_info;
+ 
+   loop_info = LOOP_INFO (loop);
+   loop_info->n_iterations = 0;
+   loop_info->initial_value = 0;
+   loop_info->initial_equiv_value = 0;
+   loop_info->comparison_value = 0;
+   loop_info->final_value = 0;
+   loop_info->final_equiv_value = 0;
+   loop_info->increment = 0;
+   loop_info->iteration_var = 0;
+   loop_info->unroll_number = 1;
+   loop_info->iv = 0;
+ }
+ 
  /* Determine the loop iterator and calculate the number of loop
     iterations.  Returns the exact number of loop iterations if it can
     be calculated, otherwise returns zero.  */
*************** loop_iterations (struct loop *loop)
*** 3261,3276 ****
    rtx reg_term;
    struct iv_class *bl;
  
!   loop_info->n_iterations = 0;
!   loop_info->initial_value = 0;
!   loop_info->initial_equiv_value = 0;
!   loop_info->comparison_value = 0;
!   loop_info->final_value = 0;
!   loop_info->final_equiv_value = 0;
!   loop_info->increment = 0;
!   loop_info->iteration_var = 0;
!   loop_info->unroll_number = 1;
!   loop_info->iv = 0;
  
    /* We used to use prev_nonnote_insn here, but that fails because it might
       accidentally get the branch for a contained loop if the branch for this
--- 3282,3288 ----
    rtx reg_term;
    struct iv_class *bl;
  
!   clear_loop_iteration_info (loop);
  
    /* We used to use prev_nonnote_insn here, but that fails because it might
       accidentally get the branch for a contained loop if the branch for this
--- loop.c.wobble	Fri Sep 19 11:33:41 2003
+++ loop.c	Fri Sep 19 14:56:37 2003
@@ -304,7 +304,7 @@ static void find_single_use_in_loop (str
 static int valid_initial_value_p (rtx, rtx, int, rtx);
 static void find_mem_givs (const struct loop *, rtx, rtx, int, int);
 static void record_biv (struct loop *, struct induction *, rtx, rtx, rtx,
-			rtx, rtx *, int, int);
+			rtx, rtx *, int, int, rtx);
 static void check_final_value (const struct loop *, struct induction *);
 static void loop_ivs_dump (const struct loop *, FILE *, int);
 static void loop_iv_class_dump (const struct iv_class *, FILE *, int);
@@ -323,9 +323,12 @@ static bool biv_fits_mode_p (const struc
 			     bool);
 static bool extension_within_bounds_p (const struct loop *, struct iv_class *,
 				       const struct biv_add_bounds *, rtx);
+static void kill_ivs (struct loop *, struct induction *);
+static bool biv_safe_extensions_p (struct loop *, struct iv_class *);
+static void check_ext_dependent_bivs (struct loop *);
 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 **);
+				rtx, rtx, rtx *, rtx *, rtx **, rtx *);
 static rtx simplify_giv_expr (const struct loop *, rtx, rtx *, int *);
 static int general_induction_var (const struct loop *loop, rtx, rtx *, rtx *,
 				  rtx *, rtx *, int, int *, enum machine_mode);
@@ -5130,6 +5133,22 @@ strength_reduce (struct loop *loop, int 
      fail if the iteration variable is a giv.  */
   loop_iterations (loop);
 
+  /* Handle the case where loop_iterations found an iteration variable
+     and the underlying biv is incremented by add-and-extend operations.
+     We must make sure that those operations behave like simple adds within
+     the current iteration space.  */
+  if (LOOP_INFO (loop)->iv != 0
+      && !biv_safe_extensions_p (loop, LOOP_INFO (loop)->iv))
+    {
+      if (loop_dump_stream)
+	fprintf (loop_dump_stream,
+		 "The iteration information relied on an unsafe biv.\n");
+
+      clear_loop_iteration_info (loop);
+    }
+
+  check_ext_dependent_bivs (loop);
+
 #ifdef HAVE_prefetch
   if (flags & LOOP_PREFETCH)
     emit_prefetch_instructions (loop);
@@ -5395,6 +5414,7 @@ check_insn_for_bivs (struct loop *loop, 
   rtx inc_val;
   rtx mult_val;
   rtx *location;
+  rtx extension;
 
   if (GET_CODE (p) == INSN
       && (set = single_set (p))
@@ -5405,10 +5425,11 @@ check_insn_for_bivs (struct loop *loop, 
 	  && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
 	  && REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
 	{
+	  extension = 0;
 	  if (basic_induction_var (loop, SET_SRC (set),
 				   GET_MODE (SET_SRC (set)),
 				   dest_reg, p, &inc_val, &mult_val,
-				   &location))
+				   &location, &extension))
 	    {
 	      /* It is a possible basic induction variable.
 	         Create and initialize an induction structure for it.  */
@@ -5416,7 +5437,7 @@ check_insn_for_bivs (struct loop *loop, 
 	      struct induction *v = xmalloc (sizeof (struct induction));
 
 	      record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
-			  not_every_iteration, maybe_multiple);
+			  not_every_iteration, maybe_multiple, extension);
 	      REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
 	    }
 	  else if (REGNO (dest_reg) < ivs->n_regs)
@@ -5635,12 +5656,15 @@ find_mem_givs (const struct loop *loop, 
    executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
    can be executed more than once per iteration.  If MAYBE_MULTIPLE
    and NOT_EVERY_ITERATION are both zero, we know that the biv update is
-   executed exactly once per iteration.  */
+   executed exactly once per iteration.
+
+   If the biv is incremented by an add-and-extend operation, EXTENSION
+   points to the extension part, otherwise it is null.  */
 
 static void
 record_biv (struct loop *loop, struct induction *v, rtx insn, rtx dest_reg,
 	    rtx inc_val, rtx mult_val, rtx *location,
-	    int not_every_iteration, int maybe_multiple)
+	    int not_every_iteration, int maybe_multiple, rtx extension)
 {
   struct loop_ivs *ivs = LOOP_IVS (loop);
   struct iv_class *bl;
@@ -5650,7 +5674,7 @@ record_biv (struct loop *loop, struct in
   v->dest_reg = dest_reg;
   v->mult_val = mult_val;
   v->add_val = inc_val;
-  v->ext_dependent = NULL_RTX;
+  v->ext_dependent = extension;
   v->location = location;
   v->mode = GET_MODE (dest_reg);
   v->always_computable = ! not_every_iteration;
@@ -6194,31 +6218,21 @@ update_giv_derive (const struct loop *lo
    If X is an assignment of an invariant into DEST_REG, we set
    *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
 
-   We also want to detect a BIV when it corresponds to a variable
-   whose mode was promoted via PROMOTED_MODE.  In that case, an increment
-   of the variable may be a PLUS that adds a SUBREG of that variable to
-   an invariant and then sign- or zero-extends the result of the PLUS
-   into the variable.
-
-   Most GIVs in such cases will be in the promoted mode, since that is the
-   probably the natural computation mode (and almost certainly the mode
-   used for addresses) on the machine.  So we view the pseudo-reg containing
-   the variable as the BIV, as if it were simply incremented.
+   We also want to detect bivs that were promoted by PROMOTED_MODE.
+   Such bivs will usually be incremented by a PLUS or MINUS and then
+   sign- or zero-extended.  If the biv is modified in this way, point
+   *EXTENSION to the extension operation, otherwise leave it null.
 
-   Note that treating the entire pseudo as a BIV will result in making
-   simple increments to any GIVs based on it.  However, if the variable
-   overflows in its declared mode but not its promoted mode, the result will
-   be incorrect.  This is acceptable if the variable is signed, since
-   overflows in such cases are undefined, but not if it is unsigned, since
-   those overflows are defined.  So we only check for SIGN_EXTEND and
-   not ZERO_EXTEND.
+   Note that this sort of biv is only valid if it never overflows
+   the inner mode of the extension.  We check this later, in
+   check_ext_dependent_bivs.
 
    If we cannot find a biv, we return 0.  */
 
 static int
 basic_induction_var (const struct loop *loop, rtx x, enum machine_mode mode,
 		     rtx dest_reg, rtx p, rtx *inc_val, rtx *mult_val,
-		     rtx **location)
+		     rtx **location, rtx *extension)
 {
   enum rtx_code code;
   rtx *argp, arg;
@@ -6281,7 +6295,8 @@ basic_induction_var (const struct loop *
 	 variable increments don't look like it says they do.  */
       return basic_induction_var (loop, SUBREG_REG (x),
 				  GET_MODE (SUBREG_REG (x)),
-				  dest_reg, p, inc_val, mult_val, location);
+				  dest_reg, p, inc_val, mult_val,
+				  location, extension);
 
     case REG:
       /* If this register is assigned in a previous insn, look at its
@@ -6318,8 +6333,8 @@ basic_induction_var (const struct loop *
 					(GET_MODE (SET_SRC (set)) == VOIDmode
 					 ? GET_MODE (x)
 					 : GET_MODE (SET_SRC (set))),
-					dest_reg, insn,
-					inc_val, mult_val, location);
+					dest_reg, insn, inc_val, mult_val,
+					location, extension);
 
 	  while (GET_CODE (dest) == SIGN_EXTRACT
 		 || GET_CODE (dest) == ZERO_EXTRACT
@@ -6365,12 +6380,15 @@ basic_induction_var (const struct loop *
       else
 	return 0;
 
+    case ZERO_EXTEND:
     case SIGN_EXTEND:
-      /* Ignore this BIV if signed arithmetic overflow is defined.  */
-      if (flag_wrapv)
+      if (*extension != 0)
 	return 0;
+
+      *extension = x;
       return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
-				  dest_reg, p, inc_val, mult_val, location);
+				  dest_reg, p, inc_val, mult_val,
+				  location, extension);
 
     case ASHIFTRT:
       /* Similar, since this can be a sign extension.  */
@@ -6392,7 +6410,7 @@ basic_induction_var (const struct loop *
 	return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
 				    GET_MODE (XEXP (x, 0)),
 				    dest_reg, insn, inc_val, mult_val,
-				    location);
+				    location, extension);
       return 0;
 
     default:
@@ -7524,6 +7542,97 @@ extension_within_bounds_p (const struct 
 
   return ((!signedp || biv_fits_mode_p (loop, bl, b, mode, false))
 	  && (!unsignedp || biv_fits_mode_p (loop, bl, b, mode, true)));
+}
+
+
+/* Discard LIST, a list of induction structures which belongs to LOOP.  */
+
+static void
+kill_ivs (struct loop *loop, struct induction *list)
+{
+  struct induction *v, *next;
+
+  for (v = list; v != 0; v = next)
+    {
+      if (REGNO (v->dest_reg) < LOOP_IVS (loop)->n_regs)
+	REG_IV_TYPE (LOOP_IVS (loop), REGNO (v->dest_reg)) = UNKNOWN_INDUCT;
+
+      next = v->next_iv;
+      free (v);
+    }
+}
+
+
+/* Return true if all add-and-extend operations on BL are equivalent
+   to simple adds.  LOOP is the loop to which BL belongs.  */
+
+static bool
+biv_safe_extensions_p (struct loop *loop, struct iv_class *bl)
+{
+  struct biv_add_bounds bounds;
+  struct induction *v;
+  bool bounds_ok;
+
+  bounds_ok = get_biv_add_bounds (bl, &bounds);
+  for (v = bl->biv; v != 0; v = v->next_iv)
+    if (v->ext_dependent != 0)
+      {
+	if (!bounds_ok)
+	  return false;
+
+	if (!extension_within_bounds_p (loop, bl, &bounds, v->ext_dependent))
+	  return false;
+      }
+  return true;
+}
+
+
+/* Check each biv in LOOP to see whether its add-and-extend increments
+   behave like normal adds.  Remove the biv if not, otherwise try
+   replacing each extension with an equivalent addition.  */
+
+static void
+check_ext_dependent_bivs (struct loop *loop)
+{
+  struct iv_class *bl, **blp;
+
+  blp = &LOOP_IVS (loop)->list;
+  while (*blp != 0)
+    {
+      bl = *blp;
+      if (!biv_safe_extensions_p (loop, bl))
+	{
+	  if (loop_dump_stream)
+	    fprintf (loop_dump_stream,
+		     "Removing biv %d since it might overflow\n",
+		     bl->regno);
+
+	  kill_ivs (loop, bl->biv);
+	  kill_ivs (loop, bl->giv);
+	  *blp = bl->next;
+	  free (bl);
+	}
+      else
+	{
+	  struct induction *v;
+
+	  for (v = bl->biv; v != 0; v = v->next_iv)
+	    if (v->ext_dependent != 0)
+	      {
+		rtx seq, insn;
+
+		seq = gen_add3_insn (v->dest_reg, v->src_reg, v->add_val);
+		if (seq != 0)
+		  {
+		    insn = emit_insn_after (seq, v->insn);
+		    delete_insn (v->insn);
+		    v->insn = insn;
+		    v->ext_dependent = 0;
+		  }
+	      }
+	  blp = &bl->next;
+	}
+    }
 }
 
 
--- loop.c.biv	Fri Sep 19 14:55:27 2003
+++ loop.c	Fri Sep 19 14:57:39 2003
@@ -6223,9 +6223,9 @@
    sign- or zero-extended.  If the biv is modified in this way, point
    *EXTENSION to the extension operation, otherwise leave it null.
 
-   Note that this sort of biv is only valid if it never overflows
-   the inner mode of the extension.  We check this later, in
-   check_ext_dependent_bivs.
+   Note that this sort of biv is only valid if it never overflows the
+   inner mode of the extension or if the semantics of such overflow
+   would be undefined.  We check this later, in check_ext_dependent_bivs.
 
    If we cannot find a biv, we return 0.  */
 
@@ -7575,7 +7575,14 @@
 
   bounds_ok = get_biv_add_bounds (bl, &bounds);
   for (v = bl->biv; v != 0; v = v->next_iv)
-    if (v->ext_dependent != 0)
+    if (v->ext_dependent != 0
+	/* Signed overflow is undefined without -fwrapv, so ignore overflow
+	   within SIGN_EXTENDs.  Note that this is safe even in cases where
+	   PROMOTE_MODE chose to sign-extend an unsigned variable.  Any
+	   operation which relies on the unsignedness of the variable will
+	   either have to do the operation in the original mode or
+	   zero-extend the register first.  */
+	&& (flag_wrapv || GET_CODE (v->ext_dependent) != SIGN_EXTEND))
       {
 	if (!bounds_ok)
 	  return false;
@@ -7614,10 +7621,17 @@
 	}
       else
 	{
+	  struct biv_add_bounds bounds;
 	  struct induction *v;
+	  bool bounds_ok;
+
+	  bounds_ok = get_biv_add_bounds (bl, &bounds);
 
 	  for (v = bl->biv; v != 0; v = v->next_iv)
-	    if (v->ext_dependent != 0)
+	    if (v->ext_dependent != 0
+		&& bounds_ok
+		&& extension_within_bounds_p (loop, bl, &bounds,
+					      v->ext_dependent))
 	      {
 		rtx seq, insn;
 

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