[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

4 files changed, 770 insertions, 758 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 92f6354..49b8438 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,23 @@
+2015-09-16  Jeff Law  <law@redhat.com>
+
+	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  <paolo.carlini@oracle.com>
 
 	* doc/invoke.texi ([Wsubobject-linkage]): Extend documentation.
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 9e38541..b97125a 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_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.  */
 
diff --git a/gcc/tree-ssa-scopedtables.c b/gcc/tree-ssa-scopedtables.c
index fedd92a..7ef085e 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<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 ();
+}
+
diff --git a/gcc/tree-ssa-scopedtables.h b/gcc/tree-ssa-scopedtables.h
index f7d9ca4..f37230e 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 <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 */