[Bug middle-end/28970] New: Wrong code for simple loop test case

[Bug middle-end/28970] New: Wrong code for simple loop test case

[bergner at vnet dot ibm dot com]

We generate bad code for the following test case using the latest 4.1 compiler.
 It compiles and runs fine using 4.2.  It also compiles and runs fine with my
3.3.3 system compiler.  I've tested this on both x86_64 and ppc64 systems, and
the test case fails for both when compiled as a 32-bit app and passes when
compiled as a 64-bit app.

#include <stdio.h>

int tar (int i)
{
  printf("expected = %d, actual = %d\n", 36863, i);
  return -1;
}

void bug(int q, int bcount)
{
  int j = 0;
  int outgo = 0;

  while(j != -1)
    {
      outgo++;
      if (outgo > q-1)
        outgo = q-1;
      j = tar (outgo*bcount);
    }
}

int main(void)
{
  bug(5, 36863);
  return 0;
}

bergner@vervain:~> gcc-4.1.2 -O2 bug01.c
bergner@vervain:~> ./a.out
expected = 36863, actual = 184315


-- 
           Summary: Wrong code for simple loop test case
           Product: gcc
           Version: 4.1.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: bergner at vnet dot ibm dot com
 GCC build triplet: powerpc64-linux
  GCC host triplet: powerpc64-linux
GCC target triplet: powerpc64-linux


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

[Bug middle-end/28970] [4.1 Regression] Wrong code for simple loop test case

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2006-09-07 05:01 -------
Confirmed, this is a loop.c bug which is why it is not in 4.2.0 at all.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
  GCC build triplet|powerpc64-linux             |
   GCC host triplet|powerpc64-linux             |
 GCC target triplet|powerpc64-linux             |powerpc-linux, i686-linux-
                   |                            |gnu
           Keywords|                            |wrong-code
      Known to fail|                            |4.1.0 4.1.1 4.1.2
      Known to work|                            |4.0.0
   Last reconfirmed|0000-00-00 00:00:00         |2006-09-07 05:01:38
               date|                            |
            Summary|Wrong code for simple loop  |[4.1 Regression] Wrong code
                   |test case                   |for simple loop test case
   Target Milestone|---                         |4.1.2


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

[Bug middle-end/28970] [4.1 Regression] Wrong code for simple loop test case

[janis at gcc dot gnu dot org]

------- Comment #2 from janis at gcc dot gnu dot org  2006-09-07 20:26 -------
A regression hunt on powerpc-linux identified the following patch:

    http://gcc.gnu.org/viewcvs?view=rev&rev=99850

    r99850 | rakdver | 2005-05-17 19:55:53 +0000 (Tue, 17 May 2005)


-- 


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

[Bug middle-end/28970] [4.1 Regression] Wrong code for simple loop test case

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2006-10-16 12:07 -------
This is a bug in loop.c

<bb 0>:
  pretmp.61 = q - 1;
  outgo = 0;

<L0>:;
  outgo.62 = outgo + 1;
  outgo = MIN_EXPR <pretmp.61, outgo.62>;
  j = tar (outgo * bcount);
  if (j != -1) goto <L0>; else goto <L4>;

<L4>:;
  return;

Bug in biv selection, so strength reduction messes up:

Loop from 45 to 46: 12 real insns.
Biv 60: insn 19 const (reg 59 [ pretmp.26 ])
Biv 60: insn 22 const (1)
Biv 60: verified
Biv 60: initialized at insn 13: initial value (0)
Giv 58: insn 17 src reg 60 benefit 4 lifetime 6

60 is not a Biv:

(insn 19 17 20 1 (set (reg/v:SI 60 [ outgo ])
        (reg:SI 59 [ pretmp.26 ])) 40 {*movsi_1} (nil)
    (nil))

(insn 20 19 21 1 (set (reg:CCGC 17 flags)
        (compare:CCGC (reg/v:SI 60 [ outgo ])
            (reg/v:SI 58 [ outgo.27 ]))) 5 {*cmpsi_1_insn} (nil)
    (nil))

(jump_insn 21 20 41 1 (set (pc)
        (if_then_else (le (reg:CCGC 17 flags)
                (const_int 0 [0x0]))
            (label_ref 23)
            (pc))) 531 {*jcc_1} (nil)
    (expr_list:REG_BR_PROB (const_int 5000 [0x1388])
        (nil)))
;; End of basic block 1, registers live:
 (nil)

;; Start of basic block 2, registers live: (nil)
(note 41 21 22 2 [bb 2] NOTE_INSN_BASIC_BLOCK)

(insn 22 41 23 2 (set (reg/v:SI 60 [ outgo ])
        (reg/v:SI 58 [ outgo.27 ])) 40 {*movsi_1} (nil)
    (nil))
;; End of basic block 2, registers live:
 (nil)

;; Start of basic block 3, registers live: (nil)
(code_label 23 22 42 3 3 "" [1 uses])


now strength reduction does:

(insn 19 17 51 1 (set (reg/v:SI 60 [ outgo ])
        (reg:SI 59 [ pretmp.26 ])) -1 (nil)
    (nil))

(insn 51 19 20 1 (parallel [
            (set (reg:SI 66)
                (mult:SI (reg:SI 59 [ pretmp.26 ])
                    (reg/v:SI 63 [ bcount ])))
            (clobber (reg:CC 17 flags))
        ]) -1 (nil)
    (nil))

(insn 20 51 21 1 (set (reg:CCGC 17 flags)
        (compare:CCGC (reg/v:SI 60 [ outgo ])
            (reg/v:SI 58 [ outgo.27 ]))) -1 (nil)
    (nil))

(jump_insn 21 20 41 1 (set (pc)
        (if_then_else (le (reg:CCGC 17 flags)
                (const_int 0 [0x0]))
            (label_ref 23)
            (pc))) -1 (nil)
    (expr_list:REG_BR_PROB (const_int 5000 [0x1388])
        (nil)))
;; End of basic block 1, registers live:
 (nil)

;; Start of basic block 2, registers live: (nil)
(note 41 21 22 2 [bb 2] NOTE_INSN_BASIC_BLOCK)

(insn 22 41 50 2 (set (reg/v:SI 60 [ outgo ])
        (reg/v:SI 58 [ outgo.27 ])) -1 (nil)
    (nil))

(insn 50 22 23 2 (parallel [
            (set (reg:SI 66)
                (plus:SI (reg:SI 66)
                    (reg/v:SI 63 [ bcount ])))
            (clobber (reg:CC 17 flags))
        ]) -1 (nil)
    (nil))
;; End of basic block 2, registers live:
 (nil)

;; Start of basic block 3, registers live: (nil)
(code_label 23 50 42 3 3 "" [1 uses])


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at gcc dot gnu dot
                   |                            |org
   Last reconfirmed|2006-09-07 05:01:38         |2006-10-16 12:07:36
               date|                            |


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

[Bug middle-end/28970] [4.1 Regression] Wrong code for simple loop test case

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2006-10-27 09:50 -------
Janis, can you hunt which path introduced this regression relative from 4.0.0
which seems to work?


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |janis at gcc dot gnu dot org
      Known to work|4.0.0                       |4.0.0 4.0.3


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

[Bug middle-end/28970] [4.1 Regression] Wrong code for simple loop test case

[janis at gcc dot gnu dot org]

------- Comment #5 from janis at gcc dot gnu dot org  2006-10-27 16:40 -------
The regression hunt results in comment #2 are from mainline during development
of 4.1.  Is there some other hunt that would be useful as well?


-- 


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

[Bug middle-end/28970] [4.1 Regression] Wrong code for simple loop test case

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2006-10-28 11:06 -------
Ah, no - I didn't look at the result of this first hunt and though it was the
switch from -floop-optimize to -floop-optimize2.  Sorry for the noise.


-- 


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

[Bug rtl-optimization/28970] [4.1 Regression] Wrong code for simple loop test case

[ebotcazou at gcc dot gnu dot org]

------- Comment #7 from ebotcazou at gcc dot gnu dot org  2006-10-29 23:06 -------
As per comment #3.


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|middle-end                  |rtl-optimization


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

[Bug rtl-optimization/28970] [4.1 Regression] Wrong code for simple loop test case

[ebotcazou at gcc dot gnu dot org]

------- Comment #8 from ebotcazou at gcc dot gnu dot org  2006-10-29 23:06 -------
Investigating.


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |ebotcazou at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2006-10-16 12:07:36         |2006-10-29 23:06:48
               date|                            |


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

[Bug rtl-optimization/28970] [4.1 regression] wrong code for simple loop test case

[ebotcazou at gcc dot gnu dot org]

------- Comment #9 from ebotcazou at gcc dot gnu dot org  2006-10-30 16:01 -------
> Bug in biv selection, so strength reduction messes up:
> 
> Loop from 45 to 46: 12 real insns.
> Biv 60: insn 19 const (reg 59 [ pretmp.26 ])
> Biv 60: insn 22 const (1)
> Biv 60: verified
> Biv 60: initialized at insn 13: initial value (0)
> 
> 60 is not a Biv:

Yeah, the limitations of loop.c are blatantly exposed by the new dialect
generated by the RTL expanders in 4.x because of the 100 tree-opt passes.

It turns out that 3.x finds the same BIVs:

Biv 61: insn 22 const (1)
Biv 61: insn 28 const (reg 65)
Biv 61: verified
Biv 61: initialized at insn 12: initial value (0)

but the non-constant increment comes after the constant one, which is enough
to prevent the GIV from being eliminated...


-- 


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

[Bug rtl-optimization/28970] [4.1 regression] wrong code for simple loop test case

[ebotcazou at gcc dot gnu dot org]

------- Comment #10 from ebotcazou at gcc dot gnu dot org  2006-11-01 12:11 -------
Subject: Bug 28970

Author: ebotcazou
Date: Wed Nov  1 12:11:18 2006
New Revision: 118379

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=118379
Log:
        PR rtl-optimization/28970
        * loop.c (loop_giv_reduce_benefit): Take the max of the addition
        cost on all the increments of the BIV.


Added:
    branches/gcc-4_1-branch/gcc/testsuite/gcc.c-torture/execute/20061101-1.c
Modified:
    branches/gcc-4_1-branch/gcc/ChangeLog
    branches/gcc-4_1-branch/gcc/loop.c
    branches/gcc-4_1-branch/gcc/testsuite/ChangeLog


-- 


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

[Bug rtl-optimization/28970] [4.1 regression] wrong code for simple loop test case

[ebotcazou at gcc dot gnu dot org]

------- Comment #11 from ebotcazou at gcc dot gnu dot org  2006-11-01 12:16 -------
More of a kludge than a fix...


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |http://gcc.gnu.org/ml/gcc-
                   |                            |patches/2006-
                   |                            |11/msg00010.html
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


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