From d31398011e31409de9fc3fcc916fcbcd568fc40c Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Wed, 16 Sep 2015 11:25:51 -0600 Subject: [PATCH] [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. From-SVN: r227831 --- gcc/ChangeLog | 20 + gcc/tree-ssa-dom.c | 760 +----------------------------------- gcc/tree-ssa-scopedtables.c | 627 +++++++++++++++++++++++++++++ gcc/tree-ssa-scopedtables.h | 121 ++++++ 4 files changed, 770 insertions(+), 758 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 92f6354b337..49b84380490 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,23 @@ +2015-09-16 Jeff Law + + 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. + 2015-09-16 Paolo Carlini * doc/invoke.texi ([Wsubobject-linkage]): Extend documentation. diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index 9e38541ab03..b97125ae9a0 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -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_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 -{ - 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 *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 > m_stack; - hash_table *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 *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 &); 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 (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 (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 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 (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. */ diff --git a/gcc/tree-ssa-scopedtables.c b/gcc/tree-ssa-scopedtables.c index fedd92a850a..7ef085e38f8 100644 --- a/gcc/tree-ssa-scopedtables.c +++ b/gcc/tree-ssa-scopedtables.c @@ -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 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 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 (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 (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 (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 (); +} + diff --git a/gcc/tree-ssa-scopedtables.h b/gcc/tree-ssa-scopedtables.h index f7d9ca4320c..f37230e6319 100644 --- a/gcc/tree-ssa-scopedtables.h +++ b/gcc/tree-ssa-scopedtables.h @@ -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 +{ + 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 *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 > m_stack; + hash_table *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 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 */ -- 2.30.2