[Bug rtl-optimization/20290] New: Miscompilation on ppc with -Os

[Bug rtl-optimization/20290] New: Miscompilation on ppc with -Os

[jakub at gcc dot gnu dot org]

extern void abort (void);

void
check (unsigned int *l)
{
  int i;
  for (i = 0; i < 288; i++)
    if (l[i] != 7 + (i < 256 || i >= 280) + (i >= 144 && i < 256))
      abort ();
}

int
main (void)
{
  int i;
  unsigned int l[288];

  for (i = 0; i < 144; i++)
    l[i] = 8;
  for (; i < 256; i++)
    l[i] = 9;
  for (; i < 280; i++)
    l[i] = 7;
  for (; i < 288; i++)
    l[i] = 8;
  check (l);
  return 0;
}

is miscompiled on ppc with -m32 -Os.  l[256] is never set.  From initial looking
at the dumps it seems that a final value of i after the loop was miscomputed
as 257 instead of the correct 256.

-- 
           Summary: Miscompilation on ppc with -Os
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P2
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: jakub at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org
GCC target triplet: powerpc-redhat-linux


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

[Bug rtl-optimization/20290] [4.0 Regression] Miscompilation on ppc with -Os

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-02 20:40 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
 GCC target triplet|powerpc-redhat-linux        |powerpc-linux, powerpc-
                   |                            |darwin
      Known to fail|                            |4.0.0 4.1.0
      Known to work|                            |3.3.3
   Last reconfirmed|0000-00-00 00:00:00         |2005-03-02 20:40:05
               date|                            |
            Summary|Miscompilation on ppc with -|[4.0 Regression]
                   |Os                          |Miscompilation on ppc with -
                   |                            |Os
   Target Milestone|---                         |4.0.0


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

[Bug middle-end/20290] [4.0/4.1 Regression] Miscompilation on ppc with -Os

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-02 20:44 -------
Note this also happens on powerpc-darwin too but that would mean it is just semi ppc specific.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
          Component|rtl-optimization            |middle-end
            Summary|[4.0 Regression]            |[4.0/4.1 Regression]
                   |Miscompilation on ppc with -|Miscompilation on ppc with -
                   |Os                          |Os


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

[Bug middle-end/20290] [4.0/4.1 Regression] Miscompilation on ppc with -Os

[jakub at gcc dot gnu dot org]

------- Additional Comments From jakub at gcc dot gnu dot org  2005-03-02 21:16 -------
It seems loop_iterations incorrectly counts number of iterations of the second
loop:
  ivtmp.2 = 113;
  goto <bb 4> (<L4>);

<L3>:;
  *(ivtmp.52 + 4294967292B) = 9;
  i = i + 1;

<L4>:;
  ivtmp.2 = ivtmp.2 - 1;
  ivtmp.52 = ivtmp.52 + 4B;
  if (ivtmp.2 != 0) goto <L3>; else goto <L16>;

<L16>:;

loop's n_iterations is 113, but only the loop header is executed 113 times,
while the loop body is executed only 112 times.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |jakub at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2005-03-02 20:40:05         |2005-03-02 21:16:56
               date|                            |


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

[Bug middle-end/20290] [4.0/4.1 Regression] Miscompilation on ppc with -Os

[jakub at gcc dot gnu dot org]

------- Additional Comments From jakub at gcc dot gnu dot org  2005-03-02 23:09 -------
The bug goes away with -Os -floop-optimize2, it is just the old loop optimizer
that doesn't handle this properly.  It seems to me that loop.c really can't
do its job correctly if it doesn't detect where the loop header and latch
are and if a BIV increments are done in header, latch or body.

Zdenek, any ideas what to do with this?

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at gcc dot gnu dot
                   |                            |org
         AssignedTo|jakub at gcc dot gnu dot org|unassigned at gcc dot gnu
                   |                            |dot org
             Status|ASSIGNED                    |NEW


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

[Bug middle-end/20290] [4.0/4.1 Regression] Miscompilation on ppc with -Os

[jakub at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |critical


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

[Bug middle-end/20290] [4.0/4.1 Regression] Miscompilation on ppc with -Os

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2005-03-02 23:15 -------
As for 4.1, I hope we will get rid of the old loop optimizer.
I will check what can be done in 4.0.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rakdver at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug middle-end/20290] [4.0/4.1 Regression] Miscompilation on ppc/arm with -Os

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-04 14:57 -------
I hear from Richard Earnshaw that this also fails on ARM too which means that it is a generic bug.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.0/4.1 Regression]        |[4.0/4.1 Regression]
                   |Miscompilation on ppc with -|Miscompilation on ppc/arm
                   |Os                          |with -Os


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

[Bug rtl-optimization/20290] [4.0/4.1 Regression] Miscompilation on ppc/arm with -Os

[aoliva at redhat dot com]

------- Additional Comments From aoliva at gcc dot gnu dot org  2005-03-20 18:34 -------
Subject: [PR rtl-optimization/20290] loop body doesn't run in every iteration if exit test is the loop entry point

Tree loop optimizations transform the second loop in main() in the
attached testcase in a loop that enters through the exit test.  We end
up miscomputing the final value of the original biv because we assume
the increment is executed in every iteration, but since the iteration
count is computed based on the number of times the exit test runs, the
multiplier we use is off by one.

This patch detects the situation of entering the loop through an
unconditional jump to the exit test, which I believe is a relatively
rare idiom that should probably be avoided by tree loop opts as well,
and makes sure the biv increment is marked as not executed in every
iteration.  This unfortunately means the biv can't be eliminated.  It
could if we kept track of two distinct properties: whether the
increment is conditional (not_every_iteration), and whether the
increment is skipped only in the last iteration (not_last_iteration).
I haven't gone as far as implementing this, since I understand the new
loop optimization infrastructure already handles this case correctly.

Bootstrapped and regtested on x86_64-linux-gnu, verified to fix the
testcase on ppc-linux by visual inspection of the assembly output.  Ok
to install?

Index: gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR rtl-optimization/20290
	* loop.c (for_each_insn_in_loop): Don't assume the loop body runs
	in every iteration if the entry point is the exit test.

Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.522
diff -u -p -r1.522 loop.c
--- gcc/loop.c 17 Jan 2005 08:46:15 -0000 1.522
+++ gcc/loop.c 20 Mar 2005 06:36:43 -0000
@@ -4655,12 +4655,18 @@ for_each_insn_in_loop (struct loop *loop
   int not_every_iteration = 0;
   int maybe_multiple = 0;
   int past_loop_latch = 0;
+  bool exit_test_is_entry = false;
   rtx p;
 
-  /* If loop_scan_start points to the loop exit test, we have to be wary of
-     subversive use of gotos inside expression statements.  */
+  /* If loop_scan_start points to the loop exit test, the loop body
+     cannot be counted on running on every iteration, and we have to
+     be wary of subversive use of gotos inside expression
+     statements.  */
   if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
-    maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
+    {
+      exit_test_is_entry = true;
+      maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
+    }
 
   /* Scan through loop and update NOT_EVERY_ITERATION and MAYBE_MULTIPLE.  */
   for (p = next_insn_in_loop (loop, loop->scan_start);
@@ -4718,10 +4724,12 @@ for_each_insn_in_loop (struct loop *loop
          beginning, don't set not_every_iteration for that.
          This can be any kind of jump, since we want to know if insns
          will be executed if the loop is executed.  */
-	  && !(JUMP_LABEL (p) == loop->top
-	       && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
-		    && any_uncondjump_p (p))
-		   || (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
+	  && (exit_test_is_entry
+	      || !(JUMP_LABEL (p) == loop->top
+		   && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
+			&& any_uncondjump_p (p))
+		       || (NEXT_INSN (p) == loop->end
+			   && any_condjump_p (p))))))
 	{
 	  rtx label = 0;
 
Index: gcc/testsuite/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR rtl-optimization/20290
	* gcc.c-torture/execute/loop-ivopts-2.c: New.

Index: gcc/testsuite/gcc.c-torture/execute/loop-ivopts-2.c
===================================================================
RCS file: gcc/testsuite/gcc.c-torture/execute/loop-ivopts-2.c
diff -N gcc/testsuite/gcc.c-torture/execute/loop-ivopts-2.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.c-torture/execute/loop-ivopts-2.c 20 Mar 2005 06:36:58 -0000
@@ -0,0 +1,50 @@
+/* PR rtl-optimization/20290  */
+   
+/* We used to mis-optimize the second loop in main on at least ppc and
+   arm, because tree loop would change the loop to something like:
+
+  ivtmp.65 = &l[i];
+  ivtmp.16 = 113;
+  goto <bb 4> (<L4>);
+
+<L3>:;
+  *(ivtmp.65 + 4294967292B) = 9;
+  i = i + 1;
+
+<L4>:;
+  ivtmp.16 = ivtmp.16 - 1;
+  ivtmp.65 = ivtmp.65 + 4B;
+  if (ivtmp.16 != 0) goto <L3>; 
+
+  We used to consider the increment of i as executed in every
+  iteration, so we'd miscompute the final value.  */
+
+extern void abort (void);
+
+void
+check (unsigned int *l)
+{
+  int i;
+  for (i = 0; i < 288; i++)
+    if (l[i] != 7 + (i < 256 || i >= 280) + (i >= 144 && i < 256))
+      abort ();
+}
+
+int
+main (void)
+{
+  int i;
+  unsigned int l[288];
+
+  for (i = 0; i < 144; i++)
+    l[i] = 8;
+  for (; i < 256; i++)
+    l[i] = 9;
+  for (; i < 280; i++)
+    l[i] = 7;
+  for (; i < 288; i++)
+    l[i] = 8;
+  check (l);
+  return 0;
+}
+

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}


-- 


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

[Bug rtl-optimization/20290] [4.0/4.1 Regression] Miscompilation on ppc/arm with -Os

[rth at gcc dot gnu dot org]

------- Additional Comments From rth at gcc dot gnu dot org  2005-03-31 21:46 -------
Subject: Re: [PR rtl-optimization/20290] loop body doesn't run in every iteration if exit test is the loop entry point

On Sun, Mar 20, 2005 at 03:33:49PM -0300, Alexandre Oliva wrote:
> 	* loop.c (for_each_insn_in_loop): Don't assume the loop body runs
> 	in every iteration if the entry point is the exit test.

Ok.


r~


-- 


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

[Bug rtl-optimization/20290] [4.0/4.1 Regression] Miscompilation on ppc/arm with -Os

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-04-02 16:54 -------
Subject: Bug 20290

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-4_0-branch
Changes by:	aoliva@gcc.gnu.org	2005-04-02 16:54:34

Modified files:
	gcc            : ChangeLog loop.c 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.c-torture/execute: loop-ivopts-2.c 

Log message:
	gcc/ChangeLog:
	PR rtl-optimization/20290
	* loop.c (for_each_insn_in_loop): Don't assume the loop body runs
	in every iteration if the entry point is the exit test.
	gcc/testsuite/ChangeLog:
	PR rtl-optimization/20290
	* gcc.c-torture/execute/loop-ivopts-2.c: New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.7592.2.113&r2=2.7592.2.114
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/loop.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.522&r2=1.522.8.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.5084.2.87&r2=1.5084.2.88
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.c-torture/execute/loop-ivopts-2.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=NONE&r2=1.1.2.1



-- 


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

[Bug rtl-optimization/20290] [4.0/4.1 Regression] Miscompilation on ppc/arm with -Os

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-04-02 16:53 -------
Subject: Bug 20290

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	aoliva@gcc.gnu.org	2005-04-02 16:53:44

Modified files:
	gcc            : ChangeLog loop.c 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.c-torture/execute: loop-ivopts-2.c 

Log message:
	gcc/ChangeLog:
	PR rtl-optimization/20290
	* loop.c (for_each_insn_in_loop): Don't assume the loop body runs
	in every iteration if the entry point is the exit test.
	gcc/testsuite/ChangeLog:
	PR rtl-optimization/20290
	* gcc.c-torture/execute/loop-ivopts-2.c: New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.8086&r2=2.8087
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/loop.c.diff?cvsroot=gcc&r1=1.524&r2=1.525
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.5267&r2=1.5268
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.c-torture/execute/loop-ivopts-2.c.diff?cvsroot=gcc&r1=NONE&r2=1.1



-- 


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

[Bug rtl-optimization/20290] [4.0/4.1 Regression] Miscompilation on ppc/arm with -Os

[aoliva at gcc dot gnu dot org]

------- Additional Comments From aoliva at gcc dot gnu dot org  2005-04-02 17:01 -------
Fixed

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


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