[PATCH][1/n] into-SSA TLC

[Richard Guenther]

This removes one FOR_EACH_REFERENCED vars loop from into-ssa.
insert_phi_nodes, which is only called when we rewrite the whole
function into SSA, not from SSA updating, has an awkward way
of inserting PHI nodes for all relevant vars which uses
three hashtable lookups for all vars we insert PHIs for (and
some more).  The following patch gets that down to zero
and trades it for a qsort on a vector we trade for a temporary
bitmap.  That sounds overall faster (not that into-ssa time
matters - only update-ssa time would), and brings me one step
closer to eventually not require the UID -> DECL mapping
(referenced-vars) in into-SSA (which is the major blocker for
getting rid of that mapping alltogether).

Bootstrap and regtest pending on x86_64-unknown-linux-gnu.

Richard.

2012-07-27  Richard Guenther  <rguenther@suse.de>

	* tree-into-ssa.c (def_blocks_p): New typedef.
	(insert_phi_nodes_compare_def_blocks): New function.
	(insert_phi_nodes): Do not walk over referenced vars, instead
	walk over recorded def_blocks, record relevant ones and sort
	them to avoid repeated hashtable lookups.

Index: gcc/tree-into-ssa.c
===================================================================
*** gcc/tree-into-ssa.c	(revision 189904)
--- gcc/tree-into-ssa.c	(working copy)
*************** struct def_blocks_d
*** 67,72 ****
--- 67,77 ----
    bitmap livein_blocks;
  };
  
+ typedef struct def_blocks_d *def_blocks_p;
+ 
+ DEF_VEC_P(def_blocks_p);
+ DEF_VEC_ALLOC_P(def_blocks_p,heap);
+ 
  
  /* Each entry in DEF_BLOCKS contains an element of type STRUCT
     DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
*************** insert_phi_nodes_for (tree var, bitmap p
*** 1142,1147 ****
--- 1147,1164 ----
      }
  }
  
+ /* Sort def_blocks after DECL_UID of their var.  */
+ 
+ static int
+ insert_phi_nodes_compare_def_blocks (const void *a, const void *b)
+ {
+   const struct def_blocks_d *defa = *(struct def_blocks_d * const *)a;
+   const struct def_blocks_d *defb = *(struct def_blocks_d * const *)b;
+   if (DECL_UID (defa->var) < DECL_UID (defb->var))
+     return -1;
+   else
+     return 1;
+ }
  
  /* Insert PHI nodes at the dominance frontier of blocks with variable
     definitions.  DFS contains the dominance frontier information for
*************** insert_phi_nodes_for (tree var, bitmap p
*** 1150,1192 ****
  static void
  insert_phi_nodes (bitmap_head *dfs)
  {
!   referenced_var_iterator rvi;
!   bitmap_iterator bi;
!   tree var;
!   bitmap vars;
!   unsigned uid;
  
    timevar_push (TV_TREE_INSERT_PHI_NODES);
  
    /* Do two stages to avoid code generation differences for UID
       differences but no UID ordering differences.  */
  
!   vars = BITMAP_ALLOC (NULL);
!   FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
      {
!       struct def_blocks_d *def_map;
! 
!       def_map = find_def_blocks_for (var);
!       if (def_map == NULL)
! 	continue;
! 
!       if (get_phi_state (var) != NEED_PHI_STATE_NO)
! 	bitmap_set_bit (vars, DECL_UID (var));
!     }
! 
!   EXECUTE_IF_SET_IN_BITMAP (vars, 0, uid, bi)
!     {
!       tree var = referenced_var (uid);
!       struct def_blocks_d *def_map;
!       bitmap idf;
! 
!       def_map = find_def_blocks_for (var);
!       idf = compute_idf (def_map->def_blocks, dfs);
!       insert_phi_nodes_for (var, idf, false);
        BITMAP_FREE (idf);
      }
  
!   BITMAP_FREE (vars);
  
    timevar_pop (TV_TREE_INSERT_PHI_NODES);
  }
--- 1167,1196 ----
  static void
  insert_phi_nodes (bitmap_head *dfs)
  {
!   htab_iterator hi;
!   unsigned i;
!   struct def_blocks_d *def_map;
!   VEC(def_blocks_p,heap) *vars;
  
    timevar_push (TV_TREE_INSERT_PHI_NODES);
  
+   vars = VEC_alloc (def_blocks_p, heap, htab_elements (def_blocks));
+   FOR_EACH_HTAB_ELEMENT (def_blocks, def_map, struct def_blocks_d *, hi)
+     if (get_phi_state (def_map->var) != NEED_PHI_STATE_NO)
+       VEC_quick_push (def_blocks_p, vars, def_map);
+ 
    /* Do two stages to avoid code generation differences for UID
       differences but no UID ordering differences.  */
+   VEC_qsort (def_blocks_p, vars, insert_phi_nodes_compare_def_blocks);
  
!   FOR_EACH_VEC_ELT (def_blocks_p, vars, i, def_map)
      {
!       bitmap idf = compute_idf (def_map->def_blocks, dfs);
!       insert_phi_nodes_for (def_map->var, idf, false);
        BITMAP_FREE (idf);
      }
  
!   VEC_free(def_blocks_p, heap, vars);
  
    timevar_pop (TV_TREE_INSERT_PHI_NODES);
  }