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] Fold bb_ann_d into basic_block_def.


Hi,

Attached is a patch to fold bb_ann_d into basic_block_def.

Currently, bb_ann_d has the following three members.

  tree phi_nodes;
  unsigned incoming_edge_threaded : 1;
  struct edge_prediction *predictions;

Since incoming_edge_threaded is used only for communication between
DOM and threadupdate, we can easily replace it with a bitmap of basic
blocks and have DOM pass it to threadupdate.

Now we are left with two pointers, namely phi_nodes and predictions.
Note that we need a pointer to point to bb_ann_d anyway, so on a
32-bit machine, we use a 4-byte pointer to point to an 8-byte object,
which isn't really efficient.

If we fold bb_ann_d into basic_block_def, obviously, we don't have to
maintain bb_ann_d.  Also, we can cut down double-dereferneces required
for phi_nodes (bb) and bb_ann (bb)->predictions at a small cost of 4
bytes for each instance of basic_block_def.

Here are timings for five runs of several cc1-i files.  (Actually,
each is run 6 times with the timing from the first run discarded to
discount host cache effects.)

               original patched   diff%
---------------------------------------
c-common.i       22.361  22.344 -0.076%
combine.i        18.716  18.722 +0.032%
fold-const.i     42.556  42.478 -0.183%
reload1.i        14.507  14.481 -0.179%
reload.i         13.400  13.364 -0.268%
insn-attrtab.i  201.553 200.158 -0.692%

Tested on i686-pc-linux-gnu.  OK to apply?

p.s.
I don't think this patch is too big, but if you would like me to move
one member to basic_block_def at a time, I can do that for you.

Kazu Hirata

2005-05-26  Kazu Hirata  <kazu@cs.umass.edu>

	* basic-block.h (basic_block_def): Add phi_nodes and
	predictions.  Remove tree_annotations.
	* predict.c (tree_predicted_by_p, tree_predict_edge,
	combine_predictions_for_bb): Adjust references to predictions.
	* tree-cfg.c (init_empty_tree_cfg, create_bb): Don't call
	create_block_annotation.
	(create_block_annotation, free_blocks_annotatios,
	clear_blocks_annotations): Remove.
	(dump_cfg_stats): Don't print out the memory spent on
	bb_ann_d.
	(delete_tree_cfg_annotations): Don't call free_blocks_annotations.
	* tree-flow-inline.h (bb_ann): Remove.
	(phi_nodes, set_phi_nodes): Update references to phi_nodes.
	* tree-flow.h (bb_ann_d): Remove.
	* tree-if-conv.c (process_phi_nodes): Update a reference to
	phi_nodes.
	* tree-phinodes.c (reserve_phi_args_for_new_edge,
	create_phi_node, remove_phi_node): Likewise.
	* tree-pretty-print.c (dump_generic_bb_buff): Don't call bb_ann.
	* tree-ssa-dom.c (threaded_blocks): New.
	(tree_ssa_dominator_optimize): Initialize, clear, and free
	threaded_blocks. Update a call to thread_through_all_blocks.
	(thread_across_edge): Use threaded_blocks instead of setting
	incoming_edge_threaded.
	* tree-ssa-threadupdate.c (threaded_through_all_blocks): Take
	a bitmap of blocks that are threaded through.
	* tree.h: Move the prototype of threaded_through_blocks to
	tree-flow.h.

Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.257
diff -u -d -p -r1.257 basic-block.h
--- basic-block.h	19 May 2005 10:38:36 -0000	1.257
+++ basic-block.h	25 May 2005 22:43:12 -0000
@@ -185,6 +185,9 @@ struct loops;
 /* Declared in tree-flow.h.  */
 struct bb_ann_d;
 
+/* Declared in tree-flow.h.  */
+struct edge_prediction;
+
 /* A basic block is a sequence of instructions with only entry and
    only one exit.  If any one of the instructions are executed, they
    will all be executed, and in sequence from first to last.
@@ -246,8 +249,11 @@ struct basic_block_def GTY((chain_next (
   /* The data used by basic block copying and reordering functions.  */
   struct reorder_block_def * rbi;
 
-  /* Annotations used at the tree level.  */
-  struct bb_ann_d *tree_annotations;
+  /* Chain of PHI nodes for this block.  */
+  tree phi_nodes;
+
+  /* A list of predictions.  */
+  struct edge_prediction *predictions;
 
   /* Expected number of executions: calculated in profile.c.  */
   gcov_type count;
Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.145
diff -u -d -p -r1.145 predict.c
--- predict.c	5 Apr 2005 19:04:55 -0000	1.145
+++ predict.c	25 May 2005 22:43:12 -0000
@@ -171,8 +171,8 @@ rtl_predicted_by_p (basic_block bb, enum
 bool
 tree_predicted_by_p (basic_block bb, enum br_predictor predictor)
 {
-  struct edge_prediction *i = bb_ann (bb)->predictions;
-  for (i = bb_ann (bb)->predictions; i; i = i->next)
+  struct edge_prediction *i;
+  for (i = bb->predictions; i; i = i->next)
     if (i->predictor == predictor)
       return true;
   return false;
@@ -233,8 +233,8 @@ tree_predict_edge (edge e, enum br_predi
 {
   struct edge_prediction *i = ggc_alloc (sizeof (struct edge_prediction));
 
-  i->next = bb_ann (e->src)->predictions;
-  bb_ann (e->src)->predictions = i;
+  i->next = e->src->predictions;
+  e->src->predictions = i;
   i->probability = probability;
   i->predictor = predictor;
   i->edge = e;
@@ -488,7 +488,7 @@ combine_predictions_for_bb (FILE *file, 
     {
       if (!bb->count)
 	set_even_probabilities (bb);
-      bb_ann (bb)->predictions = NULL;
+      bb->predictions = NULL;
       if (file)
 	fprintf (file, "%i edges in bb %i predicted to even probabilities\n",
 		 nedges, bb->index);
@@ -500,7 +500,7 @@ combine_predictions_for_bb (FILE *file, 
 
   /* We implement "first match" heuristics and use probability guessed
      by predictor with smallest index.  */
-  for (pred = bb_ann (bb)->predictions; pred; pred = pred->next)
+  for (pred = bb->predictions; pred; pred = pred->next)
     {
       int predictor = pred->predictor;
       int probability = pred->probability;
@@ -546,7 +546,7 @@ combine_predictions_for_bb (FILE *file, 
     combined_probability = best_probability;
   dump_prediction (file, PRED_COMBINED, combined_probability, bb, true);
 
-  for (pred = bb_ann (bb)->predictions; pred; pred = pred->next)
+  for (pred = bb->predictions; pred; pred = pred->next)
     {
       int predictor = pred->predictor;
       int probability = pred->probability;
@@ -556,7 +556,7 @@ combine_predictions_for_bb (FILE *file, 
       dump_prediction (file, predictor, probability, bb,
 		       !first_match || best_predictor == predictor);
     }
-  bb_ann (bb)->predictions = NULL;
+  bb->predictions = NULL;
 
   if (!bb->count)
     {
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.197
diff -u -d -p -r2.197 tree-cfg.c
--- tree-cfg.c	25 May 2005 03:59:00 -0000	2.197
+++ tree-cfg.c	25 May 2005 22:43:13 -0000
@@ -95,9 +95,6 @@ static bool found_computed_goto;
 
 /* Basic blocks and flowgraphs.  */
 static basic_block create_bb (void *, void *, basic_block);
-static void create_block_annotation (basic_block);
-static void free_blocks_annotations (void);
-static void clear_blocks_annotations (void);
 static void make_blocks (tree);
 static void factor_computed_gotos (void);
 
@@ -149,9 +146,6 @@ init_empty_tree_cfg (void)
 
   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
-
-  create_block_annotation (ENTRY_BLOCK_PTR);
-  create_block_annotation (EXIT_BLOCK_PTR);
 }
 
 /*---------------------------------------------------------------------------
@@ -322,37 +316,6 @@ factor_computed_gotos (void)
 }
 
 
-/* Create annotations for a single basic block.  */
-
-static void
-create_block_annotation (basic_block bb)
-{
-  /* Verify that the tree_annotations field is clear.  */
-  gcc_assert (!bb->tree_annotations);
-  bb->tree_annotations = ggc_alloc_cleared (sizeof (struct bb_ann_d));
-}
-
-
-/* Free the annotations for all the basic blocks.  */
-
-static void free_blocks_annotations (void)
-{
-  clear_blocks_annotations ();  
-}
-
-
-/* Clear the annotations for all the basic blocks.  */
-
-static void
-clear_blocks_annotations (void)
-{
-  basic_block bb;
-
-  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
-    bb->tree_annotations = NULL;
-}
-
-
 /* Build a flowgraph for the statement_list STMT_LIST.  */
 
 static void
@@ -431,8 +394,6 @@ create_bb (void *h, void *e, basic_block
   /* Add the newly created block to the array.  */
   BASIC_BLOCK (last_basic_block) = bb;
 
-  create_block_annotation (bb);
-
   n_basic_blocks++;
   last_basic_block++;
 
@@ -2561,11 +2522,6 @@ dump_cfg_stats (FILE *file)
   total += size;
   fprintf (file, fmt_str_1, "Edges", num_edges, SCALE (size), LABEL (size));
 
-  size = n_basic_blocks * sizeof (struct bb_ann_d);
-  total += size;
-  fprintf (file, fmt_str_1, "Basic block annotations", n_basic_blocks,
-	   SCALE (size), LABEL (size));
-
   fprintf (file, "---------------------------------------------------------\n");
   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
 	   LABEL (total));
@@ -2876,8 +2832,6 @@ void
 delete_tree_cfg_annotations (void)
 {
   basic_block bb;
-  if (n_basic_blocks > 0)
-    free_blocks_annotations ();
 
   label_to_block_map = NULL;
   FOR_EACH_BB (bb)
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.46
diff -u -d -p -r2.46 tree-flow-inline.h
--- tree-flow-inline.h	4 May 2005 20:31:10 -0000	2.46
+++ tree-flow-inline.h	25 May 2005 22:43:13 -0000
@@ -494,19 +494,12 @@ addresses_taken (tree stmt)
   return ann ? ann->addresses_taken : NULL;
 }
 
-/* Return the basic_block annotation for BB.  */
-static inline bb_ann_t
-bb_ann (basic_block bb)
-{
-  return (bb_ann_t)bb->tree_annotations;
-}
-
 /* Return the PHI nodes for basic block BB, or NULL if there are no
    PHI nodes.  */
 static inline tree
 phi_nodes (basic_block bb)
 {
-  return bb_ann (bb)->phi_nodes;
+  return bb->phi_nodes;
 }
 
 /* Set list of phi nodes of a basic block BB to L.  */
@@ -516,7 +509,7 @@ set_phi_nodes (basic_block bb, tree l)
 {
   tree phi;
 
-  bb_ann (bb)->phi_nodes = l;
+  bb->phi_nodes = l;
   for (phi = l; phi; phi = PHI_CHAIN (phi))
     set_bb_for_stmt (phi, bb);
 }
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.111
diff -u -d -p -r2.111 tree-flow.h
--- tree-flow.h	24 May 2005 19:57:49 -0000	2.111
+++ tree-flow.h	25 May 2005 22:43:14 -0000
@@ -377,25 +377,7 @@ struct edge_prediction GTY((chain_next (
   int probability;
 };
 
-/*---------------------------------------------------------------------------
-		  Block annotations stored in basic_block.tree_annotations
----------------------------------------------------------------------------*/
-struct bb_ann_d GTY(())
-{
-  /* Chain of PHI nodes for this block.  */
-  tree phi_nodes;
-
-  /* Nonzero if one or more incoming edges to this block should be threaded
-     to an outgoing edge of this block.  */
-  unsigned incoming_edge_threaded : 1;
-
-  struct edge_prediction *predictions;
-};
-
-typedef struct bb_ann_d *bb_ann_t;
-
 /* Accessors for basic block annotations.  */
-static inline bb_ann_t bb_ann (basic_block);
 static inline tree phi_nodes (basic_block);
 static inline void set_phi_nodes (basic_block, tree);
 
@@ -782,6 +764,9 @@ extern void linear_transform_loops (stru
 /* In tree-ssa-loop-ivopts.c  */
 extern bool expr_invariant_in_loop_p (struct loop *, tree);
 
+/* In tree-ssa-threadupdate.c.  */
+extern bool thread_through_all_blocks (bitmap);
+
 /* In gimplify.c  */
 tree force_gimple_operand (tree, tree *, bool, tree);
 tree force_gimple_operand_bsi (block_stmt_iterator *, tree, bool, tree);
Index: tree-if-conv.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-if-conv.c,v
retrieving revision 2.41
diff -u -d -p -r2.41 tree-if-conv.c
--- tree-if-conv.c	11 May 2005 18:27:33 -0000	2.41
+++ tree-if-conv.c	25 May 2005 22:43:14 -0000
@@ -840,7 +840,7 @@ process_phi_nodes (struct loop *loop)
 	  release_phi_node (phi);
 	  phi = next;
 	}
-      bb_ann (bb)->phi_nodes = NULL;
+      bb->phi_nodes = NULL;
     }
   return;
 }
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-phinodes.c,v
retrieving revision 2.36
diff -u -d -p -r2.36 tree-phinodes.c
--- tree-phinodes.c	3 May 2005 12:19:41 -0000	2.36
+++ tree-phinodes.c	25 May 2005 22:43:14 -0000
@@ -314,7 +314,7 @@ reserve_phi_args_for_new_edge (basic_blo
   int len = EDGE_COUNT (bb->preds);
   int cap = ideal_phi_node_len (len + 4);
 
-  for (loc = &(bb_ann (bb)->phi_nodes);
+  for (loc = &(bb->phi_nodes);
        *loc;
        loc = &PHI_CHAIN (*loc))
     {
@@ -354,7 +354,7 @@ create_phi_node (tree var, basic_block b
 
   /* Add the new PHI node to the list of PHI nodes for block BB.  */
   PHI_CHAIN (phi) = phi_nodes (bb);
-  bb_ann (bb)->phi_nodes = phi;
+  bb->phi_nodes = phi;
 
   /* Associate BB to the PHI node.  */
   set_bb_for_stmt (phi, bb);
@@ -450,7 +450,7 @@ remove_phi_node (tree phi, tree prev)
     }
   else
     {
-      for (loc = &(bb_ann (bb_for_stmt (phi))->phi_nodes);
+      for (loc = &(bb_for_stmt (phi)->phi_nodes);
 	   *loc != phi;
 	   loc = &PHI_CHAIN (*loc))
 	;
Index: tree-pretty-print.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pretty-print.c,v
retrieving revision 2.58
diff -u -d -p -r2.58 tree-pretty-print.c
--- tree-pretty-print.c	3 May 2005 12:19:41 -0000	2.58
+++ tree-pretty-print.c	25 May 2005 22:43:14 -0000
@@ -2341,8 +2341,7 @@ dump_generic_bb_buff (pretty_printer *bu
 
   dump_bb_header (buffer, bb, indent, flags);
 
-  if (bb_ann (bb))
-    dump_phi_nodes (buffer, bb, indent, flags);
+  dump_phi_nodes (buffer, bb, indent, flags);
 
   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
     {
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.113
diff -u -d -p -r2.113 tree-ssa-dom.c
--- tree-ssa-dom.c	24 May 2005 02:53:57 -0000	2.113
+++ tree-ssa-dom.c	25 May 2005 22:43:15 -0000
@@ -141,6 +141,10 @@ static VEC(tree,heap) *const_and_copies_
    know their exact value.  */
 static bitmap nonzero_vars;
 
+/* Bitmap of blocks that are scheduled to be threaded through.  This
+   is used to communicate with thread_through_blocks.  */
+static bitmap threaded_blocks;
+
 /* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
    when the current block is finalized. 
 
@@ -370,6 +374,7 @@ tree_ssa_dominator_optimize (void)
   vrp_variables_stack = VEC_alloc (tree, heap, 20);
   stmts_to_rescan = VEC_alloc (tree, heap, 20);
   nonzero_vars = BITMAP_ALLOC (NULL);
+  threaded_blocks = BITMAP_ALLOC (NULL);
   need_eh_cleanup = BITMAP_ALLOC (NULL);
 
   /* Setup callbacks for the generic dominator tree walker.  */
@@ -445,7 +450,7 @@ tree_ssa_dominator_optimize (void)
       }
 
       /* Thread jumps, creating duplicate blocks as needed.  */
-      cfg_altered |= thread_through_all_blocks ();
+      cfg_altered |= thread_through_all_blocks (threaded_blocks);
 
       /* Removal of statements may make some EH edges dead.  Purge
 	 such edges from the CFG as needed.  */
@@ -480,6 +485,7 @@ tree_ssa_dominator_optimize (void)
 
       /* Reinitialize the various tables.  */
       bitmap_clear (nonzero_vars);
+      bitmap_clear (threaded_blocks);
       htab_empty (avail_exprs);
       htab_empty (vrp_data);
 
@@ -523,6 +529,7 @@ tree_ssa_dominator_optimize (void)
 
   /* Free nonzero_vars.  */
   BITMAP_FREE (nonzero_vars);
+  BITMAP_FREE (threaded_blocks);
   BITMAP_FREE (need_eh_cleanup);
   
   VEC_free (tree, heap, avail_exprs_stack);
@@ -830,7 +837,7 @@ thread_across_edge (struct dom_walk_data
 	      else
 		edge_info = allocate_edge_info (e);
 	      edge_info->redirection_target = taken_edge;
-	      bb_ann (e->dest)->incoming_edge_threaded = true;
+	      bitmap_set_bit (threaded_blocks, e->dest->index);
 	    }
 	}
     }
Index: tree-ssa-threadupdate.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-threadupdate.c,v
retrieving revision 2.26
diff -u -d -p -r2.26 tree-ssa-threadupdate.c
--- tree-ssa-threadupdate.c	10 May 2005 20:21:28 -0000	2.26
+++ tree-ssa-threadupdate.c	25 May 2005 22:43:15 -0000
@@ -802,22 +802,20 @@ thread_block (basic_block bb)
    Returns true if one or more edges were threaded, false otherwise.  */
 
 bool
-thread_through_all_blocks (void)
+thread_through_all_blocks (bitmap threaded_blocks)
 {
-  basic_block bb;
   bool retval = false;
+  unsigned int i;
+  bitmap_iterator bi;
 
   rediscover_loops_after_threading = false;
 
-  FOR_EACH_BB (bb)
+  EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi)
     {
-      if (bb_ann (bb)->incoming_edge_threaded
-	  && EDGE_COUNT (bb->preds) > 0)
-	{
-	  retval |= thread_block (bb);
-	  bb_ann (bb)->incoming_edge_threaded = false;
-	  
-	}
+      basic_block bb = BASIC_BLOCK (i);
+
+      if (EDGE_COUNT (bb->preds) > 0)
+	retval |= thread_block (bb);
     }
 
   return retval;
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.729
diff -u -d -p -r1.729 tree.h
--- tree.h	24 May 2005 20:19:13 -0000	1.729
+++ tree.h	25 May 2005 22:43:16 -0000
@@ -3975,9 +3975,6 @@ extern int tree_node_sizes[];
    restricted to creating gimple expressions.  */
 extern bool in_gimple_form;
 
-/* In tree-ssa-threadupdate.c.  */
-extern bool thread_through_all_blocks (void);
-
 /* In tree-gimple.c.  */
 extern tree get_base_address (tree t);
 


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