Patchwork Fix PR54489 - FRE needing AVAIL_OUT

login
register
mail settings
Submitter Richard Guenther
Date Sept. 12, 2012, 2:02 p.m.
Message ID <alpine.LNX.2.00.1209121556390.28649@zhemvz.fhfr.qr>
Download mbox | patch
Permalink /patch/183378/
State New
Headers show

Comments

Richard Guenther - Sept. 12, 2012, 2:02 p.m.
This removes the need for FRE to compute AVAIL_OUT which can
consume an unreasonable amount of memory for testcases like

int foo (int a)
{
  int b = 0;
#define X if (a) b = b + 1;
#define XX X X X X X X X X X X
#define XXX XX XX XX XX XX XX XX XX XX XX
#define XXXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX
#define XXXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
#define XXXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX
#define XXXXXXX XXXXXX XXXXXX XXXXXX XXXXXX XXXXXX XXXXXX XXXXXX XXXXXX 
XXXXXX
XXXXXX
  XXXXXX
  return b;
}

instead of computing AVAIL_OUT up-front for all basic-block just
to find the SSA name whose definition dominates the current
elimination point this re-organizes elimination to perform a domwalk,
updating a SCCVN value-id (thus, SSA name) -> leader (dominating SSA
name) mapping.

It also simplifies PRE by removing that in_fre global flag and
not sharing a common execute function.  FRE and PRE now only share
elimination (and value-numbering).

It comes to my mind that if we manage to get rid of the AVAIL_OUT
use from clean () and dependent_clean () we can delay PRE insertion
(well, producing and inserting actual GIMPLE stmts) to elimination
time as well, removing its need for AVAIL_OUT.  But that's surely
for a followup (and I bet sth else than PRE blows up at -O2 as well).

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

2012-09-12  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/54489
	* tree-ssa-pre.c: Include domwalk.h.
	(in_fre): Remove.
	(sccvn_valnum_from_value_id): New function.
	(debug_bitmap_sets_for): Simplify.
	(get_representative_for): Properly initialize the SCCVN valnum.
	(create_expression_by_pieces): Likewise.
	(insert_into_preds_of_block): Likewise.
	(can_PRE_operation): Remove.
	(make_values_for_phi): Simplify.
	(compute_avail): Likewise.
	(do_SCCVN_insertion): Remove.
	(eliminate_avail, eliminate_push_avail, eliminate_insert):
	New functions.
	(eliminate): Split and perform a domwalk.
	(eliminate_bb): Former eliminate part that is now dom-enter.
	(eliminate_leave_block): New function.
	(fini_eliminate): Likewise.
	(init_pre): Simplify.
	(fini_pre): Likewise.
	(execute_pre): Fold into do_pre and do_fre.
	(do_pre): Consume execute_pre.
	(do_fre): Likewise.
	* Makefile.in (tree-ssa-pre.o): Add domwalk.h dependency.
Steven Bosscher - Sept. 12, 2012, 2:52 p.m.
On Wed, Sep 12, 2012 at 4:02 PM, Richard Guenther wrote:
> for a followup (and I bet sth else than PRE blows up at -O2 as well).

Actually, the only thing that really blows up is that enemy of scalability, VRP.

With -O2 -fno-tree-{pre,fre,vrp}, the slowest part of the compiler on
this test case are dominance computation, dominator-based
optimization, and tree CFG cleanup, but they all scale linearly with
the number of X'es in the test case :-)

Ciao!
Steven
Steven Bosscher - Sept. 13, 2012, 9:08 p.m.
On Wed, Sep 12, 2012 at 4:52 PM, Steven Bosscher wrote:
> On Wed, Sep 12, 2012 at 4:02 PM, Richard Guenther wrote:
>> for a followup (and I bet sth else than PRE blows up at -O2 as well).
>
> Actually, the only thing that really blows up is that enemy of scalability, VRP.

FWIW, this appears to be due to the well-known problem with the equiv
set, but also due to the liveness computations that tree-vrp performs,
since your commit in r139263.

Any reason why you didn't just re-use the tree-ssa-live machinery?

And any reason why you don't let a DEF kill a live SSA name? AFAICT
you're exposing all SSA names up without ever killing a USE :-)

Ciao!
Steven

Patch

Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c	(revision 191215)
+++ gcc/tree-ssa-pre.c	(working copy)
@@ -43,6 +43,7 @@  along with GCC; see the file COPYING3.
 #include "tree-scalar-evolution.h"
 #include "params.h"
 #include "dbgcnt.h"
+#include "domwalk.h"
 
 /* TODO:
 
@@ -351,8 +352,6 @@  get_or_alloc_expr_for_name (tree name)
   return result;
 }
 
-static bool in_fre = false;
-
 /* An unordered bitmap set.  One bitmap tracks values, the other,
    expressions.  */
 typedef struct bitmap_set
@@ -637,6 +636,25 @@  get_expr_value_id (pre_expr expr)
     }
 }
 
+/* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL.  */
+
+static tree
+sccvn_valnum_from_value_id (unsigned int val)
+{
+  bitmap_iterator bi;
+  unsigned int i;
+  bitmap exprset = VEC_index (bitmap, value_expressions, val);
+  EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
+    {
+      pre_expr vexpr = expression_for_id (i);
+      if (vexpr->kind == NAME)
+	return VN_INFO (PRE_EXPR_NAME (vexpr))->valnum;
+      else if (vexpr->kind == CONSTANT)
+	return PRE_EXPR_CONSTANT (vexpr);
+    }
+  return NULL_TREE;
+}
+
 /* Remove an expression EXPR from a bitmapped set.  */
 
 static void
@@ -1022,16 +1040,13 @@  DEBUG_FUNCTION void
 debug_bitmap_sets_for (basic_block bb)
 {
   print_bitmap_set (stderr, AVAIL_OUT (bb), "avail_out", bb->index);
-  if (!in_fre)
-    {
-      print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index);
-      print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index);
-      print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index);
-      print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index);
-      if (do_partial_partial)
-	print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index);
-      print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index);
-    }
+  print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index);
+  print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index);
+  print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index);
+  print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index);
+  if (do_partial_partial)
+    print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index);
+  print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index);
 }
 
 /* Print out the expressions that have VAL to OUTFILE.  */
@@ -1402,11 +1417,9 @@  get_representative_for (const pre_expr e
      that we will return.  */
   name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
   VN_INFO_GET (name)->value_id = value_id;
-  if (e->kind == CONSTANT)
-    VN_INFO (name)->valnum = PRE_EXPR_CONSTANT (e);
-  else
+  VN_INFO (name)->valnum = sccvn_valnum_from_value_id (value_id);
+  if (VN_INFO (name)->valnum == NULL_TREE)
     VN_INFO (name)->valnum = name;
-
   add_to_value (value_id, get_or_alloc_expr_for_name (name));
   if (dump_file)
     {
@@ -2563,23 +2576,6 @@  compute_antic (void)
   sbitmap_free (changed_blocks);
 }
 
-/* Return true if OP is a tree which we can perform PRE on.
-   This may not match the operations we can value number, but in
-   a perfect world would.  */
-
-static bool
-can_PRE_operation (tree op)
-{
-  return UNARY_CLASS_P (op)
-    || BINARY_CLASS_P (op)
-    || COMPARISON_CLASS_P (op)
-    || TREE_CODE (op) == MEM_REF 
-    || TREE_CODE (op) == COMPONENT_REF
-    || TREE_CODE (op) == VIEW_CONVERT_EXPR
-    || TREE_CODE (op) == CALL_EXPR
-    || TREE_CODE (op) == ARRAY_REF;
-}
-
 
 /* Inserted expressions are placed onto this worklist, which is used
    for performing quick dead code elimination of insertions we made
@@ -3072,8 +3068,7 @@  create_expression_by_pieces (basic_block
 	      VN_INFO (forcedname)->value_id = get_next_value_id ();
 	      nameexpr = get_or_alloc_expr_for_name (forcedname);
 	      add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
-	      if (!in_fre)
-		bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
+	      bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
 	      bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
 	    }
 	}
@@ -3097,9 +3092,12 @@  create_expression_by_pieces (basic_block
      we are creating the expression by pieces, and this particular piece of
      the expression may have been represented.  There is no harm in replacing
      here.  */
-  VN_INFO_GET (name)->valnum = name;
   value_id = get_expr_value_id (expr);
-  VN_INFO (name)->value_id = value_id;
+  VN_INFO_GET (name)->value_id = value_id;
+  VN_INFO (name)->valnum = sccvn_valnum_from_value_id (value_id);
+  if (VN_INFO (name)->valnum == NULL_TREE)
+    VN_INFO (name)->valnum = name;
+  gcc_assert (VN_INFO (name)->valnum != NULL_TREE);
   nameexpr = get_or_alloc_expr_for_name (name);
   add_to_value (value_id, nameexpr);
   if (NEW_SETS (block))
@@ -3339,9 +3337,11 @@  insert_into_preds_of_block (basic_block
   phi = create_phi_node (temp, block);
 
   gimple_set_plf (phi, NECESSARY, false);
-  VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
-  VN_INFO (gimple_phi_result (phi))->value_id = val;
-  bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (gimple_phi_result (phi)));
+  VN_INFO_GET (temp)->value_id = val;
+  VN_INFO (temp)->valnum = sccvn_valnum_from_value_id (val);
+  if (VN_INFO (temp)->valnum == NULL_TREE)
+    VN_INFO (temp)->valnum = temp;
+  bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
   FOR_EACH_EDGE (pred, ei, block->preds)
     {
       pre_expr ae = VEC_index (pre_expr, avail, pred->dest_idx);
@@ -3353,7 +3353,7 @@  insert_into_preds_of_block (basic_block
 	add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION);
     }
 
-  newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
+  newphi = get_or_alloc_expr_for_name (temp);
   add_to_value (val, newphi);
 
   /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
@@ -3782,8 +3782,6 @@  add_to_exp_gen (basic_block block, tree
 {
   pre_expr result;
 
-  gcc_checking_assert (!in_fre);
-
   if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op))
     return;
 
@@ -3797,6 +3795,7 @@  static void
 make_values_for_phi (gimple phi, basic_block block)
 {
   tree result = gimple_phi_result (phi);
+  unsigned i;
 
   /* We have no need for virtual phis, as they don't represent
      actual computations.  */
@@ -3806,18 +3805,14 @@  make_values_for_phi (gimple phi, basic_b
   pre_expr e = get_or_alloc_expr_for_name (result);
   add_to_value (get_expr_value_id (e), e);
   bitmap_value_insert_into_set (AVAIL_OUT (block), e);
-  if (!in_fre)
+  bitmap_insert_into_set (PHI_GEN (block), e);
+  for (i = 0; i < gimple_phi_num_args (phi); ++i)
     {
-      unsigned i;
-      bitmap_insert_into_set (PHI_GEN (block), e);
-      for (i = 0; i < gimple_phi_num_args (phi); ++i)
+      tree arg = gimple_phi_arg_def (phi, i);
+      if (TREE_CODE (arg) == SSA_NAME)
 	{
-	  tree arg = gimple_phi_arg_def (phi, i);
-	  if (TREE_CODE (arg) == SSA_NAME)
-	    {
-	      e = get_or_alloc_expr_for_name (arg);
-	      add_to_value (get_expr_value_id (e), e);
-	    }
+	  e = get_or_alloc_expr_for_name (arg);
+	  add_to_value (get_expr_value_id (e), e);
 	}
     }
 }
@@ -3855,8 +3850,7 @@  compute_avail (void)
 
       e = get_or_alloc_expr_for_name (name);
       add_to_value (get_expr_value_id (e), e);
-      if (!in_fre)
-	bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
+      bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
       bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
     }
 
@@ -3924,15 +3918,10 @@  compute_avail (void)
 	      pre_expr e = get_or_alloc_expr_for_name (op);
 
 	      add_to_value (get_expr_value_id (e), e);
-	      if (!in_fre)
-		bitmap_insert_into_set (TMP_GEN (block), e);
+	      bitmap_insert_into_set (TMP_GEN (block), e);
 	      bitmap_value_insert_into_set (AVAIL_OUT (block), e);
 	    }
 
-	  /* That's all we need to do when doing FRE.  */
-	  if (in_fre)
-	    continue;
-
 	  if (gimple_has_side_effects (stmt) || stmt_could_throw_p (stmt))
 	    continue;
 
@@ -4123,407 +4112,470 @@  compute_avail (void)
   free (worklist);
 }
 
-/* Insert the expression for SSA_VN that SCCVN thought would be simpler
-   than the available expressions for it.  The insertion point is
-   right before the first use in STMT.  Returns the SSA_NAME that should
-   be used for replacement.  */
+
+/* Local state for the eliminate domwalk.  */
+static VEC (gimple, heap) *el_to_remove;
+static VEC (gimple, heap) *el_to_update;
+static unsigned int el_todo;
+static VEC (tree, heap) *el_avail;
+static VEC (tree, heap) *el_avail_stack;
+
+/* Return a leader for OP that is available at the current point of the
+   eliminate domwalk.  */
 
 static tree
-do_SCCVN_insertion (gimple stmt, tree ssa_vn)
+eliminate_avail (tree op)
 {
-  basic_block bb = gimple_bb (stmt);
-  gimple_stmt_iterator gsi;
-  gimple_seq stmts = NULL;
-  tree expr;
-  pre_expr e;
+  tree valnum = VN_INFO (op)->valnum;
+  if (TREE_CODE (valnum) == SSA_NAME)
+    {
+      if (SSA_NAME_IS_DEFAULT_DEF (valnum))
+	return valnum;
+      if (VEC_length (tree, el_avail) > SSA_NAME_VERSION (valnum))
+	return VEC_index (tree, el_avail, SSA_NAME_VERSION (valnum));
+    }
+  else if (is_gimple_min_invariant (valnum))
+    return valnum;
+  return NULL_TREE;
+}
+
+/* At the current point of the eliminate domwalk make OP available.  */
 
-  /* First create a value expression from the expression we want
-     to insert and associate it with the value handle for SSA_VN.  */
-  e = get_or_alloc_expr_for (vn_get_expr_for (ssa_vn));
-  if (e == NULL)
+static void
+eliminate_push_avail (tree op)
+{
+  tree valnum = VN_INFO (op)->valnum;
+  if (TREE_CODE (valnum) == SSA_NAME)
+    {
+      if (VEC_length (tree, el_avail) <= SSA_NAME_VERSION (valnum))
+	VEC_safe_grow_cleared (tree, heap,
+			       el_avail, SSA_NAME_VERSION (valnum) + 1);
+      VEC_replace (tree, el_avail, SSA_NAME_VERSION (valnum), op);
+      VEC_safe_push (tree, heap, el_avail_stack, op);
+    }
+}
+
+/* Insert the expression recorded by SCCVN for VAL at *GSI.  Returns
+   the leader for the expression if insertion was successful.  */
+
+static tree
+eliminate_insert (gimple_stmt_iterator *gsi, tree val)
+{
+  tree expr = vn_get_expr_for (val);
+  if (!CONVERT_EXPR_P (expr)
+      && TREE_CODE (expr) != VIEW_CONVERT_EXPR)
     return NULL_TREE;
 
-  /* Then use create_expression_by_pieces to generate a valid
-     expression to insert at this point of the IL stream.  */
-  expr = create_expression_by_pieces (bb, e, &stmts, stmt, NULL);
-  if (expr == NULL_TREE)
+  tree op = TREE_OPERAND (expr, 0);
+  tree leader = eliminate_avail (op);
+  if (!leader)
     return NULL_TREE;
-  gsi = gsi_for_stmt (stmt);
-  gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
 
-  return expr;
+  tree res = make_temp_ssa_name (TREE_TYPE (val), NULL, "pretmp");
+  gimple tem = gimple_build_assign (res,
+				    build1 (TREE_CODE (expr),
+					    TREE_TYPE(expr), leader));
+  gsi_insert_before (gsi, tem, GSI_SAME_STMT);
+  VN_INFO_GET (res)->valnum = val;
+
+  gimple_set_plf (SSA_NAME_DEF_STMT (leader), NECESSARY, true);
+
+  pre_stats.insertions++;
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Inserted ");
+      print_gimple_stmt (dump_file, tem, 0, 0);
+    }
+
+  return res;
 }
 
-/* Eliminate fully redundant computations.  */
+/* Perform elimination for the basic-block B during the domwalk.  */
 
-static unsigned int
-eliminate (void)
+static void
+eliminate_bb (dom_walk_data *, basic_block b)
 {
-  VEC (gimple, heap) *to_remove = NULL;
-  VEC (gimple, heap) *to_update = NULL;
-  basic_block b;
-  unsigned int todo = 0;
   gimple_stmt_iterator gsi;
   gimple stmt;
-  unsigned i;
 
-  FOR_EACH_BB (b)
+  /* Mark new bb.  */
+  VEC_safe_push (tree, heap, el_avail_stack, NULL_TREE);
+
+  for (gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
     {
-      for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
+      gimple stmt, phi = gsi_stmt (gsi);
+      tree sprime = NULL_TREE, res = PHI_RESULT (phi);
+      gimple_stmt_iterator gsi2;
+
+      /* We want to perform redundant PHI elimination.  Do so by
+	 replacing the PHI with a single copy if possible.
+	 Do not touch inserted, single-argument or virtual PHIs.  */
+      if (gimple_phi_num_args (phi) == 1
+	  || virtual_operand_p (res))
 	{
-	  tree lhs = NULL_TREE;
-	  tree rhs = NULL_TREE;
+	  gsi_next (&gsi);
+	  continue;
+	}
 
-	  stmt = gsi_stmt (gsi);
+      sprime = eliminate_avail (res);
+      if (!sprime
+	  || sprime == res)
+	{
+	  eliminate_push_avail (res);
+	  gsi_next (&gsi);
+	  continue;
+	}
+      else if (is_gimple_min_invariant (sprime))
+	{
+	  if (!useless_type_conversion_p (TREE_TYPE (res),
+					  TREE_TYPE (sprime)))
+	    sprime = fold_convert (TREE_TYPE (res), sprime);
+	}
 
-	  if (gimple_has_lhs (stmt))
-	    lhs = gimple_get_lhs (stmt);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Replaced redundant PHI node defining ");
+	  print_generic_expr (dump_file, res, 0);
+	  fprintf (dump_file, " with ");
+	  print_generic_expr (dump_file, sprime, 0);
+	  fprintf (dump_file, "\n");
+	}
+
+      remove_phi_node (&gsi, false);
+
+      if (inserted_exprs
+	  && !bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res))
+	  && TREE_CODE (sprime) == SSA_NAME)
+	gimple_set_plf (SSA_NAME_DEF_STMT (sprime), NECESSARY, true);
+
+      if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
+	sprime = fold_convert (TREE_TYPE (res), sprime);
+      stmt = gimple_build_assign (res, sprime);
+      SSA_NAME_DEF_STMT (res) = stmt;
+      gimple_set_plf (stmt, NECESSARY, gimple_plf (phi, NECESSARY));
+
+      gsi2 = gsi_after_labels (b);
+      gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
+      /* Queue the copy for eventual removal.  */
+      VEC_safe_push (gimple, heap, el_to_remove, stmt);
+      /* If we inserted this PHI node ourself, it's not an elimination.  */
+      if (inserted_exprs
+	  && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res)))
+	pre_stats.phis--;
+      else
+	pre_stats.eliminations++;
+    }
 
-	  if (gimple_assign_single_p (stmt))
-	    rhs = gimple_assign_rhs1 (stmt);
+  for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      tree lhs = NULL_TREE;
+      tree rhs = NULL_TREE;
 
-	  /* Lookup the RHS of the expression, see if we have an
-	     available computation for it.  If so, replace the RHS with
-	     the available computation.
-
-	     See PR43491.
-	     We don't replace global register variable when it is a the RHS of
-	     a single assign. We do replace local register variable since gcc
-	     does not guarantee local variable will be allocated in register.  */
-	  if (gimple_has_lhs (stmt)
-	      && TREE_CODE (lhs) == SSA_NAME
-	      && !gimple_assign_ssa_name_copy_p (stmt)
-	      && (!gimple_assign_single_p (stmt)
-		  || (!is_gimple_min_invariant (rhs)
-                      && (gimple_assign_rhs_code (stmt) != VAR_DECL
-                          || !is_global_var (rhs)
-                          || !DECL_HARD_REGISTER (rhs))))
-	      && !gimple_has_volatile_ops  (stmt)
-	      && !has_zero_uses (lhs))
-	    {
-	      tree sprime = NULL;
-	      pre_expr lhsexpr = get_or_alloc_expr_for_name (lhs);
-	      pre_expr sprimeexpr;
-	      gimple orig_stmt = stmt;
-
-	      sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
-					       get_expr_value_id (lhsexpr),
-					       NULL);
+      stmt = gsi_stmt (gsi);
 
-	      if (sprimeexpr)
-		{
-		  if (sprimeexpr->kind == CONSTANT)
-		    sprime = PRE_EXPR_CONSTANT (sprimeexpr);
-		  else if (sprimeexpr->kind == NAME)
-		    sprime = PRE_EXPR_NAME (sprimeexpr);
-		  else
-		    gcc_unreachable ();
-		}
+      if (gimple_has_lhs (stmt))
+	lhs = gimple_get_lhs (stmt);
 
-	      /* If there is no existing leader but SCCVN knows this
-		 value is constant, use that constant.  */
-	      if (!sprime && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
-		{
-		  sprime = VN_INFO (lhs)->valnum;
-		  if (!useless_type_conversion_p (TREE_TYPE (lhs),
-						  TREE_TYPE (sprime)))
-		    sprime = fold_convert (TREE_TYPE (lhs), sprime);
+      if (gimple_assign_single_p (stmt))
+	rhs = gimple_assign_rhs1 (stmt);
 
-		  if (dump_file && (dump_flags & TDF_DETAILS))
-		    {
-		      fprintf (dump_file, "Replaced ");
-		      print_gimple_expr (dump_file, stmt, 0, 0);
-		      fprintf (dump_file, " with ");
-		      print_generic_expr (dump_file, sprime, 0);
-		      fprintf (dump_file, " in ");
-		      print_gimple_stmt (dump_file, stmt, 0, 0);
-		    }
-		  pre_stats.eliminations++;
-		  propagate_tree_value_into_stmt (&gsi, sprime);
-		  stmt = gsi_stmt (gsi);
-		  update_stmt (stmt);
-
-		  /* If we removed EH side-effects from the statement, clean
-		     its EH information.  */
-		  if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
-		    {
-		      bitmap_set_bit (need_eh_cleanup,
-				      gimple_bb (stmt)->index);
-		      if (dump_file && (dump_flags & TDF_DETAILS))
-			fprintf (dump_file, "  Removed EH side-effects.\n");
-		    }
-		  continue;
-		}
+      /* Lookup the RHS of the expression, see if we have an
+	 available computation for it.  If so, replace the RHS with
+	 the available computation.
+
+	 See PR43491.
+	 We don't replace global register variable when it is a the RHS of
+	 a single assign. We do replace local register variable since gcc
+	 does not guarantee local variable will be allocated in register.  */
+      if (gimple_has_lhs (stmt)
+	  && TREE_CODE (lhs) == SSA_NAME
+	  && !gimple_assign_ssa_name_copy_p (stmt)
+	  && (!gimple_assign_single_p (stmt)
+	      || (!is_gimple_min_invariant (rhs)
+		  && (gimple_assign_rhs_code (stmt) != VAR_DECL
+		      || !is_global_var (rhs)
+		      || !DECL_HARD_REGISTER (rhs))))
+	  && !gimple_has_volatile_ops  (stmt))
+	{
+	  tree sprime;
+	  gimple orig_stmt = stmt;
 
+	  sprime = eliminate_avail (lhs);
+	  if (!sprime)
+	    {
 	      /* If there is no existing usable leader but SCCVN thinks
 		 it has an expression it wants to use as replacement,
 		 insert that.  */
-	      if (!sprime || sprime == lhs)
+	      tree val = VN_INFO (lhs)->valnum;
+	      if (val != VN_TOP
+		  && TREE_CODE (val) == SSA_NAME
+		  && VN_INFO (val)->needs_insertion
+		  && (sprime = eliminate_insert (&gsi, val)) != NULL_TREE)
+		eliminate_push_avail (sprime);
+	    }
+	  else if (is_gimple_min_invariant (sprime))
+	    {
+	      /* If there is no existing leader but SCCVN knows this
+		 value is constant, use that constant.  */
+	      if (!useless_type_conversion_p (TREE_TYPE (lhs),
+					      TREE_TYPE (sprime)))
+		sprime = fold_convert (TREE_TYPE (lhs), sprime);
+
+	      if (dump_file && (dump_flags & TDF_DETAILS))
 		{
-		  tree val = VN_INFO (lhs)->valnum;
-		  if (val != VN_TOP
-		      && TREE_CODE (val) == SSA_NAME
-		      && VN_INFO (val)->needs_insertion
-		      && can_PRE_operation (vn_get_expr_for (val)))
-		    sprime = do_SCCVN_insertion (stmt, val);
+		  fprintf (dump_file, "Replaced ");
+		  print_gimple_expr (dump_file, stmt, 0, 0);
+		  fprintf (dump_file, " with ");
+		  print_generic_expr (dump_file, sprime, 0);
+		  fprintf (dump_file, " in ");
+		  print_gimple_stmt (dump_file, stmt, 0, 0);
 		}
-	      if (sprime
-		  && sprime != lhs
-		  && (rhs == NULL_TREE
-		      || TREE_CODE (rhs) != SSA_NAME
-		      || may_propagate_copy (rhs, sprime)))
+	      pre_stats.eliminations++;
+	      propagate_tree_value_into_stmt (&gsi, sprime);
+	      stmt = gsi_stmt (gsi);
+	      update_stmt (stmt);
+
+	      /* If we removed EH side-effects from the statement, clean
+		 its EH information.  */
+	      if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
 		{
-		  bool can_make_abnormal_goto
-		    = is_gimple_call (stmt)
-		      && stmt_can_make_abnormal_goto (stmt);
-
-		  gcc_assert (sprime != rhs);
-
+		  bitmap_set_bit (need_eh_cleanup,
+				  gimple_bb (stmt)->index);
 		  if (dump_file && (dump_flags & TDF_DETAILS))
-		    {
-		      fprintf (dump_file, "Replaced ");
-		      print_gimple_expr (dump_file, stmt, 0, 0);
-		      fprintf (dump_file, " with ");
-		      print_generic_expr (dump_file, sprime, 0);
-		      fprintf (dump_file, " in ");
-		      print_gimple_stmt (dump_file, stmt, 0, 0);
-		    }
-
-		  if (TREE_CODE (sprime) == SSA_NAME)
-		    gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
-				    NECESSARY, true);
-		  /* We need to make sure the new and old types actually match,
-		     which may require adding a simple cast, which fold_convert
-		     will do for us.  */
-		  if ((!rhs || TREE_CODE (rhs) != SSA_NAME)
-		      && !useless_type_conversion_p (gimple_expr_type (stmt),
-						     TREE_TYPE (sprime)))
-		    sprime = fold_convert (gimple_expr_type (stmt), sprime);
-
-		  pre_stats.eliminations++;
-		  propagate_tree_value_into_stmt (&gsi, sprime);
-		  stmt = gsi_stmt (gsi);
-		  update_stmt (stmt);
-
-		  /* If we removed EH side-effects from the statement, clean
-		     its EH information.  */
-		  if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
-		    {
-		      bitmap_set_bit (need_eh_cleanup,
-				      gimple_bb (stmt)->index);
-		      if (dump_file && (dump_flags & TDF_DETAILS))
-			fprintf (dump_file, "  Removed EH side-effects.\n");
-		    }
-
-		  /* Likewise for AB side-effects.  */
-		  if (can_make_abnormal_goto
-		      && !stmt_can_make_abnormal_goto (stmt))
-		    {
-		      bitmap_set_bit (need_ab_cleanup,
-				      gimple_bb (stmt)->index);
-		      if (dump_file && (dump_flags & TDF_DETAILS))
-			fprintf (dump_file, "  Removed AB side-effects.\n");
-		    }
+		    fprintf (dump_file, "  Removed EH side-effects.\n");
 		}
+	      continue;
 	    }
-	  /* If the statement is a scalar store, see if the expression
-	     has the same value number as its rhs.  If so, the store is
-	     dead.  */
-	  else if (gimple_assign_single_p (stmt)
-		   && !gimple_has_volatile_ops (stmt)
-		   && !is_gimple_reg (gimple_assign_lhs (stmt))
-		   && (TREE_CODE (rhs) == SSA_NAME
-		       || is_gimple_min_invariant (rhs)))
+
+	  /* If there is no usable leader mark lhs as leader for its value.  */
+	  if (!sprime)
+	    eliminate_push_avail (lhs);
+
+	  if (sprime
+	      && sprime != lhs
+	      && (rhs == NULL_TREE
+		  || TREE_CODE (rhs) != SSA_NAME
+		  || may_propagate_copy (rhs, sprime)))
 	    {
-	      tree val;
-	      val = vn_reference_lookup (gimple_assign_lhs (stmt),
-					 gimple_vuse (stmt), VN_WALK, NULL);
-	      if (TREE_CODE (rhs) == SSA_NAME)
-		rhs = VN_INFO (rhs)->valnum;
-	      if (val
-		  && operand_equal_p (val, rhs, 0))
+	      bool can_make_abnormal_goto
+		  = is_gimple_call (stmt)
+		  && stmt_can_make_abnormal_goto (stmt);
+
+	      gcc_assert (sprime != rhs);
+
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "Replaced ");
+		  print_gimple_expr (dump_file, stmt, 0, 0);
+		  fprintf (dump_file, " with ");
+		  print_generic_expr (dump_file, sprime, 0);
+		  fprintf (dump_file, " in ");
+		  print_gimple_stmt (dump_file, stmt, 0, 0);
+		}
+
+	      if (TREE_CODE (sprime) == SSA_NAME)
+		gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
+				NECESSARY, true);
+	      /* We need to make sure the new and old types actually match,
+		 which may require adding a simple cast, which fold_convert
+		 will do for us.  */
+	      if ((!rhs || TREE_CODE (rhs) != SSA_NAME)
+		  && !useless_type_conversion_p (gimple_expr_type (stmt),
+						 TREE_TYPE (sprime)))
+		sprime = fold_convert (gimple_expr_type (stmt), sprime);
+
+	      pre_stats.eliminations++;
+	      propagate_tree_value_into_stmt (&gsi, sprime);
+	      stmt = gsi_stmt (gsi);
+	      update_stmt (stmt);
+
+	      /* If we removed EH side-effects from the statement, clean
+		 its EH information.  */
+	      if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
 		{
+		  bitmap_set_bit (need_eh_cleanup,
+				  gimple_bb (stmt)->index);
 		  if (dump_file && (dump_flags & TDF_DETAILS))
-		    {
-		      fprintf (dump_file, "Deleted redundant store ");
-		      print_gimple_stmt (dump_file, stmt, 0, 0);
-		    }
+		    fprintf (dump_file, "  Removed EH side-effects.\n");
+		}
 
-		  /* Queue stmt for removal.  */
-		  VEC_safe_push (gimple, heap, to_remove, stmt);
+	      /* Likewise for AB side-effects.  */
+	      if (can_make_abnormal_goto
+		  && !stmt_can_make_abnormal_goto (stmt))
+		{
+		  bitmap_set_bit (need_ab_cleanup,
+				  gimple_bb (stmt)->index);
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "  Removed AB side-effects.\n");
 		}
 	    }
-	  /* Visit COND_EXPRs and fold the comparison with the
-	     available value-numbers.  */
-	  else if (gimple_code (stmt) == GIMPLE_COND)
+	}
+      /* If the statement is a scalar store, see if the expression
+	 has the same value number as its rhs.  If so, the store is
+	 dead.  */
+      else if (gimple_assign_single_p (stmt)
+	       && !gimple_has_volatile_ops (stmt)
+	       && !is_gimple_reg (gimple_assign_lhs (stmt))
+	       && (TREE_CODE (rhs) == SSA_NAME
+		   || is_gimple_min_invariant (rhs)))
+	{
+	  tree val;
+	  val = vn_reference_lookup (gimple_assign_lhs (stmt),
+				     gimple_vuse (stmt), VN_WALK, NULL);
+	  if (TREE_CODE (rhs) == SSA_NAME)
+	    rhs = VN_INFO (rhs)->valnum;
+	  if (val
+	      && operand_equal_p (val, rhs, 0))
 	    {
-	      tree op0 = gimple_cond_lhs (stmt);
-	      tree op1 = gimple_cond_rhs (stmt);
-	      tree result;
-
-	      if (TREE_CODE (op0) == SSA_NAME)
-		op0 = VN_INFO (op0)->valnum;
-	      if (TREE_CODE (op1) == SSA_NAME)
-		op1 = VN_INFO (op1)->valnum;
-	      result = fold_binary (gimple_cond_code (stmt), boolean_type_node,
-				    op0, op1);
-	      if (result && TREE_CODE (result) == INTEGER_CST)
+	      if (dump_file && (dump_flags & TDF_DETAILS))
 		{
-		  if (integer_zerop (result))
-		    gimple_cond_make_false (stmt);
-		  else
-		    gimple_cond_make_true (stmt);
-		  update_stmt (stmt);
-		  todo = TODO_cleanup_cfg;
+		  fprintf (dump_file, "Deleted redundant store ");
+		  print_gimple_stmt (dump_file, stmt, 0, 0);
 		}
+
+	      /* Queue stmt for removal.  */
+	      VEC_safe_push (gimple, heap, el_to_remove, stmt);
 	    }
-	  /* Visit indirect calls and turn them into direct calls if
-	     possible.  */
-	  if (is_gimple_call (stmt))
+	}
+      /* Visit COND_EXPRs and fold the comparison with the
+	 available value-numbers.  */
+      else if (gimple_code (stmt) == GIMPLE_COND)
+	{
+	  tree op0 = gimple_cond_lhs (stmt);
+	  tree op1 = gimple_cond_rhs (stmt);
+	  tree result;
+
+	  if (TREE_CODE (op0) == SSA_NAME)
+	    op0 = VN_INFO (op0)->valnum;
+	  if (TREE_CODE (op1) == SSA_NAME)
+	    op1 = VN_INFO (op1)->valnum;
+	  result = fold_binary (gimple_cond_code (stmt), boolean_type_node,
+				op0, op1);
+	  if (result && TREE_CODE (result) == INTEGER_CST)
 	    {
-	      tree orig_fn = gimple_call_fn (stmt);
-	      tree fn;
-	      if (!orig_fn)
-		continue;
-	      if (TREE_CODE (orig_fn) == SSA_NAME)
-		fn = VN_INFO (orig_fn)->valnum;
-	      else if (TREE_CODE (orig_fn) == OBJ_TYPE_REF
-		       && TREE_CODE (OBJ_TYPE_REF_EXPR (orig_fn)) == SSA_NAME)
-		fn = VN_INFO (OBJ_TYPE_REF_EXPR (orig_fn))->valnum;
+	      if (integer_zerop (result))
+		gimple_cond_make_false (stmt);
 	      else
-		continue;
-	      if (gimple_call_addr_fndecl (fn) != NULL_TREE
-		  && useless_type_conversion_p (TREE_TYPE (orig_fn),
-						TREE_TYPE (fn)))
-		{
-		  bool can_make_abnormal_goto
-		    = stmt_can_make_abnormal_goto (stmt);
-		  bool was_noreturn = gimple_call_noreturn_p (stmt);
-
-		  if (dump_file && (dump_flags & TDF_DETAILS))
-		    {
-		      fprintf (dump_file, "Replacing call target with ");
-		      print_generic_expr (dump_file, fn, 0);
-		      fprintf (dump_file, " in ");
-		      print_gimple_stmt (dump_file, stmt, 0, 0);
-		    }
+		gimple_cond_make_true (stmt);
+	      update_stmt (stmt);
+	      el_todo = TODO_cleanup_cfg;
+	    }
+	}
+      /* Visit indirect calls and turn them into direct calls if
+	 possible.  */
+      if (is_gimple_call (stmt))
+	{
+	  tree orig_fn = gimple_call_fn (stmt);
+	  tree fn;
+	  if (!orig_fn)
+	    continue;
+	  if (TREE_CODE (orig_fn) == SSA_NAME)
+	    fn = VN_INFO (orig_fn)->valnum;
+	  else if (TREE_CODE (orig_fn) == OBJ_TYPE_REF
+		   && TREE_CODE (OBJ_TYPE_REF_EXPR (orig_fn)) == SSA_NAME)
+	    fn = VN_INFO (OBJ_TYPE_REF_EXPR (orig_fn))->valnum;
+	  else
+	    continue;
+	  if (gimple_call_addr_fndecl (fn) != NULL_TREE
+	      && useless_type_conversion_p (TREE_TYPE (orig_fn),
+					    TREE_TYPE (fn)))
+	    {
+	      bool can_make_abnormal_goto
+		  = stmt_can_make_abnormal_goto (stmt);
+	      bool was_noreturn = gimple_call_noreturn_p (stmt);
 
-		  gimple_call_set_fn (stmt, fn);
-		  VEC_safe_push (gimple, heap, to_update, stmt);
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "Replacing call target with ");
+		  print_generic_expr (dump_file, fn, 0);
+		  fprintf (dump_file, " in ");
+		  print_gimple_stmt (dump_file, stmt, 0, 0);
+		}
 
-		  /* When changing a call into a noreturn call, cfg cleanup
-		     is needed to fix up the noreturn call.  */
-		  if (!was_noreturn && gimple_call_noreturn_p (stmt))
-		    todo |= TODO_cleanup_cfg;
-
-		  /* If we removed EH side-effects from the statement, clean
-		     its EH information.  */
-		  if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
-		    {
-		      bitmap_set_bit (need_eh_cleanup,
-				      gimple_bb (stmt)->index);
-		      if (dump_file && (dump_flags & TDF_DETAILS))
-			fprintf (dump_file, "  Removed EH side-effects.\n");
-		    }
+	      gimple_call_set_fn (stmt, fn);
+	      VEC_safe_push (gimple, heap, el_to_update, stmt);
 
-		  /* Likewise for AB side-effects.  */
-		  if (can_make_abnormal_goto
-		      && !stmt_can_make_abnormal_goto (stmt))
-		    {
-		      bitmap_set_bit (need_ab_cleanup,
-				      gimple_bb (stmt)->index);
-		      if (dump_file && (dump_flags & TDF_DETAILS))
-			fprintf (dump_file, "  Removed AB side-effects.\n");
-		    }
+	      /* When changing a call into a noreturn call, cfg cleanup
+		 is needed to fix up the noreturn call.  */
+	      if (!was_noreturn && gimple_call_noreturn_p (stmt))
+		el_todo |= TODO_cleanup_cfg;
+
+	      /* If we removed EH side-effects from the statement, clean
+		 its EH information.  */
+	      if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
+		{
+		  bitmap_set_bit (need_eh_cleanup,
+				  gimple_bb (stmt)->index);
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "  Removed EH side-effects.\n");
+		}
 
-		  /* Changing an indirect call to a direct call may
-		     have exposed different semantics.  This may
-		     require an SSA update.  */
-		  todo |= TODO_update_ssa_only_virtuals;
+	      /* Likewise for AB side-effects.  */
+	      if (can_make_abnormal_goto
+		  && !stmt_can_make_abnormal_goto (stmt))
+		{
+		  bitmap_set_bit (need_ab_cleanup,
+				  gimple_bb (stmt)->index);
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "  Removed AB side-effects.\n");
 		}
+
+	      /* Changing an indirect call to a direct call may
+		 have exposed different semantics.  This may
+		 require an SSA update.  */
+	      el_todo |= TODO_update_ssa_only_virtuals;
 	    }
 	}
+    }
+}
 
-      for (gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
-	{
-	  gimple stmt, phi = gsi_stmt (gsi);
-	  tree sprime = NULL_TREE, res = PHI_RESULT (phi);
-	  pre_expr sprimeexpr, resexpr;
-	  gimple_stmt_iterator gsi2;
-
-	  /* We want to perform redundant PHI elimination.  Do so by
-	     replacing the PHI with a single copy if possible.
-	     Do not touch inserted, single-argument or virtual PHIs.  */
-	  if (gimple_phi_num_args (phi) == 1
-	      || virtual_operand_p (res))
-	    {
-	      gsi_next (&gsi);
-	      continue;
-	    }
+/* Make no longer available leaders no longer available.  */
 
-	  resexpr = get_or_alloc_expr_for_name (res);
-	  sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
-					   get_expr_value_id (resexpr), NULL);
-	  if (sprimeexpr)
-	    {
-	      if (sprimeexpr->kind == CONSTANT)
-		sprime = PRE_EXPR_CONSTANT (sprimeexpr);
-	      else if (sprimeexpr->kind == NAME)
-		sprime = PRE_EXPR_NAME (sprimeexpr);
-	      else
-		gcc_unreachable ();
-	    }
-	  if (!sprime && is_gimple_min_invariant (VN_INFO (res)->valnum))
-	    {
-	      sprime = VN_INFO (res)->valnum;
-	      if (!useless_type_conversion_p (TREE_TYPE (res),
-					      TREE_TYPE (sprime)))
-		sprime = fold_convert (TREE_TYPE (res), sprime);
-	    }
-	  if (!sprime
-	      || sprime == res)
-	    {
-	      gsi_next (&gsi);
-	      continue;
-	    }
+static void
+eliminate_leave_block (dom_walk_data *, basic_block)
+{
+  tree entry;
+  while ((entry = VEC_pop (tree, el_avail_stack)) != NULL_TREE)
+    VEC_replace (tree, el_avail,
+		 SSA_NAME_VERSION (VN_INFO (entry)->valnum), NULL_TREE);
+}
 
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      fprintf (dump_file, "Replaced redundant PHI node defining ");
-	      print_generic_expr (dump_file, res, 0);
-	      fprintf (dump_file, " with ");
-	      print_generic_expr (dump_file, sprime, 0);
-	      fprintf (dump_file, "\n");
-	    }
+/* Eliminate fully redundant computations.  */
 
-	  remove_phi_node (&gsi, false);
+static unsigned int
+eliminate (void)
+{
+  struct dom_walk_data walk_data;
+  gimple_stmt_iterator gsi;
+  gimple stmt;
+  unsigned i;
 
-	  if (!bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res))
-	      && TREE_CODE (sprime) == SSA_NAME)
-	    gimple_set_plf (SSA_NAME_DEF_STMT (sprime), NECESSARY, true);
+  need_eh_cleanup = BITMAP_ALLOC (NULL);
+  need_ab_cleanup = BITMAP_ALLOC (NULL);
 
-	  if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
-	    sprime = fold_convert (TREE_TYPE (res), sprime);
-	  stmt = gimple_build_assign (res, sprime);
-	  SSA_NAME_DEF_STMT (res) = stmt;
-	  gimple_set_plf (stmt, NECESSARY, gimple_plf (phi, NECESSARY));
-
-	  gsi2 = gsi_after_labels (b);
-	  gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
-	  /* Queue the copy for eventual removal.  */
-	  VEC_safe_push (gimple, heap, to_remove, stmt);
-	  /* If we inserted this PHI node ourself, it's not an elimination.  */
-	  if (bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res)))
-	    pre_stats.phis--;
-	  else
-	    pre_stats.eliminations++;
-	}
-    }
+  el_to_remove = NULL;
+  el_to_update = NULL;
+  el_todo = 0;
+  el_avail = NULL;
+  el_avail_stack = NULL;
+
+  walk_data.dom_direction = CDI_DOMINATORS;
+  walk_data.initialize_block_local_data = NULL;
+  walk_data.before_dom_children = eliminate_bb;
+  walk_data.after_dom_children = eliminate_leave_block;
+  walk_data.global_data = NULL;
+  walk_data.block_local_data_size = 0;
+  init_walk_dominator_tree (&walk_data);
+  walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+  fini_walk_dominator_tree (&walk_data);
+
+  VEC_free (tree, heap, el_avail);
+  VEC_free (tree, heap, el_avail_stack);
 
   /* We cannot remove stmts during BB walk, especially not release SSA
      names there as this confuses the VN machinery.  The stmts ending
-     up in to_remove are either stores or simple copies.  */
-  FOR_EACH_VEC_ELT (gimple, to_remove, i, stmt)
+     up in el_to_remove are either stores or simple copies.  */
+  FOR_EACH_VEC_ELT (gimple, el_to_remove, i, stmt)
     {
       tree lhs = gimple_assign_lhs (stmt);
       tree rhs = gimple_assign_rhs1 (stmt);
@@ -4539,7 +4591,8 @@  eliminate (void)
 	{
 	  SET_USE (use_p, rhs);
 	  update_stmt (use_stmt);
-	  if (bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (lhs))
+	  if (inserted_exprs
+	      && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (lhs))
 	      && TREE_CODE (rhs) == SSA_NAME)
 	    gimple_set_plf (SSA_NAME_DEF_STMT (rhs), NECESSARY, true);
 	}
@@ -4553,21 +4606,43 @@  eliminate (void)
 	  unlink_stmt_vdef (stmt);
 	  if (gsi_remove (&gsi, true))
 	    bitmap_set_bit (need_eh_cleanup, bb->index);
-	  if (TREE_CODE (lhs) == SSA_NAME)
+	  if (inserted_exprs
+	      && TREE_CODE (lhs) == SSA_NAME)
 	    bitmap_clear_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
 	  release_defs (stmt);
 	}
     }
-  VEC_free (gimple, heap, to_remove);
+  VEC_free (gimple, heap, el_to_remove);
 
   /* We cannot update call statements with virtual operands during
      SSA walk.  This might remove them which in turn makes our
      VN lattice invalid.  */
-  FOR_EACH_VEC_ELT (gimple, to_update, i, stmt)
+  FOR_EACH_VEC_ELT (gimple, el_to_update, i, stmt)
     update_stmt (stmt);
-  VEC_free (gimple, heap, to_update);
+  VEC_free (gimple, heap, el_to_update);
 
-  return todo;
+  return el_todo;
+}
+
+/* Perform CFG cleanups made necessary by elimination.  */
+
+static void
+fini_eliminate (void)
+{
+  bool do_eh_cleanup = !bitmap_empty_p (need_eh_cleanup);
+  bool do_ab_cleanup = !bitmap_empty_p (need_ab_cleanup);
+
+  if (do_eh_cleanup)
+    gimple_purge_all_dead_eh_edges (need_eh_cleanup);
+
+  if (do_ab_cleanup)
+    gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup);
+
+  BITMAP_FREE (need_eh_cleanup);
+  BITMAP_FREE (need_ab_cleanup);
+
+  if (do_eh_cleanup || do_ab_cleanup)
+    cleanup_tree_cfg ();
 }
 
 /* Borrow a bit of tree-ssa-dce.c for the moment.
@@ -4767,7 +4842,7 @@  my_rev_post_order_compute (int *post_ord
 /* Initialize data structures used by PRE.  */
 
 static void
-init_pre (bool do_fre)
+init_pre (void)
 {
   basic_block bb;
 
@@ -4779,8 +4854,6 @@  init_pre (bool do_fre)
 			 get_max_value_id() + 1);
   name_to_id = NULL;
 
-  in_fre = do_fre;
-
   inserted_exprs = BITMAP_ALLOC (NULL);
 
   connect_infinite_loops_to_exit ();
@@ -4804,28 +4877,19 @@  init_pre (bool do_fre)
 				     sizeof (struct pre_expr_d), 30);
   FOR_ALL_BB (bb)
     {
-      if (!do_fre)
-	{
-	  EXP_GEN (bb) = bitmap_set_new ();
-	  PHI_GEN (bb) = bitmap_set_new ();
-	  TMP_GEN (bb) = bitmap_set_new ();
-	}
+      EXP_GEN (bb) = bitmap_set_new ();
+      PHI_GEN (bb) = bitmap_set_new ();
+      TMP_GEN (bb) = bitmap_set_new ();
       AVAIL_OUT (bb) = bitmap_set_new ();
     }
-
-  need_eh_cleanup = BITMAP_ALLOC (NULL);
-  need_ab_cleanup = BITMAP_ALLOC (NULL);
 }
 
 
 /* Deallocate data structures used by PRE.  */
 
 static void
-fini_pre (bool do_fre)
+fini_pre ()
 {
-  bool do_eh_cleanup = !bitmap_empty_p (need_eh_cleanup);
-  bool do_ab_cleanup = !bitmap_empty_p (need_ab_cleanup);
-
   free (postorder);
   VEC_free (bitmap, heap, value_expressions);
   BITMAP_FREE (inserted_exprs);
@@ -4839,28 +4903,12 @@  fini_pre (bool do_fre)
   free_aux_for_blocks ();
 
   free_dominance_info (CDI_POST_DOMINATORS);
-
-  if (do_eh_cleanup)
-    gimple_purge_all_dead_eh_edges (need_eh_cleanup);
-
-  if (do_ab_cleanup)
-    gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup);
-
-  BITMAP_FREE (need_eh_cleanup);
-  BITMAP_FREE (need_ab_cleanup);
-
-  if (do_eh_cleanup || do_ab_cleanup)
-    cleanup_tree_cfg ();
-
-  if (!do_fre)
-    loop_optimizer_finalize ();
 }
 
-/* Main entry point to the SSA-PRE pass.  DO_FRE is true if the caller
-   only wants to do full redundancy elimination.  */
+/* Gate and execute functions for PRE.  */
 
 static unsigned int
-execute_pre (bool do_fre)
+do_pre (void)
 {
   unsigned int todo = 0;
 
@@ -4869,18 +4917,15 @@  execute_pre (bool do_fre)
 
   /* This has to happen before SCCVN runs because
      loop_optimizer_init may create new phis, etc.  */
-  if (!do_fre)
-    loop_optimizer_init (LOOPS_NORMAL);
+  loop_optimizer_init (LOOPS_NORMAL);
 
-  if (!run_scc_vn (do_fre ? VN_WALKREWRITE : VN_WALK))
+  if (!run_scc_vn (VN_WALK))
     {
-      if (!do_fre)
-	loop_optimizer_finalize ();
-
+      loop_optimizer_finalize ();
       return 0;
     }
 
-  init_pre (do_fre);
+  init_pre ();
   scev_initialize ();
 
   /* Collect and value number expressions computed in each basic block.  */
@@ -4889,13 +4934,16 @@  execute_pre (bool do_fre)
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       basic_block bb;
-
       FOR_ALL_BB (bb)
 	{
-	  print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
-	  print_bitmap_set (dump_file, PHI_GEN (bb), "phi_gen", bb->index);
-	  print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
-	  print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
+	  print_bitmap_set (dump_file, EXP_GEN (bb),
+			    "exp_gen", bb->index);
+	  print_bitmap_set (dump_file, PHI_GEN (bb),
+			    "phi_gen", bb->index);
+	  print_bitmap_set (dump_file, TMP_GEN (bb),
+			    "tmp_gen", bb->index);
+	  print_bitmap_set (dump_file, AVAIL_OUT (bb),
+			    "avail_out", bb->index);
 	}
     }
 
@@ -4904,7 +4952,7 @@  execute_pre (bool do_fre)
      fixed, don't run it when he have an incredibly large number of
      bb's.  If we aren't going to run insert, there is no point in
      computing ANTIC, either, even though it's plenty fast.  */
-  if (!do_fre && n_basic_blocks < 4000)
+  if (n_basic_blocks < 4000)
     {
       compute_antic ();
       insert ();
@@ -4926,37 +4974,28 @@  execute_pre (bool do_fre)
   statistics_counter_event (cfun, "Constified", pre_stats.constified);
 
   clear_expression_ids ();
-  if (!do_fre)
-    {
-      remove_dead_inserted_code ();
-      todo |= TODO_verify_flow;
-    }
+  remove_dead_inserted_code ();
+  todo |= TODO_verify_flow;
 
   scev_finalize ();
-  fini_pre (do_fre);
+  fini_pre ();
+  fini_eliminate ();
+  loop_optimizer_finalize ();
+
+  /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
+     case we can merge the block with the remaining predecessor of the block.
+     It should either:
+     - call merge_blocks after each tail merge iteration
+     - call merge_blocks after all tail merge iterations
+     - mark TODO_cleanup_cfg when necessary
+     - share the cfg cleanup with fini_pre.  */
+  todo |= tail_merge_optimize (todo);
 
-  if (!do_fre)
-    /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
-       case we can merge the block with the remaining predecessor of the block.
-       It should either:
-       - call merge_blocks after each tail merge iteration
-       - call merge_blocks after all tail merge iterations
-       - mark TODO_cleanup_cfg when necessary
-       - share the cfg cleanup with fini_pre.  */
-    todo |= tail_merge_optimize (todo);
   free_scc_vn ();
 
   return todo;
 }
 
-/* Gate and execute functions for PRE.  */
-
-static unsigned int
-do_pre (void)
-{
-  return execute_pre (false);
-}
-
 static bool
 gate_pre (void)
 {
@@ -4990,7 +5029,25 @@  struct gimple_opt_pass pass_pre =
 static unsigned int
 execute_fre (void)
 {
-  return execute_pre (true);
+  unsigned int todo = 0;
+
+  if (!run_scc_vn (VN_WALKREWRITE))
+    return 0;
+
+  memset (&pre_stats, 0, sizeof (pre_stats));
+
+  /* Remove all the redundant expressions.  */
+  todo |= eliminate ();
+
+  fini_eliminate ();
+
+  free_scc_vn ();
+
+  statistics_counter_event (cfun, "Insertions", pre_stats.insertions);
+  statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations);
+  statistics_counter_event (cfun, "Constified", pre_stats.constified);
+
+  return todo;
 }
 
 static bool
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 191215)
+++ gcc/Makefile.in	(working copy)
@@ -2317,7 +2317,7 @@  tree-ssa-pre.o : tree-ssa-pre.c $(TREE_F
    $(TM_H) coretypes.h $(TREE_PASS_H) $(FLAGS_H) langhooks.h \
    $(CFGLOOP_H) alloc-pool.h $(BASIC_BLOCK_H) $(BITMAP_H) $(HASH_TABLE_H) \
    $(GIMPLE_H) $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h $(PARAMS_H) \
-   $(DBGCNT_H) tree-scalar-evolution.h $(GIMPLE_PRETTY_PRINT_H)
+   $(DBGCNT_H) tree-scalar-evolution.h $(GIMPLE_PRETTY_PRINT_H) domwalk.h
 tree-ssa-sccvn.o : tree-ssa-sccvn.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) \
    $(TM_H) coretypes.h dumpfile.h $(FLAGS_H) $(CFGLOOP_H) \