[Patch] Splitting memory references during unrolling (resubmission)

[Patch] Splitting memory references during unrolling (resubmission)

[Revital Eres]

[-- Attachment #1: Type: text/plain, Size: 205 bytes --]

Hello,

This is a resubmission of the patch relative to mainline.
(http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01334.html)

Bootstrapped (with -funroll-all-loops) & regression tests on POWER4.

Revital



[-- Attachment #2: diff_14_10 --]
[-- Type: application/octet-stream, Size: 8094 bytes --]

Index: common.opt
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/common.opt,v
retrieving revision 1.55
diff -c -3 -p -r1.55 common.opt
*** common.opt	14 Sep 2004 08:05:45 -0000	1.55
--- common.opt	14 Oct 2004 10:27:50 -0000
*************** fsplit-ivs-in-unroller
*** 748,753 ****
--- 748,758 ----
  Common Report Var(flag_split_ivs_in_unroller) Init(1)
  Split lifetimes of induction variables when loops are unrolled.
  
+ fsplit-ivs-in-memref-during-unrolling
+ Common Report Var(flag_split_ivs_in_memref_during_unrolling)
+ Split lifetimes of induction variables used in memory references
+ when loops are unrolled.
+ 
  ; Emit code to probe the stack, to help detect stack overflow; also
  ; may cause large objects to be allocated dynamically.
  fstack-check
Index: loop-unroll.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/loop-unroll.c,v
retrieving revision 1.19
diff -c -3 -p -r1.19 loop-unroll.c
*** loop-unroll.c	14 Sep 2004 08:05:45 -0000	1.19
--- loop-unroll.c	14 Oct 2004 10:27:50 -0000
*************** static struct split_ivs_info *analyze_iv
*** 107,112 ****
--- 107,113 ----
  static void si_info_start_duplication (struct split_ivs_info *);
  static void split_ivs_in_copies (struct split_ivs_info *, unsigned, bool, bool);
  static void free_si_info (struct split_ivs_info *);
+ static struct iv_to_split *analyze_memory_ref_to_split_iv (rtx);
  
  /* Unroll and/or peel (depending on FLAGS) LOOPS.  */
  void
*************** si_info_eq (const void *ivts1, const voi
*** 1407,1412 ****
--- 1408,1542 ----
    return i1->insn == i2->insn;
  }
  
+ /*  Check if INSN contains memory reference 
+     which uses induction variable that can be 
+     splitted.  I.e replace:
+     
+     load a[i]
+     ...
+     load a[i]
+     ...
+     load a[i]
+     ...
+     
+     with  ==> 
+     
+     load 4(base)
+     ...
+     load 8(base)
+     ...
+     load 12(base)
+     ...
+     
+     Where base = a+i.
+     Return NULL if INSN contains no such
+     memory reference.  Otherwise allocate
+     struct IV_TO_SPLIT and fill it with the appropriate 
+     information.
+ */
+ 
+ static struct iv_to_split *
+ analyze_memory_ref_to_split_iv (rtx insn)
+ {
+   struct iv_to_split *ivts;
+   rtx lop, rop, expr;
+   int n_loc, loc_0, loc_1, loc_2 = -1;
+   rtx set, dest, src;
+   rtx insn1 = NULL_RTX, insn2 = NULL_RTX;
+   struct rtx_iv iv1, iv2, iv;
+   
+   set = single_set (insn);
+   if (!set)
+     return NULL;
+   
+   dest = SET_DEST (set);
+   src = SET_SRC (set);
+   
+   /* reg = mem [ invariant + iv ].  */
+   if ((REG_P (dest)
+        || (GET_CODE (dest) == SUBREG
+            && REG_P (SUBREG_REG (dest))))
+       && MEM_P (src))
+     {
+       n_loc = 2;
+       loc_0 = 1;
+       loc_1 = 0;
+       expr =  XEXP (src, 0); 
+     }
+   /* mem [ invariant + iv ] = reg.  */
+   else if ((REG_P (src)
+             || (GET_CODE (src) == SUBREG
+                 && REG_P (SUBREG_REG (src))))
+            && MEM_P (dest))
+     {
+       n_loc = 2;
+       loc_0 = 0;
+       loc_1 = 0;
+       expr = XEXP (dest, 0);
+     }
+   /* reg = zero_extend (mem [ invariant + iv ]).  */
+   else if (REG_P (dest) 
+  	   && GET_CODE (src) == ZERO_EXTEND
+            && MEM_P (XEXP (src, 0)))
+     {
+       n_loc = 3;
+       loc_0 = 1;
+       loc_1 = 0;
+       loc_2 = 0;
+       expr = XEXP (XEXP (src, 0), 0);
+     }
+   else 
+     return NULL;
+   
+   if (GET_CODE (expr) != PLUS)
+     return NULL;
+   
+   lop = XEXP (expr, 0);
+   rop = XEXP (expr, 1);
+   
+   if (!REG_P (lop) || !REG_P (rop))
+     return NULL;
+   
+   insn1 = iv_get_reaching_def (insn, lop);
+   insn2 = iv_get_reaching_def (insn, rop);
+   
+   /* Memory reference is of the form: 
+      invariant + induction variable 
+      or induction variable + invariant.  */
+   if (iv_analyze (insn1, lop, &iv1)
+       && !iv1.first_special
+       && iv_analyze (insn2, rop, &iv2)
+       && !iv2.first_special
+       && ((iv1.step == const0_rtx
+            && iv2.mode == iv2.extend_mode)
+           || (iv2.step == const0_rtx
+               && iv1.mode == iv1.extend_mode)))
+     {
+       if (iv1.step == const0_rtx)
+  	iv = iv2;
+       else
+  	iv = iv1;
+       if (iv.step == NULL_RTX
+  	  || GET_CODE (iv.step) != CONST_INT)
+  	return NULL;
+       if (INTVAL (iv.step) < 0)
+  	return NULL;
+       
+       /* Record the insn.  */
+       ivts = xmalloc (sizeof (struct iv_to_split));
+       ivts->insn = insn;
+       ivts->base_var = NULL_RTX;
+       ivts->step = iv.step;
+       ivts->n_loc = n_loc;
+       ivts->loc[0] = loc_0;
+       ivts->loc[1] = loc_1;
+       ivts->loc[2] = loc_2;
+       return ivts;
+     }
+   return NULL;
+ }
+ 
+ 
  /* Determine whether there is an induction variable in INSN that
     we would like to split during unrolling.  Return NULL if INSN
     contains no interesting IVs.  Otherwise, allocate an IV_TO_SPLIT
*************** analyze_iv_to_split_insn (rtx insn)
*** 1418,1452 ****
  {
    rtx set, dest;
    struct rtx_iv iv;
!   struct iv_to_split *ivts;
! 
!   /* For now we just split the basic induction variables.  Later this may be
!      extended for example by selecting also addresses of memory references.  */
    set = single_set (insn);
    if (!set)
      return NULL;
! 
    dest = SET_DEST (set);
!   if (!REG_P (dest))
!     return NULL;
! 
!   if (!biv_p (insn, dest))
!     return NULL;
! 
!   if (!iv_analyze (insn, dest, &iv))
      abort ();
! 
!   if (iv.step == const0_rtx
!       || iv.mode != iv.extend_mode)
!     return NULL;
! 
!   /* Record the insn to split.  */
!   ivts = xmalloc (sizeof (struct iv_to_split));
!   ivts->insn = insn;
!   ivts->base_var = NULL_RTX;
!   ivts->step = iv.step;
!   ivts->n_loc = 1;
!   ivts->loc[0] = 1;
    
    return ivts;
  }
--- 1548,1583 ----
  {
    rtx set, dest;
    struct rtx_iv iv;
!   struct iv_to_split *ivts = NULL;
!   
    set = single_set (insn);
    if (!set)
      return NULL;
!   
    dest = SET_DEST (set);
!   if (REG_P (dest) 
!       && biv_p (insn, dest)
!       && !iv_analyze (insn, dest, &iv))
      abort ();
!   
!   /* Split basic induction variables if we can.  */
!   if (REG_P (dest)
!       && biv_p (insn, dest)    
!       && iv.step != const0_rtx
!       && iv.mode == iv.extend_mode)
!     {
!       /* Record the insn to split.  */
!       ivts = xmalloc (sizeof (struct iv_to_split));
!       ivts->insn = insn;
!       ivts->base_var = NULL_RTX;
!       ivts->step = iv.step;
!       ivts->n_loc = 1;
!       ivts->loc[0] = 1;
!       return ivts;
!     }
!   /* Check memory references.  */
!   if (flag_split_ivs_in_memref_during_unrolling)
!     ivts = analyze_memory_ref_to_split_iv (insn);
    
    return ivts;
  }
Index: doc/invoke.texi
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.535
diff -c -3 -p -r1.535 invoke.texi
*** doc/invoke.texi	14 Sep 2004 22:30:38 -0000	1.535
--- doc/invoke.texi	14 Oct 2004 10:27:54 -0000
*************** Objective-C and Objective-C++ Dialects}.
*** 316,321 ****
--- 316,322 ----
  -fstrength-reduce  -fstrict-aliasing  -ftracer  -fthread-jumps @gol
  -funroll-all-loops  -funroll-loops  -fpeel-loops @gol
  -fsplit-ivs-in-unroller -funswitch-loops @gol
+ -fsplit-ivs-in-memref-during-unrolling @gol
  -ftree-pre  -ftree-ccp  -ftree-dce -ftree-loop-optimize @gol
  -ftree-loop-linear -ftree-loop-im -ftree-loop-ivcanon -fivopts @gol
  -ftree-dominator-opts -ftree-dse -ftree-copyrename @gol
*************** on some of the architectures due to rest
*** 4710,4715 ****
--- 4711,4721 ----
  
  This optimization is enabled by default.
  
+ @item -fsplit-ivs-in-memref-during-unrolling
+ @opindex fsplit-ivs-in-memref-during-unrolling
+ Same as @option{-fsplit-ivs-in-unroller} for induction variables 
+ used in memory references.
+ 
  @item -fprefetch-loop-arrays
  @opindex fprefetch-loop-arrays
  If supported by the target machine, generate instructions to prefetch

[-- Attachment #3: ChangeLog14_10 --]
[-- Type: application/octet-stream, Size: 601 bytes --]

2004-10-14  Revital Eres  <eres@il.ibm.com>

             * loop-unroll.c: (analyze_memory_ref_to_split_iv):
             New function for determine whether the current
             instruction contains memory reference which uses an
             induction variable.
             (analyze_iv_to_split_insn): Expand the function to
             analyze also instructions of memory references.
             * common.opt: (fsplit-ivs-in-memref-during-unrolling): Add new
             flag.
             * invoke.texi: (fsplit-ivs-in-memref-during-unrolling):
	     Document the new flag.

Re: [Patch] Splitting memory references during unrolling (resubmission)

[David Edelsohn]

	What is the current SPEC performance benefit from this patch?

Thanks, David

Re: [Patch] Splitting memory references during unrolling (resubmission)

[Revital Eres]

David Edelsohn <dje@watson.ibm.com> wrote on 15/10/2004 05:47:41:

>    What is the current SPEC performance benefit from this patch?
> 
> Thanks, David


Hello,

This patch gains ~1% improvements on overall CINTPEC2000 on 
powerpc-linux when the number of times this optimization 
is applied in each loop is restricted to one
(I can add this restriction if this patch will be accepted); 
where gap gains ~5% improvements and bzip2 ~1%.
In CFPPEC2000 there was no significant improvements 
except swim which gained 3% improvement but mesa,
facerec and wupwise show a regression of about 1%
each.

Revital

Re: [Patch] Splitting memory references during unrolling (resubmission)

[David Edelsohn]

	This patch probably should wait for GCC 4.1.

David

Re: [Patch] Splitting memory references during unrolling (resubmission)

[Revital Eres]

> 
> could you please measure the effect of this patch on some benchmark
> on i686 and post results to the mailing list?
> 
> I suspect this optimization might spoil the code there; if this
> turned out to be the case, you would have to restrict it to work
> only on architectures where it is profitable.
> 
> Zdenek

I could not find any significant performance differences while running 
the SPEC benchmarks on the patch and mainline with -O3 and funroll-loops
flags (on i686).

I can add a new flag to enable this optimization if you still have 
concerns 
about it's effect.

Revital

Re: [Patch] Splitting memory references during unrolling (resubmission)

[Zdenek Dvorak]

Hello,

> Following the fix for the unroller patch
> (http://gcc.gnu.org/ml/gcc-patches/2004-08/msg00397.html)
> I resubmit the patch for Splitting memory references during unrolling.
> 
> Bootstrapped (with -funroll-all-loops) & regression tests on POWER4.

could you please measure the effect of this patch on some benchmark
on i686 and post results to the mailing list?

I suspect this optimization might spoil the code there; if this
turned out to be the case, you would have to restrict it to work
only on architectures where it is profitable.

Zdenek

[Patch] Splitting memory references during unrolling (resubmission)

[Revital Eres]

[-- Attachment #1: Type: text/plain, Size: 665 bytes --]

Hello,

I fixed the patch according to your comments. 

The diff file is relative to the splitting induction variables 
patch due to the fact it is not in the mainline yet.

Bootstrapped (with -funroll-all-loops) & regression tests on POWER4.

Revital

 
2004-08-17  Revital Eres  <eres@il.ibm.com>

             * loop-unroll.c: (analyze_memory_ref_containing_iv): 
             New function for determine whether the current 
             instruction contains memory reference which uses an
                 induction variable.
                 (analyze_iv_to_split_insn): Expand the function to
                 analyze also instructions of memory references.



[-- Attachment #2: diff_iv_17_8 --]
[-- Type: application/octet-stream, Size: 4941 bytes --]

This diff is relative to loop-unroll.c file as
was submitted in the patch:
http://gcc.gnu.org/ml/gcc-patches/2004-08/msg00397.html.


111d110
< static struct iv_to_split *analyze_memory_ref_containing_iv (rtx);
1430,1544c1430
< 
< /* Determine whether INSN contains memory reference
<    which uses an induction variable.  If there is a memory 
<    reference a[i] in the loop body it can be transformed  
<    into the following in the unrolled loop, where i is an
<    induction variable and base = &a+i:
<    
<    load 4(base)
<    load 8(base)
<    load 12(base)
<    .
<    .
< */
< static struct iv_to_split *
< analyze_memory_ref_containing_iv (rtx insn)
< {
<   struct iv_to_split *ivts;
<   rtx lop, rop, expr;
<   int n_loc, loc_0, loc_1, loc_2 = -1;
<   rtx set, dest, src;
<   rtx insn1 = NULL_RTX, insn2 = NULL_RTX;
<   struct rtx_iv iv1, iv2, iv;
<   
<   set = single_set (insn);
<   if (!set)
<     return NULL;
<   
<   dest = SET_DEST (set);
<   src = SET_SRC (set);
<   
<   /*  reg = mem [ invariant + iv ] */
<   if ((REG_P (dest)
<        || (GET_CODE (dest) == SUBREG
< 	   && REG_P (SUBREG_REG (dest))))
<       && MEM_P (src))
<     {
<       n_loc = 2;
<       loc_0 = 1;
<       loc_1 = 0;
<       expr =  XEXP (src, 0); 
<     }
<   /* mem [ invariant + iv ] = reg */
<   else if ((REG_P (src)
<             || (GET_CODE (src) == SUBREG
<                 && REG_P (SUBREG_REG (src))))
<            && MEM_P (dest))
<     {
<       n_loc = 2;
<       loc_0 = 0;
<       loc_1 = 0;
<       expr = XEXP (dest, 0);
<     }
<   /* reg = zero_extend (mem [ invariant + iv ]) */
<   else if (GET_CODE (dest) == REG 
< 	   && GET_CODE (src) == ZERO_EXTEND
<            && MEM_P (XEXP (src, 0)))
<     {
<       n_loc = 3;
<       loc_0 = 1;
<       loc_1 = 0;
<       loc_2 = 0;
<       expr = XEXP (XEXP (src, 0), 0);
<     }
<   else 
<     return NULL;
<   
<   if (GET_CODE (expr) != PLUS)
<     return NULL;
<   
<   lop = XEXP (expr, 0);
<   rop = XEXP (expr, 1);
<   
<   if (!REG_P (lop) || !REG_P (rop))
<     return NULL;
<   
<   insn1 = iv_get_reaching_def (insn, lop);
<   insn2 = iv_get_reaching_def (insn, rop);
<   
<   /* Memory reference is of the form: 
<      invariant + induction variable 
<      or induction variable + invariant.  */
<   if (iv_analyze (insn1, lop, &iv1)
<       && !iv1.first_special
<       && iv_analyze (insn2, rop, &iv2)
<       && !iv2.first_special
<       && ((iv1.step == const0_rtx
<            && iv2.mode == iv2.extend_mode)
<           || (iv2.step == const0_rtx
<               && iv1.mode == iv1.extend_mode)))
<     {
<       if (iv1.step == const0_rtx)
< 	iv = iv2;
<       else
< 	iv = iv1;
<       if (iv.step == NULL_RTX
< 	  || GET_CODE (iv.step) != CONST_INT)
< 	return NULL;
<       if (INTVAL (iv.step) < 0)
< 	return NULL;
<       /* Record the insn to split.  */
<       ivts = xmalloc (sizeof (struct iv_to_split));
<       ivts->insn = insn;
<       ivts->base_var = NULL_RTX;
<       ivts->step = iv.step;
<       ivts->n_loc = n_loc;
<       ivts->loc[0] = loc_0;
<       ivts->loc[1] = loc_1;
<       ivts->loc[2] = loc_2;
<       return ivts;
<     }
<   return NULL;
< }
< 
< 
< 
---
>  
1550,1584c1436,1471
< {
<   rtx set, dest;
<   struct rtx_iv iv;
<   struct iv_to_split *ivts;
<   
<   set = single_set (insn);
<   if (!set)
<     return NULL;
<   
<   dest = SET_DEST (set);
<   if (REG_P (dest) 
<       && biv_p (insn, dest)
<       && !iv_analyze (insn, dest, &iv))
<     abort ();
<   
<   /* Split basic induction variables if we can.  */
<   if (REG_P (dest)
<       && biv_p (insn, dest)    
<       && iv.step != const0_rtx
<       && iv.mode == iv.extend_mode)
<     {
<       /* Record the insn to split.  */
<       ivts = xmalloc (sizeof (struct iv_to_split));
<       ivts->insn = insn;
<       ivts->base_var = NULL_RTX;
<       ivts->step = iv.step;
<       ivts->n_loc = 1;
<       ivts->loc[0] = 1;
<       return ivts;
<     }
<   /* Check if we can split memory references.  */
<   ivts = analyze_memory_ref_containing_iv (insn);
<   return ivts;
< }
< 
---
>  {
>    rtx set, dest;
>    struct rtx_iv iv;
>    struct iv_to_split *ivts;
>    
>    /* For now we just split the basic induction variables.  Later this may be
>       extended for example by selecting also addresses of memory references.  */
>    set = single_set (insn);
>    if (!set)
>      return NULL;
>    
>    dest = SET_DEST (set);
>    if (!REG_P (dest))
>      return NULL;
>    
>    if (!biv_p (insn, dest))
>      return NULL;
>    
>    if (!iv_analyze (insn, dest, &iv))
>      abort ();
>    
>    if (iv.step == const0_rtx
>        || iv.mode != iv.extend_mode)
>      return NULL;
>    
>    /* Record the insn to split.  */
>    ivts = xmalloc (sizeof (struct iv_to_split));
>    ivts->insn = insn;
>    ivts->base_var = NULL_RTX;
>    ivts->step = iv.step;
>    ivts->n_loc = 1;
>    ivts->loc[0] = 1;
>    
>    return ivts;
>  }
>  

Re: [Patch] Splitting memory references during unrolling (resubmission)

[Steven Bosscher]

On Monday 09 August 2004 09:14, Steven Bosscher wrote:
> >   if ((REG_P (dest) || GET_MODE (dest) == SUBREG)
> >       && GET_CODE (src) == MEM)
>
> I believe you want GET_CODE here, not GET_MODE.  And when it is a
> SUBREG, you probably want to make sure that SUBREG_REG is a REG.  And
> you can use MEM_P now instead of GET_CODE (src) == MEM.
> So the condition should be:
>
>   if ((REG_P (dest)
>        || (GET_MODE (dest) == SUBREG
Aargh            ^

> 	   && REG_P (SUBREG_REG (dest))))
>       && MEM_P (src))

Never c&p a bad hunk.

  if ((REG_P (dest)
       || (GET_CODE (dest) == SUBREG
	   && REG_P (SUBREG_REG (dest))))
      && MEM_P (src))

Time for instant self-punishment.

Gr.
Steven

Re: [Patch] Splitting memory references during unrolling (resubmission)

[Steven Bosscher]

On Monday 09 August 2004 08:30, Revital Eres wrote:
> Hello,
>
> Following the fix for the unroller patch
> (http://gcc.gnu.org/ml/gcc-patches/2004-08/msg00397.html)
> I resubmit the patch for Splitting memory references during unrolling.
>
> Bootstrapped (with -funroll-all-loops) & regression tests on POWER4.
>
>
> 2004-08-09  Revital Eres  <eres@il.ibm.com>
>
>         * loop-unroll.c: (can_split_memory_ref): New function
>           for determine whether the current instruction
>           contains memory reference which uses an
>           induction variable.
>           (analyze_iv_to_split_insn): Expand the function to
>           analyze also instructions of memory references.

That would be:

	* loop-unroll.c: (can_split_memory_ref): New function
	for determine whether the current instruction
	contains memory reference which uses an
	induction variable.
	(analyze_iv_to_split_insn): Expand the function to
	analyze also instructions of memory references.

Note, different indentation

You should also send the patch as a context diff, cvs diff -c3p ...


> /* Determine whether INSN contains memory references
>    which uses an induction variable. */
>
> static struct iv_to_split *
> can_split_memory_ref (rtx insn)
> {

You make it sound like can_split_memory_ref is some sort of predicate
in the comment preceeding the function, but apparently it also returns
some relevant value.  Can you add to this comment a few more details
about what this function does and returns?

>   if ((REG_P (dest) || GET_MODE (dest) == SUBREG)
>       && GET_CODE (src) == MEM)

I believe you want GET_CODE here, not GET_MODE.  And when it is a
SUBREG, you probably want to make sure that SUBREG_REG is a REG.  And
you can use MEM_P now instead of GET_CODE (src) == MEM.
So the condition should be:

  if ((REG_P (dest)
       || (GET_MODE (dest) == SUBREG
	   && REG_P (SUBREG_REG (dest))))
      && MEM_P (src))

>   else if ((REG_P (src) || GET_MODE (src) == SUBREG)
> 	   && GET_CODE (dest) == MEM)
Same:

  if ((REG_P (src)
       || (GET_MODE (src) == SUBREG
	   && REG_P (SUBREG_REG (src))))
      && MEM_P (dest))


You also do some duplicate work here apparently:
>   if (iv_analyze (insn1, lop, &iv1)
>       && !iv1.first_special
>       && iv_analyze (insn2, rop, &iv2)
>       && !iv2.first_special
>       && iv1.step == const0_rtx
>       && iv2.mode == iv2.extend_mode)
>     {
>       if (iv2.step == NULL_RTX
(...)
>       return ivts;
>     }
>   /*  Memory reference is of the form:
>       induction variable + invariant */
>   if (iv_analyze (insn1, lop, &iv1)
>       && !iv1.first_special
>       && iv_analyze (insn2, rop, &iv2)
>       && !iv2.first_special
>       && iv2.step == const0_rtx
>       && iv1.mode == iv1.extend_mode)
>     {
>       if (iv1.step == NULL_RTX
(...)

As far as I can tell, those if-conditions are identical so you
don't have to evaluate it twice...


<  {
<    rtx set, dest;
<    struct rtx_iv iv;
<    struct iv_to_split *ivts;
<
<    /* For now we just split the basic induction variables.  Later this may be
<       extended for example by selecting also addresses of memory references.  */
<    set = single_set (insn);
<    if (!set)
<      return NULL;
(...)
---
> {
>   rtx set, dest;
>   struct rtx_iv iv;
>   struct iv_to_split *ivts;
>
>   set = single_set (insn);
>   if (!set)
>     return NULL;
>

Why did you remove the comment?
And why did you remove the abort in that hunk if iv_analyze fails?

Gr.
Steven

[Patch] Splitting memory references during unrolling (resubmission)

[Revital Eres]

[-- Attachment #1: Type: text/plain, Size: 619 bytes --]

Hello,

Following the fix for the unroller patch
(http://gcc.gnu.org/ml/gcc-patches/2004-08/msg00397.html)
I resubmit the patch for Splitting memory references during unrolling.

Bootstrapped (with -funroll-all-loops) & regression tests on POWER4.


2004-08-09  Revital Eres  <eres@il.ibm.com>

        * loop-unroll.c: (can_split_memory_ref): New function 
          for determine whether the current instruction 
          contains memory reference which uses an 
          induction variable. 
          (analyze_iv_to_split_insn): Expand the function to 
          analyze also instructions of memory references.



[-- Attachment #2: diff.ivs --]
[-- Type: application/octet-stream, Size: 5009 bytes --]

This diff is relative to loop-unroll.c file as
was submitted in the patch:
http://gcc.gnu.org/ml/gcc-patches/2004-08/msg00397.html.

110a111
> static struct iv_to_split *can_split_memory_ref (rtx);
913d913
< 
1429a1430,1548
> 
> /* Determine whether INSN contains memory references
>    which uses an induction variable. */
> 
> static struct iv_to_split *
> can_split_memory_ref (rtx insn)
> {
>   struct iv_to_split *ivts;
>   rtx lop, rop, expr;
>   int n_loc, loc_0, loc_1, loc_2 = -1;
>   rtx set, dest, src;
>   rtx insn1, insn2;
>   struct rtx_iv iv1, iv2;
>   
>   set = single_set (insn);
>   if (!set)
>     return NULL;
>   
>   dest = SET_DEST (set);
>   src = SET_SRC (set);
>   
>   /*  reg = mem [ invariant + iv ] */
>   if ((REG_P (dest) || GET_MODE (dest) == SUBREG) 
>       && GET_CODE (src) == MEM)
>     {
>       n_loc = 2;
>       loc_0 = 1;
>       loc_1 = 0;
>       expr =  XEXP (src, 0);
>     }
>   /* mem [ invariant + iv ] = reg */
>   else if ((REG_P (src) || GET_MODE (src) == SUBREG) 
> 	   && GET_CODE (dest) == MEM)
>     {
>       n_loc = 2;
>       loc_0 = 0;
>       loc_1 = 0;
>       expr = XEXP (dest, 0);
>     }
>   /* reg = zero_extend (mem [ invariant + iv ]) */
>   else if (GET_CODE (dest) == REG && GET_CODE (src) == ZERO_EXTEND)
>     {
>       if (GET_CODE (XEXP (src, 0)) != MEM)
> 	return NULL;
>       
>       n_loc = 3;
>       loc_0 = 1;
>       loc_1 = 0;
>       loc_2 = 0;
>       expr = XEXP (XEXP (src, 0), 0);
>     }
>   else 
>     return NULL;
>   
>   if (GET_CODE (expr) != PLUS)
>     return NULL;
>   
>   lop = XEXP (expr, 0);
>   rop = XEXP (expr, 1);
>   
>   if (!REG_P (lop) || !REG_P (rop))
>     return NULL;
>   
>   /* Memory reference is of the form: 
>      invariant + induction variable */                             
>   insn1 = iv_get_reaching_def (insn, lop);
>   insn2 = iv_get_reaching_def (insn, rop);
>   
>   if (iv_analyze (insn1, lop, &iv1)
>       && !iv1.first_special
>       && iv_analyze (insn2, rop, &iv2)
>       && !iv2.first_special
>       && iv1.step == const0_rtx
>       && iv2.mode == iv2.extend_mode)
>     {
>       if (iv2.step == NULL_RTX
> 	  || GET_CODE (iv2.step) != CONST_INT)
> 	return NULL;
>       if (INTVAL (iv2.step) < 0)
> 	return NULL;
>       ivts = xmalloc (sizeof (struct iv_to_split));
>       ivts->insn = insn;
>       ivts->base_var = NULL_RTX;
>       ivts->step = iv2.step;
>       ivts->n_loc = n_loc;
>       ivts->loc[0] = loc_0;
>       ivts->loc[1] = loc_1;
>       ivts->loc[2] = loc_2;
>       return ivts;
>     }
>   
>   /*  Memory reference is of the form: 
>       induction variable + invariant */    
>   if (iv_analyze (insn1, lop, &iv1)
>       && !iv1.first_special
>       && iv_analyze (insn2, rop, &iv2)
>       && !iv2.first_special
>       && iv2.step == const0_rtx
>       && iv1.mode == iv1.extend_mode)
>     {
>       if (iv1.step == NULL_RTX
> 	  || GET_CODE (iv1.step) != CONST_INT)
>         return NULL;
>       if (INTVAL (iv1.step) < 0)
> 	return NULL;
>       ivts = xmalloc (sizeof (struct iv_to_split));
>       ivts->insn = insn;
>       ivts->base_var = NULL_RTX;
>       ivts->step = iv1.step;
>       ivts->n_loc = n_loc;
>       ivts->loc[0] = loc_0;
>       ivts->loc[1] = loc_1;
>       ivts->loc[2] = loc_2;      
>       return ivts;
>     }
>   return NULL;
> }
> 
> 
1436,1470c1555,1585
<  {
<    rtx set, dest;
<    struct rtx_iv iv;
<    struct iv_to_split *ivts;
<    
<    /* For now we just split the basic induction variables.  Later this may be
<       extended for example by selecting also addresses of memory references.  */
<    set = single_set (insn);
<    if (!set)
<      return NULL;
<    
<    dest = SET_DEST (set);
<    if (!REG_P (dest))
<      return NULL;
<    
<    if (!biv_p (insn, dest))
<      return NULL;
<    
<    if (!iv_analyze (insn, dest, &iv))
<      abort ();
<    
<    if (iv.step == const0_rtx
<        || iv.mode != iv.extend_mode)
<      return NULL;
<    
<    /* Record the insn to split.  */
<    ivts = xmalloc (sizeof (struct iv_to_split));
<    ivts->insn = insn;
<    ivts->base_var = NULL_RTX;
<    ivts->step = iv.step;
<    ivts->n_loc = 1;
<    ivts->loc[0] = 1;
<    
<    return ivts;
<  }
---
> {
>   rtx set, dest;
>   struct rtx_iv iv;
>   struct iv_to_split *ivts;
>   
>   set = single_set (insn);
>   if (!set)
>     return NULL;
>   
>   dest = SET_DEST (set);
>   
>   /* Split basic induction variables if we can. */
>   if (REG_P (dest)
>       && biv_p (insn, dest)
>       && iv_analyze (insn, dest, &iv)
>       && iv.step != const0_rtx
>       && iv.mode == iv.extend_mode)
>     {
>       /* Record the insn to split.  */
>       ivts = xmalloc (sizeof (struct iv_to_split));
>       ivts->insn = insn;
>       ivts->base_var = NULL_RTX;
>       ivts->step = iv.step;
>       ivts->n_loc = 1;
>       ivts->loc[0] = 1;
>       return ivts;
>     }
>   /* Check if we can split memory references. */
>   ivts = can_split_memory_ref (insn);
>   return ivts;
> }