OSDN Git Service

2005-11-03 Andrew Pinski <pinskia@physics.uc.edu>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-live.c
index 014ec2d..132af92 100644 (file)
@@ -1,5 +1,5 @@
 /* Liveness for SSA trees.
-   Copyright (C) 2003 Free Software Foundation, Inc.
+   Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
    Contributed by Andrew MacLeod <amacleod@redhat.com>
 
 This file is part of GCC.
@@ -16,8 +16,8 @@ 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.  */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA.  */
 
 #include "config.h"
 #include "system.h"
@@ -34,12 +34,12 @@ Boston, MA 02111-1307, USA.  */
 #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"
+#include "toplev.h"
 
-static void live_worklist (tree_live_info_p, varray_type, int);
+static void live_worklist (tree_live_info_p, int *, int);
 static tree_live_info_p new_tree_live_info (var_map);
 static inline void set_if_valid (var_map, bitmap, tree);
 static inline void add_livein_if_notdef (tree_live_info_p, bitmap,
@@ -133,7 +133,7 @@ var_union (var_map map, tree var1, tree var2)
       if (map->compact_to_partition)
         p2 = map->compact_to_partition[p2];
 
-      /* If there is no root_var set, or its not a user variable, set the
+      /* If there is no root_var set, or it's not a user variable, set the
         root_var to this one.  */
       if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
         {
@@ -144,8 +144,8 @@ var_union (var_map map, tree var1, tree var2)
        other_var = var2;
     }
 
-  if (p1 == NO_PARTITION || p2 == NO_PARTITION)
-    abort ();
+  gcc_assert (p1 != NO_PARTITION);
+  gcc_assert (p2 != NO_PARTITION);
 
   if (p1 == p2)
     p3 = p1;
@@ -185,7 +185,8 @@ void
 compact_var_map (var_map map, int flags)
 {
   sbitmap used;
-  int x, limit, count, tmp, root, root_i;
+  int tmp, root, root_i;
+  unsigned int x, limit, count;
   tree var;
   root_var_p rv = NULL;
 
@@ -238,10 +239,12 @@ compact_var_map (var_map map, int flags)
   /* Build a compacted partitioning.  */
   if (count != limit)
     {
+      sbitmap_iterator sbi;
+
       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,
+      EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi)
        {
          map->partition_to_compact[x] = count;
          map->compact_to_partition[count] = x;
@@ -249,7 +252,7 @@ compact_var_map (var_map map, int flags)
          if (TREE_CODE (var) != SSA_NAME)
            change_partition_var (map, var, count);
          count++;
-       });
+       }
     }
   else
     {
@@ -274,8 +277,7 @@ change_partition_var (var_map map, tree var, int part)
 {
   var_ann_t ann;
 
-  if (TREE_CODE (var) == SSA_NAME)
-    abort();
+  gcc_assert (TREE_CODE (var) != SSA_NAME);
 
   ann = var_ann (var);
   ann->out_of_ssa_tag = 1;
@@ -284,6 +286,7 @@ change_partition_var (var_map map, tree var, int part)
     map->partition_to_var[map->compact_to_partition[part]] = var;
 }
 
+static inline void mark_all_vars_used (tree *);
 
 /* Helper function for mark_all_vars_used, called via walk_tree.  */
 
@@ -293,12 +296,23 @@ mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
 {
   tree t = *tp;
 
+  /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
+     fields that do not contain vars.  */
+  if (TREE_CODE (t) == TARGET_MEM_REF)
+    {
+      mark_all_vars_used (&TMR_SYMBOL (t));
+      mark_all_vars_used (&TMR_BASE (t));
+      mark_all_vars_used (&TMR_INDEX (t));
+      *walk_subtrees = 0;
+      return NULL;
+    }
+
   /* Only need to mark VAR_DECLS; parameters and return results are not
      eliminated as unused.  */
   if (TREE_CODE (t) == VAR_DECL)
     set_is_used (t);
 
-  if (DECL_P (t) || TYPE_P (t))
+  if (IS_TYPE_OR_DECL_P (t))
     *walk_subtrees = 0;
 
   return NULL;
@@ -324,22 +338,18 @@ create_ssa_var_map (int flags)
   basic_block bb;
   tree dest, use;
   tree stmt;
-  stmt_ann_t ann;
   var_map map;
   ssa_op_iter iter;
 #ifdef ENABLE_CHECKING
-  sbitmap used_in_real_ops;
-  sbitmap used_in_virtual_ops;
+  bitmap used_in_real_ops;
+  bitmap used_in_virtual_ops;
 #endif
 
   map = init_var_map (num_ssa_names + 1);
 
 #ifdef ENABLE_CHECKING
-  used_in_real_ops = sbitmap_alloc (num_referenced_vars);
-  sbitmap_zero (used_in_real_ops);
-
-  used_in_virtual_ops = sbitmap_alloc (num_referenced_vars);
-  sbitmap_zero (used_in_virtual_ops);
+  used_in_real_ops = BITMAP_ALLOC (NULL);
+  used_in_virtual_ops = BITMAP_ALLOC (NULL);
 #endif
 
   if (flags & SSA_VAR_MAP_REF_COUNT)
@@ -369,8 +379,6 @@ create_ssa_var_map (int flags)
       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
         {
          stmt = bsi_stmt (bsi);
-         get_stmt_operands (stmt);
-         ann = stmt_ann (stmt);
 
          /* Register USE and DEF operands in each statement.  */
          FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE)
@@ -378,7 +386,7 @@ create_ssa_var_map (int flags)
              register_ssa_partition (map, use, true);
 
 #ifdef ENABLE_CHECKING
-             SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (use))->uid);
+             bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use)));
 #endif
            }
 
@@ -387,7 +395,7 @@ create_ssa_var_map (int flags)
              register_ssa_partition (map, dest, false);
 
 #ifdef ENABLE_CHECKING
-             SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (dest))->uid);
+             bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest)));
 #endif
            }
 
@@ -396,7 +404,8 @@ create_ssa_var_map (int flags)
          FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, 
                                     SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
            {
-             SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (use))->uid);
+             bitmap_set_bit (used_in_virtual_ops, 
+                             DECL_UID (SSA_NAME_VAR (use)));
            }
 
 #endif /* ENABLE_CHECKING */
@@ -408,19 +417,21 @@ create_ssa_var_map (int flags)
 #if defined ENABLE_CHECKING
   {
     unsigned i;
-    sbitmap both = sbitmap_alloc (num_referenced_vars);
-    sbitmap_a_and_b (both, used_in_real_ops, used_in_virtual_ops);
-    if (sbitmap_first_set_bit (both) >= 0)
+    bitmap both = BITMAP_ALLOC (NULL);
+    bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
+    if (!bitmap_empty_p (both))
       {
-       EXECUTE_IF_SET_IN_SBITMAP (both, 0, i,
+       bitmap_iterator bi;
+
+       EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
          fprintf (stderr, "Variable %s used in real and virtual operands\n",
-                  get_name (referenced_var (i))));
-       abort ();
+                  get_name (referenced_var (i)));
+       internal_error ("SSA corruption");
       }
 
-    sbitmap_free (used_in_real_ops);
-    sbitmap_free (used_in_virtual_ops);
-    sbitmap_free (both);
+    BITMAP_FREE (used_in_real_ops);
+    BITMAP_FREE (used_in_virtual_ops);
+    BITMAP_FREE (both);
   }
 #endif
 
@@ -434,17 +445,17 @@ static tree_live_info_p
 new_tree_live_info (var_map map)
 {
   tree_live_info_p live;
-  int x;
+  unsigned x;
 
   live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
   live->map = map;
   live->num_blocks = last_basic_block;
 
-  live->global = BITMAP_XMALLOC ();
+  live->global = BITMAP_ALLOC (NULL);
 
   live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
   for (x = 0; x < num_var_partitions (map); x++)
-    live->livein[x] = BITMAP_XMALLOC ();
+    live->livein[x] = BITMAP_ALLOC (NULL);
 
   /* liveout is deferred until it is actually requested.  */
   live->liveout = NULL;
@@ -461,17 +472,17 @@ delete_tree_live_info (tree_live_info_p live)
   if (live->liveout)
     {
       for (x = live->num_blocks - 1; x >= 0; x--)
-        BITMAP_XFREE (live->liveout[x]);
+        BITMAP_FREE (live->liveout[x]);
       free (live->liveout);
     }
   if (live->livein)
     {
       for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
-        BITMAP_XFREE (live->livein[x]);
+        BITMAP_FREE (live->livein[x]);
       free (live->livein);
     }
   if (live->global)
-    BITMAP_XFREE (live->global);
+    BITMAP_FREE (live->global);
   
   free (live);
 }
@@ -482,38 +493,40 @@ delete_tree_live_info (tree_live_info_p live)
    passed in rather than being allocated on every call.  */
 
 static void
-live_worklist (tree_live_info_p live, varray_type stack, int i)
+live_worklist (tree_live_info_p live, int *stack, int i)
 {
-  int b;
+  unsigned b;
   tree var;
   basic_block def_bb = NULL;
   edge e;
   var_map map = live->map;
+  edge_iterator ei;
+  bitmap_iterator bi;
+  int *tos = stack;
 
   var = partition_to_var (map, i);
   if (SSA_NAME_DEF_STMT (var))
     def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
 
-  EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b,
+  EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
     {
-      VARRAY_PUSH_INT (stack, b);
-    });
+      *tos++ = b;
+    }
 
-  while (VARRAY_ACTIVE_SIZE (stack) > 0)
+  while (tos != stack)
     {
-      b = VARRAY_TOP_INT (stack);
-      VARRAY_POP (stack);
+      b = *--tos;
 
-      for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
-        if (e->src != ENTRY_BLOCK_PTR)
+      FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
+       if (e->src != ENTRY_BLOCK_PTR)
          {
            /* Its not live on entry to the block its defined in.  */
            if (e->src == def_bb)
              continue;
            if (!bitmap_bit_p (live->livein[i], e->src->index))
              {
-               bitmap_set_bit (live->livein[i], e->src->index);
-               VARRAY_PUSH_INT (stack, e->src->index);
+               bitmap_set_bit (live->livein[i], e->src->index);
+               *tos++ = e->src->index;
              }
          }
     }
@@ -556,22 +569,22 @@ tree_live_info_p
 calculate_live_on_entry (var_map map)
 {
   tree_live_info_p live;
-  int i;
+  unsigned i;
   basic_block bb;
   bitmap saw_def;
   tree phi, var, stmt;
   tree op;
   edge e;
-  varray_type stack;
+  int *stack;
   block_stmt_iterator bsi;
-  stmt_ann_t ann;
   ssa_op_iter iter;
+  bitmap_iterator bi;
 #ifdef ENABLE_CHECKING
   int num;
+  edge_iterator ei;
 #endif
 
-
-  saw_def = BITMAP_XMALLOC ();
+  saw_def = BITMAP_ALLOC (NULL);
 
   live = new_tree_live_info (map);
 
@@ -581,13 +594,13 @@ calculate_live_on_entry (var_map map)
 
       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
        {
-         for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+         for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
            {
              var = PHI_ARG_DEF (phi, i);
              if (!phi_ssa_name_p (var))
                continue;
              stmt = SSA_NAME_DEF_STMT (var);
-             e = PHI_ARG_EDGE (phi, i);
+             e = EDGE_PRED (bb, i);
 
              /* Any uses in PHIs which either don't have def's or are not
                 defined in the block from which the def comes, will be live
@@ -613,8 +626,6 @@ calculate_live_on_entry (var_map map)
       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
         {
          stmt = bsi_stmt (bsi);
-         get_stmt_operands (stmt);
-         ann = stmt_ann (stmt);
 
          FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
            {
@@ -628,11 +639,12 @@ calculate_live_on_entry (var_map map)
        }
     }
 
-  VARRAY_INT_INIT (stack, last_basic_block, "stack");
-  EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i,
+  stack = xmalloc (sizeof (int) * last_basic_block);
+  EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
     {
       live_worklist (live, stack, i);
-    });
+    }
+  free (stack);
 
 #ifdef ENABLE_CHECKING
    /* Check for live on entry partitions and report those with a DEF in
@@ -641,12 +653,12 @@ calculate_live_on_entry (var_map map)
 
   bb = ENTRY_BLOCK_PTR;
   num = 0;
-  for (e = bb->succ; e; e = e->succ_next)
+  FOR_EACH_EDGE (e, ei, bb->succs)
     {
       int entry_block = e->dest->index;
       if (e->dest == EXIT_BLOCK_PTR)
         continue;
-      for (i = 0; i < num_var_partitions (map); i++)
+      for (i = 0; i < (unsigned)num_var_partitions (map); i++)
        {
          basic_block tmp;
          tree d;
@@ -715,11 +727,10 @@ calculate_live_on_entry (var_map map)
              }
        }
     }
-  if (num > 0)
-    abort ();
+  gcc_assert (num <= 0);
 #endif
 
-  BITMAP_XFREE (saw_def);
+  BITMAP_FREE (saw_def);
 
   return live;
 }
@@ -731,7 +742,7 @@ void
 calculate_live_on_exit (tree_live_info_p liveinfo)
 {
   unsigned b;
-  int i, x;
+  unsigned i, x;
   bitmap *on_exit;
   basic_block bb;
   edge e;
@@ -740,14 +751,14 @@ calculate_live_on_exit (tree_live_info_p liveinfo)
   var_map map = liveinfo->map;
 
   on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
-  for (x = 0; x < last_basic_block; x++)
-    on_exit[x] = BITMAP_XMALLOC ();
+  for (x = 0; x < (unsigned)last_basic_block; x++)
+    on_exit[x] = BITMAP_ALLOC (NULL);
 
   /* Set all the live-on-exit bits for uses in PHIs.  */
   FOR_EACH_BB (bb)
     {
       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-       for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+       for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
          { 
            t = PHI_ARG_DEF (phi, i);
            e = PHI_ARG_EDGE (phi, i);
@@ -760,13 +771,16 @@ calculate_live_on_exit (tree_live_info_p liveinfo)
   /* Set live on exit for all predecessors of live on entry's.  */
   for (i = 0; i < num_var_partitions (map); i++)
     {
+      bitmap_iterator bi;
+
       on_entry = live_entry_blocks (liveinfo, i);
-      EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b,
+      EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
         {
-         for (e = BASIC_BLOCK(b)->pred; e; e = e->pred_next)
+         edge_iterator ei;
+         FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
            if (e->src != ENTRY_BLOCK_PTR)
              bitmap_set_bit (on_exit[e->src->index], i);
-       });
+       }
     }
 
   liveinfo->liveout = on_exit;
@@ -775,7 +789,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo)
 
 /* Initialize a tree_partition_associator object using MAP.  */
 
-tpa_p
+static tpa_p
 tpa_init (var_map map)
 {
   tpa_p tpa;
@@ -796,7 +810,7 @@ tpa_init (var_map map)
   memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
 
   x = MAX (40, (num_partitions / 20));
-  VARRAY_TREE_INIT (tpa->trees, x, "trees");
+  tpa->trees = VEC_alloc (tree, heap, x);
   VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
 
   return tpa;
@@ -838,6 +852,7 @@ tpa_delete (tpa_p tpa)
   if (!tpa)
     return;
 
+  VEC_free (tree, heap, tpa->trees);
   free (tpa->partition_to_tree_map);
   free (tpa->next_partition);
   free (tpa);
@@ -871,19 +886,20 @@ tpa_compact (tpa_p tpa)
         of the tree list.  */
       if (tpa_next_partition (tpa, first) == NO_PARTITION)
         {
-         swap_t = VARRAY_TREE (tpa->trees, last);
+         swap_t = VEC_index (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);
+         VEC_replace (tree, tpa->trees, last,
+                      VEC_index (tree, tpa->trees, x));
          VARRAY_INT (tpa->first_partition, last) 
            = VARRAY_INT (tpa->first_partition, x);
          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;
+         VEC_replace (tree, tpa->trees, x, swap_t);
          VARRAY_INT (tpa->first_partition, x) = swap_i;
          for (y = tpa_first_partition (tpa, x); 
               y != NO_PARTITION; 
@@ -943,10 +959,7 @@ root_var_init (var_map map)
 
       p = var_to_partition (map, t);
 
-#ifdef ENABLE_CHECKING
-      if (p == NO_PARTITION)
-        abort ();
-#endif
+      gcc_assert (p != NO_PARTITION);
 
       /* Make sure we only put coalesced partitions into the list once.  */
       if (TEST_BIT (seen, p))
@@ -965,7 +978,7 @@ root_var_init (var_map map)
         {
          ann->root_var_processed = 1;
          VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
-         VARRAY_PUSH_TREE (rv->trees, t);
+         VEC_safe_push (tree, heap, rv->trees, t);
          VARRAY_PUSH_INT (rv->first_partition, p);
        }
       rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
@@ -974,7 +987,7 @@ root_var_init (var_map map)
   /* 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);
+      t = VEC_index (tree, rv->trees, x);
       var_ann (t)->root_var_processed = 0;
     }
 
@@ -1019,10 +1032,7 @@ type_var_init (var_map map)
 
       p = var_to_partition (map, t);
 
-#ifdef ENABLE_CHECKING
-      if (p == NO_PARTITION)
-        abort ();
-#endif
+      gcc_assert (p != NO_PARTITION);
 
       /* If partitions have been coalesced, only add the representative 
         for the partition to the list once.  */
@@ -1033,12 +1043,12 @@ type_var_init (var_map map)
 
       /* Find the list for this type.  */
       for (y = 0; y < tv->num_trees; y++)
-        if (t == VARRAY_TREE (tv->trees, y))
+        if (t == VEC_index (tree, tv->trees, y))
          break;
       if (y == tv->num_trees)
         {
          tv->num_trees++;
-         VARRAY_PUSH_TREE (tv->trees, t);
+         VEC_safe_push (tree, heap, tv->trees, t);
          VARRAY_PUSH_INT (tv->first_partition, p);
        }
       else
@@ -1135,18 +1145,34 @@ find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
   return node;
 }
 
+/* Return cost of execution of copy instruction with FREQUENCY
+   possibly on CRITICAL edge and in HOT basic block.  */
+int
+coalesce_cost (int frequency, bool hot, bool critical)
+{
+  /* Base costs on BB frequencies bounded by 1.  */
+  int cost = frequency;
+
+  if (!cost)
+    cost = 1;
+  if (optimize_size || hot)
+    cost = 1;
+  /* Inserting copy on critical edge costs more
+     than inserting it elsewhere.  */
+  if (critical)
+    cost *= 2;
+  return cost;
+}
 
 /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE.  */
 
 void 
-add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
+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
+  gcc_assert (cl->add_mode);
 
   if (p1 == p2)
     return;
@@ -1173,12 +1199,11 @@ int compare_pairs (const void *p1, const void *p2)
 void
 sort_coalesce_list (coalesce_list_p cl)
 {
-  int x, num, count;
+  unsigned x, num, count;
   partition_pair_p chain, p;
   partition_pair_p  *list;
 
-  if (!cl->add_mode)
-    abort();
+  gcc_assert (cl->add_mode);
 
   cl->add_mode = false;
 
@@ -1204,10 +1229,7 @@ sort_coalesce_list (coalesce_list_p cl)
       for (p = chain; p != NULL; p = p->next)
        list[count++] = p;
 
-#ifdef ENABLE_CHECKING
-  if (count != num)
-    abort ();
-#endif
+      gcc_assert (count == num);
        
       qsort (list, count, sizeof (partition_pair_p), compare_pairs);
 
@@ -1242,14 +1264,13 @@ sort_coalesce_list (coalesce_list_p cl)
    partitions via P1 and P2.  Their calculated cost is returned by the function.
    NO_BEST_COALESCE is returned if the coalesce list is empty.  */
 
-int 
+static int
 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
 {
   partition_pair_p node;
   int ret;
 
-  if (cl->add_mode)
-    abort();
+  gcc_assert (!cl->add_mode);
 
   node = cl->list[0];
   if (!node)
@@ -1294,6 +1315,8 @@ add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
     }
 }
 
+DEF_VEC_I(int);
+DEF_VEC_ALLOC_I(int,heap);
 
 /* Return a conflict graph for the information contained in LIVE_INFO.  Only
    conflicts between items in the same TPA list are added.  If optional 
@@ -1306,11 +1329,13 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
   conflict_graph graph;
   var_map map;
   bitmap live;
-  int x, y, i;
+  unsigned x, y, i;
   basic_block bb;
-  varray_type partition_link, tpa_to_clear, tpa_nodes;
+  int *partition_link, *tpa_nodes;
+  VEC(int,heap) *tpa_to_clear;
   unsigned l;
   ssa_op_iter iter;
+  bitmap_iterator bi;
 
   map = live_var_map (liveinfo);
   graph = conflict_graph_new (num_var_partitions (map));
@@ -1318,16 +1343,17 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
   if (tpa_num_trees (tpa) == 0)
     return graph;
 
-  live = BITMAP_XMALLOC ();
+  live = BITMAP_ALLOC (NULL);
 
-  VARRAY_INT_INIT (partition_link, num_var_partitions (map) + 1, "part_link");
-  VARRAY_INT_INIT (tpa_nodes, tpa_num_trees (tpa), "tpa nodes");
-  VARRAY_INT_INIT (tpa_to_clear, 50, "tpa to clear");
+  partition_link = xcalloc (num_var_partitions (map) + 1, sizeof (int));
+  tpa_nodes = xcalloc (tpa_num_trees (tpa), sizeof (int));
+  tpa_to_clear = VEC_alloc (int, heap, 50);
 
   FOR_EACH_BB (bb)
     {
       block_stmt_iterator bsi;
       tree phi;
+      int idx;
 
       /* Start with live on exit temporaries.  */
       bitmap_copy (live, live_on_exit (liveinfo, bb));
@@ -1336,10 +1362,6 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
         {
          bool is_a_copy = false;
          tree stmt = bsi_stmt (bsi);
-         stmt_ann_t ann;
-
-         get_stmt_operands (stmt);
-         ann = stmt_ann (stmt);
 
          /* A copy between 2 partitions does not introduce an interference 
             by itself.  If they did, you would never be able to coalesce 
@@ -1380,7 +1402,9 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
                  if (bit)
                    bitmap_set_bit (live, p2);
                  if (cl)
-                   add_coalesce (cl, p1, p2, 1);
+                   add_coalesce (cl, p1, p2,
+                                 coalesce_cost (bb->frequency,
+                                                maybe_hot_bb_p (bb), false));
                  set_if_valid (map, live, rhs);
                }
            }
@@ -1427,32 +1451,35 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
         tpa_clear contains all the tpa_roots processed, and these are the only
         entries which need to be zero'd out for a clean restart.  */
 
-      EXECUTE_IF_SET_IN_BITMAP (live, 0, x,
+      EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
         {
          i = tpa_find_tree (tpa, x);
-         if (i != TPA_NONE)
+         if (i != (unsigned)TPA_NONE)
            {
-             int start = VARRAY_INT (tpa_nodes, i);
+             int start = tpa_nodes[i];
              /* If start is 0, a new root reference list is being started.
                 Register it to be cleared.  */
              if (!start)
-               VARRAY_PUSH_INT (tpa_to_clear, i);
+               VEC_safe_push (int, heap, tpa_to_clear, i);
 
              /* Add interferences to other tpa members seen.  */
-             for (y = start; y != 0; y = VARRAY_INT (partition_link, y))
+             for (y = start; y != 0; y = partition_link[y])
                conflict_graph_add (graph, x, y - 1);
-             VARRAY_INT (tpa_nodes, i) = x + 1;
-             VARRAY_INT (partition_link, x + 1) = start;
+             tpa_nodes[i] = x + 1;
+             partition_link[x + 1] = start;
            }
-       });
+       }
 
        /* Now clear the used tpa root references.  */
-       for (l = 0; l < VARRAY_ACTIVE_SIZE (tpa_to_clear); l++)
-         VARRAY_INT (tpa_nodes, VARRAY_INT (tpa_to_clear, l)) = 0;
-       VARRAY_POP_ALL (tpa_to_clear);
+       for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++)
+         tpa_nodes[idx] = 0;
+       VEC_truncate (int, tpa_to_clear, 0);
     }
 
-  BITMAP_XFREE (live);
+  free (tpa_nodes);
+  free (partition_link);
+  VEC_free (int, heap, tpa_to_clear);
+  BITMAP_FREE (live);
   return graph;
 }
 
@@ -1759,8 +1786,9 @@ void
 dump_live_info (FILE *f, tree_live_info_p live, int flag)
 {
   basic_block bb;
-  int i;
+  unsigned i;
   var_map map = live->map;
+  bitmap_iterator bi;
 
   if ((flag & LIVEDUMP_ENTRY) && live->livein)
     {
@@ -1784,12 +1812,27 @@ dump_live_info (FILE *f, tree_live_info_p live, int flag)
       FOR_EACH_BB (bb)
        {
          fprintf (f, "\nLive on exit from BB%d : ", bb->index);
-         EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i,
+         EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
            {
              print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
              fprintf (f, "  ");
-           });
+           }
          fprintf (f, "\n");
        }
     }
 }
+
+#ifdef ENABLE_CHECKING
+void
+register_ssa_partition_check (tree ssa_var)
+{
+  gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
+  if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
+    {
+      fprintf (stderr, "Illegally registering a virtual SSA name :");
+      print_generic_expr (stderr, ssa_var, TDF_SLIM);
+      fprintf (stderr, " in the SSA->Normal phase.\n");
+      internal_error ("SSA corruption");
+    }
+}
+#endif