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

["aoliva at redhat dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- 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