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]

[patch] Avoid using BB_VISITED everywhere


Hi,

Following the discussion on gcc@, this patch documents that BB_VISITED
is not supposed to be used by any pass.

Bootstrapped and tested on {i686,x86_64,ia64,ppc64,ppc)-suse-linux-gnu.
OK?

Gr.
Steven

	* basic-block.h: Document BB_* flags.
	* regrename.c (copyprop_hardreg_forward): Don't use BB_VISITED,
	use an sbitmap instead.
	* sched-rgn.c (compute_trg_info): Likewise.
	* tree-ssa-dce.c (visited_control_parents): New sbitmap to
	replace BB_VISITED uses.
	(find_obviously_necessary_stmts): Don't clear BB_VISITED.
	(propagate_necessity): Check the bitmap instead of BB_VISITED.
	(tree_dce_done): Free visited_control_parents.
	(perform_tree_ssa_dce): Allocate and clear it.
	* tree-ssa-pre.c (compute_antic_aux): Make non-recursive.
	(compute_antic): Iterate from here using a DFS.  Use an sbitmap
	instead of BB_VISITED.

Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.233
diff -c -3 -p -r1.233 basic-block.h
*** basic-block.h	13 Dec 2004 20:44:31 -0000	1.233
--- basic-block.h	7 Jan 2005 23:49:20 -0000
*************** typedef struct reorder_block_def
*** 285,302 ****
  
  #define BB_FREQ_MAX 10000
  
! /* Masks for basic_block.flags.  */
! #define BB_DIRTY		1
! #define BB_NEW			2
! #define BB_REACHABLE		4
! #define BB_VISITED		8
! #define BB_IRREDUCIBLE_LOOP	16
! #define BB_SUPERBLOCK		32
! #define BB_DISABLE_SCHEDULE     64
! 
! #define BB_HOT_PARTITION	128
! #define BB_COLD_PARTITION	256
! #define BB_UNPARTITIONED	0
  
  /* Partitions, to be used when partitioning hot and cold basic blocks into
     separate sections.  */
--- 285,322 ----
  
  #define BB_FREQ_MAX 10000
  
! /* Masks for basic_block.flags.  BB_VISITED should not be used by passes,
!    it is used internally by dfs_enumerate_from().
!    BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout
!    the compilation, so they are never cleared.
!    All other flags may be cleared by clear_bb_flags().  It is generally
!    a bad idea to rely on any flags being up-to-date.  */
! 
! #define BB_DIRTY		1	/* Set if insns in BB have are
! 					   modified.  Used for updating
! 					   liveness information.  */
! #define BB_NEW			2	/* Only set on blocks that have
! 					   just been created by create_bb.  */
! #define BB_REACHABLE		4	/* Set by find_unreachable_blocks.
! 					   Don't rely on this being set in
! 					   any pass.  */
! #define BB_VISITED		8	/* Used by dfs_enumerate_from().  */
! #define BB_IRREDUCIBLE_LOOP	16	/* Set for blocks in an irreducible
! 					   loop by loop analysis.  */
! #define BB_SUPERBLOCK		32	/* Set on blocks that may actually
! 					   not be single-entry single-exit
! 					   basic blocks.  */
! #define BB_DISABLE_SCHEDULE     64	/* Set on basic blocks that the
! 					   scheduler should not touch.  This
! 					   is used by SMS to prevent the
! 					   other schedulers from messing
! 					   with the loop schedule.  */
! #define BB_HOT_PARTITION	128	/* Set on blocks that should be put
! 					   in a hot section.  */
! #define BB_COLD_PARTITION	256	/* Set on blocks that should be put
! 					   in a cold section.  */
! #define BB_UNPARTITIONED	0	/* Dummy flag for convenience in the
! 					   hot/cold partitioning code.  */
  
  /* Partitions, to be used when partitioning hot and cold basic blocks into
     separate sections.  */
Index: regrename.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/regrename.c,v
retrieving revision 1.92
diff -c -3 -p -r1.92 regrename.c
*** regrename.c	22 Nov 2004 15:18:50 -0000	1.92
--- regrename.c	7 Jan 2005 23:49:21 -0000
*************** copyprop_hardreg_forward (void)
*** 1746,1774 ****
    struct value_data *all_vd;
    bool need_refresh;
    basic_block bb;
  
    need_refresh = false;
  
    all_vd = xmalloc (sizeof (struct value_data) * last_basic_block);
  
!   /* Clear all BB_VISITED flags.  We use BB_VISITED flags to indicate
!      whether we have processed a given basic block or not.  Note that
!      we never put BB_VISITED flag on ENTRY_BLOCK_PTR throughout this
!      function because we want to call init_value_data for all
!      successors of ENTRY_BLOCK_PTR.  */
!   FOR_ALL_BB (bb)
!     bb->flags &= ~BB_VISITED;
  
    FOR_EACH_BB (bb)
      {
!       bb->flags |= BB_VISITED;
  
        /* If a block has a single predecessor, that we've already
  	 processed, begin with the value data that was live at
  	 the end of the predecessor block.  */
        /* ??? Ought to use more intelligent queuing of blocks.  */
        if (EDGE_COUNT (bb->preds) == 1
! 	  && ((EDGE_PRED (bb, 0)->src->flags & BB_VISITED) != 0)
  	  && ! (EDGE_PRED (bb, 0)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
  	all_vd[bb->index] = all_vd[EDGE_PRED (bb, 0)->src->index];
        else
--- 1746,1771 ----
    struct value_data *all_vd;
    bool need_refresh;
    basic_block bb;
+   sbitmap visited;
  
    need_refresh = false;
  
    all_vd = xmalloc (sizeof (struct value_data) * last_basic_block);
  
!   visited = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
!   sbitmap_zero (visited);
  
    FOR_EACH_BB (bb)
      {
!       SET_BIT (visited, bb->index - (INVALID_BLOCK + 1));
  
        /* If a block has a single predecessor, that we've already
  	 processed, begin with the value data that was live at
  	 the end of the predecessor block.  */
        /* ??? Ought to use more intelligent queuing of blocks.  */
        if (EDGE_COUNT (bb->preds) == 1
! 	  && TEST_BIT (visited,
! 		       EDGE_PRED (bb, 0)->src->index - (INVALID_BLOCK + 1))
  	  && ! (EDGE_PRED (bb, 0)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
  	all_vd[bb->index] = all_vd[EDGE_PRED (bb, 0)->src->index];
        else
*************** copyprop_hardreg_forward (void)
*** 1778,1788 ****
  	need_refresh = true;
      }
  
!   /* Clear BB_VISITED flag on each basic block.  We do not need to
!      clear the one on ENTRY_BLOCK_PTR because it's already cleared
!      above.  */
!   FOR_EACH_BB (bb)
!     bb->flags &= ~BB_VISITED;
  
    if (need_refresh)
      {
--- 1775,1781 ----
  	need_refresh = true;
      }
  
!   sbitmap_free (visited);  
  
    if (need_refresh)
      {
Index: sched-rgn.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/sched-rgn.c,v
retrieving revision 1.89
diff -c -3 -p -r1.89 sched-rgn.c
*** sched-rgn.c	5 Jan 2005 23:19:22 -0000	1.89
--- sched-rgn.c	7 Jan 2005 23:49:21 -0000
*************** compute_trg_info (int trg)
*** 997,1002 ****
--- 997,1003 ----
    edgelst el;
    int i, j, k, update_idx;
    basic_block block;
+   sbitmap visited;
    edge_iterator ei;
    edge e;
  
*************** compute_trg_info (int trg)
*** 1006,1011 ****
--- 1007,1014 ----
    sp->is_speculative = 0;
    sp->src_prob = 100;
  
+   visited = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
+ 
    for (i = trg + 1; i < current_nr_blocks; i++)
      {
        sp = candidate_table + i;
*************** compute_trg_info (int trg)
*** 1043,1054 ****
  	     overrunning the end of the bblst_table.  */
  
  	  update_idx = 0;
  	  for (j = 0; j < el.nr_members; j++)
  	    {
  	      block = el.first_member[j]->src;
  	      FOR_EACH_EDGE (e, ei, block->succs)
  		{
! 		  if (!(e->dest->flags & BB_VISITED))
  		    {
  		      for (k = 0; k < el.nr_members; k++)
  			if (e == el.first_member[k])
--- 1046,1059 ----
  	     overrunning the end of the bblst_table.  */
  
  	  update_idx = 0;
+ 	  sbitmap_zero (visited);
  	  for (j = 0; j < el.nr_members; j++)
  	    {
  	      block = el.first_member[j]->src;
  	      FOR_EACH_EDGE (e, ei, block->succs)
  		{
! 		  if (!TEST_BIT (visited,
! 				 e->dest->index - (INVALID_BLOCK + 1)))
  		    {
  		      for (k = 0; k < el.nr_members; k++)
  			if (e == el.first_member[k])
*************** compute_trg_info (int trg)
*** 1057,1063 ****
  		      if (k >= el.nr_members)
  			{
  			  bblst_table[bblst_last++] = e->dest;
! 			  e->dest->flags |= BB_VISITED;
  			  update_idx++;
  			}
  		    }
--- 1062,1069 ----
  		      if (k >= el.nr_members)
  			{
  			  bblst_table[bblst_last++] = e->dest;
! 			  SET_BIT (visited,
! 				   e->dest->index - (INVALID_BLOCK + 1));
  			  update_idx++;
  			}
  		    }
*************** compute_trg_info (int trg)
*** 1065,1073 ****
  	    }
  	  sp->update_bbs.nr_members = update_idx;
  
- 	  FOR_ALL_BB (block)
- 	    block->flags &= ~BB_VISITED;
- 
  	  /* Make sure we didn't overrun the end of bblst_table.  */
  	  gcc_assert (bblst_last <= bblst_size);
  	}
--- 1071,1076 ----
*************** compute_trg_info (int trg)
*** 1079,1084 ****
--- 1082,1089 ----
  	  sp->src_prob = 0;
  	}
      }
+ 
+   sbitmap_free (visited);
  }
  
  /* Print candidates info, for debugging purposes.  Callable from debugger.  */
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.29
diff -c -3 -p -r2.29 tree-ssa-dce.c
*** tree-ssa-dce.c	13 Dec 2004 16:03:40 -0000	2.29
--- tree-ssa-dce.c	7 Jan 2005 23:49:21 -0000
*************** static sbitmap last_stmt_necessary;
*** 93,98 ****
--- 93,102 ----
     on the Ith edge.  */
  bitmap *control_dependence_map;
  
+ /* Vector indicating that a basic block has already had all the edges
+    processed that it is control dependent on.  */
+ sbitmap visited_control_parents;
+ 
  /* Execute CODE for each edge (given number EDGE_NUMBER within the CODE)
     for which the block with index N is control dependent.  */
  #define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE)		      \
*************** find_obviously_necessary_stmts (struct e
*** 482,492 ****
  	  NECESSARY (stmt) = 0;
  	  mark_stmt_if_obviously_necessary (stmt, el != NULL);
  	}
- 
-       /* Mark this basic block as `not visited'.  A block will be marked
- 	 visited when the edges that it is control dependent on have been
- 	 marked.  */
-       bb->flags &= ~BB_VISITED;
      }
  
    if (el)
--- 486,491 ----
*************** propagate_necessity (struct edge_list *e
*** 565,573 ****
  	     containing `i' is control dependent on, but only if we haven't
  	     already done so.  */
  	  basic_block bb = bb_for_stmt (i);
! 	  if (! (bb->flags & BB_VISITED))
  	    {
! 	      bb->flags |= BB_VISITED;
  	      mark_control_dependent_edges_necessary (bb, el);
  	    }
  	}
--- 564,573 ----
  	     containing `i' is control dependent on, but only if we haven't
  	     already done so.  */
  	  basic_block bb = bb_for_stmt (i);
! 	  if (bb != ENTRY_BLOCK_PTR
! 	      && ! TEST_BIT (visited_control_parents, bb->index))
  	    {
! 	      SET_BIT (visited_control_parents, bb->index);
  	      mark_control_dependent_edges_necessary (bb, el);
  	    }
  	}
*************** propagate_necessity (struct edge_list *e
*** 593,601 ****
  	      for (k = 0; k < PHI_NUM_ARGS (i); k++)
  		{
  		  basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
! 		  if (! (arg_bb->flags & BB_VISITED))
  		    {
! 		      arg_bb->flags |= BB_VISITED;
  		      mark_control_dependent_edges_necessary (arg_bb, el);
  		    }
  		}
--- 593,602 ----
  	      for (k = 0; k < PHI_NUM_ARGS (i); k++)
  		{
  		  basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
! 		  if (arg_bb != ENTRY_BLOCK_PTR
! 		      && ! TEST_BIT (visited_control_parents, arg_bb->index))
  		    {
! 		      SET_BIT (visited_control_parents, arg_bb->index);
  		      mark_control_dependent_edges_necessary (arg_bb, el);
  		    }
  		}
*************** tree_dce_done (bool aggressive)
*** 903,908 ****
--- 904,910 ----
  	BITMAP_XFREE (control_dependence_map[i]);
        free (control_dependence_map);
  
+       sbitmap_free (visited_control_parents);
        sbitmap_free (last_stmt_necessary);
      }
  
*************** perform_tree_ssa_dce (bool aggressive)
*** 939,944 ****
--- 941,949 ----
        find_all_control_dependences (el);
        timevar_pop (TV_CONTROL_DEPENDENCES);
  
+       visited_control_parents = sbitmap_alloc (last_basic_block);
+       sbitmap_zero (visited_control_parents);
+ 
        mark_dfs_back_edges ();
      }
  
Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-pre.c,v
retrieving revision 2.59
diff -c -3 -p -r2.59 tree-ssa-pre.c
*** tree-ssa-pre.c	8 Dec 2004 00:09:30 -0000	2.59
--- tree-ssa-pre.c	7 Jan 2005 23:49:21 -0000
*************** DEF_VEC_MALLOC_P (basic_block);
*** 1113,1164 ****
  
     ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
  
-    Iterate until fixpointed.
- 
     XXX: It would be nice to either write a set_clear, and use it for
     ANTIC_OUT, or to mark the antic_out set as deleted at the end
     of this routine, so that the pool can hand the same memory back out
     again for the next ANTIC_OUT.  */
  
- 
  static bool
! compute_antic_aux (basic_block block)
  {
-   basic_block son;
-   edge e;
    bool changed = false;
    value_set_t S, old, ANTIC_OUT;
    value_set_node_t node;
!   
    ANTIC_OUT = S = NULL;
!   /* If any edges from predecessors are abnormal, antic_in is empty, so
!      punt.  Remember that the block has an incoming abnormal edge by
!      setting the BB_VISITED flag.  */
!   if (! (block->flags & BB_VISITED))
!     {
!       edge_iterator ei;
!       FOR_EACH_EDGE (e, ei, block->preds)
! 	if (e->flags & EDGE_ABNORMAL)
! 	  {
! 	    block->flags |= BB_VISITED;
! 	    break;
! 	  }
!     }
!   if (block->flags & BB_VISITED)
!     {
!       S = NULL;
!       goto visit_sons;
!     }
!   
  
    old = set_new (false);
    set_copy (old, ANTIC_IN (block));
    ANTIC_OUT = set_new (true);
  
!   /* If the block has no successors, ANTIC_OUT is empty, because it is
!      the exit block.  */
!   if (EDGE_COUNT (block->succs) == 0);
! 
    /* If we have one successor, we could have some phi nodes to
       translate through.  */
    else if (EDGE_COUNT (block->succs) == 1)
--- 1113,1144 ----
  
     ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
  
     XXX: It would be nice to either write a set_clear, and use it for
     ANTIC_OUT, or to mark the antic_out set as deleted at the end
     of this routine, so that the pool can hand the same memory back out
     again for the next ANTIC_OUT.  */
  
  static bool
! compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
  {
    bool changed = false;
    value_set_t S, old, ANTIC_OUT;
    value_set_node_t node;
! 
    ANTIC_OUT = S = NULL;
! 
!   /* If any edges from predecessors are abnormal, antic_in is empty,
!      so do nothing.  */
!   if (block_has_abnormal_pred_edge)
!     goto maybe_dump_sets;
  
    old = set_new (false);
    set_copy (old, ANTIC_IN (block));
    ANTIC_OUT = set_new (true);
  
!   /* If the block has no successors, ANTIC_OUT is empty.  */
!   if (EDGE_COUNT (block->succs) == 0)
!     ;
    /* If we have one successor, we could have some phi nodes to
       translate through.  */
    else if (EDGE_COUNT (block->succs) == 1)
*************** compute_antic_aux (basic_block block)
*** 1206,1226 ****
  							 TMP_GEN (block),
  							 true);
    
!   /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
!      EXP_GEN - TMP_GEN */
!   for (node = S->head;
!        node;
!        node = node->next)
!     {
!       value_insert_into_set (ANTIC_IN (block), node->expr);
!     }
!   clean (ANTIC_IN (block));
!   
  
    if (!set_equal (old, ANTIC_IN (block)))
      changed = true;
  
!  visit_sons:
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        if (ANTIC_OUT)
--- 1186,1201 ----
  							 TMP_GEN (block),
  							 true);
    
!   /* Then union in the ANTIC_OUT - TMP_GEN values,
!      to get ANTIC_OUT U EXP_GEN - TMP_GEN */
!   for (node = S->head; node; node = node->next)
!     value_insert_into_set (ANTIC_IN (block), node->expr);
  
+   clean (ANTIC_IN (block));
    if (!set_equal (old, ANTIC_IN (block)))
      changed = true;
  
!  maybe_dump_sets:
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        if (ANTIC_OUT)
*************** compute_antic_aux (basic_block block)
*** 1228,1270 ****
        print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
        if (S)
  	print_value_set (dump_file, S, "S", block->index);
- 
      }
  
-   for (son = first_dom_son (CDI_POST_DOMINATORS, block);
-        son;
-        son = next_dom_son (CDI_POST_DOMINATORS, son))
-     {
-       changed |= compute_antic_aux (son);
-     }
    return changed;
  }
  
! /* Compute ANTIC sets.  */
  
  static void
  compute_antic (void)
  {
!   bool changed = true;
!   basic_block bb;
    int num_iterations = 0;
!   FOR_ALL_BB (bb)
      {
!       ANTIC_IN (bb) = set_new (true);
!       gcc_assert (!(bb->flags & BB_VISITED));
      }
  
    while (changed)
      {
!       num_iterations++;
        changed = false;
!       changed = compute_antic_aux (EXIT_BLOCK_PTR);
!     }
!   FOR_ALL_BB (bb)
!     {
!       bb->flags &= ~BB_VISITED;
      }
!   if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
      fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
  }
  
--- 1203,1284 ----
        print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
        if (S)
  	print_value_set (dump_file, S, "S", block->index);
      }
  
    return changed;
  }
  
! /* Compute ANTIC sets.  Iterates until fixpointed.  */
  
  static void
  compute_antic (void)
  {
!   bool changed= true;
    int num_iterations = 0;
!   basic_block block, *worklist;
!   size_t sp = 0;
!   sbitmap has_abnormal_preds;
! 
!   /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
!      We pre-build the map of blocks with incoming abnormal edges here.  */
!   has_abnormal_preds = sbitmap_alloc (last_basic_block);
!   sbitmap_zero (has_abnormal_preds);
!   FOR_EACH_BB (block)
      {
!       edge_iterator ei;
!       edge e;
! 
!       FOR_EACH_EDGE (e, ei, block->preds)
!         if (e->flags & EDGE_ABNORMAL)
!           {
!             SET_BIT (has_abnormal_preds, block->index);
!             break;
!           }
! 
!       /* While we are here, give empty ANTIC_IN sets to each block.  */
!       ANTIC_IN (block) = set_new (true);
      }
+   /* At the exit block we anticipate nothing.  */
+   ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true);
  
+   /* Allocate the worklist.  */
+   worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
+ 
+   /* Loop until fixpointed.  */
    while (changed)
      {
!       basic_block son, bb;
! 
        changed = false;
!       num_iterations++;
! 
!       /* Seed the algorithm by putting post-dominator children of
!          the exit block in the worklist.  */
!       for (son = first_dom_son (CDI_POST_DOMINATORS, EXIT_BLOCK_PTR);
! 	   son;
! 	   son = next_dom_son (CDI_POST_DOMINATORS, son))
! 	worklist[sp++] = son;
! 
!       /* Now visit all blocks in a DFS of the post dominator tree.  */
!       while (sp)
! 	{
! 	  bool bb_has_abnormal_pred;
! 
! 	  bb = worklist[--sp];
! 	  bb_has_abnormal_pred = TEST_BIT (has_abnormal_preds, bb->index);
!  	  changed |= compute_antic_aux (bb, bb_has_abnormal_pred);
! 
! 	  for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
! 	       son;
! 	       son = next_dom_son (CDI_POST_DOMINATORS, son))
! 	    worklist[sp++] = son;
! 	}
      }
! 
!   free (worklist);
!   sbitmap_free (has_abnormal_preds);
! 
!   if (dump_file && (dump_flags & TDF_STATS))
      fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
  }
  


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