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 <t...@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.
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c (revision 193497)
+++ gcc/tree-ssa-pre.c (working copy)
@@ -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;
}
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);
+ }
}
