[PATCH]: Allow CFG with empty BBs in selective scheduler

[PATCH]: Allow CFG with empty BBs in selective scheduler

[Alexander Monakov]

Hello,

This is a submission of a patch installed earlier on sel-sched branch:
http://gcc.gnu.org/ml/gcc-patches/2008-09/msg01946.html

We were asserting that there are no empty basic blocks in the region.  This is
no longer required, and some empty blocks may be hard to delete.  In the
failing testcase empty blocks were created during cfg_layout_finalize in the
end of pass_duplicate_computed_gotos, and they are hard to delete due to
multiple incoming complex edges.  I would like to note that this behaviour is
only triggered with -Os on this testcase, because otherwise computed gotos are
duplicated during bb-reorder pass, which calls cfg_cleanup (CLEANUP_EXPENSIVE)
before doing cfg_layout_finalize.

The patch deletes the assert, and also includes some related cleanups and
changes.

Bootstrapped and regtested on ia64-linux, also bootstrapped and regtested
earlier on sel-sched branch with selective scheduler enabled at -O2.
OK for trunk?

gcc/testsuite/Changelog:

2008-10-31  Alexander Monakov  <amonakov@ispras.ru>
	* gcc.target/ia64/20071210-2.c: New testcase.

gcc/Changelog:

2008-10-31  Alexander Monakov  <amonakov@ispras.ru>
        * sel-sched-ir.c (maybe_tidy_empty_bb): Do not attempt to delete a 
        block if there are complex incoming edges.
        (sel_merge_blocks): Remove useless assert.
        (sel_redirect_edge_and_branch): Check that edge was redirected.
        * sel-sched-ir.h (_eligible_successor_edge_p): Remove assert.
        (sel_find_rgns): Delete declaration.
        * sel-sched.c (purge_empty_blocks): Attempt to remove first block of 
        the region when it is not a preheader.

Index: gcc/sel-sched.c
===================================================================
--- gcc/sel-sched.c	(revision 141459)
+++ gcc/sel-sched.c	(working copy)
@@ -6476,9 +6476,10 @@
 static void
 purge_empty_blocks (void)
 {
-  int i ;
+  /* Do not attempt to delete preheader.  */
+  int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0;
 
-  for (i = 1; i < current_nr_blocks; )
+  while (i < current_nr_blocks)
     {
       basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i));
 
Index: gcc/sel-sched-ir.c
===================================================================
--- gcc/sel-sched-ir.c	(revision 141459)
+++ gcc/sel-sched-ir.c	(working copy)
@@ -3489,6 +3489,8 @@
 maybe_tidy_empty_bb (basic_block bb)
 {
   basic_block succ_bb, pred_bb;
+  edge e;
+  edge_iterator ei;
   bool rescan_p;
 
   /* Keep empty bb only if this block immediately precedes EXIT and
@@ -3500,6 +3502,11 @@
               || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU))))
     return false;
 
+  /* Do not attempt to redirect complex edges.  */
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    if (e->flags & EDGE_COMPLEX)
+      return false;
+
   free_data_sets (bb);
 
   /* Do not delete BB if it has more than one successor.
@@ -3518,9 +3525,6 @@
   /* Redirect all non-fallthru edges to the next bb.  */
   while (rescan_p)
     {
-      edge e;
-      edge_iterator ei;
-
       rescan_p = false;
 
       FOR_EACH_EDGE (e, ei, bb->preds)
@@ -5252,8 +5256,6 @@
 void
 sel_merge_blocks (basic_block a, basic_block b)
 {
-  gcc_assert (can_merge_blocks_p (a, b));
-
   sel_remove_empty_bb (b, true, false);
   merge_blocks (a, b);
 
@@ -5298,6 +5300,7 @@
   basic_block src;
   int prev_max_uid;
   rtx jump;
+  edge redirected;
 
   latch_edge_p = (pipelining_p
                   && current_loop_nest
@@ -5305,10 +5308,11 @@
 
   src = e->src;
   prev_max_uid = get_max_uid ();
-  
-  redirect_edge_and_branch (e, to);
-  gcc_assert (last_added_blocks == NULL);
 
+  redirected = redirect_edge_and_branch (e, to);
+
+  gcc_assert (redirected && last_added_blocks == NULL);
+
   /* When we've redirected a latch edge, update the header.  */
   if (latch_edge_p)
     {
Index: gcc/sel-sched-ir.h
===================================================================
--- gcc/sel-sched-ir.h	(revision 141459)
+++ gcc/sel-sched-ir.h	(working copy)
@@ -1358,10 +1358,6 @@
 
       e2 = EDGE_SUCC (bb, 0);
       bb = e2->dest;
-      
-      /* This couldn't happen inside a region.  */
-      gcc_assert (! in_current_region_p (bb)
-                  || (flags & SUCCS_OUT));
     }
   
   /* Save the second edge for later checks.  */
@@ -1584,7 +1580,6 @@
 extern void sel_init_pipelining (void);
 extern void sel_finish_pipelining (void);
 extern void sel_sched_region (int);
-extern void sel_find_rgns (void);
 extern loop_p get_loop_nest_for_rgn (unsigned int);
 extern bool considered_for_pipelining_p (struct loop *);
 extern void make_region_from_loop_preheader (VEC(basic_block, heap) **);

Index: gcc/testsuite/gcc.target/ia64/20071210-2.c
===================================================================
--- gcc/testsuite/gcc.target/ia64/20071210-2.c	(revision 0)
+++ gcc/testsuite/gcc.target/ia64/20071210-2.c	(revision 0)
@@ -0,0 +1,68 @@
+/* { dg-do compile } */
+/* { dg-options "-Os -fselective-scheduling2" } */
+
+extern void abort (void);
+
+struct S
+{
+  int n1, n2, n3, n4;
+};
+
+__attribute__((noinline)) struct S
+foo (int x, int y, int z)
+{
+  if (x != 10 || y != 9 || z != 8)
+    abort ();
+  struct S s = { 1, 2, 3, 4 };
+  return s;
+}
+
+__attribute__((noinline)) void **
+bar (void **u, int *v)
+{
+  void **w = u;
+  int *s = v, x, y, z;
+  void **p, **q;
+  static void *l[] = { &&lab1, &&lab1, &&lab2, &&lab3, &&lab4 };
+
+  if (!u)
+    return l;
+
+  q = *w++;
+  goto *q;
+lab2:
+  p = q;
+  q = *w++;
+  x = s[2];
+  y = s[1];
+  z = s[0];
+  s -= 1;
+  struct S r = foo (x, y, z);
+  s[3] = r.n1;
+  s[2] = r.n2;
+  s[1] = r.n3;
+  s[0] = r.n4;
+  goto *q;
+lab3:
+  p = q;
+  q = *w++;
+  s += 1;
+  s[0] = 23;
+lab1:
+  goto *q;
+lab4:
+  return 0;
+}
+
+int
+main (void)
+{
+  void **u = bar ((void **) 0, (int *) 0);
+  void *t[] = { u[2], u[4] };
+  int s[] = { 7, 8, 9, 10, 11, 12 };
+  if (bar (t, &s[1]) != (void **) 0
+      || s[0] != 4 || s[1] != 3 || s[2] != 2 || s[3] != 1
+      || s[4] != 11 || s[5] != 12)
+    abort ();
+  return 0;
+}

[PING][PATCH]: Allow CFG with empty BBs in selective scheduler

[Alexander Monakov]

Hi,

I'm not sure if this may count as a regression, as empty basic blocks are
rarely expected at the start of second scheduling pass (the testcase enables
selective scheduling at -Os to reproduce).  OK for stage 1?

On Fri, Oct 31, 2008 at 01:52:40PM +0300, Alexander Monakov wrote:
> Hello,
> 
> This is a submission of a patch installed earlier on sel-sched branch:
> http://gcc.gnu.org/ml/gcc-patches/2008-09/msg01946.html
> 
> We were asserting that there are no empty basic blocks in the region.  This is
> no longer required, and some empty blocks may be hard to delete.  In the
> failing testcase empty blocks were created during cfg_layout_finalize in the
> end of pass_duplicate_computed_gotos, and they are hard to delete due to
> multiple incoming complex edges.  I would like to note that this behaviour is
> only triggered with -Os on this testcase, because otherwise computed gotos are
> duplicated during bb-reorder pass, which calls cfg_cleanup (CLEANUP_EXPENSIVE)
> before doing cfg_layout_finalize.
> 
> The patch deletes the assert, and also includes some related cleanups and
> changes.
> 
> Bootstrapped and regtested on ia64-linux, also bootstrapped and regtested
> earlier on sel-sched branch with selective scheduler enabled at -O2.
> OK for trunk?
> 
> gcc/testsuite/Changelog:
> 
> 2008-10-31  Alexander Monakov  <amonakov@ispras.ru>
> 	* gcc.target/ia64/20071210-2.c: New testcase.
> 
> gcc/Changelog:
> 
> 2008-10-31  Alexander Monakov  <amonakov@ispras.ru>
>         * sel-sched-ir.c (maybe_tidy_empty_bb): Do not attempt to delete a 
>         block if there are complex incoming edges.
>         (sel_merge_blocks): Remove useless assert.
>         (sel_redirect_edge_and_branch): Check that edge was redirected.
>         * sel-sched-ir.h (_eligible_successor_edge_p): Remove assert.
>         (sel_find_rgns): Delete declaration.
>         * sel-sched.c (purge_empty_blocks): Attempt to remove first block of 
>         the region when it is not a preheader.
> 
> Index: gcc/sel-sched.c
> ===================================================================
> --- gcc/sel-sched.c	(revision 141459)
> +++ gcc/sel-sched.c	(working copy)
> @@ -6476,9 +6476,10 @@
>  static void
>  purge_empty_blocks (void)
>  {
> -  int i ;
> +  /* Do not attempt to delete preheader.  */
> +  int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0;
>  
> -  for (i = 1; i < current_nr_blocks; )
> +  while (i < current_nr_blocks)
>      {
>        basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i));
>  
> Index: gcc/sel-sched-ir.c
> ===================================================================
> --- gcc/sel-sched-ir.c	(revision 141459)
> +++ gcc/sel-sched-ir.c	(working copy)
> @@ -3489,6 +3489,8 @@
>  maybe_tidy_empty_bb (basic_block bb)
>  {
>    basic_block succ_bb, pred_bb;
> +  edge e;
> +  edge_iterator ei;
>    bool rescan_p;
>  
>    /* Keep empty bb only if this block immediately precedes EXIT and
> @@ -3500,6 +3502,11 @@
>                || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU))))
>      return false;
>  
> +  /* Do not attempt to redirect complex edges.  */
> +  FOR_EACH_EDGE (e, ei, bb->preds)
> +    if (e->flags & EDGE_COMPLEX)
> +      return false;
> +
>    free_data_sets (bb);
>  
>    /* Do not delete BB if it has more than one successor.
> @@ -3518,9 +3525,6 @@
>    /* Redirect all non-fallthru edges to the next bb.  */
>    while (rescan_p)
>      {
> -      edge e;
> -      edge_iterator ei;
> -
>        rescan_p = false;
>  
>        FOR_EACH_EDGE (e, ei, bb->preds)
> @@ -5252,8 +5256,6 @@
>  void
>  sel_merge_blocks (basic_block a, basic_block b)
>  {
> -  gcc_assert (can_merge_blocks_p (a, b));
> -
>    sel_remove_empty_bb (b, true, false);
>    merge_blocks (a, b);
>  
> @@ -5298,6 +5300,7 @@
>    basic_block src;
>    int prev_max_uid;
>    rtx jump;
> +  edge redirected;
>  
>    latch_edge_p = (pipelining_p
>                    && current_loop_nest
> @@ -5305,10 +5308,11 @@
>  
>    src = e->src;
>    prev_max_uid = get_max_uid ();
> -  
> -  redirect_edge_and_branch (e, to);
> -  gcc_assert (last_added_blocks == NULL);
>  
> +  redirected = redirect_edge_and_branch (e, to);
> +
> +  gcc_assert (redirected && last_added_blocks == NULL);
> +
>    /* When we've redirected a latch edge, update the header.  */
>    if (latch_edge_p)
>      {
> Index: gcc/sel-sched-ir.h
> ===================================================================
> --- gcc/sel-sched-ir.h	(revision 141459)
> +++ gcc/sel-sched-ir.h	(working copy)
> @@ -1358,10 +1358,6 @@
>  
>        e2 = EDGE_SUCC (bb, 0);
>        bb = e2->dest;
> -      
> -      /* This couldn't happen inside a region.  */
> -      gcc_assert (! in_current_region_p (bb)
> -                  || (flags & SUCCS_OUT));
>      }
>    
>    /* Save the second edge for later checks.  */
> @@ -1584,7 +1580,6 @@
>  extern void sel_init_pipelining (void);
>  extern void sel_finish_pipelining (void);
>  extern void sel_sched_region (int);
> -extern void sel_find_rgns (void);
>  extern loop_p get_loop_nest_for_rgn (unsigned int);
>  extern bool considered_for_pipelining_p (struct loop *);
>  extern void make_region_from_loop_preheader (VEC(basic_block, heap) **);
> 
> Index: gcc/testsuite/gcc.target/ia64/20071210-2.c
> ===================================================================
> --- gcc/testsuite/gcc.target/ia64/20071210-2.c	(revision 0)
> +++ gcc/testsuite/gcc.target/ia64/20071210-2.c	(revision 0)
> @@ -0,0 +1,68 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Os -fselective-scheduling2" } */
> +
> +extern void abort (void);
> +
> +struct S
> +{
> +  int n1, n2, n3, n4;
> +};
> +
> +__attribute__((noinline)) struct S
> +foo (int x, int y, int z)
> +{
> +  if (x != 10 || y != 9 || z != 8)
> +    abort ();
> +  struct S s = { 1, 2, 3, 4 };
> +  return s;
> +}
> +
> +__attribute__((noinline)) void **
> +bar (void **u, int *v)
> +{
> +  void **w = u;
> +  int *s = v, x, y, z;
> +  void **p, **q;
> +  static void *l[] = { &&lab1, &&lab1, &&lab2, &&lab3, &&lab4 };
> +
> +  if (!u)
> +    return l;
> +
> +  q = *w++;
> +  goto *q;
> +lab2:
> +  p = q;
> +  q = *w++;
> +  x = s[2];
> +  y = s[1];
> +  z = s[0];
> +  s -= 1;
> +  struct S r = foo (x, y, z);
> +  s[3] = r.n1;
> +  s[2] = r.n2;
> +  s[1] = r.n3;
> +  s[0] = r.n4;
> +  goto *q;
> +lab3:
> +  p = q;
> +  q = *w++;
> +  s += 1;
> +  s[0] = 23;
> +lab1:
> +  goto *q;
> +lab4:
> +  return 0;
> +}
> +
> +int
> +main (void)
> +{
> +  void **u = bar ((void **) 0, (int *) 0);
> +  void *t[] = { u[2], u[4] };
> +  int s[] = { 7, 8, 9, 10, 11, 12 };
> +  if (bar (t, &s[1]) != (void **) 0
> +      || s[0] != 4 || s[1] != 3 || s[2] != 2 || s[3] != 1
> +      || s[4] != 11 || s[5] != 12)
> +    abort ();
> +  return 0;
> +}

Re: [PING][PATCH]: Allow CFG with empty BBs in selective scheduler

[Vladimir Makarov]

Alexander Monakov wrote:
> Hi,
>
> I'm not sure if this may count as a regression, as empty basic blocks are
> rarely expected at the start of second scheduling pass (the testcase enables
> selective scheduling at -Os to reproduce).  OK for stage 1?
>   
Thanks, Alexander.  The patch is ok to commit it into the trunk.

Please, only merge two changelog entries for sel-sched-ir.c into one:

        * sel-sched-ir.c (maybe_tidy_empty_bb): Do not attempt to delete a 
        block if there are complex incoming edges.
        (sel_merge_blocks): Remove useless assert.
        (sel_redirect_edge_and_branch): Check that edge was redirected.
        * sel-sched-ir.h (_eligible_successor_edge_p): Remove assert.
        (sel_find_rgns): Delete declaration.


The patch would be more readable if you used -up in diff.  Please, remember about this next time.

Vlad

Re: [PING][PATCH]: Allow CFG with empty BBs in selective scheduler

[Alexander Monakov]

On Fri, Apr 24, 2009 at 01:51:45PM -0400, Vladimir Makarov wrote:
> Please, only merge two changelog entries for sel-sched-ir.c into one:
>
>        * sel-sched-ir.c (maybe_tidy_empty_bb): Do not attempt to delete a 
>        block if there are complex incoming edges.
>        (sel_merge_blocks): Remove useless assert.
>        (sel_redirect_edge_and_branch): Check that edge was redirected.
>        * sel-sched-ir.h (_eligible_successor_edge_p): Remove assert.
>        (sel_find_rgns): Delete declaration.
>

Retested on ia64-linux, committed to trunk as revision 146882.  Sorry, but I
left the changelog unchanged: the second entry is for .h file, not .c.

Thanks.

-- 
Alexander Monakov