#include "langhooks.h"
#include "cfgloop.h"
#include "tree-ssa-sccvn.h"
-#include "pointer-set.h"
/* TODO:
useful only for debugging, since we don't do identity lookups. */
-/* Mapping from decl's to value handles, by pointer equality. We
- "unshare" decls so we can give the same decl in different places
- different value handles. */
-struct pointer_map_t *decl_vh_map;
-
-/* Mapping from expressions to ids. */
-struct pointer_map_t *expression_id_map;
-
/* Next global expression id number. */
static unsigned int next_expression_id;
+typedef VEC(tree, gc) *vuse_vec;
+DEF_VEC_P (vuse_vec);
+DEF_VEC_ALLOC_P (vuse_vec, heap);
+
+static VEC(vuse_vec, heap) *expression_vuses;
+
/* Mapping from expression to id number we can use in bitmap sets. */
static VEC(tree, heap) *expressions;
static inline unsigned int
alloc_expression_id (tree expr)
{
- unsigned int *slot;
+ tree_ann_common_t ann;
+
+ ann = get_tree_common_ann (expr);
- slot = (unsigned int *) pointer_map_insert (expression_id_map,
- expr);
/* Make sure we won't overflow. */
gcc_assert (next_expression_id + 1 > next_expression_id);
- *slot = next_expression_id++;
+ ann->aux = XNEW (unsigned int);
+ * ((unsigned int *)ann->aux) = next_expression_id++;
VEC_safe_push (tree, heap, expressions, expr);
+ VEC_safe_push (vuse_vec, heap, expression_vuses, NULL);
return next_expression_id - 1;
}
static inline unsigned int
get_expression_id (tree expr)
{
- unsigned int *slot;
- slot = (unsigned int *) pointer_map_contains (expression_id_map,
- expr);
- return *slot;
+ tree_ann_common_t ann = tree_common_ann (expr);
+ gcc_assert (ann);
+ gcc_assert (ann->aux);
+
+ return *((unsigned int *)ann->aux);
}
/* Return the existing expression id for EXPR, or create one if one
static inline unsigned int
get_or_alloc_expression_id (tree expr)
{
- unsigned int *slot;
- slot = (unsigned int *) pointer_map_contains (expression_id_map,
- expr);
- if (slot)
- return *slot;
- else
+ tree_ann_common_t ann = tree_common_ann (expr);
+
+ if (ann == NULL || !ann->aux)
return alloc_expression_id (expr);
+
+ return get_expression_id (expr);
}
/* Return the expression that has expression id ID */
return VEC_index (tree, expressions, id);
}
+/* Return the expression vuses for EXPR, if there are any. */
+
+static inline vuse_vec
+get_expression_vuses (tree expr)
+{
+ unsigned int expr_id = get_or_alloc_expression_id (expr);
+ return VEC_index (vuse_vec, expression_vuses, expr_id);
+}
+
+/* Set the expression vuses for EXPR to VUSES. */
+
+static inline void
+set_expression_vuses (tree expr, vuse_vec vuses)
+{
+ unsigned int expr_id = get_or_alloc_expression_id (expr);
+ VEC_replace (vuse_vec, expression_vuses, expr_id, vuses);
+}
+
+
+/* Free the expression id field in all of our expressions,
+ and then destroy the expressions array. */
+
+static void
+clear_expression_ids (void)
+{
+ int i;
+ tree expr;
+
+ for (i = 0; VEC_iterate (tree, expressions, i, expr); i++)
+ {
+ free (tree_common_ann (expr)->aux);
+ tree_common_ann (expr)->aux = NULL;
+ }
+ VEC_free (tree, heap, expressions);
+ VEC_free (vuse_vec, heap, expression_vuses);
+}
+
static bool in_fre = false;
/* An unordered bitmap set. One bitmap tracks values, the other,
static alloc_pool reference_node_pool;
static alloc_pool comparison_node_pool;
static alloc_pool modify_expr_node_pool;
-static alloc_pool decl_node_pool;
static bitmap_obstack grand_bitmap_obstack;
/* We can't use allocation pools to hold temporary CALL_EXPR objects, since
return expr;
/* Phi translations of a given expression don't change. */
- if (EXPR_P (expr) || GIMPLE_STMT_P (expr) || REFERENCE_CLASS_P (expr)
- || DECL_P (expr))
+ if (EXPR_P (expr) || GIMPLE_STMT_P (expr))
{
- tree vh;
-
- vh = get_value_handle (expr);
- if (vh && TREE_CODE (vh) == VALUE_HANDLE)
- phitrans = phi_trans_lookup (expr, pred, VALUE_HANDLE_VUSES (vh));
- else
- phitrans = phi_trans_lookup (expr, pred, NULL);
+ phitrans = phi_trans_lookup (expr, pred, get_expression_vuses (expr));
}
else
phitrans = phi_trans_lookup (expr, pred, NULL);
tree oldsc = CALL_EXPR_STATIC_CHAIN (expr);
tree newfn, newsc = NULL;
tree newexpr = NULL_TREE;
- tree vh = get_value_handle (expr);
bool invariantarg = false;
int i, nargs;
- VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
+ VEC (tree, gc) *vuses = get_expression_vuses (expr);
VEC (tree, gc) *tvuses;
newfn = phi_translate_1 (find_leader_in_sets (oldfn, set1, set2),
newexpr->base.ann = NULL;
vn_lookup_or_add_with_vuses (newexpr, tvuses);
expr = newexpr;
+ set_expression_vuses (newexpr, tvuses);
}
phi_trans_add (oldexpr, expr, pred, tvuses);
}
VEC (tree, gc) * oldvuses = NULL;
VEC (tree, gc) * newvuses = NULL;
- oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
+ oldvuses = get_expression_vuses (expr);
if (oldvuses)
newvuses = translate_vuses_through_block (oldvuses, phiblock,
pred);
if (oldvuses != newvuses)
{
- tree newexpr = (tree) pool_alloc (decl_node_pool);
- memcpy (newexpr, expr, tree_size (expr));
- vn_lookup_or_add_with_vuses (newexpr, newvuses);
- expr = newexpr;
- phi_trans_add (expr, expr, pred, newvuses);
+ vn_lookup_or_add_with_vuses (expr, newvuses);
+ set_expression_vuses (expr, newvuses);
}
-
phi_trans_add (oldexpr, expr, pred, newvuses);
}
return expr;
}
}
- oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
+ oldvuses = get_expression_vuses (expr);
if (oldvuses)
newvuses = translate_vuses_through_block (oldvuses, phiblock,
pred);
{
newexpr->base.ann = NULL;
vn_lookup_or_add_with_vuses (newexpr, newvuses);
+ set_expression_vuses (newexpr, newvuses);
}
expr = newexpr;
}
we won't look them up that way, or use the result, anyway. */
if (translated && !is_gimple_min_invariant (translated))
{
- tree vh = get_value_handle (translated);
- VEC (tree, gc) *vuses;
-
- /* The value handle itself may also be an invariant, in
- which case, it has no vuses. */
- vuses = !is_gimple_min_invariant (vh)
- ? VALUE_HANDLE_VUSES (vh) : NULL;
- phi_trans_add (expr, translated, pred, vuses);
+ phi_trans_add (expr, translated, pred,
+ get_expression_vuses (translated));
}
if (translated != NULL)
return NULL;
}
-/* Determine if VALUE, a memory operation, is ANTIC_IN at the top of
+/* Determine if EXPR, a memory expressionn, is ANTIC_IN at the top of
BLOCK by seeing if it is not killed in the block. Note that we are
only determining whether there is a store that kills it. Because
of the order in which clean iterates over values, we are guaranteed
ANTIC_IN set already. */
static bool
-value_dies_in_block_x (tree vh, basic_block block)
+value_dies_in_block_x (tree expr, basic_block block)
{
int i;
tree vuse;
- VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
+ VEC (tree, gc) *vuses = get_expression_vuses (expr);
/* Conservatively, a value dies if it's vuses are defined in this
block, unless they come from phi nodes (which are merge operations,
valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree expr,
basic_block block)
{
- tree vh = get_value_handle (expr);
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
case tcc_binary:
if (!union_contains_value (set1, set2, arg))
return false;
}
- return !value_dies_in_block_x (vh, block);
+ return !value_dies_in_block_x (expr, block);
}
return false;
}
&& !union_contains_value (set1, set2, op3))
return false;
}
- return !value_dies_in_block_x (vh, block);
+ return !value_dies_in_block_x (expr, block);
}
}
return false;
}
case tcc_declaration:
- return !value_dies_in_block_x (vh, block);
+ return !value_dies_in_block_x (expr, block);
default:
/* No other cases should be encountered. */
|| BINARY_CLASS_P (op)
|| COMPARISON_CLASS_P (op)
|| REFERENCE_CLASS_P (op)
- || DECL_P (op)
|| (TREE_CODE (op) == CALL_EXPR
&& can_value_number_call (op));
}
return UNARY_CLASS_P (op)
|| BINARY_CLASS_P (op)
|| COMPARISON_CLASS_P (op)
- || DECL_P (op)
|| TREE_CODE (op) == INDIRECT_REF
|| TREE_CODE (op) == COMPONENT_REF
|| TREE_CODE (op) == CALL_EXPR
genop1, genop2);
break;
}
- case tcc_declaration:
- {
- /* Get the "shared" version of the DECL, that we didn't create
- using a pool. */
- folded = referenced_var_lookup (DECL_UID (expr));
- }
- break;
-
+
case tcc_unary:
{
tree op1 = TREE_OPERAND (expr, 0);
any). */
static inline void
-add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1,
+add_to_sets (tree var, tree expr, VEC(tree, gc) *vuses, bitmap_set_t s1,
bitmap_set_t s2)
{
tree val;
- val = vn_lookup_or_add_with_stmt (expr, stmt);
+ val = vn_lookup_or_add_with_vuses (expr, vuses);
/* VAR and EXPR may be the same when processing statements for which
we are not computing value numbers (e.g., non-assignments, or
and return it if it exists. */
static inline tree
-find_existing_value_expr (tree t, tree stmt)
+find_existing_value_expr (tree t, VEC (tree, gc) *vuses)
{
bitmap_iterator bi;
unsigned int bii;
bitmap_set_t exprset;
if (REFERENCE_CLASS_P (t) || TREE_CODE (t) == CALL_EXPR || DECL_P (t))
- vh = vn_lookup_with_stmt (t, stmt);
+ vh = vn_lookup_with_vuses (t, vuses);
else
vh = vn_lookup (t);
replaced with the value handles of each of the operands of EXPR.
VUSES represent the virtual use operands associated with EXPR (if
- any). Insert EXPR's operands into the EXP_GEN set for BLOCK.
-
- TOP_LEVEL is true if we are at the top of the original
- expression. This is used to differentiate between addressing and
- actual loads of globals. IE a = t vs a = t[0]. */
+ any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
static inline tree
-create_value_expr_from (tree expr, basic_block block, tree stmt,
- bool top_level)
+create_value_expr_from (tree expr, basic_block block, VEC (tree, gc) *vuses)
{
int i;
enum tree_code code = TREE_CODE (expr);
pool = binary_node_pool;
else if (TREE_CODE_CLASS (code) == tcc_comparison)
pool = comparison_node_pool;
- else if (TREE_CODE_CLASS (code) == tcc_declaration)
- pool = decl_node_pool;
else
gcc_assert (code == CALL_EXPR);
vexpr = (tree) pool_alloc (pool);
memcpy (vexpr, expr, tree_size (expr));
}
-
+
for (i = 0; i < TREE_OPERAND_LENGTH (expr); i++)
{
tree val = NULL_TREE;
tree op;
-
- if (i != 0)
- top_level = false;
-
+
op = TREE_OPERAND (expr, i);
if (op == NULL_TREE)
continue;
/* Recursively value-numberize reference ops and tree lists. */
if (REFERENCE_CLASS_P (op))
{
- tree tempop = create_value_expr_from (op, block, stmt, false);
+ tree tempop = create_value_expr_from (op, block, vuses);
op = tempop ? tempop : op;
- val = vn_lookup_or_add_with_stmt (op, stmt);
+ val = vn_lookup_or_add_with_vuses (op, vuses);
+ set_expression_vuses (op, vuses);
}
else
{
TREE_OPERAND (vexpr, i) = val;
}
- efi = find_existing_value_expr (vexpr, stmt);
+ efi = find_existing_value_expr (vexpr, vuses);
if (efi)
return efi;
get_or_alloc_expression_id (vexpr);
return temp;
}
break;
- case PARM_DECL:
- case RESULT_DECL:
- case VAR_DECL:
- case CONST_DECL:
- case FUNCTION_DECL:
case SSA_NAME:
case INTEGER_CST:
case STRING_CST:
case REAL_CST:
+ case PARM_DECL:
+ case VAR_DECL:
+ case RESULT_DECL:
return node;
default:
gcc_unreachable ();
if (sccvnval)
{
vn_add (result, sccvnval);
- if (!in_fre)
- bitmap_insert_into_set (PHI_GEN (block), result);
+ bitmap_insert_into_set (PHI_GEN (block), result);
bitmap_value_insert_into_set (AVAIL_OUT (block), result);
}
else
}
}
-/* Return true if both the statement and the value handles have no
- vuses, or both the statement and the value handle do have vuses.
-
- Unlike SCCVN, PRE needs not only to know equivalence, but what the
- actual vuses are so it can translate them through blocks. Thus,
- we have to make a new value handle if the existing one has no
- vuses but needs them. */
-
-static bool
-vuse_equiv (tree vh1, tree stmt)
-{
- bool stmt_has_vuses = !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES);
- return (VALUE_HANDLE_VUSES (vh1) && stmt_has_vuses)
- || (!VALUE_HANDLE_VUSES (vh1) && !stmt_has_vuses);
-}
-
/* Create value handles for STMT in BLOCK. Return true if we handled
the statement. */
tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
tree valvh = NULL_TREE;
tree lhsval;
+ VEC (tree, gc) *vuses = NULL;
valvh = get_sccvn_value (lhs);
+
if (valvh)
{
vn_add (lhs, valvh);
}
lhsval = valvh ? valvh : get_value_handle (lhs);
-
+ vuses = copy_vuses_from_stmt (stmt);
STRIP_USELESS_TYPE_CONVERSION (rhs);
if (can_value_number_operation (rhs)
&& (!lhsval || !is_gimple_min_invariant (lhsval)))
/* For value numberable operation, create a
duplicate expression with the operands replaced
with the value handles of the original RHS. */
- tree newt = create_value_expr_from (rhs, block, stmt, true);
+ tree newt = create_value_expr_from (rhs, block, vuses);
if (newt)
{
+ set_expression_vuses (newt, vuses);
/* If we already have a value number for the LHS, reuse
it rather than creating a new one. */
- if (lhsval && vuse_equiv (lhsval, stmt))
+ if (lhsval)
{
set_value_handle (newt, lhsval);
if (!is_gimple_min_invariant (lhsval))
}
else
{
- tree val = vn_lookup_or_add_with_stmt (newt, stmt);
+ tree val = vn_lookup_or_add_with_vuses (newt, vuses);
vn_add (lhs, val);
}
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
|| is_gimple_min_invariant (rhs)
|| TREE_CODE (rhs) == ADDR_EXPR
- || TREE_INVARIANT (rhs))
+ || TREE_INVARIANT (rhs)
+ || DECL_P (rhs))
{
if (lhsval)
{
+ set_expression_vuses (rhs, vuses);
set_value_handle (rhs, lhsval);
if (!is_gimple_min_invariant (lhsval))
add_to_value (lhsval, rhs);
/* Compute a value number for the RHS of the statement
and add its value to the AVAIL_OUT set for the block.
Add the LHS to TMP_GEN. */
- add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
+ set_expression_vuses (rhs, vuses);
+ add_to_sets (lhs, rhs, vuses, TMP_GEN (block),
AVAIL_OUT (block));
}
/* None of the rest of these can be PRE'd. */
init_pre (bool do_fre)
{
basic_block bb;
- unsigned int max_decl_size;
-
+
next_expression_id = 0;
expressions = NULL;
+ expression_vuses = NULL;
in_fre = do_fre;
inserted_exprs = NULL;
storetemp = NULL_TREE;
prephitemp = NULL_TREE;
- memset (&pre_stats, 0, sizeof (pre_stats));
- bitmap_obstack_initialize (&grand_bitmap_obstack);
-
if (!do_fre)
- {
- loop_optimizer_init (LOOPS_NORMAL);
- connect_infinite_loops_to_exit ();
- postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
- post_order_compute (postorder, false, false);
- calculate_dominance_info (CDI_POST_DOMINATORS);
- phi_translate_table = htab_create (5110, expr_pred_trans_hash,
- expr_pred_trans_eq, free);
- seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
- binary_node_pool = create_alloc_pool ("Binary tree nodes",
- tree_code_size (PLUS_EXPR), 30);
- unary_node_pool = create_alloc_pool ("Unary tree nodes",
- tree_code_size (NEGATE_EXPR), 30);
- reference_node_pool = create_alloc_pool ("Reference tree nodes",
- tree_code_size (ARRAY_REF), 30);
- comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
- tree_code_size (EQ_EXPR), 30);
- modify_expr_node_pool = create_alloc_pool ("GIMPLE_MODIFY_STMT nodes",
- tree_code_size (GIMPLE_MODIFY_STMT),
- 30);
- max_decl_size = MAX (tree_code_size (VAR_DECL), tree_code_size (PARM_DECL));
- max_decl_size = MAX (max_decl_size, tree_code_size (RESULT_DECL));
- max_decl_size = MAX (max_decl_size, tree_code_size (CONST_DECL));
- max_decl_size = MAX (max_decl_size, tree_code_size (FUNCTION_DECL));
- decl_node_pool = create_alloc_pool ("_DECL nodes", max_decl_size, 30);
-
- obstack_init (&temp_call_expr_obstack);
- modify_expr_template = NULL;
- }
-
+ loop_optimizer_init (LOOPS_NORMAL);
+
+ connect_infinite_loops_to_exit ();
+ memset (&pre_stats, 0, sizeof (pre_stats));
+
+
+ postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
+ post_order_compute (postorder, false, false);
+
FOR_ALL_BB (bb)
bb->aux = xcalloc (1, sizeof (struct bb_bitmap_sets));
+ calculate_dominance_info (CDI_POST_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
+ bitmap_obstack_initialize (&grand_bitmap_obstack);
+ phi_translate_table = htab_create (5110, expr_pred_trans_hash,
+ expr_pred_trans_eq, free);
+ seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
bitmap_set_pool = create_alloc_pool ("Bitmap sets",
sizeof (struct bitmap_set), 30);
+ binary_node_pool = create_alloc_pool ("Binary tree nodes",
+ tree_code_size (PLUS_EXPR), 30);
+ unary_node_pool = create_alloc_pool ("Unary tree nodes",
+ tree_code_size (NEGATE_EXPR), 30);
+ reference_node_pool = create_alloc_pool ("Reference tree nodes",
+ tree_code_size (ARRAY_REF), 30);
+ comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
+ tree_code_size (EQ_EXPR), 30);
+ modify_expr_node_pool = create_alloc_pool ("GIMPLE_MODIFY_STMT nodes",
+ tree_code_size (GIMPLE_MODIFY_STMT),
+ 30);
+ obstack_init (&temp_call_expr_obstack);
+ modify_expr_template = NULL;
FOR_ALL_BB (bb)
{
- if (!do_fre)
- {
- EXP_GEN (bb) = bitmap_set_new ();
- PHI_GEN (bb) = bitmap_set_new ();
- TMP_GEN (bb) = bitmap_set_new ();
- }
+ EXP_GEN (bb) = bitmap_set_new ();
+ PHI_GEN (bb) = bitmap_set_new ();
+ TMP_GEN (bb) = bitmap_set_new ();
AVAIL_OUT (bb) = bitmap_set_new ();
}
- maximal_set = do_fre ? NULL : bitmap_set_new ();
+ maximal_set = in_fre ? NULL : bitmap_set_new ();
need_eh_cleanup = BITMAP_ALLOC (NULL);
- decl_vh_map = pointer_map_create ();
- expression_id_map = pointer_map_create ();
}
{
basic_block bb;
unsigned int i;
-
- if (!in_fre)
- {
- free (postorder);
- VEC_free (tree, heap, inserted_exprs);
- VEC_free (tree, heap, need_creation);
- free_alloc_pool (binary_node_pool);
- free_alloc_pool (reference_node_pool);
- free_alloc_pool (unary_node_pool);
- free_alloc_pool (comparison_node_pool);
- free_alloc_pool (modify_expr_node_pool);
- free_alloc_pool (decl_node_pool);
- htab_delete (phi_translate_table);
- remove_fake_exit_edges ();
- free_dominance_info (CDI_POST_DOMINATORS);
- }
+
+ free (postorder);
+ VEC_free (tree, heap, inserted_exprs);
+ VEC_free (tree, heap, need_creation);
bitmap_obstack_release (&grand_bitmap_obstack);
free_alloc_pool (bitmap_set_pool);
+ free_alloc_pool (binary_node_pool);
+ free_alloc_pool (reference_node_pool);
+ free_alloc_pool (unary_node_pool);
+ free_alloc_pool (comparison_node_pool);
+ free_alloc_pool (modify_expr_node_pool);
+ htab_delete (phi_translate_table);
+ remove_fake_exit_edges ();
FOR_ALL_BB (bb)
{
bb->aux = NULL;
}
+ free_dominance_info (CDI_POST_DOMINATORS);
+
if (!bitmap_empty_p (need_eh_cleanup))
{
tree_purge_all_dead_eh_edges (need_eh_cleanup);
}
BITMAP_FREE (need_eh_cleanup);
- pointer_map_destroy (decl_vh_map);
- pointer_map_destroy (expression_id_map);
-
+
/* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
future we will want them to be persistent though. */
for (i = 0; i < num_ssa_names; i++)
&& TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
SSA_NAME_VALUE (name) = NULL;
}
- if (current_loops != NULL && !in_fre)
+ if (current_loops != NULL)
loop_optimizer_finalize ();
}
bsi_commit_edge_inserts ();
free_scc_vn ();
+ clear_expression_ids ();
if (!do_fre)
{
remove_dead_inserted_code ();
OSDN Git Service
