[Bug rtl-optimization/20376] New: The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[Bug rtl-optimization/20376] New: The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[canqun at nudt dot edu dot cn]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2577 bytes --]

Induction variables are variables whose successive values form an arithmetic 
progression over a loop. Induction variables are often divided into bivs 
(basic induction variables), which are explicitly modified by 
the same constant amount during each iteration of a loop, and gives (general 
induction variables), which may be modified or computed by a linear-function 
of a basic induction variable. 

There are three important transformations that apply to them: strength 
reduction, induction-variable removal, and linear-function test replacement. 
For example, we can do strength reduction of address givs which are usually 
used for address calculation of array elements. On platforms with post-
increment load and store instructions, this will make chance to combine a 
load/store with the following address calculation instruction.

Also the induction variable splitting is an effective optimization during loop 
unrolling.

The new loop optimizer only support a limited gives analysis (ref. loop-iv.c), 
and has not yet implemented giv strength reduction and splitting (ref. ¡®loop-
unroll.c¡¯, ¡®analyze_iv_to_split_insn¡¯, and comments in this function, ¡°For 
now we just split the basic induction 
variables. Later this may be extended for example by selecting also addresses 
of memory references.¡±)

I test 171.swim on IA64 Linux system with 1GHz itanium2 CPU. After implemented 
or improved/adjusted several compile optimizations, such as Fortran alias 
analysis (very simple one), loop unrolling (the old one), loop arrays pre-
fetching, and giv optimizations, it costs just 9.1s (28s for GCC-4.0.0) to 
execute the train mode of 171.swim. But, apply those changes on current GCC-
4.0.0 (the old loop unroller was removed), it costs 
13.4 to execute this benchmark program, and I found that giv optimizations are 
the major factor of such performance degradation.

-- 
           Summary: The missed-optimization of general induction variables
                    in the new rtl-level loop optimizer cause performance
                    degradation.
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: canqun at nudt dot edu dot cn
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: ia64-unknown-linux
  GCC host triplet: ia64-unknown-linux
GCC target triplet: ia64-unknown-linux


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-08 03:13 -------
Why isn't the tree level loop IV-OPTs doing this?

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

Re: [Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[Diego Novillo]

pinskia at gcc dot gnu dot org wrote:

> Why isn't the tree level loop IV-OPTs doing this?
> 
Because variable i is static.

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[dnovillo at redhat dot com]

------- Additional Comments From dnovillo at redhat dot com  2005-03-08 03:16 -------
Subject: Re:  The missed-optimization of general
 induction variables in the new rtl-level loop optimizer cause performance
 degradation.

pinskia at gcc dot gnu dot org wrote:

> Why isn't the tree level loop IV-OPTs doing this?
> 
Because variable i is static.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[pinskia at physics dot uc dot edu]

------- Additional Comments From pinskia at physics dot uc dot edu  2005-03-08 03:18 -------
Subject: Re:  The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.


On Mar 7, 2005, at 10:16 PM, Diego Novillo wrote:

> pinskia at gcc dot gnu dot org wrote:
>
>> Why isn't the tree level loop IV-OPTs doing this?
> Because variable i is static.

I think you commenting on the wrong bug.

-- Pinski



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

Re: [Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[Andrew Pinski]

On Mar 7, 2005, at 10:16 PM, Diego Novillo wrote:

> pinskia at gcc dot gnu dot org wrote:
>
>> Why isn't the tree level loop IV-OPTs doing this?
> Because variable i is static.

I think you commenting on the wrong bug.

-- Pinski

Re: [Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[Diego Novillo]

Andrew Pinski wrote:

> I think you commenting on the wrong bug.
> 
Indeed.  I misread 20376 as 20367.  Sorry about that.

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[dnovillo at redhat dot com]

------- Additional Comments From dnovillo at redhat dot com  2005-03-08 03:20 -------
Subject: Re:  The missed-optimization of general
 induction variables in the new rtl-level loop optimizer cause performance
 degradation.

Andrew Pinski wrote:

> I think you commenting on the wrong bug.
> 
Indeed.  I misread 20376 as 20367.  Sorry about that.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

Re: [Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[Daniel Berlin]

On Tue, 2005-03-08 at 03:18 +0000, pinskia at physics dot uc dot edu
wrote:
> ------- Additional Comments From pinskia at physics dot uc dot edu  2005-03-08 03:18 -------
> Subject: Re:  The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.
> 
> 
> On Mar 7, 2005, at 10:16 PM, Diego Novillo wrote:
> 
> > pinskia at gcc dot gnu dot org wrote:
> >
> >> Why isn't the tree level loop IV-OPTs doing this?
> > Because variable i is static.
> 
> I think you commenting on the wrong bug.

In swim, most of the loop bounds are accessed through the COMMON block,
which is a structure.

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-03-08 03:30 -------
Subject: Re:  The missed-optimization of
	general induction variables in the new rtl-level loop optimizer cause
	performance degradation.

On Tue, 2005-03-08 at 03:18 +0000, pinskia at physics dot uc dot edu
wrote:
> ------- Additional Comments From pinskia at physics dot uc dot edu  2005-03-08 03:18 -------
> Subject: Re:  The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.
> 
> 
> On Mar 7, 2005, at 10:16 PM, Diego Novillo wrote:
> 
> > pinskia at gcc dot gnu dot org wrote:
> >
> >> Why isn't the tree level loop IV-OPTs doing this?
> > Because variable i is static.
> 
> I think you commenting on the wrong bug.

In swim, most of the loop bounds are accessed through the COMMON block,
which is a structure.




-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[sje at cup dot hp dot com]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sje at cup dot hp dot com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-03-27 10:19 -------
Two things: 
1) Test case?  No test case, no way to reproduce it without re-doing the 
   investigating you have already done.  Stop work duplication, provide 
   test cases to your fellow GCC hackers.  I don't think anyone will 
   confirm this bug until there is a self-contained test case (that you 
   can add to this PR as an attachment), preferably with an annotated RTL 
   dump to show the problem (also as an attachment).  See also the bug 
   reporting guide, "http://gcc.gnu.org/bugs.html#report". 
2) Try compiling with -fweb, it may result in the code you are looking 
   for.  It basically is live range splitting, and it is a known problem 
   that we don't do that after unrolling.  Really, his is a job for the 
   register allocator, but since the existing one in GCC can not do this, 
   we need a live range splitting pass after unrolling. (And no, we do 
   not need this pass in the general case because when going out of SSA 
   form from trees we already do live range splitting too, and web is a 
   surprisingly expensive pass). 
 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |stevenb at suse dot de


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-03-30 11:38 -------
Waiting for a test case...

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[canqun at nudt dot edu dot cn]

------- Additional Comments From canqun at nudt dot edu dot cn  2005-03-30 14:42 -------
(In reply to comment #7)
> Waiting for a test case...

Part 1
! Test sase for address giv (general induction variable) optimization.
subroutine dot_product (sum, a, b, n)
   real*8 a(n), b(n), sum
   sum = 0
   do i = 1, n
     sum = sum + a (i) * b(i)
   end do
end

Part 2
// IA-64 Assembly code generated by GCC without address giv splitting
        mov ar.lc = r14
.L4:
// Loop is unrolled, but the address givs are not splitted.
// Register r17, r19 is used to calculate all the addresses
// of the array elements.
        .mmb
        ldfd f7 = [r17]
        ldfd f6 = [r19]
        nop 0
        .mmi
        add r17 = r15, r33
        add r19 = r15, r34
        shladd r15 = r18, 3, r0
        ;;
        .mmf
        nop 0
        nop 0
        fma.d f8 = f7, f6, f9
        .mmi
        ldfd f7 = [r17]
        ldfd f6 = [r19]
        add r17 = r15, r33
        .mfi
     nop 0
        shladd r15 = r16, 3, r0
        ;;
        .mmf
        nop 0
        nop 0
        fma.d f8 = f7, f6, f8
        .mmi
        ldfd f7 = [r17]
        ldfd f6 = [r19]
        add r17 = r15, r33
        .mmb
        nop 0
        add r19 = r15, r34
        nop 0
        ;;
        .mmf
        nop 0
        nop 0
        fma.d f8 = f7, f6, f8
        .mmb
        ldfd f7 = [r17]
        ldfd f6 = [r19]
        nop 0
        ;;
        .mmf
        nop 0
        nop 0
        fma.d f8 = f7, f6, f8
        ;;
        .mfb
        nop 0
        mov f9 = f8
        br.cloop.sptk.few .L4
        ...
        .endp dot_product__#
        .ident  "GCC: (GNU) 4.1.0 20050302 (experimental)"

Part 3
// IA-64 assembly code generated by GCC with address giv splitting
        mov ar.lc = r16
.L28:
[.L3:]
[.L2:]
        ...
// The loop is unrolled, and the address givs are splitted.
// Register r14, r8, r3, r35, r33, r31,r28, r29 is used to
// caculate the address of each array element respectively.
        .mmi
        ldfd f38 = [r14]
        ldfd f39 = [r8]
        add r31 = r34, r23
        .mmi
        ldfd f35 = [r3]
        ldfd f37 = [r35]
        add r33 = r34, r24
        ;;
        .mmb
        ldfd f33 = [r33]
        ldfd f34 = [r31]
        nop 0
        .mmi
        add r28 = r30, r23
        add r29 = r30, r24
        adds r22 = 4, r22
        ;;
        .mmf
        ldfd f32 = [r29]
        ldfd f15 = [r28]
        fma.d f36 = f38, f39, f14
        ;;
        .mmf
        nop 0
        nop 0
        fma.d f13 = f35, f37, f36
        ;;
        .mmf
        nop 0
        nop 0
        fma.d f12 = f33, f34, f13
        ;;
        .mfb
        nop 0
        fma.d f14 = f32, f15, f12
        br.cloop.sptk.few .L28
        ;;
.L9:
        .mfb
        stfd [r32] = f14
        nop 0
        nop 0
        ...
        .endp dot_product__#
        .ident  "GCC: (GNU) 3.5-tree-ssa 20031221 (CCRG)"

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[steven at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-03-30 19:54:01
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2005-06-24 16:39 -------
Induction variable splitting works as expected (note that r17 and r19 from each 
iteration are computed independently, so they should not block scheduling).

Iv splitting does not rename the variables in different iterations of the 
unrolled loop directly.  But you will get this if you also use -fweb.

Note however that even with -fweb you won't get the code you would like,
simply because register allocator decides to put all the new registers back
into one (which is ok, since their life ranges do not overlap).

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2005-06-24 16:56 -------
Actually, with -funroll-loops -fweb -frename-registers you get the code you 
want.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-06-26 12:12 -------
But there are bugs about -frename-registers being slow and broken, see 
PR15023.  It looks to me like the issues from that bug report may be 
fixed already, but someone should verify this. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |15023


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-07-13 09:38 -------
Subject: Bug 20376

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	rakdver@gcc.gnu.org	2005-07-13 09:38:49

Modified files:
	gcc            : ChangeLog toplev.c 
	gcc/doc        : invoke.texi 

Log message:
	PR rtl-optimization/20376
	* toplev.c (process_options): Enable -fweb and -frename-registers when
	unrolling.
	* doc/invoke.texi: Update the information about when -fweb and
	-frename-registers are enabled.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.9426&r2=2.9427
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/toplev.c.diff?cvsroot=gcc&r1=1.969&r2=1.970
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/doc/invoke.texi.diff?cvsroot=gcc&r1=1.647&r2=1.648



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-07-13 11:38 -------
Fixed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
           Keywords|                            |missed-optimization
         Resolution|                            |FIXED
   Target Milestone|---                         |4.1.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376

[Bug rtl-optimization/20376] The missed-optimization of general induction variables in the new rtl-level loop optimizer cause performance degradation.

[canqun at nudt dot edu dot cn]

------- Additional Comments From canqun at nudt dot edu dot cn  2005-07-14 15:25 -------
(In reply to comment #13)
> Fixed.

Performance test on IA-64 recently show that loop unrolling with '-fweb' and '-
frename-registers" turned on can take nearly the same effectiveness as with 
the giv splitting.

Very thanks to Steven Bosscher, Zdenek Dvorak, Andrew Pinski, and all other 
GCC developers.

Canqun Yang

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20376