--- a/gcc/tree-phinodes.c	Sun Aug 21 07:07:55 2011 +0900
+++ b/gcc/tree-phinodes.c	Fri Oct 27 22:46:09 2017 +0900
@@ -1,6 +1,5 @@
 /* Generic routines for manipulating PHIs
-   Copyright (C) 2003, 2005, 2007, 2008, 2009, 2010
-   Free Software Foundation, Inc.
+   Copyright (C) 2003-2017 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -21,14 +20,13 @@
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
 #include "tree.h"
-#include "rtl.h"	/* FIXME: Only for ceil_log2, of all things...  */
-#include "ggc.h"
-#include "basic-block.h"
-#include "tree-flow.h"
-#include "diagnostic-core.h"
 #include "gimple.h"
+#include "ssa.h"
+#include "fold-const.h"
+#include "gimple-iterator.h"
+#include "tree-ssa.h"
 
 /* Rewriting a function into SSA form can create a huge number of PHIs
    many of which may be thrown away shortly after their creation if jumps
@@ -44,14 +42,6 @@
    garbage collector.  Similar results have been seen on a wider variety
    of tests (such as the compiler itself).
 
-   Right now we maintain our free list on a per-function basis.  It may
-   or may not make sense to maintain the free list for the duration of
-   a compilation unit.
-
-   We could also use a zone allocator for these objects since they have
-   a very well defined lifetime.  If someone wants to experiment with that
-   this is the place to try it.
-
    PHI nodes have different sizes, so we can't have a single list of all
    the PHI nodes as it would be too expensive to walk down that list to
    find a PHI of a suitable size.
@@ -77,61 +67,33 @@
    the -2 on all the calculations below.  */
 
 #define NUM_BUCKETS 10
-static GTY ((deletable (""))) VEC(gimple,gc) *free_phinodes[NUM_BUCKETS - 2];
+static GTY ((deletable (""))) vec<gimple *, va_gc> *free_phinodes[NUM_BUCKETS - 2];
 static unsigned long free_phinode_count;
 
 static int ideal_phi_node_len (int);
 
-#ifdef GATHER_STATISTICS
 unsigned int phi_nodes_reused;
 unsigned int phi_nodes_created;
-#endif
-
-/* Initialize management of PHIs.  */
-
-void
-init_phinodes (void)
-{
-  int i;
-
-  for (i = 0; i < NUM_BUCKETS - 2; i++)
-    free_phinodes[i] = NULL;
-  free_phinode_count = 0;
-}
-
-/* Finalize management of PHIs.  */
-
-void
-fini_phinodes (void)
-{
-  int i;
-
-  for (i = 0; i < NUM_BUCKETS - 2; i++)
-    free_phinodes[i] = NULL;
-  free_phinode_count = 0;
-}
 
 /* Dump some simple statistics regarding the re-use of PHI nodes.  */
 
-#ifdef GATHER_STATISTICS
 void
 phinodes_print_statistics (void)
 {
   fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created);
   fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused);
 }
-#endif
 
 /* Allocate a PHI node with at least LEN arguments.  If the free list
    happens to contain a PHI node with LEN arguments or more, return
    that one.  */
 
-static inline gimple
+static inline gphi *
 allocate_phi_node (size_t len)
 {
-  gimple phi;
+  gphi *phi;
   size_t bucket = NUM_BUCKETS - 2;
-  size_t size = sizeof (struct gimple_statement_phi)
+  size_t size = sizeof (struct gphi)
 	        + (len - 1) * sizeof (struct phi_arg_d);
 
   if (free_phinode_count)
@@ -141,28 +103,25 @@
 
   /* If our free list has an element, then use it.  */
   if (bucket < NUM_BUCKETS - 2
-      && gimple_phi_capacity (VEC_index (gimple, free_phinodes[bucket], 0))
-	 >= len)
+      && gimple_phi_capacity ((*free_phinodes[bucket])[0]) >= len)
     {
       free_phinode_count--;
-      phi = VEC_pop (gimple, free_phinodes[bucket]);
-      if (VEC_empty (gimple, free_phinodes[bucket]))
-	VEC_free (gimple, gc, free_phinodes[bucket]);
-#ifdef GATHER_STATISTICS
-      phi_nodes_reused++;
-#endif
+      phi = as_a <gphi *> (free_phinodes[bucket]->pop ());
+      if (free_phinodes[bucket]->is_empty ())
+	vec_free (free_phinodes[bucket]);
+      if (GATHER_STATISTICS)
+	phi_nodes_reused++;
     }
   else
     {
-      phi = ggc_alloc_gimple_statement_d (size);
-#ifdef GATHER_STATISTICS
-      phi_nodes_created++;
+      phi = static_cast <gphi *> (ggc_internal_alloc (size));
+      if (GATHER_STATISTICS)
 	{
 	  enum gimple_alloc_kind kind = gimple_alloc_kind (GIMPLE_PHI);
-          gimple_alloc_counts[(int) kind]++;
-          gimple_alloc_sizes[(int) kind] += size;
+	  phi_nodes_created++;
+	  gimple_alloc_counts[(int) kind]++;
+	  gimple_alloc_sizes[(int) kind] += size;
 	}
-#endif
     }
 
   return phi;
@@ -189,7 +148,7 @@
     len = 2;
 
   /* Compute the number of bytes of the original request.  */
-  size = sizeof (struct gimple_statement_phi)
+  size = sizeof (struct gphi)
 	 + (len - 1) * sizeof (struct phi_arg_d);
 
   /* Round it up to the next power of two.  */
@@ -204,10 +163,10 @@
 
 /* Return a PHI node with LEN argument slots for variable VAR.  */
 
-gimple
+static gphi *
 make_phi_node (tree var, int len)
 {
-  gimple phi;
+  gphi *phi;
   int capacity, i;
 
   capacity = ideal_phi_node_len (len);
@@ -217,18 +176,21 @@
   /* We need to clear the entire PHI node, including the argument
      portion, because we represent a "missing PHI argument" by placing
      NULL_TREE in PHI_ARG_DEF.  */
-  memset (phi, 0, (sizeof (struct gimple_statement_phi)
+  memset (phi, 0, (sizeof (struct gphi)
 		   - sizeof (struct phi_arg_d)
 		   + sizeof (struct phi_arg_d) * len));
-  phi->gsbase.code = GIMPLE_PHI;
-  phi->gimple_phi.nargs = len;
-  phi->gimple_phi.capacity = capacity;
-  if (TREE_CODE (var) == SSA_NAME)
+  phi->code = GIMPLE_PHI;
+  gimple_init_singleton (phi);
+  phi->nargs = len;
+  phi->capacity = capacity;
+  if (!var)
+    ;
+  else if (TREE_CODE (var) == SSA_NAME)
     gimple_phi_set_result (phi, var);
   else
     gimple_phi_set_result (phi, make_ssa_name (var, phi));
 
-  for (i = 0; i < capacity; i++)
+  for (i = 0; i < len; i++)
     {
       use_operand_p  imm;
 
@@ -245,8 +207,8 @@
 
 /* We no longer need PHI, release it so that it may be reused.  */
 
-void
-release_phi_node (gimple phi)
+static void
+release_phi_node (gimple *phi)
 {
   size_t bucket;
   size_t len = gimple_phi_capacity (phi);
@@ -261,7 +223,7 @@
 
   bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
   bucket -= 2;
-  VEC_safe_push (gimple, gc, free_phinodes[bucket], phi);
+  vec_safe_push (free_phinodes[bucket], phi);
   free_phinode_count++;
 }
 
@@ -269,48 +231,40 @@
 /* Resize an existing PHI node.  The only way is up.  Return the
    possibly relocated phi.  */
 
-static void
-resize_phi_node (gimple *phi, size_t len)
+static gphi *
+resize_phi_node (gphi *phi, size_t len)
 {
   size_t old_size, i;
-  gimple new_phi;
+  gphi *new_phi;
 
-  gcc_assert (len > gimple_phi_capacity (*phi));
+  gcc_assert (len > gimple_phi_capacity (phi));
 
   /* The garbage collector will not look at the PHI node beyond the
      first PHI_NUM_ARGS elements.  Therefore, all we have to copy is a
      portion of the PHI node currently in use.  */
-  old_size = sizeof (struct gimple_statement_phi)
-	     + (gimple_phi_num_args (*phi) - 1) * sizeof (struct phi_arg_d);
+  old_size = sizeof (struct gphi)
+	     + (gimple_phi_num_args (phi) - 1) * sizeof (struct phi_arg_d);
 
   new_phi = allocate_phi_node (len);
 
-  memcpy (new_phi, *phi, old_size);
+  memcpy (new_phi, phi, old_size);
+  memset ((char *)new_phi + old_size, 0,
+	  (sizeof (struct gphi)
+	   - sizeof (struct phi_arg_d)
+	   + sizeof (struct phi_arg_d) * len) - old_size);
 
   for (i = 0; i < gimple_phi_num_args (new_phi); i++)
     {
       use_operand_p imm, old_imm;
       imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
-      old_imm = gimple_phi_arg_imm_use_ptr (*phi, i);
+      old_imm = gimple_phi_arg_imm_use_ptr (phi, i);
       imm->use = gimple_phi_arg_def_ptr (new_phi, i);
       relink_imm_use_stmt (imm, old_imm, new_phi);
     }
 
-  new_phi->gimple_phi.capacity = len;
-
-  for (i = gimple_phi_num_args (new_phi); i < len; i++)
-    {
-      use_operand_p imm;
+  new_phi->capacity = len;
 
-      gimple_phi_arg_set_location (new_phi, i, UNKNOWN_LOCATION);
-      imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
-      imm->use = gimple_phi_arg_def_ptr (new_phi, i);
-      imm->prev = NULL;
-      imm->next = NULL;
-      imm->loc.stmt = new_phi;
-    }
-
-  *phi = new_phi;
+  return new_phi;
 }
 
 /* Reserve PHI arguments for a new edge to basic block BB.  */
@@ -320,24 +274,26 @@
 {
   size_t len = EDGE_COUNT (bb->preds);
   size_t cap = ideal_phi_node_len (len + 4);
-  gimple_stmt_iterator gsi;
+  gphi_iterator gsi;
 
   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     {
-      gimple *loc = gsi_stmt_ptr (&gsi);
+      gphi *stmt = gsi.phi ();
 
-      if (len > gimple_phi_capacity (*loc))
+      if (len > gimple_phi_capacity (stmt))
 	{
-	  gimple old_phi = *loc;
-
-	  resize_phi_node (loc, cap);
+	  gphi *new_phi = resize_phi_node (stmt, cap);
 
 	  /* The result of the PHI is defined by this PHI node.  */
-	  SSA_NAME_DEF_STMT (gimple_phi_result (*loc)) = *loc;
+	  SSA_NAME_DEF_STMT (gimple_phi_result (new_phi)) = new_phi;
+	  gsi_set_stmt (&gsi, new_phi);
 
-	  release_phi_node (old_phi);
+	  release_phi_node (stmt);
+	  stmt = new_phi;
 	}
 
+      stmt->nargs++;
+
       /* We represent a "missing PHI argument" by placing NULL_TREE in
 	 the corresponding slot.  If PHI arguments were added
 	 immediately after an edge is created, this zeroing would not
@@ -345,24 +301,30 @@
 	 example, the loop optimizer duplicates several basic blocks,
 	 redirects edges, and then fixes up PHI arguments later in
 	 batch.  */
-      SET_PHI_ARG_DEF (*loc, len - 1, NULL_TREE);
-
-      (*loc)->gimple_phi.nargs++;
+      use_operand_p imm = gimple_phi_arg_imm_use_ptr (stmt, len - 1);
+      imm->use = gimple_phi_arg_def_ptr (stmt, len - 1);
+      imm->prev = NULL;
+      imm->next = NULL;
+      imm->loc.stmt = stmt;
+      SET_PHI_ARG_DEF (stmt, len - 1, NULL_TREE);
+      gimple_phi_arg_set_location (stmt, len - 1, UNKNOWN_LOCATION);
     }
 }
 
 /* Adds PHI to BB.  */
 
 void
-add_phi_node_to_bb (gimple phi, basic_block bb)
+add_phi_node_to_bb (gphi *phi, basic_block bb)
 {
-  gimple_stmt_iterator gsi;
+  gimple_seq seq = phi_nodes (bb);
   /* Add the new PHI node to the list of PHI nodes for block BB.  */
-  if (phi_nodes (bb) == NULL)
-    set_phi_nodes (bb, gimple_seq_alloc ());
-
-  gsi = gsi_last (phi_nodes (bb));
-  gsi_insert_after (&gsi, phi, GSI_NEW_STMT);
+  if (seq == NULL)
+    set_phi_nodes (bb, gimple_seq_alloc_with_stmt (phi));
+  else
+    {
+      gimple_seq_add_stmt (&seq, phi);
+      gcc_assert (seq == phi_nodes (bb));
+    }
 
   /* Associate BB to the PHI node.  */
   gimple_set_bb (phi, bb);
@@ -371,10 +333,10 @@
 
 /* Create a new PHI node for variable VAR at basic block BB.  */
 
-gimple
+gphi *
 create_phi_node (tree var, basic_block bb)
 {
-  gimple phi = make_phi_node (var, EDGE_COUNT (bb->preds));
+  gphi *phi = make_phi_node (var, EDGE_COUNT (bb->preds));
 
   add_phi_node_to_bb (phi, bb);
   return phi;
@@ -388,7 +350,7 @@
    PHI points to the reallocated phi node when we return.  */
 
 void
-add_phi_arg (gimple phi, tree def, edge e, source_location locus)
+add_phi_arg (gphi *phi, tree def, edge e, source_location locus)
 {
   basic_block bb = e->dest;
 
@@ -421,7 +383,7 @@
    is consistent with how we remove an edge from the edge vector.  */
 
 static void
-remove_phi_arg_num (gimple phi, int i)
+remove_phi_arg_num (gphi *phi, int i)
 {
   int num_elem = gimple_phi_num_args (phi);
 
@@ -448,7 +410,7 @@
   /* Shrink the vector and return.  Note that we do not have to clear
      PHI_ARG_DEF because the garbage collector will not look at those
      elements beyond the first PHI_NUM_ARGS elements of the array.  */
-  phi->gimple_phi.nargs--;
+  phi->nargs--;
 }
 
 
@@ -457,10 +419,11 @@
 void
 remove_phi_args (edge e)
 {
-  gimple_stmt_iterator gsi;
+  gphi_iterator gsi;
 
   for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
-    remove_phi_arg_num (gsi_stmt (gsi), e->dest_idx);
+    remove_phi_arg_num (gsi.phi (),
+			e->dest_idx);
 }
 
 
@@ -472,7 +435,7 @@
 void
 remove_phi_node (gimple_stmt_iterator *gsi, bool release_lhs_p)
 {
-  gimple phi = gsi_stmt (*gsi);
+  gimple *phi = gsi_stmt (*gsi);
 
   if (release_lhs_p)
     insert_debug_temps_for_defs (gsi);
@@ -491,7 +454,7 @@
 void
 remove_phi_nodes (basic_block bb)
 {
-  gimple_stmt_iterator gsi;
+  gphi_iterator gsi;
 
   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
     remove_phi_node (&gsi, true);
@@ -499,4 +462,54 @@
   set_phi_nodes (bb, NULL);
 }
 
+/* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
+   NULL.  */
+
+tree
+degenerate_phi_result (gphi *phi)
+{
+  tree lhs = gimple_phi_result (phi);
+  tree val = NULL;
+  size_t i;
+
+  /* Ignoring arguments which are the same as LHS, if all the remaining
+     arguments are the same, then the PHI is a degenerate and has the
+     value of that common argument.  */
+  for (i = 0; i < gimple_phi_num_args (phi); i++)
+    {
+      tree arg = gimple_phi_arg_def (phi, i);
+
+      if (arg == lhs)
+	continue;
+      else if (!arg)
+	break;
+      else if (!val)
+	val = arg;
+      else if (arg == val)
+	continue;
+      /* We bring in some of operand_equal_p not only to speed things
+	 up, but also to avoid crashing when dereferencing the type of
+	 a released SSA name.  */
+      else if (TREE_CODE (val) != TREE_CODE (arg)
+	       || TREE_CODE (val) == SSA_NAME
+	       || !operand_equal_p (arg, val, 0))
+	break;
+    }
+  return (i == gimple_phi_num_args (phi) ? val : NULL);
+}
+
+/* Set PHI nodes of a basic block BB to SEQ.  */
+
+void
+set_phi_nodes (basic_block bb, gimple_seq seq)
+{
+  gimple_stmt_iterator i;
+
+  gcc_checking_assert (!(bb->flags & BB_RTL));
+  bb->il.gimple.phi_nodes = seq;
+  if (seq)
+    for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
+      gimple_set_bb (gsi_stmt (i), bb);
+}
+
 #include "gt-tree-phinodes.h"