tree-ssa-dom.c (struct edge_info): New structure holding edge equivalences and edge redirection information.

	* tree-ssa-dom.c (struct edge_info): New structure holding
	edge equivalences and edge redirection information.
	(get_eq_expr_value, record_dominating_conditions): Kill.
	(propagate_to_outgoing_edges): Renamed from cprop_into_phis.
	Call record_edge_info.
	(allocate_edge_info, free_edge_info): New.
	(tree_ssa_dominator_optimize): Use propagate_to_outgoing_edges
	rather than cprop_into_phis.  Free all edge infos before threading
	jumps.
	(thread_across_edge): Allocate new edge info structures as needed
	and store the redirection target into the edge info structure
	instead of the edge's AUX field.
	(dom_opt_initialize_block): Mark unused argument with ATTRIBUTE_UNUSED.
	(record_equivalence_from_incoming_edge): Lose unnecessary argument.
	Revamp code which finds and records equivalences associated with
	edges to use saved data in the edge_info structure.
	(record_equivalencs_from_phis): Similarly.
	(dom_opt_finalize_block): Revamp code which finds and records
	equivalences associated with edges to use saved data in the
	edge_info structure.
	(build_and_record_new_cond): New function.
	(record_conditions): Use build_and_record_new_cond to record
	dominating conditions.
	(record_edge_info): New function.
	(record_range): Tighten test for conditions which create
	useful range records.

From-SVN: r89866

1 files changed, 482 insertions, 363 deletions

diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 41102ea..b50767f 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -45,6 +45,40 @@ Boston, MA 02111-1307, USA.  */
 
 /* This file implements optimizations on the dominator tree.  */
 
+
+/* Structure for recording edge equivalences as well as any pending
+   edge redirections during the dominator optimizer.
+
+   Computing and storing the edge equivalences instead of creating
+   them on-demand can save significant amounts of time, particularly
+   for pathological cases involving switch statements.  
+
+   These structures live for a single iteration of the dominator
+   optimizer in the edge's AUX field.  At the end of an iteration we
+   free each of these structures and update the AUX field to point
+   to any requested redirection target (the code for updating the
+   CFG and SSA graph for edge redirection expects redirection edge
+   targets to be in the AUX field for each edge.  */
+
+struct edge_info
+{
+  /* If this edge creates a simple equivalence, the LHS and RHS of
+     the equivalence will be stored here.  */
+  tree lhs;
+  tree rhs;
+
+  /* Traversing an edge may also indicate one or more particular conditions
+     are true or false.  The number of recorded conditions can vary, but
+     can be determined by the condition's code.  So we have an array
+     and its maximum index rather than use a varray.  */
+  tree *cond_equivalences;
+  unsigned int max_cond_equivalences;
+
+  /* If we can thread this edge this field records the new target.  */
+  edge redirection_target;
+};
+
+
 /* 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
@@ -231,7 +265,6 @@ static void optimize_stmt (struct dom_walk_data *,
 			   basic_block bb,
 			   block_stmt_iterator);
 static tree lookup_avail_expr (tree, bool);
-static struct eq_expr_value get_eq_expr_value (tree, int, basic_block);
 static hashval_t vrp_hash (const void *);
 static int vrp_eq (const void *, const void *);
 static hashval_t avail_expr_hash (const void *);
@@ -239,7 +272,6 @@ static hashval_t real_avail_expr_hash (const void *);
 static int avail_expr_eq (const void *, const void *);
 static void htab_statistics (FILE *, htab_t);
 static void record_cond (tree, tree);
-static void record_dominating_conditions (tree);
 static void record_const_or_copy (tree, tree);
 static void record_equality (tree, tree);
 static tree update_rhs_and_lookup_avail_expr (tree, tree, bool);
@@ -250,16 +282,15 @@ static tree simplify_switch_and_lookup_avail_expr (tree, int);
 static tree find_equivalent_equality_comparison (tree);
 static void record_range (tree, basic_block);
 static bool extract_range_from_cond (tree, tree *, tree *, int *);
-static void record_equivalences_from_phis (struct dom_walk_data *, basic_block);
-static void record_equivalences_from_incoming_edge (struct dom_walk_data *,
-						    basic_block);
+static void record_equivalences_from_phis (basic_block);
+static void record_equivalences_from_incoming_edge (basic_block);
 static bool eliminate_redundant_computations (struct dom_walk_data *,
 					      tree, stmt_ann_t);
 static void record_equivalences_from_stmt (tree, int, stmt_ann_t);
 static void thread_across_edge (struct dom_walk_data *, edge);
 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
 static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
-static void cprop_into_phis (struct dom_walk_data *, basic_block);
+static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
 static void remove_local_expressions_from_table (void);
 static void restore_vars_to_original_value (void);
 static void restore_currdefs_to_original_value (void);
@@ -283,6 +314,50 @@ local_fold (tree t)
   return t;
 }
 
+/* Allocate an EDGE_INFO for edge E and attach it to E.
+   Return the new EDGE_INFO structure.  */
+
+static struct edge_info *
+allocate_edge_info (edge e)
+{
+  struct edge_info *edge_info;
+
+  edge_info = xcalloc (1, sizeof (struct edge_info));
+
+  e->aux = edge_info;
+  return edge_info;
+}
+
+/* Free all EDGE_INFO structures associated with edges in the CFG.
+   If a partciular edge can be threaded, copy the redirection
+   target from the EDGE_INFO structure into the edge's AUX field
+   as required by code to update the CFG and SSA graph for
+   jump threading.  */
+
+static void
+free_all_edge_infos (void)
+{
+  basic_block bb;
+  edge_iterator ei;
+  edge e;
+
+  FOR_EACH_BB (bb)
+    {
+      FOR_EACH_EDGE (e, ei, bb->preds)
+        {
+	 struct edge_info *edge_info = e->aux;
+
+	  if (edge_info)
+	    {
+	      e->aux = edge_info->redirection_target;
+	      if (edge_info->cond_equivalences)
+		free (edge_info->cond_equivalences);
+	      free (edge_info);
+	    }
+	}
+    }
+}
+
 /* Jump threading, redundancy elimination and const/copy propagation. 
 
    This pass may expose new symbols that need to be renamed into SSA.  For
@@ -323,7 +398,7 @@ tree_ssa_dominator_optimize (void)
   walk_data.initialize_block_local_data = NULL;
   walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
   walk_data.before_dom_children_walk_stmts = optimize_stmt;
-  walk_data.before_dom_children_after_stmts = cprop_into_phis;
+  walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;
   walk_data.after_dom_children_before_stmts = NULL;
   walk_data.after_dom_children_walk_stmts = NULL;
   walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
@@ -362,6 +437,8 @@ tree_ssa_dominator_optimize (void)
 	  bitmap_clear (vars_to_rename);
 	}
 
+      free_all_edge_infos ();
+
       /* Thread jumps, creating duplicate blocks as needed.  */
       cfg_altered = thread_through_all_blocks ();
 
@@ -697,9 +774,15 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
 	     bypass the conditional at our original destination.  */
 	  if (dest)
 	    {
+	      struct edge_info *edge_info;
+
 	      update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
 					       e->count, taken_edge);
-	      e->aux = taken_edge;
+	      if (e->aux)
+		edge_info = e->aux;
+	      else
+		edge_info = allocate_edge_info (e);
+	      edge_info->redirection_target = taken_edge;
 	      bb_ann (e->dest)->incoming_edge_threaded = true;
 	    }
 	}
@@ -712,7 +795,8 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
    reach BB or they may come from PHI nodes at the start of BB.  */
 
 static void
-dom_opt_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
+dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			  basic_block bb)
 {
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
@@ -725,10 +809,10 @@ dom_opt_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
   VARRAY_PUSH_TREE (nonzero_vars_stack, NULL_TREE);
   VARRAY_PUSH_TREE (vrp_variables_stack, NULL_TREE);
 
-  record_equivalences_from_incoming_edge (walk_data, bb);
+  record_equivalences_from_incoming_edge (bb);
 
   /* PHI nodes can create equivalences too.  */
-  record_equivalences_from_phis (walk_data, bb);
+  record_equivalences_from_phis (bb);
 }
 
 /* Given an expression EXPR (a relational expression or a statement), 
@@ -900,22 +984,17 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
 	   && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
     {
       edge true_edge, false_edge;
-      tree cond, inverted = NULL;
-      enum tree_code cond_code;
 
       extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
 
-      cond = COND_EXPR_COND (last);
-      cond_code = TREE_CODE (cond);
-
-      if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
-	inverted = invert_truthvalue (cond);
-
       /* If the THEN arm is the end of a dominator tree or has PHI nodes,
 	 then try to thread through its edge.  */
       if (get_immediate_dominator (CDI_DOMINATORS, true_edge->dest) != bb
 	  || phi_nodes (true_edge->dest))
 	{
+	  struct edge_info *edge_info;
+	  unsigned int i;
+
 	  /* Push a marker onto the available expression stack so that we
 	     unwind any expressions related to the TRUE arm before processing
 	     the false arm below.  */
@@ -923,15 +1002,38 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
 	  VARRAY_PUSH_TREE (block_defs_stack, NULL_TREE);
 	  VARRAY_PUSH_TREE (const_and_copies_stack, NULL_TREE);
 
-	  /* Record any equivalences created by following this edge.  */
-	  if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
+	  edge_info = true_edge->aux;
+
+	  /* If we have info associated with this edge, record it into
+	     our equivalency tables.  */
+	  if (edge_info)
 	    {
-	      record_cond (cond, boolean_true_node);
-	      record_dominating_conditions (cond);
-	      record_cond (inverted, boolean_false_node);
+	      tree *cond_equivalences = edge_info->cond_equivalences;
+	      tree lhs = edge_info->lhs;
+	      tree rhs = edge_info->rhs;
+
+	      /* If we have a simple NAME = VALUE equivalency record it.
+		 Until the jump threading selection code improves, only
+		 do this if both the name and value are SSA_NAMEs with
+		 the same underlying variable to avoid missing threading
+		 opportunities.  */
+	      if (lhs
+		  && TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME
+		  && TREE_CODE (edge_info->rhs) == SSA_NAME
+		  && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs))
+		record_const_or_copy (lhs, rhs);
+
+	      /* If we have 0 = COND or 1 = COND equivalences, record them
+		 into our expression hash tables.  */
+	      if (cond_equivalences)
+		for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
+		  {
+		    tree expr = cond_equivalences[i];
+		    tree value = cond_equivalences[i + 1];
+
+		    record_cond (expr, value);
+		  }
 	    }
-	  else if (cond_code == SSA_NAME)
-	    record_const_or_copy (cond, boolean_true_node);
 
 	  /* Now thread the edge.  */
 	  thread_across_edge (walk_data, true_edge);
@@ -947,15 +1049,39 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
       if (get_immediate_dominator (CDI_DOMINATORS, false_edge->dest) != bb
 	  || phi_nodes (false_edge->dest))
 	{
-	  /* Record any equivalences created by following this edge.  */
-	  if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
+	  struct edge_info *edge_info;
+	  unsigned int i;
+
+	  edge_info = false_edge->aux;
+
+	  /* If we have info associated with this edge, record it into
+	     our equivalency tables.  */
+	  if (edge_info)
 	    {
-	      record_cond (cond, boolean_false_node);
-	      record_cond (inverted, boolean_true_node);
-	      record_dominating_conditions (inverted);
+	      tree *cond_equivalences = edge_info->cond_equivalences;
+	      tree lhs = edge_info->lhs;
+	      tree rhs = edge_info->rhs;
+
+	      /* If we have a simple NAME = VALUE equivalency record it.
+		 Until the jump threading selection code improves, only
+		 do this if both the name and value are SSA_NAMEs with
+		 the same underlying variable to avoid missing threading
+		 opportunities.  */
+	      if (lhs
+		  && TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
+		record_const_or_copy (lhs, rhs);
+
+	      /* If we have 0 = COND or 1 = COND equivalences, record them
+		 into our expression hash tables.  */
+	      if (cond_equivalences)
+		for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
+		  {
+		    tree expr = cond_equivalences[i];
+		    tree value = cond_equivalences[i + 1];
+
+		    record_cond (expr, value);
+		  }
 	    }
-	  else if (cond_code == SSA_NAME)
-	    record_const_or_copy (cond, boolean_false_node);
 
 	  thread_across_edge (walk_data, false_edge);
 
@@ -1040,8 +1166,7 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
    even if we do not know its exact value.  */
 
 static void
-record_equivalences_from_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
-			       basic_block bb)
+record_equivalences_from_phis (basic_block bb)
 {
   tree phi;
 
@@ -1138,110 +1263,62 @@ single_incoming_edge_ignoring_loop_edges (basic_block bb)
    has more than one incoming edge, then no equivalence is created.  */
 
 static void
-record_equivalences_from_incoming_edge (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
-					basic_block bb)
+record_equivalences_from_incoming_edge (basic_block bb)
 {
-  int edge_flags;
+  edge e;
   basic_block parent;
-  struct eq_expr_value eq_expr_value;
-  tree parent_block_last_stmt = NULL;
+  struct edge_info *edge_info;
 
   /* If our parent block ended with a control statment, then we may be
      able to record some equivalences based on which outgoing edge from
      the parent was followed.  */
   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
-  if (parent)
-    {
-      parent_block_last_stmt = last_stmt (parent);
-      if (parent_block_last_stmt && !is_ctrl_stmt (parent_block_last_stmt))
-	parent_block_last_stmt = NULL;
-    }
 
-  eq_expr_value.src = NULL;
-  eq_expr_value.dst = NULL;
+  e = single_incoming_edge_ignoring_loop_edges (bb);
 
-  /* If we have a single predecessor (ignoring loop backedges), then extract
-     EDGE_FLAGS from the single incoming edge.  Otherwise just return as
-     there is nothing to do.  */
-  if (EDGE_COUNT (bb->preds) >= 1
-      && parent_block_last_stmt)
+  /* If we had a single incoming edge from our parent block, then enter
+     any data associated with the edge into our tables.  */
+  if (e && e->src == parent)
     {
-      edge e = single_incoming_edge_ignoring_loop_edges (bb);
-      if (e && bb_for_stmt (parent_block_last_stmt) == e->src)
-	edge_flags = e->flags;
-      else
-	return;
-    }
-  else
-    return;
+      unsigned int i;
 
-  /* If our parent block ended in a COND_EXPR, add any equivalences
-     created by the COND_EXPR to the hash table and initialize
-     EQ_EXPR_VALUE appropriately.
-
-     EQ_EXPR_VALUE is an assignment expression created when BB's immediate
-     dominator ends in a COND_EXPR statement whose predicate is of the form
-     'VAR == VALUE', where VALUE may be another variable or a constant.
-     This is used to propagate VALUE on the THEN_CLAUSE of that
-     conditional. This assignment is inserted in CONST_AND_COPIES so that
-     the copy and constant propagator can find more propagation
-     opportunities.  */
-  if (TREE_CODE (parent_block_last_stmt) == COND_EXPR
-      && (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
-    eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
-				       (edge_flags & EDGE_TRUE_VALUE) != 0,
-				       bb);
-  /* Similarly when the parent block ended in a SWITCH_EXPR.
-     We can only know the value of the switch's condition if the dominator
-     parent is also the only predecessor of this block.  */
-  else if (EDGE_PRED (bb, 0)->src == parent
-	   && TREE_CODE (parent_block_last_stmt) == SWITCH_EXPR)
-    {
-      tree switch_cond = SWITCH_COND (parent_block_last_stmt);
+      edge_info = e->aux;
 
-      /* If the switch's condition is an SSA variable, then we may
-	 know its value at each of the case labels.  */
-      if (TREE_CODE (switch_cond) == SSA_NAME)
+      if (edge_info)
 	{
-	  tree switch_vec = SWITCH_LABELS (parent_block_last_stmt);
-	  size_t i, n = TREE_VEC_LENGTH (switch_vec);
-	  int case_count = 0;
-	  tree match_case = NULL_TREE;
-
-	  /* Search the case labels for those whose destination is
-	     the current basic block.  */
-	  for (i = 0; i < n; ++i)
+	  tree lhs = edge_info->lhs;
+	  tree rhs = edge_info->rhs;
+	  tree *cond_equivalences = edge_info->cond_equivalences;
+
+	  if (lhs)
+	    record_equality (lhs, rhs);
+
+	  if (cond_equivalences)
 	    {
-	      tree elt = TREE_VEC_ELT (switch_vec, i);
-	      if (label_to_block (CASE_LABEL (elt)) == bb)
+	      bool recorded_range = false;
+	      for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
 		{
-		  if (++case_count > 1 || CASE_HIGH (elt))
-		    break;
-		  match_case = elt;
+		  tree expr = cond_equivalences[i];
+		  tree value = cond_equivalences[i + 1];
+
+		  record_cond (expr, value);
+
+		  /* For the first true equivalence, record range
+		     information.  We only do this for the first
+		     true equivalence as it should dominate any
+		     later true equivalences.  */
+		  if (! recorded_range 
+		      && COMPARISON_CLASS_P (expr)
+		      && value == boolean_true_node
+		      && TREE_CONSTANT (TREE_OPERAND (expr, 1)))
+		    {
+		      record_range (expr, bb);
+		      recorded_range = true;
+		    }
 		}
 	    }
-
-	  /* If we encountered precisely one CASE_LABEL_EXPR and it
-	     was not the default case, or a case range, then we know
-	     the exact value of SWITCH_COND which caused us to get to
-	     this block.  Record that equivalence in EQ_EXPR_VALUE.  */
-	  if (case_count == 1
-	      && match_case
-	      && CASE_LOW (match_case)
-	      && !CASE_HIGH (match_case))
-	    {
-	      eq_expr_value.dst = switch_cond;
-	      eq_expr_value.src = fold_convert (TREE_TYPE (switch_cond),
-						CASE_LOW (match_case));
-	    }
 	}
     }
-
-  /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
-     new value for VAR, so that occurrences of VAR can be replaced with
-     VALUE while re-writing the THEN arm of a COND_EXPR.  */
-  if (eq_expr_value.src && eq_expr_value.dst)
-    record_equality (eq_expr_value.dst, eq_expr_value.src);
 }
 
 /* Dump SSA statistics on FILE.  */
@@ -1333,150 +1410,129 @@ record_cond (tree cond, tree value)
     free (element);
 }
 
-/* COND is a condition which is known to be true.   Record variants of
-   COND which must also be true.
+/* Build a new conditional using NEW_CODE, OP0 and OP1 and store
+   the new conditional into *p, then store a boolean_true_node
+   into the the *(p + 1).  */
+   
+static void
+build_and_record_new_cond (enum tree_code new_code, tree op0, tree op1, tree *p)
+{
+  *p = build2 (new_code, boolean_type_node, op0, op1);
+  p++;
+  *p = boolean_true_node;
+}
+
+/* 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.  */
 
 static void
-record_dominating_conditions (tree cond)
+record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
 {
+  tree op0, op1;
+
+  if (!COMPARISON_CLASS_P (cond))
+    return;
+
+  op0 = TREE_OPERAND (cond, 0);
+  op1 = TREE_OPERAND (cond, 1);
+
   switch (TREE_CODE (cond))
     {
     case LT_EXPR:
-      record_cond (build2 (LE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (ORDERED_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (NE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (LTGT_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      break;
-
     case GT_EXPR:
-      record_cond (build2 (GE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (ORDERED_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (NE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (LTGT_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
+      edge_info->max_cond_equivalences = 12;
+      edge_info->cond_equivalences = xmalloc (12 * sizeof (tree));
+      build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
+				  ? LE_EXPR : GE_EXPR),
+				 op0, op1, &edge_info->cond_equivalences[4]);
+      build_and_record_new_cond (ORDERED_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[6]);
+      build_and_record_new_cond (NE_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[8]);
+      build_and_record_new_cond (LTGT_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[10]);
       break;
 
     case GE_EXPR:
     case LE_EXPR:
-      record_cond (build2 (ORDERED_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
+      edge_info->max_cond_equivalences = 6;
+      edge_info->cond_equivalences = xmalloc (6 * sizeof (tree));
+      build_and_record_new_cond (ORDERED_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[4]);
       break;
 
     case EQ_EXPR:
-      record_cond (build2 (ORDERED_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (LE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (GE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
+      edge_info->max_cond_equivalences = 10;
+      edge_info->cond_equivalences = xmalloc (10 * sizeof (tree));
+      build_and_record_new_cond (ORDERED_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[4]);
+      build_and_record_new_cond (LE_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[6]);
+      build_and_record_new_cond (GE_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[8]);
       break;
 
     case UNORDERED_EXPR:
-      record_cond (build2 (NE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (UNLE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (UNGE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (UNEQ_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (UNLT_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (UNGT_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
+      edge_info->max_cond_equivalences = 16;
+      edge_info->cond_equivalences = xmalloc (16 * sizeof (tree));
+      build_and_record_new_cond (NE_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[4]);
+      build_and_record_new_cond (UNLE_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[6]);
+      build_and_record_new_cond (UNGE_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[8]);
+      build_and_record_new_cond (UNEQ_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[10]);
+      build_and_record_new_cond (UNLT_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[12]);
+      build_and_record_new_cond (UNGT_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[14]);
       break;
 
     case UNLT_EXPR:
-      record_cond (build2 (UNLE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (NE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      break;
-
     case UNGT_EXPR:
-      record_cond (build2 (UNGE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (NE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
+      edge_info->max_cond_equivalences = 8;
+      edge_info->cond_equivalences = xmalloc (8 * sizeof (tree));
+      build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
+				  ? UNLE_EXPR : UNGE_EXPR),
+				 op0, op1, &edge_info->cond_equivalences[4]);
+      build_and_record_new_cond (NE_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[6]);
       break;
 
     case UNEQ_EXPR:
-      record_cond (build2 (UNLE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (UNGE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
+      edge_info->max_cond_equivalences = 8;
+      edge_info->cond_equivalences = xmalloc (8 * sizeof (tree));
+      build_and_record_new_cond (UNLE_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[4]);
+      build_and_record_new_cond (UNGE_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[6]);
       break;
 
     case LTGT_EXPR:
-      record_cond (build2 (NE_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
-      record_cond (build2 (ORDERED_EXPR, boolean_type_node,
-			   TREE_OPERAND (cond, 0),
-			   TREE_OPERAND (cond, 1)),
-		   boolean_true_node);
+      edge_info->max_cond_equivalences = 8;
+      edge_info->cond_equivalences = xmalloc (8 * sizeof (tree));
+      build_and_record_new_cond (NE_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[4]);
+      build_and_record_new_cond (ORDERED_EXPR, op0, op1,
+				 &edge_info->cond_equivalences[6]);
+      break;
 
     default:
+      edge_info->max_cond_equivalences = 4;
+      edge_info->cond_equivalences = xmalloc (4 * sizeof (tree));
       break;
     }
+
+  /* Now store the original true and false conditions into the first
+     two slots.  */
+  edge_info->cond_equivalences[0] = cond;
+  edge_info->cond_equivalences[1] = boolean_true_node;
+  edge_info->cond_equivalences[2] = inverted;
+  edge_info->cond_equivalences[3] = boolean_false_node;
 }
 
 /* A helper function for record_const_or_copy and record_equality.
@@ -2311,14 +2367,198 @@ cprop_into_successor_phis (basic_block bb, bitmap nonzero_vars)
     }
 }
 
+/* We have finished optimizing BB, record any information implied by
+   taking a specific outgoing edge from BB.  */
+
+static void
+record_edge_info (basic_block bb)
+{
+  block_stmt_iterator bsi = bsi_last (bb);
+  struct edge_info *edge_info;
+
+  if (! bsi_end_p (bsi))
+    {
+      tree stmt = bsi_stmt (bsi);
+
+      if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
+	{
+	  tree cond = SWITCH_COND (stmt);
+
+	  if (TREE_CODE (cond) == SSA_NAME)
+	    {
+	      tree labels = SWITCH_LABELS (stmt);
+	      int i, n_labels = TREE_VEC_LENGTH (labels);
+	      tree *info = xcalloc (n_basic_blocks, sizeof (tree));
+	      edge e;
+	      edge_iterator ei;
+
+	      for (i = 0; i < n_labels; i++)
+		{
+		  tree label = TREE_VEC_ELT (labels, i);
+		  basic_block target_bb = label_to_block (CASE_LABEL (label));
+
+		  if (CASE_HIGH (label)
+		      || !CASE_LOW (label)
+		      || info[target_bb->index])
+		    info[target_bb->index] = error_mark_node;
+		  else
+		    info[target_bb->index] = label;
+		}
+
+	      FOR_EACH_EDGE (e, ei, bb->succs)
+		{
+		  basic_block target_bb = e->dest;
+		  tree node = info[target_bb->index];
 
-/* Propagate known constants/copies into PHI nodes of BB's successor
-   blocks.  */
+		  if (node != NULL && node != error_mark_node)
+		    {
+		      tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
+		      edge_info = allocate_edge_info (e);
+		      edge_info->lhs = cond;
+		      edge_info->rhs = x;
+		    }
+		}
+	      free (info);
+	    }
+	}
+
+      /* A COND_EXPR may create equivalences too.  */
+      if (stmt && TREE_CODE (stmt) == COND_EXPR)
+	{
+	  tree cond = COND_EXPR_COND (stmt);
+	  edge true_edge;
+	  edge false_edge;
+
+	  extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+
+	  /* If the conditinoal is a single variable 'X', record 'X = 1'
+	     for the true edge and 'X = 0' on the false edge.  */
+	  if (SSA_VAR_P (cond))
+	    {
+	      struct edge_info *edge_info;
+
+	      edge_info = allocate_edge_info (true_edge);
+	      edge_info->lhs = cond;
+	      edge_info->rhs = constant_boolean_node (1, TREE_TYPE (cond));
+
+	      edge_info = allocate_edge_info (false_edge);
+	      edge_info->lhs = cond;
+	      edge_info->rhs = constant_boolean_node (0, TREE_TYPE (cond));
+	    }
+	  /* Equality tests may create one or two equivalences.  */
+	  else if (COMPARISON_CLASS_P (cond))
+	    {
+	      tree op0 = TREE_OPERAND (cond, 0);
+	      tree op1 = TREE_OPERAND (cond, 1);
+
+	      /* Special case comparing booleans against a constant as we
+		 know the value of OP0 on both arms of the branch.  i.e., we
+		 can record an equivalence for OP0 rather than COND.  */
+	      if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
+		  && TREE_CODE (op0) == SSA_NAME
+		  && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
+		  && is_gimple_min_invariant (op1))
+		{
+		  if (TREE_CODE (cond) == EQ_EXPR)
+		    {
+		      edge_info = allocate_edge_info (true_edge);
+		      edge_info->lhs = op0;
+		      edge_info->rhs = (integer_zerop (op1)
+					    ? boolean_false_node
+					    : boolean_true_node);
+
+		      edge_info = allocate_edge_info (false_edge);
+		      edge_info->lhs = op0;
+		      edge_info->rhs = (integer_zerop (op1)
+					    ? boolean_true_node
+					    : boolean_false_node);
+		    }
+		  else
+		    {
+		      edge_info = allocate_edge_info (true_edge);
+		      edge_info->lhs = op0;
+		      edge_info->rhs = (integer_zerop (op1)
+					    ? boolean_true_node
+					    : boolean_false_node);
+
+		      edge_info = allocate_edge_info (false_edge);
+		      edge_info->lhs = op0;
+		      edge_info->rhs = (integer_zerop (op1)
+					    ? boolean_false_node
+					    : boolean_true_node);
+		    }
+		}
+
+	      if (is_gimple_min_invariant (op0)
+		  && (TREE_CODE (op1) == SSA_NAME
+		       || is_gimple_min_invariant (op1)))
+		{
+		  tree inverted = invert_truthvalue (cond);
+		  struct edge_info *edge_info;
+
+		  edge_info = allocate_edge_info (true_edge);
+		  record_conditions (edge_info, cond, inverted);
+
+		  if (TREE_CODE (cond) == EQ_EXPR)
+		    {
+		      edge_info->lhs = op1;
+		      edge_info->rhs = op0;
+		    }
+
+		  edge_info = allocate_edge_info (false_edge);
+		  record_conditions (edge_info, inverted, cond);
+
+		  if (TREE_CODE (cond) == NE_EXPR)
+		    {
+		      edge_info->lhs = op1;
+		      edge_info->rhs = op0;
+		    }
+		}
+
+	      if (TREE_CODE (op0) == SSA_NAME
+		  && (is_gimple_min_invariant (op1)
+		      || TREE_CODE (op1) == SSA_NAME))
+		{
+		  tree inverted = invert_truthvalue (cond);
+		  struct edge_info *edge_info;
+
+		  edge_info = allocate_edge_info (true_edge);
+		  record_conditions (edge_info, cond, inverted);
+
+		  if (TREE_CODE (cond) == EQ_EXPR)
+		    {
+		      edge_info->lhs = op0;
+		      edge_info->rhs = op1;
+		    }
+
+		  edge_info = allocate_edge_info (false_edge);
+		  record_conditions (edge_info, inverted, cond);
+
+		  if (TREE_CODE (cond) == NE_EXPR)
+		    {
+		      edge_info->lhs = op0;
+		      edge_info->rhs = op1;
+		    }
+		}
+	    }
+
+	  /* ??? TRUTH_NOT_EXPR can create an equivalence too.  */
+	}
+    }
+}
+
+/* Propagate information from BB to its outgoing edges.
+
+   This can include equivalency information implied by control statements
+   at the end of BB and const/copy propagation into PHIs in BB's
+   successor blocks.  */
 
 static void
-cprop_into_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
-		 basic_block bb)
+propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			     basic_block bb)
 {
+  
+  record_edge_info (bb);
   cprop_into_successor_phis (bb, nonzero_vars);
 }
 
@@ -3037,10 +3277,13 @@ extract_range_from_cond (tree cond, tree *hi_p, tree *lo_p, int *inverted_p)
 static void
 record_range (tree cond, basic_block bb)
 {
-  /* We explicitly ignore NE_EXPRs.  They rarely allow for meaningful
-     range optimizations and significantly complicate the implementation.  */
-  if (COMPARISON_CLASS_P (cond)
-      && TREE_CODE (cond) != NE_EXPR
+  enum tree_code code = TREE_CODE (cond);
+
+  /* We explicitly ignore NE_EXPRs and all the unordered comparisons.
+     They rarely allow for meaningful range optimizations and significantly
+     complicate the implementation.  */
+  if ((code == LT_EXPR || code == LE_EXPR || code == GT_EXPR
+       || code == GE_EXPR || code == EQ_EXPR)
       && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond, 1))) == INTEGER_TYPE)
     {
       struct vrp_hash_elt *vrp_hash_elt;
@@ -3076,130 +3319,6 @@ record_range (tree cond, basic_block bb)
     }
 }
 
-/* Given a conditional statement IF_STMT, return the assignment 'X = Y'
-   known to be true depending on which arm of IF_STMT is taken.
-
-   Not all conditional statements will result in a useful assignment.
-   Return NULL_TREE in that case.
-
-   Also enter into the available expression table statements of
-   the form:
-
-     TRUE ARM		FALSE ARM
-     1 = cond		1 = cond'
-     0 = cond'		0 = cond
-
-   This allows us to lookup the condition in a dominated block and
-   get back a constant indicating if the condition is true.  */
-
-static struct eq_expr_value
-get_eq_expr_value (tree if_stmt,
-		   int true_arm,
-		   basic_block bb)
-{
-  tree cond;
-  struct eq_expr_value retval;
-
-  cond = COND_EXPR_COND (if_stmt);
-  retval.src = NULL;
-  retval.dst = NULL;
-
-  /* If the conditional is a single variable 'X', return 'X = 1' for
-     the true arm and 'X = 0' on the false arm.  */
-  if (TREE_CODE (cond) == SSA_NAME)
-    {
-      retval.dst = cond;
-      retval.src = constant_boolean_node (true_arm, TREE_TYPE (cond));
-      return retval;
-    }
-
-  /* If we have a comparison expression, then record its result into
-     the available expression table.  */
-  if (COMPARISON_CLASS_P (cond))
-    {
-      tree op0 = TREE_OPERAND (cond, 0);
-      tree op1 = TREE_OPERAND (cond, 1);
-
-      /* Special case comparing booleans against a constant as we know
-	 the value of OP0 on both arms of the branch.  i.e., we can record
-	 an equivalence for OP0 rather than COND.  */
-      if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
-	  && TREE_CODE (op0) == SSA_NAME
-	  && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
-	  && is_gimple_min_invariant (op1))
-	{
-	  if ((TREE_CODE (cond) == EQ_EXPR && true_arm)
-	      || (TREE_CODE (cond) == NE_EXPR && ! true_arm))
-	    {
-	      retval.src = op1;
-	    }
-	  else
-	    {
-	      if (integer_zerop (op1))
-		retval.src = boolean_true_node;
-	      else
-		retval.src = boolean_false_node;
-	    }
-	  retval.dst = op0;
-	  return retval;
-	}
-
-      if (TREE_CODE (op0) == SSA_NAME
-	  && (is_gimple_min_invariant (op1) || TREE_CODE (op1) == SSA_NAME))
-	{
-	  tree inverted = invert_truthvalue (cond);
-
-	  /* When we find an available expression in the hash table, we replace
-	     the expression with the LHS of the statement in the hash table.
-
-	     So, we want to build statements such as "1 = <condition>" on the
-	     true arm and "0 = <condition>" on the false arm.  That way if we
-	     find the expression in the table, we will replace it with its
-	     known constant value.  Also insert inversions of the result and
-	     condition into the hash table.  */
-	  if (true_arm)
-	    {
-	      record_cond (cond, boolean_true_node);
-	      record_dominating_conditions (cond);
-	      record_cond (inverted, boolean_false_node);
-
-	      if (TREE_CONSTANT (op1))
-		record_range (cond, bb);
-
-		/* If the conditional is of the form 'X == Y', return 'X = Y'
-		   for the true arm.  */
-	      if (TREE_CODE (cond) == EQ_EXPR)
-		{
-		  retval.dst = op0;
-		  retval.src = op1;
-		  return retval;
-		}
-	    }
-	  else
-	    {
-
-	      record_cond (inverted, boolean_true_node);
-	      record_dominating_conditions (inverted);
-	      record_cond (cond, boolean_false_node);
-
-	      if (TREE_CONSTANT (op1))
-		record_range (inverted, bb);
-
-		/* If the conditional is of the form 'X != Y', return 'X = Y'
-		   for the false arm.  */
-	      if (TREE_CODE (cond) == NE_EXPR)
-		{
-		  retval.dst = op0;
-		  retval.src = op1;
-		  return retval;
-		}
-	    }
-	}
-    }
-
-  return retval;
-}
-
 /* Hashing and equality functions for VRP_DATA.
 
    Since this hash table is addressed by SSA_NAMEs, we can hash on