[PATCH] Make SRA tolerate most throwing statements

[PATCH] Make SRA tolerate most throwing statements

[Martin Jambor]

Hi,

back in January in
http://gcc.gnu.org/ml/gcc-patches/2014-01/msg00848.html Eric pointed
out a testcase where the problem was SRA not scalarizing an aggregate
because it was involved in a throwing statement.  The reason is that
SRA is likely to need to append new statements after each one where a
replaced aggregate is present, but throwing statements must end their
BBs.  This patch comes up with a fix for most such situations by
adding these new statements onto a single successor non-EH edge, if
there is one and only one such edge.

I have bootstrapped and tested a very similar version on x86_64-linux,
bootstrap and testing of this exact one is currently underway.  OK for
trunk?  Eric, if and once this gets in, can you please add the
testcase from your original post to the suite?

Thanks,

Martin


2014-04-15  Martin Jambor  <mjambor@suse.cz>

	* tree-sra.c (single_non_eh_succ): New function.
	(disqualify_ops_if_throwing_stmt): Renamed to
	disqualify_if_bad_bb_terminating_stmt.  Allow throwing statements
	having one non-EH successor BB.
	(gsi_for_eh_followups): New function.
	(sra_modify_expr): If stmt ends bb, use single non-EH successor to
	generate loads into replacements.
	(sra_modify_assign): Likewise and and also use the simple path for
	such statements.
	(sra_modify_function_body): Iterate safely over BBs.

diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index ffef13d..4fd0f5e 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -1142,17 +1142,41 @@ build_access_from_expr (tree expr, gimple stmt, bool write)
   return false;
 }
 
-/* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
-   modes in which it matters, return true iff they have been disqualified.  RHS
-   may be NULL, in that case ignore it.  If we scalarize an aggregate in
-   intra-SRA we may need to add statements after each statement.  This is not
-   possible if a statement unconditionally has to end the basic block.  */
+/* Return the single non-EH successor edge of BB or NULL if there is none or
+   more than one.  */
+
+static edge
+single_non_eh_succ (basic_block bb)
+{
+  edge e, res = NULL;
+  edge_iterator ei;
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    if (!(e->flags & EDGE_EH))
+      {
+	if (res)
+	  return NULL;
+	res = e;
+      }
+
+  return res;
+}
+
+/* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
+   there is no alternative spot where to put statements SRA might need to
+   generate after it.  The spot we are looking for is an edge leading to a
+   single non-EH successor, if it exists and is indeed single.  RHS may be
+   NULL, in that case ignore it.  */
+
 static bool
-disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
+disqualify_if_bad_bb_terminating_stmt (gimple stmt, tree lhs, tree rhs)
 {
   if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
-      && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
+      && stmt_ends_bb_p (stmt))
     {
+      if (single_non_eh_succ (gimple_bb (stmt)))
+	return false;
+
       disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
       if (rhs)
 	disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
@@ -1180,7 +1204,7 @@ build_accesses_from_assign (gimple stmt)
   lhs = gimple_assign_lhs (stmt);
   rhs = gimple_assign_rhs1 (stmt);
 
-  if (disqualify_ops_if_throwing_stmt (stmt, lhs, rhs))
+  if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs))
     return false;
 
   racc = build_access_from_expr_1 (rhs, stmt, false);
@@ -1319,7 +1343,7 @@ scan_function (void)
 		}
 
 	      t = gimple_call_lhs (stmt);
-	      if (t && !disqualify_ops_if_throwing_stmt (stmt, t, NULL))
+	      if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL))
 		ret |= build_access_from_expr (t, stmt, true);
 	      break;
 
@@ -2734,6 +2758,19 @@ get_access_for_expr (tree expr)
   return get_var_base_offset_size_access (base, offset, max_size);
 }
 
+/* Split the single non-EH successor edge from BB (there must be exactly one)
+   and return a gimple iterator to the new block.  */
+
+static gimple_stmt_iterator
+gsi_for_eh_followups (basic_block bb)
+{
+  edge e = single_non_eh_succ (bb);
+  gcc_assert (e);
+
+  basic_block new_bb = split_edge (e);
+  return gsi_start_bb (new_bb);
+}
+
 /* Replace the expression EXPR with a scalar replacement if there is one and
    generate other statements to do type conversion or subtree copying if
    necessary.  GSI is used to place newly created statements, WRITE is true if
@@ -2763,6 +2800,13 @@ sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
   type = TREE_TYPE (*expr);
 
   loc = gimple_location (gsi_stmt (*gsi));
+  gimple_stmt_iterator alt_gsi = gsi_none ();
+  if (write && stmt_ends_bb_p (gsi_stmt (*gsi)))
+    {
+      alt_gsi = gsi_for_eh_followups (gsi_bb (*gsi));
+      gsi = &alt_gsi;
+    }
+
   if (access->grp_to_be_replaced)
     {
       tree repl = get_access_replacement (access);
@@ -3226,14 +3270,24 @@ sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
   if (modify_this_stmt
       || gimple_has_volatile_ops (*stmt)
       || contains_vce_or_bfcref_p (rhs)
-      || contains_vce_or_bfcref_p (lhs))
+      || contains_vce_or_bfcref_p (lhs)
+      || stmt_can_throw_internal (*stmt)
+      || stmt_ends_bb_p (*stmt))
     {
       if (access_has_children_p (racc))
 	generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
 				 gsi, false, false, loc);
       if (access_has_children_p (lacc))
-	generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
-				 gsi, true, true, loc);
+	{
+	  gimple_stmt_iterator alt_gsi = gsi_none ();
+	  if (stmt_ends_bb_p (*stmt))
+	    {
+	      alt_gsi = gsi_for_eh_followups (gsi_bb (*gsi));
+	      gsi = &alt_gsi;
+	    }
+	  generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
+				   gsi, true, true, loc);
+	}
       sra_stats.separate_lhs_rhs_handling++;
 
       /* This gimplification must be done after generate_subtree_copies,
@@ -3327,8 +3381,13 @@ sra_modify_function_body (void)
 {
   bool cfg_changed = false;
   basic_block bb;
+  vec<basic_block> bb_list = vNULL;
 
   FOR_EACH_BB_FN (bb, cfun)
+    bb_list.safe_push (bb);
+
+  unsigned bb_vec_index;
+  FOR_EACH_VEC_ELT (bb_list, bb_vec_index, bb)
     {
       gimple_stmt_iterator gsi = gsi_start_bb (bb);
       while (!gsi_end_p (gsi))
@@ -3397,6 +3456,7 @@ sra_modify_function_body (void)
 	}
     }
 
+  bb_list.release ();
   return cfg_changed;
 }
 

Re: [PATCH] Make SRA tolerate most throwing statements

[Eric Botcazou]

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

> back in January in
> http://gcc.gnu.org/ml/gcc-patches/2014-01/msg00848.html Eric pointed
> out a testcase where the problem was SRA not scalarizing an aggregate
> because it was involved in a throwing statement.  The reason is that
> SRA is likely to need to append new statements after each one where a
> replaced aggregate is present, but throwing statements must end their
> BBs.  This patch comes up with a fix for most such situations by
> adding these new statements onto a single successor non-EH edge, if
> there is one and only one such edge.

Thanks for working on this.

> I have bootstrapped and tested a very similar version on x86_64-linux,
> bootstrap and testing of this exact one is currently underway.  OK for
> trunk?  Eric, if and once this gets in, can you please add the
> testcase from your original post to the suite?

Reduced testcase attached, you can install it with the patch.


	* gnat.dg/opt34.adb: New test.
	* gnat.dg/opt34_pkg.ads: New helper.


-- 
Eric Botcazou

[-- Attachment #2: opt34.adb --]
[-- Type: text/x-adasrc, Size: 653 bytes --]

-- { dg-do compile }
-- { dg-options "-O -fdump-tree-esra" }

with Opt34_Pkg; use Opt34_Pkg;

procedure Opt34 is

   function Local_Fun (Arg : T_Private) return T_Private is
      Result : T_Private;
   begin

      case Get_Integer (Arg) is
         when 1 =>
            Result := Get_Private (100);
         when 2 =>
            Result := T_Private_Zero;
         when others =>
            null;
      end case;

      return Result;
   end Local_Fun;

begin
   Assert (Get_Integer (Local_Fun (Get_Private (1))) = 100);
end;

-- { dg-final { scan-tree-dump "Created a replacement for result" "esra" } }
-- { dg-final { cleanup-tree-dump "esra" } }

[-- Attachment #3: opt34_pkg.ads --]
[-- Type: text/x-adasrc, Size: 310 bytes --]

package Opt34_Pkg is

   type T_Private is record
      I : Integer := 0;
   end record;

   T_Private_Zero : constant T_Private := (I => 0);

   function Get_Private (I : Integer) return T_Private;
   function Get_Integer (X : T_Private) return Integer;

   procedure Assert (Cond : Boolean);

end Opt34_Pkg;

Re: [PATCH] Make SRA tolerate most throwing statements

[Richard Biener]

On Tue, 15 Apr 2014, Martin Jambor wrote:

> Hi,
> 
> back in January in
> http://gcc.gnu.org/ml/gcc-patches/2014-01/msg00848.html Eric pointed
> out a testcase where the problem was SRA not scalarizing an aggregate
> because it was involved in a throwing statement.  The reason is that
> SRA is likely to need to append new statements after each one where a
> replaced aggregate is present, but throwing statements must end their
> BBs.  This patch comes up with a fix for most such situations by
> adding these new statements onto a single successor non-EH edge, if
> there is one and only one such edge.
> 
> I have bootstrapped and tested a very similar version on x86_64-linux,
> bootstrap and testing of this exact one is currently underway.  OK for
> trunk?  Eric, if and once this gets in, can you please add the
> testcase from your original post to the suite?
> 
> Thanks,
> 
> Martin
> 
> 
> 2014-04-15  Martin Jambor  <mjambor@suse.cz>
> 
> 	* tree-sra.c (single_non_eh_succ): New function.
> 	(disqualify_ops_if_throwing_stmt): Renamed to
> 	disqualify_if_bad_bb_terminating_stmt.  Allow throwing statements
> 	having one non-EH successor BB.
> 	(gsi_for_eh_followups): New function.
> 	(sra_modify_expr): If stmt ends bb, use single non-EH successor to
> 	generate loads into replacements.
> 	(sra_modify_assign): Likewise and and also use the simple path for
> 	such statements.
> 	(sra_modify_function_body): Iterate safely over BBs.
> 
> diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
> index ffef13d..4fd0f5e 100644
> --- a/gcc/tree-sra.c
> +++ b/gcc/tree-sra.c
> @@ -1142,17 +1142,41 @@ build_access_from_expr (tree expr, gimple stmt, bool write)
>    return false;
>  }
>  
> -/* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
> -   modes in which it matters, return true iff they have been disqualified.  RHS
> -   may be NULL, in that case ignore it.  If we scalarize an aggregate in
> -   intra-SRA we may need to add statements after each statement.  This is not
> -   possible if a statement unconditionally has to end the basic block.  */
> +/* Return the single non-EH successor edge of BB or NULL if there is none or
> +   more than one.  */
> +
> +static edge
> +single_non_eh_succ (basic_block bb)
> +{
> +  edge e, res = NULL;
> +  edge_iterator ei;
> +
> +  FOR_EACH_EDGE (e, ei, bb->succs)
> +    if (!(e->flags & EDGE_EH))
> +      {
> +	if (res)
> +	  return NULL;
> +	res = e;
> +      }
> +
> +  return res;
> +}
> +
> +/* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
> +   there is no alternative spot where to put statements SRA might need to
> +   generate after it.  The spot we are looking for is an edge leading to a
> +   single non-EH successor, if it exists and is indeed single.  RHS may be
> +   NULL, in that case ignore it.  */
> +
>  static bool
> -disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
> +disqualify_if_bad_bb_terminating_stmt (gimple stmt, tree lhs, tree rhs)
>  {
>    if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
> -      && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
> +      && stmt_ends_bb_p (stmt))
>      {
> +      if (single_non_eh_succ (gimple_bb (stmt)))
> +	return false;
> +
>        disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
>        if (rhs)
>  	disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
> @@ -1180,7 +1204,7 @@ build_accesses_from_assign (gimple stmt)
>    lhs = gimple_assign_lhs (stmt);
>    rhs = gimple_assign_rhs1 (stmt);
>  
> -  if (disqualify_ops_if_throwing_stmt (stmt, lhs, rhs))
> +  if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs))
>      return false;
>  
>    racc = build_access_from_expr_1 (rhs, stmt, false);
> @@ -1319,7 +1343,7 @@ scan_function (void)
>  		}
>  
>  	      t = gimple_call_lhs (stmt);
> -	      if (t && !disqualify_ops_if_throwing_stmt (stmt, t, NULL))
> +	      if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL))
>  		ret |= build_access_from_expr (t, stmt, true);
>  	      break;
>  
> @@ -2734,6 +2758,19 @@ get_access_for_expr (tree expr)
>    return get_var_base_offset_size_access (base, offset, max_size);
>  }
>  
> +/* Split the single non-EH successor edge from BB (there must be exactly one)
> +   and return a gimple iterator to the new block.  */
> +
> +static gimple_stmt_iterator
> +gsi_for_eh_followups (basic_block bb)
> +{
> +  edge e = single_non_eh_succ (bb);
> +  gcc_assert (e);
> +
> +  basic_block new_bb = split_edge (e);
> +  return gsi_start_bb (new_bb);
> +}
> +
>  /* Replace the expression EXPR with a scalar replacement if there is one and
>     generate other statements to do type conversion or subtree copying if
>     necessary.  GSI is used to place newly created statements, WRITE is true if
> @@ -2763,6 +2800,13 @@ sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
>    type = TREE_TYPE (*expr);
>  
>    loc = gimple_location (gsi_stmt (*gsi));
> +  gimple_stmt_iterator alt_gsi = gsi_none ();
> +  if (write && stmt_ends_bb_p (gsi_stmt (*gsi)))
> +    {
> +      alt_gsi = gsi_for_eh_followups (gsi_bb (*gsi));
> +      gsi = &alt_gsi;

I think you should try to either use gsi_insert_on_edge_immediate
(yeah, bad we can't build a gsi_for_edge_insert ()) or add
a gsi_for_edge_insert () building on gimple_find_edge_insert_loc
(note the before/after flag that returns - gsi_insert_* variants
that take a flag specifying after/before would come handy here).
You could also add a flag to gimple_find_edge_insert_loc whether
it always should be possible to use gsi_insert_after and split
the block in some more cases (or split it if both after and
before inserts should be valid, but that would not split in
the very rare case of an empty successor only).

Basically usually you can avoid splitting the edge.

> +    }
> +
>    if (access->grp_to_be_replaced)
>      {
>        tree repl = get_access_replacement (access);
> @@ -3226,14 +3270,24 @@ sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
>    if (modify_this_stmt
>        || gimple_has_volatile_ops (*stmt)
>        || contains_vce_or_bfcref_p (rhs)
> -      || contains_vce_or_bfcref_p (lhs))
> +      || contains_vce_or_bfcref_p (lhs)
> +      || stmt_can_throw_internal (*stmt)
> +      || stmt_ends_bb_p (*stmt))

stmt_can_throw_internal is redundant.

>      {
>        if (access_has_children_p (racc))
>  	generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
>  				 gsi, false, false, loc);
>        if (access_has_children_p (lacc))
> -	generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
> -				 gsi, true, true, loc);
> +	{
> +	  gimple_stmt_iterator alt_gsi = gsi_none ();
> +	  if (stmt_ends_bb_p (*stmt))
> +	    {
> +	      alt_gsi = gsi_for_eh_followups (gsi_bb (*gsi));
> +	      gsi = &alt_gsi;
> +	    }
> +	  generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
> +				   gsi, true, true, loc);
> +	}
>        sra_stats.separate_lhs_rhs_handling++;
>  
>        /* This gimplification must be done after generate_subtree_copies,
> @@ -3327,8 +3381,13 @@ sra_modify_function_body (void)
>  {
>    bool cfg_changed = false;
>    basic_block bb;
> +  vec<basic_block> bb_list = vNULL;
>  

    auto_vec<basic_block> bb_list;
    bb_list.create (n_basic_blocks_for_fn (cfun));

>    FOR_EACH_BB_FN (bb, cfun)
> +    bb_list.safe_push (bb);
  bb_list.quick_push (bb);

> +
> +  unsigned bb_vec_index;
> +  FOR_EACH_VEC_ELT (bb_list, bb_vec_index, bb)
>      {
>        gimple_stmt_iterator gsi = gsi_start_bb (bb);
>        while (!gsi_end_p (gsi))
> @@ -3397,6 +3456,7 @@ sra_modify_function_body (void)
>  	}
>      }
>  
> +  bb_list.release ();

and with auto_vec you can avoid this (it has a destructor).

But is it really necessary to avoid scanning new blocks (which
would mean that inserting stmts in the successor instead of
always a newly created block would not work)?

Thanks,
Richard.

>    return cfg_changed;
>  }

Re: [PATCH] Make SRA tolerate most throwing statements

[Martin Jambor]

On Wed, Apr 16, 2014 at 11:22:28AM +0200, Richard Biener wrote:
> On Tue, 15 Apr 2014, Martin Jambor wrote:
> 
> > Hi,
> > 
> > back in January in
> > http://gcc.gnu.org/ml/gcc-patches/2014-01/msg00848.html Eric pointed
> > out a testcase where the problem was SRA not scalarizing an aggregate
> > because it was involved in a throwing statement.  The reason is that
> > SRA is likely to need to append new statements after each one where a
> > replaced aggregate is present, but throwing statements must end their
> > BBs.  This patch comes up with a fix for most such situations by
> > adding these new statements onto a single successor non-EH edge, if
> > there is one and only one such edge.
> > 
> > I have bootstrapped and tested a very similar version on x86_64-linux,
> > bootstrap and testing of this exact one is currently underway.  OK for
> > trunk?  Eric, if and once this gets in, can you please add the
> > testcase from your original post to the suite?
> > 
> > Thanks,
> > 
> > Martin
> > 
> > 
> > 2014-04-15  Martin Jambor  <mjambor@suse.cz>
> > 
> > 	* tree-sra.c (single_non_eh_succ): New function.
> > 	(disqualify_ops_if_throwing_stmt): Renamed to
> > 	disqualify_if_bad_bb_terminating_stmt.  Allow throwing statements
> > 	having one non-EH successor BB.
> > 	(gsi_for_eh_followups): New function.
> > 	(sra_modify_expr): If stmt ends bb, use single non-EH successor to
> > 	generate loads into replacements.
> > 	(sra_modify_assign): Likewise and and also use the simple path for
> > 	such statements.
> > 	(sra_modify_function_body): Iterate safely over BBs.
> > 

...

> > @@ -2734,6 +2758,19 @@ get_access_for_expr (tree expr)
> >    return get_var_base_offset_size_access (base, offset, max_size);
> >  }
> >  
> > +/* Split the single non-EH successor edge from BB (there must be exactly one)
> > +   and return a gimple iterator to the new block.  */
> > +
> > +static gimple_stmt_iterator
> > +gsi_for_eh_followups (basic_block bb)
> > +{
> > +  edge e = single_non_eh_succ (bb);
> > +  gcc_assert (e);
> > +
> > +  basic_block new_bb = split_edge (e);
> > +  return gsi_start_bb (new_bb);
> > +}
> > +
> >  /* Replace the expression EXPR with a scalar replacement if there is one and
> >     generate other statements to do type conversion or subtree copying if
> >     necessary.  GSI is used to place newly created statements, WRITE is true if
> > @@ -2763,6 +2800,13 @@ sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
> >    type = TREE_TYPE (*expr);
> >  
> >    loc = gimple_location (gsi_stmt (*gsi));
> > +  gimple_stmt_iterator alt_gsi = gsi_none ();
> > +  if (write && stmt_ends_bb_p (gsi_stmt (*gsi)))
> > +    {
> > +      alt_gsi = gsi_for_eh_followups (gsi_bb (*gsi));
> > +      gsi = &alt_gsi;
> 
> I think you should try to either use gsi_insert_on_edge_immediate
> (yeah, bad we can't build a gsi_for_edge_insert ()) or add
> a gsi_for_edge_insert () building on gimple_find_edge_insert_loc
> (note the before/after flag that returns - gsi_insert_* variants
> that take a flag specifying after/before would come handy here).
> You could also add a flag to gimple_find_edge_insert_loc whether
> it always should be possible to use gsi_insert_after and split
> the block in some more cases (or split it if both after and
> before inserts should be valid, but that would not split in
> the very rare case of an empty successor only).
> 
> Basically usually you can avoid splitting the edge.

The following patch adds gsi_start_edge for that purpose and uses it
together with gsi_commit_edge_inserts from within SRA.

I did not make it an inline static function in the header like the
other gsi initializing functions because that would make
gimple-iterator.h depend on tree-cfg.h and with our current flat
includes that triggered changes of includes in half a gazillion
unrelated c files (I have that patch too because I was apparently too
lazy to think before the third coffee yesterday but I do not think it
is worth it).

Bootstrapped and tested on x86_64-linux, this time it also includes
Eric's testcase.  OK for trunk?

Thanks,

Martin


2014-04-16  Martin Jambor  <mjambor@suse.cz>

	* gimple-iterator.c (gsi_start_edge): New function.
	* gimple-iterator.h (gsi_start_edge): Declare.
	* tree-sra.c (single_non_eh_succ): New function.
	(disqualify_ops_if_throwing_stmt): Renamed to
	disqualify_if_bad_bb_terminating_stmt.  Allow throwing statements
	having one non-EH successor BB.
	(sra_modify_expr): If stmt ends bb, use single non-EH successor to
	generate loads into replacements.
	(sra_modify_assign): Likewise and and also use the simple path for
	such statements.
	(sra_modify_function_body): Commit statements on edges.

testsuite/
	* gnat.dg/opt34.adb: New.
	* gnat.dg/opt34_pkg.ads: Likewise.

diff --git a/gcc/gimple-iterator.c b/gcc/gimple-iterator.c
index 1cfeb73..8a1ec53 100644
--- a/gcc/gimple-iterator.c
+++ b/gcc/gimple-iterator.c
@@ -689,6 +689,15 @@ gsi_insert_seq_on_edge (edge e, gimple_seq seq)
   gimple_seq_add_seq (&PENDING_STMT (e), seq);
 }
 
+/* Return a new iterator pointing to the first statement in sequence of
+   statements on edge E.  Such statements need to be subsequently moved into a
+   basic block by calling gsi_commit_edge_inserts.  */
+
+gimple_stmt_iterator
+gsi_start_edge (edge e)
+{
+  return gsi_start (PENDING_STMT (e));
+}
 
 /* Insert the statement pointed-to by GSI into edge E.  Every attempt
    is made to place the statement in an existing basic block, but
diff --git a/gcc/gimple-iterator.h b/gcc/gimple-iterator.h
index c35dc81..909d58b 100644
--- a/gcc/gimple-iterator.h
+++ b/gcc/gimple-iterator.h
@@ -123,6 +123,8 @@ gsi_start_bb (basic_block bb)
   return i;
 }
 
+gimple_stmt_iterator gsi_start_edge (edge e);
+
 /* Return a new iterator initially pointing to GIMPLE_SEQ's last statement.  */
 
 static inline gimple_stmt_iterator
diff --git a/gcc/testsuite/gnat.dg/opt34.adb b/gcc/testsuite/gnat.dg/opt34.adb
new file mode 100644
index 0000000..a5d0ab6
--- /dev/null
+++ b/gcc/testsuite/gnat.dg/opt34.adb
@@ -0,0 +1,29 @@
+-- { dg-do compile }
+-- { dg-options "-O -fdump-tree-esra" }
+
+with Opt34_Pkg; use Opt34_Pkg;
+
+procedure Opt34 is
+
+   function Local_Fun (Arg : T_Private) return T_Private is
+      Result : T_Private;
+   begin
+
+      case Get_Integer (Arg) is
+         when 1 =>
+            Result := Get_Private (100);
+         when 2 =>
+            Result := T_Private_Zero;
+         when others =>
+            null;
+      end case;
+
+      return Result;
+   end Local_Fun;
+
+begin
+   Assert (Get_Integer (Local_Fun (Get_Private (1))) = 100);
+end;
+
+-- { dg-final { scan-tree-dump "Created a replacement for result" "esra" } }
+-- { dg-final { cleanup-tree-dump "esra" } }
diff --git a/gcc/testsuite/gnat.dg/opt34_pkg.ads b/gcc/testsuite/gnat.dg/opt34_pkg.ads
new file mode 100644
index 0000000..83ecb49
--- /dev/null
+++ b/gcc/testsuite/gnat.dg/opt34_pkg.ads
@@ -0,0 +1,14 @@
+package Opt34_Pkg is
+
+   type T_Private is record
+      I : Integer := 0;
+   end record;
+
+   T_Private_Zero : constant T_Private := (I => 0);
+
+   function Get_Private (I : Integer) return T_Private;
+   function Get_Integer (X : T_Private) return Integer;
+
+   procedure Assert (Cond : Boolean);
+
+end Opt34_Pkg;
diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index ffef13d..73e681d 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -1142,17 +1142,41 @@ build_access_from_expr (tree expr, gimple stmt, bool write)
   return false;
 }
 
-/* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
-   modes in which it matters, return true iff they have been disqualified.  RHS
-   may be NULL, in that case ignore it.  If we scalarize an aggregate in
-   intra-SRA we may need to add statements after each statement.  This is not
-   possible if a statement unconditionally has to end the basic block.  */
+/* Return the single non-EH successor edge of BB or NULL if there is none or
+   more than one.  */
+
+static edge
+single_non_eh_succ (basic_block bb)
+{
+  edge e, res = NULL;
+  edge_iterator ei;
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    if (!(e->flags & EDGE_EH))
+      {
+	if (res)
+	  return NULL;
+	res = e;
+      }
+
+  return res;
+}
+
+/* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
+   there is no alternative spot where to put statements SRA might need to
+   generate after it.  The spot we are looking for is an edge leading to a
+   single non-EH successor, if it exists and is indeed single.  RHS may be
+   NULL, in that case ignore it.  */
+
 static bool
-disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
+disqualify_if_bad_bb_terminating_stmt (gimple stmt, tree lhs, tree rhs)
 {
   if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
-      && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
+      && stmt_ends_bb_p (stmt))
     {
+      if (single_non_eh_succ (gimple_bb (stmt)))
+	return false;
+
       disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
       if (rhs)
 	disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
@@ -1180,7 +1204,7 @@ build_accesses_from_assign (gimple stmt)
   lhs = gimple_assign_lhs (stmt);
   rhs = gimple_assign_rhs1 (stmt);
 
-  if (disqualify_ops_if_throwing_stmt (stmt, lhs, rhs))
+  if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs))
     return false;
 
   racc = build_access_from_expr_1 (rhs, stmt, false);
@@ -1319,7 +1343,7 @@ scan_function (void)
 		}
 
 	      t = gimple_call_lhs (stmt);
-	      if (t && !disqualify_ops_if_throwing_stmt (stmt, t, NULL))
+	      if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL))
 		ret |= build_access_from_expr (t, stmt, true);
 	      break;
 
@@ -2763,6 +2787,13 @@ sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
   type = TREE_TYPE (*expr);
 
   loc = gimple_location (gsi_stmt (*gsi));
+  gimple_stmt_iterator alt_gsi = gsi_none ();
+  if (write && stmt_ends_bb_p (gsi_stmt (*gsi)))
+    {
+      alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
+      gsi = &alt_gsi;
+    }
+
   if (access->grp_to_be_replaced)
     {
       tree repl = get_access_replacement (access);
@@ -3226,14 +3257,23 @@ sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
   if (modify_this_stmt
       || gimple_has_volatile_ops (*stmt)
       || contains_vce_or_bfcref_p (rhs)
-      || contains_vce_or_bfcref_p (lhs))
+      || contains_vce_or_bfcref_p (lhs)
+      || stmt_ends_bb_p (*stmt))
     {
       if (access_has_children_p (racc))
 	generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
 				 gsi, false, false, loc);
       if (access_has_children_p (lacc))
-	generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
-				 gsi, true, true, loc);
+	{
+	  gimple_stmt_iterator alt_gsi = gsi_none ();
+	  if (stmt_ends_bb_p (*stmt))
+	    {
+	      alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
+	      gsi = &alt_gsi;
+	    }
+	  generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
+				   gsi, true, true, loc);
+	}
       sra_stats.separate_lhs_rhs_handling++;
 
       /* This gimplification must be done after generate_subtree_copies,
@@ -3397,6 +3437,7 @@ sra_modify_function_body (void)
 	}
     }
 
+  gsi_commit_edge_inserts ();
   return cfg_changed;
 }
 

Re: [PATCH] Make SRA tolerate most throwing statements

[Richard Biener]

On Thu, Apr 17, 2014 at 2:21 PM, Martin Jambor <mjambor@suse.cz> wrote:
> On Wed, Apr 16, 2014 at 11:22:28AM +0200, Richard Biener wrote:
>> On Tue, 15 Apr 2014, Martin Jambor wrote:
>>
>> > Hi,
>> >
>> > back in January in
>> > http://gcc.gnu.org/ml/gcc-patches/2014-01/msg00848.html Eric pointed
>> > out a testcase where the problem was SRA not scalarizing an aggregate
>> > because it was involved in a throwing statement.  The reason is that
>> > SRA is likely to need to append new statements after each one where a
>> > replaced aggregate is present, but throwing statements must end their
>> > BBs.  This patch comes up with a fix for most such situations by
>> > adding these new statements onto a single successor non-EH edge, if
>> > there is one and only one such edge.
>> >
>> > I have bootstrapped and tested a very similar version on x86_64-linux,
>> > bootstrap and testing of this exact one is currently underway.  OK for
>> > trunk?  Eric, if and once this gets in, can you please add the
>> > testcase from your original post to the suite?
>> >
>> > Thanks,
>> >
>> > Martin
>> >
>> >
>> > 2014-04-15  Martin Jambor  <mjambor@suse.cz>
>> >
>> >     * tree-sra.c (single_non_eh_succ): New function.
>> >     (disqualify_ops_if_throwing_stmt): Renamed to
>> >     disqualify_if_bad_bb_terminating_stmt.  Allow throwing statements
>> >     having one non-EH successor BB.
>> >     (gsi_for_eh_followups): New function.
>> >     (sra_modify_expr): If stmt ends bb, use single non-EH successor to
>> >     generate loads into replacements.
>> >     (sra_modify_assign): Likewise and and also use the simple path for
>> >     such statements.
>> >     (sra_modify_function_body): Iterate safely over BBs.
>> >
>
> ...
>
>> > @@ -2734,6 +2758,19 @@ get_access_for_expr (tree expr)
>> >    return get_var_base_offset_size_access (base, offset, max_size);
>> >  }
>> >
>> > +/* Split the single non-EH successor edge from BB (there must be exactly one)
>> > +   and return a gimple iterator to the new block.  */
>> > +
>> > +static gimple_stmt_iterator
>> > +gsi_for_eh_followups (basic_block bb)
>> > +{
>> > +  edge e = single_non_eh_succ (bb);
>> > +  gcc_assert (e);
>> > +
>> > +  basic_block new_bb = split_edge (e);
>> > +  return gsi_start_bb (new_bb);
>> > +}
>> > +
>> >  /* Replace the expression EXPR with a scalar replacement if there is one and
>> >     generate other statements to do type conversion or subtree copying if
>> >     necessary.  GSI is used to place newly created statements, WRITE is true if
>> > @@ -2763,6 +2800,13 @@ sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
>> >    type = TREE_TYPE (*expr);
>> >
>> >    loc = gimple_location (gsi_stmt (*gsi));
>> > +  gimple_stmt_iterator alt_gsi = gsi_none ();
>> > +  if (write && stmt_ends_bb_p (gsi_stmt (*gsi)))
>> > +    {
>> > +      alt_gsi = gsi_for_eh_followups (gsi_bb (*gsi));
>> > +      gsi = &alt_gsi;
>>
>> I think you should try to either use gsi_insert_on_edge_immediate
>> (yeah, bad we can't build a gsi_for_edge_insert ()) or add
>> a gsi_for_edge_insert () building on gimple_find_edge_insert_loc
>> (note the before/after flag that returns - gsi_insert_* variants
>> that take a flag specifying after/before would come handy here).
>> You could also add a flag to gimple_find_edge_insert_loc whether
>> it always should be possible to use gsi_insert_after and split
>> the block in some more cases (or split it if both after and
>> before inserts should be valid, but that would not split in
>> the very rare case of an empty successor only).
>>
>> Basically usually you can avoid splitting the edge.
>
> The following patch adds gsi_start_edge for that purpose and uses it
> together with gsi_commit_edge_inserts from within SRA.
>
> I did not make it an inline static function in the header like the
> other gsi initializing functions because that would make
> gimple-iterator.h depend on tree-cfg.h and with our current flat
> includes that triggered changes of includes in half a gazillion
> unrelated c files (I have that patch too because I was apparently too
> lazy to think before the third coffee yesterday but I do not think it
> is worth it).
>
> Bootstrapped and tested on x86_64-linux, this time it also includes
> Eric's testcase.  OK for trunk?

Ok.

Thanks,
Richard.

> Thanks,
>
> Martin
>
>
> 2014-04-16  Martin Jambor  <mjambor@suse.cz>
>
>         * gimple-iterator.c (gsi_start_edge): New function.
>         * gimple-iterator.h (gsi_start_edge): Declare.
>         * tree-sra.c (single_non_eh_succ): New function.
>         (disqualify_ops_if_throwing_stmt): Renamed to
>         disqualify_if_bad_bb_terminating_stmt.  Allow throwing statements
>         having one non-EH successor BB.
>         (sra_modify_expr): If stmt ends bb, use single non-EH successor to
>         generate loads into replacements.
>         (sra_modify_assign): Likewise and and also use the simple path for
>         such statements.
>         (sra_modify_function_body): Commit statements on edges.
>
> testsuite/
>         * gnat.dg/opt34.adb: New.
>         * gnat.dg/opt34_pkg.ads: Likewise.
>
> diff --git a/gcc/gimple-iterator.c b/gcc/gimple-iterator.c
> index 1cfeb73..8a1ec53 100644
> --- a/gcc/gimple-iterator.c
> +++ b/gcc/gimple-iterator.c
> @@ -689,6 +689,15 @@ gsi_insert_seq_on_edge (edge e, gimple_seq seq)
>    gimple_seq_add_seq (&PENDING_STMT (e), seq);
>  }
>
> +/* Return a new iterator pointing to the first statement in sequence of
> +   statements on edge E.  Such statements need to be subsequently moved into a
> +   basic block by calling gsi_commit_edge_inserts.  */
> +
> +gimple_stmt_iterator
> +gsi_start_edge (edge e)
> +{
> +  return gsi_start (PENDING_STMT (e));
> +}
>
>  /* Insert the statement pointed-to by GSI into edge E.  Every attempt
>     is made to place the statement in an existing basic block, but
> diff --git a/gcc/gimple-iterator.h b/gcc/gimple-iterator.h
> index c35dc81..909d58b 100644
> --- a/gcc/gimple-iterator.h
> +++ b/gcc/gimple-iterator.h
> @@ -123,6 +123,8 @@ gsi_start_bb (basic_block bb)
>    return i;
>  }
>
> +gimple_stmt_iterator gsi_start_edge (edge e);
> +
>  /* Return a new iterator initially pointing to GIMPLE_SEQ's last statement.  */
>
>  static inline gimple_stmt_iterator
> diff --git a/gcc/testsuite/gnat.dg/opt34.adb b/gcc/testsuite/gnat.dg/opt34.adb
> new file mode 100644
> index 0000000..a5d0ab6
> --- /dev/null
> +++ b/gcc/testsuite/gnat.dg/opt34.adb
> @@ -0,0 +1,29 @@
> +-- { dg-do compile }
> +-- { dg-options "-O -fdump-tree-esra" }
> +
> +with Opt34_Pkg; use Opt34_Pkg;
> +
> +procedure Opt34 is
> +
> +   function Local_Fun (Arg : T_Private) return T_Private is
> +      Result : T_Private;
> +   begin
> +
> +      case Get_Integer (Arg) is
> +         when 1 =>
> +            Result := Get_Private (100);
> +         when 2 =>
> +            Result := T_Private_Zero;
> +         when others =>
> +            null;
> +      end case;
> +
> +      return Result;
> +   end Local_Fun;
> +
> +begin
> +   Assert (Get_Integer (Local_Fun (Get_Private (1))) = 100);
> +end;
> +
> +-- { dg-final { scan-tree-dump "Created a replacement for result" "esra" } }
> +-- { dg-final { cleanup-tree-dump "esra" } }
> diff --git a/gcc/testsuite/gnat.dg/opt34_pkg.ads b/gcc/testsuite/gnat.dg/opt34_pkg.ads
> new file mode 100644
> index 0000000..83ecb49
> --- /dev/null
> +++ b/gcc/testsuite/gnat.dg/opt34_pkg.ads
> @@ -0,0 +1,14 @@
> +package Opt34_Pkg is
> +
> +   type T_Private is record
> +      I : Integer := 0;
> +   end record;
> +
> +   T_Private_Zero : constant T_Private := (I => 0);
> +
> +   function Get_Private (I : Integer) return T_Private;
> +   function Get_Integer (X : T_Private) return Integer;
> +
> +   procedure Assert (Cond : Boolean);
> +
> +end Opt34_Pkg;
> diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
> index ffef13d..73e681d 100644
> --- a/gcc/tree-sra.c
> +++ b/gcc/tree-sra.c
> @@ -1142,17 +1142,41 @@ build_access_from_expr (tree expr, gimple stmt, bool write)
>    return false;
>  }
>
> -/* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
> -   modes in which it matters, return true iff they have been disqualified.  RHS
> -   may be NULL, in that case ignore it.  If we scalarize an aggregate in
> -   intra-SRA we may need to add statements after each statement.  This is not
> -   possible if a statement unconditionally has to end the basic block.  */
> +/* Return the single non-EH successor edge of BB or NULL if there is none or
> +   more than one.  */
> +
> +static edge
> +single_non_eh_succ (basic_block bb)
> +{
> +  edge e, res = NULL;
> +  edge_iterator ei;
> +
> +  FOR_EACH_EDGE (e, ei, bb->succs)
> +    if (!(e->flags & EDGE_EH))
> +      {
> +       if (res)
> +         return NULL;
> +       res = e;
> +      }
> +
> +  return res;
> +}
> +
> +/* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and
> +   there is no alternative spot where to put statements SRA might need to
> +   generate after it.  The spot we are looking for is an edge leading to a
> +   single non-EH successor, if it exists and is indeed single.  RHS may be
> +   NULL, in that case ignore it.  */
> +
>  static bool
> -disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
> +disqualify_if_bad_bb_terminating_stmt (gimple stmt, tree lhs, tree rhs)
>  {
>    if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
> -      && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
> +      && stmt_ends_bb_p (stmt))
>      {
> +      if (single_non_eh_succ (gimple_bb (stmt)))
> +       return false;
> +
>        disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
>        if (rhs)
>         disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
> @@ -1180,7 +1204,7 @@ build_accesses_from_assign (gimple stmt)
>    lhs = gimple_assign_lhs (stmt);
>    rhs = gimple_assign_rhs1 (stmt);
>
> -  if (disqualify_ops_if_throwing_stmt (stmt, lhs, rhs))
> +  if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs))
>      return false;
>
>    racc = build_access_from_expr_1 (rhs, stmt, false);
> @@ -1319,7 +1343,7 @@ scan_function (void)
>                 }
>
>               t = gimple_call_lhs (stmt);
> -             if (t && !disqualify_ops_if_throwing_stmt (stmt, t, NULL))
> +             if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL))
>                 ret |= build_access_from_expr (t, stmt, true);
>               break;
>
> @@ -2763,6 +2787,13 @@ sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
>    type = TREE_TYPE (*expr);
>
>    loc = gimple_location (gsi_stmt (*gsi));
> +  gimple_stmt_iterator alt_gsi = gsi_none ();
> +  if (write && stmt_ends_bb_p (gsi_stmt (*gsi)))
> +    {
> +      alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
> +      gsi = &alt_gsi;
> +    }
> +
>    if (access->grp_to_be_replaced)
>      {
>        tree repl = get_access_replacement (access);
> @@ -3226,14 +3257,23 @@ sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
>    if (modify_this_stmt
>        || gimple_has_volatile_ops (*stmt)
>        || contains_vce_or_bfcref_p (rhs)
> -      || contains_vce_or_bfcref_p (lhs))
> +      || contains_vce_or_bfcref_p (lhs)
> +      || stmt_ends_bb_p (*stmt))
>      {
>        if (access_has_children_p (racc))
>         generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
>                                  gsi, false, false, loc);
>        if (access_has_children_p (lacc))
> -       generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
> -                                gsi, true, true, loc);
> +       {
> +         gimple_stmt_iterator alt_gsi = gsi_none ();
> +         if (stmt_ends_bb_p (*stmt))
> +           {
> +             alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
> +             gsi = &alt_gsi;
> +           }
> +         generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
> +                                  gsi, true, true, loc);
> +       }
>        sra_stats.separate_lhs_rhs_handling++;
>
>        /* This gimplification must be done after generate_subtree_copies,
> @@ -3397,6 +3437,7 @@ sra_modify_function_body (void)
>         }
>      }
>
> +  gsi_commit_edge_inserts ();
>    return cfg_changed;
>  }
>