Index: gcc/bitmap.c
===================================================================
--- gcc/bitmap.c	(revision 192023)
+++ gcc/bitmap.c	(working copy)
@@ -539,6 +539,15 @@
       to_ptr = to_elt;
     }
 }
+
+void
+bitmap_swap (bitmap a, bitmap b)
+{
+  bitmap_head tmp = *a;
+  *a = *b;
+  *b = tmp;
+}
+
 
 /* Find a bitmap element that would hold a bitmap's bit.
    Update the `current' field even if we can't find an element that
Index: gcc/bitmap.h
===================================================================
--- gcc/bitmap.h	(revision 192023)
+++ gcc/bitmap.h	(working copy)
@@ -200,6 +200,9 @@
 /* Copy a bitmap to another bitmap.  */
 extern void bitmap_copy (bitmap, const_bitmap);
 
+/* Swap 2 bitmaps.  */
+extern void bitmap_swap (bitmap, bitmap);
+
 /* True if two bitmaps are identical.  */
 extern bool bitmap_equal_p (const_bitmap, const_bitmap);
 
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c	(revision 192023)
+++ gcc/tree-ssa-pre.c	(working copy)
@@ -715,30 +715,183 @@
   unsigned int i, j;
   bitmap_iterator bi, bj;
   VEC(pre_expr, heap) *result;
+  bitmap todo = BITMAP_ALLOC (NULL);
+  bitmap values_done = BITMAP_ALLOC (NULL);
+  bitmap values_new = BITMAP_ALLOC (NULL);
+  bitmap_head *waiting = NULL;
+  unsigned int waiting_size = get_max_value_id () + 1;
+  int *nr_waiting = NULL;
+  unsigned int nr_waiting_size = next_expression_id;
 
   /* Pre-allocate roughly enough space for the array.  */
   result = VEC_alloc (pre_expr, heap, bitmap_count_bits (&set->values));
 
+  /* Handle expressions without dependencies, put expressions with dependencies
+     in todo.  */
+  EXECUTE_IF_SET_IN_BITMAP (&set->expressions, 0, i, bi)
+    {
+      pre_expr expr = expression_for_id (i);
+      switch (expr->kind)
+	{
+	case NAME:
+	case CONSTANT:
+	  break;
+
+	default:
+	  bitmap_set_bit (todo, i);
+	  continue;
+	}
+
+      VEC_safe_push (pre_expr, heap, result, expr);
+      bitmap_set_bit (values_done, get_expr_value_id (expr));
+    }
+
+  /* Handle expressions with dependencies.  Put expressions with unready
+     dependencies in waiting.  Do this in value-id order, so that if the
+     value-id order is already a topological order, we won't use the waiting
+     arrays.  */
   FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
     {
-      /* The number of expressions having a given value is usually
-	 relatively small.  Thus, rather than making a vector of all
-	 the expressions and sorting it by value-id, we walk the values
-	 and check in the reverse mapping that tells us what expressions
-	 have a given value, to filter those in our set.  As a result,
-	 the expressions are inserted in value-id order, which means
-	 topological order.
-
-	 If this is somehow a significant lose for some cases, we can
-	 choose which set to walk based on the set size.  */
       bitmap exprset = VEC_index (bitmap, value_expressions, i);
-      EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bj)
+      EXECUTE_IF_AND_IN_BITMAP (exprset, todo, 0, j, bj)
 	{
-	  if (bitmap_bit_p (&set->expressions, j))
-	    VEC_safe_push (pre_expr, heap, result, expression_for_id (j));
-        }
+	  pre_expr expr = expression_for_id (j);
+	  bool wait = false;
+	  switch (expr->kind)
+	    {
+	    case NARY:
+	      {
+		vn_nary_op_t nary = PRE_EXPR_NARY (expr);
+		unsigned int k;
+		for (k = 0; k < nary->length; k++)
+		  {
+		    tree op = nary->op[k];
+		    if (TREE_CODE (op) != SSA_NAME)
+		      continue;
+		    unsigned int v = VN_INFO (op)->value_id;
+		    if (!bitmap_bit_p (values_done, v)
+			&& bitmap_bit_p (&set->values, v))
+		      {
+			if (waiting == NULL)
+			  {
+			    waiting = XCNEWVEC (bitmap_head, waiting_size);
+			    nr_waiting = XCNEWVEC (int, nr_waiting_size);
+			  }
+			if (waiting[v].obstack == NULL)
+			  bitmap_initialize (&waiting[v],
+					     &bitmap_default_obstack);
+			if (!bitmap_bit_p (&waiting[v], j))
+			  {
+			    bitmap_set_bit (&waiting[v], j);
+			    nr_waiting[j]++;
+			  }
+			wait = true;
+		      }
+		  }
+	      }
+	      break;
+
+	    case REFERENCE:
+	      {
+		vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
+		vn_reference_op_t vro;
+
+		unsigned int k;
+		FOR_EACH_VEC_ELT (vn_reference_op_s, ref->operands, k, vro)
+		  {
+		    tree ops[3] = { vro->op0, vro->op1, vro->op2};
+		    unsigned int l;
+		    for (l = 0; l < 3; l++)
+		      {
+			tree op = ops[l];
+			if (op == NULL_TREE
+			    || TREE_CODE (op) != SSA_NAME)
+			  continue;
+			unsigned int v = VN_INFO (op)->value_id;
+			if (!bitmap_bit_p (values_done, v)
+			    && bitmap_bit_p (&set->values, v))
+			  {
+			    if (waiting == NULL)
+			      {
+				waiting = XCNEWVEC (bitmap_head, waiting_size);
+				nr_waiting = XCNEWVEC (int, nr_waiting_size);
+			      }
+			    if (waiting[v].obstack == NULL)
+			      bitmap_initialize (&waiting[v],
+						 &bitmap_default_obstack);
+			    if (!bitmap_bit_p (&waiting[v], j))
+			      {
+				bitmap_set_bit (&waiting[v], j);
+				nr_waiting[j]++;
+			      }
+			    wait = true;
+			  }
+		      }
+		  }
+	      }
+	      break;
+
+	    default:
+	      gcc_unreachable ();
+	    }
+
+	  /* The dependencies are not ready, so wait.  */
+	  if (wait)
+	    continue;
+
+	  /* The dependencies are ready so add the expr.  */
+	  VEC_safe_push (pre_expr, heap, result, expr);
+	  unsigned int value_id = get_expr_value_id (expr);
+	  if (!bitmap_bit_p (values_done, value_id))
+	    {
+	      bitmap_set_bit (values_new, value_id);
+	      bitmap_set_bit (values_done, value_id);
+	    }
+	}
     }
 
+  /* Handle newly produced values, decrease wait count for appropriate
+     expressions and handle ready expressions.  Iterate until done.  */
+  while (!bitmap_empty_p (values_new)
+	 && waiting != NULL)
+    {
+      bitmap_clear (todo);
+      bitmap_swap (todo, values_new);
+
+      EXECUTE_IF_SET_IN_BITMAP (todo, 0, i, bi)
+	{
+	  if (waiting[i].obstack == NULL)
+	    continue;
+
+	  EXECUTE_IF_SET_IN_BITMAP (&waiting[i], 0, j, bj)
+	    {
+	      nr_waiting[j]--;
+	      gcc_assert (nr_waiting[j] >= 0);
+	      if (nr_waiting[j] == 0)
+		{
+		  pre_expr expr = expression_for_id (j);
+
+		  VEC_safe_push (pre_expr, heap, result, expr);
+		  unsigned int value_id = get_expr_value_id (expr);
+		  if (!bitmap_bit_p (values_done, value_id))
+		    {
+		      bitmap_set_bit (values_done, value_id);
+		      bitmap_set_bit (values_new, value_id);
+		    }
+		}
+	    }
+	  bitmap_clear (&waiting[i]);
+	}
+    }
+
+  gcc_assert (bitmap_count_bits (&set->expressions)
+	      == VEC_length (pre_expr, result));
+  BITMAP_FREE (todo);
+  BITMAP_FREE (values_done);
+  BITMAP_FREE (values_new);
+  XDELETE (waiting);
+  XDELETE (nr_waiting);
+
   return result;
 }
 
