[Bug rtl-optimization/32283] New: Missed induction variable optimization

[Bug rtl-optimization/32283] New: Missed induction variable optimization

[pranav dot bhandarkar at gmail dot com]

Consider the following code snippet

static volatile short a[(2048)];
short foo (int len, int v)
{
  int i;
  for (i = 0; i < len; i++) {
    a[i] = v;
  }
  return a[0];
}

This should generate a post_inc for accessing elements of a. The problem  seems
to be in the loop optimizer that fails to identify 'i' as an induction
variable. For e.g the dump from 141r.loop2_invariant shows 

(insn 16 15 75 4 (set (reg/v:SI 103 [ i ])
        (const_int 0 [0x0])) 161 {*arm_movsi_insn} (nil))

(insn 75 16 17 4 (set (reg/f:SI 118)
        (symbol_ref:SI ("^a") [flags 0x2] <var_decl 0xb7dc1000 a>)) -1 (nil))

(code_label 17 75 18 5 4 "" [0 uses])

(note 18 17 21 5 [bb 5] NOTE_INSN_BASIC_BLOCK)

(insn 21 18 23 5 (set (reg:SI 110)
        (ashift:SI (reg/v:SI 103 [ i ])
            (const_int 1 [0x1]))) 115 {*arm_shiftsi3} (nil))

(insn 23 21 25 5 (set (mem/s/v:HI (plus:SI (reg:SI 110)
                (reg/f:SI 118)) [3 a S2 A16])
        (subreg/s/u:HI (reg:SI 102 [ pretmp.21 ]) 0)) 171 {*movhi_insn_arch4}
(nil))

(insn 25 23 26 5 (set (reg/v:SI 103 [ i ])
        (plus:SI (reg/v:SI 103 [ i ])
            (const_int 1 [0x1]))) 4 {*arm_addsi3} (nil))

(insn 26 25 27 5 (set (reg:CC 24 cc)
        (compare:CC (reg/v:SI 106 [ len ])
            (reg/v:SI 103 [ i ]))) 214 {*arm_cmpsi_insn} (nil))

(jump_insn 27 26 82 5 (set (pc)
        (if_then_else (gt (reg:CC 24 cc)
                (const_int 0 [0x0]))
            (label_ref:SI 82)
            (pc))) 224 {*arm_cond_branch} (expr_list:REG_BR_PROB (const_int
9900 [0x26ac])
        (nil)))

Here reg 103 i.e 'i' is incremented by 1 always and therefore 110 always
increases by 2 which means that in each iteration the address in INSN 23 is 2
more than what it was in the previous iteration. If the access is converted
into something like
*118 = v
118 += 2, 
then the auto-inc-dec pass will be able to convert this into a post_inc


Version Details:
GNU C version 4.3.0 20070316 (experimental) (arm-none-eabi)
        compiled by GNU C version 3.4.6 (Ubuntu 3.4.6-1ubuntu2).
GGC heuristics: --param ggc-min-expand=30 --param ggc-min-heapsize=4096


-- 
           Summary: Missed induction variable optimization
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pranav dot bhandarkar at gmail dot com
GCC target triplet: arm-none-eabi


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[pranav dot bhandarkar at gmail dot com]

------- Comment #1 from pranav dot bhandarkar at gmail dot com  2007-06-11 13:45 -------
Created an attachment (id=13676)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13676&action=view)
Testcase displaying the said behaviour

Added testcase that exposes the problem


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2007-06-11 14:06 -------
What if you remove the pointless 'volatile' from a?


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[pranav dot bhandarkar at gmail dot com]

------- Comment #3 from pranav dot bhandarkar at gmail dot com  2007-06-11 14:33 -------
(In reply to comment #2)
> What if you remove the pointless 'volatile' from a?
> 

No, removing the 'volatile' doesnt help either. The 'volatile' was because this
is part of a bigger test.


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[pinskia at gcc dot gnu dot org]

------- Comment #4 from pinskia at gcc dot gnu dot org  2007-06-11 18:45 -------
Note this is most likely a dup of another bug which is talking about PPC. 


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[pranav dot bhandarkar at gmail dot com]

------- Comment #5 from pranav dot bhandarkar at gmail dot com  2007-06-13 12:36 -------
Which RTL pass should take care of such induction variable optimization in 4.3
? For e.g In 4.1, It was old-loop that was doing it.


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[pinskia at gcc dot gnu dot org]

------- Comment #6 from pinskia at gcc dot gnu dot org  2007-06-13 17:53 -------
Look at PR 17108 also.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |17108


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[pranav dot bhandarkar at gmail dot com]

------- Comment #7 from pranav dot bhandarkar at gmail dot com  2007-06-14 20:50 -------
I guess strength reduction should then be implemented at the RTL level ?


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[pranav dot bhandarkar at gmail dot com]

------- Comment #8 from pranav dot bhandarkar at gmail dot com  2007-08-24 13:28 -------
Created an attachment (id=14102)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14102&action=view)
Another testcase displaying the said behaviour

IMHO, the code generated for the following can benefit from Strength reduction.
It will be possible to generate post_inc due to strength reduction.

for (dp = i = 0; i < c; i++) {
    dp += a[i] * b[i];
  }

The RTL code generated for the loop is of the form ( numbers represent pseudo
reg numbers)
137 and 136 hold the base addresses of the two arrays before entry into the
loop.
132  = 0 ;  #i,
133 = 132 ; #dp
Label:
139  = *(137 + 132)
140 = *(136 + 132)
141 = 140 * 139
133 += 141 ;#dp
132 += 2
conditional_jump back to Label.


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[ramana dot radhakrishnan at celunite dot com]

------- Comment #9 from ramana dot radhakrishnan at celunite dot com  2007-09-05 11:46 -------
The above mentioned testcase works ok and generates auto-increments in Comment
#8 . I'd still be interested in looking at why the volatile case cannot work. 

Adding Zdenek to the CC for this case. 


-- 

ramana dot radhakrishnan at celunite dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at atrey dot karlin
                   |                            |dot mff dot cuni dot cz


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[rakdver at gcc dot gnu dot org]

------- Comment #10 from rakdver at gcc dot gnu dot org  2007-09-06 17:57 -------
I'm testing a patch.


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rakdver at gcc dot gnu dot
                   |dot org                     |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-09-06 17:57:43
               date|                            |


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[rakdver at gcc dot gnu dot org]

------- Comment #11 from rakdver at gcc dot gnu dot org  2007-09-08 13:19 -------
Subject: Bug 32283

Author: rakdver
Date: Sat Sep  8 13:18:49 2007
New Revision: 128272

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=128272
Log:
        PR tree-optimization/32283
        * tree-ssa-loop-ivopts.c (may_eliminate_iv): Use
        estimated_loop_iterations.
        (determine_use_iv_cost_condition): Decrease cost of expressions
        used in iv elimination.

        * gcc.dg/tree-ssa/loop-31.c: New test.


Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-31.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-loop-ivopts.c


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[dje at gcc dot gnu dot org]

------- Comment #12 from dje at gcc dot gnu dot org  2007-09-10 18:29 -------
Created an attachment (id=14185)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14185&action=view)
postreload.c preprocessed

The patch broke bootstrap on powerpc-aix, powerpc-darwin, sparc-solaris, and
hpux -- probably all big endian targets.  reload_combine_note_store is
miscompiled.


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[amonakov at gmail dot com]

------- Comment #13 from amonakov at gmail dot com  2007-09-20 16:25 -------
This patch sometimes confuses loop2_doloop.  On ia64 this prevents use of
countable loop branch machine idiom (br.cloop).  On the example used in this
thread loop2_doloop complains:

Loop 1 is simple:
  simple exit 5 -> 6
  infinite if: (expr_list:REG_DEP_TRUE (subreg:SI (and:DI (plus:DI (minus:DI
(reg:DI 391)
                    (reg:DI 370 [ ivtmp.16 ]))
                (const:DI (plus:DI (symbol_ref:DI ("a") [flags 0x2] <var_decl
0x2aaaaabd7000 a>)
                        (const_int -2 [0xfffffffffffffffe]))))
            (const_int 1 [0x1])) 0)
    (nil))       
  number of iterations: (lshiftrt:DI (plus:DI (minus:DI (reg:DI 392)
            (reg:DI 370 [ ivtmp.16 ]))
        (const_int -2 [0xfffffffffffffffe]))
    (const_int 1 [0x1]))
  upper bound: -1
Doloop: Possible infinite iteration case.
Doloop: The loop is not suitable.

The "infinite if" condition is:
((r391 - r370) + ('a' - 2)) & 1 == 1
where r370 is &(a[i]) and r391 is len*sizeof(a[0]), so that r391+'a' is
&a[len].  Of course, such "infinite if" condition is always false, but
loop2_doloop does not see that.


-- 

amonakov at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amonakov at gmail dot com


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[ramana dot radhakrishnan at celunite dot com]

------- Comment #14 from ramana dot radhakrishnan at celunite dot com  2007-11-27 11:00 -------
(In reply to comment #13)
> This patch sometimes confuses loop2_doloop.  On ia64 this prevents use of
> countable loop branch machine idiom (br.cloop).  On the example used in this
> thread loop2_doloop complains:
> 
> Loop 1 is simple:
>   simple exit 5 -> 6
>   infinite if: (expr_list:REG_DEP_TRUE (subreg:SI (and:DI (plus:DI (minus:DI
> (reg:DI 391)
>                     (reg:DI 370 [ ivtmp.16 ]))
>                 (const:DI (plus:DI (symbol_ref:DI ("a") [flags 0x2] <var_decl
> 0x2aaaaabd7000 a>)
>                         (const_int -2 [0xfffffffffffffffe]))))
>             (const_int 1 [0x1])) 0)
>     (nil))       
>   number of iterations: (lshiftrt:DI (plus:DI (minus:DI (reg:DI 392)
>             (reg:DI 370 [ ivtmp.16 ]))
>         (const_int -2 [0xfffffffffffffffe]))
>     (const_int 1 [0x1]))
>   upper bound: -1
> Doloop: Possible infinite iteration case.
> Doloop: The loop is not suitable.
> 
> The "infinite if" condition is:
> ((r391 - r370) + ('a' - 2)) & 1 == 1
> where r370 is &(a[i]) and r391 is len*sizeof(a[0]), so that r391+'a' is
> &a[len].  Of course, such "infinite if" condition is always false, but
> loop2_doloop does not see that.
> 

This is pretty much the case that causes things to go worse even on the private
port I work on after this patch.

Debugging this on ia64 or my port shows the same point at which this detection
fails,  though mine would fail for the SI case rather than the DI case.

The infinite if case is detected in loop_iv.c : iv_number_of_iterations when it
can't simplify the above mentioned expression. I looked through tree-ssa-ivopts
but I can't see how this can get fixed there unless we change it in loop_iv.c . 

I wonder if we could use DF info to recursively figure out the reaching
definition at insn of r391 and r370 and substitute the RHS in this to simplify
this further.  

However whether that effort would be worthwhile depends on the number of such
cases that we detect in any useful benchmark. My guess is that since this is a
pretty normal construct we'd find it in quite a number of loops that are rather
self-respecting.


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[amonakov at gmail dot com]

------- Comment #15 from amonakov at gmail dot com  2007-12-05 16:26 -------
Zdenek,

please kindly share your thoughts on concerns expressed in previous comments. 
The failures of number-of-iterations analysis prohibit applying modulo
scheduling to many simple loops that are otherwise eligible; in fact, I now
test SMS with either your patch reverted, or with -funsafe-loop-optimizations,
but I believe this is not a healthy state.

Please correct me if I am wrong, but I think that optimizing out the variable
that holds number of iterations is not desirable on targets that have doloop
machine idiom, because doloop rtl pass will re-introduce it in a specially
designated register.  However, ia64 does not allow arithmetic operations with
loop counter, so it would be nice if iv-opts transformed the loop to the form
where decrement-and-branch-on-zero are the only uses of this variable, when
possible. 


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[rakdver at kam dot mff dot cuni dot cz]

------- Comment #16 from rakdver at kam dot mff dot cuni dot cz  2007-12-05 16:42 -------
Subject: Re:  Missed induction variable optimization

> Please correct me if I am wrong, but I think that optimizing out the variable
> that holds number of iterations is not desirable on targets that have doloop
> machine idiom, because doloop rtl pass will re-introduce it in a specially
> designated register.  However, ia64 does not allow arithmetic operations with
> loop counter, so it would be nice if iv-opts transformed the loop to the form
> where decrement-and-branch-on-zero are the only uses of this variable, when
> possible. 

On the other hand, performing induction variable elimination is also
clearly desirable, as doloop idiom cannot be applied in many common
cases.  At the moment, it does not seem feasible to introduce enough
target knowledge to ivopts to ensure that it can determine whether
it will be possible to determine whether the doloop pattern can be used.

I have no real idea how to solve this problem.  Probably the cleanest
way would be to somehow preserve the information about the number of
iterations of the loop determined on trees, and pass it to doloop, but
we lack the means to do that reliably.


-- 


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

[Bug rtl-optimization/32283] Missed induction variable optimization

[rakdver at gcc dot gnu dot org]

------- Comment #17 from rakdver at gcc dot gnu dot org  2007-12-16 20:29 -------
A possible way how to solve the problem:
http://gcc.gnu.org/ml/gcc-patches/2007-12/msg00769.html


-- 


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

[Bug rtl-optimization/32283] [4.3/4.4 regression] Missed induction variable optimization

[dje at gcc dot gnu dot org]

------- Comment #18 from dje at gcc dot gnu dot org  2008-10-30 14:49 -------
GCC no longer generates branch on count instructions on PowerPC.


-- 

dje at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
 GCC target triplet|arm-none-eabi               |arm-none-eabi,powerpc-linux
           Priority|P3                          |P1
            Summary|Missed induction variable   |[4.3/4.4 regression] Missed
                   |optimization                |induction variable
                   |                            |optimization
   Target Milestone|---                         |4.4.0


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

[Bug rtl-optimization/32283] [4.3/4.4 regression] Missed induction variable optimization

[rguenth at gcc dot gnu dot org]

------- Comment #19 from rguenth at gcc dot gnu dot org  2008-10-30 16:30 -------
Can someone please specify a Known-to-work version?


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
           Keywords|                            |missed-optimization
           Priority|P1                          |P3
   Target Milestone|4.4.0                       |4.3.3


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

[Bug rtl-optimization/32283] [4.3/4.4 regression] Missed induction variable optimization

[janis at gcc dot gnu dot org]

------- Comment #20 from janis at gcc dot gnu dot org  2008-10-30 16:46 -------
To add to comment #18, after r128272 GCC for powerpc-linux no longer generates
bdnz for:

int reg_values[1024];
void
clear_table (unsigned int n)
{
  unsigned int i;
  for (i = 0; i < n; i++)
    reg_values[i] = 0;
}

The patch referenced in comment #17, applied to current 4.3 branch, generates
that instruction again for this test but causes gfortran to segfault often.

As for comment #19, known to work for which particular testcase?


-- 


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

[Bug rtl-optimization/32283] [4.3/4.4 regression] Missed induction variable optimization

[rguenth at gcc dot gnu dot org]

------- Comment #21 from rguenth at gcc dot gnu dot org  2008-10-30 16:55 -------
Known-to-work for whatever testcase you want to see this PR as a regression. 
As it sounds that this problem comes and goes for different testcases in
different releases more testing coverage in the testsuite would probably a good
idea, even
for cases where it works now.


-- 


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

[Bug rtl-optimization/32283] [4.3/4.4 regression] Missed induction variable optimization

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2


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

[Bug rtl-optimization/32283] [4.3/4.4 regression] Missed induction variable optimization

[rakdver at gcc dot gnu dot org]

------- Comment #22 from rakdver at gcc dot gnu dot org  2008-11-17 03:44 -------
(In reply to comment #20)
> To add to comment #18, after r128272 GCC for powerpc-linux no longer generates
> bdnz for:
> ...

A patch for this testcase:
http://gcc.gnu.org/ml/gcc-patches/2008-11/msg00792.html


-- 


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

[Bug rtl-optimization/32283] [4.3/4.4 regression] Missed induction variable optimization

[rakdver at gcc dot gnu dot org]

------- Comment #23 from rakdver at gcc dot gnu dot org  2008-11-20 08:06 -------
Subject: Bug 32283

Author: rakdver
Date: Thu Nov 20 08:05:12 2008
New Revision: 142035

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=142035
Log:
        PR rtl-optimization/32283
        * tree-ssa-loop-niter.c (scev_probably_wraps_p): Use type of the base
        of the induction variable to decide whether it may wrap.
        * tree-ssa-loop-ivopts.c (rewrite_use_compare): Emit the initialization
        of the bound before the loop.
        * simplify-rtx.c (simplify_binary_operation_1): Add two simplifications
        regarding AND.
        (simplify_plus_minus): Only fail if no simplification is possible.
        * loop-iv.c (simple_rhs_p): Consider reg + reg and reg << cst simple.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/loop-iv.c
    trunk/gcc/simplify-rtx.c
    trunk/gcc/tree-ssa-loop-ivopts.c
    trunk/gcc/tree-ssa-loop-niter.c


-- 


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

[Bug rtl-optimization/32283] [4.3/4.4 regression] Missed induction variable optimization

[cnstar9988 at gmail dot com]

------- Comment #24 from cnstar9988 at gmail dot com  2008-12-22 05:57 -------
ping...
4.3.3


-- 

cnstar9988 at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |cnstar9988 at gmail dot com


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

[Bug rtl-optimization/32283] [4.3/4.4 regression] Missed induction variable optimization

[ramana at icerasemi dot com]

------- Comment #25 from ramana at icerasemi dot com  2009-01-15 10:34 -------
Redo CC addresses.


-- 

ramana at icerasemi dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|ramana at icerasemi dot com |ramana dot r at gmail dot
                   |                            |com


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

[Bug rtl-optimization/32283] [4.3/4.4 regression] Missed induction variable optimization

[rguenth at gcc dot gnu dot org]

------- Comment #26 from rguenth at gcc dot gnu dot org  2009-01-24 10:19 -------
GCC 4.3.3 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.3                       |4.3.4


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

[Bug rtl-optimization/32283] [4.3/4.4/4.5 regression] Missed induction variable optimization

[rguenth at gcc dot gnu dot org]

------- Comment #27 from rguenth at gcc dot gnu dot org  2009-08-04 12:28 -------
GCC 4.3.4 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.4                       |4.3.5


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

[Bug rtl-optimization/32283] [4.3/4.4/4.5 regression] Missed induction variable optimization

[amonakov at gcc dot gnu dot org]

------- Comment #28 from amonakov at gcc dot gnu dot org  2010-03-16 15:26 -------
To provide an update of the situation on 4.5 trunk:
AFAIK the situation has been generally improved with Zdenek's second commit (in
comment #23) and auto-inc-dec improvements in 4.5.  However, on the particular
testcase discussed here (comment #20), we still don't DTRT on ia64 (powerpc is
OK, don't know about arm).  There is unfortunate interplay between IVOPTS, RTL
PRE, RTL loop analysis and the auto-inc-dec pass.

First, ivopts produce harder-to-grok sequence in loop preheader, transforming
<bb 3>:
  pretmp.2_8 = (short int) v_4(D);

<bb 4>:
  # i_13 = PHI <i_6(5), 0(3)>
  a[i_13] = pretmp.2_8;
  i_6 = i_13 + 1;
  if (len_3(D) > i_6)
    goto <bb 5>;
  else
    goto <bb 6>;

<bb 5>:
  goto <bb 4>;

to

<bb 3>:
  pretmp.2_8 = (short int) v_4(D);
  ivtmp.7_11 = (long unsigned int) &a[0];
  D.2006_17 = (unsigned int) len_3(D);
  D.2007_18 = D.2006_17 + 4294967295;
  D.2008_19 = (long unsigned int) D.2007_18;
  D.2009_20 = D.2008_19 * 2;
  a.13_21 = (long unsigned int) &a;
  D.2011_22 = a.13_21 + 2;
  D.2012_23 = D.2009_20 + D.2011_22;

<bb 4>:
  # ivtmp.7_1 = PHI <ivtmp.7_12(5), ivtmp.7_11(3)>
  D.2005_16 = (void *) ivtmp.7_1;
  MEM[base: D.2005_16]{a[i]} = pretmp.2_8;
  ivtmp.7_12 = ivtmp.7_1 + 2;
  if (ivtmp.7_12 != D.2012_23)
    goto <bb 5>;
  else
    goto <bb 6>;

<bb 5>:
  goto <bb 4>;

The preheader is not cleaned up until RTL PRE.  Then, PRE transforms
L54:
   51 NOTE_INSN_BASIC_BLOCK
   52 [r371:DI]=r373:SI#0
   53 r371:DI=r371:DI+0x2
   55 r392:BI=r371:DI!=r381:DI
   56 pc={(r392:BI!=0x0)?L54:pc}

to

L83:
   82 NOTE_INSN_BASIC_BLOCK
   77 r397:DI=r371:DI+0x2
L54:
   51 NOTE_INSN_BASIC_BLOCK
   52 [r371:DI]=r373:SI#0
   75 r371:DI=r397:DI
      REG_EQUAL: r371:DI+0x2
   55 r392:BI=r371:DI!=r381:DI
   56 pc={(r392:BI!=0x0)?L83:pc}
      REG_DEAD: r392:BI
      REG_BR_PROB: 0x26ac

... which is something auto-inc-dec pass is not able to handle.  If I disable
rtl pre with -fdbg-cnt=pre:0, auto-inc is generated, but doloop pass is
confused instead:
Loop 1 is simple:
  simple exit 4 -> 5
  infinite if: (expr_list:REG_DEP_TRUE (subreg:SI (and:DI (plus:DI (minus:DI
(ashift:DI (reg:DI 390)
                        (const_int 1 [0x1]))
                    (reg:DI 371 [ ivtmp.7 ]))
                (const:DI (plus:DI (symbol_ref:DI ("a") [flags 0x2]  <var_decl
0x7ffff7968000 a>)
                        (const_int 2 [0x2]))))
            (const_int 1 [0x1])) 0)
    (nil))
  number of iterations: (lshiftrt:DI (plus:DI (minus:DI (reg:DI 381 [ D.2012 ])
            (reg:DI 371 [ ivtmp.7 ]))
        (const_int -2 [0xfffffffffffffffe]))
    (const_int 1 [0x1]))
  upper bound: -2
Doloop: Possible infinite iteration case.
Doloop: The loop is not suitable.


-- 


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

[Bug rtl-optimization/32283] [4.3/4.4/4.5/4.6 regression] Missed induction variable optimization

[rguenth at gcc dot gnu dot org]

------- Comment #29 from rguenth at gcc dot gnu dot org  2010-05-22 18:11 -------
GCC 4.3.5 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.5                       |4.3.6


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