[PATCH] proper dataflow block visitation order

[PATCH] proper dataflow block visitation order

[Seongbae Park (박성배, 朴成培)]

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

This is an embarrassing mistake on my part that I only noticed this week,
where we were using wrong block visit orders for dataflow analysis
i.e. for forward problem, reverse postorder is the best known
but we have been using postorder of inverted graph,
and for backward problem, we should have used reverse postorder of
inverted graph
but we've been using postorder (of non-inverted).

Two mistakes (of not reversing the postorder, and using wrong graph direction)
canceled each other somewhat which made this mistake not noticeable
for this long.
The following patch reduces the total number of block visits during
dataflow by about 4%
building cc1 on i686, and it also reduces the block visits for the
testcases in PR34400.

While this is an overall win, there are cases where this patch increases
the number of visits - I'll have to look at them further later,
but clearly this is the right thing to do for now.

Bootstrapped on i686 with c/c++ and no regression.
While this is not exactly a regression,
I'd like to commit this to 4.3 -
as it's a fairly safe change (famous last word :).
On the other hand, this is only a compile time fix
and not a high-impact one at that,
so I don't have very strong opinion on this.

Seongbae


2008-02-08  Seongbae Park <seongbae.park@gmail.com>

        * df-core.c (reverse_array, df_compute_postoder): New functions.
        (rest_of_handle_df_initialize): Refactored
        to call df_compute_postorder.
        (df_analyze): Refactored to call df_compute_postorder.
        Pass proper ordering for forward and backward problems.
        (df_get_postorder): Return the correct block ordering.
        (df_compact_blocks): Call df_compute_postorder.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: df-reverse-postorder-0208.patch --]
[-- Type: text/x-patch; name=df-reverse-postorder-0208.patch, Size: 4309 bytes --]

Index: gcc/df-core.c
===================================================================
--- gcc/df-core.c	(revision 132188)
+++ gcc/df-core.c	(working copy)
@@ -703,6 +703,46 @@ df_finish_pass (bool verify ATTRIBUTE_UN
 }
 
 
+/* Put all elements in the reverse order.  */
+
+static void
+reverse_array (int n, int *array)
+{
+  int i;
+  for (i = 0; i < n / 2; i++)
+    {
+      int temp = array[i];
+      array[i] = array[n - i - 1];
+      array[n - i - 1] = temp;
+    }
+}
+
+
+/* Compute the block visit orders 
+   for forward and backward dataflow problems.  */
+
+static void
+df_compute_postorder (struct df *this_df)
+{
+  if (this_df->postorder)
+    free (this_df->postorder);
+  if (this_df->postorder_inverted)
+    free (this_df->postorder_inverted);
+  this_df->postorder = XNEWVEC (int, last_basic_block);
+  this_df->postorder_inverted = XNEWVEC (int, last_basic_block);
+  this_df->n_blocks 
+    = post_order_compute (this_df->postorder, true, true);
+  this_df->n_blocks_inverted 
+    = inverted_post_order_compute (this_df->postorder_inverted);
+
+  /* These should be the same.  */
+  gcc_assert (this_df->n_blocks == this_df->n_blocks_inverted);
+
+  /* Make them reverse postorder.  */
+  reverse_array (this_df->n_blocks, this_df->postorder);
+  reverse_array (this_df->n_blocks, this_df->postorder_inverted);
+}
+
 /* Set up the dataflow instance for the entire back end.  */
 
 static unsigned int
@@ -726,11 +766,7 @@ rest_of_handle_df_initialize (void)
   if (optimize > 1)
     df_live_add_problem ();
 
-  df->postorder = XNEWVEC (int, last_basic_block);
-  df->postorder_inverted = XNEWVEC (int, last_basic_block);
-  df->n_blocks = post_order_compute (df->postorder, true, true);
-  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
-  gcc_assert (df->n_blocks == df->n_blocks_inverted);
+  df_compute_postorder (df);
 
   df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
   memset (df->hard_regs_live_count, 0, 
@@ -1184,6 +1220,8 @@ df_analyze_problem (struct dataflow *dfl
 }
 
 
+
+
 /* Analyze dataflow info for the basic blocks specified by the bitmap
    BLOCKS, or for the whole CFG if BLOCKS is zero.  */
 
@@ -1194,17 +1232,7 @@ df_analyze (void)
   bool everything;
   int i;
   
-  if (df->postorder)
-    free (df->postorder);
-  if (df->postorder_inverted)
-    free (df->postorder_inverted);
-  df->postorder = XNEWVEC (int, last_basic_block);
-  df->postorder_inverted = XNEWVEC (int, last_basic_block);
-  df->n_blocks = post_order_compute (df->postorder, true, true);
-  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
-
-  /* These should be the same.  */
-  gcc_assert (df->n_blocks == df->n_blocks_inverted);
+  df_compute_postorder (df);
 
   /* We need to do this before the df_verify_all because this is
      not kept incrementally up to date.  */
@@ -1258,12 +1286,12 @@ df_analyze (void)
           if (dflow->problem->dir == DF_FORWARD)
             df_analyze_problem (dflow,
                                 df->blocks_to_analyze,
-                                df->postorder_inverted,
+                                df->postorder,
                                 df->n_blocks_inverted);
           else
             df_analyze_problem (dflow,
                                 df->blocks_to_analyze,
-                                df->postorder,
+                                df->postorder_inverted,
                                 df->n_blocks);
         }
     }
@@ -1305,15 +1333,13 @@ df_get_n_blocks (enum df_flow_dir dir)
 int *
 df_get_postorder (enum df_flow_dir dir)
 {
-  gcc_assert (dir != DF_NONE);
-
   if (dir == DF_FORWARD)
     {
-      gcc_assert (df->postorder_inverted);
-      return df->postorder_inverted;
+      gcc_assert (df->postorder);
+      return df->postorder;
     }
-  gcc_assert (df->postorder);
-  return df->postorder;
+  gcc_assert (df->postorder_inverted);
+  return df->postorder_inverted;
 }
 
 static struct df_problem user_problem; 
@@ -1539,6 +1565,9 @@ df_compact_blocks (void)
   for (; i < last_basic_block; i++)
     SET_BASIC_BLOCK (i, NULL);
 
+  /* Recompute the block visit order. */
+  df_compute_postorder (df);
+
 #ifdef DF_DEBUG_CFG
   if (!df_lr->solutions_dirty)
     df_set_clean_cfg ();

Re: [PATCH] proper dataflow block visitation order

[Kenneth Zadeck]

Seongbae Park (???, ???) wrote:
> This is an embarrassing mistake on my part that I only noticed this week,
> where we were using wrong block visit orders for dataflow analysis
> i.e. for forward problem, reverse postorder is the best known
> but we have been using postorder of inverted graph,
> and for backward problem, we should have used reverse postorder of
> inverted graph
> but we've been using postorder (of non-inverted).
>
> Two mistakes (of not reversing the postorder, and using wrong graph direction)
> canceled each other somewhat which made this mistake not noticeable
> for this long.
> The following patch reduces the total number of block visits during
> dataflow by about 4%
> building cc1 on i686, and it also reduces the block visits for the
> testcases in PR34400.
>
> While this is an overall win, there are cases where this patch increases
> the number of visits - I'll have to look at them further later,
> but clearly this is the right thing to do for now.
>
> Bootstrapped on i686 with c/c++ and no regression.
> While this is not exactly a regression,
> I'd like to commit this to 4.3 -
> as it's a fairly safe change (famous last word :).
> On the other hand, this is only a compile time fix
> and not a high-impact one at that,
> so I don't have very strong opinion on this.
>
> Seongbae
>
>
> 2008-02-08  Seongbae Park <seongbae.park@gmail.com>
>
>         * df-core.c (reverse_array, df_compute_postoder): New functions.
>         (rest_of_handle_df_initialize): Refactored
>         to call df_compute_postorder.
>         (df_analyze): Refactored to call df_compute_postorder.
>         Pass proper ordering for forward and backward problems.
>         (df_get_postorder): Return the correct block ordering.
>         (df_compact_blocks): Call df_compute_postorder.
>   
Does this effect the issues that were raised in pr34400?

this is clearly ok for 4.4. At this point mark mitchel has to approve it
for 4.3 and i assume the answer is no.

kenny

Re: [PATCH] proper dataflow block visitation order

[Paolo Bonzini]

> Bootstrapped on i686 with c/c++ and no regression.
> While this is not exactly a regression,
> I'd like to commit this to 4.3 -

The patch may be okay for 4.3 with the changes Steven suggested. 
However, I'd like to see also an assembly language output comparison for 
some .i files (e.g. cc1 or SPEC).

Paolo

Re: [PATCH] proper dataflow block visitation order

[Kenneth Zadeck]

Paolo Bonzini wrote:
>> Bootstrapped on i686 with c/c++ and no regression.
>> While this is not exactly a regression,
>> I'd like to commit this to 4.3 -
>
> The patch may be okay for 4.3 with the changes Steven suggested.
> However, I'd like to see also an assembly language output comparison
> for some .i files (e.g. cc1 or SPEC).
>
> Paolo
we are in lock down mode.  i believe that only one of the release
managers can approve this for 4.3.

Re: [PATCH] proper dataflow block visitation order

[Paolo Bonzini]

Kenneth Zadeck wrote:
> Paolo Bonzini wrote:
>>> Bootstrapped on i686 with c/c++ and no regression.
>>> While this is not exactly a regression,
>>> I'd like to commit this to 4.3 -
>> The patch may be okay for 4.3 with the changes Steven suggested.
>> However, I'd like to see also an assembly language output comparison
>> for some .i files (e.g. cc1 or SPEC).
>>
>> Paolo
> we are in lock down mode.  i believe that only one of the release
> managers can approve this for 4.3.

It depends whether you consider it a regression.  All maintainers can 
approve regression fixes.

Paolo

Re: [PATCH] proper dataflow block visitation order

[Kenneth Zadeck]

Paolo Bonzini wrote:
> Kenneth Zadeck wrote:
>> Paolo Bonzini wrote:
>>>> Bootstrapped on i686 with c/c++ and no regression.
>>>> While this is not exactly a regression,
>>>> I'd like to commit this to 4.3 -
>>> The patch may be okay for 4.3 with the changes Steven suggested.
>>> However, I'd like to see also an assembly language output comparison
>>> for some .i files (e.g. cc1 or SPEC).
>>>
>>> Paolo
>> we are in lock down mode.  i believe that only one of the release
>> managers can approve this for 4.3.
>
> It depends whether you consider it a regression.  All maintainers can
> approve regression fixes.
>
> Paolo
i tend to be more conservative here:   4 percent extra node visits is
not significant.  there is no test case that will fail because of this
issue, nor any code that will be generated any differently.

Re: [PATCH] proper dataflow block visitation order

[Paolo Bonzini]

Kenneth Zadeck wrote:
> Paolo Bonzini wrote:
>> Kenneth Zadeck wrote:
>>> Paolo Bonzini wrote:
>>>>> Bootstrapped on i686 with c/c++ and no regression.
>>>>> While this is not exactly a regression,
>>>>> I'd like to commit this to 4.3 -
>>>> The patch may be okay for 4.3 with the changes Steven suggested.
>>>> However, I'd like to see also an assembly language output comparison
>>>> for some .i files (e.g. cc1 or SPEC).
>>>>
>>>> Paolo
>>> we are in lock down mode.  i believe that only one of the release
>>> managers can approve this for 4.3.
>> It depends whether you consider it a regression.  All maintainers can
>> approve regression fixes.
>>
>> Paolo
> i tend to be more conservative here:   4 percent extra node visits is
> not significant.  there is no test case that will fail because of this
> issue, nor any code that will be generated any differently.

I see -- indeed I asked for assembly language comparison because you 
don't expect difference.  Mark in the past was more permissive for 
compile-time regressions; the current release managers might disagree.

Paolo

Re: [PATCH] proper dataflow block visitation order

[Kenneth Zadeck]

Paolo Bonzini wrote:
> Kenneth Zadeck wrote:
>> Paolo Bonzini wrote:
>>> Kenneth Zadeck wrote:
>>>> Paolo Bonzini wrote:
>>>>>> Bootstrapped on i686 with c/c++ and no regression.
>>>>>> While this is not exactly a regression,
>>>>>> I'd like to commit this to 4.3 -
>>>>> The patch may be okay for 4.3 with the changes Steven suggested.
>>>>> However, I'd like to see also an assembly language output comparison
>>>>> for some .i files (e.g. cc1 or SPEC).
>>>>>
>>>>> Paolo
>>>> we are in lock down mode.  i believe that only one of the release
>>>> managers can approve this for 4.3.
>>> It depends whether you consider it a regression.  All maintainers can
>>> approve regression fixes.
>>>
>>> Paolo
>> i tend to be more conservative here:   4 percent extra node visits is
>> not significant.  there is no test case that will fail because of this
>> issue, nor any code that will be generated any differently.
>
> I see -- indeed I asked for assembly language comparison because you
> don't expect difference.  Mark in the past was more permissive for
> compile-timgressions; the current release managers might disagree.
>
> Paolo

note that seonbae claims a 4% difference in number of node visits.  this
will translate into almost no significant difference in compile time. 

I am all for the patch going into 4.4 with stevens changes.   But I do
not see the need for pushing this on what is now a compiler with no p1
regressions. 

kenny

Re: [PATCH] proper dataflow block visitation order

[Richard Guenther]

On Feb 9, 2008 5:22 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>
> Paolo Bonzini wrote:
> > Kenneth Zadeck wrote:
> >> Paolo Bonzini wrote:
> >>> Kenneth Zadeck wrote:
> >>>> Paolo Bonzini wrote:
> >>>>>> Bootstrapped on i686 with c/c++ and no regression.
> >>>>>> While this is not exactly a regression,
> >>>>>> I'd like to commit this to 4.3 -
> >>>>> The patch may be okay for 4.3 with the changes Steven suggested.
> >>>>> However, I'd like to see also an assembly language output comparison
> >>>>> for some .i files (e.g. cc1 or SPEC).
> >>>>>
> >>>>> Paolo
> >>>> we are in lock down mode.  i believe that only one of the release
> >>>> managers can approve this for 4.3.
> >>> It depends whether you consider it a regression.  All maintainers can
> >>> approve regression fixes.
> >>>
> >>> Paolo
> >> i tend to be more conservative here:   4 percent extra node visits is
> >> not significant.  there is no test case that will fail because of this
> >> issue, nor any code that will be generated any differently.
> >
> > I see -- indeed I asked for assembly language comparison because you
> > don't expect difference.  Mark in the past was more permissive for
> > compile-timgressions; the current release managers might disagree.
> >
> > Paolo
>
> note that seonbae claims a 4% difference in number of node visits.  this
> will translate into almost no significant difference in compile time.
>
> I am all for the patch going into 4.4 with stevens changes.   But I do
> not see the need for pushing this on what is now a compiler with no p1
> regressions.

Please do not apply this to trunk right now, but wait for stage1.  If it turns
out to be safe and worth it, you can consider backporting it for 4.3.1.

Thanks,
Richard.

Re: [PATCH] proper dataflow block visitation order

[Mark Mitchell]

Richard Guenther wrote:

>> I am all for the patch going into 4.4 with stevens changes.   But I do
>> not see the need for pushing this on what is now a compiler with no p1
>> regressions.
> 
> Please do not apply this to trunk right now, but wait for stage1.  If it turns
> out to be safe and worth it, you can consider backporting it for 4.3.1.

For the record, that would have been my decision as well.

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] proper dataflow block visitation order

[Bradley Lucier]

Seongbae:

I tried your patch from

http://gcc.gnu.org/ml/gcc-patches/2008-02/msg00269.html

on the test case in PR 26854.  I started with this revision:

euler-52% /pkgs/gcc-mainline/bin/gcc -v
Using built-in specs.
Target: x86_64-unknown-linux-gnu
Configured with: ../../mainline/configure --prefix=/pkgs/gcc-mainline  
--enable-languages=c --enable-checking=release --with-gmp=/pkgs/ 
gmp-4.2.2 --with-mpfr=/pkgs/gmp-4.2.2 --enable-gather-detailed-mem-stats
Thread model: posix
gcc version 4.3.0 20080209 (experimental) [trunk revision 132205] (GCC)

With the following compile command:

time /pkgs/gcc-mainline/bin/gcc -no-cpp-precomp -Wall -W -Wno-unused - 
O1 -fno-math-errno -fschedule-insns2 -fno-trapping-math -fno-strict- 
aliasing -fwrapv -fomit-frame-pointer -fPIC -fno-common -ftime-report  
-fmem-report -c ../all.i > & detailed-mem-report

Prepatch, the total time was

  TOTAL                 : 191.78            13.93            
206.50             776514 kB

postpatch, it was

  TOTAL                 :2888.36            15.13           
2906.24             776514 kB

The offending part seems to be

  df reaching defs      :   5.06 ( 0%) usr   3.57 (24%) sys   8.62  
( 0%) wall       0 kB ( 0%) ggc
  df live regs          :2303.03 (80%) usr   0.00 ( 0%) sys2305.63  
(79%) wall       0 kB ( 0%) ggc
  df live&initialized regs: 405.02 (14%) usr   0.06 ( 0%) sys 405.17  
(14%) wall       0 kB ( 0%) ggc

Prepatch, the times for those passes were

  df reaching defs      :  10.47 ( 5%) usr   3.11 (22%) sys  13.58  
( 7%) wall       0 kB ( 0%) ggc
  df live regs          :   9.36 ( 5%) usr   0.01 ( 0%) sys   9.43  
( 5%) wall       0 kB ( 0%) ggc
  df live&initialized regs:   7.86 ( 4%) usr   0.04 ( 0%) sys   7.91  
( 4%) wall       0 kB ( 0%) ggc

So, perhaps I did something wrong with my tests, or this program is  
pathologically bad for the new algorithm.  Perhaps you could give it  
a try yourself.

Brad

Re: [PATCH] proper dataflow block visitation order

[Steven Bosscher]

xf. http://gcc.gnu.org/ml/gcc-patches/2008-02/msg00269.html

Seongbae wrote:
> +
> +  /* Make them reverse postorder.  */
> +  reverse_array (this_df->n_blocks, this_df->postorder);
> +  reverse_array (this_df->n_blocks, this_df->postorder_inverted);
> +}

Could you also change the names, then, to df->reverse_postorder and
df->reverse_postorder_inverted? This is going to confuse the heck out
of people who want to use these for their own purposes.

Maybe you can use pre_and_rev_post_order_compute() for df->postorder,
instead of computing postorder and reverting it with reverse_array().

And actually, what is wrong with just walking these arrays from the
last element to the first, instead of using reverse_array()?

> -  gcc_assert (dir != DF_NONE);
> -

Why are you removing this assert?

Gr.
Steven