[patch] df-scan: split df_insn_delete for clearer dumps and better speed

[patch] df-scan: split df_insn_delete for clearer dumps and better speed

[Steven Bosscher]

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

Hello,

The attached patch splits a new function df_insn_info_delete from
df_insn_delete. The original motivation was to get rid of the silly
"deleting insn with uid = ..." messages when re-scanning an insn,
because the mentioned insn isn't deleted at all (it's just rescanned).
But it turns out that there is also a modest but measurable speed-up
(especially at -O0), probably because of avoiding the overhead of
df_grow_bb_info and df_grow_reg_info in common usage of
df_insn_delete.

Bootstrapped&tested on powerpc64-unknown-linux-gnu and on
x86_64-unknown-linux-gnu. OK for trunk?

Ciao!
Steven

[-- Attachment #2: df_delete_insn_info.diff --]
[-- Type: application/octet-stream, Size: 5208 bytes --]

	* df-scan.c (df_insn_info_delete): New helper function, split
	off from df_insn_delete.
	(df_scan_free_bb_info): Use it.
	(df_insn_delete, df_insn_rescan, df_insn_rescan_all,
	df_process_deferred_rescans): Likewise.

Index: df-scan.c
===================================================================
--- df-scan.c	(revision 196182)
+++ df-scan.c	(working copy)
@@ -142,6 +142,8 @@ static void df_install_ref (df_ref, stru
 static int df_ref_compare (const void *, const void *);
 static int df_mw_compare (const void *, const void *);
 
+static void df_insn_info_delete (unsigned int);
+
 /* Indexed by hardware reg number, is true if that register is ever
    used in the current function.
 
@@ -277,8 +279,7 @@ df_scan_free_bb_info (basic_block bb, vo
       FOR_BB_INSNS (bb, insn)
 	{
 	  if (INSN_P (insn))
-	    /* Record defs within INSN.  */
-	    df_insn_delete (bb, INSN_UID (insn));
+	    df_insn_info_delete (INSN_UID (insn));
 	}
 
       if (bb_index < df_scan->block_info_size)
@@ -1087,44 +1088,15 @@ df_mw_hardreg_chain_delete (struct df_mw
 }
 
 
-/* Delete all of the refs information from INSN.  BB must be passed in
-   except when called from df_process_deferred_rescans to mark the block
-   as dirty.  */
+/* Delete all of the refs information from the insn with UID.
+   Internal helper for df_insn_info_delete, df_insn_rescan, and other
+   df-scan routines that don't have to work in deferred mode and don't
+   have to mark basic blocks for re-processing.  */
 
-void
-df_insn_delete (basic_block bb, unsigned int uid)
+static void
+df_insn_info_delete (unsigned int uid)
 {
-  struct df_insn_info *insn_info = NULL;
-  if (!df)
-    return;
-
-  df_grow_bb_info (df_scan);
-  df_grow_reg_info ();
-
-  /* The block must be marked as dirty now, rather than later as in
-     df_insn_rescan and df_notes_rescan because it may not be there at
-     rescanning time and the mark would blow up.  */
-  if (bb)
-    df_set_bb_dirty (bb);
-
-  insn_info = DF_INSN_UID_SAFE_GET (uid);
-
-  /* The client has deferred rescanning.  */
-  if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
-    {
-      if (insn_info)
-	{
-	  bitmap_clear_bit (&df->insns_to_rescan, uid);
-	  bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
-	  bitmap_set_bit (&df->insns_to_delete, uid);
-	}
-      if (dump_file)
-	fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
-      return;
-    }
-
-  if (dump_file)
-    fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
+  struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
 
   bitmap_clear_bit (&df->insns_to_delete, uid);
   bitmap_clear_bit (&df->insns_to_rescan, uid);
@@ -1159,6 +1131,48 @@ df_insn_delete (basic_block bb, unsigned
     }
 }
 
+/* Delete all of the refs information from INSN, either right now
+   or marked for later in deferred mode.
+
+   FIXME: BB must be passed in, to mark the basic block containing
+	  the insn as dirty, but emit-rtl.c doesn't do so.  */
+
+void
+df_insn_delete (basic_block bb, unsigned int uid)
+{
+  if (!df)
+    return;
+
+  df_grow_bb_info (df_scan);
+  df_grow_reg_info ();
+
+  /* The block must be marked as dirty now, rather than later as in
+     df_insn_rescan and df_notes_rescan because it may not be there at
+     rescanning time and the mark would blow up.  */
+  if (bb)
+    df_set_bb_dirty (bb);
+
+  /* The client has deferred rescanning.  */
+  if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
+    {
+      struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
+      if (insn_info)
+	{
+	  bitmap_clear_bit (&df->insns_to_rescan, uid);
+	  bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
+	  bitmap_set_bit (&df->insns_to_delete, uid);
+	}
+      if (dump_file)
+	fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
+      return;
+    }
+
+  if (dump_file)
+    fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
+
+  df_insn_info_delete (uid);
+}
+
 
 /* Free all of the refs and the mw_hardregs in COLLECTION_REC.  */
 
@@ -1261,7 +1275,7 @@ df_insn_rescan (rtx insn)
       /* There's change - we need to delete the existing info.
 	 Since the insn isn't moved, we can salvage its LUID.  */
       luid = DF_INSN_LUID (insn);
-      df_insn_delete (NULL, uid);
+      df_insn_info_delete (uid);
       df_insn_create_insn_record (insn);
       DF_INSN_LUID (insn) = luid;
     }
@@ -1343,7 +1357,7 @@ df_insn_rescan_debug_internal (rtx insn)
 
 
 /* Rescan all of the insns in the function.  Note that the artificial
-   uses and defs are not touched.  This function will destroy def-se
+   uses and defs are not touched.  This function will destroy def-use
    or use-def chains.  */
 
 void
@@ -1375,7 +1389,7 @@ df_insn_rescan_all (void)
     {
       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
       if (insn_info)
-	df_insn_delete (NULL, uid);
+	df_insn_info_delete (uid);
     }
 
   bitmap_clear (&tmp);
@@ -1432,7 +1446,7 @@ df_process_deferred_rescans (void)
     {
       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
       if (insn_info)
-	df_insn_delete (NULL, uid);
+	df_insn_info_delete (uid);
     }
 
   bitmap_copy (&tmp, &df->insns_to_rescan);

Re: [patch] df-scan: split df_insn_delete for clearer dumps and better speed

[Richard Biener]

On Thu, Feb 21, 2013 at 1:10 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> Hello,
>
> The attached patch splits a new function df_insn_info_delete from
> df_insn_delete. The original motivation was to get rid of the silly
> "deleting insn with uid = ..." messages when re-scanning an insn,
> because the mentioned insn isn't deleted at all (it's just rescanned).
> But it turns out that there is also a modest but measurable speed-up
> (especially at -O0), probably because of avoiding the overhead of
> df_grow_bb_info and df_grow_reg_info in common usage of
> df_insn_delete.
>
> Bootstrapped&tested on powerpc64-unknown-linux-gnu and on
> x86_64-unknown-linux-gnu. OK for trunk?

+/* Delete all of the refs information from the insn with UID.
+   Internal helper for df_insn_info_delete, df_insn_rescan, and other

df_insn_delete I suppose

+   df-scan routines that don't have to work in deferred mode and don't
+   have to mark basic blocks for re-processing.  */

-void
-df_insn_delete (basic_block bb, unsigned int uid)
+static void
+df_insn_info_delete (unsigned int uid)
 {

+/* Delete all of the refs information from INSN, either right now
+   or marked for later in deferred mode.
+
+   FIXME: BB must be passed in, to mark the basic block containing
+         the insn as dirty, but emit-rtl.c doesn't do so.  */

you mean the remove_insn call?  So it should call df_insn_info_delete instead?
It _does_ mark the block as dirtly later, if it is not a debug insn.

Your change changes behavior for df->changeable_flags &
DF_DEFER_INSN_RESCAN btw, so it needs someone DF aware to review
and that makes it stage1 material as well I think.

It's also odd how insn_info == NULL is handled here.

Richard.

> Ciao!
> Steven

Re: [patch] df-scan: split df_insn_delete for clearer dumps and better speed

[Steven Bosscher]

On Thu, Feb 21, 2013 at 10:59 AM, Richard Biener wrote:
> On Thu, Feb 21, 2013 at 1:10 AM, Steven Bosscher wrote:
> +/* Delete all of the refs information from the insn with UID.
> +   Internal helper for df_insn_info_delete, df_insn_rescan, and other
>
> df_insn_delete I suppose

Right.


> +   df-scan routines that don't have to work in deferred mode and don't
> +   have to mark basic blocks for re-processing.  */
>
> -void
> -df_insn_delete (basic_block bb, unsigned int uid)
> +static void
> +df_insn_info_delete (unsigned int uid)
>  {
>
> +/* Delete all of the refs information from INSN, either right now
> +   or marked for later in deferred mode.
> +
> +   FIXME: BB must be passed in, to mark the basic block containing
> +         the insn as dirty, but emit-rtl.c doesn't do so.  */
>
> you mean the remove_insn call?  So it should call df_insn_info_delete instead?

Yes, remove_insn calls df_insn_delete with argument bb=NULL. This goes
against the interface documented in df-scan. It should call
df_insn_delete with a non-NULL bb argument.

df_insn_info_delete should remain internal to df-scan.c. (Ideally,
"struct df_insn_info" would be internal to DF, IMHO.)


> It _does_ mark the block as dirtly later, if it is not a debug insn.

Yes, it does. But it should have been left up to df_insn_delete to
make the block dirty. It looks like remove_insn only passes NULL
because it calls df_insn_delete on non-insns and it doesn't pass
BLOCK_FOR_INSN because it feeds BARRIERs to df_insn_delete -- totally
bogus of course...

For GCC 4.9 I want to make df_insn_delete take care of the basic block
argument itself, and remove all df_set_bb_dirty calls from emit-rtl.c.


> Your change changes behavior for df->changeable_flags &
> DF_DEFER_INSN_RESCAN btw,

Not really. All paths to df_insn_info_delete are non-deferred.


> so it needs someone DF aware to review
> and that makes it stage1 material as well I think.

Also good. I think the patch is quite safe but it's obviously not a
bug fix (except perhaps for making the dumps less confusing). Let's
consider this queued for GCC 4.9.
FWIW, I like to think of myself as quite DF aware ;-)


> It's also odd how insn_info == NULL is handled here.

Yes, for GCC 4.9 I want to put a gcc_assert in df_insn_info_delete to
make sure insn_info is always non-NULL. It can be NULL now for NOTEs
and BARRIERs (via the remove_insn path).

Ciao!
Steven

Re: [patch] df-scan: split df_insn_delete for clearer dumps and better speed

[Paolo Bonzini]

> > so it needs someone DF aware to review
> > and that makes it stage1 material as well I think.
> 
> Also good. I think the patch is quite safe but it's obviously not a
> bug fix (except perhaps for making the dumps less confusing). Let's
> consider this queued for GCC 4.9.
> FWIW, I like to think of myself as quite DF aware ;-)

You're definitely DF aware and if the steering committee
wants to appoint you as dataflow reviewer, I would have no
reason to complain...

Still DF only has reviewers, not maintainers, so it needs
someone else DF aware anyway.  If it is 4.9 material perhaps
it is simpler to place it after the patches that kill the basic
block argument.

Paolo

Re: [patch] df-scan: split df_insn_delete for clearer dumps and better speed

[Steven Bosscher]

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

On Thu, Feb 21, 2013 at 1:33 PM, Paolo Bonzini wrote:
> someone else DF aware anyway.  If it is 4.9 material perhaps
> it is simpler to place it after the patches that kill the basic
> block argument.

Here is the updated patch. Bootstrapped&tested on
powerpc64-unknown-linux-gnu. OK for trunk?

Ciao!
Steven

[-- Attachment #2: df_delete_insn_info.diff --]
[-- Type: application/octet-stream, Size: 8315 bytes --]

	* df.h (df_insn_delete): Adjust prototype.
	* emit-rtl.c (remove_insn): Pass a basic block to df_insn_delete
	and let it decide whether mark the basic block dirty.
	(set_insn_deleted): Only pass INSN_P insns to df_insn_delete.
	* df-scan.c (df_insn_info_delete): New helper function, split
	off from df_insn_delete.
	(df_scan_free_bb_info): Use it.
	(df_insn_rescan, df_insn_rescan_all, df_process_deferred_rescans):
	Likewise.
	(df_insn_delete): Likewise.  Take insn rtx as argument.  Verify
	that the insn is actually an insn and it has a non-NULL basic block.
	Do not mark basic block dirty if only deleting a DEBUG_INSN.

Index: df.h
===================================================================
--- df.h	(revision 196758)
+++ df.h	(working copy)
@@ -996,7 +996,7 @@ extern df_ref df_ref_create (rtx, rtx *, rtx,basic
 extern void df_uses_create (rtx *, rtx, int);
 extern void df_ref_remove (df_ref);
 extern struct df_insn_info * df_insn_create_insn_record (rtx);
-extern void df_insn_delete (basic_block, unsigned int);
+extern void df_insn_delete (rtx);
 extern void df_bb_refs_record (int, bool);
 extern bool df_insn_rescan (rtx);
 extern bool df_insn_rescan_debug_internal (rtx);
Index: emit-rtl.c
===================================================================
--- emit-rtl.c	(revision 196758)
+++ emit-rtl.c	(working copy)
@@ -3964,7 +3964,8 @@ add_insn_before (rtx insn, rtx before, basic_block
 void
 set_insn_deleted (rtx insn)
 {
-  df_insn_delete (BLOCK_FOR_INSN (insn), INSN_UID (insn));
+  if (INSN_P (insn))
+    df_insn_delete (insn);
   PUT_CODE (insn, NOTE);
   NOTE_KIND (insn) = NOTE_INSN_DELETED;
 }
@@ -3979,9 +3980,6 @@ remove_insn (rtx insn)
   rtx prev = PREV_INSN (insn);
   basic_block bb;
 
-  /* Later in the code, the block will be marked dirty.  */
-  df_insn_delete (NULL, INSN_UID (insn));
-
   if (prev)
     {
       NEXT_INSN (prev) = next;
@@ -4032,11 +4030,15 @@ remove_insn (rtx insn)
 
       gcc_assert (stack);
     }
+
+  /* Invalidate data flow information associated with INSN.  */
+  if (INSN_P (insn))
+    df_insn_delete (insn);
+
+  /* Fix up basic block boundaries, if necessary.  */
   if (!BARRIER_P (insn)
       && (bb = BLOCK_FOR_INSN (insn)))
     {
-      if (NONDEBUG_INSN_P (insn))
-	df_set_bb_dirty (bb);
       if (BB_HEAD (bb) == insn)
 	{
 	  /* Never ever delete the basic block note without deleting whole
Index: df-scan.c
===================================================================
--- df-scan.c	(revision 196758)
+++ df-scan.c	(working copy)
@@ -142,6 +142,8 @@ static void df_install_ref (df_ref, struct df_reg_
 static int df_ref_compare (const void *, const void *);
 static int df_mw_compare (const void *, const void *);
 
+static void df_insn_info_delete (unsigned int);
+
 /* Indexed by hardware reg number, is true if that register is ever
    used in the current function.
 
@@ -277,8 +279,7 @@ df_scan_free_bb_info (basic_block bb, void *vbb_in
       FOR_BB_INSNS (bb, insn)
 	{
 	  if (INSN_P (insn))
-	    /* Record defs within INSN.  */
-	    df_insn_delete (bb, INSN_UID (insn));
+	    df_insn_info_delete (INSN_UID (insn));
 	}
 
       if (bb_index < df_scan->block_info_size)
@@ -1087,45 +1088,16 @@ df_mw_hardreg_chain_delete (struct df_mw_hardreg *
 }
 
 
-/* Delete all of the refs information from INSN.  BB must be passed in
-   except when called from df_process_deferred_rescans to mark the block
-   as dirty.  */
-
-void
-df_insn_delete (basic_block bb, unsigned int uid)
-{
-  struct df_insn_info *insn_info = NULL;
-  if (!df)
-    return;
-
-  df_grow_bb_info (df_scan);
-  df_grow_reg_info ();
-
-  /* The block must be marked as dirty now, rather than later as in
-     df_insn_rescan and df_notes_rescan because it may not be there at
-     rescanning time and the mark would blow up.  */
-  if (bb)
-    df_set_bb_dirty (bb);
-
-  insn_info = DF_INSN_UID_SAFE_GET (uid);
-
-  /* The client has deferred rescanning.  */
-  if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
-    {
-      if (insn_info)
-	{
-	  bitmap_clear_bit (&df->insns_to_rescan, uid);
-	  bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
-	  bitmap_set_bit (&df->insns_to_delete, uid);
-	}
-      if (dump_file)
-	fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
-      return;
-    }
-
-  if (dump_file)
-    fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
-
+/* Delete all of the refs information from the insn with UID.
+   Internal helper for df_insn_delete, df_insn_rescan, and other
+   df-scan routines that don't have to work in deferred mode
+   and do not have to mark basic blocks for re-processing.  */
+
+static void
+df_insn_info_delete (unsigned int uid)
+{
+  struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
+
   bitmap_clear_bit (&df->insns_to_delete, uid);
   bitmap_clear_bit (&df->insns_to_rescan, uid);
   bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
@@ -1160,7 +1132,68 @@ df_mw_hardreg_chain_delete (struct df_mw_hardreg *
     }
 }
 
+/* Delete all of the refs information from INSN, either right now
+   or marked for later in deferred mode.  */
 
+void
+df_insn_delete (rtx insn)
+{
+  unsigned int uid;
+  basic_block bb;
+
+  gcc_checking_assert (INSN_P (insn));
+
+  if (!df)
+    return;
+
+  uid = INSN_UID (insn);
+  bb = BLOCK_FOR_INSN (insn);
+
+  /* ??? bb can be NULL after pass_free_cfg.  At that point, DF should
+     not exist anymore (as mentioned in df-core.c: "The only requirement
+     [for DF] is that there be a correct control flow graph."  Clearly
+     that isn't the case after pass_free_cfg.  But DF is freed much later
+     because some back-ends want to use DF info even though the CFG is
+     already gone.  It's not clear to me whether that is safe, actually.
+     In any case, we expect BB to be non-NULL at least up to register
+     allocation, so disallow a non-NULL BB up to there.  Not perfect
+     but better than nothing...  */
+
+  gcc_checking_assert (bb != NULL || reload_completed);
+
+  df_grow_bb_info (df_scan);
+  df_grow_reg_info ();
+
+  /* The block must be marked as dirty now, rather than later as in
+     df_insn_rescan and df_notes_rescan because it may not be there at
+     rescanning time and the mark would blow up.
+     DEBUG_INSNs do not make a block's data flow solution dirty (at
+     worst the LUIDs are no longer contiguous).  */
+  if (bb != NULL && NONDEBUG_INSN_P (insn))
+    df_set_bb_dirty (bb);
+
+  /* The client has deferred rescanning.  */
+  if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
+    {
+      struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
+      if (insn_info)
+	{
+	  bitmap_clear_bit (&df->insns_to_rescan, uid);
+	  bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
+	  bitmap_set_bit (&df->insns_to_delete, uid);
+	}
+      if (dump_file)
+	fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
+      return;
+    }
+
+  if (dump_file)
+    fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
+
+  df_insn_info_delete (uid);
+}
+
+
 /* Free all of the refs and the mw_hardregs in COLLECTION_REC.  */
 
 static void
@@ -1262,7 +1295,7 @@ df_insn_rescan (rtx insn)
       /* There's change - we need to delete the existing info.
 	 Since the insn isn't moved, we can salvage its LUID.  */
       luid = DF_INSN_LUID (insn);
-      df_insn_delete (NULL, uid);
+      df_insn_info_delete (uid);
       df_insn_create_insn_record (insn);
       DF_INSN_LUID (insn) = luid;
     }
@@ -1345,7 +1378,7 @@ df_insn_rescan_debug_internal (rtx insn)
 
 
 /* Rescan all of the insns in the function.  Note that the artificial
-   uses and defs are not touched.  This function will destroy def-se
+   uses and defs are not touched.  This function will destroy def-use
    or use-def chains.  */
 
 void
@@ -1377,7 +1410,7 @@ df_insn_rescan_all (void)
     {
       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
       if (insn_info)
-	df_insn_delete (NULL, uid);
+	df_insn_info_delete (uid);
     }
 
   bitmap_clear (&tmp);
@@ -1434,7 +1467,7 @@ df_process_deferred_rescans (void)
     {
       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
       if (insn_info)
-	df_insn_delete (NULL, uid);
+	df_insn_info_delete (uid);
     }
 
   bitmap_copy (&tmp, &df->insns_to_rescan);

Re: [patch] df-scan: split df_insn_delete for clearer dumps and better speed

[Steven Bosscher]

On Mon, Mar 18, 2013 at 1:01 AM, Steven Bosscher wrote:
> On Thu, Feb 21, 2013 at 1:33 PM, Paolo Bonzini wrote:
>> someone else DF aware anyway.  If it is 4.9 material perhaps
>> it is simpler to place it after the patches that kill the basic
>> block argument.
>
> Here is the updated patch. Bootstrapped&tested on
> powerpc64-unknown-linux-gnu. OK for trunk?

Ping?

Ciao!
Steven

Re: [patch] df-scan: split df_insn_delete for clearer dumps and better speed

[Paolo Bonzini]

Il 18/03/2013 01:01, Steven Bosscher ha scritto:
>> > someone else DF aware anyway.  If it is 4.9 material perhaps
>> > it is simpler to place it after the patches that kill the basic
>> > block argument.
> Here is the updated patch. Bootstrapped&tested on
> powerpc64-unknown-linux-gnu. OK for trunk?

Ok.

Paolo