[RFC] Don't introduce useless edge splits unless in PRE

Message ID 874l5xcf3q.fsf@ispras.ru
State New
Headers show
Series
  • [RFC] Don't introduce useless edge splits unless in PRE
Related show

Commit Message

Vladislav Ivanishin May 14, 2019, 1:58 p.m.
Hi!

The split_critical_edges() function has multiple uses and it seems, a
portion of its code was added to work only when called from tree-ssa-pre
but right now it is executed regardless of the caller.

The below patch survives bootstrap and regression testing on
x86_64-pc-linux-gnu.  Does it make sense?
If it does, then it uncovers what I think might be a latent bug in the
late uninit pass.

Without the patch, the crited pass inserts an empty basic block that
almost magically prevents the uninit pass from reporting a false
positive.

$ gcc -c -fdump-tree-all -fgimple -O -Wuninitialized gimple-fp-hfs.c
int __GIMPLE (ssa,startwith("uninit1"))
probe_hfsplus ()
{
  int D_1913;
  unsigned int ext_block_start;
  int ext;
  unsigned int _1;
  int _14;

  __BB(2):
  ext_7 = 0;
  goto __BB4;

  __BB(3):
  ext_block_start_11 = 1u;
  _1 = 0u;
  ext_13 = ext_4 + 1;
  goto __BB4;

  __BB(4,loop_header(1)):
  ext_block_start_2 = __PHI (__BB2: ext_block_start_8(D), __BB3: ext_block_start_11);
  ext_4 = __PHI (__BB2: 0, __BB3: ext_13);
  if (ext_4 <= 7)
    goto __BB3;
  else
    goto __BB5;

  __BB(5):
  ext_block_start_3 = __PHI (__BB4: ext_block_start_2);
  _14 = (int) ext_block_start_3;
  return _14;

}
(no warning)

--- gimple-fp-hfs.c.170t.veclower21
+++ gimple-fp-hfs.c.194t.crited1
@@ -24,10 +24,12 @@
   if (ext_4 <= 7)
     goto <bb 3>; [INV]
   else
-    goto <bb 5>; [INV]
+    goto <bb 6>; [INV]
+
+  <bb 6> :

   <bb 5> :
-  # ext_block_start_3 = PHI <ext_block_start_2(4)>
+  # ext_block_start_3 = PHI <ext_block_start_2(6)>
   _14 = (int) ext_block_start_3;
   return _14;

And with the patch, the useless bb 6 is not inserted and the following
is produced:

gimple-fp-hfs.c: In function 'probe_hfsplus':
gimple-fp-hfs.c:5:16: warning: 'ext_block_start' may be used uninitialized in this function [-Wmaybe-uninitialized]
    5 |   unsigned int ext_block_start;
      |                ^~~~~~~~~~~~~~~

If this patch is OK, I'll try to fix the uninit pass next.

-- 
Vlad

Comments

Richard Biener May 15, 2019, 11:33 a.m. | #1
On Tue, May 14, 2019 at 3:58 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>

> Hi!

>

> The split_critical_edges() function has multiple uses and it seems, a

> portion of its code was added to work only when called from tree-ssa-pre

> but right now it is executed regardless of the caller.

>

> The below patch survives bootstrap and regression testing on

> x86_64-pc-linux-gnu.  Does it make sense?


Yeah.  Please rename the in_pre_p parameter to for_edge_insertion_p
since that is what it ensures.  Note that the use in tree-ssa-sink.c
also requires this since it looks for places to sink code to.  Similar
the use in tree-tail-merge.c (where I'm not sure why it needs split
critical edges at all...).

So, it seems more safe to have the default of the parameter to true,
or rather have no default but adjust all few cases effectively only
changing the one before uninit.

Better (source) documentation would be using an overload,
split_edges_for_insertion?

Richard.

> If it does, then it uncovers what I think might be a latent bug in the

> late uninit pass.

>

> Without the patch, the crited pass inserts an empty basic block that

> almost magically prevents the uninit pass from reporting a false

> positive.

>

> $ gcc -c -fdump-tree-all -fgimple -O -Wuninitialized gimple-fp-hfs.c

>

>

> (no warning)

>

> --- gimple-fp-hfs.c.170t.veclower21

> +++ gimple-fp-hfs.c.194t.crited1

> @@ -24,10 +24,12 @@

>    if (ext_4 <= 7)

>      goto <bb 3>; [INV]

>    else

> -    goto <bb 5>; [INV]

> +    goto <bb 6>; [INV]

> +

> +  <bb 6> :

>

>    <bb 5> :

> -  # ext_block_start_3 = PHI <ext_block_start_2(4)>

> +  # ext_block_start_3 = PHI <ext_block_start_2(6)>

>    _14 = (int) ext_block_start_3;

>    return _14;

>

> And with the patch, the useless bb 6 is not inserted and the following

> is produced:

>

> gimple-fp-hfs.c: In function 'probe_hfsplus':

> gimple-fp-hfs.c:5:16: warning: 'ext_block_start' may be used uninitialized in this function [-Wmaybe-uninitialized]

>     5 |   unsigned int ext_block_start;

>       |                ^~~~~~~~~~~~~~~

>

> If this patch is OK, I'll try to fix the uninit pass next.

>

> --

> Vlad
Vladislav Ivanishin May 17, 2019, 4:42 p.m. | #2
Richard Biener <richard.guenther@gmail.com> writes:

> On Tue, May 14, 2019 at 3:58 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:

>>

>> Hi!

>>

>> The split_critical_edges() function has multiple uses and it seems, a

>> portion of its code was added to work only when called from tree-ssa-pre

>> but right now it is executed regardless of the caller.

>>

>> The below patch survives bootstrap and regression testing on

>> x86_64-pc-linux-gnu.  Does it make sense?

>

> Yeah.  Please rename the in_pre_p parameter to for_edge_insertion_p

> since that is what it ensures.  Note that the use in tree-ssa-sink.c

> also requires this since it looks for places to sink code to.  Similar

> the use in tree-tail-merge.c (where I'm not sure why it needs split

> critical edges at all...).

>

> So, it seems more safe to have the default of the parameter to true,

> or rather have no default but adjust all few cases effectively only

> changing the one before uninit.

>

> Better (source) documentation would be using an overload,

> split_edges_for_insertion?


Thanks for the feedback. 

Here is a safer version of the patch.
gcc/ChangeLog:

        * tree-cfg.h (split_critical_edges): Add for_edge_insertion_p
	parameter with default value false to declaration.
        (split_edges_for_insertion): New inline function.  Wrapper for
	split_critical_edges with for_edge_insertion_p = true.
        * tree-cfg.c (split_critical_edges): Don't split non-critical
	edges if for_edge_insertion_p is false.  Fix whitespace.
        * tree-ssa-pre.c (pass_pre::execute): Call
	split_edges_for_insertion instead of split_critical_edges.
        * gcc/tree-ssa-tail-merge.c (tail_merge_optimize): Ditto.
        * gcc/tree-ssa-sink.c (pass_sink_code::execute): Ditto.
	(pass_data_sink_code): Update function name in the comment.
---
 gcc/tree-cfg.c            | 14 ++++++++------
 gcc/tree-cfg.h            |  9 ++++++++-
 gcc/tree-ssa-pre.c        |  2 +-
 gcc/tree-ssa-sink.c       |  4 ++--
 gcc/tree-ssa-tail-merge.c |  2 +-
 5 files changed, 20 insertions(+), 11 deletions(-)

diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index c6a70c8f10b..eacf494d45f 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -8899,10 +8899,11 @@ struct cfg_hooks gimple_cfg_hooks = {
 };
 
 
-/* Split all critical edges.  */
+/* Split all critical edges.  Split some extra (not necessarily critical) edges
+   if FOR_EDGE_INSERTION_P is true.  */
 
 unsigned int
-split_critical_edges (void)
+split_critical_edges (bool for_edge_insertion_p /* = false */)
 {
   basic_block bb;
   edge e;
@@ -8925,11 +8926,12 @@ split_critical_edges (void)
 	     end by control flow statements, such as RESX.
 	     Go ahead and split them too.  This matches the logic in
 	     gimple_find_edge_insert_loc.  */
-	  else if ((!single_pred_p (e->dest)
-	            || !gimple_seq_empty_p (phi_nodes (e->dest))
-		    || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
+	  else if (for_edge_insertion_p
+		   && (!single_pred_p (e->dest)
+		       || !gimple_seq_empty_p (phi_nodes (e->dest))
+		       || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
 		   && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
-	           && !(e->flags & EDGE_ABNORMAL))
+		   && !(e->flags & EDGE_ABNORMAL))
 	    {
 	      gimple_stmt_iterator gsi;
 
diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h
index 212f5ff5919..836f8e8af51 100644
--- a/gcc/tree-cfg.h
+++ b/gcc/tree-cfg.h
@@ -105,7 +105,7 @@ extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
 extern tree find_case_label_for_value (const gswitch *switch_stmt, tree val);
 extern edge find_taken_edge_switch_expr (const gswitch *switch_stmt, tree val);
 extern unsigned int execute_fixup_cfg (void);
-extern unsigned int split_critical_edges (void);
+extern unsigned int split_critical_edges (bool for_edge_insertion_p = false);
 extern basic_block insert_cond_bb (basic_block, gimple *, gimple *,
 				   profile_probability);
 extern bool gimple_find_sub_bbs (gimple_seq, gimple_stmt_iterator *);
@@ -128,4 +128,11 @@ should_remove_lhs_p (tree lhs)
 	  && !TREE_ADDRESSABLE (TREE_TYPE (lhs)));
 }
 
+
+inline unsigned int
+split_edges_for_insertion ()
+{
+  return split_critical_edges (/*for_edge_insertion_p=*/true);
+}
+
 #endif /* _TREE_CFG_H  */
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 469199fa213..086f8c33336 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -4183,7 +4183,7 @@ pass_pre::execute (function *fun)
   /* This has to happen before VN runs because
      loop_optimizer_init may create new phis, etc.  */
   loop_optimizer_init (LOOPS_NORMAL);
-  split_critical_edges ();
+  split_edges_for_insertion ();
   scev_initialize ();
   calculate_dominance_info (CDI_DOMINATORS);
 
diff --git a/gcc/tree-ssa-sink.c b/gcc/tree-ssa-sink.c
index fe762f54d96..77abe3aa4b6 100644
--- a/gcc/tree-ssa-sink.c
+++ b/gcc/tree-ssa-sink.c
@@ -610,7 +610,7 @@ const pass_data pass_data_sink_code =
   "sink", /* name */
   OPTGROUP_NONE, /* optinfo_flags */
   TV_TREE_SINK, /* tv_id */
-  /* PROP_no_crit_edges is ensured by running split_critical_edges in
+  /* PROP_no_crit_edges is ensured by running split_edges_for_insertion in
      pass_data_sink_code::execute ().  */
   ( PROP_cfg | PROP_ssa ), /* properties_required */
   0, /* properties_provided */
@@ -636,7 +636,7 @@ unsigned int
 pass_sink_code::execute (function *fun)
 {
   loop_optimizer_init (LOOPS_NORMAL);
-  split_critical_edges ();
+  split_edges_for_insertion ();
   connect_infinite_loops_to_exit ();
   memset (&sink_stats, 0, sizeof (sink_stats));
   calculate_dominance_info (CDI_DOMINATORS);
diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
index 3eb63b5fa6d..cbd5a277b39 100644
--- a/gcc/tree-ssa-tail-merge.c
+++ b/gcc/tree-ssa-tail-merge.c
@@ -1746,7 +1746,7 @@ tail_merge_optimize (unsigned int todo)
     {
       cleanup_tree_cfg ();
       todo &= ~TODO_cleanup_cfg;
-      split_critical_edges ();
+      split_edges_for_insertion ();
     }
 
   if (!dom_info_available_p (CDI_DOMINATORS))
-- 
2.20.1
Bootstrap and regression tests are running.  OK if they succeed?

-- 
Vlad
Richard Biener May 20, 2019, 9:42 a.m. | #3
On Fri, May 17, 2019 at 6:42 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>

> Richard Biener <richard.guenther@gmail.com> writes:

>

> > On Tue, May 14, 2019 at 3:58 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:

> >>

> >> Hi!

> >>

> >> The split_critical_edges() function has multiple uses and it seems, a

> >> portion of its code was added to work only when called from tree-ssa-pre

> >> but right now it is executed regardless of the caller.

> >>

> >> The below patch survives bootstrap and regression testing on

> >> x86_64-pc-linux-gnu.  Does it make sense?

> >

> > Yeah.  Please rename the in_pre_p parameter to for_edge_insertion_p

> > since that is what it ensures.  Note that the use in tree-ssa-sink.c

> > also requires this since it looks for places to sink code to.  Similar

> > the use in tree-tail-merge.c (where I'm not sure why it needs split

> > critical edges at all...).

> >

> > So, it seems more safe to have the default of the parameter to true,

> > or rather have no default but adjust all few cases effectively only

> > changing the one before uninit.

> >

> > Better (source) documentation would be using an overload,

> > split_edges_for_insertion?

>

> Thanks for the feedback.

>

> Here is a safer version of the patch.

>

>

> Bootstrap and regression tests are running.  OK if they succeed?


OK.

Thanks,
Richard.

> --

> Vlad

Patch

From d6d843653b82f277e780f19f2d2b3cc3125db8b5 Mon Sep 17 00:00:00 2001
From: Vladislav Ivanishin <vlad@ispras.ru>
Date: Wed, 8 May 2019 20:29:34 +0300
Subject: [PATCH] Don't introduce useless edge splits unless in pre

gcc/Changelog:

        * tree-cfg.h (split_critical_edges): Add in_pre_p parameter with default
        value false to declaration.
        * tree-cfg.c (split_critical_edges): Don't split non-critical edges if
        in_pre_p is false.  Fix whitespace.
        * tree-ssa-pre.c (pass_pre::execute): Pass in_pre_p = true to
        split_critical_edges.
---
 gcc/tree-cfg.c     | 14 ++++++++------
 gcc/tree-cfg.h     |  2 +-
 gcc/tree-ssa-pre.c |  2 +-
 3 files changed, 10 insertions(+), 8 deletions(-)

diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 587408150fb..11683e63cd1 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -8870,10 +8870,11 @@  struct cfg_hooks gimple_cfg_hooks = {
 };
 
 
-/* Split all critical edges.  */
+/* Split all critical edges.  Split some extra edges to help PRE if IN_PRE_P is
+   true.  */
 
 unsigned int
-split_critical_edges (void)
+split_critical_edges (bool in_pre_p /* = false */)
 {
   basic_block bb;
   edge e;
@@ -8896,11 +8897,12 @@  split_critical_edges (void)
 	     end by control flow statements, such as RESX.
 	     Go ahead and split them too.  This matches the logic in
 	     gimple_find_edge_insert_loc.  */
-	  else if ((!single_pred_p (e->dest)
-	            || !gimple_seq_empty_p (phi_nodes (e->dest))
-		    || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
+	  else if (in_pre_p
+		   && (!single_pred_p (e->dest)
+		       || !gimple_seq_empty_p (phi_nodes (e->dest))
+		       || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
 		   && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
-	           && !(e->flags & EDGE_ABNORMAL))
+		   && !(e->flags & EDGE_ABNORMAL))
 	    {
 	      gimple_stmt_iterator gsi;
 
diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h
index 212f5ff5919..3fbf983b36a 100644
--- a/gcc/tree-cfg.h
+++ b/gcc/tree-cfg.h
@@ -105,7 +105,7 @@  extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
 extern tree find_case_label_for_value (const gswitch *switch_stmt, tree val);
 extern edge find_taken_edge_switch_expr (const gswitch *switch_stmt, tree val);
 extern unsigned int execute_fixup_cfg (void);
-extern unsigned int split_critical_edges (void);
+extern unsigned int split_critical_edges (bool in_pre_p = false);
 extern basic_block insert_cond_bb (basic_block, gimple *, gimple *,
 				   profile_probability);
 extern bool gimple_find_sub_bbs (gimple_seq, gimple_stmt_iterator *);
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 09335faa6a9..2c3645b5301 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -4195,7 +4195,7 @@  pass_pre::execute (function *fun)
   /* This has to happen before VN runs because
      loop_optimizer_init may create new phis, etc.  */
   loop_optimizer_init (LOOPS_NORMAL);
-  split_critical_edges ();
+  split_critical_edges (/*in_pre_p=*/true);
   scev_initialize ();
   calculate_dominance_info (CDI_DOMINATORS);
 
-- 
2.21.0