@@ -55,33 +55,6 @@ along with GCC; see the file COPYING3. If not see
/* This file implements optimizations on the dominator tree. */
-/* Representation of a "naked" right-hand-side expression, to be used
- in recording available expressions in the expression hash table. */
-
-enum expr_kind
-{
- EXPR_SINGLE,
- EXPR_UNARY,
- EXPR_BINARY,
- EXPR_TERNARY,
- EXPR_CALL,
- EXPR_PHI
-};
-
-struct hashable_expr
-{
- tree type;
- enum expr_kind kind;
- union {
- struct { tree rhs; } single;
- struct { enum tree_code op; tree opnd; } unary;
- struct { enum tree_code op; tree opnd0, opnd1; } binary;
- struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary;
- struct { gcall *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. */
@@ -91,7 +64,6 @@ struct cond_equivalence
tree value;
};
-
/* Structure for recording edge equivalences.
Computing and storing the edge equivalences instead of creating
@@ -114,137 +86,6 @@ struct edge_info
vec<cond_equivalence> cond_equivalences;
};
-/* 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;
-
-
-/* Structure for entries in the expression hash table. */
-
-class expr_hash_elt
-{
- public:
- expr_hash_elt (gimple, tree);
- expr_hash_elt (tree);
- expr_hash_elt (struct hashable_expr *, tree);
- expr_hash_elt (class expr_hash_elt &);
- ~expr_hash_elt ();
- void print (FILE *);
- tree vop (void) { return m_vop; }
- tree lhs (void) { return m_lhs; }
- struct hashable_expr *expr (void) { return &m_expr; }
- expr_hash_elt *stamp (void) { return m_stamp; }
- hashval_t hash (void) { return m_hash; }
-
- private:
- /* The expression (rhs) we want to record. */
- struct hashable_expr m_expr;
-
- /* The value (lhs) of this expression. */
- tree m_lhs;
-
- /* The virtual operand associated with the nearest dominating stmt
- loading from or storing to expr. */
- tree m_vop;
-
- /* The hash value for RHS. */
- hashval_t m_hash;
-
- /* A unique stamp, typically the address of the hash
- element itself, used in removing entries from the table. */
- struct expr_hash_elt *m_stamp;
-
- /* We should never be making assignments between objects in this class.
- Though it might allow us to exploit C++11 move semantics if we
- defined the move constructor and move assignment operator. */
- expr_hash_elt& operator=(const expr_hash_elt&);
-};
-
-/* 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 : pointer_hash <expr_hash_elt>
-{
- static inline hashval_t hash (const value_type &);
- static inline bool equal (const value_type &, const compare_type &);
- static inline void remove (value_type &);
-};
-
-/* This class defines a unwindable AVAIL_EXPRs, built on top of the
- available expression hash table.
-
- Essentially it's just a stack of available expression value pairs with
- a special marker (NULL, NULL) to indicate unwind points. */
-
-class avail_exprs_stack
-{
- public:
- /* We need access to the AVAIL_EXPR hash table so that we can
- remove entries from the hash table when unwinding the stack. */
- avail_exprs_stack (hash_table<expr_elt_hasher> *table)
- { m_stack.create (20); m_avail_exprs = table; }
- ~avail_exprs_stack (void) { m_stack.release (); }
-
- /* Push the unwinding marker onto the stack. */
- void push_marker (void) { record_expr (NULL, NULL, 'M'); }
-
- /* Restore the AVAIL_EXPRs table to its state when the last marker
- was pushed. */
- void pop_to_marker ();
-
- /* Record a single available expression that can be unwound. */
- void record_expr (expr_hash_elt_t, expr_hash_elt_t, char);
-
- private:
- vec<std::pair<expr_hash_elt_t, expr_hash_elt_t> > m_stack;
- hash_table<expr_elt_hasher> *m_avail_exprs;
-};
-
-
-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)
-{
- const struct hashable_expr *expr1 = p1->expr ();
- const struct expr_hash_elt *stamp1 = p1->stamp ();
- 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;
-
- if (p1->hash () != 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))
- return true;
-
- 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
@@ -254,7 +95,7 @@ expr_elt_hasher::remove (value_type &element)
in this table. */
static hash_table<expr_elt_hasher> *avail_exprs;
-/* Unwindable const/copy equivalences. */
+/* Unwindable equivalences, both const/copy and expression varieties. */
static const_and_copies *const_and_copies;
static avail_exprs_stack *avail_exprs_stack;
@@ -281,7 +122,6 @@ static struct opt_stats_d opt_stats;
/* Local functions. */
static void optimize_stmt (basic_block, gimple_stmt_iterator);
static tree lookup_avail_expr (gimple, bool);
-static hashval_t avail_expr_hash (class expr_hash_elt *);
static void htab_statistics (FILE *,
const hash_table<expr_elt_hasher> &);
static void record_cond (cond_equivalence *);
@@ -292,532 +132,6 @@ static void eliminate_redundant_computations (gimple_stmt_iterator *);
static void record_equivalences_from_stmt (gimple, int);
static edge single_incoming_edge_ignoring_loop_edges (basic_block);
-
-/* Given a statement STMT, initialize the hash table element pointed to
- by ELEMENT. */
-
-expr_hash_elt::expr_hash_elt (gimple stmt, tree orig_lhs)
-{
- enum gimple_code code = gimple_code (stmt);
- struct hashable_expr *expr = this->expr ();
-
- if (code == GIMPLE_ASSIGN)
- {
- enum tree_code subcode = gimple_assign_rhs_code (stmt);
-
- switch (get_gimple_rhs_class (subcode))
- {
- case GIMPLE_SINGLE_RHS:
- 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->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;
- case GIMPLE_BINARY_RHS:
- 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.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 ();
- }
- }
- else if (code == GIMPLE_COND)
- {
- expr->type = boolean_type_node;
- expr->kind = EXPR_BINARY;
- expr->ops.binary.op = gimple_cond_code (stmt);
- expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
- expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
- }
- else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
- {
- size_t nargs = gimple_call_num_args (call_stmt);
- size_t i;
-
- gcc_assert (gimple_call_lhs (call_stmt));
-
- expr->type = TREE_TYPE (gimple_call_lhs (call_stmt));
- expr->kind = EXPR_CALL;
- expr->ops.call.fn_from = call_stmt;
-
- if (gimple_call_flags (call_stmt) & (ECF_CONST | ECF_PURE))
- expr->ops.call.pure = true;
- else
- expr->ops.call.pure = false;
-
- expr->ops.call.nargs = nargs;
- expr->ops.call.args = XCNEWVEC (tree, nargs);
- for (i = 0; i < nargs; i++)
- expr->ops.call.args[i] = gimple_call_arg (call_stmt, i);
- }
- else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
- {
- expr->type = TREE_TYPE (gimple_switch_index (swtch_stmt));
- expr->kind = EXPR_SINGLE;
- expr->ops.single.rhs = gimple_switch_index (swtch_stmt);
- }
- else if (code == GIMPLE_GOTO)
- {
- expr->type = TREE_TYPE (gimple_goto_dest (stmt));
- 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 ();
-
- m_lhs = orig_lhs;
- m_vop = gimple_vuse (stmt);
- m_hash = avail_expr_hash (this);
- m_stamp = this;
-}
-
-/* Given a conditional expression COND as a tree, initialize
- a hashable_expr expression EXPR. The conditional must be a
- comparison or logical negation. A constant or a variable is
- not permitted. */
-
-static void
-initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
-{
- expr->type = boolean_type_node;
-
- if (COMPARISON_CLASS_P (cond))
- {
- expr->kind = EXPR_BINARY;
- expr->ops.binary.op = TREE_CODE (cond);
- expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
- expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
- }
- else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
- {
- expr->kind = EXPR_UNARY;
- expr->ops.unary.op = TRUTH_NOT_EXPR;
- expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
- }
- else
- gcc_unreachable ();
-}
-
-/* Given a hashable_expr expression EXPR and an LHS,
- initialize the hash table element pointed to by ELEMENT. */
-
-expr_hash_elt::expr_hash_elt (struct hashable_expr *orig, tree orig_lhs)
-{
- m_expr = *orig;
- m_lhs = orig_lhs;
- m_vop = NULL_TREE;
- m_hash = avail_expr_hash (this);
- m_stamp = this;
-}
-
-expr_hash_elt::expr_hash_elt (class expr_hash_elt &old_elt)
-{
- m_expr = old_elt.m_expr;
- m_lhs = old_elt.m_lhs;
- m_vop = old_elt.m_vop;
- m_hash = old_elt.m_hash;
- m_stamp = this;
-
- /* Now deep copy the malloc'd space for CALL and PHI args. */
- if (old_elt.m_expr.kind == EXPR_CALL)
- {
- size_t nargs = old_elt.m_expr.ops.call.nargs;
- size_t i;
-
- m_expr.ops.call.args = XCNEWVEC (tree, nargs);
- for (i = 0; i < nargs; i++)
- m_expr.ops.call.args[i] = old_elt.m_expr.ops.call.args[i];
- }
- else if (old_elt.m_expr.kind == EXPR_PHI)
- {
- size_t nargs = old_elt.m_expr.ops.phi.nargs;
- size_t i;
-
- m_expr.ops.phi.args = XCNEWVEC (tree, nargs);
- for (i = 0; i < nargs; i++)
- m_expr.ops.phi.args[i] = old_elt.m_expr.ops.phi.args[i];
- }
-}
-
-expr_hash_elt::~expr_hash_elt ()
-{
- if (m_expr.kind == EXPR_CALL)
- free (m_expr.ops.call.args);
- else if (m_expr.kind == EXPR_PHI)
- free (m_expr.ops.phi.args);
-}
-
-/* Compare two hashable_expr structures for equivalence. They are
- considered equivalent when the expressions they denote must
- necessarily be equal. The logic is intended to follow that of
- operand_equal_p in fold-const.c */
-
-static bool
-hashable_expr_equal_p (const struct hashable_expr *expr0,
- const struct hashable_expr *expr1)
-{
- tree type0 = expr0->type;
- tree type1 = expr1->type;
-
- /* If either type is NULL, there is nothing to check. */
- if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
- return false;
-
- /* If both types don't have the same signedness, precision, and mode,
- then we can't consider them equal. */
- if (type0 != type1
- && (TREE_CODE (type0) == ERROR_MARK
- || TREE_CODE (type1) == ERROR_MARK
- || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
- || TYPE_PRECISION (type0) != TYPE_PRECISION (type1)
- || TYPE_MODE (type0) != TYPE_MODE (type1)))
- return false;
-
- if (expr0->kind != expr1->kind)
- return false;
-
- switch (expr0->kind)
- {
- case EXPR_SINGLE:
- return operand_equal_p (expr0->ops.single.rhs,
- expr1->ops.single.rhs, 0);
-
- case EXPR_UNARY:
- if (expr0->ops.unary.op != expr1->ops.unary.op)
- return false;
-
- if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
- || expr0->ops.unary.op == NON_LVALUE_EXPR)
- && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
- return false;
-
- return operand_equal_p (expr0->ops.unary.opnd,
- 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));
-
- 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:
- {
- size_t i;
-
- /* If the calls are to different functions, then they
- clearly cannot be equal. */
- if (!gimple_call_same_target_p (expr0->ops.call.fn_from,
- expr1->ops.call.fn_from))
- return false;
-
- if (! expr0->ops.call.pure)
- return false;
-
- if (expr0->ops.call.nargs != expr1->ops.call.nargs)
- return false;
-
- for (i = 0; i < expr0->ops.call.nargs; i++)
- if (! operand_equal_p (expr0->ops.call.args[i],
- 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 inchash::add_expr in tree.c. */
-
-static void
-add_hashable_expr (const struct hashable_expr *expr, hash &hstate)
-{
- switch (expr->kind)
- {
- case EXPR_SINGLE:
- inchash::add_expr (expr->ops.single.rhs, hstate);
- break;
-
- case EXPR_UNARY:
- 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
- compare equal according to operand_equal_p, but which
- have different hash codes. */
- if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
- || expr->ops.unary.op == NON_LVALUE_EXPR)
- hstate.add_int (TYPE_UNSIGNED (expr->type));
-
- inchash::add_expr (expr->ops.unary.opnd, hstate);
- break;
-
- case EXPR_BINARY:
- hstate.add_object (expr->ops.binary.op);
- if (commutative_tree_code (expr->ops.binary.op))
- inchash::add_expr_commutative (expr->ops.binary.opnd0,
- expr->ops.binary.opnd1, hstate);
- else
- {
- 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;
- gcall *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++)
- 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 ();
- }
-}
-
-}
-
-/* Print a diagnostic dump of an expression hash table entry. */
-
-void
-expr_hash_elt::print (FILE *stream)
-{
- fprintf (stream, "STMT ");
-
- if (m_lhs)
- {
- print_generic_expr (stream, m_lhs, 0);
- fprintf (stream, " = ");
- }
-
- switch (m_expr.kind)
- {
- case EXPR_SINGLE:
- print_generic_expr (stream, m_expr.ops.single.rhs, 0);
- break;
-
- case EXPR_UNARY:
- fprintf (stream, "%s ", get_tree_code_name (m_expr.ops.unary.op));
- print_generic_expr (stream, m_expr.ops.unary.opnd, 0);
- break;
-
- case EXPR_BINARY:
- print_generic_expr (stream, m_expr.ops.binary.opnd0, 0);
- fprintf (stream, " %s ", get_tree_code_name (m_expr.ops.binary.op));
- print_generic_expr (stream, m_expr.ops.binary.opnd1, 0);
- break;
-
- case EXPR_TERNARY:
- fprintf (stream, " %s <", get_tree_code_name (m_expr.ops.ternary.op));
- print_generic_expr (stream, m_expr.ops.ternary.opnd0, 0);
- fputs (", ", stream);
- print_generic_expr (stream, m_expr.ops.ternary.opnd1, 0);
- fputs (", ", stream);
- print_generic_expr (stream, m_expr.ops.ternary.opnd2, 0);
- fputs (">", stream);
- break;
-
- case EXPR_CALL:
- {
- size_t i;
- size_t nargs = m_expr.ops.call.nargs;
- gcall *fn_from;
-
- fn_from = m_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++)
- {
- print_generic_expr (stream, m_expr.ops.call.args[i], 0);
- if (i + 1 < nargs)
- fprintf (stream, ", ");
- }
- fprintf (stream, ")");
- }
- break;
-
- case EXPR_PHI:
- {
- size_t i;
- size_t nargs = m_expr.ops.phi.nargs;
-
- fprintf (stream, "PHI <");
- for (i = 0; i < nargs; i++)
- {
- print_generic_expr (stream, m_expr.ops.phi.args[i], 0);
- if (i + 1 < nargs)
- fprintf (stream, ", ");
- }
- fprintf (stream, ">");
- }
- break;
- }
-
- if (m_vop)
- {
- fprintf (stream, " with ");
- print_generic_expr (stream, m_vop, 0);
- }
-
- fprintf (stream, "\n");
-}
-
-/* Delete an expr_hash_elt and reclaim its storage. */
-
-static void
-free_expr_hash_elt (void *elt)
-{
- class expr_hash_elt *element = ((class expr_hash_elt *)elt);
- delete element;
-}
-
/* Allocate an EDGE_INFO for edge E and attach it to E.
Return the new EDGE_INFO structure. */
@@ -1416,61 +730,6 @@ canonicalize_comparison (gcond *condstmt)
}
}
-/* Initialize local stacks for this optimizer and record equivalences
- upon entry to BB. Equivalences can come from the edge traversed to
- reach BB or they may come from PHI nodes at the start of BB. */
-
-/* Remove all the expressions in LOCALS from TABLE, stopping when there are
- LIMIT entries left in LOCALs. */
-
-void
-avail_exprs_stack::pop_to_marker ()
-{
- /* Remove all the expressions made available in this block. */
- while (m_stack.length () > 0)
- {
- std::pair<expr_hash_elt_t, expr_hash_elt_t> victim = m_stack.pop ();
- expr_hash_elt **slot;
-
- if (victim.first == NULL)
- break;
-
- /* 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, "<<<< ");
- victim.first->print (dump_file);
- }
-
- slot = m_avail_exprs->find_slot (victim.first, NO_INSERT);
- gcc_assert (slot && *slot == victim.first);
- if (victim.second != NULL)
- {
- free_expr_hash_elt (*slot);
- *slot = victim.second;
- }
- else
- m_avail_exprs->clear_slot (slot);
- }
-}
-
-void
-avail_exprs_stack::record_expr (class expr_hash_elt *elt1,
- class expr_hash_elt *elt2,
- char type)
-{
- if (elt1 && dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "%c>>> ", type);
- elt1->print (dump_file);
- }
-
- m_stack.safe_push (std::pair<expr_hash_elt_t, expr_hash_elt_t> (elt1, elt2));
-}
-
-
/* A trivial wrapper so that we can present the generic jump
threading code with a simple API for simplifying statements. */
static tree
@@ -1792,7 +1051,7 @@ record_cond (cond_equivalence *p)
avail_exprs_stack->record_expr (element, NULL, '1');
}
else
- free_expr_hash_elt (element);
+ delete element;
}
/* Return the loop depth of the basic block of the defining statement of X.
@@ -2707,21 +1966,6 @@ lookup_avail_expr (gimple stmt, bool insert)
return lhs;
}
-/* Hashing and equality functions for AVAIL_EXPRS. We compute a value number
- for expressions using the code of the expression and the SSA numbers of
- its operands. */
-
-static hashval_t
-avail_expr_hash (class expr_hash_elt *p)
-{
- const struct hashable_expr *expr = p->expr ();
- inchash::hash hstate;
-
- inchash::add_hashable_expr (expr, hstate);
-
- 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. */
@@ -27,6 +27,581 @@ along with GCC; see the file COPYING3. If not see
#include "tree-pass.h"
#include "tree-ssa-scopedtables.h"
#include "tree-ssa-threadedge.h"
+#include "tree-ssa-dom.h"
+#include "function.h"
+#include "stor-layout.h"
+#include "fold-const.h"
+#include "basic-block.h"
+#include "tree-eh.h"
+#include "internal-fn.h"
+#include "gimple.h"
+#include "dumpfile.h"
+
+static bool hashable_expr_equal_p (const struct hashable_expr *,
+ const struct hashable_expr *);
+
+/* Initialize local stacks for this optimizer and record equivalences
+ upon entry to BB. Equivalences can come from the edge traversed to
+ reach BB or they may come from PHI nodes at the start of BB. */
+
+/* Pop items off the unwinding stack, removing each from the hash table
+ until a marker is encountered. */
+
+void
+avail_exprs_stack::pop_to_marker ()
+{
+ /* Remove all the expressions made available in this block. */
+ while (m_stack.length () > 0)
+ {
+ std::pair<expr_hash_elt_t, expr_hash_elt_t> victim = m_stack.pop ();
+ expr_hash_elt **slot;
+
+ if (victim.first == NULL)
+ break;
+
+ /* 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, "<<<< ");
+ victim.first->print (dump_file);
+ }
+
+ slot = m_avail_exprs->find_slot (victim.first, NO_INSERT);
+ gcc_assert (slot && *slot == victim.first);
+ if (victim.second != NULL)
+ {
+ delete *slot;
+ *slot = victim.second;
+ }
+ else
+ m_avail_exprs->clear_slot (slot);
+ }
+}
+
+/* Add <ELT1,ELT2> to the unwinding stack so they can be later removed
+ from the hash table. */
+
+void
+avail_exprs_stack::record_expr (class expr_hash_elt *elt1,
+ class expr_hash_elt *elt2,
+ char type)
+{
+ if (elt1 && dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "%c>>> ", type);
+ elt1->print (dump_file);
+ }
+
+ m_stack.safe_push (std::pair<expr_hash_elt_t, expr_hash_elt_t> (elt1, elt2));
+}
+
+/* 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 inchash::add_expr in tree.c. */
+
+static void
+add_hashable_expr (const struct hashable_expr *expr, hash &hstate)
+{
+ switch (expr->kind)
+ {
+ case EXPR_SINGLE:
+ inchash::add_expr (expr->ops.single.rhs, hstate);
+ break;
+
+ case EXPR_UNARY:
+ 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
+ compare equal according to operand_equal_p, but which
+ have different hash codes. */
+ if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
+ || expr->ops.unary.op == NON_LVALUE_EXPR)
+ hstate.add_int (TYPE_UNSIGNED (expr->type));
+
+ inchash::add_expr (expr->ops.unary.opnd, hstate);
+ break;
+
+ case EXPR_BINARY:
+ hstate.add_object (expr->ops.binary.op);
+ if (commutative_tree_code (expr->ops.binary.op))
+ inchash::add_expr_commutative (expr->ops.binary.opnd0,
+ expr->ops.binary.opnd1, hstate);
+ else
+ {
+ 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;
+ gcall *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++)
+ 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 ();
+ }
+}
+
+}
+
+/* Hashing and equality functions. We compute a value number for expressions
+ using the code of the expression and the SSA numbers of its operands. */
+
+static hashval_t
+avail_expr_hash (class expr_hash_elt *p)
+{
+ const struct hashable_expr *expr = p->expr ();
+ inchash::hash hstate;
+
+ inchash::add_hashable_expr (expr, hstate);
+
+ return hstate.end ();
+}
+
+/* Compare two hashable_expr structures for equivalence. They are
+ considered equivalent when the expressions they denote must
+ necessarily be equal. The logic is intended to follow that of
+ operand_equal_p in fold-const.c */
+
+static bool
+hashable_expr_equal_p (const struct hashable_expr *expr0,
+ const struct hashable_expr *expr1)
+{
+ tree type0 = expr0->type;
+ tree type1 = expr1->type;
+
+ /* If either type is NULL, there is nothing to check. */
+ if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
+ return false;
+
+ /* If both types don't have the same signedness, precision, and mode,
+ then we can't consider them equal. */
+ if (type0 != type1
+ && (TREE_CODE (type0) == ERROR_MARK
+ || TREE_CODE (type1) == ERROR_MARK
+ || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
+ || TYPE_PRECISION (type0) != TYPE_PRECISION (type1)
+ || TYPE_MODE (type0) != TYPE_MODE (type1)))
+ return false;
+
+ if (expr0->kind != expr1->kind)
+ return false;
+
+ switch (expr0->kind)
+ {
+ case EXPR_SINGLE:
+ return operand_equal_p (expr0->ops.single.rhs,
+ expr1->ops.single.rhs, 0);
+
+ case EXPR_UNARY:
+ if (expr0->ops.unary.op != expr1->ops.unary.op)
+ return false;
+
+ if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
+ || expr0->ops.unary.op == NON_LVALUE_EXPR)
+ && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
+ return false;
+
+ return operand_equal_p (expr0->ops.unary.opnd,
+ 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));
+
+ 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:
+ {
+ size_t i;
+
+ /* If the calls are to different functions, then they
+ clearly cannot be equal. */
+ if (!gimple_call_same_target_p (expr0->ops.call.fn_from,
+ expr1->ops.call.fn_from))
+ return false;
+
+ if (! expr0->ops.call.pure)
+ return false;
+
+ if (expr0->ops.call.nargs != expr1->ops.call.nargs)
+ return false;
+
+ for (i = 0; i < expr0->ops.call.nargs; i++)
+ if (! operand_equal_p (expr0->ops.call.args[i],
+ 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 ();
+ }
+}
+
+/* Given a statement STMT, construct a hash table element. */
+
+expr_hash_elt::expr_hash_elt (gimple stmt, tree orig_lhs)
+{
+ enum gimple_code code = gimple_code (stmt);
+ struct hashable_expr *expr = this->expr ();
+
+ if (code == GIMPLE_ASSIGN)
+ {
+ enum tree_code subcode = gimple_assign_rhs_code (stmt);
+
+ switch (get_gimple_rhs_class (subcode))
+ {
+ case GIMPLE_SINGLE_RHS:
+ 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->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;
+ case GIMPLE_BINARY_RHS:
+ 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.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 ();
+ }
+ }
+ else if (code == GIMPLE_COND)
+ {
+ expr->type = boolean_type_node;
+ expr->kind = EXPR_BINARY;
+ expr->ops.binary.op = gimple_cond_code (stmt);
+ expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
+ expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
+ }
+ else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
+ {
+ size_t nargs = gimple_call_num_args (call_stmt);
+ size_t i;
+
+ gcc_assert (gimple_call_lhs (call_stmt));
+
+ expr->type = TREE_TYPE (gimple_call_lhs (call_stmt));
+ expr->kind = EXPR_CALL;
+ expr->ops.call.fn_from = call_stmt;
+
+ if (gimple_call_flags (call_stmt) & (ECF_CONST | ECF_PURE))
+ expr->ops.call.pure = true;
+ else
+ expr->ops.call.pure = false;
+
+ expr->ops.call.nargs = nargs;
+ expr->ops.call.args = XCNEWVEC (tree, nargs);
+ for (i = 0; i < nargs; i++)
+ expr->ops.call.args[i] = gimple_call_arg (call_stmt, i);
+ }
+ else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
+ {
+ expr->type = TREE_TYPE (gimple_switch_index (swtch_stmt));
+ expr->kind = EXPR_SINGLE;
+ expr->ops.single.rhs = gimple_switch_index (swtch_stmt);
+ }
+ else if (code == GIMPLE_GOTO)
+ {
+ expr->type = TREE_TYPE (gimple_goto_dest (stmt));
+ 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 ();
+
+ m_lhs = orig_lhs;
+ m_vop = gimple_vuse (stmt);
+ m_hash = avail_expr_hash (this);
+ m_stamp = this;
+}
+
+/* Given a hashable_expr expression ORIG and an ORIG_LHS,
+ construct a hash table element. */
+
+expr_hash_elt::expr_hash_elt (struct hashable_expr *orig, tree orig_lhs)
+{
+ m_expr = *orig;
+ m_lhs = orig_lhs;
+ m_vop = NULL_TREE;
+ m_hash = avail_expr_hash (this);
+ m_stamp = this;
+}
+
+/* Copy constructor for a hash table element. */
+
+expr_hash_elt::expr_hash_elt (class expr_hash_elt &old_elt)
+{
+ m_expr = old_elt.m_expr;
+ m_lhs = old_elt.m_lhs;
+ m_vop = old_elt.m_vop;
+ m_hash = old_elt.m_hash;
+ m_stamp = this;
+
+ /* Now deep copy the malloc'd space for CALL and PHI args. */
+ if (old_elt.m_expr.kind == EXPR_CALL)
+ {
+ size_t nargs = old_elt.m_expr.ops.call.nargs;
+ size_t i;
+
+ m_expr.ops.call.args = XCNEWVEC (tree, nargs);
+ for (i = 0; i < nargs; i++)
+ m_expr.ops.call.args[i] = old_elt.m_expr.ops.call.args[i];
+ }
+ else if (old_elt.m_expr.kind == EXPR_PHI)
+ {
+ size_t nargs = old_elt.m_expr.ops.phi.nargs;
+ size_t i;
+
+ m_expr.ops.phi.args = XCNEWVEC (tree, nargs);
+ for (i = 0; i < nargs; i++)
+ m_expr.ops.phi.args[i] = old_elt.m_expr.ops.phi.args[i];
+ }
+}
+
+/* Calls and PHIs have a variable number of arguments that are allocated
+ on the heap. Thus we have to have a special dtor to release them. */
+
+expr_hash_elt::~expr_hash_elt ()
+{
+ if (m_expr.kind == EXPR_CALL)
+ free (m_expr.ops.call.args);
+ else if (m_expr.kind == EXPR_PHI)
+ free (m_expr.ops.phi.args);
+}
+
+/* Print a diagnostic dump of an expression hash table entry. */
+
+void
+expr_hash_elt::print (FILE *stream)
+{
+ fprintf (stream, "STMT ");
+
+ if (m_lhs)
+ {
+ print_generic_expr (stream, m_lhs, 0);
+ fprintf (stream, " = ");
+ }
+
+ switch (m_expr.kind)
+ {
+ case EXPR_SINGLE:
+ print_generic_expr (stream, m_expr.ops.single.rhs, 0);
+ break;
+
+ case EXPR_UNARY:
+ fprintf (stream, "%s ", get_tree_code_name (m_expr.ops.unary.op));
+ print_generic_expr (stream, m_expr.ops.unary.opnd, 0);
+ break;
+
+ case EXPR_BINARY:
+ print_generic_expr (stream, m_expr.ops.binary.opnd0, 0);
+ fprintf (stream, " %s ", get_tree_code_name (m_expr.ops.binary.op));
+ print_generic_expr (stream, m_expr.ops.binary.opnd1, 0);
+ break;
+
+ case EXPR_TERNARY:
+ fprintf (stream, " %s <", get_tree_code_name (m_expr.ops.ternary.op));
+ print_generic_expr (stream, m_expr.ops.ternary.opnd0, 0);
+ fputs (", ", stream);
+ print_generic_expr (stream, m_expr.ops.ternary.opnd1, 0);
+ fputs (", ", stream);
+ print_generic_expr (stream, m_expr.ops.ternary.opnd2, 0);
+ fputs (">", stream);
+ break;
+
+ case EXPR_CALL:
+ {
+ size_t i;
+ size_t nargs = m_expr.ops.call.nargs;
+ gcall *fn_from;
+
+ fn_from = m_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++)
+ {
+ print_generic_expr (stream, m_expr.ops.call.args[i], 0);
+ if (i + 1 < nargs)
+ fprintf (stream, ", ");
+ }
+ fprintf (stream, ")");
+ }
+ break;
+
+ case EXPR_PHI:
+ {
+ size_t i;
+ size_t nargs = m_expr.ops.phi.nargs;
+
+ fprintf (stream, "PHI <");
+ for (i = 0; i < nargs; i++)
+ {
+ print_generic_expr (stream, m_expr.ops.phi.args[i], 0);
+ if (i + 1 < nargs)
+ fprintf (stream, ", ");
+ }
+ fprintf (stream, ">");
+ }
+ break;
+ }
+
+ if (m_vop)
+ {
+ fprintf (stream, " with ");
+ print_generic_expr (stream, m_vop, 0);
+ }
+
+ fprintf (stream, "\n");
+}
/* Pop entries off the stack until we hit the NULL marker.
For each entry popped, use the SRC/DEST pair to restore
@@ -133,3 +708,55 @@ const_and_copies::invalidate (tree lhs)
if (SSA_NAME_VALUE (lhs))
record_const_or_copy (lhs, NULL_TREE);
}
+
+bool
+expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
+{
+ const struct hashable_expr *expr1 = p1->expr ();
+ const struct expr_hash_elt *stamp1 = p1->stamp ();
+ 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;
+
+ if (p1->hash () != 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))
+ return true;
+
+ return false;
+}
+
+/* Given a conditional expression COND as a tree, initialize
+ a hashable_expr expression EXPR. The conditional must be a
+ comparison or logical negation. A constant or a variable is
+ not permitted. */
+
+void
+initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
+{
+ expr->type = boolean_type_node;
+
+ if (COMPARISON_CLASS_P (cond))
+ {
+ expr->kind = EXPR_BINARY;
+ expr->ops.binary.op = TREE_CODE (cond);
+ expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
+ expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
+ }
+ else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
+ {
+ expr->kind = EXPR_UNARY;
+ expr->ops.unary.op = TRUTH_NOT_EXPR;
+ expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
+ }
+ else
+ gcc_unreachable ();
+}
+
@@ -20,6 +20,123 @@ along with GCC; see the file COPYING3. If not see
#ifndef GCC_TREE_SSA_SCOPED_TABLES_H
#define GCC_TREE_SSA_SCOPED_TABLES_H
+/* Representation of a "naked" right-hand-side expression, to be used
+ in recording available expressions in the expression hash table. */
+
+enum expr_kind
+{
+ EXPR_SINGLE,
+ EXPR_UNARY,
+ EXPR_BINARY,
+ EXPR_TERNARY,
+ EXPR_CALL,
+ EXPR_PHI
+};
+
+struct hashable_expr
+{
+ tree type;
+ enum expr_kind kind;
+ union {
+ struct { tree rhs; } single;
+ struct { enum tree_code op; tree opnd; } unary;
+ struct { enum tree_code op; tree opnd0, opnd1; } binary;
+ struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary;
+ struct { gcall *fn_from; bool pure; size_t nargs; tree *args; } call;
+ struct { size_t nargs; tree *args; } phi;
+ } ops;
+};
+
+/* Structure for entries in the expression hash table. */
+
+typedef class expr_hash_elt * expr_hash_elt_t;
+
+class expr_hash_elt
+{
+ public:
+ expr_hash_elt (gimple, tree);
+ expr_hash_elt (tree);
+ expr_hash_elt (struct hashable_expr *, tree);
+ expr_hash_elt (class expr_hash_elt &);
+ ~expr_hash_elt ();
+ void print (FILE *);
+ tree vop (void) { return m_vop; }
+ tree lhs (void) { return m_lhs; }
+ struct hashable_expr *expr (void) { return &m_expr; }
+ expr_hash_elt *stamp (void) { return m_stamp; }
+ hashval_t hash (void) { return m_hash; }
+
+ private:
+ /* The expression (rhs) we want to record. */
+ struct hashable_expr m_expr;
+
+ /* The value (lhs) of this expression. */
+ tree m_lhs;
+
+ /* The virtual operand associated with the nearest dominating stmt
+ loading from or storing to expr. */
+ tree m_vop;
+
+ /* The hash value for RHS. */
+ hashval_t m_hash;
+
+ /* A unique stamp, typically the address of the hash
+ element itself, used in removing entries from the table. */
+ struct expr_hash_elt *m_stamp;
+
+ /* We should never be making assignments between objects in this class.
+ Though it might allow us to exploit C++11 move semantics if we
+ defined the move constructor and move assignment operator. */
+ expr_hash_elt& operator= (const expr_hash_elt&);
+};
+
+/* Hashtable helpers. */
+
+struct expr_elt_hasher : pointer_hash <expr_hash_elt>
+{
+ static inline hashval_t hash (const value_type &p)
+ { return p->hash (); }
+ static bool equal (const value_type &, const compare_type &);
+ static inline void remove (value_type &element)
+ { delete element; }
+};
+
+
+/* This class defines a unwindable expression equivalence table
+ layered on top of the expression hash table.
+
+ Essentially it's just a stack of available expression value pairs with
+ a special marker (NULL, NULL) to indicate unwind points. */
+
+class avail_exprs_stack
+{
+ public:
+ /* We need access to the AVAIL_EXPR hash table so that we can
+ remove entries from the hash table when unwinding the stack. */
+ avail_exprs_stack (hash_table<expr_elt_hasher> *table)
+ { m_stack.create (20); m_avail_exprs = table; }
+ ~avail_exprs_stack (void) { m_stack.release (); }
+
+ /* Push the unwinding marker onto the stack. */
+ void push_marker (void) { record_expr (NULL, NULL, 'M'); }
+
+ /* Restore the AVAIL_EXPRs table to its state when the last marker
+ was pushed. */
+ void pop_to_marker ();
+
+ /* Record a single available expression that can be unwound. */
+ void record_expr (expr_hash_elt_t, expr_hash_elt_t, char);
+
+ private:
+ vec<std::pair<expr_hash_elt_t, expr_hash_elt_t> > m_stack;
+ hash_table<expr_elt_hasher> *m_avail_exprs;
+
+ /* We do not allow copying this object or initializing one
+ from another. */
+ avail_exprs_stack& operator= (const avail_exprs_stack&);
+ avail_exprs_stack (class avail_exprs_stack &);
+};
+
/* This class defines an unwindable const/copy equivalence table
layered on top of SSA_NAME_VALUE/set_ssa_name_value.
@@ -54,6 +171,10 @@ class const_and_copies
private:
vec<tree> m_stack;
+ const_and_copies& operator= (const const_and_copies&);
+ const_and_copies (class const_and_copies &);
};
+void initialize_expr_from_cond (tree cond, struct hashable_expr *expr);
+
#endif /* GCC_TREE_SSA_SCOPED_TABLES_H */
This moves most of the support for scoped hash tables out of DOM. It's highly mechanical. I did fix a few comments along the way and added some private members to the const_and_copies and avail_expr_stack classes to ensure we're following the rule-of-3 guidelines in those classes. I can easily layer the changes to fix 47679 on top of this patch. So we're getting close to the goal line here. Bootstrapped and regression tested on x86_64-linux-gnu. Applied to the trunk. commit 0de8c264e5b6081105ccc31c67912fcd767b98ed Author: Jeff Law <law@redhat.com> Date: Tue Sep 15 21:13:37 2015 -0600 [PATCH] Move code out of tree-ssa-dom into tree-ssa-scopedtables PR tree-optimization/47679 * tree-ssa-dom.c (enum expr_kind): Moved from here to tree-ssa-scopedtables.h. (struct hashable_expr, class expr_hash_elt): Likewise. (struct expr_elt_hasher, class avail_exprs_stack): Likewise. Move associated methods into tree-ssa-scopedtables.c. (avail_expr_hash, initialize_expr_from_cond): Similarly. (hashable_expr_equal_p, add_expr_commutative): Likewise. (add_hashable_expr): Likewise. (record_cond): Delete element directly. * tree-ssa-scopedtables.h (avail_expr_stack, const_and_copies): Add private copy ctor and assignment operator methods. (expr_elt_hasher): Inline trivial methods. (initialize_expr_from_cond): Prototype. * tree-ssa-scopedtables.c: Add necessary includes, functions and methods that were previously in tree-ssa-dom.c. Improve various comments.