[ tree-ssa ] Speed up PHI insertion and SSA rewriting

[law at redhat dot com]

With the generic dominator walker basically out of the way, I decided to
take a brief stab at further improvements to compile-time performance for 
the SSA path for ugly code like interpret.cc from libjava and similar code
(CFGs with insane connectivity).

Not surprisingly I did find some low-hanging fruit.

First, in graphs with insane connectivity, counting the number of incoming
edges for a block gets rather expensive.  Especially if you do it more
than once.  If you do it every time you create a new PHI node *and* once
for every block in the dfs of every object it gets insanely expensive.
Fixing by caching the in-degree in the block's annotation cut PHI insertion
time in half.  


Second, doing an sbitmap test for every block's successor's phi nodes ie

  for each basic block
    for each successor
      for each phi node in the successor
        bitmap test

Gets really expensive when you have 800 blocks with 50000 edges and lots
of phi nodes.  Luckily the bitmap test is invariant per phi node.  ie,
instead of doing a bitmap test, we have the phi node itself carry the
information we need.  That cut about 20% off the ssa rewriting time.


Now the change that really caught me by surprise (and which I've spent most
of the yesterday analyzing) is that parallel global life computation is
a losing proposition these days.

Now if we go back many months we had a testcase (20001226-1.c) which spent
~80 seconds in phi node insertion, much of that doing global life analysis
on its thousands of variables in thousands of blocks.

In response I put together some code which allowed us to do global life
analysis on blocks of variables in parallel.  That cut the phi insertion time
from 80 seconds to 20 seconds.  Good stuff and I never gave it another thought.

Fast forward to the present time.  I'd never bothered to really tune that
code to determine how many variables we should compute global life for in
parallel.  So I figured playing with that might prove interesting.  I never
expected to find that if I throttled it to compute life analysis one variable
at a time that it'd actually be faster!

So I pulled out the original testcase which led me to write the parallel
life code.  Hmmm, phi node insertion doesn't even show up in the time
report anymore -- using either serial or parallel life computation.  Odd.

Digging a little further, what's happened is we have drastically
reduced the number of variables by using a formal temporary table.  Instead
of something like 32k variables, we've got a few hundred.    OK, so that
might explain why this test no longer has significant phi insertion times,
but it still doesn't explain why parallel is slower than serial.

Digging further, the variables in that testcase (before the formal temporary
table) tended to have amazingly similar life characteristics (no surprise
given how the testcase is written).   The net result is that each iteration
through the propagation loop did a significant amount of useful work for
a number of variables and we got nice performance improvements.  ie, we'd
tend to do useful work for almost every variable we were trying to handle
in parallel.

Now if we look at interpret.cc we get the exact opposite behavior -- each
iteration of the loop is doing a lot of useless work since a number of the
variables aren't interesting for the current block.  Andrew's recent change
mitigated that to some extent, but the more I look at this code the more
I'm convinced that the only time we want to compute life information for
variables in parallel is when they have similar lifetime characteristics.

The last tidbit of information that's worth mentioning is that this code
was compile-time neutral across larger codebases -- ie it didn't provide a
win in general.

With all that information I've decided to rip that code out and return to
the per-variable lifetime computation.  Which cut another 25% off the 
PHI insertion time for interpret.cc and (I've just verified) is compile-time
neutral across a more normal codebase.

	* tree-dfa.c (create_phi_node):  Clear PHI_REWRITTEN on all new PHIs
	(remove_all_phi_nodes_for): Set PHI_REWRITTEN on any PHIs which are
	not removed.
	* tree-ssa.c (rewrite_add_phi_arguments): Check the PHI node itself
	to see if it has already been rewritten.
	* tree.h (PHI_REWRITTEN): New accessor macro.
	(struct phi_node): New field rewritten.
	
	* tree-flow.h (struct bb_ann_d): New field num_preds.
	* tree-dfa.c (create_phi_node): Get the number of predecessors from
	the block's annotation.
	* tree-ssa.c (rewrite_into_ssa): Compute number of preds for each
	block and store it into the block's annotation.
	(insert_phi_nodes_for): Get the number of preds for each block
	from the block's annotation.

	* tree-ssa.c: Remove parallel lifetime analysis code from April 2003.
	(def_blocks_d): Remove PHI_INSERTION_POINTS field.
	(compute_global_livein): Accept livein/def bitmaps to use for
	life analyis rather than a varray of variables.  Callers updated.
	Rewritten to compute life information for one variable at a
	time instead of several variables at once.
	(insert_phis_for_deferred_variables): Remove.
	(insert_phi_nodes_for): Lose varray argument.  Callers updated.
	No longer mess with deferring PHI insertions for variables.
	(insert_phi_nodes): No longer need to deal with deferred variables.
	Kill everything related to them.


Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.171
diff -c -3 -p -r1.1.4.171 tree-dfa.c
*** tree-dfa.c	13 Oct 2003 15:35:56 -0000	1.1.4.171
--- tree-dfa.c	15 Oct 2003 22:26:18 -0000
*************** create_phi_node (tree var, basic_block b
*** 945,957 ****
  {
    tree phi;
    bb_ann_t ann;
-   int len;
-   edge e;
  
!   for (len = 0, e = bb->pred; e; e = e->pred_next)
!     len++;
  
!   phi = make_phi_node (var, len);
  
    /* Add the new PHI node to the list of PHI nodes for block BB.  */
    ann = bb_ann (bb);
--- 945,956 ----
  {
    tree phi;
    bb_ann_t ann;
  
!   phi = make_phi_node (var, bb_ann (bb)->num_preds);
  
!   /* This is a new phi node, so note that is has not yet been
!      rewritten. */
!   PHI_REWRITTEN (phi) = 0;
  
    /* Add the new PHI node to the list of PHI nodes for block BB.  */
    ann = bb_ann (bb);
*************** remove_all_phi_nodes_for (sbitmap vars)
*** 1123,1128 ****
--- 1122,1132 ----
  	  /* Only add PHI nodes for variables not in VARS.  */
  	  if (!TEST_BIT (vars, var_ann (var)->uid))
  	    {
+ 	      /* If we're not removing this PHI node, then it must have
+ 		 been rewritten by a previous call into the SSA rewriter.
+ 		 Note that fact in PHI_REWRITTEN.  */
+ 	      PHI_REWRITTEN (phi) = 1;
+ 
  	      if (new_phi_list == NULL_TREE)
  		new_phi_list = last_phi = phi;
  	      else
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.128
diff -c -3 -p -r1.1.4.128 tree-flow.h
*** tree-flow.h	14 Oct 2003 17:31:34 -0000	1.1.4.128
--- tree-flow.h	15 Oct 2003 22:17:46 -0000
*************** struct bb_ann_d
*** 306,311 ****
--- 306,315 ----
    /* EUSE/ELEFT/EKILL/EPHI nodes created in this block.  */
    varray_type erefs;
  
+   /* Number of predecessors for this block.  This is only valid during
+      SSA rewriting.  It is not maintained after conversion into SSA form.  */
+   int num_preds;
+ 
    /* Set of blocks immediately dominated by this node.  */
    bitmap dom_children;
  };
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.135
diff -c -3 -p -r1.1.4.135 tree-ssa.c
*** tree-ssa.c	15 Oct 2003 18:22:58 -0000	1.1.4.135
--- tree-ssa.c	15 Oct 2003 22:17:49 -0000
*************** struct GTY(()) def_blocks_d
*** 83,89 ****
    tree var;
    bitmap def_blocks;
    bitmap livein_blocks;
-   bitmap phi_insertion_points;
  };
  
  /* Hash table to store the current reaching definition for every variable in
--- 83,88 ----
*************** static void rewrite_add_phi_arguments (s
*** 149,164 ****
  				       basic_block, tree);
  static void delete_tree_ssa (tree);
  static void mark_def_sites (sbitmap);
! static void compute_global_livein (varray_type);
  static void set_def_block (tree, basic_block);
  static void set_livein_block (tree, basic_block);
  static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
  static void insert_phi_nodes (bitmap *, sbitmap);
- static void insert_phis_for_deferred_variables (varray_type);
  static void rewrite_stmt (block_stmt_iterator, varray_type *);
  static inline void rewrite_operand (tree *);
  static void register_new_def (tree, tree, varray_type *);
! static void insert_phi_nodes_for (tree, bitmap *, varray_type);
  static tree remove_annotations_r (tree *, int *, void *);
  static tree get_reaching_def (tree);
  static tree get_value_for (tree, htab_t);
--- 148,162 ----
  				       basic_block, tree);
  static void delete_tree_ssa (tree);
  static void mark_def_sites (sbitmap);
! static void compute_global_livein (bitmap, bitmap);
  static void set_def_block (tree, basic_block);
  static void set_livein_block (tree, basic_block);
  static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
  static void insert_phi_nodes (bitmap *, sbitmap);
  static void rewrite_stmt (block_stmt_iterator, varray_type *);
  static inline void rewrite_operand (tree *);
  static void register_new_def (tree, tree, varray_type *);
! static void insert_phi_nodes_for (tree, bitmap *);
  static tree remove_annotations_r (tree *, int *, void *);
  static tree get_reaching_def (tree);
  static tree get_value_for (tree, htab_t);
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 323,332 ****
    globals = sbitmap_alloc (num_referenced_vars);
    sbitmap_zero (globals);
  
!   /* Initialize dominance frontier and immediate dominator bitmaps.  */
    dfs = (bitmap *) xmalloc (n_basic_blocks * sizeof (bitmap *));
    FOR_EACH_BB (bb)
!     dfs[bb->index] = BITMAP_XMALLOC ();
  
    /* Compute immediate dominators, dominance frontiers and the dominator
       tree.  FIXME: DFS and dominator tree information should be cached.
--- 321,342 ----
    globals = sbitmap_alloc (num_referenced_vars);
    sbitmap_zero (globals);
  
!   /* Initialize dominance frontier and immediate dominator bitmaps. 
! 
!      Also count the number of predecessors for each block.  Doing so
!      can save significant time during PHI insertion for large graphs.  */
    dfs = (bitmap *) xmalloc (n_basic_blocks * sizeof (bitmap *));
    FOR_EACH_BB (bb)
!     {
!       edge e;
!       int count = 0;
! 
!       for (e = bb->pred; e; e = e->pred_next)
! 	count++;
! 
!       bb_ann (bb)->num_preds = count;
!       dfs[bb->index] = BITMAP_XMALLOC ();
!     }
  
    /* Compute immediate dominators, dominance frontiers and the dominator
       tree.  FIXME: DFS and dominator tree information should be cached.
*************** build_dominator_tree (dominance_info ido
*** 410,455 ****
      }
  }
  
! /* Compute global livein information for one or more objects.
! 
!    DEF_BLOCKS is a varray of struct def_blocks_d pointers, one for
!    each object of interest.
! 
!    Each of the struct def_blocks_d entries points to a set of
!    blocks where the variable is locally live at the start of
!    a block and the set of blocks where the variable is defined.
  
     Note: This routine augments the existing local livein information
!    to include global livein.  Ie, it modifies the underlying LIVEIN
!    bitmap for each object. 
! 
!    We can get great speedups by performing life analysis for several
!    objects in parallel, but this design also allows for per-variable
!    life computation by having a varray with a single element.  */
  
  static void
! compute_global_livein (varray_type def_maps)
  {
    basic_block bb, *worklist, *tos;
-   bitmap in_worklist = BITMAP_XMALLOC ();
-   struct def_blocks_d *def_map;
-   unsigned int n_elements = VARRAY_ACTIVE_SIZE (def_maps);
-   unsigned int i;
  
    tos = worklist
      = (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
  
!   /* Build a bitmap of all the blocks which belong in the worklist.  */
!   for (i = 0; i < n_elements; i++)
!     {
!       def_map = VARRAY_GENERIC_PTR (def_maps, i);
!       bitmap_a_or_b (in_worklist, in_worklist, def_map->livein_blocks);
!     }
!     
!   /* Initialize the worklist itself.  */
    FOR_EACH_BB (bb)
      {
!       if (bitmap_bit_p (in_worklist, bb->index))
  	*tos++ = bb;
      }
  
--- 420,445 ----
      }
  }
  
! /* Compute global livein information given the set of blockx where
!    an object is locally live at the start of the block (LIVEIN)
!    and the set of blocks where the object is defined (DEF_BLOCKS).
  
     Note: This routine augments the existing local livein information
!    to include global livein.  Ie, it modifies the underlying bitmap
!    for LIVEIN.  */
  
  static void
! compute_global_livein (bitmap livein, bitmap def_blocks)
  {
    basic_block bb, *worklist, *tos;
  
    tos = worklist
      = (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
  
!   /* Initialize the worklist.  */
    FOR_EACH_BB (bb)
      {
!       if (bitmap_bit_p (livein, bb->index))
  	*tos++ = bb;
      }
  
*************** compute_global_livein (varray_type def_m
*** 460,505 ****
  
        /* Pull a block off the worklist.  */
        bb = *--tos;
-       bitmap_clear_bit (in_worklist, bb->index);
  
!       for (i = 0; i < n_elements; i++)
  	{
! 	  def_map = VARRAY_GENERIC_PTR (def_maps, i);
  
! 	  /* If its not live into this block, don't look at it any further. */
! 	  if (!bitmap_bit_p (def_map->livein_blocks, bb->index))
! 	    continue;
! 
! 	  /* For each predecessor block.  */
! 	  for (e = bb->pred; e; e = e->pred_next)
  	    {
! 	      basic_block pred = e->src;
! 	      int pred_index = pred->index;
! 
! 	      /* None of this is necessary for the entry block.  */
! 	      if (pred != ENTRY_BLOCK_PTR)
! 		{
! 		  /* Update livein_blocks for each element in the 
! 		     def_maps vector.  */
! 		    if (! bitmap_bit_p (def_map->livein_blocks, pred_index)
! 			&& ! bitmap_bit_p (def_map->def_blocks, pred_index))
! 		      {
! 			bitmap_set_bit (def_map->livein_blocks, pred_index);
! 
! 			/* If this block is not in the worklist, then add
! 			   it to the worklist.  */
! 			if (! bitmap_bit_p (in_worklist, pred_index))
! 			  {
! 			    *tos++ = pred;
! 			    bitmap_set_bit (in_worklist, pred_index);
! 			  }
! 		      }
! 	        }
  	    }
  	}
      }
    free (worklist);
-   BITMAP_XFREE (in_worklist);
  }
  
  /* Collect definition sites for every variable in the function.
--- 450,474 ----
  
        /* Pull a block off the worklist.  */
        bb = *--tos;
  
!       /* For each predecessor block.  */
!       for (e = bb->pred; e; e = e->pred_next)
  	{
! 	  basic_block pred = e->src;
! 	  int pred_index = pred->index;
  
! 	  /* None of this is necessary for the entry block.  */
! 	  if (pred != ENTRY_BLOCK_PTR
! 	      && ! bitmap_bit_p (livein, pred_index)
! 	      && ! bitmap_bit_p (def_blocks, pred_index))
  	    {
! 	      *tos++ = pred;
! 	      bitmap_set_bit (livein, pred_index);
  	    }
  	}
      }
+ 
    free (worklist);
  }
  
  /* Collect definition sites for every variable in the function.
*************** static void
*** 696,707 ****
  insert_phi_nodes (bitmap *dfs, sbitmap globals)
  {
    size_t i;
-   varray_type def_maps;
  
    timevar_push (TV_TREE_INSERT_PHI_NODES);
  
-   VARRAY_GENERIC_PTR_INIT (def_maps, HOST_BITS_PER_WIDE_INT, "def_maps");
- 
    /* Array WORK_STACK is a stack of CFG blocks.  Each block that contains
       an assignment or PHI node will be pushed to this stack.  */
    VARRAY_BB_INIT (work_stack, last_basic_block, "work_stack");
--- 665,673 ----
*************** insert_phi_nodes (bitmap *dfs, sbitmap g
*** 715,733 ****
        tree var = referenced_var (i);
        var_ann_t ann = var_ann (var);
  
-       /* If we have queued enough variables, then drain the queue.  */
-       if (VARRAY_ACTIVE_SIZE (def_maps) == HOST_BITS_PER_WIDE_INT)
- 	insert_phis_for_deferred_variables (def_maps);
- 
        if (TEST_BIT (globals, ann->uid))
! 	insert_phi_nodes_for (var, dfs, def_maps);
      });
  
-   if (VARRAY_ACTIVE_SIZE (def_maps) != 0)
-     insert_phis_for_deferred_variables (def_maps);
- 
    work_stack = NULL;
-   def_maps = NULL;
    timevar_pop (TV_TREE_INSERT_PHI_NODES);
  }
  
--- 681,691 ----
        tree var = referenced_var (i);
        var_ann_t ann = var_ann (var);
  
        if (TEST_BIT (globals, ann->uid))
! 	insert_phi_nodes_for (var, dfs);
      });
  
    work_stack = NULL;
    timevar_pop (TV_TREE_INSERT_PHI_NODES);
  }
  
*************** rewrite_add_phi_arguments (struct dom_wa
*** 837,845 ****
  	{
  	  tree currdef;
  
! 	  /* Ignore PHI nodes that have already been renamed.  */
! 	  if (!TEST_BIT (vars_to_rename,
! 			 var_ann (SSA_NAME_VAR (PHI_RESULT (phi)))->uid))
  	    continue;
  
  	  currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
--- 795,803 ----
  	{
  	  tree currdef;
  
! 	  /* If this PHI node has already been rewritten, then there is
! 	     nothing to do.  */
! 	  if (PHI_REWRITTEN (phi))
  	    continue;
  
  	  currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
*************** htab_statistics (FILE *file, htab_t htab
*** 1905,1962 ****
  		  Helpers for the main SSA building functions
  ---------------------------------------------------------------------------*/
  
- /* When using fully pruned SSA form we need to compute global life
-    information for each object using fully pruned SSA form.
- 
-    For large CFGs with many variable performing a per-object global
-    life analysis can be extremely expensive.  So instead we queue
-    objects so that we can compute life information for several in
-    parallel.
- 
-    This routine drains the queue of deferred objects and inserts
-    PHI nodes for those objects.   The queue of objects is DEF_MAPS,
-    a virtual array of struct def_blocks_d pointers, one for each
-    object.  */
- 
- static void
- insert_phis_for_deferred_variables (varray_type def_maps)
- {
-   unsigned int i;
-   unsigned int num_elements;
- 
-   /* Compute global life information for the variables we have deferred.  */
-   compute_global_livein (def_maps);
- 
-   /* Now insert PHIs for each of the deferred variables.  */
-   num_elements = VARRAY_ACTIVE_SIZE (def_maps);
-   for (i = 0; i < num_elements; i++)
-     {
-       /* Pop an element off the list and restore enough state
- 	 so that we can insert its PHI nodes.  */
-       struct def_blocks_d *def_map = VARRAY_GENERIC_PTR (def_maps, i);
-       tree var = def_map->var;
-       bitmap phi_insertion_points = def_map->phi_insertion_points;
-       unsigned bb_index;
- 
-       VARRAY_POP (def_maps);
-       EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index,
- 	{
- 	  if (bitmap_bit_p (def_map->livein_blocks, bb_index))
- 	    create_phi_node (var, BASIC_BLOCK (bb_index));
- 	});
- 
-       def_map->phi_insertion_points = NULL;
-     }
- }
- 
  /* Insert PHI nodes for variable VAR.  */
  
  static void
! insert_phi_nodes_for (tree var, bitmap *dfs, varray_type def_maps)
  {
    struct def_blocks_d *def_map;
    bitmap phi_insertion_points;
    unsigned phi_vector_lengths = 0;
    int bb_index;
  
    def_map = get_def_blocks_for (var);
--- 1863,1877 ----
  		  Helpers for the main SSA building functions
  ---------------------------------------------------------------------------*/
  
  /* Insert PHI nodes for variable VAR.  */
  
  static void
! insert_phi_nodes_for (tree var, bitmap *dfs)
  {
    struct def_blocks_d *def_map;
    bitmap phi_insertion_points;
    unsigned phi_vector_lengths = 0;
+   int use_fully_pruned_ssa = 0;
    int bb_index;
  
    def_map = get_def_blocks_for (var);
*************** insert_phi_nodes_for (tree var, bitmap *
*** 1986,1992 ****
       heuristic.  */
    while (VARRAY_ACTIVE_SIZE (work_stack) > 0)
      {
-       edge e;
        basic_block bb = VARRAY_TOP_BB (work_stack);
        int bb_index = bb->index;
  
--- 1901,1906 ----
*************** insert_phi_nodes_for (tree var, bitmap *
*** 1998,2005 ****
  
  	  if (! bitmap_bit_p (phi_insertion_points, bb_index))
  	    {
! 	      for (e = bb->pred; e; e = e->pred_next)
! 		phi_vector_lengths++;
  	      VARRAY_PUSH_BB (work_stack, bb);
  	      bitmap_set_bit (phi_insertion_points, bb_index);
  	    }
--- 1912,1918 ----
  
  	  if (! bitmap_bit_p (phi_insertion_points, bb_index))
  	    {
! 	      phi_vector_lengths += bb_ann (bb)->num_preds;
  	      VARRAY_PUSH_BB (work_stack, bb);
  	      bitmap_set_bit (phi_insertion_points, bb_index);
  	    }
*************** insert_phi_nodes_for (tree var, bitmap *
*** 2024,2044 ****
       as the testcase for the compiler running wild eating memory.  */
    if (phi_vector_lengths > 64)
      {
!       /* Save away enough information so that we can defer PHI
! 	 insertion for this variable.  */
!       def_map->phi_insertion_points = phi_insertion_points;
!       VARRAY_PUSH_GENERIC_PTR (def_maps, def_map);
!       return;
      }
  
    EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index,
      {
!       create_phi_node (var, BASIC_BLOCK (bb_index));
      });
  
    phi_insertion_points = NULL;
  }
- 
  
  /* Rewrite statement pointed by iterator SI into SSA form. 
  
--- 1937,1955 ----
       as the testcase for the compiler running wild eating memory.  */
    if (phi_vector_lengths > 64)
      {
!       use_fully_pruned_ssa = 1;
!       compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
      }
  
    EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index,
      {
!       if (! use_fully_pruned_ssa
! 	  || bitmap_bit_p (def_map->livein_blocks, bb_index))
! 	create_phi_node (var, BASIC_BLOCK (bb_index));
      });
  
    phi_insertion_points = NULL;
  }
  
  /* Rewrite statement pointed by iterator SI into SSA form. 
  
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.108
diff -c -3 -p -r1.342.2.108 tree.h
*** tree.h	14 Oct 2003 00:12:58 -0000	1.342.2.108
--- tree.h	15 Oct 2003 22:18:02 -0000
*************** struct tree_ssa_name GTY(())
*** 1027,1032 ****
--- 1027,1036 ----
  
  /* In a PHI_NODE node.  */
  #define PHI_RESULT(NODE)	PHI_NODE_CHECK (NODE)->phi.result
+ 
+ /* Nonzero if the PHI node was rewritten by a previous pass through the
+    SSA renamer.  */
+ #define PHI_REWRITTEN(NODE)	PHI_NODE_CHECK (NODE)->phi.rewritten
  #define PHI_NUM_ARGS(NODE)	PHI_NODE_CHECK (NODE)->phi.num_args
  #define PHI_ARG_CAPACITY(NODE)	PHI_NODE_CHECK (NODE)->phi.capacity
  #define PHI_ARG_ELT(NODE, I)	PHI_NODE_ELT_CHECK (NODE, I)
*************** struct tree_phi_node GTY(())
*** 1047,1052 ****
--- 1051,1061 ----
    tree result;
    int num_args;
    int capacity;
+ 
+   /* Nonzero if the PHI node was rewritten by a previous pass through the
+      SSA renamer.  */
+   int rewritten;
+ 
    struct phi_arg_d GTY ((length ("((tree)&%h)->phi.capacity"))) a[1];
  };