This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

live on entry/exit speedups for SSA->Normal (PR 28071)


This patch provides a reimplementation of out of SSA's 'live on entry'
and 'live on exit' calculations. It tackles the timing issues
demonstrated in PR 28071, but I'm not so sure I'd consider it suitable
for stage 3.  I present it here anyway :-)

Previously, live on entry was calculated on a 'per variable' basis,
while live on exit was calculated on a per block basis.  It turns out
that this causes a couple of different types of slowdowns in large test
cases.

First, live on entry is switched to a per block basis representation as
well.  Instead of scanning the IL looking for live on entry uses and
track defs, the immediate use information (which wasn't available way
back when) is used to determine which uses of a variable are live on
entry to their block.  This seeds the initial state, and with block
info, all the variables can be processed at once when traversing an edge
to propagate liveness. This is the major component of the speedup.

The second part of the speedup comes from having the on-entry info in
the same form as the on-exit info. Instead of processing each variable
for live-on-entryness, on-exit calculations can utilize bitmap OR's.

bootstrapped on x86-pc-linux-gnu  with no new regressions.  

Many testcases show little difference, but some of the larger testcases
certainly do.  PR 28071 timings at -O3 go from:

   tree SSA to normal    :  32.08 (35%) usr   0.08 ( 1%) sys  32.92
(28%) wall
to
   tree SSA to normal    :  16.19 (22%) usr   0.08 ( 1%) sys  16.33
(13%) wall

the remaining time is addressed by a patch to TER.



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

	* tree-ssa-live.c (new_tree_live_info, delete_tree_live_info): Update.
	(add_livein_if_notdef): Delete.
	(loe_visit_block): New.  Propogate live on entry info for a block into
	each predecessor.  If it changes, make sure it is visited again.
	(live_worklist): Visit every block and update the live on entry info 
	for preds.  Iterate over any that changed.
	(set_var_live_on_entry): Populate the live on entry blocks with bits
	based on the immediate uses of a var.
	(calculate_live_on_entry): Remove.
	(calculate_live_on_exit): Calculate live on exit based on the newly
	oriented live on entry bits.
	(calculate_live_ranges): Build live on entry and exit vectors.
	(dump_live_info): Use new orientation of live on entry bitmaps.
	(verify_live_on_entry): New.  Split out verification code from old
	calculate_live_on_entry routine.
	* tree-ssa-live.h (struct tree_live_info_d): Add Working stack.
	(live_entry_blocks): Rename to live_on_entry and return bitmap for a
	basic_block instead of for a partition.
	(live_merge_and_clear): Add asserts.
	(make_live_on_entry): Set partition bit in basic block vector.
	* tree-outof-ssa.c (coalesce_ssa_name): Use calculate_live_ranges.

Index: tree-ssa-live.c
===================================================================
*** tree-ssa-live.c	(revision 116309)
--- tree-ssa-live.c	(working copy)
*************** Boston, MA 02110-1301, USA.  */
*** 40,55 ****
  #include "toplev.h"
  #include "vecprim.h"
  
! 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,
- 					 tree, basic_block);
  static inline void register_ssa_partition (var_map, tree, bool);
  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);
  
  /* This is where the mapping from SSA version number to real storage variable
     is tracked.  
  
--- 40,57 ----
  #include "toplev.h"
  #include "vecprim.h"
  
! static void live_worklist (tree_live_info_p);
  static tree_live_info_p new_tree_live_info (var_map);
  static inline void set_if_valid (var_map, bitmap, tree);
  static inline void register_ssa_partition (var_map, tree, bool);
  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.  
  
*************** new_tree_live_info (var_map map)
*** 522,535 ****
    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);
  
!   /* liveout is deferred until it is actually requested.  */
!   live->liveout = NULL;
    return live;
  }
  
--- 524,541 ----
    live->map = map;
    live->num_blocks = last_basic_block;
  
!   live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
!   for (x = 0; x < (unsigned)last_basic_block; x++)
      live->livein[x] = BITMAP_ALLOC (NULL);
  
!   live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
!   for (x = 0; x < (unsigned)last_basic_block; x++)
!     live->liveout[x] = BITMAP_ALLOC (NULL);
! 
!   live->work_stack = XNEWVEC (int, last_basic_block);
!   live->stack_top = live->work_stack;
! 
!   live->global = BITMAP_ALLOC (NULL);
    return live;
  }
  
*************** void 
*** 540,809 ****
  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]);
!       free (live->livein);
!     }
!   if (live->global)
!     BITMAP_FREE (live->global);
!   
    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.  */
! 
! static void
! live_worklist (tree_live_info_p live, int *stack, int i)
  {
-   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, bi)
!     {
!       *tos++ = b;
!     }
! 
!   while (tos != stack)
!     {
!       b = *--tos;
! 
!       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);
! 		*tos++ = e->src->index;
! 	      }
! 	  }
      }
  }
  
  
! /* 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);
! }
  
  
! /* 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)
! {
!   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.  */
  
! 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
! 
!   saw_def = BITMAP_ALLOC (NULL);
  
!   live = new_tree_live_info (map);
  
!   FOR_EACH_BB (bb)
      {
!       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.  */
  
!       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
!         {
! 	  var = PHI_RESULT (phi);
! 	  set_if_valid (map, saw_def, var);
! 	}
  
!       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
          {
! 	  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)
! 	    {
! 	      set_if_valid (map, saw_def, op);
  	    }
  	}
!     }
! 
!   stack = XNEWVEC (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
!       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));
  
! 	  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");
! 	      }
  	}
      }
-   gcc_assert (num <= 0);
- #endif
- 
-   BITMAP_FREE (saw_def);
  
!   return live;
  }
  
  
--- 546,709 ----
  delete_tree_live_info (tree_live_info_p live)
  {
    int x;
! 
!   BITMAP_FREE (live->global);
!   free (live->work_stack);
! 
!   for (x = live->num_blocks - 1; x >= 0; x--)
!     BITMAP_FREE (live->liveout[x]);
!   free (live->liveout);
! 
!   for (x = live->num_blocks - 1; x >= 0; x--)
!     BITMAP_FREE (live->livein[x]);
!   free (live->livein);
! 
    free (live);
  }
  
  
! /* Visit basic block BB, and propogate any required live on entry bits from 
!    LIVE into the predecessors.  VISITED is the bitmap of visited blocks.  
!    TMP is a temporary work bitmap which is passed in to avoid reallocting
!    it each time.  */
! 
! static void 
! loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
! 		 bitmap tmp)
  {
    edge e;
!   bool change;
    edge_iterator ei;
!   basic_block pred_bb;
!   bitmap loe;
!   gcc_assert (!TEST_BIT (visited, bb->index));
! 
!   SET_BIT (visited, bb->index);
!   loe = live_on_entry (live, bb);
! 
!   FOR_EACH_EDGE (e, ei, bb->preds)
!     {
!       pred_bb = e->src;
!       if (pred_bb == ENTRY_BLOCK_PTR)
! 	continue;
!       /* tmp is vars live-=on-entry from BB that aren't defined in the
! 	 pred. block.  This should be the live on entry vars to pred.  
! 	 Note that liveout is the DEFs in a block while live on entry is
! 	 being calculated.  */
!       bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]);
! 
!       /* Add these bits to live-on-entry for the pred. if there are any 
! 	 changes, and pred_bb has been visited already, add it to the
! 	 revisit stack.  */
!       change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
!       if (TEST_BIT (visited, pred_bb->index) && change)
! 	{
! 	  RESET_BIT (visited, pred_bb->index);
! 	  *(live->stack_top)++ = pred_bb->index;
! 	}
      }
  }
  
  
! /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses 
!    of all the vairables.  */
  
! static void
! live_worklist (tree_live_info_p live)
  {
!   unsigned b;
!   basic_block bb;
!   sbitmap visited = sbitmap_alloc (last_basic_block + 1);
!   bitmap tmp = BITMAP_ALLOC (NULL);
  
+   sbitmap_zero (visited);
  
!   /* Visit all the blocks in reverse order and propogate live on entry values
!      into the predecessors blocks.  */
!   FOR_EACH_BB_REVERSE (bb)
!     loe_visit_block (live, bb, visited, tmp);
  
!   /* Process any blocks which require further iteration.  */
!   while (live->stack_top != live->work_stack)
      {
!       b = *--(live->stack_top);
!       loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
      }
+ 
+   BITMAP_FREE (tmp);
+   sbitmap_free (visited);
  }
  
  
! /* Calulate the initial live on entry vector for SSA_NAME using immediate_use
!    links.  Set the live on entry fields in LIVE.  Def's are marked temporarily
!    in the liveout vector.  */
  
! static void
! set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
  {
!   int p;
!   tree stmt;
!   use_operand_p use;
!   basic_block def_bb = NULL;
!   imm_use_iterator imm_iter;
!   bool global = false;
  
!   p = var_to_partition (live->map, ssa_name);
!   if (p == NO_PARTITION)
!     return;
  
!   stmt = SSA_NAME_DEF_STMT (ssa_name);
!   if (stmt)
      {
!       def_bb = bb_for_stmt (stmt);
!       /* Mark defs in liveout bitmap for now.  */
!       if (def_bb)
! 	bitmap_set_bit (live->liveout[def_bb->index], p);
!     }
!   else
!     def_bb = ENTRY_BLOCK_PTR;
  
!   /* 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)
!     {
!       tree use_stmt = USE_STMT (use);
!       basic_block add_block = NULL;
  
!       if (TREE_CODE (use_stmt) == PHI_NODE)
          {
! 	  /* 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 != ENTRY_BLOCK_PTR)
  	    {
! 	      if (e->src != def_bb)
! 		add_block = e->src;
  	    }
  	}
!       else
!         {
! 	  /* 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)
!         {
! 	  global = true;
! 	  bitmap_set_bit (live->livein[add_block->index], p);
  	}
      }
  
!   /* 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 (global)
!     bitmap_set_bit (live->global, p);
  }
  
  
*************** calculate_live_on_entry (var_map map)
*** 812,860 ****
  void
  calculate_live_on_exit (tree_live_info_p liveinfo)
  {
!   unsigned b;
!   unsigned i, x;
!   bitmap *on_exit;
    basic_block bb;
    edge e;
!   tree t, phi;
!   bitmap on_entry;
!   var_map map = liveinfo->map;
  
!   on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
!   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 < (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);
  	  }
      }
  
!   /* 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, bi)
!         {
! 	  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;
  }
  
  
--- 712,780 ----
  void
  calculate_live_on_exit (tree_live_info_p liveinfo)
  {
!   unsigned i;
!   int p;
!   tree t, phi;
    basic_block bb;
    edge e;
!   edge_iterator ei;
  
!   /* live on entry calculations used the liveouit vector for defs.  */
!   FOR_EACH_BB (bb)
!     bitmap_clear (liveinfo->liveout[bb->index]);
  
    /* Set all the live-on-exit bits for uses in PHIs.  */
    FOR_EACH_BB (bb)
      {
+       /* Mark the PHI arguments which are live on exit to the pred block.  */
        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);
! 	    if (TREE_CODE (t) != SSA_NAME)
  	      continue;
! 	    p = var_to_partition (liveinfo->map, t);
! 	    if (p == NO_PARTITION)
! 	      continue;
! 	    e = PHI_ARG_EDGE (phi, i);
! 	    if (e->src != ENTRY_BLOCK_PTR)
! 	      bitmap_set_bit (liveinfo->liveout[e->src->index], p);
  	  }
+ 
+       /* add each successors live on entry to this bock live on exit.  */
+       FOR_EACH_EDGE (e, ei, bb->succs)
+         if (e->dest != EXIT_BLOCK_PTR)
+ 	  bitmap_ior_into (liveinfo->liveout[bb->index],
+ 			   live_on_entry (liveinfo, e->dest));
      }
+ }
  
! /* 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_ranges (var_map map)
! {
!   tree var;
!   unsigned i;
!   tree_live_info_p live;
! 
!   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);
      }
  
!   live_worklist (live);
! 
! #ifdef ENABLE_CHECKING
!   verify_live_on_entry (live);
! #endif
! 
!   calculate_live_on_exit (live);
!   return live;
  }
  
  
*************** add_conflicts_if_valid (tpa_p tpa, confl
*** 1388,1393 ****
--- 1308,1324 ----
      }
  }
  
+ 
+ /* 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.  */
*************** dump_live_info (FILE *f, tree_live_info_
*** 1865,1877 ****
        FOR_EACH_BB (bb)
  	{
  	  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))
! 	        {
! 		  print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
! 		  fprintf (f, "  ");
! 		}
  	    }
  	  fprintf (f, "\n");
  	}
--- 1796,1805 ----
        FOR_EACH_BB (bb)
  	{
  	  fprintf (f, "\nLive on entry to BB%d : ", bb->index);
! 	  EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
  	    {
! 	      print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
! 	      fprintf (f, "  ");
  	    }
  	  fprintf (f, "\n");
  	}
*************** register_ssa_partition_check (tree ssa_v
*** 1905,1908 ****
--- 1833,1935 ----
        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_on_entry (live, e->dest);
+ 	  if (loe && bitmap_bit_p (loe, i))
+ 	    {
+ 	      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
Index: tree-ssa-live.h
===================================================================
*** tree-ssa-live.h	(revision 116309)
--- tree-ssa-live.h	(working copy)
*************** register_ssa_partition (var_map map, tre
*** 201,211 ****
      As well, partitions are marked as to whether they are global (live 
      outside the basic block they are defined in).
  
!     The live-on-entry information is per variable. It provide a bitmap for 
!     each variable which has a bit set for each basic block that the variable
!     is live on entry to that block.
  
!     The live-on-exit information is per block. It provides a bitmap for each
      block indicating which partitions are live on exit from the block.
  
      For the purposes of this implementation, we treat the elements of a PHI 
--- 201,211 ----
      As well, partitions are marked as to whether they are global (live 
      outside the basic block they are defined in).
  
!     The live-on-entry information is per block.  It provide a bitmap for 
!     each block which has a bit set for each partition that is live on entry to 
!     that block.
  
!     The live-on-exit information is per block.  It provides a bitmap for each
      block indicating which partitions are live on exit from the block.
  
      For the purposes of this implementation, we treat the elements of a PHI 
*************** typedef struct tree_live_info_d
*** 237,248 ****
    /* 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;
  } *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);
  
--- 237,254 ----
    /* Number of basic blocks when live on exit calculated.  */
    int num_blocks;
  
+   /* Vector used when creating live ranges as a visited stack.  */
+   int *work_stack;
+ 
+   /* Top of workstack.  */
+   int *stack_top;
+ 
    /* Bitmap of what variables are live on exit for a basic blocks.  */
    bitmap *liveout;
  } *tree_live_info_p;
  
  
! extern tree_live_info_p calculate_live_ranges (var_map);
  extern void calculate_live_on_exit (tree_live_info_p);
  extern void delete_tree_live_info (tree_live_info_p);
  
*************** extern void delete_tree_live_info (tree_
*** 252,258 ****
  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);
--- 258,264 ----
  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_on_entry (tree_live_info_p, basic_block);
  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);
*************** partition_is_global (tree_live_info_p li
*** 273,282 ****
     partition P.  */
  
  static inline bitmap
! live_entry_blocks (tree_live_info_p live, int p)
  {
    gcc_assert (live->livein);
!   return live->livein[p];
  }
  
  
--- 279,291 ----
     partition P.  */
  
  static inline bitmap
! live_on_entry (tree_live_info_p live, basic_block bb)
  {
    gcc_assert (live->livein);
!   gcc_assert (bb != ENTRY_BLOCK_PTR);
!   gcc_assert (bb != EXIT_BLOCK_PTR);
! 
!   return live->livein[bb->index];
  }
  
  
*************** live_var_map (tree_live_info_p live)
*** 309,314 ****
--- 318,325 ----
  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]);
  }
*************** live_merge_and_clear (tree_live_info_p l
*** 319,325 ****
  static inline void 
  make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
  {
!   bitmap_set_bit (live->livein[p], bb->index);
    bitmap_set_bit (live->global, p);
  }
  
--- 330,336 ----
  static inline void 
  make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
  {
!   bitmap_set_bit (live->livein[bb->index], p);
    bitmap_set_bit (live->global, p);
  }
  
Index: tree-outof-ssa.c
===================================================================
*** tree-outof-ssa.c	(revision 116309)
--- tree-outof-ssa.c	(working copy)
*************** coalesce_ssa_name (var_map map, int flag
*** 823,830 ****
    if (num_var_partitions (map) <= 1)
      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.  */
--- 823,829 ----
    if (num_var_partitions (map) <= 1)
      return NULL;
  
!   liveinfo = calculate_live_ranges (map);
    rv = root_var_init (map);
  
    /* Remove single element variable from the list.  */

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]