[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" <gcc-bugzilla at gcc dot gnu dot org>]

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