--- gcc/cselib.h.jj	2014-01-03 11:40:57.000000000 +0100
+++ gcc/cselib.h	2014-03-03 19:23:48.633335911 +0100
@@ -95,6 +95,7 @@ extern unsigned int cselib_get_next_uid
 extern void cselib_preserve_value (cselib_val *);
 extern bool cselib_preserved_value_p (cselib_val *);
 extern void cselib_preserve_only_values (void);
+extern void cselib_remove_useless_values (vec<rtx>);
 extern void cselib_preserve_cfa_base_value (cselib_val *, unsigned int);
 extern void cselib_add_permanent_equiv (cselib_val *, rtx, rtx);
 extern bool cselib_have_permanent_equivalences (void);
--- gcc/var-tracking.c.jj	2014-03-03 18:28:18.000000000 +0100
+++ gcc/var-tracking.c	2014-03-03 19:27:07.518208397 +0100
@@ -10149,6 +10149,8 @@ vt_initialize (void)
 	}
     }
 
+  if (MAY_HAVE_DEBUG_INSNS)
+    cselib_remove_useless_values (preserved_values);
   hard_frame_pointer_adjustment = -1;
   VTI (ENTRY_BLOCK_PTR_FOR_FN (cfun))->flooded = true;
   cfa_base_rtx = NULL_RTX;
--- gcc/cselib.c.jj	2014-03-03 18:28:18.000000000 +0100
+++ gcc/cselib.c	2014-03-03 19:28:19.832782951 +0100
@@ -200,6 +200,7 @@ static unsigned int cselib_nregs;
    values.  */
 static int n_useless_values;
 static int n_useless_debug_values;
+static int n_dropped_useless_values;
 
 /* Count values whose locs have been taken exclusively from debug
    insns for the entire life of the value.  */
@@ -546,7 +547,11 @@ cselib_reset_table (unsigned int num)
     }
 
   if (cselib_preserve_constants)
-    cselib_hash_table.traverse <void *, preserve_constants_and_equivs> (NULL);
+    {
+      n_dropped_useless_values += n_useless_values;
+      cselib_hash_table.traverse <void *,
+				  preserve_constants_and_equivs> (NULL);
+    }
   else
     {
       cselib_hash_table.empty ();
@@ -681,14 +686,6 @@ remove_useless_values (void)
 {
   cselib_val **p, *v;
 
-  if (n_useless_values <= MAX_USELESS_VALUES
-      /* remove_useless_values is linear in the hash table size.  Avoid
-         quadratic behavior for very large hashtables with very few
-	 useless elements.  */
-      || ((unsigned int)n_useless_values
-	  <= (cselib_hash_table.elements () - n_debug_values) / 4))
-    return;
-
   /* First pass: eliminate locations that reference the value.  That in
      turn can make more values useless.  */
   do
@@ -712,6 +709,7 @@ remove_useless_values (void)
   n_useless_values += n_useless_debug_values;
   n_debug_values -= n_useless_debug_values;
   n_useless_debug_values = 0;
+  n_dropped_useless_values = 0;
 
   cselib_hash_table.traverse <void *, discard_useless_values> (NULL);
 
@@ -763,11 +761,43 @@ cselib_preserve_only_values (void)
 
   cselib_invalidate_mem (callmem);
 
-  remove_useless_values ();
+  if ((n_dropped_useless_values + n_useless_values) > MAX_USELESS_VALUES
+      /* Traversal with discard_useless_locs is linear in the hash table
+	 size.  Avoid quadratic behavior for very large hashtables with
+	 very few useless elements.  */
+      && ((unsigned int) (n_dropped_useless_values + n_useless_values)
+	  > (cselib_hash_table.elements () - n_debug_values) / 4))
+    {
+      /* Eliminate locations that reference the value.  That in
+	 turn can make more values useless.  */
+      do
+	{
+	  values_became_useless = 0;
+	  cselib_hash_table.traverse <void *, discard_useless_locs> (NULL);
+	}
+      while (values_became_useless);
+      n_dropped_useless_values = 0;
+    }
 
   gcc_assert (first_containing_mem == &dummy_val);
 }
 
+/* Clean out useless values (i.e. those which no longer have locations
+   associated with them) from both hash tables.  */
+
+void
+cselib_remove_useless_values (vec<rtx> values)
+{
+  unsigned int i;
+  rtx val;
+
+  if (n_dropped_useless_values)
+    remove_useless_values ();
+  cselib_preserved_hash_table.traverse <void *, discard_useless_locs> (NULL);
+  FOR_EACH_VEC_ELT (values, i, val)
+    discard_useless_locs (&CSELIB_VAL_PTR (val), NULL);
+}
+
 /* Arrange for a value to be marked as based on stack pointer
    for find_base_term purposes.  */
 
@@ -2720,7 +2750,13 @@ cselib_process_insn (rtx insn)
 
   cselib_current_insn = NULL_RTX;
 
-  remove_useless_values ();
+  if (n_useless_values > MAX_USELESS_VALUES
+      /* remove_useless_values is linear in the hash table size.  Avoid
+	 quadratic behavior for very large hashtables with very few
+	 useless elements.  */
+      && ((unsigned int)n_useless_values
+	  > (cselib_hash_table.elements () - n_debug_values) / 4))
+    remove_useless_values ();
 }
 
 /* Initialize cselib for one pass.  The caller must also call
@@ -2790,6 +2826,7 @@ cselib_finish (void)
   n_useless_values = 0;
   n_useless_debug_values = 0;
   n_debug_values = 0;
+  n_dropped_useless_values = 0;
   next_uid = 0;
 }
 
