/* SSA Dominator optimizations for trees
- Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
- 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 "config.h"
#include "system.h"
#include "coretypes.h"
+#include "hash-table.h"
#include "tm.h"
#include "tree.h"
+#include "stor-layout.h"
#include "flags.h"
-#include "rtl.h"
#include "tm_p.h"
-#include "ggc.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 "output.h"
-#include "expr.h"
-#include "function.h"
-#include "diagnostic.h"
-#include "timevar.h"
-#include "tree-dump.h"
-#include "tree-flow.h"
+#include "inchash.h"
+#include "gimple-pretty-print.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 "real.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. */
EXPR_SINGLE,
EXPR_UNARY,
EXPR_BINARY,
- EXPR_CALL
+ EXPR_TERNARY,
+ EXPR_CALL,
+ EXPR_PHI
};
struct hashable_expr
union {
struct { tree rhs; } single;
struct { enum tree_code op; tree opnd; } unary;
- struct { enum tree_code op; tree opnd0; tree opnd1; } binary;
- struct { tree fn; bool pure; size_t nargs; tree *args; } call;
+ struct { enum tree_code op; tree opnd0, opnd1; } binary;
+ struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary;
+ struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call;
+ struct { size_t nargs; tree *args; } phi;
} ops;
};
/* Structure for recording known values of a conditional expression
at the exits from its block. */
-struct cond_equivalence
+typedef struct cond_equivalence_s
{
struct hashable_expr cond;
tree value;
-};
+} cond_equivalence;
+
/* Structure for recording edge equivalences as well as any pending
edge redirections during the dominator optimizer.
Computing and storing the edge equivalences instead of creating
them on-demand can save significant amounts of time, particularly
- for pathological cases involving switch statements.
+ for pathological cases involving switch statements.
These structures live for a single iteration of the dominator
optimizer in the edge's AUX field. At the end of an iteration we
tree rhs;
/* Traversing an edge may also indicate one or more particular conditions
- are true or false. The number of recorded conditions can vary, but
- can be determined by the condition's code. So we have an array
- and its maximum index rather than use a varray. */
- struct cond_equivalence *cond_equivalences;
- unsigned int max_cond_equivalences;
+ are true or false. */
+ vec<cond_equivalence> cond_equivalences;
};
-/* Hash table with expressions made available during the renaming process.
- When an assignment of the form X_i = EXPR is found, the statement is
- stored in this table. If the same expression EXPR is later found on the
- RHS of another statement, it is replaced with X_i (thus performing
- 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 htab_t avail_exprs;
-
/* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
expressions it enters into the hash table along with a marker entry
(null). When we finish processing the block, we pop off entries and
remove the expressions from the global hash table until we hit the
marker. */
typedef struct expr_hash_elt * expr_hash_elt_t;
-DEF_VEC_P(expr_hash_elt_t);
-DEF_VEC_ALLOC_P(expr_hash_elt_t,heap);
-static VEC(expr_hash_elt_t,heap) *avail_exprs_stack;
+static vec<expr_hash_elt_t> avail_exprs_stack;
/* Structure for entries in the expression hash table. */
struct expr_hash_elt *stamp;
};
+/* Hashtable helpers. */
+
+static bool hashable_expr_equal_p (const struct hashable_expr *,
+ const struct hashable_expr *);
+static void free_expr_hash_elt (void *);
+
+struct expr_elt_hasher
+{
+ 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)
+{
+ return p->hash;
+}
+
+inline bool
+expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
+{
+ gimple stmt1 = p1->stmt;
+ const struct hashable_expr *expr1 = &p1->expr;
+ const struct expr_hash_elt *stamp1 = p1->stamp;
+ gimple stmt2 = p2->stmt;
+ const struct hashable_expr *expr2 = &p2->expr;
+ const struct expr_hash_elt *stamp2 = p2->stamp;
+
+ /* This case should apply only when removing entries from the table. */
+ if (stamp1 == stamp2)
+ return true;
+
+ /* FIXME tuples:
+ We add stmts to a hash table and them modify them. To detect the case
+ that we modify a stmt and then search for it, we assume that the hash
+ is always modified by that change.
+ We have to fully check why this doesn't happen on trunk or rewrite
+ this in a more reliable (and easier to understand) way. */
+ if (((const struct expr_hash_elt *)p1)->hash
+ != ((const struct expr_hash_elt *)p2)->hash)
+ return false;
+
+ /* In case of a collision, both RHS have to be identical and have the
+ same VUSE operands. */
+ if (hashable_expr_equal_p (expr1, expr2)
+ && types_compatible_p (expr1->type, expr2->type))
+ {
+ /* Note that STMT1 and/or STMT2 may be NULL. */
+ return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE)
+ == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE));
+ }
+
+ return false;
+}
+
+/* Delete an expr_hash_elt and reclaim its storage. */
+
+inline void
+expr_elt_hasher::remove (value_type &element)
+{
+ free_expr_hash_elt (element);
+}
+
+/* Hash table with expressions made available during the renaming process.
+ When an assignment of the form X_i = EXPR is found, the statement is
+ stored in this table. If the same expression EXPR is later found on the
+ RHS of another statement, it is replaced with X_i (thus performing
+ 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;
+
/* Stack of dest,src pairs that need to be restored during finalization.
A NULL entry is used to mark the end of pairs which need to be
restored during finalization of this block. */
-static VEC(tree,heap) *const_and_copies_stack;
+static vec<tree> const_and_copies_stack;
/* Track whether or not we have changed the control flow graph. */
static bool cfg_altered;
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 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 (struct cond_equivalence *);
+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_phis (basic_block);
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);
{
enum tree_code subcode = gimple_assign_rhs_code (stmt);
- expr->type = NULL_TREE;
-
switch (get_gimple_rhs_class (subcode))
{
case GIMPLE_SINGLE_RHS:
- expr->kind = EXPR_SINGLE;
- expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
- break;
+ expr->kind = EXPR_SINGLE;
+ expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt));
+ expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
+ break;
case GIMPLE_UNARY_RHS:
- expr->kind = EXPR_UNARY;
+ expr->kind = EXPR_UNARY;
expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
- expr->ops.unary.op = subcode;
- expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
- break;
+ if (CONVERT_EXPR_CODE_P (subcode))
+ subcode = NOP_EXPR;
+ expr->ops.unary.op = subcode;
+ expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
+ break;
case GIMPLE_BINARY_RHS:
- expr->kind = EXPR_BINARY;
+ expr->kind = EXPR_BINARY;
+ expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
+ expr->ops.binary.op = subcode;
+ expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
+ expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
+ break;
+ case GIMPLE_TERNARY_RHS:
+ expr->kind = EXPR_TERNARY;
expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
- expr->ops.binary.op = subcode;
- expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
- expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
- break;
+ expr->ops.ternary.op = subcode;
+ expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt);
+ expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt);
+ expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt);
+ break;
default:
gcc_unreachable ();
}
expr->type = TREE_TYPE (gimple_call_lhs (stmt));
expr->kind = EXPR_CALL;
- expr->ops.call.fn = gimple_call_fn (stmt);
+ expr->ops.call.fn_from = stmt;
if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
expr->ops.call.pure = true;
- else
+ else
expr->ops.call.pure = false;
expr->ops.call.nargs = nargs;
- expr->ops.call.args = (tree *) xcalloc (nargs, sizeof (tree));
+ expr->ops.call.args = XCNEWVEC (tree, nargs);
for (i = 0; i < nargs; i++)
expr->ops.call.args[i] = gimple_call_arg (stmt, i);
}
expr->kind = EXPR_SINGLE;
expr->ops.single.rhs = gimple_goto_dest (stmt);
}
+ else if (code == GIMPLE_PHI)
+ {
+ size_t nargs = gimple_phi_num_args (stmt);
+ size_t i;
+
+ expr->type = TREE_TYPE (gimple_phi_result (stmt));
+ expr->kind = EXPR_PHI;
+ expr->ops.phi.nargs = nargs;
+ expr->ops.phi.args = XCNEWVEC (tree, nargs);
+
+ for (i = 0; i < nargs; i++)
+ expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
+ }
else
gcc_unreachable ();
initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
{
expr->type = boolean_type_node;
-
+
if (COMPARISON_CLASS_P (cond))
{
expr->kind = EXPR_BINARY;
expr1->ops.unary.opnd, 0);
case EXPR_BINARY:
- {
- if (expr0->ops.binary.op != expr1->ops.binary.op)
- return false;
-
- if (operand_equal_p (expr0->ops.binary.opnd0,
- expr1->ops.binary.opnd0, 0)
- && operand_equal_p (expr0->ops.binary.opnd1,
- expr1->ops.binary.opnd1, 0))
- return true;
-
- /* For commutative ops, allow the other order. */
- return (commutative_tree_code (expr0->ops.binary.op)
- && operand_equal_p (expr0->ops.binary.opnd0,
- expr1->ops.binary.opnd1, 0)
- && operand_equal_p (expr0->ops.binary.opnd1,
- expr1->ops.binary.opnd0, 0));
- }
+ if (expr0->ops.binary.op != expr1->ops.binary.op)
+ return false;
+
+ if (operand_equal_p (expr0->ops.binary.opnd0,
+ expr1->ops.binary.opnd0, 0)
+ && operand_equal_p (expr0->ops.binary.opnd1,
+ expr1->ops.binary.opnd1, 0))
+ return true;
+
+ /* For commutative ops, allow the other order. */
+ return (commutative_tree_code (expr0->ops.binary.op)
+ && operand_equal_p (expr0->ops.binary.opnd0,
+ expr1->ops.binary.opnd1, 0)
+ && operand_equal_p (expr0->ops.binary.opnd1,
+ expr1->ops.binary.opnd0, 0));
+
+ case EXPR_TERNARY:
+ if (expr0->ops.ternary.op != expr1->ops.ternary.op
+ || !operand_equal_p (expr0->ops.ternary.opnd2,
+ expr1->ops.ternary.opnd2, 0))
+ return false;
+
+ if (operand_equal_p (expr0->ops.ternary.opnd0,
+ expr1->ops.ternary.opnd0, 0)
+ && operand_equal_p (expr0->ops.ternary.opnd1,
+ expr1->ops.ternary.opnd1, 0))
+ return true;
+
+ /* For commutative ops, allow the other order. */
+ return (commutative_ternary_tree_code (expr0->ops.ternary.op)
+ && operand_equal_p (expr0->ops.ternary.opnd0,
+ expr1->ops.ternary.opnd1, 0)
+ && operand_equal_p (expr0->ops.ternary.opnd1,
+ expr1->ops.ternary.opnd0, 0));
case EXPR_CALL:
{
/* If the calls are to different functions, then they
clearly cannot be equal. */
- if (! operand_equal_p (expr0->ops.call.fn,
- expr1->ops.call.fn, 0))
+ if (!gimple_call_same_target_p (expr0->ops.call.fn_from,
+ expr1->ops.call.fn_from))
return false;
if (! expr0->ops.call.pure)
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;
+ }
+
+ case EXPR_PHI:
+ {
+ size_t i;
+
+ if (expr0->ops.phi.nargs != expr1->ops.phi.nargs)
+ return false;
+
+ for (i = 0; i < expr0->ops.phi.nargs; i++)
+ if (! operand_equal_p (expr0->ops.phi.args[i],
+ expr1->ops.phi.args[i], 0))
+ return false;
+
return true;
}
-
+
default:
gcc_unreachable ();
}
}
+/* 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:
+ hstate.add_object (expr->ops.ternary.op);
+ if (commutative_ternary_tree_code (expr->ops.ternary.op))
+ inchash::add_expr_commutative (expr->ops.ternary.opnd0,
+ expr->ops.ternary.opnd1, hstate);
+ else
+ {
+ inchash::add_expr (expr->ops.ternary.opnd0, hstate);
+ inchash::add_expr (expr->ops.ternary.opnd1, hstate);
+ }
+ inchash::add_expr (expr->ops.ternary.opnd2, hstate);
+ break;
+
case EXPR_CALL:
{
size_t i;
enum tree_code code = CALL_EXPR;
-
- val = iterative_hash_object (code, val);
- val = iterative_hash_expr (expr->ops.call.fn, val);
+ gimple fn_from;
+
+ hstate.add_object (code);
+ fn_from = expr->ops.call.fn_from;
+ if (gimple_call_internal_p (fn_from))
+ hstate.merge_hash ((hashval_t) gimple_call_internal_fn (fn_from));
+ else
+ 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;
-
+
+ case EXPR_PHI:
+ {
+ size_t i;
+
+ for (i = 0; i < expr->ops.phi.nargs; i++)
+ 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. */
print_generic_expr (stream, element->lhs, 0);
fprintf (stream, " = ");
}
-
+
switch (element->expr.kind)
{
case EXPR_SINGLE:
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 <", 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);
+ fputs (", ", stream);
+ print_generic_expr (stream, element->expr.ops.ternary.opnd2, 0);
+ fputs (">", stream);
+ break;
+
case EXPR_CALL:
{
size_t i;
size_t nargs = element->expr.ops.call.nargs;
-
- print_generic_expr (stream, element->expr.ops.call.fn, 0);
+ gimple fn_from;
+
+ fn_from = element->expr.ops.call.fn_from;
+ if (gimple_call_internal_p (fn_from))
+ fputs (internal_fn_name (gimple_call_internal_fn (fn_from)),
+ stream);
+ else
+ print_generic_expr (stream, gimple_call_fn (fn_from), 0);
fprintf (stream, " (");
for (i = 0; i < nargs; i++)
{
fprintf (stream, ")");
}
break;
+
+ case EXPR_PHI:
+ {
+ size_t i;
+ size_t nargs = element->expr.ops.phi.nargs;
+
+ fprintf (stream, "PHI <");
+ for (i = 0; i < nargs; i++)
+ {
+ print_generic_expr (stream, element->expr.ops.phi.args[i], 0);
+ if (i + 1 < nargs)
+ fprintf (stream, ", ");
+ }
+ fprintf (stream, ">");
+ }
+ break;
}
fprintf (stream, "\n");
}
}
-/* Delete an expr_hash_elt and reclaim its storage. */
+/* Delete variable sized pieces of the expr_hash_elt ELEMENT. */
static void
-free_expr_hash_elt (void *elt)
+free_expr_hash_elt_contents (struct expr_hash_elt *element)
{
- struct expr_hash_elt *element = ((struct expr_hash_elt *)elt);
-
if (element->expr.kind == EXPR_CALL)
free (element->expr.ops.call.args);
+ else if (element->expr.kind == EXPR_PHI)
+ free (element->expr.ops.phi.args);
+}
+
+/* Delete an expr_hash_elt and reclaim its storage. */
+static void
+free_expr_hash_elt (void *elt)
+{
+ struct expr_hash_elt *element = ((struct expr_hash_elt *)elt);
+ free_expr_hash_elt_contents (element);
free (element);
}
edge_iterator ei;
edge e;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (edge_info)
{
- if (edge_info->cond_equivalences)
- free (edge_info->cond_equivalences);
+ edge_info->cond_equivalences.release ();
free (edge_info);
e->aux = NULL;
}
}
}
-/* Jump threading, redundancy elimination and const/copy propagation.
+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 =
{
- struct dom_walk_data walk_data;
+ 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
+{
+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 = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt);
- avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20);
- const_and_copies_stack = VEC_alloc (tree, heap, 20);
+ 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 ();
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);
+ 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 (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ 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));
}
}
/* 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. */
+ has inherited from the original block, needs the cleanup.
+ Don't clear bits in the bitmap, as that can break the bitmap
+ iterator. */
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);
- }
+ 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_FOR_FN (fun))
+ continue;
+ if ((unsigned) bb->index != i)
+ bitmap_set_bit (need_eh_cleanup, bb->index);
}
gimple_purge_all_dead_eh_edges (need_eh_cleanup);
- bitmap_zero (need_eh_cleanup);
+ 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. */
- htab_delete (avail_exprs);
-
- /* 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);
-
- VEC_free (expr_hash_elt_t, heap, avail_exprs_stack);
- VEC_free (tree, heap, const_and_copies_stack);
-
+
+ avail_exprs_stack.release ();
+ const_and_copies_stack.release ();
+
/* Free the value-handle array. */
threadedge_finalize_values ();
- ssa_name_values = NULL;
return 0;
}
-static bool
-gate_dominator (void)
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_dominator (gcc::context *ctxt)
{
- return flag_tree_dom != 0;
+ return new pass_dominator (ctxt);
}
-struct gimple_opt_pass pass_dominator =
-{
- {
- GIMPLE_PASS,
- "dom", /* name */
- gate_dominator, /* gate */
- tree_ssa_dominator_optimize, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_dump_func
- | TODO_update_ssa
- | TODO_cleanup_cfg
- | TODO_verify_ssa /* todo_flags_finish */
- }
-};
-
/* Given a conditional statement CONDSTMT, convert the
condition to a canonical form. */
remove_local_expressions_from_table (void)
{
/* Remove all the expressions made available in this block. */
- while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0)
+ while (avail_exprs_stack.length () > 0)
{
- struct expr_hash_elt element;
- expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack);
+ expr_hash_elt_t victim = avail_exprs_stack.pop ();
+ expr_hash_elt **slot;
if (victim == NULL)
break;
- element = *victim;
-
/* This must precede the actual removal from the hash table,
as ELEMENT and the table entry may share a call argument
vector which will be freed during removal. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "<<<< ");
- print_expr_hash_elt (dump_file, &element);
+ print_expr_hash_elt (dump_file, victim);
}
- htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
+ slot = avail_exprs->find_slot (victim, NO_INSERT);
+ gcc_assert (slot && *slot == victim);
+ avail_exprs->clear_slot (slot);
}
}
static void
restore_vars_to_original_value (void)
{
- while (VEC_length (tree, const_and_copies_stack) > 0)
+ while (const_and_copies_stack.length () > 0)
{
tree prev_value, dest;
- dest = VEC_pop (tree, const_and_copies_stack);
+ dest = const_and_copies_stack.pop ();
if (dest == NULL)
break;
fprintf (dump_file, "\n");
}
- prev_value = VEC_pop (tree, const_and_copies_stack);
+ prev_value = const_and_copies_stack.pop ();
set_ssa_name_value (dest, prev_value);
}
}
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.
record_equivalences_from_phis (basic_block bb)
{
gimple_stmt_iterator gsi;
-
+
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple phi = gsi_stmt (gsi);
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);
}
}
{
tree lhs = edge_info->lhs;
tree rhs = edge_info->rhs;
- struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
+ cond_equivalence *eq;
if (lhs)
record_equality (lhs, rhs);
- if (cond_equivalences)
- for (i = 0; i < edge_info->max_cond_equivalences; i++)
- record_cond (&cond_equivalences[i]);
+ /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
+ set via a widening type conversion, then we may be able to record
+ additional equivalences. */
+ if (lhs
+ && TREE_CODE (lhs) == SSA_NAME
+ && is_gimple_constant (rhs)
+ && TREE_CODE (rhs) == INTEGER_CST)
+ {
+ gimple defstmt = SSA_NAME_DEF_STMT (lhs);
+
+ if (defstmt
+ && is_gimple_assign (defstmt)
+ && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (defstmt)))
+ {
+ tree old_rhs = gimple_assign_rhs1 (defstmt);
+
+ /* 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.
+
+ Note that int_fits_type_p does not check the precision
+ if the upper and lower bounds are OK. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (old_rhs))
+ && (TYPE_PRECISION (TREE_TYPE (lhs))
+ > TYPE_PRECISION (TREE_TYPE (old_rhs)))
+ && int_fits_type_p (rhs, TREE_TYPE (old_rhs)))
+ {
+ tree newval = fold_convert (TREE_TYPE (old_rhs), rhs);
+ record_equality (old_rhs, newval);
+ }
+ }
+ }
+
+ for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
+ record_cond (eq);
}
}
}
fprintf (file, "\nHash table statistics:\n");
fprintf (file, " avail_exprs: ");
- htab_statistics (file, avail_exprs);
+ htab_statistics (file, *avail_exprs);
}
/* Dump SSA statistics on stderr. */
-void
+DEBUG_FUNCTION void
debug_dominator_optimization_stats (void)
{
dump_dominator_optimization_stats (stderr);
/* Dump statistics for the hash table HTAB. */
static void
-htab_statistics (FILE *file, htab_t 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 (htab),
- (long) htab_elements (htab),
- htab_collisions (htab));
+ (long) htab.size (),
+ (long) htab.elements (),
+ htab.collisions ());
}
boolean value. */
static void
-record_cond (struct cond_equivalence *p)
+record_cond (cond_equivalence *p)
{
struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
- void **slot;
+ expr_hash_elt **slot;
initialize_hash_element_from_expr (&p->cond, p->value, element);
- slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
- element->hash, INSERT);
+ slot = avail_exprs->find_slot_with_hash (element, element->hash, INSERT);
if (*slot == NULL)
{
- *slot = (void *) element;
+ *slot = element;
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_expr_hash_elt (dump_file, element);
}
- VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
+ avail_exprs_stack.safe_push (element);
}
else
- free (element);
+ free_expr_hash_elt (element);
}
/* Build a cond_equivalence record indicating that the comparison
- CODE holds between operands OP0 and OP1. */
-
+ CODE holds between operands OP0 and OP1 and push it to **P. */
+
static void
build_and_record_new_cond (enum tree_code code,
tree op0, tree op1,
- struct cond_equivalence *p)
+ vec<cond_equivalence> *p)
{
- struct hashable_expr *cond = &p->cond;
+ cond_equivalence c;
+ struct hashable_expr *cond = &c.cond;
gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
cond->ops.binary.opnd0 = op0;
cond->ops.binary.opnd1 = op1;
- p->value = boolean_true_node;
+ c.value = boolean_true_node;
+ p->safe_push (c);
}
/* Record that COND is true and INVERTED is false into the edge information
record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
{
tree op0, op1;
+ cond_equivalence c;
if (!COMPARISON_CLASS_P (cond))
return;
case GT_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (op0)))
{
- edge_info->max_cond_equivalences = 6;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 6);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
- &edge_info->cond_equivalences[4]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (LTGT_EXPR, op0, op1,
- &edge_info->cond_equivalences[5]);
- }
- else
- {
- edge_info->max_cond_equivalences = 4;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
+ &edge_info->cond_equivalences);
}
build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
? LE_EXPR : GE_EXPR),
- op0, op1, &edge_info->cond_equivalences[2]);
+ op0, op1, &edge_info->cond_equivalences);
build_and_record_new_cond (NE_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
break;
case GE_EXPR:
case LE_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (op0)))
{
- edge_info->max_cond_equivalences = 3;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 3);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
- &edge_info->cond_equivalences[2]);
- }
- else
- {
- edge_info->max_cond_equivalences = 2;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
+ &edge_info->cond_equivalences);
}
break;
case EQ_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (op0)))
{
- edge_info->max_cond_equivalences = 5;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 5);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
- &edge_info->cond_equivalences[4]);
- }
- else
- {
- edge_info->max_cond_equivalences = 4;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
+ &edge_info->cond_equivalences);
}
build_and_record_new_cond (LE_EXPR, op0, op1,
- &edge_info->cond_equivalences[2]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (GE_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
break;
case UNORDERED_EXPR:
- edge_info->max_cond_equivalences = 8;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 8);
build_and_record_new_cond (NE_EXPR, op0, op1,
- &edge_info->cond_equivalences[2]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNLE_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNGE_EXPR, op0, op1,
- &edge_info->cond_equivalences[4]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNEQ_EXPR, op0, op1,
- &edge_info->cond_equivalences[5]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNLT_EXPR, op0, op1,
- &edge_info->cond_equivalences[6]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNGT_EXPR, op0, op1,
- &edge_info->cond_equivalences[7]);
+ &edge_info->cond_equivalences);
break;
case UNLT_EXPR:
case UNGT_EXPR:
- edge_info->max_cond_equivalences = 4;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
? UNLE_EXPR : UNGE_EXPR),
- op0, op1, &edge_info->cond_equivalences[2]);
+ op0, op1, &edge_info->cond_equivalences);
build_and_record_new_cond (NE_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
break;
case UNEQ_EXPR:
- edge_info->max_cond_equivalences = 4;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
build_and_record_new_cond (UNLE_EXPR, op0, op1,
- &edge_info->cond_equivalences[2]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNGE_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
break;
case LTGT_EXPR:
- edge_info->max_cond_equivalences = 4;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
build_and_record_new_cond (NE_EXPR, op0, op1,
- &edge_info->cond_equivalences[2]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
break;
default:
- edge_info->max_cond_equivalences = 2;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
break;
}
/* Now store the original true and false conditions into the first
two slots. */
- initialize_expr_from_cond (cond, &edge_info->cond_equivalences[0].cond);
- edge_info->cond_equivalences[0].value = boolean_true_node;
+ initialize_expr_from_cond (cond, &c.cond);
+ c.value = boolean_true_node;
+ edge_info->cond_equivalences.safe_push (c);
/* It is possible for INVERTED to be the negation of a comparison,
and not a valid RHS or GIMPLE_COND condition. This happens because
invert_truthvalue may return such an expression when asked to invert
a floating-point comparison. These comparisons are not assumed to
obey the trichotomy law. */
- initialize_expr_from_cond (inverted, &edge_info->cond_equivalences[1].cond);
- edge_info->cond_equivalences[1].value = boolean_false_node;
+ initialize_expr_from_cond (inverted, &c.cond);
+ c.value = boolean_false_node;
+ edge_info->cond_equivalences.safe_push (c);
}
/* A helper function for record_const_or_copy and record_equality.
fprintf (dump_file, "\n");
}
- VEC_reserve (tree, heap, const_and_copies_stack, 2);
- VEC_quick_push (tree, const_and_copies_stack, prev_x);
- VEC_quick_push (tree, const_and_copies_stack, x);
+ const_and_copies_stack.reserve (2);
+ const_and_copies_stack.quick_push (prev_x);
+ 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.
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;
if (!defbb)
return 0;
- return defbb->loop_depth;
-}
-
-/* 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 bb_loop_depth (defbb);
}
/* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
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))
/* Returns true when STMT is a simple iv increment. It detects the
following situation:
-
+
i_1 = phi (..., i_2)
i_2 = i_1 +/- ... */
-static bool
+bool
simple_iv_increment_p (gimple stmt)
{
+ enum tree_code code;
tree lhs, preinc;
gimple phi;
size_t i;
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (gimple_assign_rhs_code (stmt) != PLUS_EXPR
- && gimple_assign_rhs_code (stmt) != MINUS_EXPR)
+ code = gimple_assign_rhs_code (stmt);
+ if (code != PLUS_EXPR
+ && code != MINUS_EXPR
+ && code != POINTER_PLUS_EXPR)
return false;
preinc = gimple_assign_rhs1 (stmt);
-
if (TREE_CODE (preinc) != SSA_NAME)
return false;
}
/* 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).
+ known value for that SSA_NAME (or NULL if no value is known).
Propagate values from CONST_AND_COPIES into the PHI nodes of the
successors of BB. */
if (gsi_end_p (gsi))
continue;
+ /* We may have an equivalence associated with this edge. While
+ we can not propagate it into non-dominated blocks, we can
+ propagate them into PHIs in non-dominated blocks. */
+
+ /* Push the unwind marker so we can reset the const and copies
+ 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.
+
+ Don't bother with [01] = COND equivalences, they're not useful
+ here. */
+ struct edge_info *edge_info = (struct edge_info *) e->aux;
+ if (edge_info)
+ {
+ tree lhs = edge_info->lhs;
+ tree rhs = edge_info->rhs;
+
+ if (lhs && TREE_CODE (lhs) == SSA_NAME)
+ record_const_or_copy (lhs, rhs);
+ }
+
indx = e->dest_idx;
for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
{
&& may_propagate_copy (orig_val, new_val))
propagate_value (orig_p, new_val);
}
+
+ restore_vars_to_original_value ();
}
}
{
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;
{
tree cond = build2 (code, boolean_type_node, op0, op1);
tree inverted = invert_truthvalue_loc (loc, cond);
+ bool can_infer_simple_equiv
+ = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
+ && real_zerop (op0));
struct edge_info *edge_info;
edge_info = allocate_edge_info (true_edge);
record_conditions (edge_info, cond, inverted);
- if (code == EQ_EXPR)
+ if (can_infer_simple_equiv && code == EQ_EXPR)
{
edge_info->lhs = op1;
edge_info->rhs = op0;
edge_info = allocate_edge_info (false_edge);
record_conditions (edge_info, inverted, cond);
- if (code == NE_EXPR)
+ if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
{
edge_info->lhs = op1;
edge_info->rhs = op0;
}
else if (TREE_CODE (op0) == SSA_NAME
- && (is_gimple_min_invariant (op1)
- || TREE_CODE (op1) == SSA_NAME))
+ && (TREE_CODE (op1) == SSA_NAME
+ || is_gimple_min_invariant (op1)))
{
tree cond = build2 (code, boolean_type_node, op0, op1);
tree inverted = invert_truthvalue_loc (loc, cond);
+ bool can_infer_simple_equiv
+ = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op1)))
+ && (TREE_CODE (op1) == SSA_NAME || real_zerop (op1)));
struct edge_info *edge_info;
edge_info = allocate_edge_info (true_edge);
record_conditions (edge_info, cond, inverted);
- if (code == EQ_EXPR)
+ if (can_infer_simple_equiv && code == EQ_EXPR)
{
edge_info->lhs = op0;
edge_info->rhs = op1;
edge_info = allocate_edge_info (false_edge);
record_conditions (edge_info, inverted, cond);
- if (TREE_CODE (cond) == NE_EXPR)
+ if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
{
edge_info->lhs = op0;
edge_info->rhs = op1;
}
}
-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;
/* Push a marker on the stacks of local information so that we know how
far to unwind when we finalize this block. */
- VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
- VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
+ avail_exprs_stack.safe_push (NULL);
+ const_and_copies_stack.safe_push (NULL_TREE);
record_equivalences_from_incoming_edge (bb);
/* PHI nodes can create equivalences too. */
record_equivalences_from_phis (bb);
+ /* Create equivalences from redundant PHIs. PHIs are only truly
+ redundant when they exist in the same block, so push another
+ marker and unwind right afterwards. */
+ avail_exprs_stack.safe_push (NULL);
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ eliminate_redundant_computations (&gsi);
+ remove_local_expressions_from_table ();
+
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
optimize_stmt (bb, 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)))
{
- 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. */
- VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
- VEC_safe_push (tree, heap, const_and_copies_stack, 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)
- {
- struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
- 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. */
- if (cond_equivalences)
- for (i = 0; i < edge_info->max_cond_equivalences; i++)
- record_cond (&cond_equivalences[i]);
- }
-
- 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;
-
- VEC_safe_push (tree, heap, const_and_copies_stack, 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)
- {
- struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
- 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. */
- if (cond_equivalences)
- for (i = 0; i < edge_info->max_cond_equivalences; i++)
- record_cond (&cond_equivalences[i]);
- }
+ thread_across_edge (false_edge);
- /* Now thread the edge. */
- dom_thread_across_edge (walk_data, 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 ();
}
{
tree expr_type;
tree cached_lhs;
+ tree def;
bool insert = true;
bool assigns_var_p = false;
gimple stmt = gsi_stmt (*gsi);
- tree def = gimple_get_lhs (stmt);
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ def = gimple_phi_result (stmt);
+ else
+ def = gimple_get_lhs (stmt);
/* Certain expressions on the RHS can be optimized away, but can not
themselves be entered into the hash tables. */
}
else if (gimple_code (stmt) == GIMPLE_SWITCH)
expr_type = TREE_TYPE (gimple_switch_index (stmt));
+ else if (gimple_code (stmt) == GIMPLE_PHI)
+ /* We can't propagate into a phi, so the logic below doesn't apply.
+ Instead record an equivalence between the cached LHS and the
+ PHI result of this statement, provided they are in the same block.
+ This should be sufficient to kill the redundant phi. */
+ {
+ if (def && cached_lhs)
+ record_const_or_copy (def, cached_lhs);
+ return;
+ }
else
gcc_unreachable ();
|| useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
|| may_propagate_copy_into_stmt (stmt, cached_lhs))
{
-#if defined ENABLE_CHECKING
- gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
- || is_gimple_min_invariant (cached_lhs));
-#endif
+ gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME
+ || is_gimple_min_invariant (cached_lhs));
if (dump_file && (dump_flags & TDF_DETAILS))
{
}
opt_stats.num_re++;
-
+
if (assigns_var_p
&& !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
cached_lhs = fold_convert (expr_type, cached_lhs);
&& gimple_assign_single_p (stmt))
{
tree rhs = gimple_assign_rhs1 (stmt);
-
+
/* 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
val = SSA_NAME_VALUE (op);
if (val && val != op)
{
- /* 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)
- && (TREE_CODE (val) != SSA_NAME
- || is_gimple_reg (val)
- || get_virtual_var (val) != get_virtual_var (op)))
- return;
-
/* Do not replace hard register operands in asm statements. */
if (gimple_code (stmt) == GIMPLE_ASM
&& !may_propagate_copy_into_asm (op))
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
}
/* 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).
+ known value for that SSA_NAME (or NULL if no value is known).
Propagate values from CONST_AND_COPIES into the uses, vuses and
vdef_ops of STMT. */
use_operand_p op_p;
ssa_op_iter iter;
- FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
- {
- if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
- cprop_operand (stmt, op_p);
- }
+ FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE)
+ cprop_operand (stmt, op_p);
}
/* Optimize the statement pointed to by iterator SI.
-
+
We try to perform some simplistic global redundancy elimination and
constant propagation:
bool modified_p = false;
old_stmt = stmt = gsi_stmt (si);
-
- if (gimple_code (stmt) == GIMPLE_COND)
- canonicalize_comparison (stmt);
-
- update_stmt_if_modified (stmt);
- opt_stats.num_stmts++;
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
+ if (gimple_code (stmt) == GIMPLE_COND)
+ canonicalize_comparison (stmt);
+
+ update_stmt_if_modified (stmt);
+ opt_stats.num_stmts++;
+
/* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
cprop_into_stmt (stmt);
if (fold_stmt (&si))
{
stmt = gsi_stmt (si);
+ gimple_set_modified (stmt, true);
if (dump_file && (dump_flags & TDF_DETAILS))
{
/* Check for redundant computations. Do this optimization only
for assignments that have no volatile ops and conditionals. */
- may_optimize_p = (!gimple_has_volatile_ops (stmt)
- && ((is_gimple_assign (stmt)
- && !gimple_rhs_has_side_effects (stmt))
+ may_optimize_p = (!gimple_has_side_effects (stmt)
+ && (is_gimple_assign (stmt)
|| (is_gimple_call (stmt)
- && gimple_call_lhs (stmt) != NULL_TREE
- && !gimple_rhs_has_side_effects (stmt))
+ && gimple_call_lhs (stmt) != NULL_TREE)
|| gimple_code (stmt) == GIMPLE_COND
|| gimple_code (stmt) == GIMPLE_SWITCH));
if (may_optimize_p)
{
- eliminate_redundant_computations (&si);
- stmt = gsi_stmt (si);
if (gimple_code (stmt) == GIMPLE_CALL)
{
/* Resolve __builtin_constant_p. If it hasn't been
stmt = gsi_stmt (si);
}
}
+
+ update_stmt_if_modified (stmt);
+ eliminate_redundant_computations (&si);
+ stmt = gsi_stmt (si);
+
+ /* Perform simple redundant store elimination. */
+ if (gimple_assign_single_p (stmt)
+ && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+ tree rhs = gimple_assign_rhs1 (stmt);
+ tree cached_lhs;
+ gimple new_stmt;
+ if (TREE_CODE (rhs) == SSA_NAME)
+ {
+ tree tem = SSA_NAME_VALUE (rhs);
+ if (tem)
+ rhs = tem;
+ }
+ /* Build a new statement with the RHS and LHS exchanged. */
+ if (TREE_CODE (rhs) == SSA_NAME)
+ {
+ gimple defstmt = SSA_NAME_DEF_STMT (rhs);
+ new_stmt = gimple_build_assign (rhs, lhs);
+ SSA_NAME_DEF_STMT (rhs) = defstmt;
+ }
+ else
+ new_stmt = gimple_build_assign (rhs, lhs);
+ gimple_set_vuse (new_stmt, gimple_vuse (stmt));
+ cached_lhs = lookup_avail_expr (new_stmt, false);
+ if (cached_lhs
+ && rhs == cached_lhs)
+ {
+ basic_block bb = gimple_bb (stmt);
+ unlink_stmt_vdef (stmt);
+ if (gsi_remove (&si, true))
+ {
+ bitmap_set_bit (need_eh_cleanup, bb->index);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Flagged to clear EH edges.\n");
+ }
+ release_defs (stmt);
+ return;
+ }
+ }
}
/* Record any additional equivalences created by this statement. */
where it goes. If that is the case, then mark the CFG as altered.
This will cause us to later call remove_unreachable_blocks and
- cleanup_tree_cfg when it is safe to do so. It is not safe to
+ cleanup_tree_cfg when it is safe to do so. It is not safe to
clean things up here since removal of edges and such can trigger
the removal of PHI nodes, which in turn can release SSA_NAMEs to
the manager.
if (gimple_modified_p (stmt) || modified_p)
{
tree val = NULL;
-
- update_stmt (stmt);
+
+ update_stmt_if_modified (stmt);
if (gimple_code (stmt) == GIMPLE_COND)
val = fold_binary_loc (gimple_location (stmt),
static tree
lookup_avail_expr (gimple stmt, bool insert)
{
- void **slot;
+ expr_hash_elt **slot;
tree lhs;
tree temp;
- struct expr_hash_elt *element = XNEW (struct expr_hash_elt);
+ struct expr_hash_elt element;
- /* Get LHS of assignment or call, else NULL_TREE. */
- lhs = gimple_get_lhs (stmt);
+ /* Get LHS of phi, assignment, or call; else NULL_TREE. */
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ lhs = gimple_phi_result (stmt);
+ else
+ lhs = gimple_get_lhs (stmt);
- initialize_hash_element (stmt, lhs, element);
+ initialize_hash_element (stmt, lhs, &element);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "LKUP ");
- print_expr_hash_elt (dump_file, element);
+ print_expr_hash_elt (dump_file, &element);
}
/* Don't bother remembering constant assignments and copy operations.
Constants and copy operations are handled by the constant/copy propagator
in optimize_stmt. */
- if (element->expr.kind == EXPR_SINGLE
- && (TREE_CODE (element->expr.ops.single.rhs) == SSA_NAME
- || is_gimple_min_invariant (element->expr.ops.single.rhs)))
- {
- free (element);
- return NULL_TREE;
- }
+ if (element.expr.kind == EXPR_SINGLE
+ && (TREE_CODE (element.expr.ops.single.rhs) == SSA_NAME
+ || is_gimple_min_invariant (element.expr.ops.single.rhs)))
+ return NULL_TREE;
/* Finally try to find the expression in the main expression hash table. */
- slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
- (insert ? INSERT : NO_INSERT));
+ slot = avail_exprs->find_slot (&element, (insert ? INSERT : NO_INSERT));
if (slot == NULL)
{
- free (element);
- return NULL_TREE;
+ free_expr_hash_elt_contents (&element);
+ return NULL_TREE;
}
-
- if (*slot == NULL)
+ else if (*slot == NULL)
{
- *slot = (void *) element;
+ struct expr_hash_elt *element2 = XNEW (struct expr_hash_elt);
+ *element2 = element;
+ element2->stamp = element2;
+ *slot = element2;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "2>>> ");
- print_expr_hash_elt (dump_file, element);
+ print_expr_hash_elt (dump_file, element2);
}
- VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
+ avail_exprs_stack.safe_push (element2);
return NULL_TREE;
}
+ else
+ free_expr_hash_elt_contents (&element);
/* Extract the LHS of the assignment so that it can be used as the current
definition of another variable. */
lhs = temp;
}
- free (element);
-
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "FIND: ");
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;
-}
-
-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)
-{
- gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt;
- const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr;
- const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp;
- gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt;
- const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr;
- const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp;
-
- /* This case should apply only when removing entries from the table. */
- if (stamp1 == stamp2)
- return true;
-
- /* FIXME tuples:
- We add stmts to a hash table and them modify them. To detect the case
- that we modify a stmt and then search for it, we assume that the hash
- is always modified by that change.
- We have to fully check why this doesn't happen on trunk or rewrite
- this in a more reliable (and easier to understand) way. */
- if (((const struct expr_hash_elt *)p1)->hash
- != ((const struct expr_hash_elt *)p2)->hash)
- return false;
-
- /* In case of a collision, both RHS have to be identical and have the
- same VUSE operands. */
- if (hashable_expr_equal_p (expr1, expr2)
- && types_compatible_p (expr1->type, expr2->type))
- {
- /* Note that STMT1 and/or STMT2 may be NULL. */
- return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE)
- == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE));
- }
-
- return false;
+ 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 (!val)
- val = arg;
- else if (!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. */
nodes as well in an effort to pick up secondary optimization
opportunities. */
-static void
+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;
fprintf (dump_file, "'\n");
}
- /* Walk over every use of LHS and try to replace the use with RHS.
+ /* Walk over every use of LHS and try to replace the use with RHS.
At this point the only reason why such a propagation would not
be successful would be if the use occurs in an ASM_EXPR. */
FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
into debug stmts will occur then. */
if (gimple_debug_bind_p (use_stmt))
continue;
-
+
/* It's not always safe to propagate into an ASM_EXPR. */
if (gimple_code (use_stmt) == GIMPLE_ASM
&& ! may_propagate_copy_into_asm (lhs))
continue;
}
+ /* It's not ok to propagate into the definition stmt of RHS.
+ <bb 9>:
+ # prephitmp.12_36 = PHI <g_67.1_6(9)>
+ g_67.1_6 = prephitmp.12_36;
+ goto <bb 9>;
+ While this is strictly all dead code we do not want to
+ deal with this here. */
+ if (TREE_CODE (rhs) == SSA_NAME
+ && SSA_NAME_DEF_STMT (rhs) == use_stmt)
+ {
+ all = false;
+ continue;
+ }
+
/* Dump details. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
/* Special cases to avoid useless calls into the folding
routines, operand scanning, etc.
- First, propagation into a PHI may cause the PHI to become
+ Propagation into a PHI may cause the PHI to become
a degenerate, so mark the PHI as interesting. No other
- actions are necessary.
-
- Second, if we're propagating a virtual operand and the
- propagation does not change the underlying _DECL node for
- the virtual operand, then no further actions are necessary. */
- if (gimple_code (use_stmt) == GIMPLE_PHI
- || (! is_gimple_reg (lhs)
- && TREE_CODE (rhs) == SSA_NAME
- && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs)))
+ actions are necessary. */
+ if (gimple_code (use_stmt) == GIMPLE_PHI)
{
+ tree result;
+
/* Dump details. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
}
- /* Propagation into a PHI may expose new degenerate PHIs,
- so mark the result of the PHI as interesting. */
- if (gimple_code (use_stmt) == GIMPLE_PHI)
- {
- tree result = get_lhs_or_phi_result (use_stmt);
- bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
- }
-
+ result = get_lhs_or_phi_result (use_stmt);
+ bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
continue;
}
- /* From this point onward we are propagating into a
+ /* From this point onward we are propagating into a
real statement. Folding may (or may not) be possible,
we may expose new operands, expose dead EH edges,
etc. */
GIMPLE_ASSIGN, and there is no way to effect such a
transformation in-place. We might want to consider
using the more general fold_stmt here. */
- fold_stmt_inplace (use_stmt);
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
+ fold_stmt_inplace (&gsi);
+ }
/* Sometimes propagation can expose new operands to the
renamer. */
}
}
- /* Ensure there is nothing else to do. */
+ /* Ensure there is nothing else to do. */
gcc_assert (!all || has_zero_uses (lhs));
/* If we were able to propagate away all uses of LHS, then
return;
}
- propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
+ if (!virtual_operand_p (lhs))
+ propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
+ else
+ {
+ gimple use_stmt;
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ /* For virtual operands we have to propagate into all uses as
+ otherwise we will create overlapping life-ranges. */
+ FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
+ FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+ SET_USE (use_p, rhs);
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
+ remove_stmt_or_phi (stmt);
+ }
/* Note that STMT may well have been deleted by now, so do
not access it, instead use the saved version # to clear
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;
A set bit indicates that the statement or PHI node which
defines the SSA_NAME should be (re)examined to determine if
it has become a degenerate PHI or trivial const/copy propagation
- opportunity.
+ opportunity.
Experiments have show we generally get better compilation
time behavior with bitmaps rather than sbitmaps. */
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
}
if (cfg_altered)
- free_dominance_info (CDI_DOMINATORS);
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ /* If we changed the CFG schedule loops for fixup by cfgcleanup. */
+ loops_state_set (LOOPS_NEED_FIXUP);
+ }
/* Propagation of const and copies may make some EH edges dead. Purge
such edges from the CFG as needed. */
return 0;
}
-struct gimple_opt_pass pass_phi_only_cprop =
-{
- {
- GIMPLE_PASS,
- "phicprop", /* name */
- gate_dominator, /* gate */
- eliminate_degenerate_phis, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- 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_dump_func
- | TODO_ggc_collect
- | TODO_verify_ssa
- | TODO_verify_stmts
- | TODO_update_ssa /* todo_flags_finish */
- }
-};
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_phi_only_cprop (gcc::context *ctxt)
+{
+ return new pass_phi_only_cprop (ctxt);
+}