subject:"\[PR48866\] three alternative fixes"

Re: [PR48866] three alternative fixes

2012-06-13 Thread Alexandre Oliva

On Apr  9, 2012, Alexandre Oliva aol...@redhat.com wrote:

 On Jun  2, 2011, Alexandre Oliva aol...@redhat.com wrote:
 On May 30, 2011, Alexandre Oliva aol...@redhat.com wrote:
 On May 30, 2011, Alexandre Oliva aol...@redhat.com wrote:

 I have 3 different, mutually exclusive patches that fix PR 48866.  The
 problem is exponential time while dealing with an expression that
 resulted from a long chain of replaceable insns with memory accesses
 moved past the debug insns referring to their results.

 1. emit debug temps for replaceable DEFs that end up being referenced in
 debug insns.  We already have some code to try to deal with this, but it
 emits the huge expressions we'd rather avoid, and it may create
 unnecessary duplication.  This new approach emits a placeholder instead
 of skipping replaceable DEFs altogether, and then, if the DEF is
 referenced in a debug insn (perhaps during the late debug re-expasion of
 some other placeholder), it is expanded.  Placeholders that end up not
 being referenced are then throw away.

 This is my favorite option, for it's safest: it doesn't change
 executable code at all (or should I say it *shouldn't* change it, for I
 haven't verified that it doesn't), retaining any register pressure
 benefits from TER.

 This revised and retested version records expansions in an array indexed
 on SSA version rather than a pointer_map, as suggested by Matz.

 Updated to deal with debug source bind stmts, added an assertion in
 var-tracking to make sure we don't get unexpected kinds of decls in
 VAR_LOCATION insns.  Regstrapped on x86_64-linux-gnu and i686-linux-gnu.
 Ok to install?

 for  gcc/ChangeLog
 from  Alexandre Oliva  aol...@redhat.com

   PR debug/48866
   * cfgexpand.c (DEBUG_INSN_TOEXPAND): New.
   (def_expansions): New.
   (def_expansions_init): New.
   (def_expansions_remove_placeholder, def_expansions_fini): New.
   (def_get_expansion_ptr): New.
   (expand_debug_expr): Create debug temps as needed.
   (expand_debug_insn): New, split out of...
   (expand_debug_locations): ... this.
   (gen_emit_debug_insn): New, split out of...
   (expand_gimple_basic_block): ... this.  Simplify expansion of
   debug stmts.  Emit placeholders for replaceable DEFs, rather
   than debug temps at last non-debug uses.
   (gimple_expand_cfg): Initialize and finalize expansions cache.
   * var-tracking.c (use_type): Check for acceptable var decls in
   var_locations.

Ping?  http://gcc.gnu.org/ml/gcc-patches/2012-04/msg00413.html

-- 
Alexandre Oliva, freedom fighterhttp://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist  Red Hat Brazil Compiler Engineer

Re: [PR48866] three alternative fixes

2012-04-09 Thread Alexandre Oliva

On Jun  2, 2011, Alexandre Oliva aol...@redhat.com wrote:

 On May 30, 2011, Alexandre Oliva aol...@redhat.com wrote:
 On May 30, 2011, Alexandre Oliva aol...@redhat.com wrote:

 I have 3 different, mutually exclusive patches that fix PR 48866.  The
 problem is exponential time while dealing with an expression that
 resulted from a long chain of replaceable insns with memory accesses
 moved past the debug insns referring to their results.

 1. emit debug temps for replaceable DEFs that end up being referenced in
 debug insns.  We already have some code to try to deal with this, but it
 emits the huge expressions we'd rather avoid, and it may create
 unnecessary duplication.  This new approach emits a placeholder instead
 of skipping replaceable DEFs altogether, and then, if the DEF is
 referenced in a debug insn (perhaps during the late debug re-expasion of
 some other placeholder), it is expanded.  Placeholders that end up not
 being referenced are then throw away.

 This is my favorite option, for it's safest: it doesn't change
 executable code at all (or should I say it *shouldn't* change it, for I
 haven't verified that it doesn't), retaining any register pressure
 benefits from TER.

 This revised and retested version records expansions in an array indexed
 on SSA version rather than a pointer_map, as suggested by Matz.

Updated to deal with debug source bind stmts, added an assertion in
var-tracking to make sure we don't get unexpected kinds of decls in
VAR_LOCATION insns.  Regstrapped on x86_64-linux-gnu and i686-linux-gnu.
Ok to install?

for  gcc/ChangeLog
from  Alexandre Oliva  aol...@redhat.com

	PR debug/48866
	* cfgexpand.c (DEBUG_INSN_TOEXPAND): New.
	(def_expansions): New.
	(def_expansions_init): New.
	(def_expansions_remove_placeholder, def_expansions_fini): New.
	(def_get_expansion_ptr): New.
	(expand_debug_expr): Create debug temps as needed.
	(expand_debug_insn): New, split out of...
	(expand_debug_locations): ... this.
	(gen_emit_debug_insn): New, split out of...
	(expand_gimple_basic_block): ... this.  Simplify expansion of
	debug stmts.  Emit placeholders for replaceable DEFs, rather
	than debug temps at last non-debug uses.
	(gimple_expand_cfg): Initialize and finalize expansions cache.
	* var-tracking.c (use_type): Check for acceptable var decls in
	var_locations.

Index: gcc/cfgexpand.c
===
--- gcc/cfgexpand.c.orig	2012-04-08 01:43:59.334000124 -0300
+++ gcc/cfgexpand.c	2012-04-08 01:50:46.851123535 -0300
@@ -2611,6 +2611,70 @@ expand_debug_parm_decl (tree decl)
   return NULL_RTX;
 }
 
+/* Mark debug insns that are placeholders for replaceable SSA_NAMEs
+   that have not been expanded yet.  */
+#define DEBUG_INSN_TOEXPAND(RTX)	\
+  (RTL_FLAG_CHECK1(DEBUG_INSN_TOEXPAND, (RTX), DEBUG_INSN)-used)
+
+/* Map replaceable SSA_NAMEs versions to their RTL expansions.  */
+static rtx *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 = XCNEWVEC (rtx, num_ssa_names);
+}
+
+/* Remove the DEBUG_INSN INSN if it still binds an SSA_NAME.  */
+
+static bool
+def_expansions_remove_placeholder (rtx insn)
+{
+  gcc_checking_assert (insn);
+
+  if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == SSA_NAME)
+{
+  gcc_assert (!DEBUG_INSN_TOEXPAND (insn));
+  remove_insn (insn);
+}
+
+  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)
+{
+  int i = num_ssa_names;
+
+  gcc_checking_assert (def_expansions);
+  while (i--)
+if (def_expansions[i])
+  def_expansions_remove_placeholder (def_expansions[i]);
+  XDELETEVEC (def_expansions);
+  def_expansions = NULL;
+}
+
+/* Return a pointer to the rtx expanded from EXP.  EXP must be a
+   replaceable SSA_NAME.  */
+
+static rtx *
+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 def_expansions[SSA_NAME_VERSION (exp)];
+}
+
+static void expand_debug_insn (rtx insn);
+
 /* Return an RTX equivalent to the value of the tree expression EXP.  */
 
 static rtx
@@ -3421,7 +3485,30 @@ 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));
+	rtx insn = *def_get_expansion_ptr (exp);
+	tree vexpr;
+
+	/* If this still has the original SSA_NAME, emit a debug
+	   temp and compute the RTX value.  */
+	if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == SSA_NAME)
+	  {
+		tree var = SSA_NAME_VAR (INSN_VAR_LOCATION_DECL (insn));
+
+		vexpr = make_node (DEBUG_EXPR_DECL);
+		DECL_ARTIFICIAL

Re: [PR48866] three alternative fixes

2011-06-02 Thread Alexandre Oliva

On May 30, 2011, Alexandre Oliva aol...@redhat.com wrote:

 On May 30, 2011, Alexandre Oliva aol...@redhat.com wrote:
 1. emit debug temps for replaceable DEFs that end up being referenced in
 debug insns.  We already have some code to try to deal with this, but it
 emits the huge expressions we'd rather avoid, and it may create
 unnecessary duplication.  This new approach emits a placeholder instead
 of skipping replaceable DEFs altogether, and then, if the DEF is
 referenced in a debug insn (perhaps during the late debug re-expasion of
 some other placeholder), it is expanded.  Placeholders that end up not
 being referenced are then throw away.

 This is my favorite option, for it's safest: it doesn't change
 executable code at all (or should I say it *shouldn't* change it, for I
 haven't verified that it doesn't), retaining any register pressure
 benefits from TER.

This revised and retested version records expansions in an array indexed
on SSA version rather than a pointer_map, as suggested by Matz.

for  gcc/ChangeLog
from  Alexandre Oliva  aol...@redhat.com

	PR debug/48866
	* cfgexpand.c (def_expansions): New.
	(def_expansions_init): New.
	(def_expansions_remove_placeholder, def_expansions_fini): New.
	(def_get_expansion_ptr): New.
	(expand_debug_expr): Create debug temps as needed.
	(expand_debug_insn): New, split out of...
	(expand_debug_locations): ... this.
	(gen_emit_debug_insn): New, split out of...
	(expand_gimple_basic_block): ... this.  Simplify expansion of
	debug stmts.  Emit placeholders for replaceable DEFs, rather
	than debug temps at last non-debug uses.
	(gimple_expand_cfg): Initialize and finalize expansions cache.

Index: gcc/cfgexpand.c
===
--- gcc/cfgexpand.c.orig	2011-06-01 19:45:02.520428653 -0300
+++ gcc/cfgexpand.c	2011-06-01 20:20:02.014975168 -0300
@@ -2337,6 +2337,70 @@ convert_debug_memory_address (enum machi
   return x;
 }
 
+/* Mark debug insns that are placeholders for replaceable SSA_NAMEs
+   that have not been expanded yet.  */
+#define DEBUG_INSN_TOEXPAND(RTX)	\
+  (RTL_FLAG_CHECK1(DEBUG_INSN_TOEXPAND, (RTX), DEBUG_INSN)-used)
+
+/* Map replaceable SSA_NAMEs versions to their RTL expansions.  */
+static rtx *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 = XCNEWVEC (rtx, num_ssa_names);
+}
+
+/* Remove the DEBUG_INSN INSN if it still binds an SSA_NAME.  */
+
+static bool
+def_expansions_remove_placeholder (rtx insn)
+{
+  gcc_checking_assert (insn);
+
+  if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == SSA_NAME)
+{
+  gcc_assert (!DEBUG_INSN_TOEXPAND (insn));
+  remove_insn (insn);
+}
+
+  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)
+{
+  int i = num_ssa_names;
+
+  gcc_checking_assert (def_expansions);
+  while (i--)
+if (def_expansions[i])
+  def_expansions_remove_placeholder (def_expansions[i]);
+  XDELETEVEC (def_expansions);
+  def_expansions = NULL;
+}
+
+/* Return a pointer to the rtx expanded from EXP.  EXP must be a
+   replaceable SSA_NAME.  */
+
+static rtx *
+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 def_expansions[SSA_NAME_VERSION (exp)];
+}
+
+static void expand_debug_insn (rtx insn);
+
 /* Return an RTX equivalent to the value of the tree expression
EXP.  */
 
@@ -3131,7 +3195,30 @@ 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));
+	rtx insn = *def_get_expansion_ptr (exp);
+	tree vexpr;
+
+	/* If this still has the original SSA_NAME, emit a debug
+	   temp and compute the RTX value.  */
+	if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == SSA_NAME)
+	  {
+		tree var = SSA_NAME_VAR (INSN_VAR_LOCATION_DECL (insn));
+
+		vexpr = make_node (DEBUG_EXPR_DECL);
+		DECL_ARTIFICIAL (vexpr) = 1;
+		TREE_TYPE (vexpr) = TREE_TYPE (var);
+		DECL_MODE (vexpr) = DECL_MODE (var);
+		INSN_VAR_LOCATION_DECL (insn) = vexpr;
+
+		gcc_checking_assert (!DEBUG_INSN_TOEXPAND (insn));
+		DEBUG_INSN_TOEXPAND (insn) = 1;
+		expand_debug_insn (insn);
+	  }
+	else
+	  vexpr = INSN_VAR_LOCATION_DECL (insn);
+
+	op0 = expand_debug_expr (vexpr);
+
 	if (!op0)
 	  return NULL;
 	  }
@@ -3293,6 +3380,45 @@ expand_debug_expr (tree exp)
 }
 }
 
+/* Expand the LOC value of the debug insn INSN.  */
+
+static void
+expand_debug_insn (rtx insn)
+{
+  tree value = (tree)INSN_VAR_LOCATION_LOC (insn);
+  rtx val;
+  enum machine_mode mode;
+
+

Re: [PR48866] three alternative fixes

2011-06-02 Thread Alexandre Oliva

On May 30, 2011, Alexandre Oliva aol...@redhat.com wrote:

 On May 30, 2011, Alexandre Oliva aol...@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.

I also posted the wrong patch upthread for this variant.  The one I
posted didn't work at all, because it contained a last-minute
optimization that changed the expansion of replaceable stmts from
EXPAND_NORMAL to EXPAND_SUM.  IIRC the former always yielded a pseudo,
whereas the former enabled replacements, but it also exposed the need
for better handling of non-general_operands when the use expects one.

This revised and retested version also drops the reordering of the
expansion of basic blocks, that Matz pointed out was unnecessary, and
switches to an array rather than a pointer_map to record the expansions.

for  gcc/ChangeLog
from  Alexandre Oliva  aol...@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-06-01 20:39:58.244953408 -0300
+++ gcc/cfgexpand.c	2011-06-01 21:44:38.005879125 -0300
@@ -2337,6 +2337,42 @@ convert_debug_memory_address (enum machi
   return x;
 }
 
+/* Map replaceable SSA_NAMEs to their RTL expansions.  */
+static rtx *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 = XCNEWVEC (rtx, num_ssa_names);
+}
+
+/* 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);
+  XDELETEVEC (def_expansions);
+  def_expansions = NULL;
+}
+
+/* Return a pointer to the rtx expanded from EXP.  EXP must be a
+   replaceable SSA_NAME.  */
+
+rtx *
+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 def_expansions[SSA_NAME_VERSION (exp)];
+}
+
 /* Return an RTX equivalent to the value of the tree expression
EXP.  */
 
@@ -3131,7 +3167,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));
+	rtx *xp = def_get_expansion_ptr (exp);
+
+	if (xp)
+	  op0 = copy_rtx (*xp);
+	else
+	  op0 = NULL;
+
+	if (!op0)
+	  op0 = expand_debug_expr (gimple_assign_rhs_to_tree (g));
+
 	if (!op0)
 	  return NULL;
 	  }
@@ -3618,20 +3663,38 @@ expand_gimple_basic_block (basic_block b
 	}
 	  else
 	{
+	  rtx *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
+

Re: [PR48866] three alternative fixes

2011-06-02 Thread Alexandre Oliva

Ugh, failed to refresh the patch file, resending with the correct one.

On May 30, 2011, Alexandre Oliva aol...@redhat.com wrote:

 On May 30, 2011, Alexandre Oliva aol...@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.

Upthread, I posted the wrong patch: instead of the one that tolerated
expanding DEFs before or after USEs, I posted a simplifying experiment
that seemed to fail, but it looks like I misinterpreted the results.

This revised and retested patch also records expansions in an array
rather than a pointer_map, and it avoids re-expanding DEFs when a USE is
expanded for the second time.  Although replaceable DEFs can only have
one USE, when the single USE appears in a call stmt, it can be expanded
twice.  I'm not sure whether it would be better to expand it twice and
let RTL optimizations drop any redundancies, or reuse the result of the
first expansion, like this patch does.

for  gcc/ChangeLog
from  Alexandre Oliva  aol...@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_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): 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-06-02 16:43:03.596818720 -0300
+++ gcc/cfgexpand.c	2011-06-02 17:18:10.217974612 -0300
@@ -2337,6 +2337,144 @@ 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 SSA_NAME DEF is expanded before
+   its single USE, so the NOTE is inserted in the insn stream, marking
+   the location where the non-replaceable portion of the expansion is
+   to be inserted.  When the single USE is expanded, it will be
+   emitted before the NOTE.  */
+static rtx *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 = XCNEWVEC (rtx, num_ssa_names);
+
+  gcc_checking_assert (!def_expansion_recent_tree);
+  gcc_checking_assert (!def_expansion_recent_rtx);
+}
+
+/* Remove the NOTE that marks the insertion location of the expansion
+   of a replaceable SSA note.  */
+
+static bool
+def_expansions_remove_placeholder (rtx note)
+{
+  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)
+{
+  int i = num_ssa_names;
+
+  gcc_checking_assert (def_expansions);
+
+  while (i--)
+if (def_expansions[i])
+  def_expansions_remove_placeholder (def_expansions[i]);
+  XDELETEVEC (def_expansions);
+  def_expansions = NULL;
+  def_expansion_recent_tree =

Re: [PR48866] three alternative fixes

2011-06-01 Thread Alexandre Oliva

On May 30, 2011, Michael Matz m...@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!

-- 
Alexandre Oliva, freedom fighterhttp://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist  Red Hat Brazil Compiler Engineer

[PR48866] three alternative fixes

2011-05-30 Thread Alexandre Oliva

I have 3 different, mutually exclusive patches that fix PR 48866.  The
problem is exponential time while dealing with an expression that
resulted from a long chain of replaceable insns with memory accesses
moved past the debug insns referring to their results.

1. emit debug temps for replaceable DEFs that end up being referenced in
debug insns.  We already have some code to try to deal with this, but it
emits the huge expressions we'd rather avoid, and it may create
unnecessary duplication.  This new approach emits a placeholder instead
of skipping replaceable DEFs altogether, and then, if the DEF is
referenced in a debug insn (perhaps during the late debug re-expasion of
some other placeholder), it is expanded.  Placeholders that end up not
being referenced are then throw away.

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.

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.

I'll post each patch with further details in separate follow-up e-mails.

-- 
Alexandre Oliva, freedom fighterhttp://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist  Red Hat Brazil Compiler Engineer

Re: [PR48866] three alternative fixes

2011-05-30 Thread Alexandre Oliva

On May 30, 2011, Alexandre Oliva aol...@redhat.com wrote:

 1. emit debug temps for replaceable DEFs that end up being referenced in
 debug insns.  We already have some code to try to deal with this, but it
 emits the huge expressions we'd rather avoid, and it may create
 unnecessary duplication.  This new approach emits a placeholder instead
 of skipping replaceable DEFs altogether, and then, if the DEF is
 referenced in a debug insn (perhaps during the late debug re-expasion of
 some other placeholder), it is expanded.  Placeholders that end up not
 being referenced are then throw away.

This is my favorite option, for it's safest: it doesn't change
executable code at all (or should I say it *shouldn't* change it, for I
haven't verified that it doesn't), retaining any register pressure
benefits from TER.

The drawbacks are higher likelihood of loss of debug information as
complex debug value expressions now require the recursive expansion of
multiple debug temps, which is now more likely to hit the recursion
limit.  E.g., for a chain of dereferences, before the patch we'd get
something like:

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

After the patch, the first two stmts would expand to:

;; x_ = y; (replaceable sequence)
(debug_insn (var_location D#3 (mem (reg ...
(debug_insn (var_location D#2 (mem D#3)))
(debug_insn (var_location D#1 (mem D#2)))
;; debug x = x_
(debug_insn (var_location x (mem D#1)))

The additional debug temps will likely come at a compile-time cost,
especially during var-tracking, but this may be at least in part
recovered because the debug temps hold values that are likely to be
computed by actual insns, so var-tracking will create value tracking
entries for them anyway.


Unlike the other patches, this alternative will *not* expand
replaceable code at its natural location, so the executable code will
remain at the point of use.  Single-stepping will therefore remain just
as confusing, and since debug bind stmts will likely remain at points
one can't stop, they may remain unusable.  The debug information
extensions I proposed at the GCC Summit last year will alleviate this
issue, but I still don't have a concrete plan for completing the
implementation of that feature, so this is something to keep in mind
if this patch is preferred.

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

for  gcc/ChangeLog
from  Alexandre Oliva  aol...@redhat.com

	PR debug/48866
	* cfgexpand.c (def_expansions): New.
	(def_expansions_init): New.
	(def_expansions_remove_placeholder, def_expansions_fini): New.
	(def_has_expansion_ptr, def_get_expansion_ptr): New.
	(expand_debug_expr): Create debug temps as needed.
	(expand_debug_insn): New, split out of...
	(expand_debug_locations): ... this.
	(gen_emit_debug_insn): New, split out of...
	(expand_gimple_basic_block): ... this.  Simplify expansion of
	debug stmts.  Emit placeholders for replaceable DEFs, rather
	than debug temps at last non-debug uses.
	(gimple_expand_cfg): Initialize and finalize expansions cache.

Index: gcc/cfgexpand.c
===
--- gcc/cfgexpand.c.orig	2011-05-28 08:40:42.0 -0300
+++ gcc/cfgexpand.c	2011-05-28 11:33:22.727418563 -0300
@@ -2337,6 +2337,84 @@ convert_debug_memory_address (enum machi
   return x;
 }
 
+/* Map replaceable SSA_NAMEs to their RTL expansions.  */
+static struct pointer_map_t *def_expansions;
+
+/* Mark debug insns that are placeholders for replaceable SSA_NAMEs
+   that have not been expanded yet.  */
+#define DEBUG_INSN_TOEXPAND(RTX)	\
+  (RTL_FLAG_CHECK1(DEBUG_INSN_TOEXPAND, (RTX), DEBUG_INSN)-used)
+
+/* 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 ();
+}
+
+/* Remove the DEBUG_INSN at **XP if it still binds an SSA_NAME.  */
+
+static bool
+def_expansions_remove_placeholder (const void *def ATTRIBUTE_UNUSED,
+   void **xp,
+   void *arg ATTRIBUTE_UNUSED)
+{
+  rtx insn = (rtx) *xp;
+
+  gcc_checking_assert (insn);
+
+  if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == SSA_NAME)
+{
+  gcc_assert (!DEBUG_INSN_TOEXPAND (insn));
+  remove_insn (insn);
+}
+
+  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);
+

Re: [PR48866] three alternative fixes

2011-05-30 Thread Alexandre Oliva

On May 30, 2011, Alexandre Oliva aol...@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.

for  gcc/ChangeLog
from  Alexandre Oliva  aol...@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 @@

Re: [PR48866] three alternative fixes

2011-05-30 Thread Michael Matz

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.

Re: [PR48866] three alternative fixes

Re: [PR48866] three alternative fixes

Re: [PR48866] three alternative fixes

Re: [PR48866] three alternative fixes

Re: [PR48866] three alternative fixes

Re: [PR48866] three alternative fixes

[PR48866] three alternative fixes

Re: [PR48866] three alternative fixes

Re: [PR48866] three alternative fixes

Re: [PR48866] three alternative fixes

10 matches

Site Navigation

Mail list logo

Footer information