Patchwork [PR48866] three alternative fixes

login
register
mail settings
Submitter Alexandre Oliva
Date May 30, 2011, 12:26 p.m.
Message ID <orlixo1iih.fsf@livre.localdomain>
Download mbox | patch
Permalink /patch/97910/
State New
Headers show

Comments

Alexandre Oliva - May 30, 2011, 12:26 p.m.
On May 30, 2011, Alexandre Oliva <aoliva@redhat.com> wrote:

> 3. expand dominators before dominated blocks, so that DEFs of
> replaceable SSA names are expanded before their uses.  Expand them when
> they're encountered, but not requiring a REG as a result.  Save the RTL
> expression that results from the expansion for use in debug insns and at
> the non-debug use.

This patch addresses some of the problems in 2, avoiding expanding code
out of order within a block, and (hopefully) ensuring that, expanding
dominators before dominatedblocks, DEFs are expanded before USEs.  There
is a theoretical possibility that a USE may be expanded before a DEF,
depending on internal details of out-of-ssa, but should this ever
happen, we'll get a failed assertion, and then disabling TER will work
around the problem.

Since no special handling of force_reg is required and we don't reorder
code, we don't need placeholders, and can record only the value
expansion of replaceable DEFs for their uses, debug or not.
Nevertheless, we expand each BB into a separate sequence, and then
re-emit the blocks into a single sequence in the original order.  This
is a bit risky, as the logic of block expansion is modified, more so
because the blocks created during expansion don't get separate sequences
and require special handling, and other (unreachable?) blocks need to be
expanded in a separate loop.

This is the sort of code we get with this patch:

;; x_ = ****y_; (actually a sequence of replaceable gimple assignments)
(set (reg) (mem (reg y_)))
(set (reg) (mem (reg...)))
(set (reg) (mem (reg...)))
;; debug x => x_
(debug_insn (var_location x (mem (reg))))
[...]
;; ? = x_ + 1;
(set (reg x_) (mem (reg...)))
(set (reg ?) (plus (reg x_) (const_int 1)))

Note that the debug_insn binds to a computed expression, although that
same expression is later stored in a register.  This is slightly
undesirable from a debug information POV, but it's probably something we
can live with.

No regressions in a regstrap on x86_64-linux-gnu and i686-linux-gnu.
Michael Matz - May 30, 2011, 1:31 p.m.
Hi,

On Mon, 30 May 2011, Alexandre Oliva wrote:

> > 3. expand dominators before dominated blocks, so that DEFs of 
> >    replaceable SSA names are expanded before their uses.  Expand them 
> >    when they're encountered, but not requiring a REG as a result.  
> >    Save the RTL expression that results from the expansion for use in 
> >    debug insns and at the non-debug use.
> 
> This patch addresses some of the problems in 2, avoiding expanding code 
> out of order within a block, and (hopefully) ensuring that, expanding 
> dominators before dominatedblocks, DEFs are expanded before USEs.  

That isn't necessary.  Replaceable SSA_NAMEs are defined in the same BB as 
their use, and hence they're expanded strictly before their use already 
right now.

> There is a theoretical possibility that a USE may be expanded before a 
> DEF, depending on internal details of out-of-ssa,

This can only happen with non-replaceable SSA_NAMEs and I thought you wish 
to deal only with replaceable.

That said, I dislike approach 2 for the same worries you noted.  And with 
the above I don't see why your approach (3) isn't workable without changes 
to the BB order, which should then be a really small patch.  As SSA_NAMEs 
are (fairly) dense it might be better to simply use an array instead of a 
pointer_map for the SSA_NAME->rtx mapping.


Ciao,
Michael.
Alexandre Oliva - June 1, 2011, 10:28 p.m.
On May 30, 2011, Michael Matz <matz@suse.de> wrote:

> Hi,
> On Mon, 30 May 2011, Alexandre Oliva wrote:

>> > 3. expand dominators before dominated blocks, so that DEFs of 
>> >    replaceable SSA names are expanded before their uses.  Expand them 
>> >    when they're encountered, but not requiring a REG as a result.  
>> >    Save the RTL expression that results from the expansion for use in 
>> >    debug insns and at the non-debug use.
>> 
>> This patch addresses some of the problems in 2, avoiding expanding code 
>> out of order within a block, and (hopefully) ensuring that, expanding 
>> dominators before dominatedblocks, DEFs are expanded before USEs.  

> That isn't necessary.  Replaceable SSA_NAMEs are defined in the same BB as 
> their use, and hence they're expanded strictly before their use already 
> right now.

Hmm...  You're obviously right.  I must have misinterpreted some other
failure, then.  Thanks, this enables some simplification to two of the
patches.

>> There is a theoretical possibility that a USE may be expanded before a 
>> DEF, depending on internal details of out-of-ssa,

> This can only happen with non-replaceable SSA_NAMEs and I thought you wish 
> to deal only with replaceable.

Yup.

> That said, I dislike approach 2 for the same worries you noted.  And with 
> the above I don't see why your approach (3) isn't workable without changes 
> to the BB order, which should then be a really small patch.

Yup.  I'll give that a try.

> As SSA_NAMEs are (fairly) dense it might be better to simply use an
> array instead of a pointer_map for the SSA_NAME->rtx mapping.

Likewise.

Thanks!

Patch

for  gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR debug/48866
	* cfgexpand.c (def_expansions): New.
	(def_expansion_recent_tree, def_expansion_recent_rtx): New.
	(def_expansions_init, def_expansions_fini): New.
	(def_has_expansion_ptr, def_get_expansion_ptr): New.
	(expand_debug_expr): Use recorded expansion if available.
	(expand_gimple_basic_block): Prepare to record expansion of
	replaceable defs.  Change return type to void.
	(gimple_expand_cfg): Initialize and finalize expansions cache.
	Expand dominator blocks before dominated.
	* expr.c (expand_expr_real_1): Use recorded expansion of
	replaceable defs.
	* expr.h (def_has_expansion_ptr): Declare.

Index: gcc/cfgexpand.c
===================================================================
--- gcc/cfgexpand.c.orig	2011-05-28 07:11:12.132275336 -0300
+++ gcc/cfgexpand.c	2011-05-28 07:19:55.128377121 -0300
@@ -2337,6 +2337,55 @@  convert_debug_memory_address (enum machi
   return x;
 }
 
+/* Map replaceable SSA_NAMEs to their RTL expansions.  */
+static struct pointer_map_t *def_expansions;
+
+/* Initialize the def_expansions data structure.  This is to be called
+   before expansion of a function starts.  */
+
+static void
+def_expansions_init (void)
+{
+  gcc_checking_assert (!def_expansions);
+  def_expansions = pointer_map_create ();
+}
+
+/* Finalize the def_expansions data structure.  This is to be called
+   at the end of the expansion of a function.  */
+
+static void
+def_expansions_fini (void)
+{
+  gcc_checking_assert (def_expansions);
+  pointer_map_destroy (def_expansions);
+  def_expansions = NULL;
+}
+
+/* Return NULL if no expansion is registered for EXP, or a pointer to
+   the rtx expanded from it otherwise.  EXP must be a replaceable
+   SSA_NAME.  */
+
+void *const *
+def_has_expansion_ptr (tree exp)
+{
+  gcc_checking_assert (def_expansions);
+  gcc_checking_assert (TREE_CODE (exp) == SSA_NAME);
+  gcc_checking_assert (bitmap_bit_p (SA.values, SSA_NAME_VERSION (exp)));
+  return pointer_map_contains (def_expansions, exp);
+}
+
+/* Return a pointer to the rtx expanded from EXP.  EXP must be a
+   replaceable SSA_NAME.  */
+
+static void **
+def_get_expansion_ptr (tree exp)
+{
+  gcc_checking_assert (def_expansions);
+  gcc_checking_assert (TREE_CODE (exp) == SSA_NAME);
+  gcc_checking_assert (bitmap_bit_p (SA.values, SSA_NAME_VERSION (exp)));
+  return pointer_map_insert (def_expansions, exp);
+}
+
 /* Return an RTX equivalent to the value of the tree expression
    EXP.  */
 
@@ -3131,7 +3180,16 @@  expand_debug_expr (tree exp)
 	gimple g = get_gimple_for_ssa_name (exp);
 	if (g)
 	  {
-	    op0 = expand_debug_expr (gimple_assign_rhs_to_tree (g));
+	    void *const *xp = def_has_expansion_ptr (exp);
+
+	    if (xp)
+	      op0 = (rtx) *xp;
+	    else
+	      op0 = NULL;
+
+	    if (!op0)
+	      op0 = expand_debug_expr (gimple_assign_rhs_to_tree (g));
+
 	    if (!op0)
 	      return NULL;
 	  }
@@ -3346,7 +3404,7 @@  expand_debug_locations (void)
 
 /* Expand basic block BB from GIMPLE trees to RTL.  */
 
-static basic_block
+static void
 expand_gimple_basic_block (basic_block bb)
 {
   gimple_stmt_iterator gsi;
@@ -3539,7 +3597,7 @@  expand_gimple_basic_block (basic_block b
 	{
 	  new_bb = expand_gimple_cond (bb, stmt);
 	  if (new_bb)
-	    return new_bb;
+	    return;
 	}
       else if (gimple_debug_bind_p (stmt))
 	{
@@ -3613,25 +3671,43 @@  expand_gimple_basic_block (basic_block b
 		  if (can_fallthru)
 		    bb = new_bb;
 		  else
-		    return new_bb;
+		    return;
 		}
 	    }
 	  else
 	    {
+	      void **xp = NULL;
 	      def_operand_p def_p;
 	      def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
 
-	      if (def_p != NULL)
+	      /* Ignore this stmt if it is in the list of
+		 replaceable expressions.  */
+	      if (def_p != NULL
+		  && SA.values
+		  && bitmap_bit_p (SA.values,
+				   SSA_NAME_VERSION (DEF_FROM_PTR (def_p))))
 		{
-		  /* Ignore this stmt if it is in the list of
-		     replaceable expressions.  */
-		  if (SA.values
-		      && bitmap_bit_p (SA.values,
-				       SSA_NAME_VERSION (DEF_FROM_PTR (def_p))))
-		    continue;
+		  tree def = DEF_FROM_PTR (def_p);
+		  gimple g = get_gimple_for_ssa_name (def);
+		  rtx retval;
+
+		  last = get_last_insn ();
+
+		  retval = expand_expr (gimple_assign_rhs_to_tree (g),
+					NULL_RTX, VOIDmode, EXPAND_SUM);
+
+		  xp = def_get_expansion_ptr (def);
+		  gcc_checking_assert (!*xp);
+		  *xp = retval;
 		}
-	      last = expand_gimple_stmt (stmt);
+	      else
+		last = expand_gimple_stmt (stmt);
 	      maybe_dump_rtl_for_gimple_stmt (stmt, last);
+	      if (xp && dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "\n=> ");
+		  print_rtl (dump_file, (rtx) *xp);
+		}
 	    }
 	}
     }
@@ -3680,10 +3756,9 @@  expand_gimple_basic_block (basic_block b
 
   update_bb_for_insn (bb);
 
-  return bb;
+  return;
 }
 
-
 /* Create a basic block for initialization code.  */
 
 static basic_block
@@ -3969,6 +4044,9 @@  gimple_expand_cfg (void)
   edge e;
   rtx var_seq;
   unsigned i;
+  VEC (basic_block, heap) *h;
+  int nblocks;
+
 
   timevar_push (TV_OUT_OF_SSA);
   rewrite_out_of_ssa (&SA);
@@ -4112,11 +4190,41 @@  gimple_expand_cfg (void)
     e->flags &= ~EDGE_EXECUTABLE;
 
   lab_rtx_for_bb = pointer_map_create ();
+  def_expansions_init ();
+
+  /* Expand dominators before dominated blocks, so that replaceable
+     DEFs are always expanded before their uses.  */
+  nblocks = last_basic_block;
+  blocks = sbitmap_alloc (nblocks);
+  sbitmap_zero (blocks);
+
+  h = get_all_dominated_blocks (CDI_DOMINATORS, init_block->next_bb);
+
+  FOR_EACH_VEC_ELT (basic_block, h, i, bb)
+    {
+      gcc_checking_assert (bb->index < nblocks);
+      SET_BIT (blocks, bb->index);
+
+      start_sequence ();
+      emit_note (NOTE_INSN_DELETED);
+      expand_gimple_basic_block (bb);
+      end_sequence ();
+    }
+
+  VEC_free (basic_block, heap, h);
+
   FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
-    bb = expand_gimple_basic_block (bb);
+    if (bb->index >= nblocks)
+      continue;
+    else if (TEST_BIT (blocks, bb->index))
+      emit_insn (BB_HEAD (bb));
+    else
+      expand_gimple_basic_block (bb);
+  sbitmap_free (blocks);
 
   if (MAY_HAVE_DEBUG_INSNS)
     expand_debug_locations ();
+  def_expansions_fini ();
 
   execute_free_datastructures ();
   timevar_push (TV_OUT_OF_SSA);
Index: gcc/expr.c
===================================================================
--- gcc/expr.c.orig	2011-05-28 07:11:12.139275310 -0300
+++ gcc/expr.c	2011-05-28 07:11:14.895265175 -0300
@@ -8424,10 +8424,21 @@  expand_expr_real_1 (tree exp, rtx target
 	  && !SSA_NAME_IS_DEFAULT_DEF (exp)
 	  && (optimize || DECL_IGNORED_P (SSA_NAME_VAR (exp)))
 	  && stmt_is_replaceable_p (SSA_NAME_DEF_STMT (exp)))
-	g = SSA_NAME_DEF_STMT (exp);
+	{
+	  g = SSA_NAME_DEF_STMT (exp);
+	  if (g)
+	    return expand_expr_real (gimple_assign_rhs_to_tree (g),
+				     target, tmode, modifier, NULL);
+	}
       if (g)
-	return expand_expr_real (gimple_assign_rhs_to_tree (g), target, tmode,
-				 modifier, NULL);
+	{
+	  void *const *xp = def_has_expansion_ptr (exp);
+	  rtx retval = (rtx) *xp;
+
+	  gcc_assert (retval);
+
+	  return retval;
+	}
 
       ssa_name = exp;
       decl_rtl = get_rtx_for_ssa_name (ssa_name);
Index: gcc/expr.h
===================================================================
--- gcc/expr.h.orig	2011-05-28 07:11:12.147275281 -0300
+++ gcc/expr.h	2011-05-28 07:16:13.428175792 -0300
@@ -693,4 +693,7 @@  extern tree build_libfunc_function (cons
 /* Get the personality libfunc for a function decl.  */
 rtx get_personality_function (tree);
 
+/* In cfgexpand.c.  */
+void *const *def_has_expansion_ptr (tree);
+
 #endif /* GCC_EXPR_H */