[PATCH] Avoid re-allocating PHIs in split_edge

[PATCH] Avoid re-allocating PHIs in split_edge

[Richard Biener]

The following patch makes sure to not grow the number of incoming
edges in the destination when doing split_edge on GIMPLE.  That's
easy by first redirecting the existing edge to the destination
to the new block rather than creating the new fallthru from the
new block to the destination.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2017-08-22  Richard Biener  <rguenther@suse.de>

	* tree-cfg.c (gimple_split_edge): Avoid reallocating target
	PHI nodes.

Index: gcc/tree-cfg.c
===================================================================
--- gcc/tree-cfg.c	(revision 251215)
+++ gcc/tree-cfg.c	(working copy)
@@ -2844,10 +2844,11 @@ gimple_split_edge (edge edge_in)
   new_bb = create_empty_bb (after_bb);
   new_bb->frequency = EDGE_FREQUENCY (edge_in);
   new_bb->count = edge_in->count;
-  new_edge = make_single_succ_edge (new_bb, dest, EDGE_FALLTHRU);
 
   e = redirect_edge_and_branch (edge_in, new_bb);
   gcc_assert (e == edge_in);
+
+  new_edge = make_single_succ_edge (new_bb, dest, EDGE_FALLTHRU);
   reinstall_phi_args (new_edge, e);
 
   return new_bb;

Re: [PATCH] Avoid re-allocating PHIs in split_edge

[Jeff Law]

On 08/22/2017 03:03 AM, Richard Biener wrote:
> 
> The following patch makes sure to not grow the number of incoming
> edges in the destination when doing split_edge on GIMPLE.  That's
> easy by first redirecting the existing edge to the destination
> to the new block rather than creating the new fallthru from the
> new block to the destination.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.
> 
> Richard.
> 
> 2017-08-22  Richard Biener  <rguenther@suse.de>
> 
> 	* tree-cfg.c (gimple_split_edge): Avoid reallocating target
> 	PHI nodes.
Definitely a good thing.  Having PHIs get reallocated has led to some
subtle bugs.  I realize this isn't a complete solution to that problem,
but every bit helps.

jeff

Re: [PATCH] Avoid re-allocating PHIs in split_edge

[Richard Biener]

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

On Tue, Aug 22, 2017 at 4:11 PM Jeff Law <law@redhat.com> wrote:
>
> On 08/22/2017 03:03 AM, Richard Biener wrote:
> >
> > The following patch makes sure to not grow the number of incoming
> > edges in the destination when doing split_edge on GIMPLE.  That's
> > easy by first redirecting the existing edge to the destination
> > to the new block rather than creating the new fallthru from the
> > new block to the destination.
> >
> > Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.
> >
> > Richard.
> >
> > 2017-08-22  Richard Biener  <rguenther@suse.de>
> >
> >       * tree-cfg.c (gimple_split_edge): Avoid reallocating target
> >       PHI nodes.
> Definitely a good thing.  Having PHIs get reallocated has led to some
> subtle bugs.  I realize this isn't a complete solution to that problem,
> but every bit helps.

So this causes PHI args to be swapped which I need to avoid now.

Thus the following followup, bootstrapped on x86_64-unknown-linux-gnu,
testing in progress.

Richard.

From b17d1ec8ef94f1ab87fcfedf7c947815e60e42e7 Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Tue, 20 Oct 2020 12:52:31 +0200
Subject: [PATCH] Avoid changing PHIs in GIMPLE split_edge
To: gcc-patches@gcc.gnu.org

Previously I've changed gimple_split_edge to avoid PHI node
re-allocation, but this introduced swapping of PHI arguments
due to the way edge redirection works.  This is now a problem
for me and which can be solved with the following approach
reducing the overhead of split_edge even more.  We can simply
pretend there are no PHI nodes if we can make sure the
new fallthru will have the same dest_idx as the old edge
into the destination.

2020-10-20  Richard Biener  <rguenther@suse.de>

        * tree-cfg.c (reinstall_phi_args): Remove.
        (gimple_split_edge): Remove PHIs around the edge redirection
        to avoid touching them at all.

[-- Attachment #2: p --]
[-- Type: application/octet-stream, Size: 3457 bytes --]

From b17d1ec8ef94f1ab87fcfedf7c947815e60e42e7 Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Tue, 20 Oct 2020 12:52:31 +0200
Subject: [PATCH] Avoid changing PHIs in GIMPLE split_edge
To: gcc-patches@gcc.gnu.org

Previously I've changed gimple_split_edge to avoid PHI node
re-allocation, but this introduced swapping of PHI arguments
due to the way edge redirection works.  This is now a problem
for me and which can be solved with the following approach
reducing the overhead of split_edge even more.  We can simply
pretend there are no PHI nodes if we can make sure the
new fallthru will have the same dest_idx as the old edge
into the destination.

2020-10-20  Richard Biener  <rguenther@suse.de>

	* tree-cfg.c (reinstall_phi_args): Remove.
	(gimple_split_edge): Remove PHIs around the edge redirection
	to avoid touching them at all.
---
 gcc/tree-cfg.c | 50 +++++++++++++++++---------------------------------
 1 file changed, 17 insertions(+), 33 deletions(-)

diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 3d825c20212..5139f111fec 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -2888,35 +2888,6 @@ last_and_only_stmt (basic_block bb)
     return NULL;
 }
 
-/* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
-
-static void
-reinstall_phi_args (edge new_edge, edge old_edge)
-{
-  edge_var_map *vm;
-  int i;
-  gphi_iterator phis;
-
-  vec<edge_var_map> *v = redirect_edge_var_map_vector (old_edge);
-  if (!v)
-    return;
-
-  for (i = 0, phis = gsi_start_phis (new_edge->dest);
-       v->iterate (i, &vm) && !gsi_end_p (phis);
-       i++, gsi_next (&phis))
-    {
-      gphi *phi = phis.phi ();
-      tree result = redirect_edge_var_map_result (vm);
-      tree arg = redirect_edge_var_map_def (vm);
-
-      gcc_assert (result == gimple_phi_result (phi));
-
-      add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
-    }
-
-  redirect_edge_var_map_clear (old_edge);
-}
-
 /* Returns the basic block after which the new basic block created
    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
    near its "logical" location.  This is of most help to humans looking
@@ -2956,11 +2927,24 @@ gimple_split_edge (edge edge_in)
   new_bb = create_empty_bb (after_bb);
   new_bb->count = edge_in->count ();
 
-  e = redirect_edge_and_branch (edge_in, new_bb);
-  gcc_assert (e == edge_in);
-
+  /* We want to avoid re-allocating PHIs when we first
+     add the fallthru edge from new_bb to dest but we also
+     want to avoid changing PHI argument order when
+     first redirecting edge_in away from dest.  The former
+     avoids changing PHI argument order by adding them
+     last and then the redirection swapping it back into
+     place by means of unordered remove.
+     So hack around things by temporarily removing all PHIs
+     from the destination during the edge redirection and then
+     making sure the edges stay in order.  */
+  gimple_seq saved_phis = phi_nodes (dest);
+  unsigned old_dest_idx = edge_in->dest_idx;
+  set_phi_nodes (dest, NULL);
   new_edge = make_single_succ_edge (new_bb, dest, EDGE_FALLTHRU);
-  reinstall_phi_args (new_edge, e);
+  e = redirect_edge_and_branch (edge_in, new_bb);
+  gcc_assert (e == edge_in && new_edge->dest_idx == old_dest_idx);
+  /* set_phi_nodes sets the BB of the PHI nodes, so do it manually here.  */
+  dest->il.gimple.phi_nodes = saved_phis;
 
   return new_bb;
 }
-- 
2.26.2