[tree-ssa] variable partitions & liveness

Andrew MacLeod amacleod@redhat.com
Fri Apr 4 17:59:00 GMT 2003


So in attempting to write a coalescing partitioner for the un-ssa pass,
I've discovered what I need to change in the var_map routines.

This patch removes the var_map partition wrapper stuff from tree-ssa.c,
and places it in tree-ssa-live.[ch] These routines have been genericized
further, and can be used for dense representation of live range
information, amongst other things. I tried to add more consistancy to
the routine names. And I modified the way compaction works so it can
work with version variables as well as normal ones. (restriction removal
:-)

The next step after this patch is to provide some basic live range
information on the reduced partition sets, ie live-on-entry and
live-on-exit at the very least. They will go into the same new files.

*Then* I can do the coalescing partitioner :-)

I also restructured the calls and uses of var_maps in the un-ssa pass
such that its better structured for plug-and-replace coalescing
routines. There is a coalescing routine supplied here which coalesces
all versions of a variable into one version. This then gets mapped to
the real variable. The net effect is exactly the same as before this
patch, except now there is a single routine 'coalesce_ssa_name' in
tree-ssa.c which is responsible for coalescing ranges. This is a
plug&replace routine which will be replaced shortly with a real
overlapping range coalescer.

Timings on this are a very marginal difference in the unssa pass,
nothing of any significance. 

This bootstraps and causes no new regressions.  
comments? Ok to check in?

Andrew

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.81
diff -c -p -r1.903.2.81 Makefile.in
*** Makefile.in	1 Apr 2003 01:09:13 -0000	1.903.2.81
--- Makefile.in	4 Apr 2003 16:13:17 -0000
*************** C_OBJS = c-parse.o c-lang.o $(C_AND_OBJC
*** 786,792 ****
  OBJS = tree-cfg.o tree-dfa.o tree-ssa.o tree-optimize.o tree-simple.o      \
   tree-alias-type.o gimplify.o tree-nomudflap.o tree-pretty-print.o         \
   tree-alias-common.o tree-ssa-ccp.o tree-browser.o @ANDER@ tree-ssa-dce.o  \
!  tree-ssa-pre.o tree-ssa-copyprop.o                                        \
   alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	           \
   cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
   cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o	   \
--- 786,792 ----
  OBJS = tree-cfg.o tree-dfa.o tree-ssa.o tree-optimize.o tree-simple.o      \
   tree-alias-type.o gimplify.o tree-nomudflap.o tree-pretty-print.o         \
   tree-alias-common.o tree-ssa-ccp.o tree-browser.o @ANDER@ tree-ssa-dce.o  \
!  tree-ssa-pre.o tree-ssa-copyprop.o tree-ssa-live.o 			   \
   alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	           \
   cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
   cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o	   \
*************** tree-alias-common.o: tree-alias-common.c
*** 1458,1464 ****
  tree-ssa.o : tree-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
     $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h diagnostic.h \
     ssa.h errors.h toplev.h function.h $(TIMEVAR_H) tree-alias-common.h \
!    $(TM_H) coretypes.h $(TREE_DUMP_H)
  tree-ssa-pre.o : tree-ssa-pre.c $(TREE_FLOW_H) $(CONFIG_H) \
     $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \
     $(GGC_H) output.h diagnostic.h ssa.h errors.h toplev.h $(TIMEVAR_H) \
--- 1458,1468 ----
  tree-ssa.o : tree-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
     $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h diagnostic.h \
     ssa.h errors.h toplev.h function.h $(TIMEVAR_H) tree-alias-common.h \
!    $(TM_H) coretypes.h $(TREE_DUMP_H) tree-ssa-live.h
! tree-ssa-live.o : tree-ssa-live.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
!    $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h diagnostic.h \
!    ssa.h errors.h toplev.h function.h $(TIMEVAR_H) tree-alias-common.h \
!    $(TM_H) coretypes.h $(TREE_DUMP_H) tree-ssa-live.h
  tree-ssa-pre.o : tree-ssa-pre.c $(TREE_FLOW_H) $(CONFIG_H) \
     $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \
     $(GGC_H) output.h diagnostic.h ssa.h errors.h toplev.h $(TIMEVAR_H) \
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.62
diff -c -p -r1.1.4.62 tree-ssa.c
*** tree-ssa.c	1 Apr 2003 23:04:02 -0000	1.1.4.62
--- tree-ssa.c	4 Apr 2003 16:13:20 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 45,50 ****
--- 45,51 ----
  #include "tree-alias-common.h"
  #include "hashtab.h"
  #include "tree-dump.h"
+ #include "tree-ssa-live.h"
  
  /* This file builds the SSA form for a function as described in:
  
*************** static htab_t avail_exprs;
*** 112,134 ****
     propagation).  */
  static htab_t const_and_copies;
  
- /* Used to create the variable mapping when we go out of SSA form.  */
- typedef struct _var_map
- {
-   /* The partition of all ssa names.  */
-   partition var_partition;
- 
-   /* Compressed partition map */
-   int *compaction;
- 
-   /* Mapping of partition to vars.  */
-   tree *partition_to_var;
- 
-   unsigned int num_partitions;
- } *var_map;
- 
- #define VAR_ANN_PARTITION(ann) (ann->partition)
- 
  /* Used to hold all the components requires to do SSA PHI elimination.  */
  
  typedef struct _elim_graph
--- 113,118 ----
*************** static int avail_expr_eq		PARAMS ((const
*** 207,223 ****
  static struct def_blocks_d *get_def_blocks_for PARAMS ((tree));
  static void htab_statistics		PARAMS ((FILE *, htab_t));
  
- static var_map create_var_map		PARAMS ((int));
- static void set_var_mapping		PARAMS ((var_map, tree, sbitmap));
- static var_map create_var_partition	PARAMS ((void));
- static inline tree mapped_var_from_ref	PARAMS ((var_map, tree));
- static void delete_var_map		PARAMS ((var_map));
- static int get_var_partition		PARAMS ((var_map, tree));
- static void set_partition_for_var	PARAMS ((var_map, tree, int));
- void dump_tree_partition		PARAMS ((FILE *, var_map, int));
- static void compact_var_map		PARAMS ((var_map));
- static inline tree var_from_partition	PARAMS ((var_map, int));
- 
  static tree create_temp			PARAMS ((tree));
  static void insert_copy_on_edge		PARAMS ((edge, tree, tree));
  static elim_graph new_elim_graph	PARAMS ((int));
--- 191,196 ----
*************** static void elim_backward		PARAMS ((elim
*** 231,236 ****
--- 204,211 ----
  static void elim_create			PARAMS ((elim_graph, int));
  static void eliminate_phi		PARAMS ((edge, int, elim_graph));
  static void eliminate_extraneous_phis	PARAMS ((void));
+ static void coalesce_ssa_name		PARAMS ((var_map));
+ static void assign_vars			PARAMS ((var_map));
  
  /* FIXME: [UNSSA] Remove once the real unSSA pass is implemented.  */
  #if 1
*************** rewrite_block (bb, eq_expr_value)
*** 830,1158 ****
  }
  
  
- 
- /* This is where the mapping from SSA version number to real storage variable
-    is tracked.  
- 
-    All SSA versions of the same variable may not ultimately be mapped back to
-    the same real variable. In that instance, we need to detect the live
-    range overlap, and give one of the variable new storage. The vector
-    'partition_to_var' tracks which partition maps to whicvh variable.
- 
-    Given a VAR, it is sometimes desirable to know which partition that VAR
-    represents.  There is an additional field in the variable annotation to
-    track that information.  */
- 
- /* Create the variable partition and initialize it.  */
- 
- static var_map
- create_var_map (size)
-      int size;
- {
-   var_map map;
- 
-   map = (var_map) xmalloc (sizeof (struct _var_map));
-   map->var_partition = partition_new (size);
-   map->partition_to_var 
- 	      = (tree *)xmalloc (size * sizeof (tree));
-   memset (map->partition_to_var, 0, size * sizeof (tree));
- 
-   map->compaction = NULL;
-   map->num_partitions = size;
-   return map;
- }
- 
- /* Free memory associated with a var_map.  */
- 
- static void
- delete_var_map (map)
-      var_map map;
- {
-   free (map->partition_to_var);
-   partition_delete (map->var_partition);
-   if (map->compaction)
-     free (map->compaction);
-   free (map);
- }
- 
- 
- /* Given a partition number, return the variable which represents that 
-    partition.  */
- 
- static inline tree
- var_from_partition (map, i)
-      var_map map;
-      int i;
- {
-   return map->partition_to_var [i];
- }
- 
- /* Given a variable, return the partition number which contains it.  */
- 
- static int
- get_var_partition (map, var)
-      var_map map;
-      tree var;
- {
-   var_ann_t ann;
-   int part;
- 
-   if (TREE_CODE (var) == SSA_NAME)
-     {
-       part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
-       if (map->compaction)
- 	part = map->compaction[part];
-     }
-   else
-     {
-       ann = var_ann (var);
-       part = VAR_ANN_PARTITION (ann);
-     }
-   return part;
- }
- 
- /* Given a variable, return the variable which represents the entire partition
-    the specified one is a member of.  */
- 
- static inline tree
- mapped_var_from_ref (map, var)
-      var_map map;
-      tree var;
- {
-   int part;
- 
-   part = get_var_partition (map, var);
-   return var_from_partition (map, part);
- }
- 
- /* Compress the partition numbers such that they fall in the range 
-    0..(num_partitions-1) instead of whereever they turned out during
-    the partitioning exercise. This removes any references to unused
-    partitions, thereby allowing bitmaps and other vectors to be much
-    denser.  */
- 
- static void 
- compact_var_map (map)
-      var_map map;
- {
-   sbitmap used;
-   int x, limit, count, tmp;
- 
-   limit = map->num_partitions;
-   used = sbitmap_alloc (limit);
-   sbitmap_zero (used);
- 
-   map->compaction = (int *)xmalloc (limit * sizeof (int));
- 
-   /* Find out which partitions are actually referenced.  */
-   count = 0;
-   for (x = 0; x < limit; x++)
-     {
-       map->compaction[x] = x;
-       tmp = partition_find (map->var_partition, x);
-       if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
-         {
- 	  SET_BIT (used, tmp);
- 	  count++;
- 	}
-     }
-   
-   /* Build a compacted partitioning.  */
-   if (count != limit)
-     {
-       count = 0;
-       /* SSA renaming begins at 1, so skip 0 when compacting.  */
-       EXECUTE_IF_SET_IN_SBITMAP (used, 1, x,
- 	{
- 	  map->compaction[x] = count;
- 	  set_partition_for_var (map, map->partition_to_var[x], count);
- 	  count++;
- 	});
-     }
-   else
-     {
-       free (map->compaction);
-       map->compaction = NULL;
-     }
- 
-   map->num_partitions = count;
-   sbitmap_free (used);
- }
- 
- 
- /* For debuging. Output a partition.  */
- 
- void
- dump_tree_partition (f, map, dump_flags)
-      FILE *f;
-      var_map map;
-      int dump_flags;
- {
-   int t;
-   unsigned x, y, p;
- 
-   fprintf (f, "\nPartition map \n\n");
-   if (dump_flags & TDF_DETAILS)
-     {
-       for (x = 1; x <= next_ssa_version; x++)
- 	{
- 	  p = partition_find (map->var_partition, x);
- 	  if (map->compaction)
- 	    p = map->compaction[p];
- 	  fprintf (f, "ver %3d -> partition %3d  (", x, p);
- 	  print_generic_expr (f, var_from_partition (map, p), TDF_SLIM);
- 	  fprintf (f, ")\n");
- 	}
-       fprintf (f, "\n\n");
-     }
- 
-   for (x = 0; x < map->num_partitions; x++)
-     {
-       if (map->partition_to_var[x] == NULL_TREE)
-         continue;
-       t = 0;
-       for (y = 1; y < next_ssa_version; y++)
-         {
- 	  p = partition_find (map->var_partition, y);
- 	  if (map->compaction)
- 	    p = map->compaction[p];
- 	  if (p == x)
- 	    {
- 	      if (t++ == 0)
- 	        {
- 		  fprintf(stderr, "Partition %d (", x);
- 		  print_generic_expr (f, var_from_partition (map, p), TDF_SLIM);
- 		  fprintf (stderr, " - ");
- 		}
- 	      fprintf (stderr, "%d ", y);
- 	    }
- 	}
-       if (t != 0)
- 	fprintf (stderr, ")\n");
-     }
-   fprintf (f, "\n");
- }
- 
- /* Set the partition mapping fields for a var.  Eventually, this routine 
-    needs to recognize overlapping live ranges, and assign different variables
-    for overlapping ranges. Right now, we just stupidly always use the
-    root variable.  */
- 
- static void 
- set_partition_for_var (map, var, part)
-      var_map map;
-      tree var;
-      int part;
- {
-   var_ann_t ann;
- 
-   ann = var_ann (var);
-   ann->processed_out_of_ssa = 1;
-   VAR_ANN_PARTITION (ann) = part;
-   map->partition_to_var[part] = var;
- }
- 
- /* Used to map an ssa versioned var to a real var.  */
- 
- static void
- set_var_mapping (map, ssa_var, visited)
-      var_map map;
-      tree ssa_var;
-      sbitmap visited;
- {
-   var_ann_t ann;
-   tree var;
-   int version;
- 
-   var = SSA_NAME_VAR (ssa_var);
-   ann = var_ann (var);
-   version = SSA_NAME_VERSION (ssa_var);
-   if (TEST_BIT (visited, version))
-     return;
-   SET_BIT (visited, version);
-   if (!ann->processed_out_of_ssa)
-     {
-       /* First time var is processed, give it this partition.  */
-       set_partition_for_var (map, var, version);
-     }
-   else
-     {
-       /* Dummy version. Make all versions refer to the root 
- 	 version for that variable.   Ultimately, we need to 
- 	 look for overlapping live ranges and create new 
- 	 variables for those instead of this.  */
-       VAR_ANN_PARTITION (ann) 
- 		    = partition_union (map->var_partition, 
- 				       VAR_ANN_PARTITION (ann), 
- 				       version);
-       map->partition_to_var[VAR_ANN_PARTITION (ann)] = var;
-     }
- }
- 
- 
- /* This looks through the function to determine what SSA versioned variables
-    need to have entries in the partition table. Partitions are created, and
-    variables are asigned to represents partitions.
- 
-    *TODO* Currently, we simply make all versioned versions of a variable map to
-    that variable.  This will create incorrect code when there are overlapping
-    live ranges. The correct fix to this is coming, it will be different version
-    of this function which puts overlapping live ranges into different 
-    partitions.  */
- 
- static var_map
- create_var_partition ()
- {
-   block_stmt_iterator bsi;
-   basic_block bb;
-   tree *dest;
-   tree stmt;
-   varray_type ops;
-   unsigned x;
-   int i;
-   var_map map;
-   tree phi;
-   sbitmap visited;
- 
-   map = create_var_map (next_ssa_version + 1);
- 
-   visited = sbitmap_alloc (next_ssa_version + 1);
-   sbitmap_zero (visited);
- 
-   FOR_EACH_BB (bb)
-     {
-       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-         {
- 	  stmt = bsi_stmt (bsi);
- 	  get_stmt_operands (stmt);
- 
- 	  ops = use_ops (stmt);
- 	  for (x = 0; ops && x < VARRAY_ACTIVE_SIZE (ops); x++)
- 	    {
- 	      tree *use = VARRAY_GENERIC_PTR (ops, x);
- 	      set_var_mapping (map, *use, visited);
- 	    }
- 
- 	  dest = def_op (stmt);
- 	  if (dest)
- 	    set_var_mapping (map, *dest, visited);
- 	  
- 	}
-       
-       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
- 	{
- 	  set_var_mapping (map, PHI_RESULT (phi), visited);
- 	  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
- 	    set_var_mapping (map, PHI_ARG_DEF (phi, i), visited);
- 	  
- 	}
-     }
- 
-   sbitmap_free (visited);
-   return map;
- }
- 
- 
  /* This function will create a temporary for a partition based on the
     type of the variable which already represents a partition.  */
  
--- 805,810 ----
*************** create_temp (t)
*** 1163,1168 ****
--- 815,823 ----
    tree tmp;
    const char *name = NULL;
    tree type;
+ 
+   if (TREE_CODE (t) == SSA_NAME)
+     t = SSA_NAME_VAR (t);
   
    if (TREE_CODE (t) != VAR_DECL 
        && TREE_CODE (t) != PARM_DECL
*************** eliminate_name (g, T)
*** 1262,1268 ****
       elim_graph g;
       tree T;
  {
!   int version = get_var_partition (g->map, T);
  
    /* If this is the first time a node is added, clear the graph.
       Delaying it until here prevents clearing all the vectors
--- 917,923 ----
       elim_graph g;
       tree T;
  {
!   int version = var_to_partition (g->map, T);
  
    /* If this is the first time a node is added, clear the graph.
       Delaying it until here prevents clearing all the vectors
*************** eliminate_build (g, B, i)
*** 1295,1308 ****
    
    for (phi = phi_nodes (B); phi; phi = TREE_CHAIN (phi))
      {
!       T0 = mapped_var_from_ref (g->map, PHI_RESULT (phi));
!       Ti = mapped_var_from_ref (g->map, PHI_ARG_DEF (phi, i));
        if (T0 != Ti)
          {
  	  eliminate_name (g, T0);
  	  eliminate_name (g, Ti);
! 	  p0 = get_var_partition (g->map, T0);
! 	  pi = get_var_partition (g->map, Ti);
  	  SET_BIT (g->pred[pi], p0);
  	  SET_BIT (g->succ[p0], pi);
  	  edges++;
--- 950,963 ----
    
    for (phi = phi_nodes (B); phi; phi = TREE_CHAIN (phi))
      {
!       T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi));
!       Ti = var_to_partition_to_var (g->map, PHI_ARG_DEF (phi, i));
        if (T0 != Ti)
          {
  	  eliminate_name (g, T0);
  	  eliminate_name (g, Ti);
! 	  p0 = var_to_partition (g->map, T0);
! 	  pi = var_to_partition (g->map, Ti);
  	  SET_BIT (g->pred[pi], p0);
  	  SET_BIT (g->succ[p0], pi);
  	  edges++;
*************** elim_backward (g, T)
*** 1360,1367 ****
        if (!TEST_BIT (g->visited, P))
          elim_backward (g, P);
        insert_copy_on_edge (g->e, 
! 			   var_from_partition (g->map, P), 
! 			   var_from_partition (g->map, T));
      });
  }
  
--- 1015,1022 ----
        if (!TEST_BIT (g->visited, P))
          elim_backward (g, P);
        insert_copy_on_edge (g->e, 
! 			   partition_to_var (g->map, P), 
! 			   partition_to_var (g->map, T));
      });
  }
  
*************** elim_create (g, T)
*** 1379,1392 ****
  
    if (elim_unvisited_predecessor (g, T))
      {
!       U = create_temp (var_from_partition (g->map, T));
!       insert_copy_on_edge (g->e, U, var_from_partition (g->map, T));
        EXECUTE_IF_SET_IN_SBITMAP (g->pred[T], 0, P,
  	{
  	  if (!TEST_BIT (g->visited, P))
  	    {
  	      elim_backward (g, P);
! 	      insert_copy_on_edge (g->e, var_from_partition (g->map, P), U);
  	    }
  	});
      }
--- 1034,1047 ----
  
    if (elim_unvisited_predecessor (g, T))
      {
!       U = create_temp (partition_to_var (g->map, T));
!       insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
        EXECUTE_IF_SET_IN_SBITMAP (g->pred[T], 0, P,
  	{
  	  if (!TEST_BIT (g->visited, P))
  	    {
  	      elim_backward (g, P);
! 	      insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
  	    }
  	});
      }
*************** elim_create (g, T)
*** 1397,1404 ****
  	  SET_BIT (g->visited, T);
  	  RESET_BIT (g->succ[T], S);
  	  insert_copy_on_edge (g->e, 
! 			       var_from_partition (g->map, T), 
! 			       var_from_partition (g->map, S));
  	});
      }
    
--- 1052,1059 ----
  	  SET_BIT (g->visited, T);
  	  RESET_BIT (g->succ[T], S);
  	  insert_copy_on_edge (g->e, 
! 			       partition_to_var (g->map, T), 
! 			       partition_to_var (g->map, S));
  	});
      }
    
*************** eliminate_phi (e, i, g)
*** 1429,1436 ****
        num_phi++;
      }
  
!   num_nodes = g->map->num_partitions;
! 
    g->e = e;
  
    x = eliminate_build (g, B, i);
--- 1084,1090 ----
        num_phi++;
      }
  
!   num_nodes = num_var_partitions (g->map);
    g->e = e;
  
    x = eliminate_build (g, B, i);
*************** eliminate_extraneous_phis ()
*** 1496,1501 ****
--- 1150,1247 ----
      }
  }
  
+ /* Reduce the number of live ranges in the var_map. We don't associate any
+    actual variables with partitions yet, its still left in SSA form.  */
+ 
+ static void
+ coalesce_ssa_name (map)
+      var_map map;
+ {
+   int num, x;
+   tree t1, var;
+   var_ann_t ann;
+ 
+   varray_type real_vars;
+ /* FIXME. Currently, all versions of a var are coalesced together, regardless
+    of whether there is an overlapping live range. This needs to be fixed 
+    shortly.  */
+ 
+   num = num_var_partitions (map);
+   VARRAY_TREE_INIT (real_vars, num, "real_vars");
+ 
+   for (x = 0; x< num; x++)
+     {
+       t1 = partition_to_var (map, x);
+       var = SSA_NAME_VAR (t1);
+       ann = var_ann (var);
+       if (!ann->processed_out_of_ssa)
+         {
+ 	  ann->partition = x;
+ 	  ann->processed_out_of_ssa = 1;
+ 	  VARRAY_PUSH_TREE (real_vars, var);
+ 	}
+       else
+         {
+ 	  var = partition_to_var (map, x);
+ 	  ann->partition 
+ 		= var_union (map, var, partition_to_var (map, ann->partition));
+ 	}
+     }
+   /* Now reset the processed bit on the vars.  */
+   while (VARRAY_ACTIVE_SIZE (real_vars) > 0)
+     {
+       var = VARRAY_TOP_TREE (real_vars);
+       VARRAY_POP (real_vars);
+       ann = var_ann (var);
+       ann->processed_out_of_ssa = 0;
+     }
+ }
+ 
+ /* Take the ssa-name var_map, and make real variables out of each partition.
+    This will be used to make each SSA-version varaiable to a real variable.  */
+ 
+ static void
+ assign_vars (map)
+      var_map map;
+ {
+   int num, x;
+   tree t, var;
+   var_ann_t ann;
+ 
+   num = num_var_partitions (map);
+   for (x = 0; x< num; x++)
+     {
+       t = partition_to_var (map, x);
+       if (!t) 
+         continue;
+ 
+       if (TREE_CODE (t) == SSA_NAME)
+         {
+ 	  /* If the base variable for this version has not been assigned
+ 	     a partition, then we use that.  */
+ 	  var = SSA_NAME_VAR (t);
+ 	  ann = var_ann (var);
+ 	  if (!ann->processed_out_of_ssa)
+ 	    {
+ 	      change_partition_var (map, var, x);
+ 	      continue;
+ 	    }
+ 	}
+       else
+ 	{
+ 	  /* Make sure This variable agree's with this partition.  */
+ 	  if (var_to_partition (map, t) == x)
+ 	    continue;
+ 	}
+       /* If this point is reached, we need a new temp.  */
+ 
+       var = create_temp (t);
+       change_partition_var (map, var, x);
+     }
+ 
+ }
+ 
+ 
  /* Take function FNDECL out of SSA form.
  
     FIXME: Need to support overlapping live ranges for different versions of
*************** rewrite_out_of_ssa (fndecl)
*** 1520,1528 ****
    timevar_push (TV_TREE_SSA_TO_NORMAL);
  
    eliminate_extraneous_phis ();
!   map = create_var_partition ();
    compact_var_map (map);
  
    g = new_elim_graph (map->num_partitions);
    g->map = map;
    FOR_EACH_BB (bb)
--- 1266,1283 ----
    timevar_push (TV_TREE_SSA_TO_NORMAL);
  
    eliminate_extraneous_phis ();
!   map = create_ssa_var_map ();
!   /* Shrink the map to include only referenced variables.  */
    compact_var_map (map);
  
+   coalesce_ssa_name (map);
+   /* Shrink the map again now that ranges have been coalesced.  */
+   compact_var_map (map);
+ 
+   /* This is the final var list, so assign real variables to the different
+      partitions.  */
+   assign_vars (map);
+ 
    g = new_elim_graph (map->num_partitions);
    g->map = map;
    FOR_EACH_BB (bb)
*************** rewrite_out_of_ssa (fndecl)
*** 1548,1560 ****
  	  for (i = 0; i < num_ops; i++)
  	    {
  	      use_p = VARRAY_GENERIC_PTR (ops, i);
! 	      *use_p = mapped_var_from_ref (map, *use_p);
  	    }
  
  	  if (def_op (stmt))
  	    {
  	      tree *def_p = def_op (stmt);
! 	      *def_p = mapped_var_from_ref (map, *def_p);
  
  	      if (is_copy && num_ops == 1 && use_p && (*def_p == *use_p))
  		remove = 1;
--- 1303,1315 ----
  	  for (i = 0; i < num_ops; i++)
  	    {
  	      use_p = VARRAY_GENERIC_PTR (ops, i);
! 	      *use_p = var_to_partition_to_var (map, *use_p);
  	    }
  
  	  if (def_op (stmt))
  	    {
  	      tree *def_p = def_op (stmt);
! 	      *def_p = var_to_partition_to_var (map, *def_p);
  
  	      if (is_copy && num_ops == 1 && use_p && (*def_p == *use_p))
  		remove = 1;



----- tree-ssa-live.h ----------------------

/* Routines for liveness in SSA trees.
   Copyright (C) 2003 Free Software Foundation, Inc.
   Contributed by Andrew MacLeod  <amacleod@redhat.com>

This file is part of GNU CC.

GNU CC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */


#ifndef _TREE_SSA_LIVE_H__
#define _TREE_SSA_LIVE_H 1


/* Used to create the variable mapping when we go out of SSA form.  */
typedef struct _var_map
{
  /* The partition of all variables.  */
  partition var_partition;

  /* Vector for compacting partitions.  */
  int *partition_to_compact;
  int *compact_to_partition;

  /* Mapping of partition numbers to vars.  */
  tree *partition_to_var;

  /* Current number of partitions.  */
  unsigned int num_partitions;

  /* Original partition size.  */
  unsigned int partition_size;
} *var_map;

#define VAR_ANN_PARTITION(ann) (ann->partition)

extern var_map init_var_map		PARAMS ((int));
extern void delete_var_map		PARAMS ((var_map));
extern void dump_var_map		PARAMS ((FILE *, var_map, int));
extern void compact_var_map		PARAMS ((var_map));
extern int var_union			PARAMS ((var_map, tree, tree));
extern void change_partition_var	PARAMS ((var_map, tree, int));
extern var_map create_ssa_var_map	PARAMS ((void));

static inline int num_var_partitions	PARAMS ((var_map));
static inline tree var_to_partition_to_var	PARAMS ((var_map, tree));
static inline tree partition_to_var	PARAMS ((var_map, int));
static inline void register_ssa_partition	PARAMS ((var_map, tree));
static inline int var_to_partition		PARAMS ((var_map, tree));

/* Number of partitions.  */

static inline int 
num_var_partitions (map)
     var_map map;
{
  return map->num_partitions;
}

 
/* Given a partition number, return the variable which represents that 
   partition.  */
 
static inline tree
partition_to_var (map, i)
     var_map map;
     int i;
{
  if (map->compact_to_partition)
    i = map->compact_to_partition[i];
  return map->partition_to_var[i];
}

/* Given a variable, return the partition number which contains it.  */

static inline int
var_to_partition (map, var)
     var_map map;
     tree var;
{
  var_ann_t ann;
  int part;

  if (TREE_CODE (var) == SSA_NAME)
    {
      part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
      if (map->partition_to_compact)
	part = map->partition_to_compact[part];
    }
  else
    {
      ann = var_ann (var);
      part = VAR_ANN_PARTITION (ann);
    }
  return part;
}

/* Given a variable, return the variable which represents the entire partition
   the specified one is a member of.  */

static inline tree
var_to_partition_to_var (map, var)
     var_map map;
     tree var;
{
  int part;

  part = var_to_partition (map, var);
  return partition_to_var (map, part);
}

/* This routine registers an SSA versioned variable with the partition
   manager. Any unregistered partitions may be compacted out later.  */

static inline void
register_ssa_partition (map, ssa_var)
     var_map map;
     tree ssa_var;
{
  if (TREE_CODE (ssa_var) != SSA_NAME)
    abort ();
  map->partition_to_var[SSA_NAME_VERSION (ssa_var)] = ssa_var;
}



#endif /* _TREE_SSA_LIVE_H  */



------- tree-ssa-live.c -------------------

/* Liveness for SSA trees.
   Copyright (C) 2003 Free Software Foundation, Inc.
   Contributed by Andrew MacLeod <amacleod@redhat.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "flags.h"
#include "basic-block.h"
#include "function.h"
#include "diagnostic.h"
#include "bitmap.h"
#include "tree-flow.h"
#include "tree-simple.h"
#include "tree-inline.h"
#include "varray.h"
#include "timevar.h"
#include "tree-alias-common.h"
#include "hashtab.h"
#include "tree-dump.h"
#include "tree-ssa-live.h"

extern unsigned long next_ssa_version;


/* This is where the mapping from SSA version number to real storage variable
   is tracked.  

   All SSA versions of the same variable may not ultimately be mapped back to
   the same real variable. In that instance, we need to detect the live
   range overlap, and give one of the variable new storage. The vector
   'partition_to_var' tracks which partition maps to which variable.

   Given a VAR, it is sometimes desirable to know which partition that VAR
   represents.  There is an additional field in the variable annotation to
   track that information.  */

/* Create the variable partition and initialize it.  */

var_map
init_var_map (size)
     int size;
{
  var_map map;

  map = (var_map) xmalloc (sizeof (struct _var_map));
  map->var_partition = partition_new (size);
  map->partition_to_var 
	      = (tree *)xmalloc (size * sizeof (tree));
  memset (map->partition_to_var, 0, size * sizeof (tree));

  map->partition_to_compact = NULL;
  map->compact_to_partition = NULL;
  map->num_partitions = size;
  map->partition_size = size;
  return map;
}

/* Free memory associated with a var_map.  */

void
delete_var_map (map)
     var_map map;
{
  free (map->partition_to_var);
  partition_delete (map->var_partition);
  if (map->partition_to_compact)
    free (map->partition_to_compact);
  if (map->compact_to_partition)
    free (map->compact_to_partition);
  free (map);
}

/* This function will combine 2 partitions.  */

int
var_union (map, var1, var2)
     var_map map;
     tree var1, var2;
{
  int p1, p2, p3;

  /* This is independant of partition_to_compact. If partition_to_compact is 
     on, then whichever one of these partitions is absorbed will never have a
     dereference into the partition_to_compact array any more.  */

  p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
  p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));

  if (p1 == p2)
    p3 = p1;
  else
    p3 = partition_union (map->var_partition, p1, p2);

  if (map->partition_to_compact)
    p3 = map->partition_to_compact[p3];

  return p3;
}


/* Compress the partition numbers such that they fall in the range 
   0..(num_partitions-1) instead of whereever they turned out during
   the partitioning exercise. This removes any references to unused
   partitions, thereby allowing bitmaps and other vectors to be much
   denser.  */

void 
compact_var_map (map)
     var_map map;
{
  sbitmap used;
  int x, limit, count, tmp;
  tree var;

  limit = map->partition_size;
  used = sbitmap_alloc (limit);
  sbitmap_zero (used);

  /* Already compressed? Abandon the old one.  */
  if (map->partition_to_compact)
    free (map->partition_to_compact);
  if (map->compact_to_partition)
    free (map->compact_to_partition);

  map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
  memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));

  /* Find out which partitions are actually referenced.  */
  count = 0;
  for (x = 0; x < limit; x++)
    {
      tmp = partition_find (map->var_partition, x);
      if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
        {
	  SET_BIT (used, tmp);
	  count++;
	}
    }
  

  /* Build a compacted partitioning.  */
  if (count != limit)
    {
      map->compact_to_partition = (int *)xmalloc (count * sizeof (int));
      count = 0;
      /* SSA renaming begins at 1, so skip 0 when compacting.  */
      EXECUTE_IF_SET_IN_SBITMAP (used, 1, x,
	{
	  map->partition_to_compact[x] = count;
	  map->compact_to_partition[count] = x;
	  var = map->partition_to_var[x];
	  if (TREE_CODE (var) != SSA_NAME)
	    change_partition_var (map, var, count);
	  count++;
	});
    }
  else
    {
      free (map->partition_to_compact);
      map->partition_to_compact = NULL;
    }

  map->num_partitions = count;
  sbitmap_free (used);
}


/* This routine can be used to change the representative variable for a 
   partition from an SSA variable to a regular variable. Since SSA variables
   are versioned, that association cannot be changed. This allows partitions
   to be mapped back to real variables.  */
  
void 
change_partition_var (map, var, part)
     var_map map;
     tree var;
     int part;
{
  var_ann_t ann;

  if (TREE_CODE (var) == SSA_NAME)
    abort();

  ann = var_ann (var);
  ann->processed_out_of_ssa = 1;
  VAR_ANN_PARTITION (ann) = part;
  if (map->compact_to_partition)
    map->partition_to_var[map->compact_to_partition[part]] = var;
}


/* This looks through the function to determine what SSA versioned variables
   need to have entries in the partition table.  */

var_map
create_ssa_var_map ()
{
  block_stmt_iterator bsi;
  basic_block bb;
  tree *dest;
  tree stmt;
  varray_type ops;
  unsigned x;
  int i;
  var_map map;
  tree phi;

  map = init_var_map (next_ssa_version + 1);
  FOR_EACH_BB (bb)
    {
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
        {
	  stmt = bsi_stmt (bsi);
	  get_stmt_operands (stmt);

	  ops = use_ops (stmt);
	  for (x = 0; ops && x < VARRAY_ACTIVE_SIZE (ops); x++)
	    {
	      tree *use = VARRAY_GENERIC_PTR (ops, x);
	      register_ssa_partition (map, *use);
	    }

	  dest = def_op (stmt);
	  if (dest)
	    register_ssa_partition (map, *dest);
	}
      
      for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
	{
	  register_ssa_partition (map, PHI_RESULT (phi));
	  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
	    register_ssa_partition (map, PHI_ARG_DEF (phi, i));
	}
    }

  return map;
}


/* Output a partition.  */

void
dump_var_map (f, map, dump_flags)
     FILE *f;
     var_map map;
     int dump_flags;
{
  int t;
  unsigned x, y;
  int p;

  fprintf (f, "\nPartition map \n\n");
  if (dump_flags & TDF_DETAILS)
    {
      for (x = 1; x <= next_ssa_version; x++)
	{
	  p = partition_find (map->var_partition, x);
	  if (map->partition_to_compact)
	    p = map->partition_to_compact[p];
	  fprintf (f, "ver %3d -> partition %3d  (", x, p);
	  if (p >= 0)
	    print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
	  fprintf (f, ")\n");
	}
      fprintf (f, "\n\n");
    }

  for (x = 0; x < map->num_partitions; x++)
    {
      if (map->compact_to_partition != NULL)
	p = map->compact_to_partition[x];
      else
	p = x;

      if (map->partition_to_var[p] == NULL_TREE)
        continue;
      t = 0;
      for (y = 1; y < next_ssa_version; y++)
        {
	  p = partition_find (map->var_partition, y);
	  if (map->partition_to_compact)
	    p = map->partition_to_compact[p];
	  if (p == (int)x)
	    {
	      if (t++ == 0)
	        {
		  fprintf(stderr, "Partition %d (", x);
		  print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
		  fprintf (stderr, " - ");
		}
	      fprintf (stderr, "%d ", y);
	    }
	}
      if (t != 0)
	fprintf (stderr, ")\n");
    }
  fprintf (f, "\n");
}



More information about the Gcc-patches mailing list