+/* Given a statement STMT, initialize the hash table element pointed to
+ by ELEMENT. */
+
+static void
+initialize_hash_element (gimple stmt, tree lhs,
+ struct expr_hash_elt *element)
+{
+ enum gimple_code code = gimple_code (stmt);
+ struct hashable_expr *expr = &element->expr;
+
+ if (code == GIMPLE_ASSIGN)
+ {
+ enum tree_code subcode = gimple_assign_rhs_code (stmt);
+
+ expr->type = NULL_TREE;
+
+ switch (get_gimple_rhs_class (subcode))
+ {
+ case GIMPLE_SINGLE_RHS:
+ expr->kind = EXPR_SINGLE;
+ expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
+ break;
+ case GIMPLE_UNARY_RHS:
+ expr->kind = EXPR_UNARY;
+ expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
+ expr->ops.unary.op = subcode;
+ expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
+ break;
+ 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;
+ 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 (code == GIMPLE_CALL)
+ {
+ size_t nargs = gimple_call_num_args (stmt);
+ size_t i;
+
+ gcc_assert (gimple_call_lhs (stmt));
+
+ expr->type = TREE_TYPE (gimple_call_lhs (stmt));
+ expr->kind = EXPR_CALL;
+ expr->ops.call.fn = gimple_call_fn (stmt);
+
+ if (gimple_call_flags (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 = (tree *) xcalloc (nargs, sizeof (tree));
+ for (i = 0; i < nargs; i++)
+ expr->ops.call.args[i] = gimple_call_arg (stmt, i);
+ }
+ else if (code == GIMPLE_SWITCH)
+ {
+ expr->type = TREE_TYPE (gimple_switch_index (stmt));
+ expr->kind = EXPR_SINGLE;
+ expr->ops.single.rhs = gimple_switch_index (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
+ gcc_unreachable ();
+
+ element->lhs = lhs;
+ element->stmt = stmt;
+ element->hash = avail_expr_hash (element);
+ element->stamp = element;
+}
+
+/* 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. */
+
+static void
+initialize_hash_element_from_expr (struct hashable_expr *expr,
+ tree lhs,
+ struct expr_hash_elt *element)
+{
+ element->expr = *expr;
+ element->lhs = lhs;
+ element->stmt = NULL;
+ element->hash = avail_expr_hash (element);
+ element->stamp = element;
+}
+
+/* Compare two hashable_expr structures for equivalence.
+ They are considered equivalent when the 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_CALL:
+ {
+ size_t i;
+
+ /* If the calls are to different functions, then they
+ clearly cannot be equal. */
+ if (! operand_equal_p (expr0->ops.call.fn,
+ expr1->ops.call.fn, 0))
+ 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;
+
+ return true;
+ }
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
+/* Compute a hash value for a hashable_expr value EXPR and a
+ previously accumulated hash value VAL. If two hashable_expr
+ values compare equal with hashable_expr_equal_p, they must
+ hash to the same value, given an identical value of VAL.
+ The logic is intended to follow iterative_hash_expr in tree.c. */
+
+static hashval_t
+iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val)
+{
+ switch (expr->kind)
+ {
+ case EXPR_SINGLE:
+ val = iterative_hash_expr (expr->ops.single.rhs, val);
+ break;
+
+ case EXPR_UNARY:
+ val = iterative_hash_object (expr->ops.unary.op, val);
+
+ /* 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)
+ val += TYPE_UNSIGNED (expr->type);
+
+ val = iterative_hash_expr (expr->ops.unary.opnd, val);
+ break;
+
+ case EXPR_BINARY:
+ val = iterative_hash_object (expr->ops.binary.op, val);
+ if (commutative_tree_code (expr->ops.binary.op))
+ val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0,
+ expr->ops.binary.opnd1, val);
+ else
+ {
+ val = iterative_hash_expr (expr->ops.binary.opnd0, val);
+ val = iterative_hash_expr (expr->ops.binary.opnd1, val);
+ }
+ break;
+
+ case EXPR_CALL:
+ {
+ size_t i;
+ enum tree_code code = CALL_EXPR;
+
+ val = iterative_hash_object (code, val);
+ val = iterative_hash_expr (expr->ops.call.fn, val);
+ for (i = 0; i < expr->ops.call.nargs; i++)
+ val = iterative_hash_expr (expr->ops.call.args[i], val);
+ }
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+
+ return val;
+}
+
+/* Print a diagnostic dump of an expression hash table entry. */
+
+static void
+print_expr_hash_elt (FILE * stream, const struct expr_hash_elt *element)
+{
+ if (element->stmt)
+ fprintf (stream, "STMT ");
+ else
+ fprintf (stream, "COND ");
+
+ if (element->lhs)
+ {
+ print_generic_expr (stream, element->lhs, 0);
+ fprintf (stream, " = ");
+ }
+
+ switch (element->expr.kind)
+ {
+ case EXPR_SINGLE:
+ print_generic_expr (stream, element->expr.ops.single.rhs, 0);
+ break;
+
+ case EXPR_UNARY:
+ fprintf (stream, "%s ", tree_code_name[element->expr.ops.unary.op]);
+ print_generic_expr (stream, element->expr.ops.unary.opnd, 0);
+ break;
+
+ case EXPR_BINARY:
+ print_generic_expr (stream, element->expr.ops.binary.opnd0, 0);
+ fprintf (stream, " %s ", tree_code_name[element->expr.ops.binary.op]);
+ print_generic_expr (stream, element->expr.ops.binary.opnd1, 0);
+ break;
+
+ case EXPR_CALL:
+ {
+ size_t i;
+ size_t nargs = element->expr.ops.call.nargs;
+
+ print_generic_expr (stream, element->expr.ops.call.fn, 0);
+ fprintf (stream, " (");
+ for (i = 0; i < nargs; i++)
+ {
+ print_generic_expr (stream, element->expr.ops.call.args[i], 0);
+ if (i + 1 < nargs)
+ fprintf (stream, ", ");
+ }
+ fprintf (stream, ")");
+ }
+ break;
+ }
+ fprintf (stream, "\n");
+
+ if (element->stmt)
+ {
+ fprintf (stream, " ");
+ print_gimple_stmt (stream, element->stmt, 0, 0);
+ }
+}
+
+/* Delete an expr_hash_elt and reclaim its storage. */
+
+static void
+free_expr_hash_elt (void *elt)
+{
+ struct expr_hash_elt *element = ((struct expr_hash_elt *)elt);
+
+ if (element->expr.kind == EXPR_CALL)
+ free (element->expr.ops.call.args);
+
+ free (element);
+}
+