This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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

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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]