#include "domwalk.h"
#include "real.h"
#include "tree-pass.h"
-#include "flags.h"
#include "langhooks.h"
/* This file implements optimizations on the dominator tree. */
have to perform in lookup_avail_expr and finally it allows us to
significantly reduce the number of calls into the hashing routine
itself. */
+
struct expr_hash_elt
{
/* The value (lhs) of this expression. */
/* Track whether or not we have changed the control flow graph. */
static bool cfg_altered;
+/* Bitmap of blocks that have had EH statements cleaned. We should
+ remove their dead edges eventually. */
+static bitmap need_eh_cleanup;
+
/* Statistics for dominator optimizations. */
struct opt_stats_d
{
static struct opt_stats_d opt_stats;
-/* This virtual array holds pairs of edges which describe a scheduled
- edge redirection from jump threading.
-
- The first entry in each pair is the edge we are going to redirect.
-
- The second entry in each pair is the edge leading to our final
- destination block. By providing this as an edge rather than the
- final target block itself we can correctly handle redirections
- when the target block had PHIs which required edge insertions/splitting
- to remove the PHIs. */
-static GTY(()) varray_type redirection_edges;
-
/* A virtual array holding value range records for the variable identified
by the index, SSA_VERSION. */
static varray_type vrp_data;
static struct eq_expr_value get_eq_expr_value (tree, int, varray_type *,
basic_block, varray_type *);
static hashval_t avail_expr_hash (const void *);
+static hashval_t real_avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static void htab_statistics (FILE *, htab_t);
static void record_cond (tree, tree, varray_type *);
+static void record_dominating_conditions (tree, varray_type *);
static void record_const_or_copy (tree, tree, varray_type *);
static void record_equality (tree, tree, varray_type *);
-static tree update_rhs_and_lookup_avail_expr (tree, tree, varray_type *,
- stmt_ann_t, bool);
+static tree update_rhs_and_lookup_avail_expr (tree, tree, varray_type *, bool);
static tree simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *,
- tree, stmt_ann_t, int);
+ tree, int);
static tree simplify_cond_and_lookup_avail_expr (tree, varray_type *,
stmt_ann_t, int);
-static tree simplify_switch_and_lookup_avail_expr (tree, varray_type *,
- stmt_ann_t, int);
+static tree simplify_switch_and_lookup_avail_expr (tree, varray_type *, int);
static tree find_equivalent_equality_comparison (tree);
static void record_range (tree, basic_block, varray_type *);
static bool extract_range_from_cond (tree, tree *, tree *, int *);
static void restore_currdefs_to_original_value (varray_type locals,
unsigned limit);
static void register_definitions_for_stmt (stmt_ann_t, varray_type *);
-static void redirect_edges_and_update_ssa_graph (varray_type);
+static edge single_incoming_edge_ignoring_loop_edges (basic_block);
/* Local version of fold that doesn't introduce cruft. */
/* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
may have been added by fold, and "useless" type conversions that might
now be apparent due to propagation. */
- STRIP_MAIN_TYPE_NOPS (t);
STRIP_USELESS_TYPE_CONVERSION (t);
return t;
VARRAY_TREE (table, SSA_NAME_VERSION (var)) = value;
}
-/* REDIRECTION_EDGES contains edge pairs where we want to revector the
- destination of the first edge to the destination of the second edge.
-
- These redirections may significantly change the SSA graph since we
- allow redirection through blocks with PHI nodes and blocks with
- real instructions in some cases.
-
- This routine will perform the requested redirections and incrementally
- update the SSA graph.
-
- Note in some cases requested redirections may be ignored as they can
- not be safely implemented. */
-
-static void
-redirect_edges_and_update_ssa_graph (varray_type redirection_edges)
-{
- basic_block tgt;
- unsigned int i;
- size_t old_num_referenced_vars = num_referenced_vars;
-
- /* First note any variables which we are going to have to take
- out of SSA form. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
- {
- block_stmt_iterator bsi;
- edge e;
- basic_block tgt;
- tree phi;
-
- e = VARRAY_EDGE (redirection_edges, i);
- tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
-
- /* All variables referenced in PHI nodes we bypass must be
- renamed. */
- for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
- {
- tree result = SSA_NAME_VAR (PHI_RESULT (phi));
- bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
- }
-
- /* Any variables set by statements at the start of the block we
- are bypassing must also be taken our of SSA form. */
- for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
- {
- unsigned int j;
- def_optype defs;
- vdef_optype vdefs;
- tree stmt = bsi_stmt (bsi);
- stmt_ann_t ann = stmt_ann (stmt);
-
- if (TREE_CODE (stmt) == COND_EXPR)
- break;
-
- get_stmt_operands (stmt);
-
- defs = DEF_OPS (ann);
- for (j = 0; j < NUM_DEFS (defs); j++)
- {
- tree op = SSA_NAME_VAR (DEF_OP (defs, j));
- bitmap_set_bit (vars_to_rename, var_ann (op)->uid);
- }
-
- vdefs = VDEF_OPS (ann);
- for (j = 0; j < NUM_VDEFS (vdefs); j++)
- {
- tree op = VDEF_RESULT (vdefs, j);
- bitmap_set_bit (vars_to_rename, var_ann (op)->uid);
- }
- }
-
- /* Finally, any variables in PHI nodes at our final destination
- must also be taken our of SSA form. */
- for (phi = phi_nodes (tgt); phi; phi = TREE_CHAIN (phi))
- {
- tree result = SSA_NAME_VAR (PHI_RESULT (phi));
- int j;
-
- bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
-
- for (j = 0; j < PHI_NUM_ARGS (phi); j++)
- {
- tree arg = PHI_ARG_DEF (phi, j);
-
- if (TREE_CODE (arg) != SSA_NAME)
- continue;
-
- arg = SSA_NAME_VAR (arg);
- bitmap_set_bit (vars_to_rename, var_ann (arg)->uid);
- }
- }
- }
-
- /* Take those selected variables out of SSA form. This must be
- done before we start redirecting edges. */
- if (bitmap_first_set_bit (vars_to_rename) >= 0)
- rewrite_vars_out_of_ssa (vars_to_rename);
-
- /* The out of SSA translation above may split the edge from
- E->src to E->dest. This could potentially cause us to lose
- an assignment leading to invalid warnings about uninitialized
- variables or incorrect code.
-
- Luckily, we can detect this by looking at the last statement
- in E->dest. If it is not a COND_EXPR or SWITCH_EXPR, then
- the edge was split and instead of E, we want E->dest->succ. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
- {
- edge e = VARRAY_EDGE (redirection_edges, i);
- tree last = last_stmt (e->dest);
-
- if (last
- && TREE_CODE (last) != COND_EXPR
- && TREE_CODE (last) != SWITCH_EXPR)
- {
- e = e->dest->succ;
-
-#ifdef ENABLE_CHECKING
- /* There should only be a single successor if the
- original edge was split. */
- if (e->succ_next)
- abort ();
-#endif
- /* Replace the edge in REDIRECTION_EDGES for the
- loop below. */
- VARRAY_EDGE (redirection_edges, i) = e;
- }
- }
-
- /* If we created any new variables as part of the out-of-ssa
- translation, then any jump threads must be invalidated if they
- bypass a block in which we skipped instructions.
-
- This is necessary as instructions which appeared to be NOPS
- may be necessary after the out-of-ssa translation. */
- if (num_referenced_vars != old_num_referenced_vars)
- {
- for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
- {
- block_stmt_iterator bsi;
- edge e;
-
- e = VARRAY_EDGE (redirection_edges, i);
- for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
- {
- tree stmt = bsi_stmt (bsi);
-
- if (IS_EMPTY_STMT (stmt)
- || TREE_CODE (stmt) == LABEL_EXPR)
- continue;
-
- if (TREE_CODE (stmt) == COND_EXPR)
- break;
-
- /* Invalidate the jump thread. */
- VARRAY_EDGE (redirection_edges, i) = NULL;
- VARRAY_EDGE (redirection_edges, i + 1) = NULL;
- break;
- }
- }
- }
-
- /* Now redirect the edges. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
- {
- basic_block src;
- edge e;
-
- e = VARRAY_EDGE (redirection_edges, i);
- if (!e)
- continue;
-
- tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
-
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
- e->src->index, e->dest->index, tgt->index);
-
- src = e->src;
-
- e = redirect_edge_and_branch (e, tgt);
- PENDING_STMT (e) = NULL_TREE;
-
- /* Updating the dominance information would be nontrivial. */
- free_dominance_info (CDI_DOMINATORS);
-
- if ((dump_file && (dump_flags & TDF_DETAILS))
- && e->src != src)
- fprintf (dump_file, " basic block %d created\n",
- e->src->index);
-
- cfg_altered = true;
- }
-
- VARRAY_CLEAR (redirection_edges);
-
- for (i = old_num_referenced_vars; i < num_referenced_vars; i++)
- {
- bitmap_set_bit (vars_to_rename, i);
- var_ann (referenced_var (i))->out_of_ssa_tag = 0;
- }
-}
-
/* Jump threading, redundancy elimination and const/copy propagation.
- Optimize function FNDECL based on a walk through the dominator tree.
-
This pass may expose new symbols that need to be renamed into SSA. For
every new symbol exposed, its corresponding bit will be set in
- VARS_TO_RENAME.
-
- PHASE indicates which dump file from the DUMP_FILES array to use when
- dumping debugging information. */
+ VARS_TO_RENAME. */
static void
tree_ssa_dominator_optimize (void)
{
- basic_block bb;
struct dom_walk_data walk_data;
unsigned int i;
mark_dfs_back_edges ();
/* Create our hash tables. */
- avail_exprs = htab_create (1024, avail_expr_hash, avail_expr_eq, free);
- VARRAY_TREE_INIT (const_and_copies, highest_ssa_version, "const_and_copies");
+ avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
+ VARRAY_TREE_INIT (const_and_copies, num_ssa_names, "const_and_copies");
nonzero_vars = BITMAP_XMALLOC ();
- VARRAY_EDGE_INIT (redirection_edges, 20, "redirection_edges");
- VARRAY_GENERIC_PTR_INIT (vrp_data, highest_ssa_version, "vrp_data");
+ VARRAY_GENERIC_PTR_INIT (vrp_data, num_ssa_names, "vrp_data");
+ need_eh_cleanup = BITMAP_XMALLOC ();
/* Setup callbacks for the generic dominator tree walker. */
walk_data.walk_stmts_backward = false;
/* Now initialize the dominator walker. */
init_walk_dominator_tree (&walk_data);
- /* Reset block_forwardable in each block's annotation. We use that
- attribute when threading through COND_EXPRs. */
- FOR_EACH_BB (bb)
- bb_ann (bb)->forwardable = 1;
-
calculate_dominance_info (CDI_DOMINATORS);
/* If we prove certain blocks are unreachable, then we want to
/* Recursively walk the dominator tree optimizing statements. */
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
- /* Wipe the hash tables. */
-
- if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
- redirect_edges_and_update_ssa_graph (redirection_edges);
+ /* If we exposed any new variables, go ahead and put them into
+ SSA form now, before we handle jump threading. This simplifies
+ interactions between rewriting of _DECL nodes into SSA form
+ and rewriting SSA_NAME nodes into SSA form after block
+ duplication and CFG manipulation. */
+ if (bitmap_first_set_bit (vars_to_rename) >= 0)
+ {
+ rewrite_into_ssa (false);
+ bitmap_clear (vars_to_rename);
+ }
- /* We may have made some basic blocks unreachable, remove them. */
- cfg_altered |= delete_unreachable_blocks ();
+ /* Thread jumps, creating duplicate blocks as needed. */
+ cfg_altered = thread_through_all_blocks ();
- /* If the CFG was altered, then recompute the dominator tree. This
- is not strictly needed if we only removed unreachable blocks, but
- may produce better results. If we threaded jumps, then rebuilding
- the dominator tree is strictly necessary. */
- if (cfg_altered)
+ /* Removal of statements may make some EH edges dead. Purge
+ such edges from the CFG as needed. */
+ if (bitmap_first_set_bit (need_eh_cleanup) >= 0)
{
- cleanup_tree_cfg ();
- calculate_dominance_info (CDI_DOMINATORS);
+ cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
+ bitmap_zero (need_eh_cleanup);
}
- /* If we are going to iterate (CFG_ALTERED is true), then we must
- perform any queued renaming before the next iteration. */
- if (cfg_altered
- && bitmap_first_set_bit (vars_to_rename) >= 0)
- {
- rewrite_into_ssa ();
- bitmap_clear (vars_to_rename);
+ free_dominance_info (CDI_DOMINATORS);
+ cfg_altered = cleanup_tree_cfg ();
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ rewrite_ssa_into_ssa ();
- /* The into SSA translation may have created new SSA_NAMES whic
- affect the size of CONST_AND_COPIES and VRP_DATA. */
- VARRAY_GROW (const_and_copies, highest_ssa_version);
- VARRAY_GROW (vrp_data, highest_ssa_version);
+ if (VARRAY_ACTIVE_SIZE (const_and_copies) <= num_ssa_names)
+ {
+ VARRAY_GROW (const_and_copies, num_ssa_names);
+ VARRAY_GROW (vrp_data, num_ssa_names);
}
/* Reinitialize the various tables. */
}
while (cfg_altered);
- /* Remove any unreachable blocks left behind and linearize the CFG. */
- cleanup_tree_cfg ();
-
/* Debugging dumps. */
if (dump_file && (dump_flags & TDF_STATS))
dump_dominator_optimization_stats (dump_file);
- /* We emptyed the hash table earlier, now delete it completely. */
+ /* We emptied the hash table earlier, now delete it completely. */
htab_delete (avail_exprs);
- /* It is not nocessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
+ /* It is not necessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
of the do-while loop above. */
/* Free nonzero_vars. */
BITMAP_XFREE (nonzero_vars);
+ BITMAP_XFREE (need_eh_cleanup);
}
static bool
NULL, /* next */
0, /* static_pass_number */
TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
tree phi;
/* Each PHI creates a temporary equivalence, record them. */
- for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
- tree src = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, e));
+ tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
tree dst = PHI_RESULT (phi);
record_const_or_copy (dst, src, &bd->const_and_copies);
register_new_def (dst, &bd->block_defs);
if (TREE_CODE (USE_OP (uses, i)) == SSA_NAME)
tmp = get_value_for (USE_OP (uses, i), const_and_copies);
if (tmp)
- *USE_OP_PTR (uses, i) = tmp;
+ SET_USE_OP (uses, i, tmp);
}
/* Similarly for virtual uses. */
if (TREE_CODE (VUSE_OP (vuses, i)) == SSA_NAME)
tmp = get_value_for (VUSE_OP (vuses, i), const_and_copies);
if (tmp)
- VUSE_OP (vuses, i) = tmp;
+ SET_VUSE_OP (vuses, i, tmp);
}
/* Try to lookup the new expression. */
/* Restore the statement's original uses/defs. */
for (i = 0; i < NUM_USES (uses); i++)
- *USE_OP_PTR (uses, i) = uses_copy[i];
+ SET_USE_OP (uses, i, uses_copy[i]);
for (i = 0; i < NUM_VUSES (vuses); i++)
- VUSE_OP (vuses, i) = vuses_copy[i];
+ SET_VUSE_OP (vuses, i, vuses_copy[i]);
free (uses_copy);
free (vuses_copy);
cached_lhs = lookup_avail_expr (dummy_cond, NULL, false);
if (!cached_lhs || ! is_gimple_min_invariant (cached_lhs))
{
- stmt_ann_t ann = get_stmt_ann (dummy_cond);
cached_lhs = simplify_cond_and_lookup_avail_expr (dummy_cond,
NULL,
- ann,
+ NULL,
false);
}
}
edge taken_edge = find_taken_edge (e->dest, cached_lhs);
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
- if (dest == e->src)
+ if (dest == e->dest)
return;
/* If we have a known destination for the conditional, then
we can perform this optimization, which saves at least one
conditional jump each time it applies since we get to
- bypass the conditional at our original destination.
-
- Note that we can either thread through a block with PHIs
- or to a block with PHIs, but not both. At this time the
- bookkeeping to keep the CFG & SSA up-to-date has proven
- difficult. */
+ bypass the conditional at our original destination. */
if (dest)
{
- int saved_forwardable = bb_ann (e->src)->forwardable;
- edge tmp_edge;
-
- bb_ann (e->src)->forwardable = 0;
- tmp_edge = tree_block_forwards_to (dest);
- taken_edge = (tmp_edge ? tmp_edge : taken_edge);
- bb_ann (e->src)->forwardable = saved_forwardable;
- VARRAY_PUSH_EDGE (redirection_edges, e);
- VARRAY_PUSH_EDGE (redirection_edges, taken_edge);
+ e->aux = taken_edge;
+ bb_ann (e->dest)->incoming_edge_threaded = true;
}
}
}
}
/* Use the SSA_NAMES in LOCALS to restore TABLE to its original
- state, stopping when there are LIMIT entires left in LOCALs. */
+ state, stopping when there are LIMIT entries left in LOCALs. */
static void
restore_nonzero_vars_to_original_value (varray_type locals,
}
/* Use the source/dest pairs in LOCALS to restore TABLE to its original
- state, stopping when there are LIMIT entires left in LOCALs. */
+ state, stopping when there are LIMIT entries left in LOCALs. */
static void
restore_vars_to_original_value (varray_type locals,
if (TREE_CODE_CLASS (cond_code) == '<')
{
record_cond (cond, boolean_true_node, &bd->avail_exprs);
+ record_dominating_conditions (cond, &bd->avail_exprs);
record_cond (inverted, boolean_false_node, &bd->avail_exprs);
}
else if (cond_code == SSA_NAME)
{
record_cond (cond, boolean_false_node, &bd->avail_exprs);
record_cond (inverted, boolean_true_node, &bd->avail_exprs);
+ record_dominating_conditions (inverted, &bd->avail_exprs);
}
else if (cond_code == SSA_NAME)
record_const_or_copy (cond, boolean_false_node,
Ignoring any alternatives which are the same as the result, if
all the alternatives are equal, then the PHI node creates an
- equivalence. */
+ equivalence.
+
+ Additionally, if all the PHI alternatives are known to have a nonzero
+ value, then the result of this PHI is known to have a nonzero value,
+ even if we do not know its exact value. */
+
static void
record_equivalences_from_phis (struct dom_walk_data *walk_data, basic_block bb)
{
= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
tree phi;
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree lhs = PHI_RESULT (phi);
tree rhs = NULL;
breaking out of the loop, then we have a PHI which may create
a useful equivalence. We do not need to record unwind data for
this, since this is a true assignment and not an equivalence
- infered from a comparison. All uses of this ssa name are dominated
+ inferred from a comparison. All uses of this ssa name are dominated
by this assignment, so unwinding just costs time and space. */
if (i == PHI_NUM_ARGS (phi)
&& may_propagate_copy (lhs, rhs))
set_value_for (lhs, rhs, const_and_copies);
+ /* Now see if we know anything about the nonzero property for the
+ result of this PHI. */
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ {
+ if (!PHI_ARG_NONZERO (phi, i))
+ break;
+ }
+
+ if (i == PHI_NUM_ARGS (phi))
+ bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
+
register_new_def (lhs, &bd->block_defs);
}
}
+/* Ignoring loop backedges, if BB has precisely one incoming edge then
+ return that edge. Otherwise return NULL. */
+static edge
+single_incoming_edge_ignoring_loop_edges (basic_block bb)
+{
+ edge retval = NULL;
+ edge e;
+
+ for (e = bb->pred; e; e = e->pred_next)
+ {
+ /* A loop back edge can be identified by the destination of
+ the edge dominating the source of the edge. */
+ if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
+ continue;
+
+ /* If we have already seen a non-loop edge, then we must have
+ multiple incoming non-loop edges and thus we return NULL. */
+ if (retval)
+ return NULL;
+
+ /* This is the first non-loop incoming edge we have found. Record
+ it. */
+ retval = e;
+ }
+
+ return retval;
+}
+
/* Record any equivalences created by the incoming edge to BB. If BB
has more than one incoming edge, then no equivalence is created. */
eq_expr_value.src = NULL;
eq_expr_value.dst = NULL;
- /* If we have a single predecessor, then extract EDGE_FLAGS from
- our single incoming edge. Otherwise clear EDGE_FLAGS and
- PARENT_BLOCK_LAST_STMT since they're not needed. */
+ /* If we have a single predecessor (ignoring loop backedges), then extract
+ EDGE_FLAGS from the single incoming edge. Otherwise just return as
+ there is nothing to do. */
if (bb->pred
- && ! bb->pred->pred_next
- && parent_block_last_stmt
- && bb_for_stmt (parent_block_last_stmt) == bb->pred->src)
+ && parent_block_last_stmt)
{
- edge_flags = bb->pred->flags;
+ edge e = single_incoming_edge_ignoring_loop_edges (bb);
+ if (e && bb_for_stmt (parent_block_last_stmt) == e->src)
+ edge_flags = e->flags;
+ else
+ return;
}
else
- {
- edge_flags = 0;
- parent_block_last_stmt = NULL;
- }
+ return;
/* If our parent block ended in a COND_EXPR, add any equivalences
created by the COND_EXPR to the hash table and initialize
conditional. This assignment is inserted in CONST_AND_COPIES so that
the copy and constant propagator can find more propagation
opportunities. */
- if (parent_block_last_stmt
- && bb->pred->pred_next == NULL
- && TREE_CODE (parent_block_last_stmt) == COND_EXPR
+ if (TREE_CODE (parent_block_last_stmt) == COND_EXPR
&& (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
(edge_flags & EDGE_TRUE_VALUE) != 0,
&bd->avail_exprs,
bb,
&bd->vrp_variables);
- /* Similarly when the parent block ended in a SWITCH_EXPR. */
- else if (parent_block_last_stmt
- && bb->pred->pred_next == NULL
+ /* Similarly when the parent block ended in a SWITCH_EXPR.
+ We can only know the value of the switch's condition if the dominator
+ parent is also the only predecessor of this block. */
+ else if (bb->pred->src == parent
&& TREE_CODE (parent_block_last_stmt) == SWITCH_EXPR)
{
tree switch_cond = SWITCH_COND (parent_block_last_stmt);
tree elt = TREE_VEC_ELT (switch_vec, i);
if (label_to_block (CASE_LABEL (elt)) == bb)
{
- if (++case_count > 1)
+ if (++case_count > 1 || CASE_HIGH (elt))
break;
match_case = elt;
}
the exact value of SWITCH_COND which caused us to get to
this block. Record that equivalence in EQ_EXPR_VALUE. */
if (case_count == 1
+ && match_case
&& CASE_LOW (match_case)
&& !CASE_HIGH (match_case))
{
eq_expr_value.dst = switch_cond;
- eq_expr_value.src = CASE_LOW (match_case);
+ eq_expr_value.src = fold_convert (TREE_TYPE (switch_cond),
+ CASE_LOW (match_case));
}
}
}
free (element);
}
+/* COND is a condition which is known to be true. Record variants of
+ COND which must also be true.
+
+ For example, if a < b is true, then a <= b must also be true. */
+
+static void
+record_dominating_conditions (tree cond, varray_type *block_avail_exprs_p)
+{
+ switch (TREE_CODE (cond))
+ {
+ case LT_EXPR:
+ record_cond (build2 (LE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (ORDERED_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (NE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (LTGT_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ break;
+
+ case GT_EXPR:
+ record_cond (build2 (GE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (ORDERED_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (NE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (LTGT_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ break;
+
+ case GE_EXPR:
+ case LE_EXPR:
+ record_cond (build2 (ORDERED_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ break;
+
+ case EQ_EXPR:
+ record_cond (build2 (ORDERED_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (LE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (GE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ break;
+
+ case UNORDERED_EXPR:
+ record_cond (build2 (NE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (UNLE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (UNGE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (UNEQ_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (UNLT_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (UNGT_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ break;
+
+ case UNLT_EXPR:
+ record_cond (build2 (UNLE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (NE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ break;
+
+ case UNGT_EXPR:
+ record_cond (build2 (UNGE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (NE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ break;
+
+ case UNEQ_EXPR:
+ record_cond (build2 (UNLE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (UNGE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ break;
+
+ case LTGT_EXPR:
+ record_cond (build2 (NE_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+ record_cond (build2 (ORDERED_EXPR, boolean_type_node,
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1)),
+ boolean_true_node,
+ block_avail_exprs_p);
+
+ default:
+ break;
+ }
+}
+
/* A helper function for record_const_or_copy and record_equality.
Do the work of recording the value and undo info. */
/* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
variable compared against zero. If we're honoring signed zeros,
then we cannot record this value unless we know that the value is
- non-zero. */
+ nonzero. */
if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
&& (TREE_CODE (y) != REAL_CST
|| REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
static tree
simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
- tree stmt,
- stmt_ann_t ann,
- int insert)
+ tree stmt, int insert)
{
tree rhs = TREE_OPERAND (stmt, 1);
enum tree_code rhs_code = TREE_CODE (rhs);
result = update_rhs_and_lookup_avail_expr (stmt,
rhs_def_operand,
&bd->avail_exprs,
- ann,
insert);
}
}
tree type = TREE_TYPE (TREE_OPERAND (stmt, 0));
tree t;
+ /* If we care about correct floating point results, then
+ don't fold x + c1 - c2. Note that we need to take both
+ the codes and the signs to figure this out. */
+ if (FLOAT_TYPE_P (type)
+ && !flag_unsafe_math_optimizations
+ && (rhs_def_code == PLUS_EXPR
+ || rhs_def_code == MINUS_EXPR))
+ {
+ bool neg = false;
+
+ neg ^= (rhs_code == MINUS_EXPR);
+ neg ^= (rhs_def_code == MINUS_EXPR);
+ neg ^= real_isneg (TREE_REAL_CST_PTR (outer_const));
+ neg ^= real_isneg (TREE_REAL_CST_PTR (def_stmt_op1));
+
+ if (neg)
+ goto dont_fold_assoc;
+ }
+
/* Ho hum. So fold will only operate on the outermost
thingy that we give it, so we have to build the new
expression in two pieces. This requires that we handle
&& TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
&& is_gimple_val (TREE_OPERAND (t, 1))))
result = update_rhs_and_lookup_avail_expr
- (stmt, t, &bd->avail_exprs, ann, insert);
+ (stmt, t, &bd->avail_exprs, insert);
}
}
}
+ dont_fold_assoc:;
}
/* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
if (rhs_code == TRUNC_DIV_EXPR)
t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0,
- build_int_2 (tree_log2 (op1), 0));
+ build_int_cst (NULL_TREE, tree_log2 (op1), 0));
else
t = build (BIT_AND_EXPR, TREE_TYPE (op0), op0,
local_fold (build (MINUS_EXPR, TREE_TYPE (op1),
op1, integer_one_node)));
result = update_rhs_and_lookup_avail_expr (stmt, t,
- &bd->avail_exprs,
- ann, insert);
+ &bd->avail_exprs, insert);
}
}
TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), LE_EXPR);
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
- = convert (type, integer_zero_node);
+ = fold_convert (type, integer_zero_node);
}
val = simplify_cond_and_lookup_avail_expr (dummy_cond,
&bd->avail_exprs,
TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), GE_EXPR);
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
- = convert (type, integer_zero_node);
+ = fold_convert (type, integer_zero_node);
val = simplify_cond_and_lookup_avail_expr (dummy_cond,
&bd->avail_exprs,
t = op;
result = update_rhs_and_lookup_avail_expr (stmt, t,
- &bd->avail_exprs,
- ann, insert);
+ &bd->avail_exprs, insert);
}
}
if (t)
result = update_rhs_and_lookup_avail_expr (stmt, t,
- &bd->avail_exprs,
- ann, insert);
+ &bd->avail_exprs, insert);
}
return result;
/* Update the statement to use the new equivalent
condition. */
COND_EXPR_COND (stmt) = new_cond;
- ann->modified = 1;
+
+ /* If this is not a real stmt, ann will be NULL and we
+ avoid processing the operands. */
+ if (ann)
+ modify_stmt (stmt);
/* Lookup the condition and return its known value if it
exists. */
static tree
simplify_switch_and_lookup_avail_expr (tree stmt,
varray_type *block_avail_exprs_p,
- stmt_ann_t ann,
int insert)
{
tree cond = SWITCH_COND (stmt);
def = TREE_OPERAND (def, 1);
if (TREE_CODE (def) == NOP_EXPR)
{
+ int need_precision;
+ bool fail;
+
def = TREE_OPERAND (def, 0);
+
+#ifdef ENABLE_CHECKING
+ /* ??? Why was Jeff testing this? We are gimple... */
+ if (!is_gimple_val (def))
+ abort ();
+#endif
+
to = TREE_TYPE (cond);
ti = TREE_TYPE (def);
- /* If we have an extension that preserves sign, then we
+ /* If we have an extension that preserves value, then we
can copy the source value into the switch. */
- if (TYPE_UNSIGNED (to) == TYPE_UNSIGNED (ti)
- && TYPE_PRECISION (to) >= TYPE_PRECISION (ti)
- && is_gimple_val (def))
+
+ need_precision = TYPE_PRECISION (ti);
+ fail = false;
+ if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
+ fail = true;
+ else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
+ need_precision += 1;
+ if (TYPE_PRECISION (to) < need_precision)
+ fail = true;
+
+ if (!fail)
{
SWITCH_COND (stmt) = def;
- ann->modified = 1;
+ modify_stmt (stmt);
return lookup_avail_expr (stmt, block_avail_exprs_p, insert);
}
return 0;
}
+
+/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
+ known value for that SSA_NAME (or NULL if no value is known).
+
+ NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
+ even if we don't know their precise value.
+
+ Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
+ nodes of the successors of BB. */
+
+static void
+cprop_into_successor_phis (basic_block bb,
+ varray_type const_and_copies,
+ bitmap nonzero_vars)
+{
+ edge e;
+
+ /* This can get rather expensive if the implementation is naive in
+ how it finds the phi alternative associated with a particular edge. */
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ tree phi;
+ int phi_num_args;
+ int hint;
+
+ /* If this is an abnormal edge, then we do not want to copy propagate
+ into the PHI alternative associated with this edge. */
+ if (e->flags & EDGE_ABNORMAL)
+ continue;
+
+ phi = phi_nodes (e->dest);
+ if (! phi)
+ continue;
+
+ /* There is no guarantee that for any two PHI nodes in a block that
+ the phi alternative associated with a particular edge will be
+ at the same index in the phi alternative array.
+
+ However, it is very likely they will be the same. So we keep
+ track of the index of the alternative where we found the edge in
+ the previous phi node and check that index first in the next
+ phi node. If that hint fails, then we actually search all
+ the entries. */
+ phi_num_args = PHI_NUM_ARGS (phi);
+ hint = phi_num_args;
+ for ( ; phi; phi = PHI_CHAIN (phi))
+ {
+ int i;
+ tree new;
+ use_operand_p orig_p;
+ tree orig;
+
+ /* If the hint is valid (!= phi_num_args), see if it points
+ us to the desired phi alternative. */
+ if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
+ ;
+ else
+ {
+ /* The hint was either invalid or did not point to the
+ correct phi alternative. Search all the alternatives
+ for the correct one. Update the hint. */
+ for (i = 0; i < phi_num_args; i++)
+ if (PHI_ARG_EDGE (phi, i) == e)
+ break;
+ hint = i;
+ }
+
+#ifdef ENABLE_CHECKING
+ /* If we did not find the proper alternative, then something is
+ horribly wrong. */
+ if (hint == phi_num_args)
+ abort ();
+#endif
+
+ /* The alternative may be associated with a constant, so verify
+ it is an SSA_NAME before doing anything with it. */
+ orig_p = PHI_ARG_DEF_PTR (phi, hint);
+ orig = USE_FROM_PTR (orig_p);
+ if (TREE_CODE (orig) != SSA_NAME)
+ continue;
+
+ /* If the alternative is known to have a nonzero value, record
+ that fact in the PHI node itself for future use. */
+ if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (orig)))
+ PHI_ARG_NONZERO (phi, hint) = true;
+
+ /* If we have *ORIG_P in our constant/copy table, then replace
+ ORIG_P with its value in our constant/copy table. */
+ new = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (orig));
+ if (new
+ && (TREE_CODE (new) == SSA_NAME
+ || is_gimple_min_invariant (new))
+ && may_propagate_copy (orig, new))
+ {
+ propagate_value (orig_p, new);
+ }
+ }
+ }
+}
+
+
/* Propagate known constants/copies into PHI nodes of BB's successor
blocks. */
cprop_into_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
- cprop_into_successor_phis (bb, const_and_copies);
+ cprop_into_successor_phis (bb, const_and_copies, nonzero_vars);
}
/* Search for redundant computations in STMT. If any are found, then
eliminate_redundant_computations (struct dom_walk_data *walk_data,
tree stmt, stmt_ann_t ann)
{
- vdef_optype vdefs = VDEF_OPS (ann);
+ v_may_def_optype v_may_defs = V_MAY_DEF_OPS (ann);
tree *expr_p, def = NULL_TREE;
bool insert = true;
tree cached_lhs;
|| ! def
|| TREE_CODE (def) != SSA_NAME
|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
- || NUM_VDEFS (vdefs) != 0)
+ || NUM_V_MAY_DEFS (v_may_defs) != 0)
insert = false;
/* Check if the expression has been computed before. */
if (! cached_lhs && TREE_CODE (stmt) == MODIFY_EXPR)
cached_lhs = simplify_rhs_and_lookup_avail_expr (walk_data,
stmt,
- ann,
insert);
/* Similarly if this is a COND_EXPR and we did not find its
expression in the hash table, simplify the condition and
else if (!cached_lhs && TREE_CODE (stmt) == SWITCH_EXPR)
cached_lhs = simplify_switch_and_lookup_avail_expr (stmt,
&bd->avail_exprs,
- ann,
insert);
opt_stats.num_exprs_considered++;
CACHED_LHS into *EXPR_P. */
if (cached_lhs
&& (TREE_CODE (cached_lhs) != SSA_NAME
- || may_propagate_copy (cached_lhs, *expr_p)))
+ || may_propagate_copy (*expr_p, cached_lhs)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
&& is_gimple_min_invariant (cached_lhs)))
retval = true;
- propagate_value (expr_p, cached_lhs);
- ann->modified = 1;
+ propagate_tree_value (expr_p, cached_lhs);
+ modify_stmt (stmt);
}
return retval;
}
/* If the RHS of the assignment is a constant or another variable that
may be propagated, register it in the CONST_AND_COPIES table. We
do not need to record unwind data for this, since this is a true
- assignment and not an equivalence infered from a comparison. All
+ assignment and not an equivalence inferred from a comparison. All
uses of this ssa name are dominated by this assignment, so unwinding
just costs time and space. */
if (may_optimize_p
/* Look at both sides for pointer dereferences. If we find one, then
the pointer must be nonnull and we can enter that equivalence into
the hash tables. */
- for (i = 0; i < 2; i++)
- {
- tree t = TREE_OPERAND (stmt, i);
-
- /* Strip away any COMPONENT_REFs. */
- while (TREE_CODE (t) == COMPONENT_REF)
- t = TREE_OPERAND (t, 0);
-
- /* Now see if this is a pointer dereference. */
- if (TREE_CODE (t) == INDIRECT_REF)
- {
- tree op = TREE_OPERAND (t, 0);
-
- /* If the pointer is a SSA variable, then enter new
- equivalences into the hash table. */
- if (TREE_CODE (op) == SSA_NAME)
- record_var_is_nonzero (op, block_nonzero_vars_p);
- }
- }
+ if (flag_delete_null_pointer_checks)
+ for (i = 0; i < 2; i++)
+ {
+ tree t = TREE_OPERAND (stmt, i);
+
+ /* Strip away any COMPONENT_REFs. */
+ while (TREE_CODE (t) == COMPONENT_REF)
+ t = TREE_OPERAND (t, 0);
+
+ /* Now see if this is a pointer dereference. */
+ if (TREE_CODE (t) == INDIRECT_REF)
+ {
+ tree op = TREE_OPERAND (t, 0);
+
+ /* If the pointer is a SSA variable, then enter new
+ equivalences into the hash table. */
+ while (TREE_CODE (op) == SSA_NAME)
+ {
+ tree def = SSA_NAME_DEF_STMT (op);
+
+ record_var_is_nonzero (op, block_nonzero_vars_p);
+
+ /* And walk up the USE-DEF chains noting other SSA_NAMEs
+ which are known to have a nonzero value. */
+ if (def
+ && TREE_CODE (def) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (def, 1)) == NOP_EXPR)
+ op = TREE_OPERAND (TREE_OPERAND (def, 1), 0);
+ else
+ break;
+ }
+ }
+ }
/* A memory store, even an aliased store, creates a useful
equivalence. By exchanging the LHS and RHS, creating suitable
{
tree rhs = TREE_OPERAND (stmt, 1);
tree new;
- size_t j;
/* FIXME: If the LHS of the assignment is a bitfield and the RHS
is a constant, we need to adjust the constant to fit into the
if (rhs)
{
- vdef_optype vdefs = VDEF_OPS (ann);
-
/* Build a new statement with the RHS and LHS exchanged. */
new = build (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
- /* Get an annotation and set up the real operands. */
- get_stmt_ann (new);
- get_stmt_operands (new);
+ create_ssa_artficial_load_stmt (&(ann->operands), new);
- /* Clear out the virtual operands on the new statement, we are
- going to set them explicitly below. */
- remove_vuses (new);
- remove_vdefs (new);
+ /* Finally enter the statement into the available expression
+ table. */
+ lookup_avail_expr (new, block_avail_exprs_p, true);
+ }
+ }
+}
+
+/* Replace *OP_P in STMT with any known equivalent value for *OP_P from
+ CONST_AND_COPIES. */
- start_ssa_stmt_operands (new);
- /* For each VDEF on the original statement, we want to create a
- VUSE of the VDEF result on the new statement. */
- for (j = 0; j < NUM_VDEFS (vdefs); j++)
+static bool
+cprop_operand (tree stmt, use_operand_p op_p, varray_type const_and_copies)
+{
+ bool may_have_exposed_new_symbols = false;
+ tree val;
+ tree op = USE_FROM_PTR (op_p);
+
+ /* If the operand has a known constant value or it is known to be a
+ copy of some other variable, use the value or copy stored in
+ CONST_AND_COPIES. */
+ val = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (op));
+ if (val)
+ {
+ tree op_type, val_type;
+
+ /* Do not change the base variable in the virtual operand
+ tables. That would make it impossible to reconstruct
+ the renamed virtual operand if we later modify this
+ statement. Also only allow the new value to be an SSA_NAME
+ for propagation into virtual operands. */
+ if (!is_gimple_reg (op)
+ && (get_virtual_var (val) != get_virtual_var (op)
+ || TREE_CODE (val) != SSA_NAME))
+ return false;
+
+ /* Get the toplevel type of each operand. */
+ op_type = TREE_TYPE (op);
+ val_type = TREE_TYPE (val);
+
+ /* While both types are pointers, get the type of the object
+ pointed to. */
+ while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
+ {
+ op_type = TREE_TYPE (op_type);
+ val_type = TREE_TYPE (val_type);
+ }
+
+ /* Make sure underlying types match before propagating a constant by
+ converting the constant to the proper type. Note that convert may
+ return a non-gimple expression, in which case we ignore this
+ propagation opportunity. */
+ if (TREE_CODE (val) != SSA_NAME)
+ {
+ if (!lang_hooks.types_compatible_p (op_type, val_type))
{
- tree op = VDEF_RESULT (vdefs, j);
- add_vuse (op, new);
+ val = fold_convert (TREE_TYPE (op), val);
+ if (!is_gimple_min_invariant (val))
+ return false;
}
+ }
- finalize_ssa_stmt_operands (new);
+ /* Certain operands are not allowed to be copy propagated due
+ to their interaction with exception handling and some GCC
+ extensions. */
+ else if (!may_propagate_copy (op, val))
+ return false;
- /* Finally enter the statement into the available expression
- table. */
- lookup_avail_expr (new, block_avail_exprs_p, true);
+ /* Dump details. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Replaced '");
+ print_generic_expr (dump_file, op, dump_flags);
+ fprintf (dump_file, "' with %s '",
+ (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
+ print_generic_expr (dump_file, val, dump_flags);
+ fprintf (dump_file, "'\n");
}
+
+ /* If VAL is an ADDR_EXPR or a constant of pointer type, note
+ that we may have exposed a new symbol for SSA renaming. */
+ if (TREE_CODE (val) == ADDR_EXPR
+ || (POINTER_TYPE_P (TREE_TYPE (op))
+ && is_gimple_min_invariant (val)))
+ may_have_exposed_new_symbols = true;
+
+ propagate_value (op_p, val);
+
+ /* And note that we modified this statement. This is now
+ safe, even if we changed virtual operands since we will
+ rescan the statement and rewrite its operands again. */
+ modify_stmt (stmt);
+ }
+ return may_have_exposed_new_symbols;
+}
+
+/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
+ known value for that SSA_NAME (or NULL if no value is known).
+
+ Propagate values from CONST_AND_COPIES into the uses, vuses and
+ v_may_def_ops of STMT. */
+
+static bool
+cprop_into_stmt (tree stmt, varray_type const_and_copies)
+{
+ bool may_have_exposed_new_symbols = false;
+ stmt_ann_t ann = stmt_ann (stmt);
+ size_t i, num_uses, num_vuses, num_v_may_defs;
+ vuse_optype vuses;
+ v_may_def_optype v_may_defs;
+ use_optype uses;
+
+ uses = USE_OPS (ann);
+ num_uses = NUM_USES (uses);
+ for (i = 0; i < num_uses; i++)
+ {
+ use_operand_p op_p = USE_OP_PTR (uses, i);
+ if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
+ may_have_exposed_new_symbols
+ |= cprop_operand (stmt, op_p, const_and_copies);
+ }
+
+ vuses = VUSE_OPS (ann);
+ num_vuses = NUM_VUSES (vuses);
+ for (i = 0; i < num_vuses; i++)
+ {
+ use_operand_p op_p = VUSE_OP_PTR (vuses, i);
+ if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
+ may_have_exposed_new_symbols
+ |= cprop_operand (stmt, op_p, const_and_copies);
}
+
+ v_may_defs = V_MAY_DEF_OPS (ann);
+ num_v_may_defs = NUM_V_MAY_DEFS (v_may_defs);
+ for (i = 0; i < num_v_may_defs; i++)
+ {
+ use_operand_p op_p = V_MAY_DEF_OP_PTR (v_may_defs, i);
+ if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
+ may_have_exposed_new_symbols
+ |= cprop_operand (stmt, op_p, const_and_copies);
+ }
+ return may_have_exposed_new_symbols;
}
+
/* Optimize the statement pointed by iterator SI.
We try to perform some simplistic global redundancy elimination and
the variable in the LHS in the CONST_AND_COPIES table. */
static void
-optimize_stmt (struct dom_walk_data *walk_data,
- basic_block bb ATTRIBUTE_UNUSED,
+optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
block_stmt_iterator si)
{
stmt_ann_t ann;
tree stmt;
- vdef_optype vdefs;
bool may_optimize_p;
bool may_have_exposed_new_symbols = false;
struct dom_walk_block_data *bd
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
- vdefs = VDEF_OPS (ann);
opt_stats.num_stmts++;
may_have_exposed_new_symbols = false;
print_generic_stmt (dump_file, stmt, TDF_SLIM);
}
- /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
+ /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
may_have_exposed_new_symbols = cprop_into_stmt (stmt, const_and_copies);
/* If the statement has been modified with constant replacements,
else if (TREE_CODE (stmt) == SWITCH_EXPR)
val = SWITCH_COND (stmt);
- if (val && TREE_CODE (val) == INTEGER_CST
- && find_taken_edge (bb_for_stmt (stmt), val))
+ if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
cfg_altered = true;
+
+ /* If we simplified a statement in such a way as to be shown that it
+ cannot trap, update the eh information and the cfg to match. */
+ if (maybe_clean_eh_stmt (stmt))
+ {
+ bitmap_set_bit (need_eh_cleanup, bb->index);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Flagged to clear EH edges.\n");
+ }
}
-
+
if (may_have_exposed_new_symbols)
{
if (! bd->stmts_to_rescan)
static tree
update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs,
varray_type *block_avail_exprs_p,
- stmt_ann_t ann,
bool insert)
{
tree cached_lhs = NULL;
/* And make sure we record the fact that we modified this
statement. */
- ann->modified = 1;
+ modify_stmt (stmt);
return cached_lhs;
}
if (TREE_CODE (cond) == SSA_NAME)
{
retval.dst = cond;
- retval.src = (true_arm ? integer_one_node : integer_zero_node);
+ retval.src = constant_boolean_node (true_arm, TREE_TYPE (cond));
return retval;
}
if (true_arm)
{
record_cond (cond, boolean_true_node, block_avail_exprs_p);
+ record_dominating_conditions (cond, block_avail_exprs_p);
record_cond (inverted, boolean_false_node, block_avail_exprs_p);
if (TREE_CONSTANT (op1))
{
record_cond (inverted, boolean_true_node, block_avail_exprs_p);
+ record_dominating_conditions (inverted, block_avail_exprs_p);
record_cond (cond, boolean_false_node, block_avail_exprs_p);
if (TREE_CONSTANT (op1))
return val;
}
+static hashval_t
+real_avail_expr_hash (const void *p)
+{
+ return ((const struct expr_hash_elt *)p)->hash;
+}
static int
avail_expr_eq (const void *p1, const void *p2)
return false;
}
-/* Given STMT and a pointer to the block local defintions BLOCK_DEFS_P,
+/* Given STMT and a pointer to the block local definitions BLOCK_DEFS_P,
register register all objects set by this statement into BLOCK_DEFS_P
and CURRDEFS. */
register_definitions_for_stmt (stmt_ann_t ann, varray_type *block_defs_p)
{
def_optype defs;
- vdef_optype vdefs;
+ v_may_def_optype v_may_defs;
+ v_must_def_optype v_must_defs;
unsigned int i;
defs = DEF_OPS (ann);
}
/* Register new virtual definitions made by the statement. */
- vdefs = VDEF_OPS (ann);
- for (i = 0; i < NUM_VDEFS (vdefs); i++)
+ v_may_defs = V_MAY_DEF_OPS (ann);
+ for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
+ {
+ /* FIXME: We shouldn't be registering new defs if the variable
+ doesn't need to be renamed. */
+ register_new_def (V_MAY_DEF_RESULT (v_may_defs, i), block_defs_p);
+ }
+
+ /* Register new virtual mustdefs made by the statement. */
+ v_must_defs = V_MUST_DEF_OPS (ann);
+ for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
{
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
- register_new_def (VDEF_RESULT (vdefs, i), block_defs_p);
+ register_new_def (V_MUST_DEF_OP (v_must_defs, i), block_defs_p);
}
}