Patchwork PR55124 - tentative patch for ICE in PRE

login
register
mail settings
Submitter Tom de Vries
Date Nov. 29, 2012, 12:14 p.m.
Message ID <50B751AD.5030504@mentor.com>
Download mbox | patch
Permalink /patch/202729/
State New
Headers show

Comments

Tom de Vries - Nov. 29, 2012, 12:14 p.m.
On 29/11/12 11:26, Richard Biener wrote:
> I'm continuing trying to move value-ids back to PRE land.  Your patch
> would be nice in a form that verifies the order is indeed topological,
> maybe you can re-work it in a way that does this in
> sorted_array_from_bitmap_set in a ENABLE_CHECKING piece?

Richard,

These are my current patches, tested together with tree-ssa.exp.


The first patch checks the topological order in sorted_array_from_bitmap_set.
Testing only this one with tree-ssa.exp gives 400 failures.

Btw, I'm not 100% sure if this patch checks the required order. It's clear what
topological order means if there is one expression per value. I've ran
tree-ssa.exp with an assert that the number of expressions and values in the
bitmap_set is equal in sorted_array_from_bitmap_set, and that passed, so that
seems to be the case generally, but I don't know if that's by design.
If there are more expressions with the same value, this patch is a 'weak' check,
meaning a value is considered available if one expression with that value is
available. A 'strong' check would consider a value available if all expressions
with that value are available. I can imagine doing clean on a strongly or weakly
ordered array could give different results.


The second patch calculates value_id during pre. If you're working on the
value_id part, I'll stop here.

Thanks,
- Tom

2012-11-29  Tom de Vries  <tom@codesourcery.com>

	* tree-ssa-pre.c (sorted_array_from_bitmap_set): Use
	EXECUTE_IF_AND_IN_BITMAP instead of EXECUTE_IF_SET_IN_BITMAP.  Check
	sort result ifdef ENABLE_CHECKING.  Check if the sorted array has the
	same number of expressions as the bitmap_set.
Richard Guenther - Nov. 29, 2012, 12:52 p.m.
On Thu, Nov 29, 2012 at 1:14 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 29/11/12 11:26, Richard Biener wrote:
>> I'm continuing trying to move value-ids back to PRE land.  Your patch
>> would be nice in a form that verifies the order is indeed topological,
>> maybe you can re-work it in a way that does this in
>> sorted_array_from_bitmap_set in a ENABLE_CHECKING piece?
>
> Richard,
>
> These are my current patches, tested together with tree-ssa.exp.
>
>
> The first patch checks the topological order in sorted_array_from_bitmap_set.
> Testing only this one with tree-ssa.exp gives 400 failures.
>
> Btw, I'm not 100% sure if this patch checks the required order. It's clear what
> topological order means if there is one expression per value. I've ran
> tree-ssa.exp with an assert that the number of expressions and values in the
> bitmap_set is equal in sorted_array_from_bitmap_set, and that passed, so that
> seems to be the case generally, but I don't know if that's by design.
> If there are more expressions with the same value, this patch is a 'weak' check,
> meaning a value is considered available if one expression with that value is
> available. A 'strong' check would consider a value available if all expressions
> with that value are available. I can imagine doing clean on a strongly or weakly
> ordered array could give different results.
>
>
> The second patch calculates value_id during pre. If you're working on the
> value_id part, I'll stop here.

Thanks.

For the moment I am fixing value-id assigns in tree-ssa-sccvn.c but there
seems to be an issue with possibly assigning the same value-ids for
conflicting topology:

  if ()
    {
      a = b + c;
      d = a + 1;
    }
  else
    {
      f = g + h;
      i = f - 1;
    }

if for some reason we value-number 'a' and 'i' the same and 'd' and 'f' the
same then there is no value-id ordering that sorts correctly according
to expression dependencies (some reason being for example
g == b + c, h = 2).  So I'm indeed not sure that simply sorting after
value-id and assigning "proper" value-ids will work at all.

patch that adjusts value-id assignment in SCCVN according to PREs
expectations attached.

Richard.

> Thanks,
> - Tom
>
> 2012-11-29  Tom de Vries  <tom@codesourcery.com>
>
>         * tree-ssa-pre.c (sorted_array_from_bitmap_set): Use
>         EXECUTE_IF_AND_IN_BITMAP instead of EXECUTE_IF_SET_IN_BITMAP.  Check
>         sort result ifdef ENABLE_CHECKING.  Check if the sorted array has the
>         same number of expressions as the bitmap_set.
>
>

Patch

Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c	(revision 193497)
+++ gcc/tree-ssa-sccvn.c	(working copy)
@@ -3967,8 +3967,8 @@ 
 
 /* Set the value ids in the valid hash tables.  */
 
-static void
-set_hashtable_value_ids (void)
+void
+vn_set_hashtable_value_ids (void)
 {
   htab_iterator hi;
   vn_nary_op_t vno;
@@ -4000,7 +4000,6 @@ 
 {
   size_t i;
   tree param;
-  bool changed = true;
 
   default_vn_walk_kind = default_vn_walk_kind_;
 
@@ -4029,45 +4028,6 @@ 
 	  }
     }
 
-  /* Initialize the value ids.  */
-
-  for (i = 1; i < num_ssa_names; ++i)
-    {
-      tree name = ssa_name (i);
-      vn_ssa_aux_t info;
-      if (!name)
-	continue;
-      info = VN_INFO (name);
-      if (info->valnum == name
-	  || info->valnum == VN_TOP)
-	info->value_id = get_next_value_id ();
-      else if (is_gimple_min_invariant (info->valnum))
-	info->value_id = get_or_alloc_constant_value_id (info->valnum);
-    }
-
-  /* Propagate until they stop changing.  */
-  while (changed)
-    {
-      changed = false;
-      for (i = 1; i < num_ssa_names; ++i)
-	{
-	  tree name = ssa_name (i);
-	  vn_ssa_aux_t info;
-	  if (!name)
-	    continue;
-	  info = VN_INFO (name);
-	  if (TREE_CODE (info->valnum) == SSA_NAME
-	      && info->valnum != name
-	      && info->value_id != VN_INFO (info->valnum)->value_id)
-	    {
-	      changed = true;
-	      info->value_id = VN_INFO (info->valnum)->value_id;
-	    }
-	}
-    }
-
-  set_hashtable_value_ids ();
-
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "Value numbers:\n");
Index: gcc/tree-ssa-sccvn.h
===================================================================
--- gcc/tree-ssa-sccvn.h	(revision 193497)
+++ gcc/tree-ssa-sccvn.h	(working copy)
@@ -184,6 +184,7 @@ 
 extern vn_ssa_aux_t VN_INFO_GET (tree);
 tree vn_get_expr_for (tree);
 bool run_scc_vn (vn_lookup_kind);
+void vn_set_hashtable_value_ids (void);
 void free_scc_vn (void);
 tree vn_nary_op_lookup (tree, vn_nary_op_t *);
 tree vn_nary_op_lookup_stmt (gimple, vn_nary_op_t *);
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c	(revision 193497)
+++ gcc/tree-ssa-pre.c	(working copy)
@@ -573,7 +573,61 @@ 
   *slot = new_pair;
 }
 
+/* Assign a value_id to OP, if it needs one.  */
 
+static void
+assign_value_id (tree op)
+{
+  tree valnum;
+
+  if (TREE_CODE (op) != SSA_NAME
+      || VN_INFO (op)->value_id != 0)
+    return;
+
+  valnum = VN_INFO (op)->valnum;
+  /* Check if op is unkown.  */
+  if (valnum == VN_TOP)
+    return;
+
+  /* Handle case that op is a constant.  */
+  if (TREE_CODE (valnum) != SSA_NAME)
+    {
+      VN_INFO (op)->value_id = get_or_alloc_constant_value_id (valnum);
+      return;
+    }
+
+  if (VN_INFO (valnum)->value_id != 0)
+    /* Copy the value_id from the valuation.  */
+    VN_INFO (op)->value_id = VN_INFO (valnum)->value_id;
+  else
+    {
+      /* Op has no value_id, and it's valuation has no value_id.  Allocate
+	 one.  */
+      VN_INFO (op)->value_id = get_next_value_id ();
+
+      /* If necessary, copy new value_id to the valuation.  */
+      if (valnum != op)
+	{
+	  VN_INFO (valnum)->value_id = VN_INFO (op)->value_id;
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "assigned value id %u to ssa_name ",
+		       VN_INFO (op)->value_id);
+	      print_generic_expr (dump_file, valnum, 0);
+	      fprintf (dump_file, "\n");
+	    }
+	}
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "assigned value id %u to ssa_name ",
+	       VN_INFO (op)->value_id);
+      print_generic_expr (dump_file, op, 0);
+      fprintf (dump_file, "\n");
+    }
+}
+
 /* Add expression E to the expression set of value id V.  */
 
 static void
@@ -614,6 +668,8 @@ 
 static unsigned int
 get_expr_value_id (pre_expr expr)
 {
+  unsigned int value_id;
+
   switch (expr->kind)
     {
     case CONSTANT:
@@ -628,14 +684,21 @@ 
 	return id;
       }
     case NAME:
-      return VN_INFO (PRE_EXPR_NAME (expr))->value_id;
+      value_id = VN_INFO (PRE_EXPR_NAME (expr))->value_id;
+      gcc_assert (value_id != 0 ||
+		  VN_INFO (PRE_EXPR_NAME (expr))->valnum == VN_TOP);
+      return value_id;
     case NARY:
-      return PRE_EXPR_NARY (expr)->value_id;
+      value_id = PRE_EXPR_NARY (expr)->value_id;
+      break;
     case REFERENCE:
-      return PRE_EXPR_REFERENCE (expr)->value_id;
+      value_id = PRE_EXPR_REFERENCE (expr)->value_id;
+      break;
     default:
       gcc_unreachable ();
     }
+  gcc_assert (value_id != 0);
+  return value_id;
 }
 
 /* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL.  */
@@ -718,6 +781,9 @@ 
   unsigned int i, j;
   bitmap_iterator bi, bj;
   VEC(pre_expr, heap) *result;
+#ifdef ENABLE_CHECKING
+  bitmap values_done = BITMAP_ALLOC (NULL);
+#endif
 
   /* Pre-allocate roughly enough space for the array.  */
   result = VEC_alloc (pre_expr, heap, bitmap_count_bits (&set->values));
@@ -735,13 +801,70 @@ 
 	 If this is somehow a significant lose for some cases, we can
 	 choose which set to walk based on the set size.  */
       bitmap exprset = VEC_index (bitmap, value_expressions, i);
-      EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bj)
+      EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, j, bj)
 	{
-	  if (bitmap_bit_p (&set->expressions, j))
-	    VEC_safe_push (pre_expr, heap, result, expression_for_id (j));
-        }
+	  pre_expr expr = expression_for_id (j);
+	  VEC_safe_push (pre_expr, heap, result, expr);
+
+#ifdef ENABLE_CHECKING
+	  switch (expr->kind)
+	    {
+	    case NARY:
+	      {
+		vn_nary_op_t nary = PRE_EXPR_NARY (expr);
+		unsigned int k;
+		for (k = 0; k < nary->length; k++)
+		  {
+		    tree op = nary->op[k];
+		    if (TREE_CODE (op) != SSA_NAME)
+		      continue;
+		    unsigned int v = VN_INFO (op)->value_id;
+		    if (!bitmap_bit_p (values_done, v)
+			&& bitmap_bit_p (&set->values, v))
+		      gcc_unreachable ();
+		  }
+	      }
+	      break;
+
+	    case REFERENCE:
+	      {
+		vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
+		vn_reference_op_t vro;
+
+		unsigned int k;
+		FOR_EACH_VEC_ELT (vn_reference_op_s, ref->operands, k, vro)
+		  {
+		    tree ops[3] = { vro->op0, vro->op1, vro->op2};
+		    unsigned int l;
+		    for (l = 0; l < 3; l++)
+		      {
+			tree op = ops[l];
+			if (op == NULL_TREE
+			    || TREE_CODE (op) != SSA_NAME)
+			  continue;
+			unsigned int v = VN_INFO (op)->value_id;
+			if (!bitmap_bit_p (values_done, v)
+			    && bitmap_bit_p (&set->values, v))
+			  gcc_unreachable ();
+		      }
+		  }
+	      }
+	      break;
+
+	    default:
+	      break;
+	    }
+
+	  bitmap_set_bit (values_done, get_expr_value_id (expr));
+#endif
+	}
     }
 
+  gcc_assert (bitmap_count_bits (&set->expressions)
+	      == VEC_length (pre_expr, result));
+#ifdef ENABLE_CHECKING
+  BITMAP_FREE (values_done);
+#endif
   return result;
 }
 
@@ -1526,6 +1649,12 @@ 
 		  return constant;
 		get_or_alloc_expression_id (expr);
 	      }
+	    if (dump_file && (dump_flags & TDF_DETAILS))
+	      {
+		fprintf (dump_file, "assigned value id %u to pre_expr ", new_val_id);
+		print_pre_expr (dump_file, expr);
+		fprintf (dump_file, " with id %u\n", expr->id);
+	      }
 	    add_to_value (new_val_id, expr);
 	  }
 	return expr;
@@ -1726,6 +1855,12 @@ 
 		  return constant;
 		get_or_alloc_expression_id (expr);
 	      }
+	    if (dump_file && (dump_flags & TDF_DETAILS))
+	      {
+		fprintf (dump_file, "assigned value id %u to pre_expr ", new_val_id);
+		print_pre_expr (dump_file, expr);
+		fprintf (dump_file, " with id %u\n", expr->id);
+	      }
 	    add_to_value (new_val_id, expr);
 	  }
 	VEC_free (vn_reference_op_s, heap, newoperands);
@@ -2932,6 +3067,14 @@ 
 	      VN_INFO_GET (forcedname)->valnum = forcedname;
 	      VN_INFO (forcedname)->value_id = get_next_value_id ();
 	      nameexpr = get_or_alloc_expr_for_name (forcedname);
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "assigned value id %u to pre_expr ",
+			   VN_INFO (forcedname)->value_id);
+		  print_pre_expr (dump_file, nameexpr);
+		  fprintf (dump_file, " with id %u\n", nameexpr->id);
+		}
+
 	      add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
 	      bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
 	      bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
@@ -3657,26 +3800,17 @@ 
 make_values_for_phi (gimple phi, basic_block block)
 {
   tree result = gimple_phi_result (phi);
-  unsigned i;
 
   /* We have no need for virtual phis, as they don't represent
      actual computations.  */
   if (virtual_operand_p (result))
     return;
 
+  assign_value_id (result);
   pre_expr e = get_or_alloc_expr_for_name (result);
   add_to_value (get_expr_value_id (e), e);
   bitmap_value_insert_into_set (AVAIL_OUT (block), e);
   bitmap_insert_into_set (PHI_GEN (block), e);
-  for (i = 0; i < gimple_phi_num_args (phi); ++i)
-    {
-      tree arg = gimple_phi_arg_def (phi, i);
-      if (TREE_CODE (arg) == SSA_NAME)
-	{
-	  e = get_or_alloc_expr_for_name (arg);
-	  add_to_value (get_expr_value_id (e), e);
-	}
-    }
 }
 
 /* Compute the AVAIL set for all basic blocks.
@@ -3710,6 +3844,7 @@ 
 	  || virtual_operand_p (name))
 	continue;
 
+      assign_value_id (name);
       e = get_or_alloc_expr_for_name (name);
       add_to_value (get_expr_value_id (e), e);
       bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
@@ -3775,8 +3910,8 @@ 
 
 	  FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
 	    {
+	      assign_value_id (op);
 	      pre_expr e = get_or_alloc_expr_for_name (op);
-
 	      add_to_value (get_expr_value_id (e), e);
 	      bitmap_insert_into_set (TMP_GEN (block), e);
 	      bitmap_value_insert_into_set (AVAIL_OUT (block), e);
@@ -3800,6 +3935,7 @@ 
 		vn_reference_t ref;
 		pre_expr result = NULL;
 		VEC(vn_reference_op_s, heap) *ops = NULL;
+		bool assigned_value_id = false;
 
 		/* We can value number only calls to real functions.  */
 		if (gimple_call_internal_p (stmt))
@@ -3826,10 +3962,24 @@ 
 		    result->kind = REFERENCE;
 		    result->id = 0;
 		    PRE_EXPR_REFERENCE (result) = ref;
+		    if (ref->value_id == 0)
+		      {
+			assign_value_id (ref->result);
+			ref->value_id = VN_INFO (ref->result)->value_id;
+			assigned_value_id = true;
+		      }
 
 		    get_or_alloc_expression_id (result);
 		    add_to_value (get_expr_value_id (result), result);
 		    bitmap_value_insert_into_set (EXP_GEN (block), result);
+		    if (assigned_value_id
+			&& dump_file && (dump_flags & TDF_DETAILS))
+		      {
+			fprintf (dump_file, "assigned value id %u to pre_expr ",
+				 get_expr_value_id (result));
+			print_pre_expr (dump_file, result);
+			fprintf (dump_file, " with id %u\n", result->id);
+		      }
 		  }
 		continue;
 	      }
@@ -3837,6 +3987,7 @@ 
 	    case GIMPLE_ASSIGN:
 	      {
 		pre_expr result = NULL;
+		bool assigned_value_id = false;
 		switch (vn_get_stmt_kind (stmt))
 		  {
 		  case VN_NARY:
@@ -3866,6 +4017,12 @@ 
 		      result->kind = NARY;
 		      result->id = 0;
 		      PRE_EXPR_NARY (result) = nary;
+		      if (nary->value_id == 0)
+			{
+			  assign_value_id (nary->result);
+			  nary->value_id = VN_INFO (nary->result)->value_id;
+			  assigned_value_id = true;
+			}
 		      break;
 		    }
 
@@ -3907,6 +4064,12 @@ 
 		      result->kind = REFERENCE;
 		      result->id = 0;
 		      PRE_EXPR_REFERENCE (result) = ref;
+		      if (ref->value_id == 0)
+			{
+			  assign_value_id (ref->result);
+			  ref->value_id = VN_INFO (ref->result)->value_id;
+			  assigned_value_id = true;
+			}
 		      break;
 		    }
 
@@ -3915,6 +4078,14 @@ 
 		  }
 
 		get_or_alloc_expression_id (result);
+		if (assigned_value_id
+		    && dump_file && (dump_flags & TDF_DETAILS))
+		  {
+		    fprintf (dump_file, "assigned value id %u to pre_expr ",
+			     get_expr_value_id (result));
+		    print_pre_expr (dump_file, result);
+		    fprintf (dump_file, " with id %u\n", result->id);
+		  }
 		add_to_value (get_expr_value_id (result), result);
 		bitmap_value_insert_into_set (EXP_GEN (block), result);
 		continue;
@@ -3933,6 +4104,30 @@ 
     }
 
   free (worklist);
+
+  /* Propagate value-ids until they stop changing.  */
+  bool changed = true;
+  while (changed)
+    {
+      changed = false;
+      for (i = 1; i < num_ssa_names; ++i)
+	{
+	  tree name = ssa_name (i);
+	  vn_ssa_aux_t info;
+	  if (!name)
+	    continue;
+	  info = VN_INFO (name);
+	  if (TREE_CODE (info->valnum) == SSA_NAME
+	      && info->valnum != name
+	      && info->value_id != VN_INFO (info->valnum)->value_id)
+	    {
+	      changed = true;
+	      info->value_id = VN_INFO (info->valnum)->value_id;
+	    }
+	}
+    }
+
+  vn_set_hashtable_value_ids ();
 }
 
 
@@ -4589,6 +4784,17 @@ 
 	}
     }
   BITMAP_FREE (worklist);
+
+  /* Release SSA names we just created to have leaders in
+     get_representative_for but never ended up using.  */
+  for (i = 0; i < num_ssa_names; ++i)
+    {
+      tree name = ssa_name (i);
+      if (name
+	  && !SSA_NAME_IS_DEFAULT_DEF (name)
+	  && gimple_nop_p (SSA_NAME_DEF_STMT (name)))
+	release_ssa_name (name);
+    }
 }