[tree-ssa]. Some out-of-ssa restructuring and new infratructure routines.

Andrew MacLeod amacleod@redhat.com
Wed Jul 23 16:48:00 GMT 2003


OK, time to do a source dump or I'll lose track of my changes :-)

This patch generalizes a couple of existing structures, and introduces a
coalescing object. This is a restructuring phase which is a prerequisite to
doing memory coalescing of non-interfering variables. So things have been 
renamed, and some moved from tree-ssa.c to tree-ssa-live.c

In order to coalesce memory locations, we need live range information
on the variables partitions have been assigned to, then we need to build a 
conflict graph over these variables, and then coalesce what we can. All the
required components except for the list of coalesces already existed, but neededto be abstracted a bit to allow then to be resued in a different context.

When coalescing variables, we do it by type. The root_var structure organized
partitions based on the root_variable of their SSA_NAME. the new type_var 
structure does the exact same thing, except it organizes them by type. The
common parts of this were abstracted out into a new type called a tpa_p 
(type_partition_associator). The conflict graph and coalescer were broken out 
from ssa_name_coalesce, and changed to use the tpa_p type. Both can now be
used unchanged to do the required work on the types now.  Along the way, I 
renamed all the root_var and the new type_var and tpa_ routines for some
consistancy.

I've also added an option tree-combine-temps which will allow us to turn on
or off the memory location coalescer.

The memory coalescing is going to be done immediately after the
ssa_names have been converted to real variables, but before we actually 
convert PHI nodes into copies.

To avoid requiring a bunch of live range information on non-ssa variables,
Ive modified the live range routines to either treat PHI nodes the way they 
were before, or now optionally as if they were copies at the end of the source
block. This way we can combine the existing live range information for 
coalesced partitions, calculate new live on exit information based on the
copies that SSA->normal is about to issue, and try to coalesce these copies
before they are issued. This avoid rebuilding the live on entry information
and also avoids any new live range routines for non-ssa variables.

A new coalescing list object has been created. Its not being used yet, but
it will be shortly. The conflict graph builder will add any copies it
sees into the coalesce list. The list will organize whatever partition
coalesces are added to it such that we end up with a straightforward stack
of desired coalesces in order of important (most to least).  These routines
will no doubt be modified as we statr to use them, but this is the initial cut.

The next step is to simply recalculate the live range information, build
an interference graph and related coalesce list, and then coalesce memory locations. 
With these infrastructure changes, it should be a fairly quick task, especially
since everything except the coalesce_list has already been uased and debugged.

This has been bootstrapped on x86 and introduces no new failures. There is a
fairly minor compile time hit in the out-of-ssa pass, mostly due to a few extra
bit vectors and the movement of conflict graph size reduction from var_maps
to the tpa_p structures. (The conflict graph is slightly larger in size, but
has the same number of conflicts). This was required in order to allow for a
similarly automatically sparse type-based conflict graph. Once the type-based coalescing
is done, I'll revisit if there is any sillyness going on.

Oh, the compile time hit on compiling all of gcc is that the out-of-ssa pass
takes a cumulative 5.5 second (ballpark) on my machine instead of 5.1 seconds.

So is it OK to check this in, or do you want me to wait? I know Diego is
looking at a mini-merge... This oughtn't affect it too much since its
pretty localized, but I've already checked in stuff yesterday which
probably made life a little more miserable :-)

Dunno if I want to do it 2 days in a row or not :-)

Andrew



2003-07-23  Andrew MacLeod  <amacleod@redhat.com>

	* common.opt (ftree-combine-temps): Add new option.
	* flags.h (flag_tree_combine_temps): New flag.
	* opts.c (decode_options): Initialize flag_tree_combine_temps.
	(common_handle_option): Handle new flag.
	* toplev.c (flag_tree_combine_temps): Declare.
	(lang_independent_options f): Add tree-combine-temp.
	* tree-ssa-live.c (var_union): When combining 2 root variables, choose 
	the user variable over a temporary as the new variable.
	(compact_var_map): Use renamed root_var routines.
	(calculate_live_on_exit): New parameter. Add ability to treat PHI 
	nodes as copies in their source block.
	(tpa_init): Initialize a tpa object.
	(tpa_remove_partition): Remove a partition from a tpa list.
	(tpa_delete): Delete a tpa object.
	(tpa_compact): Hide single elemenet lists.
	(root_var_init): Split common part into tpa_init and rename.
	(remove_root_var_partition, delete_root_va, dump_root_var): Delete.
	(type_var_init): New. Initialize a type_var object.
	(create_coalesce_list): New. Create a coalesce_list object.
	(delete_coalesce_list): New. Free a coalesce list's memory.
	(find_partition_pair): New. Find a coalesce pair in a coalesce list.
	(add_coalesce): New. Add a coalesce between 2 partitions.
	(sort_coalesce_list): New. Sort coalesce pairs by importance.
	(pop_best_coalesce): New. Get best remaining pair to coalesce.
	(add_conflicts_if_valid): Move from tree-ssa.c.
	(build_tree_conflict_graph): Move from coalesce_ssa_name in tree-ssa.c.
	Genericize to use tpa_p instead of root_var object. Don't add 
	interferences between copies. Update coalesce list.
	(coalesce_tpa_members): Move from coalesce_ssa_name in tree-ssa.c. Use
	tpa_p instead of root_var.
	(dump_coalesce_list): New. Show debug info for a coalesce list.
	(tpa_dump): Rename from dump_root_var and genericize to use tpa_p.
	* tree-ssa-live.h (root_var_p): Rename structure type to tpa_p
	(tpa_num_trees, tpa_tree, tpa_first_partition, tpa_next_partition, 
	tpa_find_tree): New. Generic versions of existing root_var routines.
	(tpa_decompact): New. Include single version lists.
	(root_var_p): Declare as type tpa_p.
	(root_var_num, root_var, root_var_first_partition, 
	root_var_next_partition, root_var_dump, root_var_delete,
	root_var_remove_partition, root_var_find , root_var_compac,
	root_var_decompac): Rename and call generic versions.
	(type_var_p): New. Use tpa_p structure for a type based association.
	(type_var_num, type_var, type_var_first_partition, 
	type_var_next_partition, type_var_dump, type_var_delete,
	type_var_remove_partition, type_var_find, type_var_compact, 
	type_var_decompact): New. Call generic versions of the routine.
	(struct partition_pair_d): New. Represent a desired coalesce.
	(struct coalesce_list_d): New. Organize lists of desired coalesces.
	(NO_BEST_COALESCE): Define value.
	* tree-ssa.c (set_if_valid): Remove.
	(add_conflicts_if_valid): Remove. Move to tree-ssa-live.c.
	(print_exprs): New. Routine for commonly used output format.
	(coalesce_abnormal_edges): New. Split from coalece_ssa_name. Force
	partition coalesces across abnormal edges.
	(coalesce_ssa_name): Split out build_tree_conflict_graph, 
	coalesce_abnormal_edges, and coalesce_tpa_members. Return live
	range info if required. Use renamed root_var routines.
	(assign_vars): Use renamed root_var routines.
	(replace_variable): Mark as inline.
	(rewrite_out_of_ssa): Don't compact varmap anymore. Free live range
	info if aquired.



Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.14.2.1
diff -c -p -r1.14.2.1 common.opt
*** common.opt	21 Jul 2003 13:50:32 -0000	1.14.2.1
--- common.opt	23 Jul 2003 13:46:03 -0000
*************** Common
*** 538,543 ****
--- 538,546 ----
  ftree-dce
  Common
  
+ ftree-combine-temps
+ Common
+ 
  ftree-dominator-opts
  Common
  
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.86.2.30
diff -c -p -r1.86.2.30 flags.h
*** flags.h	21 Jul 2003 13:50:46 -0000	1.86.2.30
--- flags.h	23 Jul 2003 13:46:03 -0000
*************** extern int flag_tree_copyprop;
*** 701,706 ****
--- 701,709 ----
  /* Enable SSA-DCE on trees.  */
  extern int flag_tree_dce;
  
+ /* Enable SSA->normal pass memory location coalescing.  */
+ extern int flag_tree_combine_temps;
+ 
  /* Enable dominator optimizations while re-writing into SSA form.  */
  extern int flag_tree_dom;
  
Index: opts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/opts.c,v
retrieving revision 1.31.2.1
diff -c -p -r1.31.2.1 opts.c
*** opts.c	21 Jul 2003 13:50:56 -0000	1.31.2.1
--- opts.c	23 Jul 2003 13:46:04 -0000
*************** decode_options (unsigned int argc, const
*** 491,496 ****
--- 491,497 ----
        flag_tree_ccp = 1;
        flag_tree_dce = 1;
        flag_tree_copyprop = 1;
+       flag_tree_combine_temps = 1;
        flag_tree_dom = 1;
      }
  
*************** common_handle_option (size_t scode, cons
*** 1345,1350 ****
--- 1346,1355 ----
  
      case OPT_ftree_dce:
        flag_tree_dce = value;
+       break;
+ 
+     case OPT_ftree_combine_temps:
+       flag_tree_combine_temps = value;
        break;
  
      case OPT_ftree_dominator_opts:
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.654.2.59
diff -c -p -r1.654.2.59 toplev.c
*** toplev.c	21 Jul 2003 13:51:04 -0000	1.654.2.59
--- toplev.c	23 Jul 2003 13:46:06 -0000
*************** int flag_tree_dce = 0;
*** 973,978 ****
--- 973,981 ----
  /* Enable promotion of virtual to real operands in must-alias situations.  */
  int flag_tree_must_alias = 0;
  
+ /* Enable SSA->normal pass memory location coalescing.  */
+ int flag_tree_combine_temps = 0;
+ 
  /* Enable dominator optimizations while re-writing into SSA form.  */
  int flag_tree_dom = 0;
  
*************** static const lang_independent_options f_
*** 1332,1338 ****
    { "tree-dominator-opts", &flag_tree_dom, 1,
     N_("Enable dominator optimizations while re-writing into SSA form") },
    { "tree-must-alias", &flag_tree_must_alias, 1,
!    N_("Detect must-alias relations to remove pointer de-references") }
  };
  
  /* Table of language-specific options.  */
--- 1335,1344 ----
    { "tree-dominator-opts", &flag_tree_dom, 1,
     N_("Enable dominator optimizations while re-writing into SSA form") },
    { "tree-must-alias", &flag_tree_must_alias, 1,
!    N_("Detect must-alias relations to remove pointer de-references") },
!   { "tree-combine-temps", &flag_tree_combine_temps, 1,
!    N_("Coalesce memory temporaries in the SSA->normal pass.") }
! 
  };
  
  /* Table of language-specific options.  */
Index: tree-ssa-live.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-live.c,v
retrieving revision 1.1.2.12
diff -c -p -r1.1.2.12 tree-ssa-live.c
*** tree-ssa-live.c	22 Jul 2003 18:36:38 -0000	1.1.2.12
--- tree-ssa-live.c	23 Jul 2003 13:46:06 -0000
*************** static inline void set_if_valid (var_map
*** 47,53 ****
  static inline void add_livein_if_notdef (tree_live_info_p, sbitmap,
  					 tree, basic_block);
  static inline void register_ssa_partition (var_map, tree);
! 
  
  /* This is where the mapping from SSA version number to real storage variable
     is tracked.  
--- 47,55 ----
  static inline void add_livein_if_notdef (tree_live_info_p, sbitmap,
  					 tree, basic_block);
  static inline void register_ssa_partition (var_map, tree);
! static inline void add_conflicts_if_valid (tpa_p, conflict_graph,
! 					   var_map, sbitmap, tree);
! static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool);
  
  /* This is where the mapping from SSA version number to real storage variable
     is tracked.  
*************** var_union (var_map map, tree var1, tree 
*** 157,163 ****
          p2 = map->compact_to_partition[p2];
        if (root_var != NULL_TREE)
          return -1;
!       root_var = var2;
      }
  
    if (p1 == NO_PARTITION || p2 == NO_PARTITION)
--- 159,169 ----
          p2 = map->compact_to_partition[p2];
        if (root_var != NULL_TREE)
          return -1;
!       /* If there is no root_var set, or its not a user variable, set the
! 	 root_var to this one.  */
!       if (!root_var || is_gimple_tmp_var (root_var))
! 	root_var = var2;
!       
      }
  
    if (p1 == NO_PARTITION || p2 == NO_PARTITION)
*************** compact_var_map (var_map map, int flags)
*** 220,226 ****
      }
  
    if (flags & VARMAP_NO_SINGLE_DEFS)
!     rv = init_root_var (map);
  
    map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
    memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
--- 226,232 ----
      }
  
    if (flags & VARMAP_NO_SINGLE_DEFS)
!     rv = root_var_init (map);
  
    map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
    memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
*************** compact_var_map (var_map map, int flags)
*** 236,245 ****
  	     in the root_var table, if one is available.  */
  	  if (rv)
  	    {
! 	      root = find_root_var (rv, tmp);
! 	      root_i = first_root_var_partition (rv, root);
  	      /* If there is only one, don't include this in the compaction.  */
! 	      if (next_root_var_partition (rv, root_i) == ROOT_VAR_NONE)
  	        continue;
  	    }
  	  SET_BIT (used, tmp);
--- 242,251 ----
  	     in the root_var table, if one is available.  */
  	  if (rv)
  	    {
! 	      root = root_var_find (rv, tmp);
! 	      root_i = root_var_first_partition (rv, root);
  	      /* If there is only one, don't include this in the compaction.  */
! 	      if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE)
  	        continue;
  	    }
  	  SET_BIT (used, tmp);
*************** compact_var_map (var_map map, int flags)
*** 272,278 ****
    map->num_partitions = count;
  
    if (rv)
!     delete_root_var (rv);
    sbitmap_free (used);
  }
  
--- 278,284 ----
    map->num_partitions = count;
  
    if (rv)
!     root_var_delete (rv);
    sbitmap_free (used);
  }
  
*************** calculate_live_on_entry (var_map map)
*** 595,601 ****
  /* Calculate the live on exit vectors.  */
  
  void
! calculate_live_on_exit (tree_live_info_p liveinfo)
  {
    unsigned b;
    int i;
--- 601,607 ----
  /* Calculate the live on exit vectors.  */
  
  void
! calculate_live_on_exit (tree_live_info_p liveinfo, bool phi_as_copy)
  {
    unsigned b;
    int i;
*************** calculate_live_on_exit (tree_live_info_p
*** 609,628 ****
    on_exit = sbitmap_vector_alloc (n_basic_blocks, num_var_partitions (map));
    sbitmap_vector_zero (on_exit, n_basic_blocks);
  
!   /* Set all the live-on-exit bits for uses in PHIs.  */
!   FOR_EACH_BB (bb)
      {
!       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
          {
! 	  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
! 	    { 
! 	      t = PHI_ARG_DEF (phi, i);
! 	      e = PHI_ARG_EDGE (phi, i);
! 	      if (TREE_CONSTANT (t) || e->src == ENTRY_BLOCK_PTR)
! 	        continue;
! 	      set_if_valid (map, on_exit[e->src->index], t);
! 	    }
! 
  	}
      }
  
--- 615,635 ----
    on_exit = sbitmap_vector_alloc (n_basic_blocks, num_var_partitions (map));
    sbitmap_vector_zero (on_exit, n_basic_blocks);
  
!   /* If we aren't treating PHI's as copies at the end of their blocks, set all
!      the live-on-exit bits for uses in PHIs.  */
!   if (!phi_as_copy)
      {
!       FOR_EACH_BB (bb)
          {
! 	  for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
! 	    for (i = 0; i < PHI_NUM_ARGS (phi); i++)
! 	      { 
! 		t = PHI_ARG_DEF (phi, i);
! 		e = PHI_ARG_EDGE (phi, i);
! 		if (TREE_CONSTANT (t) || e->src == ENTRY_BLOCK_PTR)
! 		  continue;
! 		set_if_valid (map, on_exit[e->src->index], t);
! 	      }
  	}
      }
  
*************** calculate_live_on_exit (tree_live_info_p
*** 642,670 ****
  }
  
  
! /* Initialize a root_var object.  */
  
! root_var_p
! init_root_var (var_map map)
  {
!   root_var_p rv;
    int num_partitions = num_var_partitions (map);
    int x;
-   tree t;
-   var_ann_t ann;
  
    if (num_partitions == 0)
      return NULL;
  
!   rv = (root_var_p) xmalloc (sizeof (struct root_var_d));
!   rv->num_root_vars = 0;
!   rv->map = map;
!   rv->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
!   memset (rv->next_partition, ROOT_VAR_NONE, num_partitions * sizeof (int));
  
    x = MAX (40, (num_partitions / 20));
!   VARRAY_TREE_INIT (rv->root_var, x, "root_var");
!   VARRAY_INT_INIT (rv->first_partition, x, "first_partition");
  
    /* Start at the end and work towards the front. This will provide a list
       that is ordered from smallest to largest.  */
--- 649,806 ----
  }
  
  
! /* Initialize a tree_partition_associator object.  */
  
! tpa_p
! tpa_init (var_map map)
  {
!   tpa_p tpa;
    int num_partitions = num_var_partitions (map);
    int x;
  
    if (num_partitions == 0)
      return NULL;
  
!   tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
!   tpa->num_trees = 0;
!   tpa->uncompressed_num = -1;
!   tpa->map = map;
!   tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
!   memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
! 
!   VARRAY_INT_INIT (tpa->partition_to_tree_map, num_partitions, "tree_map");
  
    x = MAX (40, (num_partitions / 20));
!   VARRAY_TREE_INIT (tpa->trees, x, "trees");
!   VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
! 
!   return tpa;
! 
! }
! 
! /* Remove a partition from a TPA's list.  */
! 
! void
! tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
! {
!   int i;
! 
!   i = tpa_first_partition (tpa, tree_index);
!   if (i == partition_index)
!     {
!       VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i];
!     }
!   else
!     {
!       for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
!         {
! 	  if (tpa->next_partition[i] == partition_index)
! 	    {
! 	      tpa->next_partition[i] = tpa->next_partition[partition_index];
! 	      break;
! 	    }
! 	}
!     }
! }
! 
! /* Free the memory used by a tree_partition_associator object.  */
! void
! tpa_delete (tpa_p tpa)
! {
!   if (!tpa)
!     return;
! 
!   free (tpa->next_partition);
!   free (tpa);
! }
! 
! 
! /* This routine will remove any tree entires which have only a single
!    element.  This will help keep the size of the conflict graph down.  
!    The function returns the number of remaining tree lists.  */
! 
! int 
! tpa_compact (tpa_p tpa)
! {
!   int last, x, y, first, swap_i;
!   tree swap_t;
! 
!   /* Find the last list which has more than 1 partition.  */
!   for (last = tpa->num_trees - 1; last > 0; last--)
!     {
!       first = tpa_first_partition (tpa, last);
!       if (tpa_next_partition (tpa, first) != NO_PARTITION)
!         break;
!     }
! 
!   x = 0;
!   while (x < last)
!     {
!       first = tpa_first_partition (tpa, x);
!       /* If there is not more than one partition, swap with the current end
! 	 of the tree list.  */
!       if (tpa_next_partition (tpa, first) == NO_PARTITION)
!         {
! 	  swap_t = VARRAY_TREE (tpa->trees, last);
! 	  swap_i = VARRAY_INT (tpa->first_partition, last);
! 
! 	  /* Update the last entry. Since it is known to only have one
! 	     partition, there is nothing else to update.  */
! 	  VARRAY_TREE (tpa->trees, last) = VARRAY_TREE (tpa->trees, x);
! 	  VARRAY_INT (tpa->first_partition, last) 
! 	    = VARRAY_INT (tpa->first_partition, x);
! 	  VARRAY_INT (tpa->partition_to_tree_map, 
! 		      tpa_first_partition (tpa, last)) = last;
! 
! 	  /* Since this list is known to have more than one partition, update
! 	     the list owner entries.  */
! 	  VARRAY_TREE (tpa->trees, x) = swap_t;
! 	  VARRAY_INT (tpa->first_partition, x) = swap_i;
! 	  for (y = tpa_first_partition (tpa, x); 
! 	       y != NO_PARTITION; 
! 	       y = tpa_next_partition (tpa, y))
! 	    VARRAY_INT (tpa->partition_to_tree_map, y) = x;
! 
! 	  /* Ensure last is a list with more than one partition.  */
! 	  last--;
! 	  for (; last > x; last--)
! 	    {
! 	      first = tpa_first_partition (tpa, last);
! 	      if (tpa_next_partition (tpa, first) != NO_PARTITION)
! 		break;
! 	    }
! 	}
!       x++;
!     }
! 
!   first = tpa_first_partition (tpa, x);
!   if (tpa_next_partition (tpa, first) != NO_PARTITION)
!     x++;
!   tpa->uncompressed_num = tpa->num_trees;
!   tpa->num_trees = x;
!   return last;
! }
! 
! 
! /* Initialize a root_var object with SSA partitions which are based on each root
!    variable.  */
! 
! root_var_p
! root_var_init (var_map map)
! {
!   root_var_p rv;
!   int num_partitions = num_var_partitions (map);
!   int x, p;
!   tree t;
!   var_ann_t ann;
!   sbitmap seen;
! 
!   rv = tpa_init (map);
!   if (!rv)
!     return NULL;
! 
!   seen = sbitmap_alloc (num_partitions);
!   sbitmap_zero (seen);
  
    /* Start at the end and work towards the front. This will provide a list
       that is ordered from smallest to largest.  */
*************** init_root_var (var_map map)
*** 674,771 ****
        /* The var map may not be compacted yet, so check for NULL.  */
        if (!t) 
          continue;
        if (TREE_CODE (t) == SSA_NAME)
  	t = SSA_NAME_VAR (t);
        ann = var_ann (t);
        if (ann->root_var_processed)
          {
! 	  rv->next_partition[x] = VARRAY_INT (rv->first_partition, 
  					      VAR_ANN_ROOT_INDEX (ann));
! 	  VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = x;
  	}
        else
          {
  	  ann->root_var_processed = 1;
! 	  VAR_ANN_ROOT_INDEX (ann) = rv->num_root_vars++;
! 	  VARRAY_PUSH_TREE (rv->root_var, t);
! 	  VARRAY_PUSH_INT (rv->first_partition, x);
  	}
      }
  
    /* Reset the out_of_ssa_tag flag on each variable for later use.  */
!   for (x = 0; x < rv->num_root_vars; x++)
      {
!       t = VARRAY_TREE (rv->root_var, x);
        var_ann (t)->root_var_processed = 0;
      }
  
    return rv;
  }
  
- /* Remove a partition form a root_var's list.  */
  
! void
! remove_root_var_partition (root_var_p rv, int root_index, int partition_index)
  {
!   int i;
  
!   i = first_root_var_partition (rv, root_index);
!   if (i == partition_index)
      {
!       VARRAY_INT (rv->first_partition, root_index) = rv->next_partition[i];
      }
    else
      {
!       for ( ; i != ROOT_VAR_NONE; i = next_root_var_partition (rv, i))
          {
! 	  if (rv->next_partition[i] == partition_index)
  	    {
! 	      rv->next_partition[i] = rv->next_partition[partition_index];
! 	      break;
  	    }
  	}
      }
  }
  
! /* Free the memory used by a root_var object.  */
  void
! delete_root_var (root_var_p rv)
  {
!   if (!rv)
!     return;
  
!   free (rv->next_partition);
!   free (rv);
  }
  
  
! /* Output a root_var object.  */
  void
! dump_root_var (FILE *f, root_var_p rv)
  {
    int x, i;
  
!   if (!rv)
      return;
  
!   fprintf (f, "Root Var dump\n");
!   for (x = 0; x < num_root_vars (rv); x++)
      {
!       print_generic_expr (f, root_var (rv, x), TDF_SLIM);
        fprintf (f, " : (");
!       for (i = first_root_var_partition (rv, x); 
! 	   i != ROOT_VAR_NONE;
! 	   i = next_root_var_partition (rv, i))
  	{
! 	  print_generic_expr (f, partition_to_var (rv->map, i), TDF_SLIM);
  	  fprintf (f, " ");
  	}
        fprintf (f, ")\n");
      }
!   fprintf (f, ")\n");
  }
- 
- 
  
  /* Output a partition.  */
  
--- 810,1404 ----
        /* The var map may not be compacted yet, so check for NULL.  */
        if (!t) 
          continue;
+ 
+       p = var_to_partition (map, t);
+ #ifdef ENABLE_CHECKING
+       if (p == NO_PARTITION)
+         abort ();
+ #endif
+       /* Make sure we only put coalesced partitions into the list once.  */
+       if (TEST_BIT (seen, p))
+         continue;
+       SET_BIT (seen, p);
        if (TREE_CODE (t) == SSA_NAME)
  	t = SSA_NAME_VAR (t);
        ann = var_ann (t);
        if (ann->root_var_processed)
          {
! 	  rv->next_partition[p] = VARRAY_INT (rv->first_partition, 
  					      VAR_ANN_ROOT_INDEX (ann));
! 	  VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = p;
  	}
        else
          {
  	  ann->root_var_processed = 1;
! 	  VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
! 	  VARRAY_PUSH_TREE (rv->trees, t);
! 	  VARRAY_PUSH_INT (rv->first_partition, p);
  	}
+       VARRAY_INT (rv->partition_to_tree_map, p) = VAR_ANN_ROOT_INDEX (ann);
      }
  
    /* Reset the out_of_ssa_tag flag on each variable for later use.  */
!   for (x = 0; x < rv->num_trees; x++)
      {
!       t = VARRAY_TREE (rv->trees, x);
        var_ann (t)->root_var_processed = 0;
      }
  
+   sbitmap_free (seen);
    return rv;
  }
  
  
! /* Initialize a type_var structure which associates all the partitions of the
!    same type to the type node. Volatiles are ignored.  */
! 
! type_var_p
! type_var_init (var_map map)
  {
!   type_var_p tv;
!   int x, y, p;
!   int num_partitions = num_var_partitions (map);
!   tree t;
!   sbitmap seen;
  
!   seen = sbitmap_alloc (num_partitions);
!   sbitmap_zero (seen);
! 
!   tv = tpa_init (map);
!   if (!tv)
!     return NULL;
! 
!   for (x = num_partitions - 1; x >= 0; x--)
!     {
!       t = partition_to_var (map, x);
!       if (!t || TREE_THIS_VOLATILE (t))
!         continue;
!       p = var_to_partition (map, t);
! #ifdef ENABLE_CHECKING
!       if (p == NO_PARTITION)
!         abort ();
! #endif
!       /* If partitions have been coalesced, only add the representative for the
! 	 partition to the list once.  */
!       if (TEST_BIT (seen, p))
!         continue;
!       SET_BIT (seen, p);
!       t = TREE_TYPE (t);
! 
!       /* Find the list for this type.  */
!       for (y = 0; y < tv->num_trees; y++)
!         if (t == VARRAY_TREE (tv->trees, y))
! 	  break;
!       if (y == tv->num_trees)
!         {
! 	  tv->num_trees++;
! 	  VARRAY_PUSH_TREE (tv->trees, t);
! 	  VARRAY_PUSH_INT (tv->first_partition, p);
! 	}
!       else
!         {
! 	  tv->next_partition[p] = VARRAY_INT (tv->first_partition, y);
! 	  VARRAY_INT (tv->first_partition, y) = p;
! 	}
!       VARRAY_INT (tv->partition_to_tree_map, p) = y;
!     }
!   sbitmap_free (seen);
!   return tv;
! }
! 
! 
! /* Create a coalesce list object that is empty.  */
! 
! coalesce_list_p 
! create_coalesce_list (var_map map)
! {
!   coalesce_list_p list;
! 
!   list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
! 
!   list->map = map;
!   list->add_mode = true;
!   list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
! 					     sizeof (struct partition_pair_d));
!   return list;
! }
! 
! 
! /* Delete a coalesce list.  */
! 
! void 
! delete_coalesce_list (coalesce_list_p cl)
! {
!   free (cl->list);
!   free (cl);
! }
! 
! /* Find a matching coalesce pair. If one isn't found, return NULL if 'create' 
!    is false, otherwise create a new coalesce object and return it.  */
! 
! static partition_pair_p
! find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
! {
!   partition_pair_p node, tmp;
!   int s;
!     
!   /* Normalize so that p1 is the smaller value.  */
!   if (p2 < p1)
!     {
!       s = p1;
!       p1 = p2;
!       p2 = s;
!     }
!   
!   tmp = NULL;
! 
!   /* The list is sorted such that if we find a value greater than p2,
!      p2 is not in the list.  */
!   for (node = cl->list[p1]; node; node = node->next)
!     {
!       if (node->second_partition == p2)
!         return node;
!       else
!         if (node->second_partition > p2)
! 	  break;
!      tmp = node;
!     }
! 
!   if (!create)
!     return NULL;
! 
!   node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
!   node->first_partition = p1;
!   node->second_partition = p2;
!   node->cost = 0;
!     
!   if (tmp != NULL)
      {
!       node->next = tmp->next;
!       tmp->next = node;
      }
    else
      {
!       /* This is now the first node in the list.  */
!       node->next = cl->list[p1];
!       cl->list[p1] = node;
!     }
! 
!   return node;
! }
! 
! /* Add a pair of partitions to the coalesce list with a specified cost.  */
! 
! void 
! add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
! {
!   partition_pair_p node;
! 
! #ifdef ENABLE_CHECKING
!   if (!cl->add_mode)
!     abort();
! #endif
! 
!   if (p1 == p2)
!     return;
! 
!   node = find_partition_pair (cl, p1, p2, true);
! 
!   node->cost += value;
! }
! 
! 
! /* Prepare the coalesce list for removal of preferred pairs.  When finished,
!    list element 0 has all the coalesce pairs, sorted in order from most
!    impoortant coalesce to least important.  */
! 
! void 
! sort_coalesce_list (coalesce_list_p cl)
! {
!   int x, num, last, val;
!   partition_pair_p n1, n1_prev ,n2, n2_end, n2_last;
! 
!   if (!cl->add_mode)
!     abort();
! 
!   cl->add_mode = false;
!   last = 0;
! 
!   /* Compact the list so we know how many lists there are.  */
!   num = num_var_partitions (cl->map);
!   for (x = 0; x < num; x++)
!     if (cl->list[x] != NULL)
!       {
!         if (x != last)
! 	  cl->list[last] = cl->list[x];
! 	last++;
!       }
! 
!   num = last;
! 
!   /* While there is more than one list, merge lists in pairs until only
!      1 list remains.  */
!   while (num > 1)
!     {
!       last = 0;
!       for (x = 0; x < num; x += 2)
          {
! 	  n1 = cl->list[x];
! 	  n2 = cl->list[x+1];
! 	  for (n1_prev = NULL; n1 ; n1 = n1->next)
  	    {
! 	      val = n1->second_partition;
! 	      if (n2->second_partition  <= val)
! 		{
! 		  n2_last = n2;
! 		  /* Merge as many as will fit before n1.  */
! 		  for (n2_end = n2; n2_end; n2_end = n2_end->next)
! 		    {
! 		      if (n2_end->second_partition > val)
! 			break;
! 		      n2_last = n2_end;
! 		    }
! 		  if (n1_prev)
! 		    {
! 		      n2_last->next = n1;
! 		      n1_prev->next = n2;
! 		    }
! 		  else
! 		    {
! 		      n2_last->next = n1;
! 		      cl->list[x] = n2;
! 		    }
! 		  n2 = n2_end;
! 		}
! 	      n1_prev = n1;
! 	    }
! 	  /* Append anything left over should be appended to the end.  */
! 	  if (!n2)
! 	    n1_prev->next = n2;
! 	  cl->list[last++] = cl->list[x];
! 	}
! 
!       /* If there were an odd number of lists, move the last one up as well.  */
!       if (x % 2 != 0)
! 	cl->list[last++] = cl->list[num];
! 
!       num = last;
!     }
! }
! 
! 
! /* Retrieve the best remaining pair to coalesce.  Returns the 2 partitions
!    via parameters, and their calculated cost via the return value. The return
!    value is NO_BEST_COALESCE if the coalesce list is empty.  */
! 
! int 
! pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
! {
!   partition_pair_p node;
!   int ret;
! 
!   if (cl->add_mode)
!     abort();
! 
!   node = cl->list[0];
!   if (!node)
!     return NO_BEST_COALESCE;
! 
!   cl->list[0] = node->next;
! 
!   *p1 = node->first_partition;
!   *p2 = node->second_partition;
!   ret = node->cost;
!   free (node);
! 
!   return ret;
! }
! 
! /* If a variable is in a partition, and it's not already live, add a 
!    conflict between it and any other live partition.  Reset the live bit.  */
! 
! static inline void 
! add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
! 			var_map map, sbitmap vec, tree var)
! { 
!   int p, y, first;
!   p = var_to_partition (map, var);
!   if (p != NO_PARTITION)
!     { 
!       RESET_BIT (vec, p);
!       first = tpa_find_tree (tpa, p);
!       /* If find returns nothing, this object isn't interesting.  */
!       if (first == TPA_NONE)
!         return;
!       /* Only add interferences between objects in the same list.  */
!       for (y = tpa_first_partition (tpa, first);
! 	   y != TPA_NONE;
! 	   y = tpa_next_partition (tpa, y))
! 	{
! 	  if (TEST_BIT (vec, y))
! 	    conflict_graph_add (graph, p, y);
! 	}
!     }
! }
! 
! 
! /* Build a conflict graph for the information contained in a live range
!    information structure.  If a coalesce list is passed in, any copies
!    discovered are added to the list.  */
! 
! conflict_graph
! build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, 
! 			   coalesce_list_p cl)
! {
!   conflict_graph graph;
!   var_map map;
!   sbitmap live;
!   int num, x, y;
!   basic_block bb;
!   varray_type stmt_stack, ops;
!   tree stmt, *var_p, var;
! 
!   map = live_var_map (liveinfo);
!   graph = conflict_graph_new (num_var_partitions (map));
! 
!   if (tpa_num_trees (tpa) == 0)
!     return graph;
! 
!   live = sbitmap_alloc (num_var_partitions (map));
! 
!   FOR_EACH_BB (bb)
!     {
!       /* Start with live on exit temporaries.  */
!       sbitmap_copy (live, live_on_exit (liveinfo, bb));
! 
!       FOR_EACH_STMT_IN_REVERSE (stmt_stack, bb, stmt)
!         {
! 	  tree important_copy_rhs_partition = NULL_TREE;
! 
! 	  get_stmt_operands (stmt);
! 
! 	  /* Copies between 2 partitions do not introduce an interference 
! 	     by itself.  If they did, you would never be able to coalesce 
! 	     two things which are copied. If the two variables really do 
! 	     conflict, they will conflict elsewhere in the program.  
! 	     
! 	     This is handled specially here since we may also be interested 
! 	     in copies between real variables and SSA_NAME variables. We may
! 	     be interested in trying to coalesce SSA_NAME variables with
! 	     root variables in some cases.   */
! 
! 	  if (TREE_CODE (stmt) == MODIFY_EXPR)
! 	    {
! 	      tree lhs = TREE_OPERAND (stmt, 0);
! 	      tree rhs = TREE_OPERAND (stmt, 1);
! 	      int p1, p2;
! 	      int bit;
! 
! 	      if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
! 		p1 = var_to_partition (map, lhs);
! 	      else 
! 		p1 = NO_PARTITION;
! 
! 	      if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
! 		p2 = var_to_partition (map, rhs);
! 	      else 
! 		p2 = NO_PARTITION;
! 
! 	      if (p1 != NO_PARTITION && p2 != NO_PARTITION)
! 		{
! 		  important_copy_rhs_partition = rhs;
! 		  bit = TEST_BIT (live, p2);
! 		  /* If the RHS is live, make it not live while we add
! 		     the conflicts, then make it live again.  */
! 		  if (bit)
! 		    RESET_BIT (live, p2);
! 		  add_conflicts_if_valid (tpa, graph, map, live, lhs);
! 		  if (bit)
! 		    SET_BIT (live, p2);
! 		  if (cl)
! 		    add_coalesce (cl, p1, p2, 1);
! 		}
! 	    }
! 
! 	  if (!important_copy_rhs_partition)
! 	    {
! 	      ops = def_ops (stmt);
! 	      num = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! 	      for (x = 0; x < num; x++)
! 		{
! 		  var_p = VARRAY_GENERIC_PTR (ops, x);
! 		  add_conflicts_if_valid (tpa, graph, map, live, *var_p);
! 		}
! 	    }
! 
! 	  ops = vdef_ops (stmt);
! 	  num = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! 	  for (x = 0; x < num; x++)
! 	    {
! 	      var = VDEF_RESULT (VARRAY_TREE (ops, x));
! 	      add_conflicts_if_valid (tpa, graph, map, live, var);
! 	    }
! 
! 	  if (important_copy_rhs_partition)
! 	    set_if_valid (map, live, important_copy_rhs_partition);
! 	  else
! 	    {
! 	      ops = use_ops (stmt);
! 	      num = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! 	      for (x = 0; x < num; x++)
! 		{
! 		  var_p = VARRAY_GENERIC_PTR (ops, x);
! 		  set_if_valid (map, live, *var_p);
! 		}
! 	    }
! 
! 	  ops = vuse_ops (stmt);
! 	  num = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! 	  for (x = 0; x < num; x++)
! 	    {
! 	      var = VARRAY_TREE (ops, x);
! 	      set_if_valid (map, live, var);
! 	    }
!  
! 	  ops = vdef_ops (stmt);
! 	  num = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! 	  for (x = 0; x < num; x++)
! 	    {
! 	      var = VDEF_OP (VARRAY_TREE (ops, x));
! 	      set_if_valid (map, live, var);
  	    }
  	}
+ 
+       /* Anything which is still live at this point interferes.  */
+ 
+       EXECUTE_IF_SET_IN_SBITMAP (live, 0, x,
+         {
+ 	  for (y = tpa_first_partition (tpa, tpa_find_tree (tpa, x));
+ 	       y != TPA_NONE;
+ 	       y = tpa_next_partition (tpa, y))
+ 	    {
+ 	      if (x != y && TEST_BIT (live, y))
+ 		conflict_graph_add (graph, x, y);
+ 	    }
+ 
+ 	});
      }
+ 
+   sbitmap_free (live);
+   return graph;
  }
  
! 
  void
! coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map)
  {
!   int x, y, z;
!   tree var, tmp;
  
!   for (x = 0; x < tpa_num_trees (tpa); x++)
!     {
!       while (tpa_first_partition (tpa, x) != TPA_NONE)
!         {
! 	  /* Coalesce first partition with everything that doesn't conflict.  */
! 	  y = tpa_first_partition (tpa, x);
! 	  tpa_remove_partition (tpa, x, y);
! 	  var = partition_to_var (map, y);
! 	  for (z = tpa_next_partition (tpa, y); 
! 	       z != TPA_NONE; 
! 	       z = tpa_next_partition (tpa, z))
! 	    {
! 	      tmp = partition_to_var (map, z);
! 	      /* If partitions are already merged, don't check for conflict.  */
! 	      if (tmp == var)
! 	        tpa_remove_partition (tpa, x, z);
! 	      else if (!conflict_graph_conflict_p (graph, y, z))
! 		{
! 		  var_union (map, var, tmp);
! 		  tpa_remove_partition (tpa, x, z);
! 		  conflict_graph_merge_regs (graph, y, z);
! 		}
! 	    }
! 	}
!     }
  }
  
+ /* Show debug info for a coalesce list.  */
+ void 
+ dump_coalesce_list (FILE *f, coalesce_list_p cl)
+ {
+   partition_pair_p node;
+   int x, num;
+   tree var;
  
!   if (cl->add_mode)
!     {
!       fprintf (f, "Coalesce List:\n");
!       num = num_var_partitions (cl->map);
!       for (x = 0; x < num; x++)
!         {
! 	  node = cl->list[x];
! 	  if (node)
! 	    {
! 	      fprintf (f, "[");
! 	      print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
! 	      fprintf (f, "] - ");
! 	      for ( ; node; node = node->next)
! 	        {
! 		  var = partition_to_var (cl->map, node->second_partition);
! 		  print_generic_expr (f, var, TDF_SLIM);
! 		  fprintf (f, "(%1d), ", node->cost);
! 		}
! 	      fprintf (f, "\n");
! 	    }
! 	}
!     }
!   else
!     {
!       fprintf (f, "Sorted Coalesce list:\n");
!       for (node = cl->list[0]; node; node = node->next)
!         {
! 	  fprintf (f, "(%d) ", node->cost);
! 	  var = partition_to_var (cl->map, node->first_partition);
! 	  print_generic_expr (f, var, TDF_SLIM);
! 	  fprintf (f, " : ");
! 	  var = partition_to_var (cl->map, node->second_partition);
! 	  print_generic_expr (f, var, TDF_SLIM);
! 	  fprintf (f, "\n");
! 	}
!     }
! }
! 
! 
! /* Output a tree_partition_associator object.  */
  void
! tpa_dump (FILE *f, tpa_p tpa)
  {
    int x, i;
  
!   if (!tpa)
      return;
  
!   for (x = 0; x < tpa_num_trees (tpa); x++)
      {
!       print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
        fprintf (f, " : (");
!       for (i = tpa_first_partition (tpa, x); 
! 	   i != TPA_NONE;
! 	   i = tpa_next_partition (tpa, i))
  	{
! 	  print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
  	  fprintf (f, " ");
+ #ifdef ENABLE_CHECKING
+ 	  if (tpa_find_tree (tpa, i) != x)
+ 	    fprintf (f, "**find tree incorrectly set** ");
+ #endif
  	}
        fprintf (f, ")\n");
      }
!   fflush (f);
  }
  
  /* Output a partition.  */
  
Index: tree-ssa-live.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-live.h,v
retrieving revision 1.1.2.6
diff -c -p -r1.1.2.6 tree-ssa-live.h
*** tree-ssa-live.h	22 Jul 2003 18:36:38 -0000	1.1.2.6
--- tree-ssa-live.h	23 Jul 2003 13:46:07 -0000
*************** typedef struct tree_live_info_d
*** 177,183 ****
  
  
  extern tree_live_info_p calculate_live_on_entry (var_map);
! extern void calculate_live_on_exit (tree_live_info_p);
  extern void delete_tree_live_info (tree_live_info_p);
  
  #define LIVEDUMP_ENTRY	0x01
--- 177,183 ----
  
  
  extern tree_live_info_p calculate_live_on_entry (var_map);
! extern void calculate_live_on_exit (tree_live_info_p, bool);
  extern void delete_tree_live_info (tree_live_info_p);
  
  #define LIVEDUMP_ENTRY	0x01
*************** extern void delete_tree_live_info (tree_
*** 185,195 ****
  #define LIVEDUMP_ALL	(LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
  extern void dump_live_info (FILE *, tree_live_info_p, int);
  
- 
  static inline int partition_is_global (tree_live_info_p, int);
  static inline sbitmap live_entry_blocks (tree_live_info_p, int);
  static inline sbitmap live_on_exit (tree_live_info_p, basic_block);
! 
  
  static inline int
  partition_is_global (tree_live_info_p live, int p)
--- 185,194 ----
  #define LIVEDUMP_ALL	(LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
  extern void dump_live_info (FILE *, tree_live_info_p, int);
  
  static inline int partition_is_global (tree_live_info_p, int);
  static inline sbitmap live_entry_blocks (tree_live_info_p, int);
  static inline sbitmap live_on_exit (tree_live_info_p, basic_block);
! static inline var_map live_var_map (tree_live_info_p);
  
  static inline int
  partition_is_global (tree_live_info_p live, int p)
*************** live_on_exit (tree_live_info_p live, bas
*** 221,305 ****
    return live->liveout[bb->index];
  }
  
  
- /* Once a var_map has been created and compressed, a complimentary root_var
-    object can be built.  This creates a list of all the root variables from
-    which ssa version names are derived.  Each root variable has a list of 
-    which partitions are versions of that root.  
- 
-    A varray of tree elements represent each distinct root variable.
-    A parallel array of ints represent a partition number that is a version
-      of the root variable.
-    This partition number is then used as in index into the next_partition
-    array, which returns the index of the next partition which is a version
-    of the root var. ROOT_VAR_NONE indicates the end of the list.  
  
!    ************************************************************************/
  
  
! typedef struct root_var_d
  {
!   varray_type root_var;
    varray_type first_partition;
    int *next_partition;
!   int num_root_vars;
    var_map map;
! } *root_var_p;
  
  static inline tree root_var (root_var_p, int);
! static inline int first_root_var_partition (root_var_p, int);
! static inline int next_root_var_partition (root_var_p, int);
! static inline int num_root_vars (root_var_p);
! static inline int find_root_var (root_var_p, int);
! extern root_var_p init_root_var (var_map);
! extern void delete_root_var (root_var_p);
! extern void dump_root_var (FILE *, root_var_p);
! extern void remove_root_var_partition (root_var_p, int, int);
  
  /* Value returned when there are no more partitions associated with a root
     variable.  */
! #define ROOT_VAR_NONE		-1
  
  /* Number of distinct root variables.  */
  static inline int 
! num_root_vars (root_var_p rv)
  {
!   return rv->num_root_vars;
  }
  
  /* A specific root variable.  */
  static inline tree
  root_var (root_var_p rv, int i)
  {
!   return VARRAY_TREE (rv->root_var, i);
  }
  
! /* First partition belonging to a root variable version.  */
  static inline int
! first_root_var_partition (root_var_p rv, int i)
  {
!   return VARRAY_INT (rv->first_partition, i);
  }
  
  /* Next partition belonging to a root variable partition list.  */
  static inline int
! next_root_var_partition (root_var_p rv, int i)
  {
!   return rv->next_partition[i];
  }
  
! /* Find the root_var index for a specific partition.  */
  static inline int
! find_root_var (root_var_p rv, int i)
  {
!   tree t;
!   var_ann_t ann;
  
!   t = partition_to_var (rv->map, i);
!   if (TREE_CODE (t) == SSA_NAME)
!     t = SSA_NAME_VAR (t);
!   ann = var_ann (t);
!   return (VAR_ANN_ROOT_INDEX (ann));
  }
  
  #endif /* _TREE_SSA_LIVE_H  */
--- 220,562 ----
    return live->liveout[bb->index];
  }
  
+ static inline var_map 
+ live_var_map (tree_live_info_p live)
+ {
+   return live->map;
+ }
  
  
! /* A tree_partition_associator object is a base structure which allows
!    partitions to be associated with a tree object.
  
+    A varray of tree elements represent each distinct tree item.
+    A parallel int array represents the first partition number associated with 
+    the tree.
+    This partition number is then used as in index into the next_partition
+    array, which returns the index of the next partition which is associated
+    with the tree. TPA_NONE indicates the end of the list.  
+    A varray paralleling the partition list 'partition_to_tree_map' is used
+    to indicate which tree index the partition is in.  */
  
! typedef struct tree_partition_associator_d
  {
!   varray_type trees;
    varray_type first_partition;
+   varray_type partition_to_tree_map;
    int *next_partition;
!   int num_trees;
!   int uncompressed_num;
    var_map map;
! } *tpa_p;
! 
! /* Value returned when there are no more partitions associated with a tree.  */
! #define TPA_NONE		-1
! 
! 
! static inline tree tpa_tree (tpa_p, int);
! static inline int tpa_first_partition (tpa_p, int);
! static inline int tpa_next_partition (tpa_p, int);
! static inline int tpa_num_trees (tpa_p);
! static inline int tpa_find_tree (tpa_p, int);
! static inline void tpa_decompact (tpa_p);
! extern tpa_p tpa_init (var_map);
! extern void tpa_delete (tpa_p);
! extern void tpa_dump (FILE *, tpa_p);
! extern void tpa_remove_partition (tpa_p, int, int);
! extern int tpa_compact (tpa_p);
! 
! 
! /* Number of distinct tree nodes.  */
! static inline int
! tpa_num_trees (tpa_p tpa)
! {
!   return tpa->num_trees;
! }
! 
! /* Retreive the tree node for a specified index.  */
! static inline tree
! tpa_tree (tpa_p tpa, int i)
! {
!   return VARRAY_TREE (tpa->trees, i);
! }
! 
! /* Get the first partition associated with a tree.  */
! static inline int
! tpa_first_partition (tpa_p tpa, int i)
! {
!   return VARRAY_INT (tpa->first_partition, i);
! }
! 
! /* Get the next partition in a list.  */
! static inline int
! tpa_next_partition (tpa_p tpa, int i)
! {
!   return tpa->next_partition[i];
! }
! 
! /* Get the tree whose list a partition is a member of.  TPA_NONE is returned
!    if the partition is not associated with any list.  */
! static inline int 
! tpa_find_tree (tpa_p tpa, int i)
! {
!   return VARRAY_INT (tpa->partition_to_tree_map, i);
! }
! 
! /* Compacting removes lists with single elements. This routine puts them
!    back in again.  */
! static inline void 
! tpa_decompact(tpa_p tpa)
! {
! #ifdef ENABLE_CHECKING
!   if (tpa->uncompressed_num == -1)
!     abort ();
! #endif
!   tpa->num_trees = tpa->uncompressed_num;
! }
! 
! /* Once a var_map has been created and compressed, a complimentary root_var
!    object can be built.  This creates a list of all the root variables from
!    which ssa version names are derived.  Each root variable has a list of 
!    which partitions are versions of that root.  
! 
!    This is implemented using the tree_partition_associator.
! 
!    The tree vector is used to represent the root variable.
!    The list of partitions represent SSA versions of the root variable.  */
! 
! typedef tpa_p root_var_p;
  
  static inline tree root_var (root_var_p, int);
! static inline int root_var_first_partition (root_var_p, int);
! static inline int root_var_next_partition (root_var_p, int);
! static inline int root_var_num (root_var_p);
! static inline void root_var_dump (FILE *, root_var_p);
! static inline void root_var_remove_partition (root_var_p, int, int);
! static inline void root_var_delete (root_var_p);
! static inline int root_var_find (root_var_p, int);
! static inline int root_var_compact (root_var_p);
! static inline void root_var_decompact (tpa_p);
! 
! extern root_var_p root_var_init (var_map);
  
  /* Value returned when there are no more partitions associated with a root
     variable.  */
! #define ROOT_VAR_NONE		TPA_NONE
  
  /* Number of distinct root variables.  */
  static inline int 
! root_var_num (root_var_p rv)
  {
!   return tpa_num_trees (rv);
  }
  
  /* A specific root variable.  */
  static inline tree
  root_var (root_var_p rv, int i)
  {
!   return tpa_tree (rv, i);
  }
  
! /* First partition belonging to a root variable list.  */
  static inline int
! root_var_first_partition (root_var_p rv, int i)
  {
!   return tpa_first_partition (rv, i);
  }
  
  /* Next partition belonging to a root variable partition list.  */
  static inline int
! root_var_next_partition (root_var_p rv, int i)
! {
!   return tpa_next_partition (rv, i);
! }
! 
! /* Show debug info for a root_var list.  */
! static inline void
! root_var_dump (FILE *f, root_var_p rv)
  {
!   fprintf (f, "\nRoot Var dump\n");
!   tpa_dump (f, rv);
!   fprintf (f, "\n");
  }
  
! /* destroy a root_var object.  */
! static inline void
! root_var_delete (root_var_p rv)
! {
!   tpa_delete (rv);
! }
! 
! /* Remove a partition from a root_var list.  */
! static inline void
! root_var_remove_partition (root_var_p rv, int root_index, int partition_index)
! {
!   tpa_remove_partition (rv, root_index, partition_index);
! }
! 
! /* Find the root_var list index for a specific partition.  */
! static inline int
! root_var_find (root_var_p rv, int i)
! {
!   return tpa_find_tree (rv, i);
! }
! 
! /* Hide single element lists in the object.  */
! static inline int 
! root_var_compact (root_var_p rv)
! {
!   return tpa_compact (rv);
! }
! 
! /* Expose the single element lists in the object.  */
! static inline void
! root_var_decompact (root_var_p rv)
! {
!   tpa_decompact (rv);
! }
! 
! /* This is similar to a root_var structure, except this associates partitions
!    with their type rather than their root variable. This is used to 
!    coalesce memory locations based on type.   */
! 
! typedef tpa_p type_var_p;
! 
! static inline tree type_var (type_var_p, int);
! static inline int type_var_first_partition (type_var_p, int);
! static inline int type_var_next_partition (type_var_p, int);
! static inline int type_var_num (type_var_p);
! static inline void type_var_dump (FILE *, type_var_p);
! static inline void type_var_remove_partition (type_var_p, int, int);
! static inline void type_var_delete (type_var_p);
! static inline int type_var_find (type_var_p, int);
! static inline int type_var_compact (type_var_p);
! static inline void type_var_decompact (type_var_p);
! 
! extern type_var_p type_var_init (var_map);
! 
! 
! /* Value returned when there is no partitions associated with a list.  */
! #define TYPE_VAR_NONE		TPA_NONE
! 
! /* Number of distinct type lists.  */
! static inline int 
! type_var_num (type_var_p tv)
! {
!   return tpa_num_trees (tv);
! }
! 
! /* The type of a specific list.  */
! static inline tree
! type_var (type_var_p tv, int i)
! {
!   return tpa_tree (tv, i);
! }
! 
! /* First partition belonging to a type list.  */
  static inline int
! type_var_first_partition (type_var_p tv, int i)
  {
!   return tpa_first_partition (tv, i);
! }
  
! /* Next partition belonging to a type list.  */
! static inline int
! type_var_next_partition (type_var_p tv, int i)
! {
!   return tpa_next_partition (tv, i);
  }
+ 
+ /* Show debug info for a type_var object.  */
+ static inline void
+ type_var_dump (FILE *f, type_var_p tv)
+ {
+   fprintf (f, "\nType Var dump\n");
+   tpa_dump (f, tv);
+   fprintf (f, "\n");
+ }
+ 
+ /* Delete a type_var object.  */
+ static inline void
+ type_var_delete (type_var_p tv)
+ {
+   tpa_delete (tv);
+ }
+ 
+ /* Remove a partition from a specific list.  */
+ static inline void
+ type_var_remove_partition (type_var_p tv, int type_index, int partition_index)
+ {
+   tpa_remove_partition (tv, type_index, partition_index);
+ }
+ 
+ /* Find the type index for the list a partition is in.  */
+ static inline int
+ type_var_find (type_var_p tv, int i)
+ {
+   return tpa_find_tree (tv, i);
+ }
+ 
+ /* Hide single element lists.  */
+ static inline int 
+ type_var_compact (type_var_p tv)
+ {
+   return tpa_compact (tv);
+ }
+ 
+ /* Expose single element lists.  */
+ static inline void
+ type_var_decompact (type_var_p tv)
+ {
+   tpa_decompact (tv);
+ }
+ 
+ /* This set of routines implements a coalesce_list. This is an object which
+    is used to track pairs of partitions which are desireable to coalesce
+    together at some point.  Costs are associated with each pair, and when 
+    all desired information has been collected, the object can be used to 
+    order the pairs for processing.  */
+ 
+ /* This structure defines a pair for coalescing.  */
+ 
+ typedef struct partition_pair_d
+ {
+   int first_partition;
+   int second_partition;
+   int cost;
+   struct partition_pair_d *next;
+ } *partition_pair_p;
+ 
+ /* This structure maintains the list of coalesce pairs.  
+    When add_mode is true, list is a triangular shaped list of coalesce pairs.
+    The smaller partition number is used to index the list, and the larger is
+    index is located in a partition_pair_p object. Each of these lists are sorted
+    from smallest to largest second_partition.  New coalesce pairs are allowed
+    to be added in this mode.
+    When add_mode is false, the lists have all been merged into list[0]. The
+    rest of the lists are not used. list[0] is ordered from most desirable
+    coalesce to least desirable. pop_best_coalesce() retreives the pairs
+    one at a time.  */
+ 
+ typedef struct coalesce_list_d 
+ {
+   var_map map;
+   partition_pair_p *list;
+   bool add_mode;
+ } *coalesce_list_p;
+ 
+ extern coalesce_list_p create_coalesce_list (var_map);
+ extern void add_coalesce (coalesce_list_p, int, int, int);
+ extern void sort_coalesce_list (coalesce_list_p);
+ extern void dump_coalesce_list (FILE *, coalesce_list_p);
+ extern void delete_coalesce_list (coalesce_list_p);
+ 
+ #define NO_BEST_COALESCE	-1
+ extern int pop_best_coalesce (coalesce_list_p, int *, int *);
+ 
+ extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p,
+ 						 coalesce_list_p);
+ extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map);
+ 
  
  #endif /* _TREE_SSA_LIVE_H  */
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.108
diff -c -p -r1.1.4.108 tree-ssa.c
*** tree-ssa.c	22 Jul 2003 18:36:38 -0000	1.1.4.108
--- tree-ssa.c	23 Jul 2003 13:46:07 -0000
*************** static int elim_unvisited_predecessor (e
*** 176,188 ****
  static void elim_backward (elim_graph, int);
  static void elim_create (elim_graph, int);
  static void eliminate_phi (edge, int, elim_graph);
! static void coalesce_ssa_name (var_map);
  static void assign_vars (var_map);
- static inline void set_if_valid (var_map, sbitmap, tree);
- static inline void add_conflicts_if_valid (root_var_p, conflict_graph,
- 					   var_map, sbitmap, tree);
  static void replace_variable (var_map, tree *);
  static void eliminate_extraneous_phis (var_map);
  
  /* Main entry point to the SSA builder.  FNDECL is the gimplified function
     to convert.  VARS is an sbitmap representing variables that need to be
--- 176,188 ----
  static void elim_backward (elim_graph, int);
  static void elim_create (elim_graph, int);
  static void eliminate_phi (edge, int, elim_graph);
! static tree_live_info_p coalesce_ssa_name (var_map);
  static void assign_vars (var_map);
  static void replace_variable (var_map, tree *);
  static void eliminate_extraneous_phis (var_map);
+ static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p);
+ static void print_exprs (FILE *, const char *, tree, const char *, tree,
+ 			 const char *);
  
  /* Main entry point to the SSA builder.  FNDECL is the gimplified function
     to convert.  VARS is an sbitmap representing variables that need to be
*************** eliminate_phi (edge e, int i, elim_graph
*** 1150,1333 ****
      }
  }
  
- /* Set the bit for a partition index if the variable is in a partition.  */
  
! static inline void 
! set_if_valid (var_map map, sbitmap vec, tree var)
! { 
!   int p = var_to_partition (map, var);
!   if (p != NO_PARTITION)
!     SET_BIT (vec, p);
! }
! 
! /* If a variable is in a partition, and it's not already live, add a 
!    conflict between it and any other live partition.  Reset the live bit.  */
! 
! static inline void 
! add_conflicts_if_valid (root_var_p rv, conflict_graph graph,
! 			var_map map, sbitmap vec, tree var)
! { 
!   int p, y;
!   p = var_to_partition (map, var);
!   if (p != NO_PARTITION)
!     { 
!       RESET_BIT (vec, p);
!       for (y = first_root_var_partition (rv, find_root_var (rv, p));
! 	   y != ROOT_VAR_NONE;
! 	   y = next_root_var_partition (rv, y))
! 	{
! 	  if (TEST_BIT (vec, y))
! 	    conflict_graph_add (graph, p, y);
! 	}
!     }
! }
! 
! /* Reduce the number of live ranges in the var_map. The only partitions
!    which are associated with actual variables are those which are forced
!    to be coalesced for various reason. (live on entry, live across abnormal 
!    edges, etc.)  */
  
  static void
! coalesce_ssa_name (var_map map)
  {
!   int num, x, y, z;
!   conflict_graph graph;
!   basic_block bb;
!   varray_type stmt_stack, ops;
!   tree stmt;
!   sbitmap live;
!   tree *var_p, var, tmp, phi;
!   root_var_p rv;
!   tree_live_info_p liveinfo;
!   edge e;
!   var_ann_t ann;
! 
!   if (num_var_partitions (map) <= 1)
!     return;
!   
!   liveinfo = calculate_live_on_entry (map);
!   calculate_live_on_exit (liveinfo);
!   graph = conflict_graph_new (num_var_partitions (map));
!   live = sbitmap_alloc (num_var_partitions (map));
!   rv = init_root_var (map);
! 
!   /* Build a conflict graph.  */
! 
!   FOR_EACH_BB (bb)
!     {
!       /* Start with live on exit temporaries.  */
!       sbitmap_copy (live, live_on_exit (liveinfo, bb));
! 
!       FOR_EACH_STMT_IN_REVERSE (stmt_stack, bb, stmt)
!         {
! 	  get_stmt_operands (stmt);
! 
! 	  ops = def_ops (stmt);
! 	  num = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! 	  for (x = 0; x < num; x++)
! 	    {
! 	      var_p = VARRAY_GENERIC_PTR (ops, x);
! 	      add_conflicts_if_valid (rv, graph, map, live, *var_p);
! 	    }
! 
! 	  ops = vdef_ops (stmt);
! 	  num = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! 	  for (x = 0; x < num; x++)
! 	    {
! 	      var = VDEF_RESULT (VARRAY_TREE (ops, x));
! 	      add_conflicts_if_valid (rv, graph, map, live, var);
! 	    }
! 
! 	  
! 	  ops = use_ops (stmt);
! 	  num = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! 	  for (x = 0; x < num; x++)
! 	    {
! 	      var_p = VARRAY_GENERIC_PTR (ops, x);
! 	      set_if_valid (map, live, *var_p);
! 	    }
!   
! 	  ops = vuse_ops (stmt);
! 	  num = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! 	  for (x = 0; x < num; x++)
! 	    {
! 	      var = VARRAY_TREE (ops, x);
! 	      set_if_valid (map, live, var);
! 	    }
!  
! 	  ops = vdef_ops (stmt);
! 	  num = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! 	  for (x = 0; x < num; x++)
! 	    {
! 	      var = VDEF_OP (VARRAY_TREE (ops, x));
! 	      set_if_valid (map, live, var);
! 	    }
! 	}
! 
!       /* Anything which is still live at this point interferes.  */
! 
!       EXECUTE_IF_SET_IN_SBITMAP (live, 0, x,
!         {
! 	  for (y = first_root_var_partition (rv, find_root_var (rv, x));
! 	       y != ROOT_VAR_NONE;
! 	       y = next_root_var_partition (rv, y))
! 	    {
! 	      if (x != y && TEST_BIT (live, y))
! 		conflict_graph_add (graph, x, y);
! 	    }
! 
! 	});
!     }
! 
!   /* First, coalesce all live on entry variables to their root variable. 
!      This will ensure the first use is coming from the right memory location. */
! 
!   sbitmap_zero (live);
! 
!   /* Set 'live' vector to indicate live on entry partitions.  */
! 
!   num = num_var_partitions (map);
!   for (x = 0 ; x < num; x++)
!     for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
!       if (e->dest != EXIT_BLOCK_PTR)
! 	{
! 	  if (TEST_BIT (live_entry_blocks (liveinfo, x), e->dest->index))
! 	    SET_BIT (live, x);
! 	}
!   delete_tree_live_info (liveinfo);
  
-   /* Assign root variable as partition representative for each live on entry
-      partition.  */
-   EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, 
-     {
-       var = root_var (rv, find_root_var (rv, x));
-       ann = var_ann (var);
-       /* If these aren't already coalesced...  */
-       if (partition_to_var (map, x) != var)
- 	{
- 	  if (ann->out_of_ssa_tag)
- 	    {
- 	      /* This root variable has already been assigned to another
- 		 partition which is not coalesced with this one.  */
- 	      abort ();
- 	    }
  
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      fprintf (dump_file, "Must coalesce ");
! 	      print_generic_expr (dump_file, 
! 				  partition_to_var (map, x), 
! 				  TDF_SLIM);
! 	      fprintf (dump_file, " with the root variable ");
! 	      print_generic_expr (dump_file, var, TDF_SLIM);
! 	      fprintf (dump_file, ".\n");
! 	    }
  
! 	  change_partition_var (map, var, x);
! 	}
!     });
  
!   sbitmap_free (live);
  
    /* Code cannot be inserted on abnormal edges. Look for all abnormal 
       edges, and coalesce any PHI results with their arguments across 
--- 1150,1182 ----
      }
  }
  
  
! /* Shortcut routine to print messages of the form: "str expr str expr str."  */
  
  static void
! print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
! 	     tree expr2, const char *str3)
  {
!   fprintf (f, "%s", str1);
!   print_generic_expr (f, expr1, TDF_SLIM);
!   fprintf (f, "%s", str2);
!   print_generic_expr (f, expr2, TDF_SLIM);
!   fprintf (f, "%s", str3);
! }
  
  
! /* Coalesce partitions which are live across abnormal edges. Since code 
!    cannot be inserted on these edges, failure to coalesce something across
!    an abnormal edge is a non-compilable situation.  */
  
! static void
! coalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv)
! {
  
!   basic_block bb;
!   edge e;
!   tree phi, var, tmp;
!   int x, y;
  
    /* Code cannot be inserted on abnormal edges. Look for all abnormal 
       edges, and coalesce any PHI results with their arguments across 
*************** coalesce_ssa_name (var_map map)
*** 1350,1382 ****
  	    tmp = PHI_ARG_DEF (phi, y);
  	    if (TREE_CONSTANT (tmp))
  	      {
! 		fprintf (stderr, "\nConstant argument in PHI. Can't insert :");
! 		print_generic_expr (stderr, var, TDF_SLIM);
! 		fprintf (stderr, " = ");
! 		print_generic_expr (stderr, tmp, TDF_SLIM);
! 		fprintf (stderr, "' across an abnormal edge\n");
  		abort ();
  	      }
  	    y = var_to_partition (map, tmp);
  	    if (x == NO_PARTITION || y == NO_PARTITION)
  	      abort ();
! 	    if (find_root_var (rv, x) != find_root_var (rv, y))
  	      {
! 		/* FIXME. If the root variables are not the same, we 
! 		   can't coalesce the partitions, but maybe we can create
! 		   a new version of the PHI_RESULT variable, issue 
! 		   a copy in the DEST block instead, and use it in the 
! 		   PHI node. Adding a new partition/version at this point
! 		   is really a bad idea, so for now, PUNT!.  */
! 		fprintf (stderr, "\nDifferent root vars '\n");
! 		print_generic_expr (stderr, 
! 				    root_var (rv, find_root_var (rv, x)),
! 				    TDF_SLIM);
! 		fprintf (stderr, "' and '");
! 		print_generic_expr (stderr, 
! 				    root_var (rv, find_root_var (rv, y)),
! 				    TDF_SLIM);
! 		fprintf (stderr, "' across an abnormal edge\n");
  		abort ();
  	      }
  
--- 1199,1218 ----
  	    tmp = PHI_ARG_DEF (phi, y);
  	    if (TREE_CONSTANT (tmp))
  	      {
! 	        print_exprs (stderr,
! 			     "\nConstant argument in PHI. Can't insert :",
! 			     var, " = ", tmp, "' across an abnormal edge\n");
  		abort ();
  	      }
  	    y = var_to_partition (map, tmp);
  	    if (x == NO_PARTITION || y == NO_PARTITION)
  	      abort ();
! 	    if (root_var_find (rv, x) != root_var_find (rv, y))
  	      {
! 		print_exprs (stderr, "\nDifferent root vars '\n",
! 			     root_var (rv, root_var_find (rv, x)), "' and '",
! 			     root_var (rv, root_var_find (rv, y)),
! 			     "' across an abnormal edge\n");
  		abort ();
  	      }
  
*************** coalesce_ssa_name (var_map map)
*** 1390,1458 ****
  		    if (dump_file 
  			&& (dump_flags & TDF_DETAILS))
  		      {
! 			fprintf (dump_file , "ABNORMAL: Coalescing ");
! 			print_generic_expr (dump_file, 
! 					    var, 
! 					    TDF_SLIM);
! 			fprintf (dump_file , " and ");
! 			print_generic_expr (dump_file, 
! 					    tmp, 
! 					    TDF_SLIM);
! 			fprintf (dump_file , " over abnormal edge.\n");
  		      }
  		    var_union (map, var, tmp);
  		    conflict_graph_merge_regs (graph, x, y);
  		  }
  		else
  		  {
! 		    fprintf (stderr, "\n");
! 		    print_generic_expr (stderr, 
! 					partition_to_var (map, x), 
! 					TDF_SLIM);
! 		    fprintf (stderr, " and ");
! 		    print_generic_expr (stderr, 
! 					partition_to_var (map, y), 
! 					TDF_SLIM);
! 		    fprintf (stderr, " conflict across an abnormal edge\n");
  		    abort ();
  		  }
  	      }
  	  }
  
-     if (dump_file && (dump_flags & TDF_DETAILS))
-       {
-         dump_var_map (dump_file, map);
-       }
  
  
!   for (x = 0; x < num_root_vars (rv); x++)
      {
!       while (first_root_var_partition (rv, x) != ROOT_VAR_NONE)
!         {
! 	  /* Coalesce first partition with everything that doesn't conflict.  */
! 	  y = first_root_var_partition (rv, x);
! 	  remove_root_var_partition (rv, x, y);
! 	  var = partition_to_var (map, y);
! 	  for (z = next_root_var_partition (rv, y); 
! 	       z != ROOT_VAR_NONE; 
! 	       z = next_root_var_partition (rv, z))
  	    {
! 	      tmp = partition_to_var (map, z);
! 	      /* If partitions are already merged, don't check for conflict.  */
! 	      if (tmp == var)
! 	        remove_root_var_partition (rv, x, z);
! 	      else if (!conflict_graph_conflict_p (graph, y, z))
! 		{
! 		  var_union (map, var, tmp);
! 		  remove_root_var_partition (rv, x, z);
! 		  conflict_graph_merge_regs (graph, y, z);
! 		}
  	    }
  	}
!     }
  
!   delete_root_var (rv);
    conflict_graph_delete (graph);
  }
  
  /* Take the ssa-name var_map, and assign real variables to each partition.  */
--- 1226,1349 ----
  		    if (dump_file 
  			&& (dump_flags & TDF_DETAILS))
  		      {
! 			print_exprs (dump_file, "ABNORMAL: Coalescing ", var,
! 				     " and ", tmp, " over abnormal edge.\n");
  		      }
  		    var_union (map, var, tmp);
  		    conflict_graph_merge_regs (graph, x, y);
  		  }
  		else
  		  {
! 		    print_exprs (stderr, "\n", partition_to_var (map, x),
! 				 " and ", partition_to_var (map, y),
! 				 " conflict across an abnormal edge\n");
  		    abort ();
  		  }
  	      }
  	  }
+ }
  
  
+ /* Reduce the number of live ranges in the var_map. The only partitions
+    which are associated with actual variables at this point are those which 
+    are forced to be coalesced for various reason. (live on entry, live 
+    across abnormal edges, etc.). 
+    Live range information is returned if flag_tree_combine_temps
+    is set, otherwise NULL.  */
+ 
+ static tree_live_info_p
+ coalesce_ssa_name (var_map map)
+ {
+   int num, x;
+   sbitmap live;
+   tree var;
+   root_var_p rv;
+   tree_live_info_p liveinfo;
+   edge e;
+   var_ann_t ann;
+   conflict_graph graph;
+ 
+   if (num_var_partitions (map) <= 1)
+     return NULL;
+   
+   liveinfo = calculate_live_on_entry (map);
+   calculate_live_on_exit (liveinfo, false);
+   rv = root_var_init (map);
+ 
+   /* Remove single element variable from the list.  */
+   root_var_compact (rv);
+ 
+   /* Build a conflict graph.  */
+   graph = build_tree_conflict_graph (liveinfo, rv, NULL);
+ 
+   /* Put the single element variables back in.  */
+   root_var_decompact (rv);
+ 
+   /* First, coalesce all live on entry variables to their root variable. 
+      This will ensure the first use is coming from the right memory location. */
+ 
+   live = sbitmap_alloc (num_var_partitions (map));
+   sbitmap_zero (live);
+ 
+   /* Set 'live' vector to indicate live on entry partitions.  */
+ 
+   num = num_var_partitions (map);
+   for (x = 0 ; x < num; x++)
+     for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+       if (e->dest != EXIT_BLOCK_PTR)
+ 	{
+ 	  if (TEST_BIT (live_entry_blocks (liveinfo, x), e->dest->index))
+ 	    SET_BIT (live, x);
+ 	}
+ 
+   if (!flag_tree_combine_temps)
+     {
+       delete_tree_live_info (liveinfo);
+       liveinfo = NULL;
+     }
  
!   /* Assign root variable as partition representative for each live on entry
!      partition.  */
!   EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, 
      {
!       var = root_var (rv, root_var_find (rv, x));
!       ann = var_ann (var);
!       /* If these aren't already coalesced...  */
!       if (partition_to_var (map, x) != var)
! 	{
! 	  if (ann->out_of_ssa_tag)
  	    {
! 	      /* This root variable has already been assigned to another
! 		 partition which is not coalesced with this one.  */
! 	      abort ();
! 	    }
! 
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      print_exprs (dump_file, "Must coalesce ", 
! 			   partition_to_var (map, x),
! 			   " with the root variable ", var, ".\n");
  	    }
+ 
+ 	  change_partition_var (map, var, x);
  	}
!     });
! 
!   sbitmap_free (live);
! 
!   /* Coalesce partitions live across abnormal edges.  */
!   coalesce_abnormal_edges (map, graph, rv);
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     dump_var_map (dump_file, map);
! 
!   /* Coalesce partitions of a root variable whereever possible.  */
!   coalesce_tpa_members (rv, graph, map);
  
!   root_var_delete (rv);
    conflict_graph_delete (graph);
+ 
+   return liveinfo;
  }
  
  /* Take the ssa-name var_map, and assign real variables to each partition.  */
*************** assign_vars (var_map map)
*** 1465,1471 ****
    var_ann_t ann;
    root_var_p rv;
  
!   rv = init_root_var (map);
    if (!rv) 
      return;
  
--- 1356,1362 ----
    var_ann_t ann;
    root_var_p rv;
  
!   rv = root_var_init (map);
    if (!rv) 
      return;
  
*************** assign_vars (var_map map)
*** 1494,1507 ****
  	}
      }
  
!   num = num_root_vars (rv);
    for (x = 0; x < num; x++)
      {
        var = root_var (rv, x);
        ann = var_ann (var);
!       for (i = first_root_var_partition (rv, x);
  	   i != ROOT_VAR_NONE;
! 	   i = next_root_var_partition (rv, i))
  	{
  	  t = partition_to_var (map, i);
  
--- 1385,1398 ----
  	}
      }
  
!   num = root_var_num (rv);
    for (x = 0; x < num; x++)
      {
        var = root_var (rv, x);
        ann = var_ann (var);
!       for (i = root_var_first_partition (rv, x);
  	   i != ROOT_VAR_NONE;
! 	   i = root_var_next_partition (rv, i))
  	{
  	  t = partition_to_var (map, i);
  
*************** assign_vars (var_map map)
*** 1516,1527 ****
  	    }
  
  	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      fprintf (dump_file, "Overlap :  '");
! 	      print_generic_expr (dump_file, t, TDF_SLIM);
! 	      fprintf (dump_file, "'  conflicts with  '");
! 	      print_generic_expr (dump_file, var, TDF_SLIM);
! 	    }
  
  	  var = create_temp (t);
  	  change_partition_var (map, var, i);
--- 1407,1414 ----
  	    }
  
  	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    print_exprs (dump_file, "Overlap :  '", t, "'  conflicts with  '",
! 			 var, "");
  
  	  var = create_temp (t);
  	  change_partition_var (map, var, i);
*************** assign_vars (var_map map)
*** 1536,1547 ****
  	}
      }
  
!   delete_root_var (rv);
  }
  
  /* Replace *p with whatever variable it has been rewritten to.  */
  
! static void
  replace_variable (var_map map, tree *p)
  {
    tree new_var;
--- 1423,1434 ----
  	}
      }
  
!   root_var_delete (rv);
  }
  
  /* Replace *p with whatever variable it has been rewritten to.  */
  
! static inline void
  replace_variable (var_map map, tree *p)
  {
    tree new_var;
*************** rewrite_out_of_ssa (tree fndecl)
*** 1583,1588 ****
--- 1470,1476 ----
    tree phi, next;
    elim_graph g;
    int repeat, first_iteration;
+   tree_live_info_p liveinfo;
  
    timevar_push (TV_TREE_SSA_TO_NORMAL);
  
*************** rewrite_out_of_ssa (tree fndecl)
*** 1594,1607 ****
    map = create_ssa_var_map ();
    eliminate_extraneous_phis (map);
  
!   /* Shrink the map to include only referenced variables.  Exclude variables
!      which have only one SSA version since there is nothing to coalesce.  */
!   compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      dump_var_map (dump_file, map);
  
!   coalesce_ssa_name (map);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
--- 1482,1494 ----
    map = create_ssa_var_map ();
    eliminate_extraneous_phis (map);
  
!   /* Shrink the map to include only referenced variables.  */
!   compact_var_map (map, VARMAP_NORMAL);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      dump_var_map (dump_file, map);
  
!   liveinfo = coalesce_ssa_name (map);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
*************** rewrite_out_of_ssa (tree fndecl)
*** 1610,1618 ****
      }
  
    /* This is the final var list, so assign real variables to the different
!      partitions.  Include single reference vars this time. */
! 
!   compact_var_map (map, VARMAP_NORMAL);
    assign_vars (map);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
--- 1497,1503 ----
      }
  
    /* This is the final var list, so assign real variables to the different
!      partitions.  */
    assign_vars (map);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
*************** rewrite_out_of_ssa (tree fndecl)
*** 1620,1625 ****
--- 1505,1515 ----
        fprintf (dump_file, "After Root variable replacement:\n");
        dump_var_map (dump_file, map);
      }
+ 
+   if (liveinfo)
+     delete_tree_live_info (liveinfo);
+ 
+   /* Replace PHI nodes with any required copies.  */
  
    g = new_elim_graph (map->num_partitions);
    g->map = map;





More information about the Gcc-patches mailing list