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

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

[Corey Minyard]

[-- Attachment #1: Type: text/plain, Size: 894 bytes --]

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


[-- Attachment #2: loopfix.diff --]
[-- Type: text/plain, Size: 3998 bytes --]

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);
 	  }
 

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

[David Edelsohn]

	This is similar to the same bug which has been reported for a few
months, but the patches have not been approved.

David

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

[Corey Minyard]

David Edelsohn wrote:

>	This is similar to the same bug which has been reported for a few
>months, but the patches have not been approved.
>
>David
>
I found a rather controversial patch about loop unrolling, but nothing 
beyond that, and I don't think that will fix this problem.  I'll work on 
a patch that detects the situation in the insns and does this, if no one 
has any other suggestions for a fix.

-Corey

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

[guerby]

This might explain the strange errors people are seeing with Ada file names
on some targets since these loops will likely be generated for Ada string
code.

David, you said patches to fix this seemingly known weren't accepted in
the past, what was the reason?

-- 
Laurent Guerby <guerby@acm.org>

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

[Corey Minyard]

guerby@acm.org wrote:

>This might explain the strange errors people are seeing with Ada file names
>on some targets since these loops will likely be generated for Ada string
>code.
>
Yes, someone else was seeing this exact problem on Alpha Linux, too.  I 
don't have an Alpha box, and unless someone wants to send me one, I 
can't verify it.

>
>
>David, you said patches to fix this seemingly known weren't accepted in
>the past, what was the reason?
>
I'd like to see the patches.  I'm sure someone can make them acceptable :-).

-Corey

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

[David Edelsohn]

>>>>> Corey Minyard writes:

> David, you said patches to fix this seemingly known weren't accepted in
> the past, what was the reason?
> 
Corey> I'd like to see the patches.  I'm sure someone can make them acceptable :-).

       Look for patches over the last six months by Zoltan Hidvegi.
Comments about the patch were that it did not fix all failure cases.
There also were questions whether the patch should fix the optimized code
or disable the optimization.

	The current loop optimization code is a mess, but waiting for a
long-term replacement seems to prevent short-term fixes.

David

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

[David Edelsohn]

>>>>> Corey Minyard writes:

> David, you said patches to fix this seemingly known weren't accepted in
> the past, what was the reason?
> 
Corey> I'd like to see the patches.  I'm sure someone can make them acceptable :-).

       Look for patches over the last six months by Zoltan Hidvegi.
Comments about the patch were that it did not fix all failure cases.
There also were questions whether the patch should fix the optimized code
or disable the optimization.

	The current loop optimization code is a mess, but waiting for a
long-term replacement seems to prevent short-term fixes.

David

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

[Richard Henderson]

On Thu, Nov 22, 2001 at 01:21:20AM -0600, Corey Minyard wrote:
>      for I in 1 .. Len loop
>          a[i] := b[i];
>      end loop;

Give me a complete compilable testcase and I'll look at it.


r~

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

[Andreas Schwab]

[-- Attachment #1: Type: text/plain, Size: 678 bytes --]

Richard Henderson <rth@redhat.com> writes:

|> On Thu, Nov 22, 2001 at 01:21:20AM -0600, Corey Minyard wrote:
|> >      for I in 1 .. Len loop
|> >          a[i] := b[i];
|> >      end loop;
|> 
|> Give me a complete compilable testcase and I'll look at it.

Here is a testcase for ia64-linux.  It crashes in

	    while (in < p)
	      *out++ = *in++;

because ar.lc == -1 (ie. "infinite").

Andreas.

-- 
Andreas Schwab                                  "And now for something
Andreas.Schwab@suse.de				completely different."
SuSE Labs, SuSE GmbH, Schanzäckerstr. 10, D-90443 Nürnberg
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5

[-- Attachment #2: loop.c --]
[-- Type: text/plain, Size: 2263 bytes --]

char *strchr (const char *, int);
void abort ();
#define isblank(c)     ((c) == ' ' || (c) == '\t')

/* Return the address of the first nonwhitespace or null in the string S.  */

char *
next_token (s)
     char *s;
{
  register char *p = s;

  while (isblank ((unsigned char)*p))
    ++p;
  return p;
}

void
collapse_continuations (line)
     char *line;
{
  register char *in, *out, *p;
  register int backslash;
  register unsigned int bs_write;

  in = strchr (line, '\n');
  if (in == 0)
    return;

  out = in;
  while (out > line && out[-1] == '\\')
    --out;

  while (*in != '\0')
    {
      /* BS_WRITE gets the number of quoted backslashes at
	 the end just before IN, and BACKSLASH gets nonzero
	 if the next character is quoted.  */
      backslash = 0;
      bs_write = 0;
      for (p = in - 1; p >= line && *p == '\\'; --p)
	{
	  if (backslash)
	    ++bs_write;
	  backslash = !backslash;

	  /* It should be impossible to go back this far without exiting,
	     but if we do, we can't get the right answer.  */
	  if (in == out - 1)
	    abort ();
	}

      /* Output the appropriate number of backslashes.  */
      while (bs_write-- > 0)
	*out++ = '\\';

      /* Skip the newline.  */
      ++in;

      /* If the newline is quoted, discard following whitespace
	 and any preceding whitespace; leave just one space.  */
      if (backslash)
	{
	  in = next_token (in);
	  while (out > line && isblank ((unsigned char)out[-1]))
	    --out;
	  *out++ = ' ';
	}
      else
	/* If the newline isn't quoted, put it in the output.  */
	*out++ = '\n';

      /* Now copy the following line to the output.
	 Stop when we find backslashes followed by a newline.  */
      while (*in != '\0')
	if (*in == '\\')
	  {
	    p = in + 1;
	    while (*p == '\\')
	      ++p;
	    if (*p == '\n')
	      {
		in = p;
		break;
	      }
	    while (in < p)
	      *out++ = *in++;
	  }
	else
	  *out++ = *in++;
    }

  *out = '\0';
}

int main ()
{
  char line[] = "VER = `\tif grep AM_INIT_AUTOMAKE $(TOOL)/configure.in >/dev/null 2>&1; then \\\n\t  sed < $(TOOL)/configure.in -n 's/AM_INIT_AUTOMAKE[^,]*, *\\([^)]*\\))/\\1/p'; \\\n\telse \\\n\t  sed < $(TOOL)/Makefile.in -n 's/^VERSION *= *//p'; \\\n\tfi`";

  collapse_continuations (line);
  return 0;
}

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

[Richard Henderson]

On Sun, Nov 25, 2001 at 05:57:07PM +0100, Andreas Schwab wrote:
> Here is a testcase for ia64-linux.  It crashes in
> 
> 	    while (in < p)
> 	      *out++ = *in++;
> 
> because ar.lc == -1 (ie. "infinite").

At first blush, this is a gcse problem.  Copy propagation doesn't
replace all ocurrences of r341, and doloop winds up computing ar.lc
from the wrong register.


r~

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

[Richard Henderson]

On Sun, Nov 25, 2001 at 05:57:07PM +0100, Andreas Schwab wrote:
> Here is a testcase for ia64-linux.  It crashes in
> 
> 	    while (in < p)
> 	      *out++ = *in++;
> 
> because ar.lc == -1 (ie. "infinite").

At first blush, this is a gcse problem.  Copy propagation doesn't
replace all ocurrences of r341, and doloop winds up computing ar.lc
from the wrong register.


r~

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

[Richard Henderson]

I've committed the following simplification as execute/20011126-2.c.


r~



/* Problem originally visible on ia64.

   There is a partial redundancy of "in + 1" that makes GCSE want to
   transform the final while loop to 

     p = in + 1;
     tmp = p;
     ...
     goto start;
   top:
     tmp = tmp + 1;
   start:
     in = tmp;
     if (in < p) goto top;

   We miscalculate the number of loop iterations as (p - tmp) = 0
   instead of (p - in) = 1, which results in overflow in the doloop
   optimization.  */

static const char *
test (const char *in, char *out)
{
  while (1)
    {
      if (*in == 'a')
	{
	  const char *p = in + 1;
	  while (*p == 'x')
	    ++p;
	  if (*p == 'b')
	    return p;
	  while (in < p)
	    *out++ = *in++;
	}
    }
}

int main ()
{
  char out[4];
  test ("aab", out);
  return 0;
}

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

[Richard Henderson]

I've committed the following simplification as execute/20011126-2.c.


r~



/* Problem originally visible on ia64.

   There is a partial redundancy of "in + 1" that makes GCSE want to
   transform the final while loop to 

     p = in + 1;
     tmp = p;
     ...
     goto start;
   top:
     tmp = tmp + 1;
   start:
     in = tmp;
     if (in < p) goto top;

   We miscalculate the number of loop iterations as (p - tmp) = 0
   instead of (p - in) = 1, which results in overflow in the doloop
   optimization.  */

static const char *
test (const char *in, char *out)
{
  while (1)
    {
      if (*in == 'a')
	{
	  const char *p = in + 1;
	  while (*p == 'x')
	    ++p;
	  if (*p == 'b')
	    return p;
	  while (in < p)
	    *out++ = *in++;
	}
    }
}

int main ()
{
  char out[4];
  test ("aab", out);
  return 0;
}

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

[Andreas Schwab]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 661 bytes --]

Richard Henderson <rth@redhat.com> writes:

|> On Thu, Nov 22, 2001 at 01:21:20AM -0600, Corey Minyard wrote:
|> >      for I in 1 .. Len loop
|> >          a[i] := b[i];
|> >      end loop;
|> 
|> Give me a complete compilable testcase and I'll look at it.

Here is a testcase for ia64-linux.  It crashes in

	    while (in < p)
	      *out++ = *in++;

because ar.lc == -1 (ie. "infinite").

Andreas.

-- 
Andreas Schwab                                  "And now for something
Andreas.Schwab@suse.de				completely different."
SuSE Labs, SuSE GmbH, Schanzäckerstr. 10, D-90443 Nürnberg
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5

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

[Corey Minyard]

[-- Attachment #1: Type: text/plain, Size: 1990 bytes --]

Richard Henderson wrote:

>On Thu, Nov 22, 2001 at 01:21:20AM -0600, Corey Minyard wrote:
>
>>     for I in 1 .. Len loop
>>         a[i] := b[i];
>>     end loop;
>>
>
>Give me a complete compilable testcase and I'll look at it.
>
>
>r~
>
The following shows the problem:

    procedure Ada.Tster (S   : in out String;
                         Len : in out Integer) is
    begin
       Len := 0;
       for I in 1 .. S'Length loop
          if S (I) /= ' ' then
             Len := Len + 1;
             S (Len) := S (I);
          end if;
       end loop;
    end Ada.Tster;

Unfortunately, it's not simple to reproduce this, since you have to 
build an Ada cross compiler, and you have to compile this code as part 
of the compiler (since you can't compile anything else easily without 
having gnatlib compiled and installed)  And it's not the same as the one 
reported by Andreas Schwab; I don't think you can reproduce this 
particular bug with the C compiler.  You have to jump past the increment 
to enter the loop, but the jump has to be after the loop begin note.

I have attached a patch that is less of a cheap hack than the previous 
one, it scans the insns of the loop to detect the situation.  With this 
patch I can do a full bootstrap on the PowerPC.  Another way to solve 
this problem would be to move the jump past the increment to before the 
loop begin note; the doloop code will detect this and not apply the 
doloop optimization, but then no for loops from the Ada front-end will 
have doloop optimization.

The attached patch might be done in a simpler manner, but I don't know 
the code well enought right now to know, and I couldn't find a better 
way in a quick search.  It was more complicated than I like because in 
some loop the increment variable is not the same one that is 
incremented, another variable is incremented then assigned to the 
increment variable.  This code only handles one level of assignment, it 
might be necessary to have more.

-Corey


[-- Attachment #2: gcc-ppc.diff --]
[-- Type: text/plain, Size: 7375 bytes --]

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/25 04:37:10
@@ -66,6 +66,8 @@
   PARAMS ((const struct loop *, rtx, rtx, rtx, rtx, rtx));
 static int doloop_modify_runtime
   PARAMS ((const struct loop *, rtx, rtx, rtx, enum machine_mode, rtx));
+static int assigned_to_regno
+  PARAMS ((unsigned int, rtx, rtx));
 
 
 /* Return the loop termination condition for PATTERN or zero
@@ -596,6 +598,15 @@
 			      copy_rtx (neg_inc ? final_value : initial_value),
 			      NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
 
+  if (loop_info->skip_incr)
+    {
+      /* 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;
@@ -689,6 +700,44 @@
 }
 
 
+/* Return nonzero of the register number is set explicitly or implicitly
+   in the given instruction over the given range. */
+static int
+assigned_to_regno(regno, x, end)
+     unsigned int regno;
+     rtx x;
+     rtx end;
+{
+  rtx p;
+  unsigned int dest_reg;
+  rtx set;
+
+  if ((set = single_set (x))
+      && GET_CODE (SET_DEST (set)) == REG)
+    {
+      dest_reg = REGNO (SET_DEST (set));
+
+      /* Is it set explicitly? */
+      if (dest_reg == regno)
+	return 1;
+
+      /* Search the the instruction to see if the variable set in the given
+	 instruction sets the variable we are looking for in the instruction
+	 range. */
+      for (p = NEXT_INSN (x); p != end; p = NEXT_INSN (p))
+	{
+	  if (GET_CODE (p) == INSN
+	      && (set = single_set (p))
+	      && REGNO (SET_DEST (set)) == regno
+	      && (GET_CODE (SET_SRC (set)) == REG)
+	      && REGNO (SET_SRC (set)) == dest_reg)
+	    return 1;
+	}
+    }
+
+  return 0;
+}
+
 /* This is the main entry point.  Process loop described by LOOP
    validating that the loop is suitable for conversion to use a low
    overhead looping instruction, replacing the jump insn where
@@ -714,6 +763,8 @@
   rtx iterations_max;
   rtx start_label;
   rtx condition;
+  rtx p;
+  rtx jump_target;
 
   if (loop_dump_stream)
     fprintf (loop_dump_stream,
@@ -737,6 +788,41 @@
       	fprintf (loop_dump_stream,
 		 "Doloop: Cannot precondition loop.\n");
       return 0;
+    }
+
+  jump_target = 0;
+  for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
+    {
+      /* Search for a jump before the first instruction. */
+      if (GET_CODE (p) == JUMP_INSN
+	  && any_uncondjump_p (p)
+	  && JUMP_LABEL (p) != 0
+	  /* Check to see whether the jump actually
+	     jumps out of the loop (meaning it's no loop).
+	     This case can happen for things like
+	     do {..} while (0).  If this label was generated previously
+	     by loop, we can't tell anything about it and have to reject
+	     the loop.  */
+	  && INSN_IN_RANGE_P (JUMP_LABEL (p), loop->start, loop->end))
+	{
+	  jump_target = JUMP_LABEL(p);
+	}
+      else if (p == jump_target)
+	  break;
+      /* If the jump has been detected and we find an assignment before
+	 its target, and the assignment affect the loop variable, then
+	 we have a jump over the initial loop increment, so mark it. */
+      else if (jump_target
+	       && GET_CODE (p) == INSN
+	       && assigned_to_regno (REGNO (loop_info->iteration_var), p,
+				     loop->end))
+	{
+	  loop_info->skip_incr = 1;
+	  if (loop_dump_stream)
+	    fprintf (loop_dump_stream,
+		     "Doloop: Skip over first increment detected.\n");
+	  break;
+	}
     }
 
   /* Determine or estimate the maximum number of loop iterations.  */
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/25 04:38:02
@@ -282,12 +282,6 @@
   rtx insn;
 } loop_replace_args;
 
-/* Nonzero iff INSN is between START and END, inclusive.  */
-#define INSN_IN_RANGE_P(INSN, START, END)	\
-  (INSN_UID (INSN) < max_uid_for_loop		\
-   && INSN_LUID (INSN) >= INSN_LUID (START)	\
-   && INSN_LUID (INSN) <= INSN_LUID (END))
-
 /* Indirect_jump_in_function is computed once per function.  */
 static int indirect_jump_in_function;
 static int indirect_jump_in_function_p PARAMS ((rtx));
Index: loop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.h,v
retrieving revision 1.56
diff -u -r1.56 loop.h
--- loop.h	2001/10/29 22:13:40	1.56
+++ loop.h	2001/11/25 04:38:05
@@ -50,6 +50,11 @@
 #define REGNO_FIRST_LUID(REGNO) uid_luid[REGNO_FIRST_UID (REGNO)]
 #define REGNO_LAST_LUID(REGNO) uid_luid[REGNO_LAST_UID (REGNO)]
 
+/* Nonzero iff INSN is between START and END, inclusive.  */
+#define INSN_IN_RANGE_P(INSN, START, END)	\
+  (INSN_UID (INSN) < max_uid_for_loop		\
+   && INSN_LUID (INSN) >= INSN_LUID (START)	\
+   && INSN_LUID (INSN) <= INSN_LUID (END))
 
 /* A "basic induction variable" or biv is a pseudo reg that is set
    (within this loop) only by incrementing or decrementing it.  */
@@ -372,6 +377,8 @@
   struct loop_ivs ivs;
   /* Non-zero if call is in pre_header extended basic block.  */
   int pre_header_has_call;
+  /* Non-zero if the loop skips over the first increment/decrement. */
+  int skip_incr;
 };
 
 
Index: ada/Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ada/Makefile.in,v
retrieving revision 1.8
diff -u -r1.8 Makefile.in
--- ada/Makefile.in	2001/11/06 21:12:13	1.8
+++ ada/Makefile.in	2001/11/25 04:38:41
@@ -104,6 +104,10 @@
 MKDIR = mkdir -p
 AR = ar
 AR_FLAGS = rc
+# Some systems may be missing symbolic links, regular links, or both.
+# Allow configure to check this and use "ln -s", "ln", or "cp" as appropriate.
+LN=@LN@
+LN_S=@LN_S@
 # How to invoke ranlib.
 RANLIB = ranlib
 # Test to use to see whether ranlib exists on the system.
Index: ada/decl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ada/decl.c,v
retrieving revision 1.8
diff -u -r1.8 decl.c
--- ada/decl.c	2001/10/30 21:33:07	1.8
+++ ada/decl.c	2001/11/25 04:39:20
@@ -1011,7 +1011,10 @@
 	    && (AGGREGATE_TYPE_P (gnu_type)
 		&& ! (TREE_CODE (gnu_type) == RECORD_TYPE
 		      && TYPE_IS_PADDING_P (gnu_type))))
-	  static_p = 1;
+	  {
+	    static_p = 1;
+	    const_flag = 0;
+	  }
 
 	set_lineno (gnat_entity, ! global_bindings_p ());
 	gnu_decl = create_var_decl (gnu_entity_id, gnu_ext_name, gnu_type,
Index: ada/misc.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ada/misc.c,v
retrieving revision 1.13
diff -u -r1.13 misc.c
--- ada/misc.c	2001/11/18 11:04:45	1.13
+++ ada/misc.c	2001/11/25 04:39:32
@@ -747,10 +747,13 @@
   enum machine_mode sa_mode = Pmode;
   rtx stack_save;
 
+#if 0 /* This seems to be broken, at least on PowerPC.  - Corey Minyard */
 #ifdef HAVE_save_stack_nonlocal
   if (HAVE_save_stack_nonlocal)
     sa_mode = insn_operand_mode[(int) CODE_FOR_save_stack_nonlocal][0];
 #endif
+#endif
+
 #ifdef STACK_SAVEAREA_MODE
   sa_mode = STACK_SAVEAREA_MODE (SAVE_NONLOCAL);
 #endif

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

[Richard Henderson]

On Sun, Nov 25, 2001 at 05:07:49PM -0600, Corey Minyard wrote:
> Unfortunately, it's not simple to reproduce this, since you have to 
> build an Ada cross compiler, and you have to compile this code as part 
> of the compiler (since you can't compile anything else easily without 
> having gnatlib compiled and installed)  And it's not the same as the one 
> reported by Andreas Schwab; I don't think you can reproduce this 
> particular bug with the C compiler.  You have to jump past the increment 
> to enter the loop, but the jump has to be after the loop begin note.

No, this appears to be exactly the same bug that Andreas demonstrates.
The reason being that it's GCSE that transforms the rtl to have the jump
after the loop begin note.

I'll look at your patch in a minute.  In the future, _always_ include
the -p option to diff.


r~

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

[Richard Henderson]

On Sun, Nov 25, 2001 at 05:07:49PM -0600, Corey Minyard wrote:
> Unfortunately, it's not simple to reproduce this, since you have to 
> build an Ada cross compiler, and you have to compile this code as part 
> of the compiler (since you can't compile anything else easily without 
> having gnatlib compiled and installed)  And it's not the same as the one 
> reported by Andreas Schwab; I don't think you can reproduce this 
> particular bug with the C compiler.  You have to jump past the increment 
> to enter the loop, but the jump has to be after the loop begin note.

No, this appears to be exactly the same bug that Andreas demonstrates.
The reason being that it's GCSE that transforms the rtl to have the jump
after the loop begin note.

I'll look at your patch in a minute.  In the future, _always_ include
the -p option to diff.


r~

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

[Richard Henderson]

The problem is not limited to doloop -- the unroller ought
to hit this problem as well.  I'm testing the following.



r~



Index: loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.369
diff -c -p -d -r1.369 loop.c
*** loop.c	2001/11/15 23:44:56	1.369
--- loop.c	2001/11/26 01:52:34
*************** typedef struct loop_replace_args
*** 282,293 ****
    rtx insn;
  } loop_replace_args;
  
- /* Nonzero iff INSN is between START and END, inclusive.  */
- #define INSN_IN_RANGE_P(INSN, START, END)	\
-   (INSN_UID (INSN) < max_uid_for_loop		\
-    && INSN_LUID (INSN) >= INSN_LUID (START)	\
-    && INSN_LUID (INSN) <= INSN_LUID (END))
- 
  /* Indirect_jump_in_function is computed once per function.  */
  static int indirect_jump_in_function;
  static int indirect_jump_in_function_p PARAMS ((rtx));
--- 282,287 ----
Index: loop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.h,v
retrieving revision 1.56
diff -c -p -d -r1.56 loop.h
*** loop.h	2001/10/29 22:13:40	1.56
--- loop.h	2001/11/26 01:52:34
*************** Software Foundation, 59 Temple Place - S
*** 50,55 ****
--- 50,60 ----
  #define REGNO_FIRST_LUID(REGNO) uid_luid[REGNO_FIRST_UID (REGNO)]
  #define REGNO_LAST_LUID(REGNO) uid_luid[REGNO_LAST_UID (REGNO)]
  
+ /* Nonzero iff INSN is between START and END, inclusive.  */
+ #define INSN_IN_RANGE_P(INSN, START, END)	\
+   (INSN_UID (INSN) < max_uid_for_loop		\
+    && INSN_LUID (INSN) >= INSN_LUID (START)	\
+    && INSN_LUID (INSN) <= INSN_LUID (END))
  
  /* A "basic induction variable" or biv is a pseudo reg that is set
     (within this loop) only by incrementing or decrementing it.  */
Index: unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
retrieving revision 1.147
diff -c -p -d -r1.147 unroll.c
*** unroll.c	2001/11/21 00:50:56	1.147
--- unroll.c	2001/11/26 01:52:34
*************** loop_iterations (loop)
*** 3480,3485 ****
--- 3480,3486 ----
    int unsigned_p, compare_dir, final_larger;
    rtx last_loop_insn;
    rtx reg_term;
+   rtx insn;
    struct iv_class *bl;
  
    loop_info->n_iterations = 0;
*************** loop_iterations (loop)
*** 3705,3710 ****
--- 3706,3762 ----
  
    if (initial_value == 0)
      return 0;
+ 
+   /* Some code transformations can result in code akin to
+ 
+ 	LOOP_BEG
+ 	  goto start;
+ 	top:
+ 	  i++;
+ 	start:
+ 	  ...
+ 	LOOP_CONT
+ 	  if (i < n) goto top;
+ 	LOOP_END
+ 
+      In this situation, we skip the increment the first time through
+      the loop, which results in an incorrect estimate of the number
+      of iterations.  As we did for GIVs above, adjust the initial value
+      to compensate.  */
+ 
+   off_by_one = 0;
+   for (insn = loop->start; insn != loop->top; insn = NEXT_INSN (insn))
+     if (GET_CODE (insn) == JUMP_INSN)
+       {
+ 	if (any_uncondjump_p (insn)
+ 	    && JUMP_LABEL (insn)
+ 	    && INSN_IN_RANGE_P (JUMP_LABEL (insn), loop->top, loop->cont))
+ 	  {
+ 	    if (reg_set_between_p (bl->biv->src_reg, insn, JUMP_LABEL (insn)))
+ 	      off_by_one = 1;
+ 	    break;
+ 	  }
+ 	/* No idea what's going on.  */
+ 	if (loop_dump_stream)
+ 	  fprintf (loop_dump_stream,
+ 		   "Loop iterations: Confused by jump before loop top.\n");
+ 	return 0;
+       }
+ 
+   if (off_by_one)
+     {
+       if (loop_dump_stream)
+ 	fprintf (loop_dump_stream,
+ 		 "Loop iterations: Basic induction var skips initial incr.\n");
+       if (GET_CODE (increment) != CONST_INT)
+ 	{
+ 	  if (loop_dump_stream)
+ 	    fprintf (loop_dump_stream,
+ 		     "Loop iterations: Can't adjust with non-constant incr.\n");
+ 	  return 0;
+ 	}
+       initial_value = plus_constant (initial_value, -INTVAL (increment));
+     }
  
    unsigned_p = 0;
    off_by_one = 0;

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

[Corey Minyard]

That patch looks a lot better than mine :-).  However, I'm getting a 
segv compiling unwind-dw2-fde.c.  I put a print in (I can't use gdb 5.0 
with the output of gcc 3.0 on Linux PowerPC), and it's dying in the line: 

  && INSN_IN_RANGE_P (JUMP_LABEL (insn), loop->top, loop->cont)

It looks like loop->top is alway NULL.  I'm working with a slightly old 
CVS, maybe I should update, or is this a real problem?

-Corey

Richard Henderson wrote:

>The problem is not limited to doloop -- the unroller ought
>to hit this problem as well.  I'm testing the following.
>
>
>
>r~
>
>
>
>Index: loop.c
>===================================================================
>RCS file: /cvs/gcc/gcc/gcc/loop.c,v
>retrieving revision 1.369
>diff -c -p -d -r1.369 loop.c
>*** loop.c	2001/11/15 23:44:56	1.369
>--- loop.c	2001/11/26 01:52:34
>*************** typedef struct loop_replace_args
>*** 282,293 ****
>    rtx insn;
>  } loop_replace_args;
>  
>- /* Nonzero iff INSN is between START and END, inclusive.  */
>- #define INSN_IN_RANGE_P(INSN, START, END)	\
>-   (INSN_UID (INSN) < max_uid_for_loop		\
>-    && INSN_LUID (INSN) >= INSN_LUID (START)	\
>-    && INSN_LUID (INSN) <= INSN_LUID (END))
>- 
>  /* Indirect_jump_in_function is computed once per function.  */
>  static int indirect_jump_in_function;
>  static int indirect_jump_in_function_p PARAMS ((rtx));
>--- 282,287 ----
>Index: loop.h
>===================================================================
>RCS file: /cvs/gcc/gcc/gcc/loop.h,v
>retrieving revision 1.56
>diff -c -p -d -r1.56 loop.h
>*** loop.h	2001/10/29 22:13:40	1.56
>--- loop.h	2001/11/26 01:52:34
>*************** Software Foundation, 59 Temple Place - S
>*** 50,55 ****
>--- 50,60 ----
>  #define REGNO_FIRST_LUID(REGNO) uid_luid[REGNO_FIRST_UID (REGNO)]
>  #define REGNO_LAST_LUID(REGNO) uid_luid[REGNO_LAST_UID (REGNO)]
>  
>+ /* Nonzero iff INSN is between START and END, inclusive.  */
>+ #define INSN_IN_RANGE_P(INSN, START, END)	\
>+   (INSN_UID (INSN) < max_uid_for_loop		\
>+    && INSN_LUID (INSN) >= INSN_LUID (START)	\
>+    && INSN_LUID (INSN) <= INSN_LUID (END))
>  
>  /* A "basic induction variable" or biv is a pseudo reg that is set
>     (within this loop) only by incrementing or decrementing it.  */
>Index: unroll.c
>===================================================================
>RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
>retrieving revision 1.147
>diff -c -p -d -r1.147 unroll.c
>*** unroll.c	2001/11/21 00:50:56	1.147
>--- unroll.c	2001/11/26 01:52:34
>*************** loop_iterations (loop)
>*** 3480,3485 ****
>--- 3480,3486 ----
>    int unsigned_p, compare_dir, final_larger;
>    rtx last_loop_insn;
>    rtx reg_term;
>+   rtx insn;
>    struct iv_class *bl;
>  
>    loop_info->n_iterations = 0;
>*************** loop_iterations (loop)
>*** 3705,3710 ****
>--- 3706,3762 ----
>  
>    if (initial_value == 0)
>      return 0;
>+ 
>+   /* Some code transformations can result in code akin to
>+ 
>+ 	LOOP_BEG
>+ 	  goto start;
>+ 	top:
>+ 	  i++;
>+ 	start:
>+ 	  ...
>+ 	LOOP_CONT
>+ 	  if (i < n) goto top;
>+ 	LOOP_END
>+ 
>+      In this situation, we skip the increment the first time through
>+      the loop, which results in an incorrect estimate of the number
>+      of iterations.  As we did for GIVs above, adjust the initial value
>+      to compensate.  */
>+ 
>+   off_by_one = 0;
>+   for (insn = loop->start; insn != loop->top; insn = NEXT_INSN (insn))
>+     if (GET_CODE (insn) == JUMP_INSN)
>+       {
>+ 	if (any_uncondjump_p (insn)
>+ 	    && JUMP_LABEL (insn)
>+ 	    && INSN_IN_RANGE_P (JUMP_LABEL (insn), loop->top, loop->cont))
>+ 	  {
>+ 	    if (reg_set_between_p (bl->biv->src_reg, insn, JUMP_LABEL (insn)))
>+ 	      off_by_one = 1;
>+ 	    break;
>+ 	  }
>+ 	/* No idea what's going on.  */
>+ 	if (loop_dump_stream)
>+ 	  fprintf (loop_dump_stream,
>+ 		   "Loop iterations: Confused by jump before loop top.\n");
>+ 	return 0;
>+       }
>+ 
>+   if (off_by_one)
>+     {
>+       if (loop_dump_stream)
>+ 	fprintf (loop_dump_stream,
>+ 		 "Loop iterations: Basic induction var skips initial incr.\n");
>+       if (GET_CODE (increment) != CONST_INT)
>+ 	{
>+ 	  if (loop_dump_stream)
>+ 	    fprintf (loop_dump_stream,
>+ 		     "Loop iterations: Can't adjust with non-constant incr.\n");
>+ 	  return 0;
>+ 	}
>+       initial_value = plus_constant (initial_value, -INTVAL (increment));
>+     }
>  
>    unsigned_p = 0;
>    off_by_one = 0;
>

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

[Bryce McKinlay]

Corey Minyard wrote:

> I put a print in (I can't use gdb 5.0 with the output of gcc 3.0 on 
> Linux PowerPC),

Try:

Index: sysv4.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/config/rs6000/sysv4.h,v
retrieving revision 1.74
diff -u -r1.74 sysv4.h
--- sysv4.h     2001/11/22 02:19:56     1.74
+++ sysv4.h     2001/11/26 08:42:13
@@ -845,7 +845,7 @@
 
 /* Use DWARF 2 debugging information by default.  */
 #undef PREFERRED_DEBUGGING_TYPE
-#define        PREFERRED_DEBUGGING_TYPE DWARF2_DEBUG
+#define        PREFERRED_DEBUGGING_TYPE DBX_DEBUG
 
 /* Historically we have also supported stabs debugging.  */
 #define        DBX_DEBUGGING_INFO


Bryce.

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

[Bryce McKinlay]

Corey Minyard wrote:

> I put a print in (I can't use gdb 5.0 with the output of gcc 3.0 on 
> Linux PowerPC),

Try:

Index: sysv4.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/config/rs6000/sysv4.h,v
retrieving revision 1.74
diff -u -r1.74 sysv4.h
--- sysv4.h     2001/11/22 02:19:56     1.74
+++ sysv4.h     2001/11/26 08:42:13
@@ -845,7 +845,7 @@
 
 /* Use DWARF 2 debugging information by default.  */
 #undef PREFERRED_DEBUGGING_TYPE
-#define        PREFERRED_DEBUGGING_TYPE DWARF2_DEBUG
+#define        PREFERRED_DEBUGGING_TYPE DBX_DEBUG
 
 /* Historically we have also supported stabs debugging.  */
 #define        DBX_DEBUGGING_INFO


Bryce.

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

[Corey Minyard]

That patch looks a lot better than mine :-).  However, I'm getting a 
segv compiling unwind-dw2-fde.c.  I put a print in (I can't use gdb 5.0 
with the output of gcc 3.0 on Linux PowerPC), and it's dying in the line: 

  && INSN_IN_RANGE_P (JUMP_LABEL (insn), loop->top, loop->cont)

It looks like loop->top is alway NULL.  I'm working with a slightly old 
CVS, maybe I should update, or is this a real problem?

-Corey

Richard Henderson wrote:

>The problem is not limited to doloop -- the unroller ought
>to hit this problem as well.  I'm testing the following.
>
>
>
>r~
>
>
>
>Index: loop.c
>===================================================================
>RCS file: /cvs/gcc/gcc/gcc/loop.c,v
>retrieving revision 1.369
>diff -c -p -d -r1.369 loop.c
>*** loop.c	2001/11/15 23:44:56	1.369
>--- loop.c	2001/11/26 01:52:34
>*************** typedef struct loop_replace_args
>*** 282,293 ****
>    rtx insn;
>  } loop_replace_args;
>  
>- /* Nonzero iff INSN is between START and END, inclusive.  */
>- #define INSN_IN_RANGE_P(INSN, START, END)	\
>-   (INSN_UID (INSN) < max_uid_for_loop		\
>-    && INSN_LUID (INSN) >= INSN_LUID (START)	\
>-    && INSN_LUID (INSN) <= INSN_LUID (END))
>- 
>  /* Indirect_jump_in_function is computed once per function.  */
>  static int indirect_jump_in_function;
>  static int indirect_jump_in_function_p PARAMS ((rtx));
>--- 282,287 ----
>Index: loop.h
>===================================================================
>RCS file: /cvs/gcc/gcc/gcc/loop.h,v
>retrieving revision 1.56
>diff -c -p -d -r1.56 loop.h
>*** loop.h	2001/10/29 22:13:40	1.56
>--- loop.h	2001/11/26 01:52:34
>*************** Software Foundation, 59 Temple Place - S
>*** 50,55 ****
>--- 50,60 ----
>  #define REGNO_FIRST_LUID(REGNO) uid_luid[REGNO_FIRST_UID (REGNO)]
>  #define REGNO_LAST_LUID(REGNO) uid_luid[REGNO_LAST_UID (REGNO)]
>  
>+ /* Nonzero iff INSN is between START and END, inclusive.  */
>+ #define INSN_IN_RANGE_P(INSN, START, END)	\
>+   (INSN_UID (INSN) < max_uid_for_loop		\
>+    && INSN_LUID (INSN) >= INSN_LUID (START)	\
>+    && INSN_LUID (INSN) <= INSN_LUID (END))
>  
>  /* A "basic induction variable" or biv is a pseudo reg that is set
>     (within this loop) only by incrementing or decrementing it.  */
>Index: unroll.c
>===================================================================
>RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
>retrieving revision 1.147
>diff -c -p -d -r1.147 unroll.c
>*** unroll.c	2001/11/21 00:50:56	1.147
>--- unroll.c	2001/11/26 01:52:34
>*************** loop_iterations (loop)
>*** 3480,3485 ****
>--- 3480,3486 ----
>    int unsigned_p, compare_dir, final_larger;
>    rtx last_loop_insn;
>    rtx reg_term;
>+   rtx insn;
>    struct iv_class *bl;
>  
>    loop_info->n_iterations = 0;
>*************** loop_iterations (loop)
>*** 3705,3710 ****
>--- 3706,3762 ----
>  
>    if (initial_value == 0)
>      return 0;
>+ 
>+   /* Some code transformations can result in code akin to
>+ 
>+ 	LOOP_BEG
>+ 	  goto start;
>+ 	top:
>+ 	  i++;
>+ 	start:
>+ 	  ...
>+ 	LOOP_CONT
>+ 	  if (i < n) goto top;
>+ 	LOOP_END
>+ 
>+      In this situation, we skip the increment the first time through
>+      the loop, which results in an incorrect estimate of the number
>+      of iterations.  As we did for GIVs above, adjust the initial value
>+      to compensate.  */
>+ 
>+   off_by_one = 0;
>+   for (insn = loop->start; insn != loop->top; insn = NEXT_INSN (insn))
>+     if (GET_CODE (insn) == JUMP_INSN)
>+       {
>+ 	if (any_uncondjump_p (insn)
>+ 	    && JUMP_LABEL (insn)
>+ 	    && INSN_IN_RANGE_P (JUMP_LABEL (insn), loop->top, loop->cont))
>+ 	  {
>+ 	    if (reg_set_between_p (bl->biv->src_reg, insn, JUMP_LABEL (insn)))
>+ 	      off_by_one = 1;
>+ 	    break;
>+ 	  }
>+ 	/* No idea what's going on.  */
>+ 	if (loop_dump_stream)
>+ 	  fprintf (loop_dump_stream,
>+ 		   "Loop iterations: Confused by jump before loop top.\n");
>+ 	return 0;
>+       }
>+ 
>+   if (off_by_one)
>+     {
>+       if (loop_dump_stream)
>+ 	fprintf (loop_dump_stream,
>+ 		 "Loop iterations: Basic induction var skips initial incr.\n");
>+       if (GET_CODE (increment) != CONST_INT)
>+ 	{
>+ 	  if (loop_dump_stream)
>+ 	    fprintf (loop_dump_stream,
>+ 		     "Loop iterations: Can't adjust with non-constant incr.\n");
>+ 	  return 0;
>+ 	}
>+       initial_value = plus_constant (initial_value, -INTVAL (increment));
>+     }
>  
>    unsigned_p = 0;
>    off_by_one = 0;
>

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

[Corey Minyard]

[-- Attachment #1: Type: text/plain, Size: 483 bytes --]

Not all loops have loop->top set in this situation, because that's only 
set in bottom entry loops, it seems.

I've made some small changes.  Here's just the ones to unroll.c (I 
didn't include the move of the macro from loop.c into loop.h).

I'm also thinking that it would be good enough to let the loop run to 
loop->cont, and not use loop->top at all.  It's bootstrapping right now, 
so we'll see if this works.  I tried on a small testcase, and it seemed 
to work.

-Corey






[-- Attachment #2: v1 --]
[-- Type: text/plain, Size: 2046 bytes --]

Index: unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
retrieving revision 1.146
diff -u -r1.146 unroll.c
--- unroll.c	2001/11/16 17:08:12	1.146
+++ unroll.c	2001/11/26 16:44:55
@@ -3479,6 +3479,8 @@
   int unsigned_p, compare_dir, final_larger;
   rtx last_loop_insn;
   rtx reg_term;
+  rtx insn;
+  rtx end_loop_scan;
   struct iv_class *bl;
 
   loop_info->n_iterations = 0;
@@ -3704,6 +3706,62 @@
 
   if (initial_value == 0)
     return 0;
+
+  /* Some code transformations can result in code akin to
+
+	LOOP_BEG
+	  goto start;
+	top:
+	  i++;
+	start:
+	  ...
+	LOOP_CONT
+	  if (i < n) goto top;
+	LOOP_END
+
+     In this situation, we skip the increment the first time through
+     the loop, which results in an incorrect estimate of the number
+     of iterations.  As we did for GIVs above, adjust the initial value
+     to compensate.  */
+
+  off_by_one = 0;
+  if (loop->top)
+    end_loop_scan = loop->top;
+  else
+    end_loop_scan = loop->cont;
+
+  for (insn = loop->start; insn != end_loop_scan; insn = NEXT_INSN (insn))
+    if (GET_CODE (insn) == JUMP_INSN)
+      {
+	if (any_uncondjump_p (insn)
+	    && JUMP_LABEL (insn)
+	    && INSN_IN_RANGE_P (JUMP_LABEL (insn), insn, loop->end))
+	  {
+	    if (reg_set_between_p (bl->biv->src_reg, insn, JUMP_LABEL (insn)))
+	      off_by_one = 1;
+	    break;
+	  }
+	/* No idea what's going on.  */
+	if (loop_dump_stream)
+	  fprintf (loop_dump_stream,
+		   "Loop iterations: Confused by jump before loop top.\n");
+	return 0;
+      }
+
+  if (off_by_one)
+    {
+      if (loop_dump_stream)
+	fprintf (loop_dump_stream,
+		 "Loop iterations: Basic induction var skips initial incr.\n");
+      if (GET_CODE (increment) != CONST_INT)
+	{
+	  if (loop_dump_stream)
+	    fprintf (loop_dump_stream,
+		     "Loop iterations: Can't adjust with non-constant incr.\n");
+	  return 0;
+	}
+      initial_value = plus_constant (initial_value, -INTVAL (increment));
+    }
 
   unsigned_p = 0;
   off_by_one = 0;

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

[Corey Minyard]

It just finished bootstrapping successfully.

-Corey

Corey Minyard wrote:

> Not all loops have loop->top set in this situation, because that's 
> only set in bottom entry loops, it seems.
>
> I've made some small changes.  Here's just the ones to unroll.c (I 
> didn't include the move of the macro from loop.c into loop.h).
>
> I'm also thinking that it would be good enough to let the loop run to 
> loop->cont, and not use loop->top at all.  It's bootstrapping right 
> now, so we'll see if this works.  I tried on a small testcase, and it 
> seemed to work.
>
> -Corey

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

[Corey Minyard]

It just finished bootstrapping successfully.

-Corey

Corey Minyard wrote:

> Not all loops have loop->top set in this situation, because that's 
> only set in bottom entry loops, it seems.
>
> I've made some small changes.  Here's just the ones to unroll.c (I 
> didn't include the move of the macro from loop.c into loop.h).
>
> I'm also thinking that it would be good enough to let the loop run to 
> loop->cont, and not use loop->top at all.  It's bootstrapping right 
> now, so we'll see if this works.  I tried on a small testcase, and it 
> seemed to work.
>
> -Corey

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

[Richard Henderson]

On Mon, Nov 26, 2001 at 10:59:25AM -0600, Corey Minyard wrote:
> Not all loops have loop->top set in this situation, because that's only 
> set in bottom entry loops, it seems.

Oh, duh.  Look at scan_loop: loop->top is set in exactly the condition
that we're interested in and no other.  That simplifies the code in
loop_iterations greatly.

ia64 bootstrap underway.


r~



Index: unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
retrieving revision 1.147
diff -c -p -d -r1.147 unroll.c
*** unroll.c	2001/11/21 00:50:56	1.147
--- unroll.c	2001/11/26 21:46:30
*************** loop_iterations (loop)
*** 3480,3485 ****
--- 3480,3486 ----
    int unsigned_p, compare_dir, final_larger;
    rtx last_loop_insn;
    rtx reg_term;
+   rtx insn;
    struct iv_class *bl;
  
    loop_info->n_iterations = 0;
*************** loop_iterations (loop)
*** 3705,3710 ****
--- 3706,3747 ----
  
    if (initial_value == 0)
      return 0;
+ 
+   /* Some code transformations can result in code akin to
+ 
+ 	LOOP_BEG
+ 	  goto start;
+ 	top:
+ 	  i++;
+ 	start:
+ 	  ...
+ 	LOOP_CONT
+ 	  if (i < n) goto top;
+ 	LOOP_END
+ 
+      We'll have already detected this form of loop in scan_loop,
+      and set loop->top and loop->scan_start appropriately.
+ 
+      In this situation, we skip the increment the first time through
+      the loop, which results in an incorrect estimate of the number
+      of iterations.  As we did for GIVs above, adjust the initial value
+      to compensate.  */
+ 
+   if (loop->top
+       && reg_set_between_p (bl->biv->src_reg, loop->top, loop->scan_start))
+     {
+       if (loop_dump_stream)
+ 	fprintf (loop_dump_stream,
+ 		 "Loop iterations: Basic induction var skips initial incr.\n");
+       if (GET_CODE (increment) != CONST_INT)
+ 	{
+ 	  if (loop_dump_stream)
+ 	    fprintf (loop_dump_stream,
+ 		     "Loop iterations: Can't adjust with non-constant incr.\n");
+ 	  return 0;
+ 	}
+       initial_value = plus_constant (initial_value, -INTVAL (increment));
+     }
  
    unsigned_p = 0;
    off_by_one = 0;

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

[Corey Minyard]

Richard Henderson wrote:

>On Mon, Nov 26, 2001 at 10:59:25AM -0600, Corey Minyard wrote:
>
>>Not all loops have loop->top set in this situation, because that's only 
>>set in bottom entry loops, it seems.
>>
>
>Oh, duh.  Look at scan_loop: loop->top is set in exactly the condition
>that we're interested in and no other.  That simplifies the code in
>loop_iterations greatly.
>
>ia64 bootstrap underway.
>
Thanks, it passes my simple testcase.  I'm bootstrapping on PowerPC now.

You probably noticed, but the insn variable is no longer required.

-Corey

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

[Corey Minyard]

Richard Henderson wrote:

>On Mon, Nov 26, 2001 at 10:59:25AM -0600, Corey Minyard wrote:
>
>>Not all loops have loop->top set in this situation, because that's only 
>>set in bottom entry loops, it seems.
>>
>
>Oh, duh.  Look at scan_loop: loop->top is set in exactly the condition
>that we're interested in and no other.  That simplifies the code in
>loop_iterations greatly.
>
>ia64 bootstrap underway.
>
Thanks, it passes my simple testcase.  I'm bootstrapping on PowerPC now.

You probably noticed, but the insn variable is no longer required.

-Corey

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

[Corey Minyard]

Richard Henderson wrote:

>On Mon, Nov 26, 2001 at 10:59:25AM -0600, Corey Minyard wrote:
>
>>Not all loops have loop->top set in this situation, because that's only 
>>set in bottom entry loops, it seems.
>>
>
>Oh, duh.  Look at scan_loop: loop->top is set in exactly the condition
>that we're interested in and no other.  That simplifies the code in
>loop_iterations greatly.
>
>ia64 bootstrap underway.
>
The PowerPC bootstrap completed.  It looks good here.

-Corey

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

[Richard Henderson]

Unfortunately, it causes a regression on x86 for 
gcc.c-torture/execute/20011008-3.c at -O3.  I've
not yet examined why...


r~

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

[Corey Minyard]

Richard Henderson wrote:

>Unfortunately, it causes a regression on x86 for 
>gcc.c-torture/execute/20011008-3.c at -O3.  I've
>not yet examined why...
>
>
>r~
>
I'll spend some time looking at it.

-Corey

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

[Richard Henderson]

I've got a hack that appears to work -- the start label
must be before the CONT marker.

I'm nervous about this patch now, because I don't think
we really understand the exact situation in which the
original problem can ocurr.  But as I've as yet got no
further failures to look at, I'll commit it anyway.


r~


	* unroll.c (loop_iterations): Detect one situation in which we
	overestimate the number of iterations.

Index: unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
retrieving revision 1.147
diff -c -p -d -r1.147 unroll.c
*** unroll.c	2001/11/21 00:50:56	1.147
--- unroll.c	2001/11/27 18:27:08
*************** loop_iterations (loop)
*** 3706,3711 ****
--- 3706,3746 ----
    if (initial_value == 0)
      return 0;
  
+   /* Some code transformations can result in code akin to
+ 
+ 	  tmp = i + 1;
+ 	  ...
+ 	  goto scan_start;
+ 	top:
+ 	  tmp = tmp + 1;
+ 	scan_start:
+ 	  i = tmp;
+ 	  if (i < n) goto top;
+ 
+      We'll have already detected this form of loop in scan_loop,
+      and set loop->top and loop->scan_start appropriately.
+ 
+      In this situation, we skip the increment the first time through
+      the loop, which results in an incorrect estimate of the number
+      of iterations.  Adjust the initial value to compensate.  */
+ 
+   if (loop->scan_start && loop->cont
+       && INSN_LUID (loop->scan_start) < INSN_LUID (loop->cont)
+       && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
+     {
+       if (loop_dump_stream)
+ 	fprintf (loop_dump_stream,
+ 	         "Loop iterations: Basic induction var skips initial incr.\n");
+       if (GET_CODE (increment) != CONST_INT)
+ 	{
+ 	  if (loop_dump_stream)
+ 	    fprintf (loop_dump_stream,
+ 		     "Loop iterations: Can't adjust with non-constant incr.\n");
+ 	  return 0;
+ 	}
+       initial_value = plus_constant (initial_value, -INTVAL (increment));
+     }
+ 
    unsigned_p = 0;
    off_by_one = 0;
    switch (comparison_code)

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

[Corey Minyard]

[-- Attachment #1: Type: text/plain, Size: 1135 bytes --]

Unforunately, this causes my original problem to come back.  I'm nervous 
about this patch, too, I don't understand it at all.

The loop where the problem occurred in the regression was reversed after 
this was done, but I turned off the reversal and it had the same 
problem.  But it looks like the rest of the loop optimization code 
handles this (jumping over the first increment) situation correctly, the 
only problem occurrred in the doloop code.

I tried moving this test to doloop_modify_runtime in doloop.c and adding 
the increment to the "diff" rtx in this situation, and it works in my 
simple testcase and didn't cause the problem in the regression.  I 
haven't bootstrapped or run any tests yet, and I can't test the ia64 
case with it.  But I'll start a bootstrap now.

-Corey

Richard Henderson wrote:

>I've got a hack that appears to work -- the start label
>must be before the CONT marker.
>
>I'm nervous about this patch now, because I don't think
>we really understand the exact situation in which the
>original problem can ocurr.  But as I've as yet got no
>further failures to look at, I'll commit it anyway.
>


[-- Attachment #2: gcc-ppc4.diff --]
[-- Type: text/plain, Size: 1441 bytes --]

Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.12
diff -u -p -r1.12 doloop.c
--- doloop.c	2001/11/16 02:26:38	1.12
+++ doloop.c	2001/11/27 19:45:17
@@ -546,6 +546,8 @@ doloop_modify_runtime (loop, iterations_
   rtx increment;
   int unsigned_p;
   enum rtx_code comparison_code;
+  struct loop_ivs *ivs = LOOP_IVS (loop);
+  struct iv_class *bl = REG_IV_CLASS (ivs, REGNO (loop_info->iteration_var));
 
   increment = loop_info->increment;
   initial_value = loop_info->initial_value;
@@ -595,6 +597,24 @@ doloop_modify_runtime (loop, iterations_
 			      copy_rtx (neg_inc ? initial_value : final_value),
 			      copy_rtx (neg_inc ? final_value : initial_value),
 			      NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
+
+  if (loop->top
+      && reg_set_between_p (bl->biv->src_reg, loop->top, loop->scan_start))
+    {
+      if (loop_dump_stream)
+	fprintf (loop_dump_stream,
+		 "Loop iterations: Basic induction var skips initial incr.\n");
+      if (GET_CODE (increment) != CONST_INT)
+	{
+	  if (loop_dump_stream)
+	    fprintf (loop_dump_stream,
+		     "Loop iterations: Can't adjust with non-constant incr.\n");
+	  return 0;
+	}
+      diff = expand_simple_binop (GET_MODE (diff), PLUS,
+				  diff, GEN_INT (INTVAL (increment)),
+				  NULL_RTX, 1, OPTAB_LIB_WIDEN);
+    }
 
   if (abs_inc * loop_info->unroll_number != 1)
     {

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

[Richard Henderson]

On Tue, Nov 27, 2001 at 01:52:41PM -0600, Corey Minyard wrote:
> Unforunately, this causes my original problem to come back.  I'm nervous 
> about this patch, too, I don't understand it at all.

This original problem is the Ada test case you forwarded,
or something else?

> I tried moving this test to doloop_modify_runtime in doloop.c and adding 
> the increment to the "diff" rtx in this situation, and it works in my 
> simple testcase and didn't cause the problem in the regression.

Hum.  Perhaps you're right -- putting this change in doloop
will limit liability, so to speak.  I'll move my change.


r~

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

[Corey Minyard]

Richard Henderson wrote:

>On Tue, Nov 27, 2001 at 01:52:41PM -0600, Corey Minyard wrote:
>
>>Unforunately, this causes my original problem to come back.  I'm nervous 
>>about this patch, too, I don't understand it at all.
>>
>
>This original problem is the Ada test case you forwarded,
>or something else? 
>
yes, the original Ada testcase.

>>I tried moving this test to doloop_modify_runtime in doloop.c and adding 
>>the increment to the "diff" rtx in this situation, and it works in my 
>>simple testcase and didn't cause the problem in the regression.
>>
>
>Hum.  Perhaps you're right -- putting this change in doloop
>will limit liability, so to speak.  I'll move my change.
>
Are you moving back to the original loop test?  I think the original 
test you had didn't work because it wasn't the doloop case, but if you 
put it in the doloop code it should work properly.

Bummer, my bootstrap just segv-ed.  Oh well, a little more work, some 
variable was probably NULL.

-Corey

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

[Richard Henderson]

On Tue, Nov 27, 2001 at 03:26:43PM -0600, Corey Minyard wrote:
> Are you moving back to the original loop test?  I think the original 
> test you had didn't work because it wasn't the doloop case, but if you 
> put it in the doloop code it should work properly.

I'm taking out the CONT test, yes.  But I'm keeping the LUID
test against the BIV initializer rather than scanning with
reg_set_between_p.


r~


Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.12
diff -c -p -d -r1.12 doloop.c
*** doloop.c	2001/11/16 02:26:38	1.12
--- doloop.c	2001/11/27 22:06:50
*************** doloop_modify_runtime (loop, iterations_
*** 596,601 ****
--- 596,641 ----
  			      copy_rtx (neg_inc ? final_value : initial_value),
  			      NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
  
+   /* Some code transformations can result in code akin to
+ 
+ 	  tmp = i + 1;
+ 	  ...
+ 	  goto scan_start;
+ 	top:
+ 	  tmp = tmp + 1;
+ 	scan_start:
+ 	  i = tmp;
+ 	  if (i < n) goto top;
+ 
+      We'll have already detected this form of loop in scan_loop,
+      and set loop->top and loop->scan_start appropriately.
+ 
+      In this situation, we skip the increment the first time through
+      the loop, which results in an incorrect estimate of the number
+      of iterations.  Adjust the difference to compensate.  */
+   /* ??? Logically, it would seem this belongs in loop_iterations.
+      However, this causes regressions e.g. on x86 execute/20011008-3.c,
+      so I do not believe we've properly characterized the exact nature
+      of the problem.  In the meantime, this fixes execute/20011126-2.c
+      on ia64 and some Ada front end miscompilation on ppc.  */
+ 
+   if (loop->scan_start)
+     {
+       struct loop_ivs *ivs = LOOP_IVS (loop);
+       struct iv_class *bl
+ 	= REG_IV_CLASS (ivs, REGNO (loop_info->iteration_var));
+ 
+       if (INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
+ 	{
+ 	  if (loop_dump_stream)
+ 	    fprintf (loop_dump_stream,
+ 	         "Doloop: Basic induction var skips initial incr.\n");
+ 
+ 	  diff = expand_simple_binop (mode, PLUS, diff, increment, diff,
+ 				      unsigned_p, OPTAB_LIB_WIDEN);
+ 	}
+     }
+ 
    if (abs_inc * loop_info->unroll_number != 1)
      {
        int shift_count;

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

[Corey Minyard]

[-- Attachment #1.1: Type: text/plain, Size: 621 bytes --]



Richard Henderson wrote:

>On Tue, Nov 27, 2001 at 03:26:43PM -0600, Corey Minyard wrote:
>
>>Are you moving back to the original loop test?  I think the original 
>>test you had didn't work because it wasn't the doloop case, but if you 
>>put it in the doloop code it should work properly.
>>
>
>I'm taking out the CONT test, yes.  But I'm keeping the LUID
>test against the BIV initializer rather than scanning with
>reg_set_between_p.
>
You will need to set the bl variable a little differently, in case its a 
GIV.  I've attached a patch.  That was the cause of my segv earlier. 
 Bootstrapping again....

-Corey



[-- Attachment #1.2: Type: text/html, Size: 1027 bytes --]

[-- Attachment #2: gcc-ppc5.diff --]
[-- Type: text/plain, Size: 2290 bytes --]

Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.12
diff -u -p -r1.12 doloop.c
--- doloop.c	2001/11/16 02:26:38	1.12
+++ doloop.c	2001/11/27 23:01:46
@@ -596,6 +596,59 @@ doloop_modify_runtime (loop, iterations_
 			      copy_rtx (neg_inc ? final_value : initial_value),
 			      NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
 
+  /* Some code transformations can result in code akin to
+
+	  tmp = i + 1;
+	  ...
+	  goto scan_start;
+	top:
+	  tmp = tmp + 1;
+	scan_start:
+	  i = tmp;
+	  if (i < n) goto top;
+
+     We'll have already detected this form of loop in scan_loop,
+     and set loop->top and loop->scan_start appropriately.
+
+     In this situation, we skip the increment the first time through
+     the loop, which results in an incorrect estimate of the number
+     of iterations.  Adjust the difference to compensate.  */
+  /* ??? Logically, it would seem this belongs in loop_iterations.
+     However, this causes regressions e.g. on x86 execute/20011008-3.c,
+     so I do not believe we've properly characterized the exact nature
+     of the problem.  In the meantime, this fixes execute/20011126-2.c
+     on ia64 and some Ada front end miscompilation on ppc.  */
+
+  if (loop->scan_start)
+    {
+      rtx iteration_var;
+      struct loop_ivs *ivs = LOOP_IVS (loop);
+      struct iv_class *bl;
+
+      iteration_var = loop_info->iteration_var;
+
+      if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
+	bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
+      else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
+	{
+	  struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
+	  bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
+	}
+      else
+	abort(); /* iteration var must be an induction variable to get
+		    to here. */
+
+      if (INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
+	{
+	  if (loop_dump_stream)
+	    fprintf (loop_dump_stream,
+	         "Doloop: Basic induction var skips initial incr.\n");
+
+	  diff = expand_simple_binop (mode, PLUS, diff, increment, diff,
+				      unsigned_p, OPTAB_LIB_WIDEN);
+	}
+    }
+
   if (abs_inc * loop_info->unroll_number != 1)
     {
       int shift_count;

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

[Richard Henderson]

On Tue, Nov 27, 2001 at 05:05:35PM -0600, Corey Minyard wrote:
> You will need to set the bl variable a little differently, in case its a 
> GIV.  I've attached a patch.  That was the cause of my segv earlier. 

Ug.  I should have done a complete bootstrap with ia64 as well --
Seems that some cases the BIV initializer is constructed by loop,
or something.  In any case, INSN_LUID aborts.

>  Bootstrapping again....

Me too.  Current patch appended.


r~



Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.13
diff -c -p -d -r1.13 doloop.c
*** doloop.c	2001/11/27 22:09:10	1.13
--- doloop.c	2001/11/27 23:29:17
*************** doloop_modify_runtime (loop, iterations_
*** 622,631 ****
    if (loop->scan_start)
      {
        struct loop_ivs *ivs = LOOP_IVS (loop);
!       struct iv_class *bl
! 	= REG_IV_CLASS (ivs, REGNO (loop_info->iteration_var));
  
!       if (INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
  	{
  	  if (loop_dump_stream)
  	    fprintf (loop_dump_stream,
--- 622,642 ----
    if (loop->scan_start)
      {
        struct loop_ivs *ivs = LOOP_IVS (loop);
!       struct iv_class *bl;
  
!       if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
! 	bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
!       else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
! 	{
! 	  struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
! 	  bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
! 	}
!       else
! 	/* Iteration var must be an induction variable to get here.  */
! 	abort();
! 
!       if (INSN_UID (bl->biv->insn) < max_uid_for_loop
! 	  && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
  	{
  	  if (loop_dump_stream)
  	    fprintf (loop_dump_stream,

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

[Corey Minyard]

Richard Henderson wrote:

>On Tue, Nov 27, 2001 at 05:05:35PM -0600, Corey Minyard wrote:
>
>>You will need to set the bl variable a little differently, in case its a 
>>GIV.  I've attached a patch.  That was the cause of my segv earlier. 
>>
>
>Ug.  I should have done a complete bootstrap with ia64 as well --
>Seems that some cases the BIV initializer is constructed by loop,
>or something.  In any case, INSN_LUID aborts.
>
>> Bootstrapping again....
>>
>
>Me too.  Current patch appended.
>
I had to add the iteration_var variable, but it has fully bootstrapped. 
 I'll try to set up to run regressions tomorrow and see what happens.

Thanks for you help.

-Corey

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

[Corey Minyard]

Richard Henderson wrote:

>On Tue, Nov 27, 2001 at 05:05:35PM -0600, Corey Minyard wrote:
>
>>You will need to set the bl variable a little differently, in case its a 
>>GIV.  I've attached a patch.  That was the cause of my segv earlier. 
>>
>
>Ug.  I should have done a complete bootstrap with ia64 as well --
>Seems that some cases the BIV initializer is constructed by loop,
>or something.  In any case, INSN_LUID aborts.
>
>> Bootstrapping again....
>>
>
>Me too.  Current patch appended.
>
I had to add the iteration_var variable, but it has fully bootstrapped. 
 I'll try to set up to run regressions tomorrow and see what happens.

Thanks for you help.

-Corey

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

[Richard Henderson]

On Tue, Nov 27, 2001 at 05:05:35PM -0600, Corey Minyard wrote:
> You will need to set the bl variable a little differently, in case its a 
> GIV.  I've attached a patch.  That was the cause of my segv earlier. 

Ug.  I should have done a complete bootstrap with ia64 as well --
Seems that some cases the BIV initializer is constructed by loop,
or something.  In any case, INSN_LUID aborts.

>  Bootstrapping again....

Me too.  Current patch appended.


r~



Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.13
diff -c -p -d -r1.13 doloop.c
*** doloop.c	2001/11/27 22:09:10	1.13
--- doloop.c	2001/11/27 23:29:17
*************** doloop_modify_runtime (loop, iterations_
*** 622,631 ****
    if (loop->scan_start)
      {
        struct loop_ivs *ivs = LOOP_IVS (loop);
!       struct iv_class *bl
! 	= REG_IV_CLASS (ivs, REGNO (loop_info->iteration_var));
  
!       if (INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
  	{
  	  if (loop_dump_stream)
  	    fprintf (loop_dump_stream,
--- 622,642 ----
    if (loop->scan_start)
      {
        struct loop_ivs *ivs = LOOP_IVS (loop);
!       struct iv_class *bl;
  
!       if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
! 	bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
!       else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
! 	{
! 	  struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
! 	  bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
! 	}
!       else
! 	/* Iteration var must be an induction variable to get here.  */
! 	abort();
! 
!       if (INSN_UID (bl->biv->insn) < max_uid_for_loop
! 	  && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
  	{
  	  if (loop_dump_stream)
  	    fprintf (loop_dump_stream,

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

[Corey Minyard]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2940 bytes --]

Richard Henderson wrote:

  On Tue, Nov 27, 2001 at 03:26:43PM -0600, Corey Minyard wrote:
  
    Are you moving back to the original loop test?  I think the original test you had didn't work because it wasn't the doloop case, but if you put it in the doloop code it should work properly.
    
    I'm taking out the CONT test, yes.  But I'm keeping the LUID test against the BIV initializer rather than scanning with reg_set_between_p.
    
You will need to set the bl variable a little differently, in case its a
GIV.  I've attached a patch.  That was the cause of my segv earlier.  Bootstrapping
again....
    
-Corey
    
    
    
    
Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.12
diff -u -p -r1.12 doloop.c
--- doloop.c	2001/11/16 02:26:38	1.12
+++ doloop.c	2001/11/27 23:01:46
@@ -596,6 +596,59 @@ doloop_modify_runtime (loop, iterations_
 			      copy_rtx (neg_inc ? final_value : initial_value),
 			      NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
 
+  /* Some code transformations can result in code akin to
+
+	  tmp = i + 1;
+	  ...
+	  goto scan_start;
+	top:
+	  tmp = tmp + 1;
+	scan_start:
+	  i = tmp;
+	  if (i < n) goto top;
+
+     We'll have already detected this form of loop in scan_loop,
+     and set loop->top and loop->scan_start appropriately.
+
+     In this situation, we skip the increment the first time through
+     the loop, which results in an incorrect estimate of the number
+     of iterations.  Adjust the difference to compensate.  */
+  /* ??? Logically, it would seem this belongs in loop_iterations.
+     However, this causes regressions e.g. on x86 execute/20011008-3.c,
+     so I do not believe we've properly characterized the exact nature
+     of the problem.  In the meantime, this fixes execute/20011126-2.c
+     on ia64 and some Ada front end miscompilation on ppc.  */
+
+  if (loop->scan_start)
+    {
+      rtx iteration_var;
+      struct loop_ivs *ivs = LOOP_IVS (loop);
+      struct iv_class *bl;
+
+      iteration_var = loop_info->iteration_var;
+
+      if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
+	bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
+      else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
+	{
+	  struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
+	  bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
+	}
+      else
+	abort(); /* iteration var must be an induction variable to get
+		    to here. */
+
+      if (INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
+	{
+	  if (loop_dump_stream)
+	    fprintf (loop_dump_stream,
+	         "Doloop: Basic induction var skips initial incr.\n");
+
+	  diff = expand_simple_binop (mode, PLUS, diff, increment, diff,
+				      unsigned_p, OPTAB_LIB_WIDEN);
+	}
+    }
+
   if (abs_inc * loop_info->unroll_number != 1)
     {
       int shift_count;

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

[Richard Henderson]

On Tue, Nov 27, 2001 at 03:26:43PM -0600, Corey Minyard wrote:
> Are you moving back to the original loop test?  I think the original 
> test you had didn't work because it wasn't the doloop case, but if you 
> put it in the doloop code it should work properly.

I'm taking out the CONT test, yes.  But I'm keeping the LUID
test against the BIV initializer rather than scanning with
reg_set_between_p.


r~


Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.12
diff -c -p -d -r1.12 doloop.c
*** doloop.c	2001/11/16 02:26:38	1.12
--- doloop.c	2001/11/27 22:06:50
*************** doloop_modify_runtime (loop, iterations_
*** 596,601 ****
--- 596,641 ----
  			      copy_rtx (neg_inc ? final_value : initial_value),
  			      NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
  
+   /* Some code transformations can result in code akin to
+ 
+ 	  tmp = i + 1;
+ 	  ...
+ 	  goto scan_start;
+ 	top:
+ 	  tmp = tmp + 1;
+ 	scan_start:
+ 	  i = tmp;
+ 	  if (i < n) goto top;
+ 
+      We'll have already detected this form of loop in scan_loop,
+      and set loop->top and loop->scan_start appropriately.
+ 
+      In this situation, we skip the increment the first time through
+      the loop, which results in an incorrect estimate of the number
+      of iterations.  Adjust the difference to compensate.  */
+   /* ??? Logically, it would seem this belongs in loop_iterations.
+      However, this causes regressions e.g. on x86 execute/20011008-3.c,
+      so I do not believe we've properly characterized the exact nature
+      of the problem.  In the meantime, this fixes execute/20011126-2.c
+      on ia64 and some Ada front end miscompilation on ppc.  */
+ 
+   if (loop->scan_start)
+     {
+       struct loop_ivs *ivs = LOOP_IVS (loop);
+       struct iv_class *bl
+ 	= REG_IV_CLASS (ivs, REGNO (loop_info->iteration_var));
+ 
+       if (INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
+ 	{
+ 	  if (loop_dump_stream)
+ 	    fprintf (loop_dump_stream,
+ 	         "Doloop: Basic induction var skips initial incr.\n");
+ 
+ 	  diff = expand_simple_binop (mode, PLUS, diff, increment, diff,
+ 				      unsigned_p, OPTAB_LIB_WIDEN);
+ 	}
+     }
+ 
    if (abs_inc * loop_info->unroll_number != 1)
      {
        int shift_count;

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

[Corey Minyard]

Richard Henderson wrote:

>On Tue, Nov 27, 2001 at 01:52:41PM -0600, Corey Minyard wrote:
>
>>Unforunately, this causes my original problem to come back.  I'm nervous 
>>about this patch, too, I don't understand it at all.
>>
>
>This original problem is the Ada test case you forwarded,
>or something else? 
>
yes, the original Ada testcase.

>>I tried moving this test to doloop_modify_runtime in doloop.c and adding 
>>the increment to the "diff" rtx in this situation, and it works in my 
>>simple testcase and didn't cause the problem in the regression.
>>
>
>Hum.  Perhaps you're right -- putting this change in doloop
>will limit liability, so to speak.  I'll move my change.
>
Are you moving back to the original loop test?  I think the original 
test you had didn't work because it wasn't the doloop case, but if you 
put it in the doloop code it should work properly.

Bummer, my bootstrap just segv-ed.  Oh well, a little more work, some 
variable was probably NULL.

-Corey

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

[Richard Henderson]

On Tue, Nov 27, 2001 at 01:52:41PM -0600, Corey Minyard wrote:
> Unforunately, this causes my original problem to come back.  I'm nervous 
> about this patch, too, I don't understand it at all.

This original problem is the Ada test case you forwarded,
or something else?

> I tried moving this test to doloop_modify_runtime in doloop.c and adding 
> the increment to the "diff" rtx in this situation, and it works in my 
> simple testcase and didn't cause the problem in the regression.

Hum.  Perhaps you're right -- putting this change in doloop
will limit liability, so to speak.  I'll move my change.


r~

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

[Corey Minyard]

Unforunately, this causes my original problem to come back.  I'm nervous 
about this patch, too, I don't understand it at all.

The loop where the problem occurred in the regression was reversed after 
this was done, but I turned off the reversal and it had the same 
problem.  But it looks like the rest of the loop optimization code 
handles this (jumping over the first increment) situation correctly, the 
only problem occurrred in the doloop code.

I tried moving this test to doloop_modify_runtime in doloop.c and adding 
the increment to the "diff" rtx in this situation, and it works in my 
simple testcase and didn't cause the problem in the regression.  I 
haven't bootstrapped or run any tests yet, and I can't test the ia64 
case with it.  But I'll start a bootstrap now.

-Corey

Richard Henderson wrote:

>I've got a hack that appears to work -- the start label
>must be before the CONT marker.
>
>I'm nervous about this patch now, because I don't think
>we really understand the exact situation in which the
>original problem can ocurr.  But as I've as yet got no
>further failures to look at, I'll commit it anyway.
>

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

[Richard Henderson]

I've got a hack that appears to work -- the start label
must be before the CONT marker.

I'm nervous about this patch now, because I don't think
we really understand the exact situation in which the
original problem can ocurr.  But as I've as yet got no
further failures to look at, I'll commit it anyway.


r~


	* unroll.c (loop_iterations): Detect one situation in which we
	overestimate the number of iterations.

Index: unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
retrieving revision 1.147
diff -c -p -d -r1.147 unroll.c
*** unroll.c	2001/11/21 00:50:56	1.147
--- unroll.c	2001/11/27 18:27:08
*************** loop_iterations (loop)
*** 3706,3711 ****
--- 3706,3746 ----
    if (initial_value == 0)
      return 0;
  
+   /* Some code transformations can result in code akin to
+ 
+ 	  tmp = i + 1;
+ 	  ...
+ 	  goto scan_start;
+ 	top:
+ 	  tmp = tmp + 1;
+ 	scan_start:
+ 	  i = tmp;
+ 	  if (i < n) goto top;
+ 
+      We'll have already detected this form of loop in scan_loop,
+      and set loop->top and loop->scan_start appropriately.
+ 
+      In this situation, we skip the increment the first time through
+      the loop, which results in an incorrect estimate of the number
+      of iterations.  Adjust the initial value to compensate.  */
+ 
+   if (loop->scan_start && loop->cont
+       && INSN_LUID (loop->scan_start) < INSN_LUID (loop->cont)
+       && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
+     {
+       if (loop_dump_stream)
+ 	fprintf (loop_dump_stream,
+ 	         "Loop iterations: Basic induction var skips initial incr.\n");
+       if (GET_CODE (increment) != CONST_INT)
+ 	{
+ 	  if (loop_dump_stream)
+ 	    fprintf (loop_dump_stream,
+ 		     "Loop iterations: Can't adjust with non-constant incr.\n");
+ 	  return 0;
+ 	}
+       initial_value = plus_constant (initial_value, -INTVAL (increment));
+     }
+ 
    unsigned_p = 0;
    off_by_one = 0;
    switch (comparison_code)

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

[Corey Minyard]

Richard Henderson wrote:

>Unfortunately, it causes a regression on x86 for 
>gcc.c-torture/execute/20011008-3.c at -O3.  I've
>not yet examined why...
>
>
>r~
>
I'll spend some time looking at it.

-Corey

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

[Richard Henderson]

Unfortunately, it causes a regression on x86 for 
gcc.c-torture/execute/20011008-3.c at -O3.  I've
not yet examined why...


r~

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

[Corey Minyard]

Richard Henderson wrote:

>On Mon, Nov 26, 2001 at 10:59:25AM -0600, Corey Minyard wrote:
>
>>Not all loops have loop->top set in this situation, because that's only 
>>set in bottom entry loops, it seems.
>>
>
>Oh, duh.  Look at scan_loop: loop->top is set in exactly the condition
>that we're interested in and no other.  That simplifies the code in
>loop_iterations greatly.
>
>ia64 bootstrap underway.
>
The PowerPC bootstrap completed.  It looks good here.

-Corey

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

[Richard Henderson]

On Mon, Nov 26, 2001 at 10:59:25AM -0600, Corey Minyard wrote:
> Not all loops have loop->top set in this situation, because that's only 
> set in bottom entry loops, it seems.

Oh, duh.  Look at scan_loop: loop->top is set in exactly the condition
that we're interested in and no other.  That simplifies the code in
loop_iterations greatly.

ia64 bootstrap underway.


r~



Index: unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
retrieving revision 1.147
diff -c -p -d -r1.147 unroll.c
*** unroll.c	2001/11/21 00:50:56	1.147
--- unroll.c	2001/11/26 21:46:30
*************** loop_iterations (loop)
*** 3480,3485 ****
--- 3480,3486 ----
    int unsigned_p, compare_dir, final_larger;
    rtx last_loop_insn;
    rtx reg_term;
+   rtx insn;
    struct iv_class *bl;
  
    loop_info->n_iterations = 0;
*************** loop_iterations (loop)
*** 3705,3710 ****
--- 3706,3747 ----
  
    if (initial_value == 0)
      return 0;
+ 
+   /* Some code transformations can result in code akin to
+ 
+ 	LOOP_BEG
+ 	  goto start;
+ 	top:
+ 	  i++;
+ 	start:
+ 	  ...
+ 	LOOP_CONT
+ 	  if (i < n) goto top;
+ 	LOOP_END
+ 
+      We'll have already detected this form of loop in scan_loop,
+      and set loop->top and loop->scan_start appropriately.
+ 
+      In this situation, we skip the increment the first time through
+      the loop, which results in an incorrect estimate of the number
+      of iterations.  As we did for GIVs above, adjust the initial value
+      to compensate.  */
+ 
+   if (loop->top
+       && reg_set_between_p (bl->biv->src_reg, loop->top, loop->scan_start))
+     {
+       if (loop_dump_stream)
+ 	fprintf (loop_dump_stream,
+ 		 "Loop iterations: Basic induction var skips initial incr.\n");
+       if (GET_CODE (increment) != CONST_INT)
+ 	{
+ 	  if (loop_dump_stream)
+ 	    fprintf (loop_dump_stream,
+ 		     "Loop iterations: Can't adjust with non-constant incr.\n");
+ 	  return 0;
+ 	}
+       initial_value = plus_constant (initial_value, -INTVAL (increment));
+     }
  
    unsigned_p = 0;
    off_by_one = 0;

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

[Corey Minyard]

Not all loops have loop->top set in this situation, because that's only 
set in bottom entry loops, it seems.

I've made some small changes.  Here's just the ones to unroll.c (I 
didn't include the move of the macro from loop.c into loop.h).

I'm also thinking that it would be good enough to let the loop run to 
loop->cont, and not use loop->top at all.  It's bootstrapping right now, 
so we'll see if this works.  I tried on a small testcase, and it seemed 
to work.

-Corey

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

[Richard Henderson]

The problem is not limited to doloop -- the unroller ought
to hit this problem as well.  I'm testing the following.



r~



Index: loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.369
diff -c -p -d -r1.369 loop.c
*** loop.c	2001/11/15 23:44:56	1.369
--- loop.c	2001/11/26 01:52:34
*************** typedef struct loop_replace_args
*** 282,293 ****
    rtx insn;
  } loop_replace_args;
  
- /* Nonzero iff INSN is between START and END, inclusive.  */
- #define INSN_IN_RANGE_P(INSN, START, END)	\
-   (INSN_UID (INSN) < max_uid_for_loop		\
-    && INSN_LUID (INSN) >= INSN_LUID (START)	\
-    && INSN_LUID (INSN) <= INSN_LUID (END))
- 
  /* Indirect_jump_in_function is computed once per function.  */
  static int indirect_jump_in_function;
  static int indirect_jump_in_function_p PARAMS ((rtx));
--- 282,287 ----
Index: loop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.h,v
retrieving revision 1.56
diff -c -p -d -r1.56 loop.h
*** loop.h	2001/10/29 22:13:40	1.56
--- loop.h	2001/11/26 01:52:34
*************** Software Foundation, 59 Temple Place - S
*** 50,55 ****
--- 50,60 ----
  #define REGNO_FIRST_LUID(REGNO) uid_luid[REGNO_FIRST_UID (REGNO)]
  #define REGNO_LAST_LUID(REGNO) uid_luid[REGNO_LAST_UID (REGNO)]
  
+ /* Nonzero iff INSN is between START and END, inclusive.  */
+ #define INSN_IN_RANGE_P(INSN, START, END)	\
+   (INSN_UID (INSN) < max_uid_for_loop		\
+    && INSN_LUID (INSN) >= INSN_LUID (START)	\
+    && INSN_LUID (INSN) <= INSN_LUID (END))
  
  /* A "basic induction variable" or biv is a pseudo reg that is set
     (within this loop) only by incrementing or decrementing it.  */
Index: unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
retrieving revision 1.147
diff -c -p -d -r1.147 unroll.c
*** unroll.c	2001/11/21 00:50:56	1.147
--- unroll.c	2001/11/26 01:52:34
*************** loop_iterations (loop)
*** 3480,3485 ****
--- 3480,3486 ----
    int unsigned_p, compare_dir, final_larger;
    rtx last_loop_insn;
    rtx reg_term;
+   rtx insn;
    struct iv_class *bl;
  
    loop_info->n_iterations = 0;
*************** loop_iterations (loop)
*** 3705,3710 ****
--- 3706,3762 ----
  
    if (initial_value == 0)
      return 0;
+ 
+   /* Some code transformations can result in code akin to
+ 
+ 	LOOP_BEG
+ 	  goto start;
+ 	top:
+ 	  i++;
+ 	start:
+ 	  ...
+ 	LOOP_CONT
+ 	  if (i < n) goto top;
+ 	LOOP_END
+ 
+      In this situation, we skip the increment the first time through
+      the loop, which results in an incorrect estimate of the number
+      of iterations.  As we did for GIVs above, adjust the initial value
+      to compensate.  */
+ 
+   off_by_one = 0;
+   for (insn = loop->start; insn != loop->top; insn = NEXT_INSN (insn))
+     if (GET_CODE (insn) == JUMP_INSN)
+       {
+ 	if (any_uncondjump_p (insn)
+ 	    && JUMP_LABEL (insn)
+ 	    && INSN_IN_RANGE_P (JUMP_LABEL (insn), loop->top, loop->cont))
+ 	  {
+ 	    if (reg_set_between_p (bl->biv->src_reg, insn, JUMP_LABEL (insn)))
+ 	      off_by_one = 1;
+ 	    break;
+ 	  }
+ 	/* No idea what's going on.  */
+ 	if (loop_dump_stream)
+ 	  fprintf (loop_dump_stream,
+ 		   "Loop iterations: Confused by jump before loop top.\n");
+ 	return 0;
+       }
+ 
+   if (off_by_one)
+     {
+       if (loop_dump_stream)
+ 	fprintf (loop_dump_stream,
+ 		 "Loop iterations: Basic induction var skips initial incr.\n");
+       if (GET_CODE (increment) != CONST_INT)
+ 	{
+ 	  if (loop_dump_stream)
+ 	    fprintf (loop_dump_stream,
+ 		     "Loop iterations: Can't adjust with non-constant incr.\n");
+ 	  return 0;
+ 	}
+       initial_value = plus_constant (initial_value, -INTVAL (increment));
+     }
  
    unsigned_p = 0;
    off_by_one = 0;

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

[Corey Minyard]

Richard Henderson wrote:

>On Thu, Nov 22, 2001 at 01:21:20AM -0600, Corey Minyard wrote:
>
>>     for I in 1 .. Len loop
>>         a[i] := b[i];
>>     end loop;
>>
>
>Give me a complete compilable testcase and I'll look at it.
>
>
>r~
>
The following shows the problem:

    procedure Ada.Tster (S   : in out String;
                         Len : in out Integer) is
    begin
       Len := 0;
       for I in 1 .. S'Length loop
          if S (I) /= ' ' then
             Len := Len + 1;
             S (Len) := S (I);
          end if;
       end loop;
    end Ada.Tster;

Unfortunately, it's not simple to reproduce this, since you have to 
build an Ada cross compiler, and you have to compile this code as part 
of the compiler (since you can't compile anything else easily without 
having gnatlib compiled and installed)  And it's not the same as the one 
reported by Andreas Schwab; I don't think you can reproduce this 
particular bug with the C compiler.  You have to jump past the increment 
to enter the loop, but the jump has to be after the loop begin note.

I have attached a patch that is less of a cheap hack than the previous 
one, it scans the insns of the loop to detect the situation.  With this 
patch I can do a full bootstrap on the PowerPC.  Another way to solve 
this problem would be to move the jump past the increment to before the 
loop begin note; the doloop code will detect this and not apply the 
doloop optimization, but then no for loops from the Ada front-end will 
have doloop optimization.

The attached patch might be done in a simpler manner, but I don't know 
the code well enought right now to know, and I couldn't find a better 
way in a quick search.  It was more complicated than I like because in 
some loop the increment variable is not the same one that is 
incremented, another variable is incremented then assigned to the 
increment variable.  This code only handles one level of assignment, it 
might be necessary to have more.

-Corey

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

[Richard Kenner]

    procedure Ada.Tster (S   : in out String;
                         Len : in out Integer) is

You shouldn't use "Ada.".  Just "Tster" is fine.

    Unfortunately, it's not simple to reproduce this, since you have to
    build an Ada cross compiler, and you have to compile this code as part
    of the compiler (since you can't compile anything else easily without
    having gnatlib compiled and installed) 

The latter is not totally true.  Just do "make gnatlib" and let it get as
far as the symlinks.  It doesn't matter if the compiles blow up (as they will
if you have a cross-compiler with no assembler).

Then, in the object directory, you can just do ./gnat1 -Iada/rts followed by
the location of the test program.

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

[Richard Kenner]

    procedure Ada.Tster (S   : in out String;
                         Len : in out Integer) is

You shouldn't use "Ada.".  Just "Tster" is fine.

    Unfortunately, it's not simple to reproduce this, since you have to
    build an Ada cross compiler, and you have to compile this code as part
    of the compiler (since you can't compile anything else easily without
    having gnatlib compiled and installed) 

The latter is not totally true.  Just do "make gnatlib" and let it get as
far as the symlinks.  It doesn't matter if the compiles blow up (as they will
if you have a cross-compiler with no assembler).

Then, in the object directory, you can just do ./gnat1 -Iada/rts followed by
the location of the test program.

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

[dewar]

    procedure Ada.Tster (S   : in out String;
                         Len : in out Integer) is

There is in fact a specific rule in the Ada RM that prevents a user program
from compiling children of Ada. Now you can use -gnatg to allow this (that's
how we compile the runtime), but that is unusual usage :-)

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

[dewar]

    procedure Ada.Tster (S   : in out String;
                         Len : in out Integer) is

There is in fact a specific rule in the Ada RM that prevents a user program
from compiling children of Ada. Now you can use -gnatg to allow this (that's
how we compile the runtime), but that is unusual usage :-)