Loop optimization bug with Ada front end on PPC (and probably Alpha)

[Corey Minyard <minyard at acm dot org>]

I've found a bug in the doloop optimization that has to do with how the
Ada front end generates code.  This occurs on PowerPC and Alpha, it
doesn't seem to happen on x86 because this particular optimiation never
seems to get hit.

The problem is that the Ada front end generates code for "for" loops like:

     for I in 1 .. Len loop
         a[i] := b[i];
     end loop;

The output RTL (in pseudocode) is something like:

     I := 1;
     goto loopstart
loopcont:
     i := i + 1;
loopstart:
     a[i] := b[i];
     if (i /= Len) then
         goto loopcont;
     end if;

The doloop optimization doesn't handle this case correctly because the
loop variable is incremented after the loop comparison, not before, so
doloop optimization will execute the loop one too few times.  I've
attached a cheap hack that fixes the bug, but it's a cheap hack.  How
should this really be fixed?

-Corey

Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.128
diff -u -r1.128 basic-block.h
--- basic-block.h	2001/11/15 07:55:45	1.128
+++ basic-block.h	2001/11/22 05:56:32
@@ -409,6 +409,9 @@
   /* Non-zero if the loop has a NOTE_INSN_LOOP_VTOP.  */
   rtx vtop;
 
+  /* Non-zero if the loop has a NOTE_INSN_LOOP_SKIPINCR. */
+  rtx skip_incr;
+
   /* Non-zero if the loop has a NOTE_INSN_LOOP_CONT.
      A continue statement will generate a branch to NEXT_INSN (cont).  */
   rtx cont;
Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.12
diff -u -r1.12 doloop.c
--- doloop.c	2001/11/16 02:26:38	1.12
+++ doloop.c	2001/11/22 05:56:36
@@ -596,6 +596,15 @@
 			      copy_rtx (neg_inc ? final_value : initial_value),
 			      NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
 
+  if (loop->skip_incr && ! loop->vtop)
+    {
+      /* If skip_incr is set, then the increment for the loop is done
+	 after the test, so we need to iterate one more time. */
+      diff = expand_simple_binop (GET_MODE (diff), PLUS,
+				  diff, GEN_INT(1),
+				  NULL_RTX, 1, OPTAB_LIB_WIDEN);
+    }
+
   if (abs_inc * loop_info->unroll_number != 1)
     {
       int shift_count;
Index: final.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/final.c,v
retrieving revision 1.222
diff -u -r1.222 final.c
--- final.c	2001/11/15 14:58:19	1.222
+++ final.c	2001/11/22 05:56:49
@@ -2115,6 +2115,7 @@
 	case NOTE_INSN_LOOP_END:
 	case NOTE_INSN_LOOP_CONT:
 	case NOTE_INSN_LOOP_VTOP:
+	case NOTE_INSN_LOOP_SKIPINCR:
 	case NOTE_INSN_FUNCTION_END:
 	case NOTE_INSN_REPEATED_LINE_NUMBER:
 	case NOTE_INSN_RANGE_BEG:
Index: loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.369
diff -u -r1.369 loop.c
--- loop.c	2001/11/15 23:44:56	1.369
+++ loop.c	2001/11/22 05:57:26
@@ -2519,6 +2519,10 @@
 	    current_loop->vtop = insn;
 	    break;
 
+	  case NOTE_INSN_LOOP_SKIPINCR:
+	    current_loop->skip_incr = insn;
+	    break;
+
 	  case NOTE_INSN_LOOP_END:
 	    if (! current_loop)
 	      abort ();
Index: rtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.c,v
retrieving revision 1.103
diff -u -r1.103 rtl.c
--- rtl.c	2001/11/03 16:28:33	1.103
+++ rtl.c	2001/11/22 05:57:29
@@ -263,6 +263,7 @@
   "NOTE_INSN_BLOCK_BEG", "NOTE_INSN_BLOCK_END",
   "NOTE_INSN_LOOP_BEG", "NOTE_INSN_LOOP_END",
   "NOTE_INSN_LOOP_CONT", "NOTE_INSN_LOOP_VTOP",
+  "NOTE_INSN_LOOP_SKIPINCR",
   "NOTE_INSN_FUNCTION_END",
   "NOTE_INSN_PROLOGUE_END", "NOTE_INSN_EPILOGUE_BEG",
   "NOTE_INSN_DELETED_LABEL", "NOTE_INSN_FUNCTION_BEG",
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.314
diff -u -r1.314 rtl.h
--- rtl.h	2001/11/15 23:44:55	1.314
+++ rtl.h	2001/11/22 05:57:39
@@ -674,6 +674,9 @@
   NOTE_INSN_LOOP_CONT,
   /* Generated at the start of a duplicated exit test.  */
   NOTE_INSN_LOOP_VTOP,
+  /* Generated at the start of an increment that is skipped the
+     first time in the loop. */
+  NOTE_INSN_LOOP_SKIPINCR,
 
   /* This kind of note is generated at the end of the function body,
      just before the return insn or return label.  In an optimizing
Index: ada/trans.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ada/trans.c,v
retrieving revision 1.5
diff -u -r1.5 trans.c
--- trans.c	2001/11/15 23:34:17	1.5
+++ trans.c	2001/11/22 05:59:10
@@ -2374,6 +2374,8 @@
 					convert (TREE_TYPE (gnu_loop_var),
 						 integer_one_node));
 	    set_lineno (gnat_iter_scheme, 1);
+	    if (gnu_bottom_condition != integer_one_node)
+	      emit_note (NULL, NOTE_INSN_LOOP_SKIPINCR);
 	    expand_expr_stmt (gnu_expr);
 	  }