[tree-ssa] Remove semi-pruned support

law@redhat.com law@redhat.com
Tue Jan 20 03:08:00 GMT 2004


Roughly a year ago I introduced the ability to use fully-pruned SSA
form rather than semi-pruned SSA form when inserting PHI nodes.  The
compiler dynamically switched between them on a per-variable basis
depending on the total number of PHI arguments we would create.
As the number of PHI arguments grew for a particular variable, we
switched to a fully pruned SSA form.

For large testcases, using a semi-pruned form could easily lead to explosions
of PHI nodes -- so bad PHI node insertion would eat all available virtual
memory and crash the compiler.  Fully pruned form costed more compile-time to
compute, but could drastically reduce the number of PHI nodes we needed
(which in turn improved memory behavior and compile-time) and allow those
nasty testcases to actually compile.

Since that time we've made numerous changes to the life computation, phi
insertion and other related code.  The utility of being able to switch
between pruned and semi-pruned form has diminished greatly.  And certain
aspects of how we handle re-rewriting make using semi-pruned almost always
a bad choice.  Testing the components of cc1 we have:


No changes:	370.30 seconds
Semi-pruned:    373.48 seconds
Fully-pruned:   368.76 seconds

Eliminating the heuristic and semi-pruned bits is effectively compile time
neutral and a minor cleanup.  It's also safe since fully pruned avoids the
PHI explosions that semi-pruned form is prone to trigger.

This also means there's ultimately one less magic constant in the
compiler and/or magic tuning knob that nobody would really understand
how to use.



Bootstrapped and regression tested i686-pc-linux-gnu

	* tree-ssa.c (insert_phi_nodes_for): Always use fully pruned
	SSA form.

Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.189
diff -c -p -r1.1.4.189 tree-ssa.c
*** tree-ssa.c	19 Jan 2004 23:21:42 -0000	1.1.4.189
--- tree-ssa.c	20 Jan 2004 03:04:59 -0000
*************** insert_phi_nodes_for (tree var, bitmap *
*** 3193,3200 ****
  {
    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);
--- 3193,3198 ----
*************** insert_phi_nodes_for (tree var, bitmap *
*** 3214,3227 ****
       which are added to the worklist are potential sites for
       PHI nodes. 
  
!      The iteration step could be done during PHI insertion.  But
!      finding all the PHI insertion blocks first allows us to use
!      that list of blocks in our heuristics to determine if we should
!      use semi-pruned for fully-pruned SSA forms. 
! 
!      While we're iterating we also compute the total length of all the
!      PHI node vectors for this variable.  We use this in our 
!      heuristic.  */
    while (VARRAY_ACTIVE_SIZE (work_stack) > 0)
      {
        basic_block bb = VARRAY_TOP_BB (work_stack);
--- 3212,3223 ----
       which are added to the worklist are potential sites for
       PHI nodes. 
  
!      The iteration step could be done during PHI insertion just as
!      easily.  We do it here for historical reasons -- we used to have
!      a heuristic which used the potential PHI insertion points to
!      determine if fully pruned or semi pruned SSA form was appropriate.
! 
!      We now always use fully pruned SSA form.  */
    while (VARRAY_ACTIVE_SIZE (work_stack) > 0)
      {
        basic_block bb = VARRAY_TOP_BB (work_stack);
*************** insert_phi_nodes_for (tree var, bitmap *
*** 3236,3274 ****
  	{
  	  basic_block bb = BASIC_BLOCK (dfs_index);
  
- 	  phi_vector_lengths += bb_ann (bb)->num_preds;
  	  VARRAY_PUSH_BB (work_stack, bb);
  	  bitmap_set_bit (phi_insertion_points, dfs_index);
  	});
      }
  
!   /* Now that we know the number of elements in all the potential
!      PHI nodes for this variable, we can determine if it is 
!      worth computing the fully pruned SSA form.  The larger the
!      total number of elements, the more important it is to use
!      the fully pruned form.
!  
!      Experimentation showed that once we get more than 8 phi vector
!      entries that moving to a fully-pruned implementation is comparable
!      to semi-pruned.  32 showed up as the threshold which maximized
!      overall compile-time performance. 
! 
!      Note that as this number gets larger, the potential for the
!      compiler to run wild and eat all available memory increases. 
!      So if you decide to change it, do so with care.  Consider
!      compile/20001226-1 with all memory references disambiguated
!      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;
--- 3232,3251 ----
  	{
  	  basic_block bb = BASIC_BLOCK (dfs_index);
  
  	  VARRAY_PUSH_BB (work_stack, bb);
  	  bitmap_set_bit (phi_insertion_points, dfs_index);
  	});
      }
  
!   /* Now compute global livein for this variable.  Note this modifies
!      def_map->livein_blocks.  */
!   compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
! 
!   /* And insert the PHI nodes.  */
!   EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
! 			    0, bb_index,
      {
!       create_phi_node (var, BASIC_BLOCK (bb_index));
      });
  
    phi_insertion_points = NULL;















More information about the Gcc-patches mailing list