/* SSA Dominator optimizations for trees
- Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
+the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful,
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to
-the Free Software Foundation, 51 Franklin Street, Fifth Floor,
-Boston, MA 02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
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 edges 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);
+ unsigned i;
+ bitmap_iterator bi;
+
+ /* Jump threading may have created forwarder blocks from blocks
+ needing EH cleanup; the new successor of these blocks, which
+ has inherited from the original block, needs the cleanup. */
+ EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ if (single_succ_p (bb) == 1
+ && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
+ {
+ bitmap_clear_bit (need_eh_cleanup, i);
+ bitmap_set_bit (need_eh_cleanup, single_succ (bb)->index);
+ }
+ }
+
+ 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
SSA_NAME_VALUE (name) = NULL;
}
+ statistics_counter_event (cfun, "Redundant expressions eliminated",
+ opt_stats.num_re);
+ statistics_counter_event (cfun, "Constants propagated",
+ opt_stats.num_const_prop);
+ statistics_counter_event (cfun, "Copies propagated",
+ opt_stats.num_copy_prop);
+
/* Debugging dumps. */
if (dump_file && (dump_flags & TDF_STATS))
dump_dominator_optimization_stats (dump_file);
+ loop_optimizer_finalize ();
+
/* Delete our main hashtable. */
htab_delete (avail_exprs);
return flag_tree_dom != 0;
}
-struct tree_opt_pass pass_dominator =
+struct gimple_opt_pass pass_dominator =
{
+ {
+ GIMPLE_PASS,
"dom", /* name */
gate_dominator, /* gate */
tree_ssa_dominator_optimize, /* execute */
TODO_dump_func
| TODO_update_ssa
| TODO_cleanup_cfg
- | TODO_verify_ssa
- | TODO_update_smt_usage, /* todo_flags_finish */
- 0 /* letter */
+ | TODO_verify_ssa /* todo_flags_finish */
+ }
};
/* 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 have an outgoing edge to a block with multiple incoming and
- outgoing edges, then we may be able to thread the edge. ie, we
+ outgoing edges, then we may be able to thread the edge, i.e., we
may be able to statically determine which of the outgoing edges
will be traversed when the incoming edge from BB is traversed. */
if (single_succ_p (bb)
void
dump_dominator_optimization_stats (FILE *file)
{
- long n_exprs;
-
fprintf (file, "Total number of statements: %6ld\n\n",
opt_stats.num_stmts);
fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
opt_stats.num_exprs_considered);
- n_exprs = opt_stats.num_exprs_considered;
- if (n_exprs == 0)
- n_exprs = 1;
-
- fprintf (file, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
- opt_stats.num_re, PERCENT (opt_stats.num_re,
- n_exprs));
- fprintf (file, " Constants propagated: %6ld\n",
- opt_stats.num_const_prop);
- fprintf (file, " Copies propagated: %6ld\n",
- opt_stats.num_copy_prop);
-
fprintf (file, "\nHash table statistics:\n");
fprintf (file, " avail_exprs: ");
(by depth), then use that.
Otherwise it doesn't matter which value we choose, just so
long as we canonicalize on one value. */
- if (TREE_INVARIANT (y))
+ if (is_gimple_min_invariant (y))
;
- else if (TREE_INVARIANT (x) || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
+ else if (is_gimple_min_invariant (x)
+ || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
prev_x = x, x = y, y = prev_x, prev_x = prev_y;
- else if (prev_x && TREE_INVARIANT (prev_x))
+ else if (prev_x && is_gimple_min_invariant (prev_x))
x = y, y = prev_x, prev_x = prev_y;
else if (prev_y && TREE_CODE (prev_y) != VALUE_HANDLE)
y = prev_y;
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);
}
}
}
tree op1 = TREE_OPERAND (cond, 1);
/* Special case comparing booleans against a constant as we
- know the value of OP0 on both arms of the branch. i.e., we
+ know the value of OP0 on both arms of the branch, i.e., we
can record an equivalence for OP0 rather than COND. */
if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
&& TREE_CODE (op0) == SSA_NAME
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);
&& !is_gimple_reg (lhs))
{
tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
- tree new;
-
- /* 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
- type of the LHS. If the LHS is a bitfield and the RHS is not
- a constant, then we can not record any equivalences for this
- statement since we would need to represent the widening or
- narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
- and should not be necessary if GCC represented bitfields
- properly. */
- if (lhs_code == COMPONENT_REF
- && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
- {
- if (TREE_CONSTANT (rhs))
- rhs = widen_bitfield (rhs, TREE_OPERAND (lhs, 1), lhs);
- else
- rhs = NULL;
-
- /* If the value overflowed, then we can not use this equivalence. */
- if (rhs && ! is_gimple_min_invariant (rhs))
- rhs = NULL;
- }
-
- if (rhs)
- {
- /* Build a new statement with the RHS and LHS exchanged. */
- new = build2_gimple (GIMPLE_MODIFY_STMT, rhs, lhs);
+ tree new_stmt;
- create_ssa_artificial_load_stmt (new, stmt);
+ /* Build a new statement with the RHS and LHS exchanged. */
+ new_stmt = build_gimple_modify_stmt (rhs, lhs);
+ create_ssa_artificial_load_stmt (new_stmt, stmt, true);
- /* Finally enter the statement into the available expression
- table. */
- lookup_avail_expr (new, true);
- }
+ /* Finally enter the statement into the available expression
+ table. */
+ 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))
static hashval_t
avail_expr_hash (const void *p)
{
- tree stmt = ((struct expr_hash_elt *)p)->stmt;
- tree rhs = ((struct expr_hash_elt *)p)->rhs;
+ tree stmt = ((const struct expr_hash_elt *)p)->stmt;
+ tree rhs = ((const struct expr_hash_elt *)p)->rhs;
tree vuse;
ssa_op_iter iter;
hashval_t val = 0;
static int
avail_expr_eq (const void *p1, const void *p2)
{
- tree stmt1 = ((struct expr_hash_elt *)p1)->stmt;
- tree rhs1 = ((struct expr_hash_elt *)p1)->rhs;
- tree stmt2 = ((struct expr_hash_elt *)p2)->stmt;
- tree rhs2 = ((struct expr_hash_elt *)p2)->rhs;
+ tree stmt1 = ((const struct expr_hash_elt *)p1)->stmt;
+ tree rhs1 = ((const struct expr_hash_elt *)p1)->rhs;
+ tree stmt2 = ((const struct expr_hash_elt *)p2)->stmt;
+ tree rhs2 = ((const struct expr_hash_elt *)p2)->rhs;
/* If they are the same physical expression, return true. */
if (rhs1 == rhs2 && stmt1 == stmt2)
/* 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);
- gcc_assert (!ret || ((struct expr_hash_elt *)p1)->hash
- == ((struct expr_hash_elt *)p2)->hash);
+ gcc_assert (!ret || ((const struct expr_hash_elt *)p1)->hash
+ == ((const struct expr_hash_elt *)p2)->hash);
return ret;
}
te->count += e->count;
remove_edge (e);
- cfg_altered = 1;
+ cfg_altered = true;
}
else
ei_next (&ei);
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
}
}
+ 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);
BITMAP_FREE (interesting_names1);
- if (cfg_altered)
- free_dominance_info (CDI_DOMINATORS);
return 0;
}
-struct tree_opt_pass pass_phi_only_cprop =
+struct gimple_opt_pass pass_phi_only_cprop =
{
+ {
+ GIMPLE_PASS,
"phicprop", /* name */
gate_dominator, /* gate */
eliminate_degenerate_phis, /* execute */
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 */
- 0 /* letter */
+ TODO_cleanup_cfg
+ | TODO_dump_func
+ | TODO_ggc_collect
+ | TODO_verify_ssa
+ | TODO_verify_stmts
+ | TODO_update_ssa /* todo_flags_finish */
+ }
};
OSDN Git Service
