rewrite the live on entry routines to use the immediate use links.

rewrite the live on exit routines to be calculated on demand as they are needed.


2006-08-18  Andrew MacLeod  <amacleod@redhat.com>

	* tree-ssa-live.c (new_tree_live_info): Don't initialize global bitmap
	and initialize livein vectors to NULL rather than an empty bitmap.
	(delete_tree_live_info): Free live bitmaps only if allocated.
	(live_worklist):  Use stack which is in liveinfo struct.  Stack is
	already initially set upon entry now.
	(add_livein_if_notdef): Remove.
	(set_var_live_on_entry):  New.  Calculate the initial set of live on
	entry blocks using immediate use links.
	(calculate_live_on_entry): Call set_var_live_on_entry for each var.
	Split out the data verification code.
	(calculate_live_on_exit): Remove.
	(calc_live_at_exit): New.  Calculate the live on exit data for a
	single basic block.
	(build_tree_conflict_graph):  Use calc_live_at_exit.
	(dump_live_info): Use calc_live_at_exit, check for empty live-on-entry
	vectors.
	(verify_live_on_entry): New.  Split out verification code from
	calculate_live_on_entry.
	* tree-ssa-live.h (struct tree_live_info_d): Remove global and liveout
	bitmaps.  Add succ_mask and integer work stack fields.
	(partition_is_global): Check for existance of live on entry info.
	(live_on_exit): Remove.
	(live_merge_and_clear): Add asserts.
	(make_live_on_entry): Allocate a bitmap if needed.
	* tree-outof-ssa.c (coalesce_ssa_name, coalesce_vars): Remove call to
	calculate_live_on_exit.






git-svn-id: https://gcc.gnu.org/svn/gcc/branches/out-of-ssa-the-sequel@116257 138bc75d-0d04-0410-961f-82ee72b054a4

4 files changed, 326 insertions, 281 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 02e00bb9366..27c7c1685f8 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,32 @@
+2006-08-18  Andrew MacLeod  <amacleod@redhat.com>
+
+	* tree-ssa-live.c (new_tree_live_info): Don't initialize global bitmap
+	and initialize livein vectors to NULL rather than an empty bitmap.
+	(delete_tree_live_info): Free live bitmaps only if allocated.
+	(live_worklist):  Use stack which is in liveinfo struct.  Stack is
+	already initially set upon entry now.
+	(add_livein_if_notdef): Remove.
+	(set_var_live_on_entry):  New.  Calculate the initial set of live on
+	entry blocks using immediate use links.
+	(calculate_live_on_entry): Call set_var_live_on_entry for each var.
+	Split out the data verification code.
+	(calculate_live_on_exit): Remove.
+	(calc_live_at_exit): New.  Calculate the live on exit data for a
+	single basic block.
+	(build_tree_conflict_graph):  Use calc_live_at_exit.
+	(dump_live_info): Use calc_live_at_exit, check for empty live-on-entry
+	vectors.
+	(verify_live_on_entry): New.  Split out verification code from
+	calculate_live_on_entry.
+	* tree-ssa-live.h (struct tree_live_info_d): Remove global and liveout
+	bitmaps.  Add succ_mask and integer work stack fields.
+	(partition_is_global): Check for existance of live on entry info.
+	(live_on_exit): Remove.
+	(live_merge_and_clear): Add asserts.
+	(make_live_on_entry): Allocate a bitmap if needed.
+	* tree-outof-ssa.c (coalesce_ssa_name, coalesce_vars): Remove call to
+	calculate_live_on_exit.
+
 2006-08-04  Andrew MacLeod  <amacleod@redhat.com>
 
 	* tree-ssa-copyrename.c (copy_rename_partition_coalesce): Change parms
diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c
index a169eb6b8e8..ba7e1223a6b 100644
--- a/gcc/tree-outof-ssa.c
+++ b/gcc/tree-outof-ssa.c
@@ -824,7 +824,6 @@ coalesce_ssa_name (var_map map, int flags)
     return NULL;
 
   liveinfo = calculate_live_on_entry (map);
-  calculate_live_on_exit (liveinfo);
   rv = root_var_init (map);
 
   /* Remove single element variable from the list.  */
@@ -1194,8 +1193,6 @@ coalesce_vars (var_map map, tree_live_info_p liveinfo)
    }
 
   
-  /* Re-calculate live on exit info.  */
-  calculate_live_on_exit (liveinfo);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
index a78e0f3eaa7..8c183178615 100644
--- a/gcc/tree-ssa-live.c
+++ b/gcc/tree-ssa-live.c
@@ -40,15 +40,17 @@ Boston, MA 02110-1301, USA.  */
 #include "toplev.h"
 #include "vecprim.h"
 
-static void live_worklist (tree_live_info_p, int *, int);
+static void live_worklist (tree_live_info_p, 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,
-					 tree, basic_block);
 static inline void add_conflicts_if_valid (tpa_p, conflict_graph,
 					   var_map, bitmap, tree);
 static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool);
 
+#ifdef ENABLE_CHECKING
+static void verify_live_on_entry (tree_live_info_p);
+#endif
+
 /* This is where the mapping from SSA version number to real storage variable
    is tracked.  
 
@@ -491,7 +493,6 @@ create_ssa_var_map (void)
 
 
 /* Allocate and return a new live range information object base on MAP.  */
-
 static tree_live_info_p
 new_tree_live_info (var_map map)
 {
@@ -502,69 +503,69 @@ new_tree_live_info (var_map map)
   live->map = map;
   live->num_blocks = last_basic_block;
 
-  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_ALLOC (NULL);
+    live->livein[x] = NULL;
+
+  live->work_stack = XNEWVEC (int, last_basic_block);
+  live->stack_top = live->work_stack;
+  live->succ_mask = NULL;
 
-  /* liveout is deferred until it is actually requested.  */
-  live->liveout = NULL;
   return live;
 }
 
 
 /* Free storage for live range info object LIVE.  */
-
 void 
 delete_tree_live_info (tree_live_info_p live)
 {
   int x;
-  if (live->liveout)
-    {
-      for (x = live->num_blocks - 1; x >= 0; x--)
-        BITMAP_FREE (live->liveout[x]);
-      free (live->liveout);
-    }
   if (live->livein)
     {
       for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
-        BITMAP_FREE (live->livein[x]);
+        if (live->livein[x])
+	  BITMAP_FREE (live->livein[x]);
       free (live->livein);
     }
-  if (live->global)
-    BITMAP_FREE (live->global);
-  
+
+  if (live->succ_mask)
+    BITMAP_FREE (live->succ_mask);
+
+  free (live->work_stack);
   free (live);
 }
 
 
 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses 
-   for partition I.  STACK is a varray used for temporary memory which is 
-   passed in rather than being allocated on every call.  */
-
+   for partition I.  */
 static void
-live_worklist (tree_live_info_p live, int *stack, int i)
+live_worklist (tree_live_info_p live, int i)
 {
-  unsigned b;
-  tree var;
-  basic_block def_bb = NULL;
   edge e;
-  var_map map = live->map;
+  tree var;
+  unsigned b;
   edge_iterator ei;
-  bitmap_iterator bi;
-  int *tos = stack;
+  basic_block def_bb = NULL;
+  int *tos = live->stack_top;
+  int *empty_stack = live->work_stack;
 
-  var = partition_to_var (map, i);
+  var = partition_to_var (live->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, bi)
-    {
-      *tos++ = b;
-    }
+#ifdef ENABLE_CHECKING
+  {
+    int x = 0;
+    bitmap_iterator bi;
 
-  while (tos != stack)
+    /* Make sure the stack has the same number of elements as liveins.  */
+    EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
+      x++;
+    gcc_assert (x == (tos - empty_stack));
+  }
+#endif
+
+  while (tos != empty_stack)
     {
       b = *--tos;
 
@@ -581,260 +582,167 @@ live_worklist (tree_live_info_p live, int *stack, int i)
 	      }
 	  }
     }
-}
 
-
-/* If VAR is in a partition of MAP, set the bit for that partition in VEC.  */
-
-static inline void
-set_if_valid (var_map map, bitmap vec, tree var)
-{
-  int p = var_to_partition (map, var);
-  if (p != NO_PARTITION)
-    bitmap_set_bit (vec, p);
+  /* Reset stack top pointer.  */
+  live->stack_top = live->work_stack;
 }
 
 
-/* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and 
-   global bit for it in the LIVE object.  BB is the block being processed.  */
-
-static inline void
-add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
-		      tree var, basic_block bb)
+/* Calulate the live on entry vector for the SSA_NAME using immediate_use
+   links.  Set the live on entry fields in LIVE.  */
+static void
+set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
 {
-  int p = var_to_partition (live->map, var);
-  if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
-    return;
-  if (!bitmap_bit_p (def_vec, p))
-    {
-      bitmap_set_bit (live->livein[p], bb->index);
-      bitmap_set_bit (live->global, p);
-    }
-}
-
-
-/* Given partition map MAP, calculate all the live on entry bitmaps for 
-   each basic block.  Return a live info object.  */
+  int p;
+  tree stmt;
+  use_operand_p use;
+  bitmap on_entry = NULL;
+  basic_block def_bb = NULL;
+  imm_use_iterator imm_iter;
 
-tree_live_info_p 
-calculate_live_on_entry (var_map map)
-{
-  tree_live_info_p live;
-  unsigned i;
-  basic_block bb;
-  bitmap saw_def;
-  tree phi, var, stmt;
-  tree op;
-  edge e;
-  int *stack;
-  block_stmt_iterator bsi;
-  ssa_op_iter iter;
-  bitmap_iterator bi;
-#ifdef ENABLE_CHECKING
-  int num;
-  edge_iterator ei;
-#endif
+  p = var_to_partition (live->map, ssa_name);
+  if (p == NO_PARTITION)
+    return;
 
-  saw_def = BITMAP_ALLOC (NULL);
+  stmt = SSA_NAME_DEF_STMT (ssa_name);
+  if (stmt)
+    def_bb = bb_for_stmt (stmt);
+  else
+    def_bb = ENTRY_BLOCK_PTR;
 
-  live = new_tree_live_info (map);
+  gcc_assert (live->stack_top == live->work_stack);
 
-  FOR_EACH_BB (bb)
+  /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
+     add it to the list of live on entry blocks.  */
+  FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
     {
-      bitmap_clear (saw_def);
-
-      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-	{
-	  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 = 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
-		 on entry to that block.  */
-	      if (!stmt || e->src != bb_for_stmt (stmt))
-		add_livein_if_notdef (live, saw_def, var, e->src);
-	    }
-        }
-
-      /* Don't mark PHI results as defined until all the PHI nodes have
-	 been processed. If the PHI sequence is:
-	    a_3 = PHI <a_1, a_2>
-	    b_3 = PHI <b_1, a_3>
-	 The a_3 referred to in b_3's PHI node is the one incoming on the
-	 edge, *not* the PHI node just seen.  */
+      tree use_stmt = USE_STMT (use);
+      basic_block add_block = NULL;
 
-      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+      if (TREE_CODE (use_stmt) == PHI_NODE)
         {
-	  var = PHI_RESULT (phi);
-	  set_if_valid (map, saw_def, var);
+	  /* Uses in PHI's are considered to be live at exit of the SRC block
+	     as this is where a copy would be inserted.  Check to see if it is
+	     defined in that block, or whether its live on entry.  */
+	  int index = PHI_ARG_INDEX_FROM_USE (use);
+	  edge e = PHI_ARG_EDGE (use_stmt, index);
+	  if (e->src != def_bb && e->src != ENTRY_BLOCK_PTR)
+	    add_block = e->src;
 	}
-
-      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+      else
         {
-	  stmt = bsi_stmt (bsi);
-
-	  FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
-	    {
-	      add_livein_if_notdef (live, saw_def, op, bb);
-	    }
-
-	  FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
+	  /* If its not defined in this block, its live on entry.  */
+	  basic_block use_bb = bb_for_stmt (use_stmt);
+	  if (use_bb != def_bb)
+	    add_block = use_bb;
+	}  
+
+      /* If there was a live on entry use, set the bit.  */
+      if (add_block)
+        {
+	  /* Don't allocate a bitmap until its needed.  */
+	  if (!on_entry)
+	    on_entry = BITMAP_ALLOC (NULL);
+	  if (!bitmap_bit_p (on_entry, add_block->index))
 	    {
-	      set_if_valid (map, saw_def, op);
+	      bitmap_set_bit (on_entry, add_block->index);
+	      *(live->stack_top)++ = add_block->index;
 	    }
 	}
     }
 
-  stack = XNEWVEC (int, last_basic_block);
-  EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
+  /* If SSA_NAME is live on entry to at least one block, fill in all the live
+     on entry blocks between the def and all the uses.  */
+  if (on_entry)
     {
-      live_worklist (live, stack, i);
+      live->livein[p] = on_entry;
+      live_worklist (live, p);
     }
-  free (stack);
+}
 
-#ifdef ENABLE_CHECKING
-   /* Check for live on entry partitions and report those with a DEF in
-      the program. This will typically mean an optimization has done
-      something wrong.  */
 
-  bb = ENTRY_BLOCK_PTR;
-  num = 0;
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    {
-      int entry_block = e->dest->index;
-      if (e->dest == EXIT_BLOCK_PTR)
-        continue;
-      for (i = 0; i < (unsigned)num_var_partitions (map); i++)
-	{
-	  basic_block tmp;
-	  tree d;
-	  var = partition_to_var (map, i);
-	  stmt = SSA_NAME_DEF_STMT (var);
-	  tmp = bb_for_stmt (stmt);
-	  d = default_def (SSA_NAME_VAR (var));
+/* Given partition map MAP, calculate all the live on entry bitmaps for 
+   each partition.  Return a new live info object.  */
+tree_live_info_p 
+calculate_live_on_entry (var_map map)
+{
+  tree var;
+  unsigned i;
+  tree_live_info_p live;
 
-	  if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
-	    {
-	      if (!IS_EMPTY_STMT (stmt))
-		{
-		  num++;
-		  print_generic_expr (stderr, var, TDF_SLIM);
-		  fprintf (stderr, " is defined ");
-		  if (tmp)
-		    fprintf (stderr, " in BB%d, ", tmp->index);
-		  fprintf (stderr, "by:\n");
-		  print_generic_expr (stderr, stmt, TDF_SLIM);
-		  fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", 
-			   entry_block);
-		  fprintf (stderr, " So it appears to have multiple defs.\n");
-		}
-	      else
-	        {
-		  if (d != var)
-		    {
-		      num++;
-		      print_generic_expr (stderr, var, TDF_SLIM);
-		      fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
-		      if (d)
-		        {
-			  fprintf (stderr, " but is not the default def of ");
-			  print_generic_expr (stderr, d, TDF_SLIM);
-			  fprintf (stderr, "\n");
-			}
-		      else
-			fprintf (stderr, " and there is no default def.\n");
-		    }
-		}
-	    }
-	  else
-	    if (d == var)
-	      {
-		/* The only way this var shouldn't be marked live on entry is 
-		   if it occurs in a PHI argument of the block.  */
-		int z, ok = 0;
-		for (phi = phi_nodes (e->dest); 
-		     phi && !ok; 
-		     phi = PHI_CHAIN (phi))
-		  {
-		    for (z = 0; z < PHI_NUM_ARGS (phi); z++)
-		      if (var == PHI_ARG_DEF (phi, z))
-			{
-			  ok = 1;
-			  break;
-			}
-		  }
-		if (ok)
-		  continue;
-	        num++;
-		print_generic_expr (stderr, var, TDF_SLIM);
-		fprintf (stderr, " is not marked live-on-entry to entry BB%d ", 
-			 entry_block);
-		fprintf (stderr, "but it is a default def so it should be.\n");
-	      }
-	}
+  live = new_tree_live_info (map);
+  for (i = 0; i < num_var_partitions (map); i++)
+    {
+      var = partition_to_var (map, i);
+      if (var != NULL_TREE)
+	set_var_live_on_entry (var, live);
     }
-  gcc_assert (num <= 0);
-#endif
-
-  BITMAP_FREE (saw_def);
 
+#ifdef ENABLE_CHECKING
+  verify_live_on_entry (live);
+#endif
   return live;
 }
 
 
-/* Calculate the live on exit vectors based on the entry info in LIVEINFO.  */
-
+/* Calculate live at exit on demand for basic block BB.  Use the live on entry
+   info in LIVEINFO, and return the results in the already allocated bitmap 
+   AT_EXIT.  */
 void
-calculate_live_on_exit (tree_live_info_p liveinfo)
+calc_live_at_exit (basic_block bb, tree_live_info_p liveinfo, bitmap at_exit)
 {
-  unsigned b;
-  unsigned i, x;
-  bitmap *on_exit;
-  basic_block bb;
   edge e;
-  tree t, phi;
+  unsigned x;
+  tree phi, use;
+  int partition;
   bitmap on_entry;
+  edge_iterator ei;
   var_map map = liveinfo->map;
+  bitmap succ_mask;
+  
+  if (liveinfo->succ_mask == NULL)
+    liveinfo->succ_mask = BITMAP_ALLOC (NULL);
+  succ_mask = liveinfo->succ_mask;
 
-  on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
-  for (x = 0; x < (unsigned)last_basic_block; x++)
-    on_exit[x] = BITMAP_ALLOC (NULL);
+  bitmap_clear (succ_mask);
+  bitmap_clear (at_exit);
 
-  /* Set all the live-on-exit bits for uses in PHIs.  */
-  FOR_EACH_BB (bb)
+  FOR_EACH_EDGE (e, ei, bb->succs)
     {
-      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-	for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
-	  { 
-	    t = PHI_ARG_DEF (phi, i);
-	    e = PHI_ARG_EDGE (phi, i);
-	    if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
-	      continue;
-	    set_if_valid (map, on_exit[e->src->index], t);
-	  }
-    }
+      basic_block succ = e->dest;
 
-  /* Set live on exit for all predecessors of live on entry's.  */
-  for (i = 0; i < num_var_partitions (map); i++)
-    {
-      bitmap_iterator bi;
+      /* Set a bit in succ_mask for each edge.  At the end of the edge loop, 
+	 succ_mask will have a bit set for each successor edge of this 
+	 block.   */
+      if (succ != EXIT_BLOCK_PTR)
+	bitmap_set_bit (succ_mask, succ->index);
 
-      on_entry = live_entry_blocks (liveinfo, i);
-      EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
+      /* Visit all the PHI nodes on the edge, and mark any phi arguments on
+	 this edge as live at exit.  */
+      for (phi = phi_nodes (succ); phi; phi = PHI_CHAIN (phi))
         {
-	  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);
+	  use = PHI_ARG_DEF_FROM_EDGE (phi, e);
+	  if (TREE_CODE (use) != SSA_NAME)
+	    continue;
+	  partition = var_to_partition (map, use);
+	  if (partition == NO_PARTITION)
+	    continue;
+	  bitmap_set_bit (at_exit, partition);
 	}
     }
-
-  liveinfo->liveout = on_exit;
+ 
+  /* Loop over each partition, and if it has a live on entry bitmap, check to
+     see if it is live on any successor block of BB.  This is easily determined
+     by checking if live on entry intersects succ_mask.  */
+  for (x = 0; x < num_var_partitions (map); x++)
+    {
+      /* iF any variable is live on entry to any succ block, add to live
+         at exit bitmap.  */
+      on_entry = live_entry_blocks (liveinfo, x);
+      if (on_entry && !bitmap_bit_p (at_exit, x) 
+	  && bitmap_intersect_p (on_entry, succ_mask))
+	bitmap_set_bit (at_exit, x);
+    }
 }
 
 
@@ -1418,6 +1326,19 @@ add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
     }
 }
 
+
+/* If VAR is in a partition of MAP, set the bit for that partition in VEC.  */
+
+static inline void
+set_if_valid (var_map map, bitmap vec, tree var)
+{
+  int p = var_to_partition (map, var);
+  if (p != NO_PARTITION)
+    bitmap_set_bit (vec, p);
+}
+
+
+
 /* Return a conflict graph for the information contained in LIVE_INFO.  Only
    conflicts between items in the same TPA list are added.  If optional 
    coalesce list CL is passed in, any copies encountered are added.  */
@@ -1455,8 +1376,8 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
       tree phi;
       int idx;
 
-      /* Start with live on exit temporaries.  */
-      bitmap_copy (live, live_on_exit (liveinfo, bb));
+      /* Start with live at exit temporaries.  */
+      calc_live_at_exit (bb, liveinfo, live);
 
       for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
         {
@@ -1891,7 +1812,8 @@ dump_live_info (FILE *f, tree_live_info_p live, int flag)
 	  fprintf (f, "\nLive on entry to BB%d : ", bb->index);
 	  for (i = 0; i < num_var_partitions (map); i++)
 	    {
-	      if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
+	      bitmap loe = live_entry_blocks (live, i);
+	      if (loe && bitmap_bit_p (loe, bb->index))
 	        {
 		  print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
 		  fprintf (f, "  ");
@@ -1901,21 +1823,25 @@ dump_live_info (FILE *f, tree_live_info_p live, int flag)
 	}
     }
 
-  if ((flag & LIVEDUMP_EXIT) && live->liveout)
+  if (flag & LIVEDUMP_EXIT)
     {
+      bitmap liveout = BITMAP_ALLOC (NULL);
       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, bi)
+	  calc_live_at_exit (bb, live, liveout);
+	  fprintf (f, "\nLive at exit from BB%d : ", bb->index);
+	  EXECUTE_IF_SET_IN_BITMAP (liveout, 0, i, bi)
 	    {
 	      print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
 	      fprintf (f, "  ");
 	    }
 	  fprintf (f, "\n");
 	}
+      BITMAP_FREE (liveout);
     }
 }
 
+
 #ifdef ENABLE_CHECKING
 void
 register_ssa_partition_check (tree ssa_var)
@@ -1929,4 +1855,106 @@ register_ssa_partition_check (tree ssa_var)
       internal_error ("SSA corruption");
     }
 }
+
+
+/* Verify that the info in LIVE matches the current cfg.  */
+static void
+verify_live_on_entry (tree_live_info_p live)
+{
+  unsigned i;
+  tree var;
+  tree phi, stmt;
+  basic_block bb;
+  edge e;
+  int num;
+  edge_iterator ei;
+  var_map map = live->map;
+
+   /* Check for live on entry partitions and report those with a DEF in
+      the program. This will typically mean an optimization has done
+      something wrong.  */
+
+  bb = ENTRY_BLOCK_PTR;
+  num = 0;
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      int entry_block = e->dest->index;
+      if (e->dest == EXIT_BLOCK_PTR)
+        continue;
+      for (i = 0; i < (unsigned)num_var_partitions (map); i++)
+	{
+	  basic_block tmp;
+	  tree d;
+	  bitmap loe;
+	  var = partition_to_var (map, i);
+	  stmt = SSA_NAME_DEF_STMT (var);
+	  tmp = bb_for_stmt (stmt);
+	  d = default_def (SSA_NAME_VAR (var));
+
+	  loe = live_entry_blocks (live, i);
+	  if (loe && bitmap_bit_p (loe, entry_block))
+	    {
+	      if (!IS_EMPTY_STMT (stmt))
+		{
+		  num++;
+		  print_generic_expr (stderr, var, TDF_SLIM);
+		  fprintf (stderr, " is defined ");
+		  if (tmp)
+		    fprintf (stderr, " in BB%d, ", tmp->index);
+		  fprintf (stderr, "by:\n");
+		  print_generic_expr (stderr, stmt, TDF_SLIM);
+		  fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", 
+			   entry_block);
+		  fprintf (stderr, " So it appears to have multiple defs.\n");
+		}
+	      else
+	        {
+		  if (d != var)
+		    {
+		      num++;
+		      print_generic_expr (stderr, var, TDF_SLIM);
+		      fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
+		      if (d)
+		        {
+			  fprintf (stderr, " but is not the default def of ");
+			  print_generic_expr (stderr, d, TDF_SLIM);
+			  fprintf (stderr, "\n");
+			}
+		      else
+			fprintf (stderr, " and there is no default def.\n");
+		    }
+		}
+	    }
+	  else
+	    if (d == var)
+	      {
+		/* The only way this var shouldn't be marked live on entry is 
+		   if it occurs in a PHI argument of the block.  */
+		int z, ok = 0;
+		for (phi = phi_nodes (e->dest); 
+		     phi && !ok; 
+		     phi = PHI_CHAIN (phi))
+		  {
+		    for (z = 0; z < PHI_NUM_ARGS (phi); z++)
+		      if (var == PHI_ARG_DEF (phi, z))
+			{
+			  ok = 1;
+			  break;
+			}
+		  }
+		if (ok)
+		  continue;
+	        num++;
+		print_generic_expr (stderr, var, TDF_SLIM);
+		fprintf (stderr, " is not marked live-on-entry to entry BB%d ", 
+			 entry_block);
+		fprintf (stderr, "but it is a default def so it should be.\n");
+	      }
+	}
+    }
+  gcc_assert (num <= 0);
+}
 #endif
+
+
+
diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index 7427ba50577..f539a8dbde4 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -209,23 +209,26 @@ typedef struct tree_live_info_d
   /* Var map this relates to.  */
   var_map map;
 
-  /* Bitmap indicating which partitions are global.  */
-  bitmap global;
-
   /* Bitmap of live on entry blocks for partition elements.  */
   bitmap *livein;
 
   /* Number of basic blocks when live on exit calculated.  */
   int num_blocks;
 
-  /* Bitmap of what variables are live on exit for a basic blocks.  */
-  bitmap *liveout;
+  /* Vector used when creating live ranges as a visited stack.  */
+  int *work_stack;
+
+  /* Top of woirkstack.  */
+  int *stack_top;
+
+  /* Temporary working bitmap used by calc_live_at_exit.  */
+  bitmap succ_mask;
 } *tree_live_info_p;
 
 
 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);
+extern void calc_live_at_exit (basic_block, tree_live_info_p, bitmap);
 
 #define LIVEDUMP_ENTRY	0x01
 #define LIVEDUMP_EXIT	0x02
@@ -234,7 +237,6 @@ extern void dump_live_info (FILE *, tree_live_info_p, int);
 
 static inline int partition_is_global (tree_live_info_p, int);
 static inline bitmap live_entry_blocks (tree_live_info_p, int);
-static inline bitmap live_on_exit (tree_live_info_p, basic_block);
 static inline var_map live_var_map (tree_live_info_p);
 static inline void live_merge_and_clear (tree_live_info_p, int, int);
 static inline void make_live_on_entry (tree_live_info_p, basic_block, int);
@@ -245,13 +247,13 @@ static inline void make_live_on_entry (tree_live_info_p, basic_block, int);
 static inline int
 partition_is_global (tree_live_info_p live, int p)
 {
-  gcc_assert (live->global);
-  return bitmap_bit_p (live->global, p);
+  gcc_assert (live->livein);
+  return (live->livein[p] != NULL);
 }
 
 
 /* Return the bitmap from LIVE representing the live on entry blocks for 
-   partition P.  */
+   partition P.  A NULL means there are NO live blocks.  */
 
 static inline bitmap
 live_entry_blocks (tree_live_info_p live, int p)
@@ -261,20 +263,6 @@ live_entry_blocks (tree_live_info_p live, int p)
 }
 
 
-/* Return the bitmap from LIVE representing the live on exit partitions from
-   block BB.  */
-
-static inline bitmap
-live_on_exit (tree_live_info_p live, basic_block bb)
-{
-  gcc_assert (live->liveout);
-  gcc_assert (bb != ENTRY_BLOCK_PTR);
-  gcc_assert (bb != EXIT_BLOCK_PTR);
-
-  return live->liveout[bb->index];
-}
-
-
 /* Return the partition map which the information in LIVE utilizes.  */
 
 static inline var_map 
@@ -290,6 +278,8 @@ live_var_map (tree_live_info_p live)
 static inline void 
 live_merge_and_clear (tree_live_info_p live, int p1, int p2)
 {
+  gcc_assert (live->livein[p1]);
+  gcc_assert (live->livein[p2]);
   bitmap_ior_into (live->livein[p1], live->livein[p2]);
   bitmap_zero (live->livein[p2]);
 }
@@ -300,8 +290,9 @@ live_merge_and_clear (tree_live_info_p live, int p1, int p2)
 static inline void 
 make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
 {
+  if (live->livein[p] == NULL)
+    live->livein[p] = BITMAP_ALLOC (NULL);
   bitmap_set_bit (live->livein[p], bb->index);
-  bitmap_set_bit (live->global, p);
 }