Patchwork [PR48866] three alternative fixes

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

Comments

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

> 2. emit placeholders for replaceable DEFs and, when the DEFs are
> expanded at their point of use, emit the expansion next to the
> placeholder, rather than at the current stream.  The result of the
> expansion is saved and used in debug insns that reference the
> replaceable DEF.  If the result is forced into a REG shortly thereafter,
> the code resulting from this is also emitted next to the placeholder,
> and the saved expansion is updated.  If the USE is expanded before the
> DEF, the insn stream resulting from the expansion is saved and emitted
> at the point of the DEF.

IMHO this is the riskiest of the 3 patches, for shuffling expansions
around isn't exactly something I'm comfortable with.  There's a very
real risk that moving the expansion of sub-expressions to their
definition points may end up moving uses before definitions.

I've actually caught a few such cases, and the checks on whether the
result of expanding the sub-expression is the requested target, the
handling of recent expansions and the resetting of recent expansions
across basic blocks were all in reponse to such cases.  I'm not sure
there aren't other, so I'm not entirely comfortable with this approach.
However, it survived regstrap on x86_64-linux-gnu and i686-linux-gnu, at
various optimization levels, so it might actually be safe.

One nice property of this patch is that debug insns remain after the
expansion of DEFs they refer to, so they will most often bind to a
simple expression, even a REG, if the expansion was forced to one.  This
is superior to the two other patches in that users of a debugger will be
able to modify the user variable, whereas with the others, the variable
will likely be bound to a computed expression, which the debugger will
be unable to modify.

Of course, moving replaceable expressions to their original points
extends the live ranges of their results, be they registers or computed
expressions involving other registers.

With this patch, the generated code looks like this:

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


Another negative point of this patch is that it emits placeholder notes,
that are discarded at the end of expansion, i.e., garbage.  One
complication is that, since DEF and USE may be in different blocks, and
there's no guarantee that DEF will be expanded before USE, we end up
having to support the possibility that the USE is expanded first.  In
either case, the insns are emitted in a separate sequence, and then
emitted at the proper place, which is an additional inefficiency at
expand time.  Some of this may be recovered by the simpler debug
expressions, if they survive, but only for -g compilations.

Here's the patch, regstrapped on x86_64-linux-gnu and i686-linux-gnu.

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): New.
	(def_expansions_remove_placeholder, def_expansions_fini): New.
	(def_has_expansion_ptr, def_get_expansion_ptr): New.
	(def_expansion_recent, def_expansion_record_recent): New.
	(def_expansion_add_insns): New.
	(expand_debug_expr): Use recorded expansion if available.
	(expand_gimple_basic_block): Emit or prepare to record
	expansion of replaceable defs.  Reset recent expansions at the
	end of the block.
	(gimple_expand_cfg): Initialize and finalize expansions cache.
	* expr.c: Include gimple-pretty-print.h.
	(store_expr): Forget recent expansions upon nontemporal moves.
	(expand_expr_real_1): Reuse or record expansion of replaceable
	defs.
	* expr.h (def_get_expansion_ptr, def_expansion_recent): Declare.
	(def_expansion_record_recent, def_expansion_add_insns): Declare.
	* explow.c (force_recent): New.
	(force_reg): Use it.  Split into...
	(force_reg_1): ... this.
	* Makefile.in (expr.o): Depend on gimple-pretty-print.h.

Index: gcc/cfgexpand.c
===================================================================
--- gcc/cfgexpand.c.orig	2011-05-26 05:03:08.492988988 -0300
+++ gcc/cfgexpand.c	2011-05-26 05:03:31.861035336 -0300
@@ -2337,6 +2337,166 @@  convert_debug_memory_address (enum machi
   return x;
 }
 
+/* Map replaceable SSA_NAMEs to NOTE_INSN_VAR_LOCATIONs that hold
+   their RTL expansions (once available) in their NOTE_VAR_LOCATIONs
+   (without a VAR_LOCATION rtx).  The NOTE is always after the
+   expansion insns.
+
+   If the SSA_NAME DEF is expanded before its single USE, the NOTE is
+   inserted in the insn stream, marking the location where the
+   non-replaceable portion of the expansion is to be inserted.
+
+   If the USE is expanded first, the NOTE and the expansion are
+   emitted as a separate insn chain, that is to be re-emitted when the
+   DEF is expanded.  */
+static struct pointer_map_t *def_expansions;
+
+/* The latest expanded SSA name, and its corresponding RTL expansion.
+   These are used to enable the insertion of the insn that stores the
+   expansion in a register at the end of the sequence expanded for the
+   SSA DEF.  */
+static tree def_expansion_recent_tree;
+static rtx def_expansion_recent_rtx;
+
+/* 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 ();
+
+  gcc_checking_assert (!def_expansion_recent_tree);
+  gcc_checking_assert (!def_expansion_recent_rtx);
+}
+
+/* Remove the NOTE at **XP that marks the insertion location of the
+   expansion of a replaceable SSA note.  */
+
+static bool
+def_expansions_remove_placeholder (const void *def ATTRIBUTE_UNUSED,
+				   void **xp,
+				   void *arg ATTRIBUTE_UNUSED)
+{
+  rtx note = (rtx) *xp;
+
+  if (!note)
+    return true;
+
+  gcc_checking_assert (NOTE_P (note));
+  remove_insn (note);
+
+  return true;
+}
+
+/* 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_traverse (def_expansions,
+			def_expansions_remove_placeholder, NULL);
+
+  pointer_map_destroy (def_expansions);
+  def_expansions = NULL;
+  def_expansion_recent_tree = NULL;
+  def_expansion_recent_rtx = NULL;
+}
+
+/* Return NULL if no expansions is registered for EXP, or a pointer to
+   the address of its location NOTE otherwise.  EXP must be a
+   replaceable SSA_NAME.  */
+
+static 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 address of EXP's location NOTE.  If the
+   address (not the pointer) is NULL, the caller must initialize it
+   with a newly-created NOTE.  EXP must be a replaceable SSA_NAME.  */
+
+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 SSA name, if any, that was recently expanded to the value
+   X.  */
+
+tree
+def_expansion_recent (rtx x)
+{
+  if (!def_expansion_recent_rtx)
+    return NULL;
+
+  if (x == def_expansion_recent_rtx
+      || rtx_equal_p (x, def_expansion_recent_rtx))
+    return def_expansion_recent_tree;
+
+  return NULL;
+}
+
+/* Record that DEF was recently expanded to the value X.  */
+
+void
+def_expansion_record_recent (tree def, rtx x)
+{
+  def_expansion_recent_tree = def;
+  def_expansion_recent_rtx = x;
+}
+
+/* Forget recent expansions.  */
+
+void
+def_expansion_reset_recent (void)
+{
+  def_expansion_record_recent (NULL, NULL);
+}
+
+/* Add INSNS to the insn seq generated for DEF, and update the
+   RTL value of DEF to VAL.  */
+
+void
+def_expansion_add_insns (tree def, rtx insns, rtx val)
+{
+  void **xp = def_get_expansion_ptr (def);
+  rtx note = (rtx) *xp;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "\n;; (cont) ");
+      print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (def), 0,
+			 TDF_SLIM | (dump_flags & TDF_LINENO));
+      fprintf (dump_file, "\n");
+
+      print_rtl (dump_file, insns);
+
+      fprintf (dump_file, "\n=> ");
+      print_rtl (dump_file, val);
+    }
+
+  gcc_checking_assert (note);
+  emit_insn_before (insns, note);
+  gcc_checking_assert (NOTE_VAR_LOCATION (note));
+  NOTE_VAR_LOCATION (note) = val;
+
+  def_expansion_recent_tree = NULL;
+  def_expansion_recent_rtx = NULL;
+}
+
 /* Return an RTX equivalent to the value of the tree expression
    EXP.  */
 
@@ -3131,7 +3291,20 @@  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)
+	      {
+		rtx note = (rtx) *xp;
+		gcc_checking_assert (NOTE_P (note));
+		op0 = NOTE_VAR_LOCATION (note);
+	      }
+	    else
+	      op0 = NULL;
+
+	    if (!op0)
+	      op0 = expand_debug_expr (gimple_assign_rhs_to_tree (g));
+
 	    if (!op0)
 	      return NULL;
 	  }
@@ -3621,22 +3794,46 @@  expand_gimple_basic_block (basic_block b
 	      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);
+		  void **xp = def_get_expansion_ptr (def);
+
+		  last = get_last_insn ();
+
+		  if (!*xp)
+		    {
+		      rtx note = emit_note (NOTE_INSN_VAR_LOCATION);
+		      NOTE_VAR_LOCATION (note) = NULL;
+		      *xp = note;
+		    }
+		  else
+		    {
+		      rtx note = (rtx) *xp;
+		      rtx first;
+
+		      for (first = note;
+			   PREV_INSN (first);
+			   first = PREV_INSN (first))
+			;
+
+		      emit_insn (first);
+		    }
 		}
-	      last = expand_gimple_stmt (stmt);
+	      else
+		last = expand_gimple_stmt (stmt);
 	      maybe_dump_rtl_for_gimple_stmt (stmt, last);
 	    }
 	}
     }
 
   currently_expanding_gimple_stmt = NULL;
+  def_expansion_reset_recent ();
 
   /* Expand implicit goto and convert goto_locus.  */
   FOR_EACH_EDGE (e, ei, bb->succs)
@@ -4112,11 +4309,14 @@  gimple_expand_cfg (void)
     e->flags &= ~EDGE_EXECUTABLE;
 
   lab_rtx_for_bb = pointer_map_create ();
+  def_expansions_init ();
+
   FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
     bb = expand_gimple_basic_block (bb);
 
   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-26 05:03:08.493988990 -0300
+++ gcc/expr.c	2011-05-26 05:03:31.869035352 -0300
@@ -48,6 +48,7 @@  along with GCC; see the file COPYING3.  
 #include "tree-iterator.h"
 #include "tree-pass.h"
 #include "tree-flow.h"
+#include "gimple-pretty-print.h"
 #include "target.h"
 #include "timevar.h"
 #include "df.h"
@@ -4675,6 +4676,9 @@  store_expr (tree exp, rtx target, int ca
 			       (call_param_p
 				? EXPAND_STACK_PARM : EXPAND_NORMAL),
 			       &alt_rtl);
+      /* Don't risk moving loads before stores.  */
+      if (!nontemporal)
+	def_expansion_reset_recent ();
     }
 
   /* If TEMP is a VOIDmode constant and the mode of the type of EXP is not
@@ -8424,10 +8428,71 @@  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);
+	{
+	  rtx retval;
+	  rtx insns;
+	  void **xp = def_get_expansion_ptr (exp);
+	  rtx note = (rtx) *xp;
+	  bool def_expanded = !!note;
+
+	  if (note && NOTE_VAR_LOCATION (note))
+	    return NOTE_VAR_LOCATION (note);
+
+	  start_sequence ();
+
+	  retval = expand_expr_real (gimple_assign_rhs_to_tree (g),
+				     target, tmode, modifier, NULL);
+
+	  insns = get_insns ();
+
+	  if (retval == target)
+	    {
+	      end_sequence ();
+	      emit_insn (insns);
+	      return retval;
+	    }
+
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "\n;; ");
+	      print_gimple_stmt (dump_file, g, 0,
+				 TDF_SLIM | (dump_flags & TDF_LINENO));
+	      fprintf (dump_file, "\n");
+
+	      print_rtl (dump_file, insns);
+
+	      fprintf (dump_file, "\n=> ");
+	      print_rtl (dump_file, retval);
+	    }
+
+	  if (!def_expanded)
+	    {
+	      note = emit_note (NOTE_INSN_VAR_LOCATION);
+	      *xp = note;
+	    }
+
+	  end_sequence ();
+
+	  if (def_expanded)
+	    {
+	      /* Make sure this is not in the instruction stream.  */
+	      gcc_checking_assert (PREV_INSN (note));
+	      emit_insn_before (insns, note);
+	      gcc_checking_assert (!NOTE_VAR_LOCATION (note));
+	    }
+
+	  NOTE_VAR_LOCATION (note) = retval;
+	  def_expansion_record_recent (exp, 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-26 05:03:08.494988992 -0300
+++ gcc/expr.h	2011-05-26 05:03:31.897035408 -0300
@@ -693,4 +693,11 @@  extern tree build_libfunc_function (cons
 /* Get the personality libfunc for a function decl.  */
 rtx get_personality_function (tree);
 
+/* In cfgexpand.c.  */
+void **def_get_expansion_ptr (tree);
+tree def_expansion_recent (rtx);
+void def_expansion_record_recent (tree, rtx);
+void def_expansion_reset_recent (void);
+void def_expansion_add_insns (tree, rtx, rtx);
+
 #endif /* GCC_EXPR_H */
Index: gcc/explow.c
===================================================================
--- gcc/explow.c.orig	2011-05-26 05:03:08.495988994 -0300
+++ gcc/explow.c	2011-05-26 05:03:31.900035414 -0300
@@ -638,22 +638,62 @@  copy_to_mode_reg (enum machine_mode mode
   return temp;
 }
 
+/* If X is the value of a recently-expanded SSA def, emit the insns
+   generated by FN (MODE, X) at the end of the expansion of that def,
+   otherwise emit them in the current insn seq.  */
+
+static inline rtx
+force_recent (enum machine_mode mode, rtx x,
+	      rtx (*fn) (enum machine_mode, rtx))
+{
+  tree def = def_expansion_recent (x);
+  rtx retval;
+  rtx insns;
+
+  if (!def)
+    return fn (mode, x);
+
+  start_sequence ();
+  retval = fn (mode, x);
+  insns = get_insns ();
+  end_sequence ();
+
+  def_expansion_add_insns (def, insns, retval);
+
+  return retval;
+}
+
+static rtx force_reg_1 (enum machine_mode, rtx);
+
 /* Load X into a register if it is not already one.
    Use mode MODE for the register.
    X should be valid for mode MODE, but it may be a constant which
    is valid for all integer modes; that's why caller must specify MODE.
 
+   If X is the value of a recent SSA def expansion, emit the insns at
+   the end of that expansion, rather than into the current seq.
+
    The caller must not alter the value in the register we return,
    since we mark it as a "constant" register.  */
 
 rtx
 force_reg (enum machine_mode mode, rtx x)
 {
-  rtx temp, insn, set;
-
   if (REG_P (x))
     return x;
 
+  return force_recent (mode, x, force_reg_1);
+}
+
+/* Load X into a register if it is not already one.
+   Use mode MODE for the register.
+   Internal implementation of force_reg.  */
+
+static rtx
+force_reg_1 (enum machine_mode mode, rtx x)
+{
+  rtx temp, insn, set;
+
   if (general_operand (x, mode))
     {
       temp = gen_reg_rtx (mode);
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in.orig	2011-05-26 05:03:08.496988996 -0300
+++ gcc/Makefile.in	2011-05-26 05:03:31.904035421 -0300
@@ -2940,7 +2940,8 @@  except.o : except.c $(CONFIG_H) $(SYSTEM
 expr.o : expr.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(TREE_H) $(FLAGS_H) $(FUNCTION_H) $(REGS_H) $(EXPR_H) $(OPTABS_H) \
    $(LIBFUNCS_H) $(INSN_ATTR_H) insn-config.h $(RECOG_H) output.h \
-   typeclass.h hard-reg-set.h toplev.h $(DIAGNOSTIC_CORE_H) hard-reg-set.h $(EXCEPT_H) \
+   typeclass.h hard-reg-set.h toplev.h $(DIAGNOSTIC_CORE_H) \
+   gimple-pretty-print.h hard-reg-set.h $(EXCEPT_H) \
    reload.h langhooks.h intl.h $(TM_P_H) $(TARGET_H) \
    tree-iterator.h gt-expr.h $(MACHMODE_H) $(TIMEVAR_H) $(TREE_FLOW_H) \
    $(TREE_PASS_H) $(DF_H) $(DIAGNOSTIC_H) vecprim.h $(SSAEXPAND_H)