/* SSA Dominator optimizations for trees
- Copyright (C) 2001-2013 Free Software Foundation, Inc.
+ Copyright (C) 2001-2014 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
#include "hash-table.h"
#include "tm.h"
#include "tree.h"
+#include "stor-layout.h"
#include "flags.h"
#include "tm_p.h"
+#include "predict.h"
+#include "vec.h"
+#include "hashtab.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "hard-reg-set.h"
+#include "input.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
#include "basic-block.h"
#include "cfgloop.h"
-#include "function.h"
+#include "inchash.h"
#include "gimple-pretty-print.h"
-#include "tree-flow.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "tree-into-ssa.h"
#include "domwalk.h"
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
+#include "tree-ssa-threadupdate.h"
#include "langhooks.h"
#include "params.h"
+#include "tree-ssa-threadedge.h"
+#include "tree-ssa-dom.h"
+#include "inchash.h"
/* This file implements optimizations on the dominator tree. */
struct expr_elt_hasher
{
- typedef expr_hash_elt value_type;
- typedef expr_hash_elt compare_type;
- static inline hashval_t hash (const value_type *);
- static inline bool equal (const value_type *, const compare_type *);
- static inline void remove (value_type *);
+ typedef expr_hash_elt *value_type;
+ typedef expr_hash_elt *compare_type;
+ typedef int store_values_directly;
+ static inline hashval_t hash (const value_type &);
+ static inline bool equal (const value_type &, const compare_type &);
+ static inline void remove (value_type &);
};
inline hashval_t
-expr_elt_hasher::hash (const value_type *p)
+expr_elt_hasher::hash (const value_type &p)
{
return p->hash;
}
inline bool
-expr_elt_hasher::equal (const value_type *p1, const compare_type *p2)
+expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
{
gimple stmt1 = p1->stmt;
const struct hashable_expr *expr1 = &p1->expr;
/* Delete an expr_hash_elt and reclaim its storage. */
inline void
-expr_elt_hasher::remove (value_type *element)
+expr_elt_hasher::remove (value_type &element)
{
free_expr_hash_elt (element);
}
global redundancy elimination). Similarly as we pass through conditionals
we record the conditional itself as having either a true or false value
in this table. */
-static hash_table <expr_elt_hasher> avail_exprs;
+static hash_table<expr_elt_hasher> *avail_exprs;
/* Stack of dest,src pairs that need to be restored during finalization.
static void optimize_stmt (basic_block, gimple_stmt_iterator);
static tree lookup_avail_expr (gimple, bool);
static hashval_t avail_expr_hash (const void *);
-static void htab_statistics (FILE *, hash_table <expr_elt_hasher>);
+static void htab_statistics (FILE *,
+ const hash_table<expr_elt_hasher> &);
static void record_cond (cond_equivalence *);
static void record_const_or_copy (tree, tree);
static void record_equality (tree, tree);
static void record_equivalences_from_incoming_edge (basic_block);
static void eliminate_redundant_computations (gimple_stmt_iterator *);
static void record_equivalences_from_stmt (gimple, int);
-static void dom_thread_across_edge (struct dom_walk_data *, edge);
-static void dom_opt_leave_block (struct dom_walk_data *, basic_block);
-static void dom_opt_enter_block (struct dom_walk_data *, basic_block);
static void remove_local_expressions_from_table (void);
static void restore_vars_to_original_value (void);
static edge single_incoming_edge_ignoring_loop_edges (basic_block);
case GIMPLE_UNARY_RHS:
expr->kind = EXPR_UNARY;
expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
+ if (CONVERT_EXPR_CODE_P (subcode))
+ subcode = NOP_EXPR;
expr->ops.unary.op = subcode;
expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
break;
expr1->ops.call.args[i], 0))
return false;
+ if (stmt_could_throw_p (expr0->ops.call.fn_from))
+ {
+ int lp0 = lookup_stmt_eh_lp (expr0->ops.call.fn_from);
+ int lp1 = lookup_stmt_eh_lp (expr1->ops.call.fn_from);
+ if ((lp0 > 0 || lp1 > 0) && lp0 != lp1)
+ return false;
+ }
+
return true;
}
}
}
+/* Generate a hash value for a pair of expressions. This can be used
+ iteratively by passing a previous result in HSTATE.
+
+ The same hash value is always returned for a given pair of expressions,
+ regardless of the order in which they are presented. This is useful in
+ hashing the operands of commutative functions. */
+
+namespace inchash
+{
+
+static void
+add_expr_commutative (const_tree t1, const_tree t2, hash &hstate)
+{
+ hash one, two;
+
+ inchash::add_expr (t1, one);
+ inchash::add_expr (t2, two);
+ hstate.add_commutative (one, two);
+}
+
/* Compute a hash value for a hashable_expr value EXPR and a
previously accumulated hash value VAL. If two hashable_expr
values compare equal with hashable_expr_equal_p, they must
hash to the same value, given an identical value of VAL.
- The logic is intended to follow iterative_hash_expr in tree.c. */
+ The logic is intended to follow inchash::add_expr in tree.c. */
-static hashval_t
-iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val)
+static void
+add_hashable_expr (const struct hashable_expr *expr, hash &hstate)
{
switch (expr->kind)
{
case EXPR_SINGLE:
- val = iterative_hash_expr (expr->ops.single.rhs, val);
+ inchash::add_expr (expr->ops.single.rhs, hstate);
break;
case EXPR_UNARY:
- val = iterative_hash_object (expr->ops.unary.op, val);
+ hstate.add_object (expr->ops.unary.op);
/* Make sure to include signedness in the hash computation.
Don't hash the type, that can lead to having nodes which
have different hash codes. */
if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
|| expr->ops.unary.op == NON_LVALUE_EXPR)
- val += TYPE_UNSIGNED (expr->type);
+ hstate.add_int (TYPE_UNSIGNED (expr->type));
- val = iterative_hash_expr (expr->ops.unary.opnd, val);
+ inchash::add_expr (expr->ops.unary.opnd, hstate);
break;
case EXPR_BINARY:
- val = iterative_hash_object (expr->ops.binary.op, val);
+ hstate.add_object (expr->ops.binary.op);
if (commutative_tree_code (expr->ops.binary.op))
- val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0,
- expr->ops.binary.opnd1, val);
+ inchash::add_expr_commutative (expr->ops.binary.opnd0,
+ expr->ops.binary.opnd1, hstate);
else
{
- val = iterative_hash_expr (expr->ops.binary.opnd0, val);
- val = iterative_hash_expr (expr->ops.binary.opnd1, val);
+ inchash::add_expr (expr->ops.binary.opnd0, hstate);
+ inchash::add_expr (expr->ops.binary.opnd1, hstate);
}
break;
case EXPR_TERNARY:
- val = iterative_hash_object (expr->ops.ternary.op, val);
+ hstate.add_object (expr->ops.ternary.op);
if (commutative_ternary_tree_code (expr->ops.ternary.op))
- val = iterative_hash_exprs_commutative (expr->ops.ternary.opnd0,
- expr->ops.ternary.opnd1, val);
+ inchash::add_expr_commutative (expr->ops.ternary.opnd0,
+ expr->ops.ternary.opnd1, hstate);
else
{
- val = iterative_hash_expr (expr->ops.ternary.opnd0, val);
- val = iterative_hash_expr (expr->ops.ternary.opnd1, val);
+ inchash::add_expr (expr->ops.ternary.opnd0, hstate);
+ inchash::add_expr (expr->ops.ternary.opnd1, hstate);
}
- val = iterative_hash_expr (expr->ops.ternary.opnd2, val);
+ inchash::add_expr (expr->ops.ternary.opnd2, hstate);
break;
case EXPR_CALL:
enum tree_code code = CALL_EXPR;
gimple fn_from;
- val = iterative_hash_object (code, val);
+ hstate.add_object (code);
fn_from = expr->ops.call.fn_from;
if (gimple_call_internal_p (fn_from))
- val = iterative_hash_hashval_t
- ((hashval_t) gimple_call_internal_fn (fn_from), val);
+ hstate.merge_hash ((hashval_t) gimple_call_internal_fn (fn_from));
else
- val = iterative_hash_expr (gimple_call_fn (fn_from), val);
+ inchash::add_expr (gimple_call_fn (fn_from), hstate);
for (i = 0; i < expr->ops.call.nargs; i++)
- val = iterative_hash_expr (expr->ops.call.args[i], val);
+ inchash::add_expr (expr->ops.call.args[i], hstate);
}
break;
size_t i;
for (i = 0; i < expr->ops.phi.nargs; i++)
- val = iterative_hash_expr (expr->ops.phi.args[i], val);
+ inchash::add_expr (expr->ops.phi.args[i], hstate);
}
break;
default:
gcc_unreachable ();
}
+}
- return val;
}
/* Print a diagnostic dump of an expression hash table entry. */
break;
case EXPR_UNARY:
- fprintf (stream, "%s ", tree_code_name[element->expr.ops.unary.op]);
+ fprintf (stream, "%s ", get_tree_code_name (element->expr.ops.unary.op));
print_generic_expr (stream, element->expr.ops.unary.opnd, 0);
break;
case EXPR_BINARY:
print_generic_expr (stream, element->expr.ops.binary.opnd0, 0);
- fprintf (stream, " %s ", tree_code_name[element->expr.ops.binary.op]);
+ fprintf (stream, " %s ", get_tree_code_name (element->expr.ops.binary.op));
print_generic_expr (stream, element->expr.ops.binary.opnd1, 0);
break;
case EXPR_TERNARY:
- fprintf (stream, " %s <", tree_code_name[element->expr.ops.ternary.op]);
+ fprintf (stream, " %s <", get_tree_code_name (element->expr.ops.ternary.op));
print_generic_expr (stream, element->expr.ops.ternary.opnd0, 0);
fputs (", ", stream);
print_generic_expr (stream, element->expr.ops.ternary.opnd1, 0);
edge_iterator ei;
edge e;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
FOR_EACH_EDGE (e, ei, bb->preds)
{
}
}
+class dom_opt_dom_walker : public dom_walker
+{
+public:
+ dom_opt_dom_walker (cdi_direction direction)
+ : dom_walker (direction), m_dummy_cond (NULL) {}
+
+ virtual void before_dom_children (basic_block);
+ virtual void after_dom_children (basic_block);
+
+private:
+ void thread_across_edge (edge);
+
+ gimple m_dummy_cond;
+};
+
/* Jump threading, redundancy elimination and const/copy propagation.
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. */
-static unsigned int
-tree_ssa_dominator_optimize (void)
+namespace {
+
+const pass_data pass_data_dominator =
+{
+ GIMPLE_PASS, /* type */
+ "dom", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
+};
+
+class pass_dominator : public gimple_opt_pass
{
- struct dom_walk_data walk_data;
+public:
+ pass_dominator (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_dominator, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ opt_pass * clone () { return new pass_dominator (m_ctxt); }
+ virtual bool gate (function *) { return flag_tree_dom != 0; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_dominator
+unsigned int
+pass_dominator::execute (function *fun)
+{
memset (&opt_stats, 0, sizeof (opt_stats));
/* Create our hash tables. */
- avail_exprs.create (1024);
+ avail_exprs = new hash_table<expr_elt_hasher> (1024);
avail_exprs_stack.create (20);
const_and_copies_stack.create (20);
need_eh_cleanup = BITMAP_ALLOC (NULL);
- /* Setup callbacks for the generic dominator tree walker. */
- walk_data.dom_direction = CDI_DOMINATORS;
- walk_data.initialize_block_local_data = NULL;
- walk_data.before_dom_children = dom_opt_enter_block;
- walk_data.after_dom_children = dom_opt_leave_block;
- /* Right now we only attach a dummy COND_EXPR to the global data pointer.
- When we attach more stuff we'll need to fill this out with a real
- structure. */
- walk_data.global_data = NULL;
- walk_data.block_local_data_size = 0;
-
- /* Now initialize the dominator walker. */
- init_walk_dominator_tree (&walk_data);
-
calculate_dominance_info (CDI_DOMINATORS);
cfg_altered = false;
/* 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);
+ that we update the loop info.
+
+ TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
+ to several overly conservative bail-outs in jump threading, case
+ gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
+ missing. We should improve jump threading in future then
+ LOOPS_HAVE_PREHEADERS won't be needed here. */
+ loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
/* Initialize the value-handle array. */
threadedge_initialize_values ();
mark_dfs_back_edges ();
/* Recursively walk the dominator tree optimizing statements. */
- walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+ dom_opt_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
{
gimple_stmt_iterator gsi;
basic_block bb;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, fun)
{
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
update_stmt_if_modified (gsi_stmt (gsi));
iterator. */
EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
{
- basic_block bb = BASIC_BLOCK (i);
+ basic_block bb = BASIC_BLOCK_FOR_FN (fun, i);
if (bb == NULL)
continue;
while (single_succ_p (bb)
&& (single_succ_edge (bb)->flags & EDGE_EH) == 0)
bb = single_succ (bb);
- if (bb == EXIT_BLOCK_PTR)
+ if (bb == EXIT_BLOCK_PTR_FOR_FN (fun))
continue;
if ((unsigned) bb->index != i)
bitmap_set_bit (need_eh_cleanup, bb->index);
bitmap_clear (need_eh_cleanup);
}
- statistics_counter_event (cfun, "Redundant expressions eliminated",
+ statistics_counter_event (fun, "Redundant expressions eliminated",
opt_stats.num_re);
- statistics_counter_event (cfun, "Constants propagated",
+ statistics_counter_event (fun, "Constants propagated",
opt_stats.num_const_prop);
- statistics_counter_event (cfun, "Copies propagated",
+ statistics_counter_event (fun, "Copies propagated",
opt_stats.num_copy_prop);
/* Debugging dumps. */
loop_optimizer_finalize ();
/* Delete our main hashtable. */
- avail_exprs.dispose ();
-
- /* And finalize the dominator walker. */
- fini_walk_dominator_tree (&walk_data);
+ delete avail_exprs;
+ avail_exprs = NULL;
/* Free asserted bitmaps and stacks. */
BITMAP_FREE (need_eh_cleanup);
/* Free the value-handle array. */
threadedge_finalize_values ();
- ssa_name_values.release ();
return 0;
}
-static bool
-gate_dominator (void)
-{
- return flag_tree_dom != 0;
-}
-
-namespace {
-
-const pass_data pass_data_dominator =
-{
- GIMPLE_PASS, /* type */
- "dom", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
- TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
- ( PROP_cfg | PROP_ssa ), /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- ( TODO_cleanup_cfg | TODO_update_ssa
- | TODO_verify_ssa
- | TODO_verify_flow ), /* todo_flags_finish */
-};
-
-class pass_dominator : public gimple_opt_pass
-{
-public:
- pass_dominator(gcc::context *ctxt)
- : gimple_opt_pass(pass_data_dominator, ctxt)
- {}
-
- /* opt_pass methods: */
- opt_pass * clone () { return new pass_dominator (ctxt_); }
- bool gate () { return gate_dominator (); }
- unsigned int execute () { return tree_ssa_dominator_optimize (); }
-
-}; // class pass_dominator
-
} // anon namespace
gimple_opt_pass *
print_expr_hash_elt (dump_file, victim);
}
- slot = avail_exprs.find_slot_with_hash (victim, victim->hash, NO_INSERT);
+ slot = avail_exprs->find_slot (victim, NO_INSERT);
gcc_assert (slot && *slot == victim);
- avail_exprs.clear_slot (slot);
+ avail_exprs->clear_slot (slot);
}
}
return lookup_avail_expr (stmt, false);
}
+/* Record into the equivalence tables any equivalences implied by
+ traversing edge E (which are cached in E->aux).
+
+ Callers are responsible for managing the unwinding markers. */
+static void
+record_temporary_equivalences (edge e)
+{
+ int i;
+ struct edge_info *edge_info = (struct edge_info *) e->aux;
+
+ /* If we have info associated with this edge, record it into
+ our equivalence tables. */
+ if (edge_info)
+ {
+ cond_equivalence *eq;
+ tree lhs = edge_info->lhs;
+ tree rhs = edge_info->rhs;
+
+ /* If we have a simple NAME = VALUE equivalence, record it. */
+ if (lhs && TREE_CODE (lhs) == SSA_NAME)
+ record_const_or_copy (lhs, rhs);
+
+ /* If we have 0 = COND or 1 = COND equivalences, record them
+ into our expression hash tables. */
+ for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
+ record_cond (eq);
+ }
+}
+
/* Wrapper for common code to attempt to thread an edge. For example,
it handles lazily building the dummy condition and the bookkeeping
when jump threading is successful. */
-static void
-dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)
+void
+dom_opt_dom_walker::thread_across_edge (edge e)
{
- if (! walk_data->global_data)
- {
- gimple dummy_cond =
+ if (! m_dummy_cond)
+ m_dummy_cond =
gimple_build_cond (NE_EXPR,
integer_zero_node, integer_zero_node,
NULL, NULL);
- walk_data->global_data = dummy_cond;
- }
- thread_across_edge ((gimple) walk_data->global_data, e, false,
- &const_and_copies_stack,
- simplify_stmt_for_jump_threading);
+ /* Push a marker on both stacks so we can unwind the tables back to their
+ current state. */
+ avail_exprs_stack.safe_push (NULL);
+ const_and_copies_stack.safe_push (NULL_TREE);
+
+ /* Traversing E may result in equivalences we can utilize. */
+ record_temporary_equivalences (e);
+
+ /* With all the edge equivalences in the tables, go ahead and attempt
+ to thread through E->dest. */
+ ::thread_across_edge (m_dummy_cond, e, false,
+ &const_and_copies_stack,
+ simplify_stmt_for_jump_threading);
+
+ /* And restore the various tables to their state before
+ we threaded this edge.
+
+ XXX The code in tree-ssa-threadedge.c will restore the state of
+ the const_and_copies table. We we just have to restore the expression
+ table. */
+ remove_local_expressions_from_table ();
}
/* PHI nodes can create equivalences too.
this, since this is a true 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 (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs))
+ if (i == gimple_phi_num_args (phi)
+ && may_propagate_copy (lhs, rhs))
set_ssa_name_value (lhs, rhs);
}
}
/* If the conversion widens the original value and
the constant is in the range of the type of OLD_RHS,
- then convert the constant and record the equivalence.
+ then convert the constant and record the equivalence.
Note that int_fits_type_p does not check the precision
if the upper and lower bounds are OK. */
fprintf (file, "\nHash table statistics:\n");
fprintf (file, " avail_exprs: ");
- htab_statistics (file, avail_exprs);
+ htab_statistics (file, *avail_exprs);
}
/* Dump statistics for the hash table HTAB. */
static void
-htab_statistics (FILE *file, hash_table <expr_elt_hasher> htab)
+htab_statistics (FILE *file, const hash_table<expr_elt_hasher> &htab)
{
fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
(long) htab.size (),
initialize_hash_element_from_expr (&p->cond, p->value, element);
- slot = avail_exprs.find_slot_with_hash (element, element->hash, INSERT);
+ slot = avail_exprs->find_slot_with_hash (element, element->hash, INSERT);
if (*slot == NULL)
{
*slot = element;
const_and_copies_stack.quick_push (x);
}
+/* Record that X is equal to Y in const_and_copies. Record undo
+ information in the block-local vector. */
+
+static void
+record_const_or_copy (tree x, tree y)
+{
+ tree prev_x = SSA_NAME_VALUE (x);
+
+ gcc_assert (TREE_CODE (x) == SSA_NAME);
+
+ if (TREE_CODE (y) == SSA_NAME)
+ {
+ tree tmp = SSA_NAME_VALUE (y);
+ if (tmp)
+ y = tmp;
+ }
+
+ record_const_or_copy_1 (x, y, prev_x);
+}
+
/* Return the loop depth of the basic block of the defining statement of X.
This number should not be treated as absolutely correct because the loop
information may not be completely up-to-date when dom runs. However, it
will be relatively correct, and as more passes are taught to keep loop info
up to date, the result will become more and more accurate. */
-int
+static int
loop_depth_of_name (tree x)
{
gimple defstmt;
return bb_loop_depth (defbb);
}
-/* Record that X is equal to Y in const_and_copies. Record undo
- information in the block-local vector. */
-
-static void
-record_const_or_copy (tree x, tree y)
-{
- tree prev_x = SSA_NAME_VALUE (x);
-
- gcc_assert (TREE_CODE (x) == SSA_NAME);
-
- if (TREE_CODE (y) == SSA_NAME)
- {
- tree tmp = SSA_NAME_VALUE (y);
- if (tmp)
- y = tmp;
- }
-
- record_const_or_copy_1 (x, y, prev_x);
-}
-
/* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
This constrains the cases in which we may treat this as assignment. */
if (is_gimple_min_invariant (y))
;
else if (is_gimple_min_invariant (x)
+ /* ??? When threading over backedges the following is important
+ for correctness. See PR61757. */
|| (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 && is_gimple_min_invariant (prev_x))
table back to its original state after processing this edge. */
const_and_copies_stack.safe_push (NULL_TREE);
- /* Extract and record any simple NAME = VALUE equivalences.
+ /* Extract and record any simple NAME = VALUE equivalences.
Don't bother with [01] = COND equivalences, they're not useful
here. */
{
int i;
int n_labels = gimple_switch_num_labels (stmt);
- tree *info = XCNEWVEC (tree, last_basic_block);
+ tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
edge e;
edge_iterator ei;
}
}
-static void
-dom_opt_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
- basic_block bb)
+void
+dom_opt_dom_walker::before_dom_children (basic_block bb)
{
gimple_stmt_iterator gsi;
any finalization actions in preparation for leaving this node in
the dominator tree. */
-static void
-dom_opt_leave_block (struct dom_walk_data *walk_data, basic_block bb)
+void
+dom_opt_dom_walker::after_dom_children (basic_block bb)
{
gimple last;
&& (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
&& potentially_threadable_block (single_succ (bb)))
{
- /* Push a marker on the stack, which thread_across_edge expects
- and will remove. */
- const_and_copies_stack.safe_push (NULL_TREE);
- dom_thread_across_edge (walk_data, single_succ_edge (bb));
+ thread_across_edge (single_succ_edge (bb));
}
else if ((last = last_stmt (bb))
&& gimple_code (last) == GIMPLE_COND
/* Only try to thread the edge if it reaches a target block with
more than one predecessor and more than one successor. */
if (potentially_threadable_block (true_edge->dest))
- {
- struct edge_info *edge_info;
- unsigned int i;
-
- /* Push a marker onto the available expression stack so that we
- unwind any expressions related to the TRUE arm before processing
- the false arm below. */
- avail_exprs_stack.safe_push (NULL);
- const_and_copies_stack.safe_push (NULL_TREE);
-
- edge_info = (struct edge_info *) true_edge->aux;
-
- /* If we have info associated with this edge, record it into
- our equivalence tables. */
- if (edge_info)
- {
- cond_equivalence *eq;
- tree lhs = edge_info->lhs;
- tree rhs = edge_info->rhs;
-
- /* If we have a simple NAME = VALUE equivalence, record it. */
- if (lhs && TREE_CODE (lhs) == SSA_NAME)
- record_const_or_copy (lhs, rhs);
-
- /* If we have 0 = COND or 1 = COND equivalences, record them
- into our expression hash tables. */
- for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
- record_cond (eq);
- }
-
- dom_thread_across_edge (walk_data, true_edge);
-
- /* And restore the various tables to their state before
- we threaded this edge. */
- remove_local_expressions_from_table ();
- }
+ thread_across_edge (true_edge);
/* Similarly for the ELSE arm. */
if (potentially_threadable_block (false_edge->dest))
- {
- struct edge_info *edge_info;
- unsigned int i;
-
- const_and_copies_stack.safe_push (NULL_TREE);
- edge_info = (struct edge_info *) false_edge->aux;
-
- /* If we have info associated with this edge, record it into
- our equivalence tables. */
- if (edge_info)
- {
- cond_equivalence *eq;
- tree lhs = edge_info->lhs;
- tree rhs = edge_info->rhs;
-
- /* If we have a simple NAME = VALUE equivalence, record it. */
- if (lhs && TREE_CODE (lhs) == SSA_NAME)
- record_const_or_copy (lhs, rhs);
-
- /* If we have 0 = COND or 1 = COND equivalences, record them
- into our expression hash tables. */
- for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
- record_cond (eq);
- }
-
- /* Now thread the edge. */
- dom_thread_across_edge (walk_data, false_edge);
+ thread_across_edge (false_edge);
- /* No need to remove local expressions from our tables
- or restore vars to their original value as that will
- be done immediately below. */
- }
}
+ /* These remove expressions local to BB from the tables. */
remove_local_expressions_from_table ();
restore_vars_to_original_value ();
}
if (!may_propagate_copy (op, val))
return;
- /* Do not propagate addresses that point to volatiles into memory
- stmts without volatile operands. */
- if (POINTER_TYPE_P (TREE_TYPE (val))
- && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val)))
- && gimple_has_mem_ops (stmt)
- && !gimple_has_volatile_ops (stmt))
- return;
-
- /* Do not propagate copies if the propagated value is at a deeper loop
- depth than the propagatee. Otherwise, this may move loop variant
- variables outside of their loops and prevent coalescing
- opportunities. If the value was loop invariant, it will be hoisted
- by LICM and exposed for copy propagation. */
- if (loop_depth_of_name (val) > loop_depth_of_name (op))
- return;
-
/* Do not propagate copies into simple IV increment statements.
See PR23821 for how this can disturb IV analysis. */
if (TREE_CODE (val) != INTEGER_CST
return NULL_TREE;
/* Finally try to find the expression in the main expression hash table. */
- slot = avail_exprs.find_slot_with_hash (&element, element.hash,
- (insert ? INSERT : NO_INSERT));
+ slot = avail_exprs->find_slot (&element, (insert ? INSERT : NO_INSERT));
if (slot == NULL)
{
free_expr_hash_elt_contents (&element);
gimple stmt = ((const struct expr_hash_elt *)p)->stmt;
const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr;
tree vuse;
- hashval_t val = 0;
+ inchash::hash hstate;
- val = iterative_hash_hashable_expr (expr, val);
+ inchash::add_hashable_expr (expr, hstate);
/* If the hash table entry is not associated with a statement, then we
can just hash the expression and not worry about virtual operands
and such. */
if (!stmt)
- return val;
+ return hstate.end ();
/* Add the SSA version numbers of the vuse operand. This is important
because compound variables like arrays are not renamed in the
operands. Rather, the rename is done on the virtual variable
representing all the elements of the array. */
if ((vuse = gimple_vuse (stmt)))
- val = iterative_hash_expr (vuse, val);
+ inchash::add_expr (vuse, hstate);
- return val;
+ return hstate.end ();
}
/* PHI-ONLY copy and constant propagation. This pass is meant to clean
up degenerate PHIs created by or exposed by jump threading. */
-/* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
- NULL. */
-
-tree
-degenerate_phi_result (gimple phi)
-{
- tree lhs = gimple_phi_result (phi);
- tree val = NULL;
- size_t i;
-
- /* Ignoring arguments which are the same as LHS, if all the remaining
- arguments are the same, then the PHI is a degenerate and has the
- value of that common argument. */
- for (i = 0; i < gimple_phi_num_args (phi); i++)
- {
- tree arg = gimple_phi_arg_def (phi, i);
-
- if (arg == lhs)
- continue;
- else if (!arg)
- break;
- else if (!val)
- val = arg;
- else if (arg == val)
- continue;
- /* We bring in some of operand_equal_p not only to speed things
- up, but also to avoid crashing when dereferencing the type of
- a released SSA name. */
- else if (TREE_CODE (val) != TREE_CODE (arg)
- || TREE_CODE (val) == SSA_NAME
- || !operand_equal_p (arg, val, 0))
- break;
- }
- return (i == gimple_phi_num_args (phi) ? val : NULL);
-}
-
/* Given a statement STMT, which is either a PHI node or an assignment,
remove it from the IL. */
static void
propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names)
{
- /* First verify that propagation is valid and isn't going to move a
- loop variant variable outside its loop. */
- if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
- && (TREE_CODE (rhs) != SSA_NAME
- || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
- && may_propagate_copy (lhs, rhs)
- && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
+ /* First verify that propagation is valid. */
+ if (may_propagate_copy (lhs, rhs))
{
use_operand_p use_p;
imm_use_iterator iter;
pick up the secondary optimization opportunities with minimal
cost. */
-static unsigned int
-eliminate_degenerate_phis (void)
+namespace {
+
+const pass_data pass_data_phi_only_cprop =
+{
+ GIMPLE_PASS, /* type */
+ "phicprop", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_PHI_CPROP, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
+};
+
+class pass_phi_only_cprop : public gimple_opt_pass
+{
+public:
+ pass_phi_only_cprop (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_phi_only_cprop, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ opt_pass * clone () { return new pass_phi_only_cprop (m_ctxt); }
+ virtual bool gate (function *) { return flag_tree_dom != 0; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_phi_only_cprop
+
+unsigned int
+pass_phi_only_cprop::execute (function *fun)
{
bitmap interesting_names;
bitmap interesting_names1;
phase in dominator order. Presumably this is because walking
in dominator order leaves fewer PHIs for later examination
by the worklist phase. */
- eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
+ eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR_FOR_FN (fun),
+ interesting_names);
/* Second phase. Eliminate second order degenerate PHIs as well
as trivial copies or constant initializations identified by
{
free_dominance_info (CDI_DOMINATORS);
/* If we changed the CFG schedule loops for fixup by cfgcleanup. */
- if (current_loops)
- loops_state_set (LOOPS_NEED_FIXUP);
+ loops_state_set (LOOPS_NEED_FIXUP);
}
/* Propagation of const and copies may make some EH edges dead. Purge
return 0;
}
-namespace {
-
-const pass_data pass_data_phi_only_cprop =
-{
- GIMPLE_PASS, /* type */
- "phicprop", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
- TV_TREE_PHI_CPROP, /* tv_id */
- ( PROP_cfg | PROP_ssa ), /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- ( TODO_cleanup_cfg | TODO_verify_ssa
- | TODO_verify_stmts
- | TODO_update_ssa ), /* todo_flags_finish */
-};
-
-class pass_phi_only_cprop : public gimple_opt_pass
-{
-public:
- pass_phi_only_cprop(gcc::context *ctxt)
- : gimple_opt_pass(pass_data_phi_only_cprop, ctxt)
- {}
-
- /* opt_pass methods: */
- opt_pass * clone () { return new pass_phi_only_cprop (ctxt_); }
- bool gate () { return gate_dominator (); }
- unsigned int execute () { return eliminate_degenerate_phis (); }
-
-}; // class pass_phi_only_cprop
-
} // anon namespace
gimple_opt_pass *
projects / gcc.git / blobdiff