/* SSA Dominator optimizations for trees
- Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
expressions are removed from AVAIL_EXPRS. Else we may change the
hash code for an expression and be unable to find/remove it from
AVAIL_EXPRS. */
-static VEC(tree,heap) *stmts_to_rescan;
+typedef tree *tree_p;
+DEF_VEC_P(tree_p);
+DEF_VEC_ALLOC_P(tree_p,heap);
+
+static VEC(tree_p,heap) *stmts_to_rescan;
/* Structure for entries in the expression hash table.
avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
avail_exprs_stack = VEC_alloc (tree, heap, 20);
const_and_copies_stack = VEC_alloc (tree, heap, 20);
- stmts_to_rescan = VEC_alloc (tree, heap, 20);
+ stmts_to_rescan = VEC_alloc (tree_p, heap, 20);
need_eh_cleanup = BITMAP_ALLOC (NULL);
/* Setup callbacks for the generic dominator tree walker. */
init_walk_dominator_tree (&walk_data);
calculate_dominance_info (CDI_DOMINATORS);
+ cfg_altered = false;
- /* We need to know which edges exit loops so that we can
- aggressively thread through loop headers to an exit
- edge. */
- loop_optimizer_init (0);
- if (current_loops)
- {
- mark_loop_exit_edges ();
- loop_optimizer_finalize ();
- }
-
- /* Clean up the CFG so that any forwarder blocks created by loop
- canonicalization are removed. */
- cleanup_tree_cfg ();
- calculate_dominance_info (CDI_DOMINATORS);
+ /* We need to know loop structures in order to avoid destroying them
+ in jump threading. Note that we still can e.g. thread through loop
+ headers to an exit edge, or through loop header to the loop body, assuming
+ that we update the loop info. */
+ loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES);
/* We need accurate information regarding back edges in the CFG
- for jump threading. */
+ for jump threading; this may include back edes that are not part of
+ a single loop. */
mark_dfs_back_edges ();
-
+
/* Recursively walk the dominator tree optimizing statements. */
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
free_all_edge_infos ();
/* Thread jumps, creating duplicate blocks as needed. */
- cfg_altered |= thread_through_all_blocks ();
+ cfg_altered |= thread_through_all_blocks (first_pass_instance);
+
+ if (cfg_altered)
+ free_dominance_info (CDI_DOMINATORS);
/* Removal of statements may make some EH edges dead. Purge
such edges from the CFG as needed. */
if (!bitmap_empty_p (need_eh_cleanup))
{
- cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
+ tree_purge_all_dead_eh_edges (need_eh_cleanup);
bitmap_zero (need_eh_cleanup);
}
- if (cfg_altered)
- free_dominance_info (CDI_DOMINATORS);
-
/* Finally, remove everything except invariants in SSA_NAME_VALUE.
Long term we will be able to let everything in SSA_NAME_VALUE
if (dump_file && (dump_flags & TDF_STATS))
dump_dominator_optimization_stats (dump_file);
+ loop_optimizer_finalize ();
+
/* Delete our main hashtable. */
htab_delete (avail_exprs);
VEC_free (tree, heap, avail_exprs_stack);
VEC_free (tree, heap, const_and_copies_stack);
- VEC_free (tree, heap, stmts_to_rescan);
+ VEC_free (tree_p, heap, stmts_to_rescan);
return 0;
}
TODO_dump_func
| TODO_update_ssa
| TODO_cleanup_cfg
- | TODO_verify_ssa
- | TODO_update_smt_usage, /* todo_flags_finish */
+ | TODO_verify_ssa, /* todo_flags_finish */
0 /* letter */
};
/* A trivial wrapper so that we can present the generic jump
threading code with a simple API for simplifying statements. */
static tree
-simplify_stmt_for_jump_threading (tree stmt)
+simplify_stmt_for_jump_threading (tree stmt, tree within_stmt ATTRIBUTE_UNUSED)
{
return lookup_avail_expr (stmt, false);
}
walk_data->global_data = dummy_cond;
}
- thread_across_edge (walk_data->global_data, e, false,
+ thread_across_edge ((tree) walk_data->global_data, e, false,
&const_and_copies_stack,
simplify_stmt_for_jump_threading);
}
/* If we queued any statements to rescan in this block, then
go ahead and rescan them now. */
- while (VEC_length (tree, stmts_to_rescan) > 0)
+ while (VEC_length (tree_p, stmts_to_rescan) > 0)
{
- tree stmt = VEC_last (tree, stmts_to_rescan);
+ tree *stmt_p = VEC_last (tree_p, stmts_to_rescan);
+ tree stmt = *stmt_p;
basic_block stmt_bb = bb_for_stmt (stmt);
if (stmt_bb != bb)
break;
- VEC_pop (tree, stmts_to_rescan);
- mark_new_vars_to_rename (stmt);
+ VEC_pop (tree_p, stmts_to_rescan);
+ pop_stmt_changes (stmt_p);
}
}
indx = e->dest_idx;
for ( ; phi; phi = PHI_CHAIN (phi))
{
- tree new;
+ tree new_val;
use_operand_p orig_p;
- tree orig;
+ tree orig_val;
/* 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, indx);
- orig = USE_FROM_PTR (orig_p);
- if (TREE_CODE (orig) != SSA_NAME)
+ orig_val = USE_FROM_PTR (orig_p);
+ if (TREE_CODE (orig_val) != SSA_NAME)
continue;
/* If we have *ORIG_P in our constant/copy table, then replace
ORIG_P with its value in our constant/copy table. */
- new = SSA_NAME_VALUE (orig);
- if (new
- && new != orig
- && (TREE_CODE (new) == SSA_NAME
- || is_gimple_min_invariant (new))
- && may_propagate_copy (orig, new))
- propagate_value (orig_p, new);
+ new_val = SSA_NAME_VALUE (orig_val);
+ if (new_val
+ && new_val != orig_val
+ && (TREE_CODE (new_val) == SSA_NAME
+ || is_gimple_min_invariant (new_val))
+ && may_propagate_copy (orig_val, new_val))
+ propagate_value (orig_p, new_val);
}
}
}
if (! def
|| TREE_CODE (def) != SSA_NAME
|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
- || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF)
+ || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF)
/* Do not record equivalences for increments of ivs. This would create
overlapping live ranges for a very questionable gain. */
|| simple_iv_increment_p (stmt))
if (cached_lhs
&& ((TREE_CODE (cached_lhs) != SSA_NAME
&& (modify_expr_p
- || tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p),
- TREE_TYPE (cached_lhs))))
+ || useless_type_conversion_p (TREE_TYPE (*expr_p),
+ TREE_TYPE (cached_lhs))))
|| may_propagate_copy (*expr_p, cached_lhs)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
retval = true;
if (modify_expr_p
- && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p),
- TREE_TYPE (cached_lhs)))
+ && !useless_type_conversion_p (TREE_TYPE (*expr_p),
+ TREE_TYPE (cached_lhs)))
cached_lhs = fold_convert (TREE_TYPE (*expr_p), cached_lhs);
propagate_tree_value (expr_p, cached_lhs);
Detect and record those equivalences. */
static void
-record_equivalences_from_stmt (tree stmt,
- int may_optimize_p,
- stmt_ann_t ann)
+record_equivalences_from_stmt (tree stmt, int may_optimize_p, stmt_ann_t ann)
{
tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
enum tree_code lhs_code = TREE_CODE (lhs);
vops and recording the result in the available expression table,
we may be able to expose more redundant loads. */
if (!ann->has_volatile_ops
+ && stmt_references_memory_p (stmt)
&& (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == SSA_NAME
|| is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt, 1)))
&& !is_gimple_reg (lhs))
{
tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
- tree new;
+ tree new_stmt;
/* 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)
{
/* Build a new statement with the RHS and LHS exchanged. */
- new = build2_gimple (GIMPLE_MODIFY_STMT, rhs, lhs);
+ new_stmt = build_gimple_modify_stmt (rhs, lhs);
- create_ssa_artficial_load_stmt (new, stmt);
+ create_ssa_artificial_load_stmt (new_stmt, stmt);
/* Finally enter the statement into the available expression
table. */
- lookup_avail_expr (new, true);
+ lookup_avail_expr (new_stmt, true);
}
}
}
propagation opportunity. */
if (TREE_CODE (val) != SSA_NAME)
{
- if (!lang_hooks.types_compatible_p (op_type, val_type))
+ if (!useless_type_conversion_p (op_type, val_type))
{
val = fold_convert (TREE_TYPE (op), val);
if (!is_gimple_min_invariant (val))
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. */
+ vdef_ops of STMT. */
static bool
cprop_into_stmt (tree stmt)
ann = stmt_ann (stmt);
opt_stats.num_stmts++;
may_have_exposed_new_symbols = false;
+ push_stmt_changes (bsi_stmt_ptr (si));
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_generic_stmt (dump_file, stmt, TDF_SLIM);
}
- /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
+ /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
may_have_exposed_new_symbols = cprop_into_stmt (stmt);
/* If the statement has been modified with constant replacements,
/* Record any additional equivalences created by this statement. */
if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
- record_equivalences_from_stmt (stmt,
- may_optimize_p,
- ann);
+ record_equivalences_from_stmt (stmt, may_optimize_p, ann);
/* If STMT is a COND_EXPR and it was modified, then we may know
where it goes. If that is the case, then mark the CFG as altered.
Ultimately I suspect we're going to need to change the interface
into the SSA_NAME manager. */
-
if (ann->modified)
{
tree val = NULL;
}
if (may_have_exposed_new_symbols)
- VEC_safe_push (tree, heap, stmts_to_rescan, bsi_stmt (si));
+ {
+ /* Queue the statement to be re-scanned after all the
+ AVAIL_EXPRS have been processed. The change buffer stack for
+ all the pushed statements will be processed when this queue
+ is emptied. */
+ VEC_safe_push (tree_p, heap, stmts_to_rescan, bsi_stmt_ptr (si));
+ }
+ else
+ {
+ /* Otherwise, just discard the recently pushed change buffer. If
+ not, the STMTS_TO_RESCAN queue will get out of synch with the
+ change buffer stack. */
+ discard_stmt_changes (bsi_stmt_ptr (si));
+ }
}
/* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
/* In case of a collision, both RHS have to be identical and have the
same VUSE operands. */
- if ((TREE_TYPE (rhs1) == TREE_TYPE (rhs2)
- || lang_hooks.types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2)))
+ if (types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2))
&& operand_equal_p (rhs1, rhs2, OEP_PURE_SAME))
{
bool ret = compare_ssa_operands_equal (stmt1, stmt2, SSA_OP_VUSE);
remove_stmt_or_phi (tree t)
{
if (TREE_CODE (t) == PHI_NODE)
- remove_phi_node (t, NULL);
+ remove_phi_node (t, NULL, true);
else
{
block_stmt_iterator bsi = bsi_for_stmt (t);
bsi_remove (&bsi, true);
+ release_defs (t);
}
}
fprintf (dump_file, "\n");
}
+ push_stmt_changes (&use_stmt);
+
/* Propagate the RHS into this use of the LHS. */
FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
propagate_value (use_p, rhs);
tree result = get_lhs_or_phi_result (use_stmt);
bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
}
+
+ discard_stmt_changes (&use_stmt);
continue;
}
/* Sometimes propagation can expose new operands to the
renamer. Note this will call update_stmt at the
appropriate time. */
- mark_new_vars_to_rename (use_stmt);
+ pop_stmt_changes (&use_stmt);
/* Dump details. */
if (dump_file && (dump_flags & TDF_DETAILS))
te->count += e->count;
remove_edge (e);
- cfg_altered = 1;
+ cfg_altered = true;
}
else
ei_next (&ei);
eliminate_degenerate_phis (void)
{
bitmap interesting_names;
+ bitmap interesting_names1;
/* Bitmap of blocks which need EH information updated. We can not
update it on-the-fly as doing so invalidates the dominator tree. */
Experiments have show we generally get better compilation
time behavior with bitmaps rather than sbitmaps. */
interesting_names = BITMAP_ALLOC (NULL);
+ interesting_names1 = BITMAP_ALLOC (NULL);
+
+ calculate_dominance_info (CDI_DOMINATORS);
+ cfg_altered = false;
/* First phase. Eliminate degenerate PHIs via a dominator
walk of the CFG.
phase in dominator order. Presumably this is because walking
in dominator order leaves fewer PHIs for later examination
by the worklist phase. */
- calculate_dominance_info (CDI_DOMINATORS);
eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
/* Second phase. Eliminate second order degenerate PHIs as well
unsigned int i;
bitmap_iterator bi;
- EXECUTE_IF_SET_IN_BITMAP (interesting_names, 0, i, bi)
+ /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
+ changed during the loop. Copy it to another bitmap and
+ use that. */
+ bitmap_copy (interesting_names1, interesting_names);
+
+ EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
{
tree name = ssa_name (i);
}
}
+ if (cfg_altered)
+ free_dominance_info (CDI_DOMINATORS);
+
/* Propagation of const and copies may make some EH edges dead. Purge
such edges from the CFG as needed. */
if (!bitmap_empty_p (need_eh_cleanup))
{
- cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
+ tree_purge_all_dead_eh_edges (need_eh_cleanup);
BITMAP_FREE (need_eh_cleanup);
}
BITMAP_FREE (interesting_names);
- if (cfg_altered)
- free_dominance_info (CDI_DOMINATORS);
+ BITMAP_FREE (interesting_names1);
return 0;
}
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_cleanup_cfg | TODO_dump_func
- | TODO_ggc_collect | TODO_verify_ssa
- | TODO_verify_stmts | TODO_update_smt_usage
- | TODO_update_ssa, /* todo_flags_finish */
+ TODO_cleanup_cfg
+ | TODO_dump_func
+ | TODO_ggc_collect
+ | TODO_verify_ssa
+ | TODO_verify_stmts
+ | TODO_update_ssa, /* todo_flags_finish */
0 /* letter */
};
OSDN Git Service
