Autoincrement addressing patch

["Michael P. Hayes" <michaelh at ongaonga dot chch dot cri dot nz>]

Here's an experimental patch for better detection and generation
of autoincrement addressing modes.

Rather than just combining a single memory reference with an increment
in another insn, it tries to generate the desired increment using
multiple memory references.

For example, it will try converting *p; *(p+1); p += 2 into *p++;
*p++,  saving an insn and more importantly preventing a
pipeline stall on many pipelined architectures.


I've had no problems with this patch yet, using the C4x port I have
been developing with the gcc2 snapshots.  Unfortunately, the
modified CSE pass with EGCS seems to stifle this optimisation.


Michael.


Index: flow.c
===================================================================
RCS file: /usr/local/src/cvsroot/gnu/egcs/gcc/flow.c,v
retrieving revision 1.1.1.2
retrieving revision 1.2
diff -c -r1.1.1.2 -r1.2
*** flow.c	1998/01/07 00:54:06	1.1.1.2
--- flow.c	1998/01/07 03:35:39	1.2
***************
*** 181,186 ****
--- 181,198 ----
  
  static rtx *reg_next_use;
  
+ struct autoinc 
+ {
+   HOST_WIDE_INT inc;
+   HOST_WIDE_INT offset;
+   rtx insn;
+   rtx addr;
+   rtx x;
+   struct autoinc *next;
+ };
+ 
+ static struct autoinc **reg_auto_inc;
+ 
  /* Size of a regset for the current function,
     in (1) bytes and (2) elements.  */
  
***************
*** 267,272 ****
--- 279,286 ----
  static void mark_used_regs		PROTO((regset, regset, rtx, int, rtx));
  static int try_pre_increment_1		PROTO((rtx));
  static int try_pre_increment		PROTO((rtx, rtx, HOST_WIDE_INT));
+ static void free_all_auto_inc		PROTO((int));
+ static void free_auto_inc		PROTO((struct autoinc **));
  void dump_flow_info			PROTO((FILE *));
  
  /* Find basic blocks of the current function and perform data flow analysis.
***************
*** 967,972 ****
--- 981,992 ----
    reg_next_use = (rtx *) alloca (nregs * sizeof (rtx));
    bzero ((char *) reg_next_use, nregs * sizeof (rtx));
  
+ #ifdef AUTO_INC_DEC
+   reg_auto_inc = (struct autoinc **)
+     alloca (nregs * sizeof (struct autoinc *));
+   bzero ((char *) reg_auto_inc, nregs * sizeof (struct autoinc *));
+ #endif
+ 
    /* Set up several regset-vectors used internally within this function.
       Their meanings are documented above, with their declarations.  */
  
***************
*** 1310,1315 ****
--- 1330,1338 ----
  				 }
  			     });
  
+ #ifdef AUTO_INC_DEC
+   free_all_auto_inc(nregs);
+ #endif
  
    free_regset_vector (basic_block_live_at_end, n_basic_blocks);
    free_regset_vector (basic_block_new_live_at_end, n_basic_blocks);
***************
*** 2145,2150 ****
--- 2168,2197 ----
  
  #ifdef AUTO_INC_DEC
  
+ static void
+ free_auto_inc (p)
+      struct autoinc **p;
+ {
+   struct autoinc *a = *p;
+   if (!a)
+     return;
+   if (a->next)
+     free_auto_inc ((&a->next));
+   free (*p);
+   *p = 0;
+ }
+ 
+ static void
+ free_all_auto_inc (nregs)
+      int nregs;
+ {
+   int r;
+ 
+   for (r = 0; r < nregs; r++)
+     free_auto_inc(&reg_auto_inc[r]);
+ }
+ 
+ 
  /* X is a MEM found in INSN.  See if we can convert it into an auto-increment
     reference.  */
  
***************
*** 2156,2162 ****
--- 2203,2215 ----
  {
    rtx addr = XEXP (x, 0);
    HOST_WIDE_INT offset = 0;
+   register int size = GET_MODE_SIZE (GET_MODE (x));
+   struct autoinc *a;
+   register rtx y;
    rtx set;
+   rtx use;
+   rtx incr;
+   int regno;
  
    /* Here we detect use of an index register which might be good for
       postincrement, postdecrement, preincrement, or predecrement.  */
***************
*** 2164,2177 ****
    if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
      offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
  
!   if (GET_CODE (addr) == REG)
      {
!       register rtx y;
!       register int size = GET_MODE_SIZE (GET_MODE (x));
!       rtx use;
!       rtx incr;
!       int regno = REGNO (addr);
  
        /* Is the next use an increment that might make auto-increment? */
        if ((incr = reg_next_use[regno]) != 0
  	  && (set = single_set (incr)) != 0
--- 2217,2366 ----
    if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
      offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
  
!   if (GET_CODE (addr) != REG)
!     return;
! 
!   regno = REGNO (addr);
! 
!   /* Build a list of candidate memory references for each address
!      register that can be potentially converted to use auto-increment
!      addressing modes.  Stop when we have enough auto-increments to
!      increment the address by the desired amount, for example:
!      *p; *(p + 1); p = p + 2  becomes *p++; *p++  */
! 
!   if (reg_auto_inc[regno] != 0)
      {
!       struct autoinc *b = reg_auto_inc[regno];
!       int incs = 0;      
! 
!       /* Can this memory reference be changed to auto-increment?  */
!       if (BLOCK_NUM (insn) != BLOCK_NUM (b->insn)
! 	  /* Can't add side effects to jumps; if reg is spilled and
! 	     reloaded, there's no way to store back the altered value.  */
! 	  || GET_CODE (insn) == JUMP_INSN
! 	  /* The memory reference must be on the chain.  */
! 	  || reg_next_use[regno] != b->insn
! 	  || !(0
! #ifdef HAVE_POST_INCREMENT
! 	       || (offset == b->inc && b->inc > 0)
! #endif
! #ifdef HAVE_PRE_INCREMENT
! 	       || (offset == b->inc - size && b->inc > 0)
! #endif
! #ifdef HAVE_POST_DECREMENT
! 	       || (offset == b->inc && b->inc < 0)
! #endif
! #ifdef HAVE_PRE_DECREMENT
! 	       || (offset == b->inc + size && b->inc < 0)
! #endif
! 	       )
! 	  /* Make sure this reg appears only once in this insn.  */
! 	  || (use = find_use_as_address (PATTERN (insn), addr, offset),
! 	      use == 0 || use == (rtx) 1))
! 	{
! 	  /* Give up ... */
! 	  free_auto_inc(&reg_auto_inc[regno]);
! 	  return;
! 	}
!   
!       a = (struct autoinc *) xmalloc (sizeof (struct autoinc));	      
!       a->insn = insn;
!       a->offset = offset;
!       a->addr = addr;
!       a->x = x;
!       a->next = b;
!       a->inc = b->inc > 0 ? b->inc - size : b->inc + size;
!       reg_auto_inc[regno] = a;
!       
!       if (a->inc != 0)
! 	return;
  
+       /* Validate all the required changes to the memory references.  */
+       for (a = reg_auto_inc[regno]; a->next; a = a->next)
+ 	{
+ 	  enum rtx_code inc_code = a->next->inc > 0
+ 	    ? ((a->offset == a->inc) ? POST_INC : PRE_INC)
+ 	    : ((a->offset == a->inc) ? POST_DEC : PRE_DEC);
+ 	  
+ 	  incs++;
+ 	  validate_change (a->insn, &XEXP (a->x, 0),
+ 			   gen_rtx (inc_code, Pmode, a->addr),
+ 			   1);
+ 	}
+       if (! apply_change_group ())
+ 	{
+ 	  free_auto_inc(&reg_auto_inc[regno]);
+ 	  return;
+ 	}
+       
+       for (a = reg_auto_inc[regno]; a->next; a = a->next)
+ 	{
+ 	  REG_NOTES (a->insn)
+ 	    = gen_rtx (EXPR_LIST, REG_INC, a->addr, REG_NOTES (a->insn));
+ 	}
+       
+       /* Modify the old increment-insn to simply copy
+ 	 the already-incremented value of our register.  */
+       set = single_set(a->insn);
+       if (! validate_change (a->insn, &SET_SRC (set), addr, 0))
+ 	abort ();
+       
+       /* If that makes it a no-op (copying the register into itself) delete
+ 	 it so it won't appear to be a "use" and a "set" of this
+ 	 register.  */
+       if (SET_DEST (set) == addr)
+ 	{
+ 	  PUT_CODE (a->insn, NOTE);
+ 	  NOTE_LINE_NUMBER (a->insn) = NOTE_INSN_DELETED;
+ 	  NOTE_SOURCE_FILE (a->insn) = 0;
+ 	}
+       
+       if (regno >= FIRST_PSEUDO_REGISTER)
+ 	{
+ 	  /* Count an extra reference to the reg.  When a reg is
+ 	     incremented, spilling it is worse, so we want to make
+ 	     that less likely.  */
+ 	  REG_N_REFS (regno) += loop_depth * incs;
+ 	  
+ 	  /* Count the increments as a setting of the register,
+ 	     even though it isn't a SET in rtl.  */
+ 	  REG_N_SETS (regno) += incs;
+ 	}
+       
+       free_auto_inc(&reg_auto_inc[regno]);
+       return;
+     }
+   else
+     {
+       /* Is the next use an increment that might make auto-increment? */
+       if ((incr = reg_next_use[regno]) == 0
+ 	  || (set = single_set (incr)) == 0
+ 	  || BLOCK_NUM (incr) != BLOCK_NUM (insn)
+ 	  || (y = SET_SRC (set), GET_CODE (y) != PLUS)
+ 	  || XEXP (y, 0) != addr
+ 	  || GET_CODE (XEXP (y, 1)) != CONST_INT)
+ 	return;
+ 
+       /* Deal with the simple case (p = p + inc). */
+       if (dead_or_set_p (incr, addr))
+ 	{
+ 	  a = (struct autoinc *) xmalloc (sizeof (struct autoinc));	      
+ 	  a->insn = incr;
+ 	  a->inc = INTVAL (XEXP (y, 1));
+ 	  a->offset = 0;
+ 	  a->addr = 0;
+ 	  a->x = 0;
+ 	  a->next = 0;
+ 	  reg_auto_inc[regno] = a;
+ 	  return find_auto_inc (needed, x, insn);
+ 	}
+     }
+ 
+   /* The redundant code in the following needs to be pruned,
+      especially for the simple case.  */
+ 
+   if (GET_CODE (addr) == REG)   
+     {
        /* Is the next use an increment that might make auto-increment? */
        if ((incr = reg_next_use[regno]) != 0
  	  && (set = single_set (incr)) != 0