--- a/gcc/tree-ssa-pre.c	Fri Oct 27 22:46:09 2017 +0900
+++ b/gcc/tree-ssa-pre.c	Thu Oct 25 07:37:49 2018 +0900
@@ -1,5 +1,5 @@
 /* Full and partial redundancy elimination and code hoisting on SSA GIMPLE.
-   Copyright (C) 2001-2017 Free Software Foundation, Inc.
+   Copyright (C) 2001-2018 Free Software Foundation, Inc.
    Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
    <stevenb@suse.de>
 
@@ -49,6 +49,7 @@
 #include "dbgcnt.h"
 #include "domwalk.h"
 #include "tree-ssa-propagate.h"
+#include "tree-ssa-dce.h"
 #include "tree-cfgcleanup.h"
 #include "alias.h"
 
@@ -400,15 +401,6 @@
   return expressions[id];
 }
 
-/* Free the expression id field in all of our expressions,
-   and then destroy the expressions array.  */
-
-static void
-clear_expression_ids (void)
-{
-  expressions.release ();
-}
-
 static object_allocator<pre_expr_d> pre_expr_pool ("pre_expr nodes");
 
 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it.  */
@@ -671,6 +663,7 @@
       id = VN_INFO (PRE_EXPR_NAME (expr))->value_id;
       break;
     case NARY:
+      gcc_assert (!PRE_EXPR_NARY (expr)->predicated_values);
       id = PRE_EXPR_NARY (expr)->value_id;
       break;
     case REFERENCE:
@@ -685,10 +678,10 @@
   return id;
 }
 
-/* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL.  */
+/* Return a VN valnum (SSA name or constant) for the PRE value-id VAL.  */
 
 static tree
-sccvn_valnum_from_value_id (unsigned int val)
+vn_valnum_from_value_id (unsigned int val)
 {
   bitmap_iterator bi;
   unsigned int i;
@@ -704,16 +697,6 @@
   return NULL_TREE;
 }
 
-/* Remove an expression EXPR from a bitmapped set.  */
-
-static void
-bitmap_remove_expr_from_set (bitmap_set_t set, pre_expr expr)
-{
-  unsigned int val  = get_expr_value_id (expr);
-  bitmap_clear_bit (&set->values, val);
-  bitmap_clear_bit (&set->expressions, get_expression_id (expr));
-}
-
 /* Insert an expression EXPR into a bitmapped set.  */
 
 static void
@@ -813,20 +796,21 @@
 {
   unsigned int i;
   bitmap_iterator bi;
-  pre_expr to_remove = NULL;
+  unsigned to_remove = -1U;
+  bitmap_and_compl_into (&a->values, &b->values);
   FOR_EACH_EXPR_ID_IN_SET (a, i, bi)
     {
-      if (to_remove)
+      if (to_remove != -1U)
 	{
-	  bitmap_remove_expr_from_set (a, to_remove);
-	  to_remove = NULL;
+	  bitmap_clear_bit (&a->expressions, to_remove);
+	  to_remove = -1U;
 	}
       pre_expr expr = expression_for_id (i);
-      if (bitmap_bit_p (&b->values, get_expr_value_id (expr)))
-	to_remove = expr;
+      if (! bitmap_bit_p (&a->values, get_expr_value_id (expr)))
+	to_remove = i;
     }
-  if (to_remove)
-    bitmap_remove_expr_from_set (a, to_remove);
+  if (to_remove != -1U)
+    bitmap_clear_bit (&a->expressions, to_remove);
 }
 
 
@@ -841,12 +825,6 @@
   return bitmap_bit_p (&set->values, value_id);
 }
 
-static inline bool
-bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr)
-{
-  return bitmap_bit_p (&set->expressions, get_expression_id (expr));
-}
-
 /* Return true if two bitmap sets are equal.  */
 
 static bool
@@ -1237,9 +1215,10 @@
 find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2,
 		     bitmap_set_t set3 = NULL)
 {
-  pre_expr result;
-
-  result = bitmap_find_leader (set1, val);
+  pre_expr result = NULL;
+
+  if (set1)
+    result = bitmap_find_leader (set1, val);
   if (!result && set2)
     result = bitmap_find_leader (set2, val);
   if (!result && set3)
@@ -1266,7 +1245,7 @@
   gcc_unreachable ();
 }
 
-/* Get a representative SSA_NAME for a given expression.
+/* Get a representative SSA_NAME for a given expression that is available in B.
    Since all of our sub-expressions are treated as values, we require
    them to be SSA_NAME's for simplicity.
    Prior versions of GVNPRE used to use "value handles" here, so that
@@ -1275,9 +1254,9 @@
    them to be usable without finding leaders).  */
 
 static tree
-get_representative_for (const pre_expr e)
+get_representative_for (const pre_expr e, basic_block b = NULL)
 {
-  tree name;
+  tree name, valnum = NULL_TREE;
   unsigned int value_id = get_expr_value_id (e);
 
   switch (e->kind)
@@ -1298,7 +1277,18 @@
 	  {
 	    pre_expr rep = expression_for_id (i);
 	    if (rep->kind == NAME)
-	      return VN_INFO (PRE_EXPR_NAME (rep))->valnum;
+	      {
+		tree name = PRE_EXPR_NAME (rep);
+		valnum = VN_INFO (name)->valnum;
+		gimple *def = SSA_NAME_DEF_STMT (name);
+		/* We have to return either a new representative or one
+		   that can be used for expression simplification and thus
+		   is available in B.  */
+		if (! b 
+		    || gimple_nop_p (def)
+		    || dominated_by_p (CDI_DOMINATORS, b, gimple_bb (def)))
+		  return name;
+	      }
 	    else if (rep->kind == CONSTANT)
 	      return PRE_EXPR_CONSTANT (rep);
 	  }
@@ -1313,9 +1303,9 @@
      ???  We should be able to re-use this when we insert the statement
      to compute it.  */
   name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
-  VN_INFO_GET (name)->value_id = value_id;
-  VN_INFO (name)->valnum = name;
-  /* ???  For now mark this SSA name for release by SCCVN.  */
+  VN_INFO (name)->value_id = value_id;
+  VN_INFO (name)->valnum = valnum ? valnum : name;
+  /* ???  For now mark this SSA name for release by VN.  */
   VN_INFO (name)->needs_insertion = true;
   add_to_value (value_id, get_or_alloc_expr_for_name (name));
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1331,19 +1321,19 @@
 }
 
 
-
 static pre_expr
-phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
-	       basic_block pred, basic_block phiblock);
+phi_translate (bitmap_set_t, pre_expr, bitmap_set_t, bitmap_set_t, edge);
 
 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
    the phis in PRED.  Return NULL if we can't find a leader for each part
    of the translated expression.  */
 
 static pre_expr
-phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
-		 basic_block pred, basic_block phiblock)
+phi_translate_1 (bitmap_set_t dest,
+		 pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, edge e)
 {
+  basic_block pred = e->src;
+  basic_block phiblock = e->dest;
   switch (expr->kind)
     {
     case NARY:
@@ -1364,9 +1354,12 @@
                 pre_expr leader, result;
 		unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id;
 		leader = find_leader_in_sets (op_val_id, set1, set2);
-                result = phi_translate (leader, set1, set2, pred, phiblock);
+		result = phi_translate (dest, leader, set1, set2, e);
 		if (result && result != leader)
-		  newnary->op[i] = get_representative_for (result);
+		  /* If op has a leader in the sets we translate make
+		     sure to use the value of the translated expression.
+		     We might need a new representative for that.  */
+		  newnary->op[i] = get_representative_for (result, pred);
 		else if (!result)
 		  return NULL;
 
@@ -1393,21 +1386,45 @@
 		       to be inserted and increased register pressure.
 		       See PR77498 - this avoids doing predcoms work in
 		       a less efficient way.  */
-		    if (find_edge (pred, phiblock)->flags & EDGE_DFS_BACK)
+		    if (e->flags & EDGE_DFS_BACK)
 		      ;
 		    else
 		      {
 			unsigned value_id = get_expr_value_id (constant);
-			constant = find_leader_in_sets (value_id, set1, set2,
+			/* We want a leader in ANTIC_OUT or AVAIL_OUT here.
+			   dest has what we computed into ANTIC_OUT sofar
+			   so pick from that - since topological sorting
+			   by sorted_array_from_bitmap_set isn't perfect
+			   we may lose some cases here.  */
+			constant = find_leader_in_sets (value_id, dest,
 							AVAIL_OUT (pred));
 			if (constant)
-			  return constant;
+			  {
+			    if (dump_file && (dump_flags & TDF_DETAILS))
+			      {
+				fprintf (dump_file, "simplifying ");
+				print_pre_expr (dump_file, expr);
+				fprintf (dump_file, " translated %d -> %d to ",
+					 phiblock->index, pred->index);
+				PRE_EXPR_NARY (expr) = newnary;
+				print_pre_expr (dump_file, expr);
+				PRE_EXPR_NARY (expr) = nary;
+				fprintf (dump_file, " to ");
+				print_pre_expr (dump_file, constant);
+				fprintf (dump_file, "\n");
+			      }
+			    return constant;
+			  }
 		      }
 		  }
 		else
 		  return constant;
 	      }
 
+	    /* vn_nary_* do not valueize operands.  */
+	    for (i = 0; i < newnary->length; ++i)
+	      if (TREE_CODE (newnary->op[i]) == SSA_NAME)
+		newnary->op[i] = VN_INFO (newnary->op[i])->valnum;
 	    tree result = vn_nary_op_lookup_pieces (newnary->length,
 						    newnary->opcode,
 						    newnary->type,
@@ -1419,50 +1436,11 @@
 	    expr = pre_expr_pool.allocate ();
 	    expr->kind = NARY;
 	    expr->id = 0;
-	    if (nary)
+	    if (nary && !nary->predicated_values)
 	      {
 		PRE_EXPR_NARY (expr) = nary;
 		new_val_id = nary->value_id;
 		get_or_alloc_expression_id (expr);
-		/* When we end up re-using a value number make sure that
-		   doesn't have unrelated (which we can't check here)
-		   range or points-to info on it.  */
-		if (result
-		    && INTEGRAL_TYPE_P (TREE_TYPE (result))
-		    && SSA_NAME_RANGE_INFO (result)
-		    && ! SSA_NAME_IS_DEFAULT_DEF (result))
-		  {
-		    if (! VN_INFO (result)->info.range_info)
-		      {
-			VN_INFO (result)->info.range_info
-			  = SSA_NAME_RANGE_INFO (result);
-			VN_INFO (result)->range_info_anti_range_p
-			  = SSA_NAME_ANTI_RANGE_P (result);
-		      }
-		    if (dump_file && (dump_flags & TDF_DETAILS))
-		      {
-			fprintf (dump_file, "clearing range info of ");
-			print_generic_expr (dump_file, result);
-			fprintf (dump_file, "\n");
-		      }
-		    SSA_NAME_RANGE_INFO (result) = NULL;
-		  }
-		else if (result
-			 && POINTER_TYPE_P (TREE_TYPE (result))
-			 && SSA_NAME_PTR_INFO (result)
-			 && ! SSA_NAME_IS_DEFAULT_DEF (result))
-		  {
-		    if (! VN_INFO (result)->info.ptr_info)
-		      VN_INFO (result)->info.ptr_info
-			= SSA_NAME_PTR_INFO (result);
-		    if (dump_file && (dump_flags & TDF_DETAILS))
-		      {
-			fprintf (dump_file, "clearing points-to info of ");
-			print_generic_expr (dump_file, result);
-			fprintf (dump_file, "\n");
-		      }
-		    SSA_NAME_PTR_INFO (result) = NULL;
-		  }
 	      }
 	    else
 	      {
@@ -1519,7 +1497,7 @@
 		  }
 		op_val_id = VN_INFO (op[n])->value_id;
 		leader = find_leader_in_sets (op_val_id, set1, set2);
-		opresult = phi_translate (leader, set1, set2, pred, phiblock);
+		opresult = phi_translate (dest, leader, set1, set2, e);
 		if (opresult && opresult != leader)
 		  {
 		    tree name = get_representative_for (opresult);
@@ -1566,7 +1544,6 @@
 	if (changed || newvuse != vuse)
 	  {
 	    unsigned int new_val_id;
-	    pre_expr constant;
 
 	    tree result = vn_reference_lookup_pieces (newvuse, ref->set,
 						      ref->type,
@@ -1611,15 +1588,7 @@
 	    expr->id = 0;
 
 	    if (newref)
-	      {
-		PRE_EXPR_REFERENCE (expr) = newref;
-		constant = fully_constant_expression (expr);
-		if (constant != expr)
-		  return constant;
-
-		new_val_id = newref->value_id;
-		get_or_alloc_expression_id (expr);
-	      }
+	      new_val_id = newref->value_id;
 	    else
 	      {
 		if (changed || !same_valid)
@@ -1637,12 +1606,9 @@
 						     newoperands,
 						     result, new_val_id);
 		newoperands = vNULL;
-		PRE_EXPR_REFERENCE (expr) = newref;
-		constant = fully_constant_expression (expr);
-		if (constant != expr)
-		  return constant;
-		get_or_alloc_expression_id (expr);
 	      }
+	    PRE_EXPR_REFERENCE (expr) = newref;
+	    get_or_alloc_expression_id (expr);
 	    add_to_value (new_val_id, expr);
 	  }
 	newoperands.release ();
@@ -1659,7 +1625,6 @@
 	if (gimple_code (def_stmt) == GIMPLE_PHI
 	    && gimple_bb (def_stmt) == phiblock)
 	  {
-	    edge e = find_edge (pred, gimple_bb (def_stmt));
 	    tree def = PHI_ARG_DEF (def_stmt, e->dest_idx);
 
 	    /* Handle constant. */
@@ -1682,8 +1647,8 @@
 /* Wrapper around phi_translate_1 providing caching functionality.  */
 
 static pre_expr
-phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
-	       basic_block pred, basic_block phiblock)
+phi_translate (bitmap_set_t dest, pre_expr expr,
+	       bitmap_set_t set1, bitmap_set_t set2, edge e)
 {
   expr_pred_trans_t slot = NULL;
   pre_expr phitrans;
@@ -1701,7 +1666,7 @@
   /* Don't add translations of NAMEs as those are cheap to translate.  */
   if (expr->kind != NAME)
     {
-      if (phi_trans_add (&slot, expr, pred))
+      if (phi_trans_add (&slot, expr, e->src))
 	return slot->v;
       /* Store NULL for the value we want to return in the case of
 	 recursing.  */
@@ -1709,7 +1674,10 @@
     }
 
   /* Translate.  */
-  phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock);
+  basic_block saved_valueize_bb = vn_context_bb;
+  vn_context_bb = e->src;
+  phitrans = phi_translate_1 (dest, expr, set1, set2, e);
+  vn_context_bb = saved_valueize_bb;
 
   if (slot)
     {
@@ -1730,14 +1698,13 @@
    expressions in DEST.  */
 
 static void
-phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
-		   basic_block phiblock)
+phi_translate_set (bitmap_set_t dest, bitmap_set_t set, edge e)
 {
   vec<pre_expr> exprs;
   pre_expr expr;
   int i;
 
-  if (gimple_seq_empty_p (phi_nodes (phiblock)))
+  if (gimple_seq_empty_p (phi_nodes (e->dest)))
     {
       bitmap_set_copy (dest, set);
       return;
@@ -1747,18 +1714,11 @@
   FOR_EACH_VEC_ELT (exprs, i, expr)
     {
       pre_expr translated;
-      translated = phi_translate (expr, set, NULL, pred, phiblock);
+      translated = phi_translate (dest, expr, set, NULL, e);
       if (!translated)
 	continue;
 
-      /* We might end up with multiple expressions from SET being
-	 translated to the same value.  In this case we do not want
-	 to retain the NARY or REFERENCE expression but prefer a NAME
-	 which would be the leader.  */
-      if (translated->kind == NAME)
-	bitmap_value_replace_in_set (dest, translated);
-      else
-	bitmap_value_insert_into_set (dest, translated);
+      bitmap_insert_into_set (dest, translated);
     }
   exprs.release ();
 }
@@ -1961,7 +1921,15 @@
   FOR_EACH_VEC_ELT (exprs, i, expr)
     {
       if (!valid_in_sets (set1, set2, expr))
-	bitmap_remove_expr_from_set (set1, expr);
+	{
+	  unsigned int val  = get_expr_value_id (expr);
+	  bitmap_clear_bit (&set1->expressions, get_expression_id (expr));
+	  /* We are entered with possibly multiple expressions for a value
+	     so before removing a value from the set see if there's an
+	     expression for it left.  */
+	  if (! bitmap_find_leader (set1, val))
+	    bitmap_clear_bit (&set1->values, val);
+	}
     }
   exprs.release ();
 }
@@ -1974,15 +1942,17 @@
 {
   bitmap_iterator bi;
   unsigned i;
-  pre_expr to_remove = NULL;
+  unsigned to_remove = -1U;
+  bool any_removed = false;
 
   FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
     {
       /* Remove queued expr.  */
-      if (to_remove)
+      if (to_remove != -1U)
 	{
-	  bitmap_remove_expr_from_set (set, to_remove);
-	  to_remove = NULL;
+	  bitmap_clear_bit (&set->expressions, to_remove);
+	  any_removed = true;
+	  to_remove = -1U;
 	}
 
       pre_expr expr = expression_for_id (i);
@@ -1998,7 +1968,7 @@
 					   block, gimple_bb (def_stmt)))
 		      || (gimple_bb (def_stmt) == block
 			  && value_dies_in_block_x (expr, block))))
-		to_remove = expr;
+		to_remove = i;
 	    }
 	}
       else if (expr->kind == NARY)
@@ -2010,13 +1980,36 @@
 	     as the available expression might be after the exit point.  */
 	  if (BB_MAY_NOTRETURN (block)
 	      && vn_nary_may_trap (nary))
-	    to_remove = expr;
+	    to_remove = i;
 	}
     }
 
   /* Remove queued expr.  */
-  if (to_remove)
-    bitmap_remove_expr_from_set (set, to_remove);
+  if (to_remove != -1U)
+    {
+      bitmap_clear_bit (&set->expressions, to_remove);
+      any_removed = true;
+    }
+
+  /* Above we only removed expressions, now clean the set of values
+     which no longer have any corresponding expression.  We cannot
+     clear the value at the time we remove an expression since there
+     may be multiple expressions per value.
+     If we'd queue possibly to be removed values we could use
+     the bitmap_find_leader way to see if there's still an expression
+     for it.  For some ratio of to be removed values and number of
+     values/expressions in the set this might be faster than rebuilding
+     the value-set.  */
+  if (any_removed)
+    {
+      bitmap_clear (&set->values);
+      FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
+	{
+	  pre_expr expr = expression_for_id (i);
+	  unsigned int value_id = get_expr_value_id (expr);
+	  bitmap_set_bit (&set->values, value_id);
+	}
+    }
 }
 
 static sbitmap has_abnormal_preds;
@@ -2029,17 +2022,17 @@
      ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
 
    ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
-*/
+
+   Note that clean() is deferred until after the iteration.  */
 
 static bool
 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
 {
   bitmap_set_t S, old, ANTIC_OUT;
-  bitmap_iterator bi;
-  unsigned int bii;
   edge e;
   edge_iterator ei;
 
+  bool was_visited = BB_VISITED (block);
   bool changed = ! BB_VISITED (block);
   BB_VISITED (block) = 1;
   old = ANTIC_OUT = S = NULL;
@@ -2059,9 +2052,9 @@
      translate through.  */
   else if (single_succ_p (block))
     {
-      basic_block succ_bb = single_succ (block);
-      gcc_assert (BB_VISITED (succ_bb));
-      phi_translate_set (ANTIC_OUT, ANTIC_IN (succ_bb), block, succ_bb);
+      e = single_succ_edge (block);
+      gcc_assert (BB_VISITED (e->dest));
+      phi_translate_set (ANTIC_OUT, ANTIC_IN (e->dest), e);
     }
   /* If we have multiple successors, we take the intersection of all of
      them.  Note that in the case of loop exit phi nodes, we may have
@@ -2069,16 +2062,16 @@
   else
     {
       size_t i;
-      basic_block bprime, first = NULL;
-
-      auto_vec<basic_block> worklist (EDGE_COUNT (block->succs));
+      edge first = NULL;
+
+      auto_vec<edge> worklist (EDGE_COUNT (block->succs));
       FOR_EACH_EDGE (e, ei, block->succs)
 	{
 	  if (!first
 	      && BB_VISITED (e->dest))
-	    first = e->dest;
+	    first = e;
 	  else if (BB_VISITED (e->dest))
-	    worklist.quick_push (e->dest);
+	    worklist.quick_push (e);
 	  else
 	    {
 	      /* Unvisited successors get their ANTIC_IN replaced by the
@@ -2095,7 +2088,7 @@
          which is guaranteed by iteration order.  */
       gcc_assert (first != NULL);
 
-      phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
+      phi_translate_set (ANTIC_OUT, ANTIC_IN (first->dest), first);
 
       /* If we have multiple successors we need to intersect the ANTIC_OUT
          sets.  For values that's a simple intersection but for
@@ -2104,31 +2097,29 @@
 	 Avoid randomness and running into cycles like for PR82129 and
 	 canonicalize the expression we choose to the one with the
 	 lowest id.  This requires we actually compute the union first.  */
-      FOR_EACH_VEC_ELT (worklist, i, bprime)
+      FOR_EACH_VEC_ELT (worklist, i, e)
 	{
-	  if (!gimple_seq_empty_p (phi_nodes (bprime)))
+	  if (!gimple_seq_empty_p (phi_nodes (e->dest)))
 	    {
 	      bitmap_set_t tmp = bitmap_set_new ();
-	      phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
+	      phi_translate_set (tmp, ANTIC_IN (e->dest), e);
 	      bitmap_and_into (&ANTIC_OUT->values, &tmp->values);
 	      bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions);
 	      bitmap_set_free (tmp);
 	    }
 	  else
 	    {
-	      bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (bprime)->values);
+	      bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (e->dest)->values);
 	      bitmap_ior_into (&ANTIC_OUT->expressions,
-			       &ANTIC_IN (bprime)->expressions);
+			       &ANTIC_IN (e->dest)->expressions);
 	    }
 	}
       if (! worklist.is_empty ())
 	{
-	  /* Prune expressions not in the value set, canonicalizing to
-	     expression with lowest ID.  */
+	  /* Prune expressions not in the value set.  */
 	  bitmap_iterator bi;
 	  unsigned int i;
 	  unsigned int to_clear = -1U;
-	  bitmap seen_value = BITMAP_ALLOC (NULL);
 	  FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT, i, bi)
 	    {
 	      if (to_clear != -1U)
@@ -2138,13 +2129,11 @@
 		}
 	      pre_expr expr = expression_for_id (i);
 	      unsigned int value_id = get_expr_value_id (expr);
-	      if (!bitmap_bit_p (&ANTIC_OUT->values, value_id)
-		  || !bitmap_set_bit (seen_value, value_id))
+	      if (!bitmap_bit_p (&ANTIC_OUT->values, value_id))
 		to_clear = i;
 	    }
 	  if (to_clear != -1U)
 	    bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
-	  BITMAP_FREE (seen_value);
 	}
     }
 
@@ -2161,11 +2150,40 @@
 
   /* Then union in the ANTIC_OUT - TMP_GEN values,
      to get ANTIC_OUT U EXP_GEN - TMP_GEN */
-  FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
-    bitmap_value_insert_into_set (ANTIC_IN (block),
-				  expression_for_id (bii));
-
-  clean (ANTIC_IN (block));
+  bitmap_ior_into (&ANTIC_IN (block)->values, &S->values);
+  bitmap_ior_into (&ANTIC_IN (block)->expressions, &S->expressions);
+
+  /* clean (ANTIC_IN (block)) is defered to after the iteration converged
+     because it can cause non-convergence, see for example PR81181.  */
+
+  /* Intersect ANTIC_IN with the old ANTIC_IN.  This is required until
+     we properly represent the maximum expression set, thus not prune
+     values without expressions during the iteration.  */
+  if (was_visited
+      && bitmap_and_into (&ANTIC_IN (block)->values, &old->values))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "warning: intersecting with old ANTIC_IN "
+		 "shrinks the set\n");
+      /* Prune expressions not in the value set.  */
+      bitmap_iterator bi;
+      unsigned int i;
+      unsigned int to_clear = -1U;
+      FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (block), i, bi)
+	{
+	  if (to_clear != -1U)
+	    {
+	      bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
+	      to_clear = -1U;
+	    }
+	  pre_expr expr = expression_for_id (i);
+	  unsigned int value_id = get_expr_value_id (expr);
+	  if (!bitmap_bit_p (&ANTIC_IN (block)->values, value_id))
+	    to_clear = i;
+	}
+      if (to_clear != -1U)
+	bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
+    }
 
   if (!bitmap_set_equal (old, ANTIC_IN (block)))
     changed = true;
@@ -2243,45 +2261,44 @@
      VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever.  */
   else if (single_succ_p (block))
     {
-      basic_block succ = single_succ (block);
-      if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
-	phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
+      e = single_succ_edge (block);
+      if (!(e->flags & EDGE_DFS_BACK))
+	phi_translate_set (PA_OUT, PA_IN (e->dest), e);
     }
   /* If we have multiple successors, we take the union of all of
      them.  */
   else
     {
       size_t i;
-      basic_block bprime;
-
-      auto_vec<basic_block> worklist (EDGE_COUNT (block->succs));
+
+      auto_vec<edge> worklist (EDGE_COUNT (block->succs));
       FOR_EACH_EDGE (e, ei, block->succs)
 	{
 	  if (e->flags & EDGE_DFS_BACK)
 	    continue;
-	  worklist.quick_push (e->dest);
+	  worklist.quick_push (e);
 	}
       if (worklist.length () > 0)
 	{
-	  FOR_EACH_VEC_ELT (worklist, i, bprime)
+	  FOR_EACH_VEC_ELT (worklist, i, e)
 	    {
 	      unsigned int i;
 	      bitmap_iterator bi;
 
-	      FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
+	      FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (e->dest), i, bi)
 		bitmap_value_insert_into_set (PA_OUT,
 					      expression_for_id (i));
-	      if (!gimple_seq_empty_p (phi_nodes (bprime)))
+	      if (!gimple_seq_empty_p (phi_nodes (e->dest)))
 		{
 		  bitmap_set_t pa_in = bitmap_set_new ();
-		  phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
+		  phi_translate_set (pa_in, PA_IN (e->dest), e);
 		  FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
 		    bitmap_value_insert_into_set (PA_OUT,
 						  expression_for_id (i));
 		  bitmap_set_free (pa_in);
 		}
 	      else
-		FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
+		FOR_EACH_EXPR_ID_IN_SET (PA_IN (e->dest), i, bi)
 		  bitmap_value_insert_into_set (PA_OUT,
 						expression_for_id (i));
 	    }
@@ -2397,6 +2414,12 @@
       gcc_checking_assert (num_iterations < 500);
     }
 
+  /* We have to clean after the dataflow problem converged as cleaning
+     can cause non-convergence because it is based on expressions
+     rather than values.  */
+  FOR_EACH_BB_FN (block, cfun)
+    clean (ANTIC_IN (block));
+
   statistics_histogram_event (cfun, "compute_antic iterations",
 			      num_iterations);
 
@@ -2404,9 +2427,7 @@
     {
       /* For partial antic we ignore backedges and thus we do not need
          to perform any iteration when we process blocks in postorder.  */
-      int postorder_num
-	= pre_and_rev_post_order_compute (NULL, postorder.address (), false);
-      for (i = postorder_num - 1 ; i >= 0; i--)
+      for (i = postorder.length () - 1; i >= 0; i--)
 	{
 	  basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
 	  compute_partial_antic_aux (block,
@@ -2448,7 +2469,7 @@
 	if (TREE_CODE (baseop) == ADDR_EXPR
 	    && handled_component_p (TREE_OPERAND (baseop, 0)))
 	  {
-	    HOST_WIDE_INT off;
+	    poly_int64 off;
 	    tree base;
 	    base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
 						  &off);
@@ -2732,6 +2753,8 @@
        that value numbering saw through.  */
     case NAME:
       folded = PRE_EXPR_NAME (expr);
+      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (folded))
+	return NULL_TREE;
       if (useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
 	return folded;
       break;
@@ -2750,11 +2773,7 @@
 	  unsigned int operand = 1;
 	  vn_reference_op_t currop = &ref->operands[0];
 	  tree sc = NULL_TREE;
-	  tree fn;
-	  if (TREE_CODE (currop->op0) == FUNCTION_DECL)
-	    fn = currop->op0;
-	  else
-	    fn = find_or_generate_expression (block, currop->op0, stmts);
+	  tree fn  = find_or_generate_expression (block, currop->op0, stmts);
 	  if (!fn)
 	    return NULL_TREE;
 	  if (currop->op1)
@@ -2772,14 +2791,26 @@
 		return NULL_TREE;
 	      args.quick_push (arg);
 	    }
-	  gcall *call
-	    = gimple_build_call_vec ((TREE_CODE (fn) == FUNCTION_DECL
-				      ? build_fold_addr_expr (fn) : fn), args);
-	  gimple_call_set_with_bounds (call, currop->with_bounds);
+	  gcall *call = gimple_build_call_vec (fn, args);
 	  if (sc)
 	    gimple_call_set_chain (call, sc);
 	  tree forcedname = make_ssa_name (currop->type);
 	  gimple_call_set_lhs (call, forcedname);
+	  /* There's no CCP pass after PRE which would re-compute alignment
+	     information so make sure we re-materialize this here.  */
+	  if (gimple_call_builtin_p (call, BUILT_IN_ASSUME_ALIGNED)
+	      && args.length () - 2 <= 1
+	      && tree_fits_uhwi_p (args[1])
+	      && (args.length () != 3 || tree_fits_uhwi_p (args[2])))
+	    {
+	      unsigned HOST_WIDE_INT halign = tree_to_uhwi (args[1]);
+	      unsigned HOST_WIDE_INT hmisalign
+		= args.length () == 3 ? tree_to_uhwi (args[2]) : 0;
+	      if ((halign & (halign - 1)) == 0
+		  && (hmisalign & ~(halign - 1)) == 0)
+		set_ptr_info_alignment (get_ptr_info (forcedname),
+					halign, hmisalign);
+	    }
 	  gimple_set_vuse (call, BB_LIVE_VOP_ON_EXIT (block));
 	  gimple_seq_add_stmt_without_update (&forced_stmts, call);
 	  folded = forcedname;
@@ -2905,7 +2936,7 @@
 
 	  if (forcedname != folded)
 	    {
-	      VN_INFO_GET (forcedname)->valnum = forcedname;
+	      VN_INFO (forcedname)->valnum = forcedname;
 	      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);
@@ -2931,8 +2962,8 @@
      the expression may have been represented.  There is no harm in replacing
      here.  */
   value_id = get_expr_value_id (expr);
-  VN_INFO_GET (name)->value_id = value_id;
-  VN_INFO (name)->valnum = sccvn_valnum_from_value_id (value_id);
+  VN_INFO (name)->value_id = value_id;
+  VN_INFO (name)->valnum = vn_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);
@@ -3008,7 +3039,8 @@
       gcc_assert (!(pred->flags & EDGE_ABNORMAL));
       if (!gimple_seq_empty_p (stmts))
 	{
-	  gsi_insert_seq_on_edge (pred, stmts);
+	  basic_block new_bb = gsi_insert_seq_on_edge_immediate (pred, stmts);
+	  gcc_assert (! new_bb);
 	  insertions = true;
 	}
       if (!builtexpr)
@@ -3036,8 +3068,8 @@
   temp = make_temp_ssa_name (type, NULL, "prephitmp");
   phi = create_phi_node (temp, block);
 
-  VN_INFO_GET (temp)->value_id = val;
-  VN_INFO (temp)->valnum = sccvn_valnum_from_value_id (val);
+  VN_INFO (temp)->value_id = val;
+  VN_INFO (temp)->valnum = vn_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));
@@ -3190,8 +3222,7 @@
 	      gcc_assert (!(pred->flags & EDGE_FAKE));
 	      bprime = pred->src;
 	      /* We are looking at ANTIC_OUT of bprime.  */
-	      eprime = phi_translate (expr, ANTIC_IN (block), NULL,
-				      bprime, block);
+	      eprime = phi_translate (NULL, expr, ANTIC_IN (block), NULL, pred);
 
 	      /* eprime will generally only be NULL if the
 		 value of the expression, translated
@@ -3282,8 +3313,8 @@
 	      gimple_stmt_iterator gsi = gsi_after_labels (block);
 	      gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
 
-	      VN_INFO_GET (temp)->value_id = val;
-	      VN_INFO (temp)->valnum = sccvn_valnum_from_value_id (val);
+	      VN_INFO (temp)->value_id = val;
+	      VN_INFO (temp)->valnum = vn_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));
@@ -3346,9 +3377,8 @@
 	         and so not come across fake pred edges.  */
 	      gcc_assert (!(pred->flags & EDGE_FAKE));
 	      bprime = pred->src;
-	      eprime = phi_translate (expr, ANTIC_IN (block),
-				      PA_IN (block),
-				      bprime, block);
+	      eprime = phi_translate (NULL, expr, ANTIC_IN (block),
+				      PA_IN (block), pred);
 
 	      /* eprime will generally only be NULL if the
 		 value of the expression, translated
@@ -3725,6 +3755,7 @@
 
       /* Pick a block from the worklist.  */
       block = worklist[--sp];
+      vn_context_bb = block;
 
       /* Initially, the set of available values in BLOCK is that of
 	 its immediate dominator.  */
@@ -3796,7 +3827,7 @@
 	    BB_LIVE_VOP_ON_EXIT (block) = gimple_vdef (stmt);
 
 	  if (gimple_has_side_effects (stmt)
-	      || stmt_could_throw_p (stmt)
+	      || stmt_could_throw_p (cfun, stmt)
 	      || is_gimple_debug (stmt))
 	    continue;
 
@@ -3866,7 +3897,7 @@
 			continue;
 
 		      vn_nary_op_lookup_stmt (stmt, &nary);
-		      if (!nary)
+		      if (!nary || nary->predicated_values)
 			continue;
 
 		      /* If the NARY traps and there was a preceding
@@ -4026,68 +4057,11 @@
 	   son = next_dom_son (CDI_DOMINATORS, son))
 	worklist[sp++] = son;
     }
+  vn_context_bb = NULL;
 
   free (worklist);
 }
 
-/* Cheap DCE of a known set of possibly dead stmts.
-
-   Because we don't follow exactly the standard PRE algorithm, and decide not
-   to insert PHI nodes sometimes, and because value numbering of casts isn't
-   perfect, we sometimes end up inserting dead code.   This simple DCE-like
-   pass removes any insertions we made that weren't actually used.  */
-
-static void
-remove_dead_inserted_code (void)
-{
-  /* ???  Re-use inserted_exprs as worklist not only as initial set.
-     This may end up removing non-inserted code as well.  If we
-     keep inserted_exprs unchanged we could restrict new worklist
-     elements to members of inserted_exprs.  */
-  bitmap worklist = inserted_exprs;
-  while (! bitmap_empty_p (worklist))
-    {
-      /* Pop item.  */
-      unsigned i = bitmap_first_set_bit (worklist);
-      bitmap_clear_bit (worklist, i);
-
-      tree def = ssa_name (i);
-      /* Removed by somebody else or still in use.  */
-      if (! def || ! has_zero_uses (def))
-	continue;
-
-      gimple *t = SSA_NAME_DEF_STMT (def);
-      if (gimple_has_side_effects (t))
-	continue;
-
-      /* Add uses to the worklist.  */
-      ssa_op_iter iter;
-      use_operand_p use_p;
-      FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE)
-	{
-	  tree use = USE_FROM_PTR (use_p);
-	  if (TREE_CODE (use) == SSA_NAME
-	      && ! SSA_NAME_IS_DEFAULT_DEF (use))
-	    bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
-	}
-
-      /* Remove stmt.  */
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	{
-	  fprintf (dump_file, "Removing unnecessary insertion:");
-	  print_gimple_stmt (dump_file, t, 0);
-	}
-      gimple_stmt_iterator gsi = gsi_for_stmt (t);
-      if (gimple_code (t) == GIMPLE_PHI)
-	remove_phi_node (&gsi, true);
-      else
-	{
-	  gsi_remove (&gsi, true);
-	  release_defs (t);
-	}
-    }
-}
-
 
 /* Initialize data structures used by PRE.  */
 
@@ -4131,6 +4105,7 @@
 fini_pre ()
 {
   value_expressions.release ();
+  expressions.release ();
   BITMAP_FREE (inserted_exprs);
   bitmap_obstack_release (&grand_bitmap_obstack);
   bitmap_set_pool.release ();
@@ -4173,6 +4148,34 @@
 
 }; // class pass_pre
 
+/* Valueization hook for RPO VN when we are calling back to it
+   at ANTIC compute time.  */
+
+static tree
+pre_valueize (tree name)
+{
+  if (TREE_CODE (name) == SSA_NAME)
+    {
+      tree tem = VN_INFO (name)->valnum;
+      if (tem != VN_TOP && tem != name)
+	{
+	  if (TREE_CODE (tem) != SSA_NAME
+	      || SSA_NAME_IS_DEFAULT_DEF (tem))
+	    return tem;
+	  /* We create temporary SSA names for representatives that
+	     do not have a definition (yet) but are not default defs either
+	     assume they are fine to use.  */
+	  basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (tem));
+	  if (! def_bb
+	      || dominated_by_p (CDI_DOMINATORS, vn_context_bb, def_bb))
+	    return tem;
+	  /* ??? Now we could look for a leader.  Ideally we'd somehow
+	     expose RPO VN leaders and get rid of AVAIL_OUT as well...  */
+	}
+    }
+  return name;
+}
+
 unsigned int
 pass_pre::execute (function *fun)
 {
@@ -4181,26 +4184,27 @@
   do_partial_partial =
     flag_tree_partial_pre && optimize_function_for_speed_p (fun);
 
-  /* This has to happen before SCCVN runs because
+  /* This has to happen before VN runs because
      loop_optimizer_init may create new phis, etc.  */
   loop_optimizer_init (LOOPS_NORMAL);
   split_critical_edges ();
-
-  run_scc_vn (VN_WALK);
+  scev_initialize ();
+
+  run_rpo_vn (VN_WALK);
 
   init_pre ();
-  scev_initialize ();
-
-  /* Collect and value number expressions computed in each basic block.  */
-  compute_avail ();
+
+  vn_valueize = pre_valueize;
 
   /* Insert can get quite slow on an incredibly large number of basic
      blocks due to some quadratic behavior.  Until this behavior is
      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.  */
+     computing ANTIC, either, even though it's plenty fast nor do
+     we require AVAIL.  */
   if (n_basic_blocks_for_fn (fun) < 4000)
     {
+      compute_avail ();
       compute_antic ();
       insert ();
     }
@@ -4215,24 +4219,26 @@
      not keeping virtual operands up-to-date.  */
   gcc_assert (!need_ssa_update_p (fun));
 
-  /* Remove all the redundant expressions.  */
-  todo |= vn_eliminate (inserted_exprs);
-
   statistics_counter_event (fun, "Insertions", pre_stats.insertions);
   statistics_counter_event (fun, "PA inserted", pre_stats.pa_insert);
   statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
   statistics_counter_event (fun, "New PHIs", pre_stats.phis);
 
-  clear_expression_ids ();
+  todo |= eliminate_with_rpo_vn (inserted_exprs);
+
+  vn_valueize = NULL;
+
+  /* Because we don't follow exactly the standard PRE algorithm, and decide not
+     to insert PHI nodes sometimes, and because value numbering of casts isn't
+     perfect, we sometimes end up inserting dead code.   This simple DCE-like
+     pass removes any insertions we made that weren't actually used.  */
+  simple_dce_from_worklist (inserted_exprs);
+
+  fini_pre ();
 
   scev_finalize ();
-  remove_dead_inserted_code ();
-  fini_pre ();
   loop_optimizer_finalize ();
 
-  /* Restore SSA info before tail-merging as that resets it as well.  */
-  scc_vn_restore_ssa_info ();
-
   /* 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:
@@ -4242,7 +4248,7 @@
      - share the cfg cleanup with fini_pre.  */
   todo |= tail_merge_optimize (todo);
 
-  free_scc_vn ();
+  free_rpo_vn ();
 
   /* Tail merging invalidates the virtual SSA web, together with
      cfg-cleanup opportunities exposed by PRE this will wreck the