[PATCH] df: Don't abuse bb->aux (PR94148)

[PATCH] df: Don't abuse bb->aux (PR94148)

[Segher Boessenkool]

The df dataflow solvers use the aux field in the basic_block struct,
although that is reserved for any use by passes.  And not only that,
it is required that you set all such fields to NULL before calling
the solvers, or you quietly get wrong results.

This changes the solvers to use a local array for last_change_age
instead, just like it already had a local array for last_visit_age.

Tested on powerpc64-linux {-m32,-m64}.  Also tested with the tests for
PR94042, which it also solves (I need to confirm that still though,
there are other testsuite problems interfering with my testing).

	PR rtl-optimization/94148
	PR rtl-optimization/94042
	* df-core.c (BB_LAST_CHANGE_AGE): Delete.
	(df_worklist_propagate_forward): New parameter last_change_age, use
	that instead of bb->aux.
	(df_worklist_propagate_backward): Ditto.
	(df_worklist_dataflow_doublequeue): Use a local array last_change_age.

---
 gcc/df-core.c | 35 ++++++++++++++++++-----------------
 1 file changed, 18 insertions(+), 17 deletions(-)

diff --git a/gcc/df-core.c b/gcc/df-core.c
index 346849e..9875a26 100644
--- a/gcc/df-core.c
+++ b/gcc/df-core.c
@@ -871,9 +871,6 @@ make_pass_df_finish (gcc::context *ctxt)
    The general data flow analysis engine.
 ----------------------------------------------------------------------------*/
 
-/* Return time BB when it was visited for last time.  */
-#define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux)
-
 /* Helper function for df_worklist_dataflow.
    Propagate the dataflow forward.
    Given a BB_INDEX, do the dataflow propagation
@@ -897,7 +894,8 @@ df_worklist_propagate_forward (struct dataflow *dataflow,
                                unsigned *bbindex_to_postorder,
                                bitmap pending,
                                sbitmap considered,
-			       ptrdiff_t age)
+			       vec<int> &last_change_age,
+			       int age)
 {
   edge e;
   edge_iterator ei;
@@ -908,7 +906,8 @@ df_worklist_propagate_forward (struct dataflow *dataflow,
   if (EDGE_COUNT (bb->preds) > 0)
     FOR_EACH_EDGE (e, ei, bb->preds)
       {
-        if (age <= BB_LAST_CHANGE_AGE (e->src)
+	if (bbindex_to_postorder[e->src->index] < last_change_age.length ()
+	    && age <= last_change_age[bbindex_to_postorder[e->src->index]]
 	    && bitmap_bit_p (considered, e->src->index))
           changed |= dataflow->problem->con_fun_n (e);
       }
@@ -942,7 +941,8 @@ df_worklist_propagate_backward (struct dataflow *dataflow,
                                 unsigned *bbindex_to_postorder,
                                 bitmap pending,
                                 sbitmap considered,
-			        ptrdiff_t age)
+				vec<int> &last_change_age,
+				int age)
 {
   edge e;
   edge_iterator ei;
@@ -953,7 +953,8 @@ df_worklist_propagate_backward (struct dataflow *dataflow,
   if (EDGE_COUNT (bb->succs) > 0)
     FOR_EACH_EDGE (e, ei, bb->succs)
       {
-        if (age <= BB_LAST_CHANGE_AGE (e->dest)
+	if (bbindex_to_postorder[e->dest->index] < last_change_age.length ()
+	    && age <= last_change_age[bbindex_to_postorder[e->dest->index]]
 	    && bitmap_bit_p (considered, e->dest->index))
           changed |= dataflow->problem->con_fun_n (e);
       }
@@ -991,10 +992,10 @@ df_worklist_propagate_backward (struct dataflow *dataflow,
    worklists (we are processing WORKLIST and storing new BBs to visit in
    PENDING).
 
-   As an optimization we maintain ages when BB was changed (stored in bb->aux)
-   and when it was last visited (stored in last_visit_age).  This avoids need
-   to re-do confluence function for edges to basic blocks whose source
-   did not change since destination was visited last time.  */
+   As an optimization we maintain ages when BB was changed (stored in
+   last_change_age) and when it was last visited (stored in last_visit_age).
+   This avoids need to re-do confluence function for edges to basic blocks
+   whose source did not change since destination was visited last time.  */
 
 static void
 df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
@@ -1010,11 +1011,11 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
   int age = 0;
   bool changed;
   vec<int> last_visit_age = vNULL;
+  vec<int> last_change_age = vNULL;
   int prev_age;
-  basic_block bb;
-  int i;
 
   last_visit_age.safe_grow_cleared (n_blocks);
+  last_change_age.safe_grow_cleared (n_blocks);
 
   /* Double-queueing. Worklist is for the current iteration,
      and pending is for the next. */
@@ -1032,30 +1033,30 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
 
 	  bitmap_clear_bit (pending, index);
 	  bb_index = blocks_in_postorder[index];
-	  bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
 	  prev_age = last_visit_age[index];
 	  if (dir == DF_FORWARD)
 	    changed = df_worklist_propagate_forward (dataflow, bb_index,
 						     bbindex_to_postorder,
 						     pending, considered,
+						     last_change_age,
 						     prev_age);
 	  else
 	    changed = df_worklist_propagate_backward (dataflow, bb_index,
 						      bbindex_to_postorder,
 						      pending, considered,
+						      last_change_age,
 						      prev_age);
 	  last_visit_age[index] = ++age;
 	  if (changed)
-	    bb->aux = (void *)(ptrdiff_t)age;
+	    last_change_age[index] = age;
 	}
       bitmap_clear (worklist);
     }
-  for (i = 0; i < n_blocks; i++)
-    BASIC_BLOCK_FOR_FN (cfun, blocks_in_postorder[i])->aux = NULL;
 
   BITMAP_FREE (worklist);
   BITMAP_FREE (pending);
   last_visit_age.release ();
+  last_change_age.release ();
 
   /* Dump statistics. */
   if (dump_file)
-- 
1.8.3.1

Re: [PATCH] df: Don't abuse bb->aux (PR94148)

[Segher Boessenkool]

Hi,

On Thu, Mar 12, 2020 at 10:29:45PM +0000, Segher Boessenkool wrote:
> The df dataflow solvers use the aux field in the basic_block struct,
> although that is reserved for any use by passes.  And not only that,
> it is required that you set all such fields to NULL before calling
> the solvers, or you quietly get wrong results.
> 
> This changes the solvers to use a local array for last_change_age
> instead, just like it already had a local array for last_visit_age.
> 
> Tested on powerpc64-linux {-m32,-m64}.  Also tested with the tests for
> PR94042, which it also solves (I need to confirm that still though,
> there are other testsuite problems interfering with my testing).

I can confirm it also fixes PR94042, no extra patch to shrink-wrap is
needed even (as I thought before).


Segher


> 	PR rtl-optimization/94148
> 	PR rtl-optimization/94042
> 	* df-core.c (BB_LAST_CHANGE_AGE): Delete.
> 	(df_worklist_propagate_forward): New parameter last_change_age, use
> 	that instead of bb->aux.
> 	(df_worklist_propagate_backward): Ditto.
> 	(df_worklist_dataflow_doublequeue): Use a local array last_change_age.

Re: [PATCH] df: Don't abuse bb->aux (PR94148)

[Richard Biener]

On March 12, 2020 11:29:45 PM GMT+01:00, Segher Boessenkool <segher@kernel.crashing.org> wrote:
>The df dataflow solvers use the aux field in the basic_block struct,
>although that is reserved for any use by passes.  And not only that,
>it is required that you set all such fields to NULL before calling
>the solvers, or you quietly get wrong results.
>
>This changes the solvers to use a local array for last_change_age
>instead, just like it already had a local array for last_visit_age.
>
>Tested on powerpc64-linux {-m32,-m64}.  Also tested with the tests for
>PR94042, which it also solves (I need to confirm that still though,
>there are other testsuite problems interfering with my testing).

OK for trunk and affected branches (can you report back how old this issue is?) 

Thanks, 
Richard. 

>	PR rtl-optimization/94148
>	PR rtl-optimization/94042
>	* df-core.c (BB_LAST_CHANGE_AGE): Delete.
>	(df_worklist_propagate_forward): New parameter last_change_age, use
>	that instead of bb->aux.
>	(df_worklist_propagate_backward): Ditto.
>	(df_worklist_dataflow_doublequeue): Use a local array last_change_age.
>
>---
> gcc/df-core.c | 35 ++++++++++++++++++-----------------
> 1 file changed, 18 insertions(+), 17 deletions(-)
>
>diff --git a/gcc/df-core.c b/gcc/df-core.c
>index 346849e..9875a26 100644
>--- a/gcc/df-core.c
>+++ b/gcc/df-core.c
>@@ -871,9 +871,6 @@ make_pass_df_finish (gcc::context *ctxt)
>    The general data flow analysis engine.
>----------------------------------------------------------------------------*/
> 
>-/* Return time BB when it was visited for last time.  */
>-#define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux)
>-
> /* Helper function for df_worklist_dataflow.
>    Propagate the dataflow forward.
>    Given a BB_INDEX, do the dataflow propagation
>@@ -897,7 +894,8 @@ df_worklist_propagate_forward (struct dataflow
>*dataflow,
>                                unsigned *bbindex_to_postorder,
>                                bitmap pending,
>                                sbitmap considered,
>-			       ptrdiff_t age)
>+			       vec<int> &last_change_age,
>+			       int age)
> {
>   edge e;
>   edge_iterator ei;
>@@ -908,7 +906,8 @@ df_worklist_propagate_forward (struct dataflow
>*dataflow,
>   if (EDGE_COUNT (bb->preds) > 0)
>     FOR_EACH_EDGE (e, ei, bb->preds)
>       {
>-        if (age <= BB_LAST_CHANGE_AGE (e->src)
>+	if (bbindex_to_postorder[e->src->index] < last_change_age.length ()
>+	    && age <= last_change_age[bbindex_to_postorder[e->src->index]]
> 	    && bitmap_bit_p (considered, e->src->index))
>           changed |= dataflow->problem->con_fun_n (e);
>       }
>@@ -942,7 +941,8 @@ df_worklist_propagate_backward (struct dataflow
>*dataflow,
>                                 unsigned *bbindex_to_postorder,
>                                 bitmap pending,
>                                 sbitmap considered,
>-			        ptrdiff_t age)
>+				vec<int> &last_change_age,
>+				int age)
> {
>   edge e;
>   edge_iterator ei;
>@@ -953,7 +953,8 @@ df_worklist_propagate_backward (struct dataflow
>*dataflow,
>   if (EDGE_COUNT (bb->succs) > 0)
>     FOR_EACH_EDGE (e, ei, bb->succs)
>       {
>-        if (age <= BB_LAST_CHANGE_AGE (e->dest)
>+	if (bbindex_to_postorder[e->dest->index] < last_change_age.length ()
>+	    && age <= last_change_age[bbindex_to_postorder[e->dest->index]]
> 	    && bitmap_bit_p (considered, e->dest->index))
>           changed |= dataflow->problem->con_fun_n (e);
>       }
>@@ -991,10 +992,10 @@ df_worklist_propagate_backward (struct dataflow
>*dataflow,
>  worklists (we are processing WORKLIST and storing new BBs to visit in
>    PENDING).
> 
>-   As an optimization we maintain ages when BB was changed (stored in
>bb->aux)
>-   and when it was last visited (stored in last_visit_age).  This
>avoids need
>-   to re-do confluence function for edges to basic blocks whose source
>-   did not change since destination was visited last time.  */
>+   As an optimization we maintain ages when BB was changed (stored in
>+   last_change_age) and when it was last visited (stored in
>last_visit_age).
>+   This avoids need to re-do confluence function for edges to basic
>blocks
>+   whose source did not change since destination was visited last
>time.  */
> 
> static void
> df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
>@@ -1010,11 +1011,11 @@ df_worklist_dataflow_doublequeue (struct
>dataflow *dataflow,
>   int age = 0;
>   bool changed;
>   vec<int> last_visit_age = vNULL;
>+  vec<int> last_change_age = vNULL;
>   int prev_age;
>-  basic_block bb;
>-  int i;
> 
>   last_visit_age.safe_grow_cleared (n_blocks);
>+  last_change_age.safe_grow_cleared (n_blocks);
> 
>   /* Double-queueing. Worklist is for the current iteration,
>      and pending is for the next. */
>@@ -1032,30 +1033,30 @@ df_worklist_dataflow_doublequeue (struct
>dataflow *dataflow,
> 
> 	  bitmap_clear_bit (pending, index);
> 	  bb_index = blocks_in_postorder[index];
>-	  bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
> 	  prev_age = last_visit_age[index];
> 	  if (dir == DF_FORWARD)
> 	    changed = df_worklist_propagate_forward (dataflow, bb_index,
> 						     bbindex_to_postorder,
> 						     pending, considered,
>+						     last_change_age,
> 						     prev_age);
> 	  else
> 	    changed = df_worklist_propagate_backward (dataflow, bb_index,
> 						      bbindex_to_postorder,
> 						      pending, considered,
>+						      last_change_age,
> 						      prev_age);
> 	  last_visit_age[index] = ++age;
> 	  if (changed)
>-	    bb->aux = (void *)(ptrdiff_t)age;
>+	    last_change_age[index] = age;
> 	}
>       bitmap_clear (worklist);
>     }
>-  for (i = 0; i < n_blocks; i++)
>-    BASIC_BLOCK_FOR_FN (cfun, blocks_in_postorder[i])->aux = NULL;
> 
>   BITMAP_FREE (worklist);
>   BITMAP_FREE (pending);
>   last_visit_age.release ();
>+  last_change_age.release ();
> 
>   /* Dump statistics. */
>   if (dump_file)

Re: [PATCH] df: Don't abuse bb->aux (PR94148)

[Segher Boessenkool]

On Fri, Mar 13, 2020 at 07:30:17AM +0100, Richard Biener wrote:
> On March 12, 2020 11:29:45 PM GMT+01:00, Segher Boessenkool <segher@kernel.crashing.org> wrote:
> >The df dataflow solvers use the aux field in the basic_block struct,
> >although that is reserved for any use by passes.  And not only that,
> >it is required that you set all such fields to NULL before calling
> >the solvers, or you quietly get wrong results.
> >
> >This changes the solvers to use a local array for last_change_age
> >instead, just like it already had a local array for last_visit_age.
> >
> >Tested on powerpc64-linux {-m32,-m64}.  Also tested with the tests for
> >PR94042, which it also solves (I need to confirm that still though,
> >there are other testsuite problems interfering with my testing).
> 
> OK for trunk and affected branches (can you report back how old this issue is?) 

It's from r161197:
commit 1a0f3fa13745c4052c53e6d84c64539fb5f57e00
Author: Jan Hubicka <jh@suse.cz>
Date:   Tue Jun 22 17:51:15 2010 +0200

This is https://patchwork.ozlabs.org/patch/55394/ btw, which has the ML
discussion and everything.

$ git branch -r --contains 1a0f3fa13745|grep fsf.releases
  fsf/releases/gcc-4.6
  fsf/releases/gcc-4.7
  fsf/releases/gcc-4.8
  fsf/releases/gcc-4.9
  fsf/releases/gcc-5
  fsf/releases/gcc-6
  fsf/releases/gcc-7
  fsf/releases/gcc-8
  fsf/releases/gcc-9

(Maybe there was a backport to 4.5, but that is far back enough already ;-) )


Segher