diff options
Diffstat (limited to 'gcc/tree-ssa-scopedtables.c')
| -rw-r--r-- | gcc/tree-ssa-scopedtables.c | 271 |
1 files changed, 271 insertions, 0 deletions
diff --git a/gcc/tree-ssa-scopedtables.c b/gcc/tree-ssa-scopedtables.c index e5de6a5..3e72333 100644 --- a/gcc/tree-ssa-scopedtables.c +++ b/gcc/tree-ssa-scopedtables.c @@ -33,6 +33,8 @@ along with GCC; see the file COPYING3. If not see #include "tree-eh.h" #include "internal-fn.h" #include "tree-dfa.h" +#include "options.h" +#include "params.h" static bool hashable_expr_equal_p (const struct hashable_expr *, const struct hashable_expr *); @@ -94,6 +96,153 @@ avail_exprs_stack::record_expr (class expr_hash_elt *elt1, m_stack.safe_push (std::pair<expr_hash_elt_t, expr_hash_elt_t> (elt1, elt2)); } +/* Helper for walk_non_aliased_vuses. Determine if we arrived at + the desired memory state. */ + +static void * +vuse_eq (ao_ref *, tree vuse1, unsigned int cnt, void *data) +{ + tree vuse2 = (tree) data; + if (vuse1 == vuse2) + return data; + + /* This bounds the stmt walks we perform on reference lookups + to O(1) instead of O(N) where N is the number of dominating + stores leading to a candidate. We re-use the SCCVN param + for this as it is basically the same complexity. */ + if (cnt > (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS)) + return (void *)-1; + + return NULL; +} + +/* Search for an existing instance of STMT in the AVAIL_EXPRS_STACK table. + If found, return its LHS. Otherwise insert STMT in the table and + return NULL_TREE. + + Also, when an expression is first inserted in the table, it is also + is also added to AVAIL_EXPRS_STACK, so that it can be removed when + we finish processing this block and its children. */ + +tree +avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p) +{ + expr_hash_elt **slot; + tree lhs; + + /* 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); + + class expr_hash_elt element (stmt, lhs); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "LKUP "); + element.print (dump_file); + } + + /* 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))) + return NULL_TREE; + + /* Finally try to find the expression in the main expression hash table. */ + slot = m_avail_exprs->find_slot (&element, (insert ? INSERT : NO_INSERT)); + if (slot == NULL) + { + return NULL_TREE; + } + else if (*slot == NULL) + { + class expr_hash_elt *element2 = new expr_hash_elt (element); + *slot = element2; + + record_expr (element2, NULL, '2'); + return NULL_TREE; + } + + /* If we found a redundant memory operation do an alias walk to + check if we can re-use it. */ + if (gimple_vuse (stmt) != (*slot)->vop ()) + { + tree vuse1 = (*slot)->vop (); + tree vuse2 = gimple_vuse (stmt); + /* If we have a load of a register and a candidate in the + hash with vuse1 then try to reach its stmt by walking + up the virtual use-def chain using walk_non_aliased_vuses. + But don't do this when removing expressions from the hash. */ + ao_ref ref; + if (!(vuse1 && vuse2 + && gimple_assign_single_p (stmt) + && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME + && (ao_ref_init (&ref, gimple_assign_rhs1 (stmt)), + ref.base_alias_set = ref.ref_alias_set = tbaa_p ? -1 : 0, true) + && walk_non_aliased_vuses (&ref, vuse2, + vuse_eq, NULL, NULL, vuse1) != NULL)) + { + if (insert) + { + class expr_hash_elt *element2 = new expr_hash_elt (element); + + /* Insert the expr into the hash by replacing the current + entry and recording the value to restore in the + avail_exprs_stack. */ + record_expr (element2, *slot, '2'); + *slot = element2; + } + return NULL_TREE; + } + } + + /* Extract the LHS of the assignment so that it can be used as the current + definition of another variable. */ + lhs = (*slot)->lhs (); + + /* Valueize the result. */ + if (TREE_CODE (lhs) == SSA_NAME) + { + tree tem = SSA_NAME_VALUE (lhs); + if (tem) + lhs = tem; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "FIND: "); + print_generic_expr (dump_file, lhs, 0); + fprintf (dump_file, "\n"); + } + + return lhs; +} + +/* Enter condition equivalence P into the hash table. + + This indicates that a conditional expression has a known + boolean value. */ + +void +avail_exprs_stack::record_cond (cond_equivalence *p) +{ + class expr_hash_elt *element = new expr_hash_elt (&p->cond, p->value); + expr_hash_elt **slot; + + slot = m_avail_exprs->find_slot_with_hash (element, element->hash (), INSERT); + if (*slot == NULL) + { + *slot = element; + record_expr (element, NULL, '1'); + } + else + delete element; +} + /* Generate a hash value for a pair of expressions. This can be used iteratively by passing a previous result in HSTATE. @@ -798,3 +947,125 @@ initialize_expr_from_cond (tree cond, struct hashable_expr *expr) gcc_unreachable (); } +/* Build a cond_equivalence record indicating that the comparison + 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, + vec<cond_equivalence> *p, + bool val = true) +{ + cond_equivalence c; + struct hashable_expr *cond = &c.cond; + + gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison); + + cond->type = boolean_type_node; + cond->kind = EXPR_BINARY; + cond->ops.binary.op = code; + cond->ops.binary.opnd0 = op0; + cond->ops.binary.opnd1 = op1; + + c.value = val ? boolean_true_node : boolean_false_node; + p->safe_push (c); +} + +/* Record that COND is true and INVERTED is false into the edge information + structure. Also record that any conditions dominated by COND are true + as well. + + For example, if a < b is true, then a <= b must also be true. */ + +void +record_conditions (vec<cond_equivalence> *p, tree cond, tree inverted) +{ + tree op0, op1; + cond_equivalence c; + + if (!COMPARISON_CLASS_P (cond)) + return; + + op0 = TREE_OPERAND (cond, 0); + op1 = TREE_OPERAND (cond, 1); + + switch (TREE_CODE (cond)) + { + case LT_EXPR: + case GT_EXPR: + if (FLOAT_TYPE_P (TREE_TYPE (op0))) + { + build_and_record_new_cond (ORDERED_EXPR, op0, op1, p); + build_and_record_new_cond (LTGT_EXPR, op0, op1, p); + } + + build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR + ? LE_EXPR : GE_EXPR), + op0, op1, p); + build_and_record_new_cond (NE_EXPR, op0, op1, p); + build_and_record_new_cond (EQ_EXPR, op0, op1, p, false); + break; + + case GE_EXPR: + case LE_EXPR: + if (FLOAT_TYPE_P (TREE_TYPE (op0))) + { + build_and_record_new_cond (ORDERED_EXPR, op0, op1, p); + } + break; + + case EQ_EXPR: + if (FLOAT_TYPE_P (TREE_TYPE (op0))) + { + build_and_record_new_cond (ORDERED_EXPR, op0, op1, p); + } + build_and_record_new_cond (LE_EXPR, op0, op1, p); + build_and_record_new_cond (GE_EXPR, op0, op1, p); + break; + + case UNORDERED_EXPR: + build_and_record_new_cond (NE_EXPR, op0, op1, p); + build_and_record_new_cond (UNLE_EXPR, op0, op1, p); + build_and_record_new_cond (UNGE_EXPR, op0, op1, p); + build_and_record_new_cond (UNEQ_EXPR, op0, op1, p); + build_and_record_new_cond (UNLT_EXPR, op0, op1, p); + build_and_record_new_cond (UNGT_EXPR, op0, op1, p); + break; + + case UNLT_EXPR: + case UNGT_EXPR: + build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR + ? UNLE_EXPR : UNGE_EXPR), + op0, op1, p); + build_and_record_new_cond (NE_EXPR, op0, op1, p); + break; + + case UNEQ_EXPR: + build_and_record_new_cond (UNLE_EXPR, op0, op1, p); + build_and_record_new_cond (UNGE_EXPR, op0, op1, p); + break; + + case LTGT_EXPR: + build_and_record_new_cond (NE_EXPR, op0, op1, p); + build_and_record_new_cond (ORDERED_EXPR, op0, op1, p); + break; + + default: + break; + } + + /* Now store the original true and false conditions into the first + two slots. */ + initialize_expr_from_cond (cond, &c.cond); + c.value = boolean_true_node; + p->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, &c.cond); + c.value = boolean_false_node; + p->safe_push (c); +} |