[dataflow]: Allow web to be moved past scheduling by adding libcall ids

[Daniel Berlin <dberlin at dberlin dot org>]

On dataflow branch, if you move web (or any pass that calls cleanup_cfg)
past the fist scheduling pass, any machine that runs the first
scheduling pass (like ppc) will fail to work properly.

This is because scheduling will move pieces of non-REG_NO_CONFLICT
libcall blocks around, and the scanning in dce.c will now fail to find
the beginning and end pieces. 

Other places in our compiler will happily mark the rest of the program
in one direction or the other as a libcall block in this situation
(instead of asserting that it finds the other end of it), which I
decided this was the wrong answer (the main reason being that they
aren't part of a libcall).

After speaking with Ian Taylor about what to do here, I implemented the
following:

I added a reg note which tells you which instructions are part of which
libcall notes.

This enables DCE (and any other pass that scans libcalls) to precisely
mark the rest of the instructions that are part of a libcall it has
marked a portion of, instead of either

	a. Scanning in both directions for each libcall.
	b. Accidently marking the rest of the program when scheduling has
hoisted some part of our libcall.


One could argue that scheduling shouldn't move pieces of libcalls
independently (and indeed, for no-conflict blocks, it won't), since it
doesn't matter in the end, but ISTM that we should just let it move
whatever it wants, and still DTRT.  Special casing more libcalls in more
places seems to be the opposite of what we want to do (which is remove
as much of libcalls as possible).

In addition, this note makes it easier to not have to maintain global
state variables in order to determine whether you are in a libcall block
or not.

If the current instruction is part of a libcall, it will have the
REG_LIBCALL_ID note attached.  No more trying to determine the bounds,
seeing if you are inside them, setting a static variable, and then
resetting it when you are done.

Bootstrapped and regtested on dataflow branch on ppc-gnu-linux with web
moved past scheduling.

Committed to dataflow-branch



2006-02-06  Daniel Berlin  <dberlin@dberlin.org>
	
	* doc/rtl.texi: Document REG_LIBCALL_ID.
	* optabs.c (libcall_id): New variable.
	(emit_no_conflict_block): Use it to emit
	REG_LIBCALL_ID.
	(emit_libcall_block): Ditto.
	* combine.c (distribute_notes): Deal with
	REG_LIbCALL_ID.
	* reg-notes.def (LIBCALL_ID): New note.
	* dce.c (marked_libcalls): New variable.
	(in_libcall): Removed.
	(mark_insn): Mark which libcalls we need to fully mark.
	(mark_libcall_insns): New function.
	(end_dce): Free marked_libcalls.
	(init_dce): Allocate marked_libcalls.
	Call mark_libcall_insns.
Index: doc/rtl.texi
===================================================================
--- doc/rtl.texi	(revision 110617)
+++ doc/rtl.texi	(working copy)
@@ -3481,6 +3481,12 @@ of the JUMP@.  The format is a bitmask o
 This is used on an RTX_FRAME_RELATED_P insn wherein the attached expression
 is used in place of the actual insn pattern.  This is done in cases where
 the pattern is either complex or misleading.
+
+@findex REG_LIBCALL_ID
+@item REG_LIBCALL_ID
+This is used to specify that an insn is part of a libcall.  Each libcall
+in a function has a unique id, and all the insns that are part of that
+libcall will have a REG_LIBCALL_ID note attached with the same ID.
 @end table
 
 For convenience, the machine mode in an @code{insn_list} or
Index: optabs.c
===================================================================
--- optabs.c	(revision 110635)
+++ optabs.c	(working copy)
@@ -125,6 +125,10 @@ static rtx expand_parity (enum machine_m
 static enum rtx_code get_rtx_code (enum tree_code, bool);
 static rtx vector_compare_rtx (tree, bool, enum insn_code);
 
+/* Current libcall id.  It doesn't matter what these are, as long
+   as they are unique to each libcall that is emitted.  */
+static HOST_WIDE_INT libcall_id = 0;
+
 #ifndef HAVE_conditional_trap
 #define HAVE_conditional_trap 0
 #define gen_conditional_trap(a,b) (gcc_unreachable (), NULL_RTX)
@@ -3351,6 +3355,13 @@ emit_no_conflict_block (rtx insns, rtx t
 					 REG_NOTES (first));
   REG_NOTES (last) = gen_rtx_INSN_LIST (REG_RETVAL, first, REG_NOTES (last));
 
+  next = NEXT_INSN (last);
+  for (insn = first; insn != next; insn = NEXT_INSN (insn))
+    REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LIBCALL_ID,
+					  GEN_INT (libcall_id),
+					  REG_NOTES (insn));
+  libcall_id++;
+
   return last;
 }
 
@@ -3378,7 +3389,6 @@ emit_no_conflict_block (rtx insns, rtx t
 
    Except for the first group of insns (the ones setting pseudos), the
    block is delimited by REG_RETVAL and REG_LIBCALL notes.  */
-
 void
 emit_libcall_block (rtx insns, rtx target, rtx result, rtx equiv)
 {
@@ -3525,6 +3535,12 @@ emit_libcall_block (rtx insns, rtx targe
 						 REG_NOTES (first));
 	  REG_NOTES (last) = gen_rtx_INSN_LIST (REG_RETVAL, first,
 						REG_NOTES (last));
+	  next = NEXT_INSN (last);
+	  for (insn = first; insn != next; insn = NEXT_INSN (insn))
+	    REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LIBCALL_ID,
+	    				          GEN_INT (libcall_id),
+						  REG_NOTES (insn));
+	  libcall_id++;
 	}
     }
 }
Index: combine.c
===================================================================
--- combine.c	(revision 110635)
+++ combine.c	(working copy)
@@ -12061,6 +12061,15 @@ distribute_notes (rtx notes, rtx from_in
 	     to simply delete it.  */
 	  break;
 
+	case REG_LIBCALL_ID:
+	  /* If the insn previously containing this note still exists,
+	     put it back where it was.  Otherwise move it to the previous
+	     insn.  */
+	  if (!NOTE_P (from_insn))
+	    place = from_insn;
+	  else
+	    place = prev_real_insn (from_insn);
+	  break;
 	case REG_RETVAL:
 	  /* If the insn previously containing this note still exists,
 	     put it back where it was.  Otherwise move it to the previous
Index: reg-notes.def
===================================================================
--- reg-notes.def	(revision 110617)
+++ reg-notes.def	(working copy)
@@ -163,3 +163,7 @@ REG_NOTE (CROSSING_JUMP)
 /* This kind of note is generated at each to `setjmp', and similar
    functions that can return twice.  */
 REG_NOTE (SETJMP)
+
+/* This kind of note identifies what libcall id an instruction is part of.  */
+REG_NOTE (LIBCALL_ID)
+
Index: dce.c
===================================================================
--- dce.c	(revision 110617)
+++ dce.c	(working copy)
@@ -56,7 +56,7 @@ static bool something_changed;
 static VEC(rtx,heap) *worklist;
 
 static bitmap marked = NULL;
-
+static bitmap marked_libcalls = NULL;
 
 /* Return true if INSN a normal instruction that can be deleted by the
    DCE pass.  */
@@ -107,10 +107,6 @@ marked_insn_p (rtx insn)
     return true;
 }
 
-/* Flag to keep recursive walk of libcall from going south (assuming
-   the stack grows downward).  */
-static bool in_libcall = 0;
-
 
 /* If INSN has not yet been marked as needed, mark it now, and add it to
    the worklist.  */
@@ -121,40 +117,20 @@ mark_insn (rtx insn, bool fast)
   if (!marked_insn_p (insn))
     {
       unsigned int id = INSN_UID (insn);
+      rtx note;
+
       if (!fast)
 	VEC_safe_push (rtx, heap, worklist, insn);
       bitmap_set_bit (marked, INSN_UID (insn));
       if (dump_file)
 	fprintf (dump_file, "  Adding insn %d to worklist\n", id);
 
-      /* The skeptical programmer may wonder what happens if one of
-	 the middle instructions is the one that needs to be marked
-	 live.  The answer is that this should never happen.  */
-      if (!in_libcall && find_reg_note (insn, REG_LIBCALL, NULL_RTX))
-	{
-	  in_libcall = 1;
-	  if (dump_file)
-	    fprintf (dump_file, 
-		     "Marking rest of libcall starting at insn %d\n", id);
-	  while (!find_reg_note (insn, REG_RETVAL, NULL_RTX))
-	    {
-	      insn = NEXT_INSN (insn);
-	      mark_insn (insn, fast);
-	    }
-	  in_libcall = 0;
-	}
-      else if (!in_libcall && find_reg_note (insn, REG_RETVAL, NULL_RTX))
+      if ((note = find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX)))
 	{
-	  in_libcall = 1;
 	  if (dump_file)
-	    fprintf (dump_file, 
-		     "Marking rest of libcall ending at insn %d\n", id);
-	  while (!find_reg_note (insn, REG_LIBCALL, NULL_RTX))
-	    {
-	      insn = PREV_INSN (insn);
-	      mark_insn (insn, fast);
-	    }
-	  in_libcall = 0;
+	    fprintf (dump_file, "Marking libcall " HOST_WIDE_INT_PRINT_DEC "\n",
+ 		     INTVAL (XEXP (note, 0)));
+	  bitmap_set_bit (marked_libcalls, INTVAL (XEXP (note, 0)));
 	}
     }
 }
@@ -233,6 +209,7 @@ init_dce (bool fast)
   df_analyze (dce_df);
 
   marked = BITMAP_ALLOC (NULL);
+  marked_libcalls = BITMAP_ALLOC (NULL);
   if (dump_file)
     df_dump (dce_df, dump_file);
 }
@@ -259,6 +236,28 @@ delete_unmarked_insns (void)
 	}
 }
 
+/* Mark each instruction belonging to a libcall whose id is in
+   marked_libcalls.  */
+
+static void
+mark_libcall_insns (void)
+{
+  basic_block bb;
+  rtx insn;
+
+  if (bitmap_empty_p (marked_libcalls))
+    return;
+  FOR_EACH_BB (bb)
+    FOR_BB_INSNS (bb, insn)
+      {
+	rtx note;
+	if ((note = find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX)))
+	  {
+	    if (bitmap_bit_p (marked_libcalls, INTVAL (XEXP (note, 0))))
+	      mark_insn (insn, false);
+	  }
+      }
+}
 
 /* Free the data allocated by init_dce.  */
 
@@ -266,6 +265,7 @@ static void
 end_dce (void)
 {
   BITMAP_FREE (marked);
+  BITMAP_FREE (marked_libcalls);
 
   df_finish (dce_df);
   dce_df = NULL;
@@ -341,6 +341,11 @@ rest_of_handle_dce (void)
   while (VEC_length (rtx, worklist) > 0)
     mark_reg_dependencies (VEC_pop (rtx, worklist));
 
+  mark_libcall_insns ();
+
+  while (VEC_length (rtx, worklist) > 0)
+    mark_reg_dependencies (VEC_pop (rtx, worklist));
+
   delete_unmarked_insns ();
 
   end_dce ();