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]

tree profiling merge: profile support in cgraph


Hi,
this patch adds neccesary infrastructure for profile guided inlining (and for
considering loop nest when profile is unavailable) While the profile is
maintained, it is never actually used yet nor initialized.  I am going to do
that in followup patches.  I just wanted to go throught the interface changes
first.

Note that I also moved REG_BR_PROB_BASE from rtl.h into basic-block.h so
we have one reason fewer to include rtl.h in all tree based
optimizers...

Bootstrapped/regtested i686-pc-gnu-linux, will commit it shortly.
Honza

2005-05-19  Jan Hubicka  <jh@suse.cz>
	* basic-block.h (REG_BR_PROB_BASE): Define.
	* cgraph.c (cgraph_create_edge): Initialize loop_nest and count.
	(dump_cgraph_node): Dump count.
	(cgraph_clone_edge): Rescale counts.
	(cgraph_clone_node): Likewise.
	* cgraph.h: Include basic-block.h
	(cgraph_node): Add count.
	(cgraph_edge): Add count and loop_nest.
	(cgraph_node, cgraph_edge, cgraph_clone_edge, cgraph_clone_node):
	Update prototypes.
	* cgraphunit.c: Kill now redundant inlining comment.
	(cgraph_create_edges): Make static, maintain current basic block;
	fix pasto.
	(record_call_1): Fill in new fields.
	* ipa-inline.c (cgraph_clone_inlined_nodes): Update call of
	cgraph_clone_node.
	(cgraph_decide_recursive_inlining): Likewise.
	* rtl.h (REG_BR_PROB_BASE): Kill.
	* tree-inline.c (copy_body_r): Update call of cgraph_clone_edge.
	(expand_call_inline): Update call of cgraph_create_edge.
	* tree-optimize.c (tree_rest_of_compilation): Likewise.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.256
diff -c -3 -p -r1.256 basic-block.h
*** basic-block.h	13 May 2005 13:34:17 -0000	1.256
--- basic-block.h	18 May 2005 21:44:35 -0000
*************** struct edge_list
*** 555,560 ****
--- 555,563 ----
    edge *index_to_edge;
  };
  
+ /* The base value for branch probability notes and edge probabilities.  */
+ #define REG_BR_PROB_BASE  10000
+ 
  /* This is the value which indicates no edge is present.  */
  #define EDGE_INDEX_NO_EDGE	-1
  
Index: cgraph.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraph.c,v
retrieving revision 1.71
diff -c -3 -p -r1.71 cgraph.c
*** cgraph.c	23 Apr 2005 21:27:38 -0000	1.71
--- cgraph.c	18 May 2005 21:44:35 -0000
*************** cgraph_edge (struct cgraph_node *node, t
*** 275,281 ****
  
  struct cgraph_edge *
  cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
! 		    tree call_expr)
  {
    struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge));
  #ifdef ENABLE_CHECKING
--- 275,281 ----
  
  struct cgraph_edge *
  cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
! 		    tree call_expr, gcov_type count, int nest)
  {
    struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge));
  #ifdef ENABLE_CHECKING
*************** cgraph_create_edge (struct cgraph_node *
*** 312,317 ****
--- 312,319 ----
      caller->callees->prev_callee = edge;
    caller->callees = edge;
    callee->callers = edge;
+   edge->count = count;
+   edge->loop_nest = nest;
    return edge;
  }
  
*************** dump_cgraph_node (FILE *f, struct cgraph
*** 559,564 ****
--- 561,569 ----
      fprintf (f, " (inline copy in %s/%i)",
  	     cgraph_node_name (node->global.inlined_to),
  	     node->global.inlined_to->uid);
+   if (node->count)
+     fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
+ 	     (HOST_WIDEST_INT)node->count);
    if (node->local.self_insns)
      fprintf (f, " %i insns", node->local.self_insns);
    if (node->global.insns && node->global.insns != node->local.self_insns)
*************** dump_cgraph_node (FILE *f, struct cgraph
*** 587,592 ****
--- 592,600 ----
      {
        fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
  	       edge->caller->uid);
+       if (edge->count)
+ 	fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
+ 		 (HOST_WIDEST_INT)edge->count);
        if (!edge->inline_failed)
  	fprintf(f, "(inlined) ");
      }
*************** cgraph_function_possibly_inlined_p (tree
*** 829,848 ****
  
  /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
  struct cgraph_edge *
! cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n, tree call_expr)
  {
!   struct cgraph_edge *new = cgraph_create_edge (n, e->callee, call_expr);
  
    new->inline_failed = e->inline_failed;
    return new;
  }
  
! /* Create node representing clone of N.  */
  struct cgraph_node *
! cgraph_clone_node (struct cgraph_node *n)
  {
    struct cgraph_node *new = cgraph_create_node ();
    struct cgraph_edge *e;
  
    new->decl = n->decl;
    new->origin = n->origin;
--- 837,864 ----
  
  /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
  struct cgraph_edge *
! cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
! 		   tree call_expr, int count_scale, int loop_nest)
  {
!   struct cgraph_edge *new;
! 
!   new = cgraph_create_edge (n, e->callee, call_expr,
!                             e->count * count_scale / REG_BR_PROB_BASE,
! 		            e->loop_nest + loop_nest);
  
    new->inline_failed = e->inline_failed;
+   e->count -= new->count;
    return new;
  }
  
! /* Create node representing clone of N executed COUNT times.  Decrease
!    the execution counts from original node too.  */
  struct cgraph_node *
! cgraph_clone_node (struct cgraph_node *n, gcov_type count, int loop_nest)
  {
    struct cgraph_node *new = cgraph_create_node ();
    struct cgraph_edge *e;
+   int count_scale;
  
    new->decl = n->decl;
    new->origin = n->origin;
*************** cgraph_clone_node (struct cgraph_node *n
*** 855,863 ****
    new->local = n->local;
    new->global = n->global;
    new->rtl = n->rtl;
  
    for (e = n->callees;e; e=e->next_callee)
!     cgraph_clone_edge (e, new, e->call_expr);
  
    new->next_clone = n->next_clone;
    new->prev_clone = n;
--- 871,885 ----
    new->local = n->local;
    new->global = n->global;
    new->rtl = n->rtl;
+   new->count = count;
+   if (n->count)
+     count_scale = new->count * REG_BR_PROB_BASE / n->count;
+   else
+     count_scale = 0;
+   n->count -= count;
  
    for (e = n->callees;e; e=e->next_callee)
!     cgraph_clone_edge (e, new, e->call_expr, count_scale, loop_nest);
  
    new->next_clone = n->next_clone;
    new->prev_clone = n;
Index: cgraph.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraph.h,v
retrieving revision 1.52
diff -c -3 -p -r1.52 cgraph.h
*** cgraph.h	17 May 2005 16:56:22 -0000	1.52
--- cgraph.h	18 May 2005 21:44:35 -0000
*************** Software Foundation, 59 Temple Place - S
*** 22,27 ****
--- 22,28 ----
  #ifndef GCC_CGRAPH_H
  #define GCC_CGRAPH_H
  #include "tree.h"
+ #include "basic-block.h"
  
  /* Information about the function collected locally.
     Available after function is analyzed.  */
*************** struct cgraph_node GTY((chain_next ("%h.
*** 109,114 ****
--- 112,119 ----
    struct cgraph_global_info global;
    struct cgraph_rtl_info rtl;
    
+   /* Expected number of executions: calculated in profile.c.  */
+   gcov_type count;
    /* Unique id of the node.  */
    int uid;
    /* Set when function must be output - it is externally visible
*************** struct cgraph_edge GTY((chain_next ("%h.
*** 141,146 ****
--- 146,155 ----
    /* When NULL, inline this call.  When non-NULL, points to the explanation
       why function was not inlined.  */
    const char *inline_failed;
+   /* Expected number of executions: calculated in profile.c.  */
+   gcov_type count;
+   /* Depth of loop nest, 1 means no loop nest.  */
+   int loop_nest;
  };
  
  /* The cgraph_varpool data structure.
*************** void cgraph_remove_node (struct cgraph_n
*** 190,214 ****
  void cgraph_node_remove_callees (struct cgraph_node *node);
  struct cgraph_edge *cgraph_create_edge (struct cgraph_node *,
  					struct cgraph_node *,
! 				        tree);
! struct cgraph_node *cgraph_node (tree decl);
  struct cgraph_node *cgraph_node_for_asm (tree asmname);
! struct cgraph_edge *cgraph_edge (struct cgraph_node *, tree call_expr);
  struct cgraph_local_info *cgraph_local_info (tree);
  struct cgraph_global_info *cgraph_global_info (tree);
  struct cgraph_rtl_info *cgraph_rtl_info (tree);
  const char * cgraph_node_name (struct cgraph_node *);
! struct cgraph_edge * cgraph_clone_edge (struct cgraph_edge *, struct cgraph_node *, tree);
! struct cgraph_node * cgraph_clone_node (struct cgraph_node *);
  
! struct cgraph_varpool_node *cgraph_varpool_node (tree decl);
  struct cgraph_varpool_node *cgraph_varpool_node_for_asm (tree asmname);
  void cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *);
  void cgraph_varpool_finalize_decl (tree);
  void cgraph_redirect_edge_callee (struct cgraph_edge *, struct cgraph_node *);
  
  bool cgraph_function_possibly_inlined_p (tree);
! void cgraph_unnest_node (struct cgraph_node *node);
  void cgraph_varpool_enqueue_needed_node (struct cgraph_varpool_node *);
  void cgraph_varpool_reset_queue (void);
  bool decide_is_variable_needed (struct cgraph_varpool_node *, tree);
--- 199,223 ----
  void cgraph_node_remove_callees (struct cgraph_node *node);
  struct cgraph_edge *cgraph_create_edge (struct cgraph_node *,
  					struct cgraph_node *,
! 				        tree, gcov_type, int);
! struct cgraph_node *cgraph_node (tree);
  struct cgraph_node *cgraph_node_for_asm (tree asmname);
! struct cgraph_edge *cgraph_edge (struct cgraph_node *, tree);
  struct cgraph_local_info *cgraph_local_info (tree);
  struct cgraph_global_info *cgraph_global_info (tree);
  struct cgraph_rtl_info *cgraph_rtl_info (tree);
  const char * cgraph_node_name (struct cgraph_node *);
! struct cgraph_edge * cgraph_clone_edge (struct cgraph_edge *, struct cgraph_node *, tree, int, int);
! struct cgraph_node * cgraph_clone_node (struct cgraph_node *, gcov_type, int);
  
! struct cgraph_varpool_node *cgraph_varpool_node (tree);
  struct cgraph_varpool_node *cgraph_varpool_node_for_asm (tree asmname);
  void cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *);
  void cgraph_varpool_finalize_decl (tree);
  void cgraph_redirect_edge_callee (struct cgraph_edge *, struct cgraph_node *);
  
  bool cgraph_function_possibly_inlined_p (tree);
! void cgraph_unnest_node (struct cgraph_node *);
  void cgraph_varpool_enqueue_needed_node (struct cgraph_varpool_node *);
  void cgraph_varpool_reset_queue (void);
  bool decide_is_variable_needed (struct cgraph_varpool_node *, tree);
*************** bool cgraph_varpool_assemble_pending_dec
*** 219,225 ****
  void cgraph_finalize_function (tree, bool);
  void cgraph_lower_function (struct cgraph_node *);
  void cgraph_finalize_compilation_unit (void);
- void cgraph_create_edges (struct cgraph_node *, tree);
  void cgraph_optimize (void);
  void cgraph_mark_needed_node (struct cgraph_node *);
  void cgraph_mark_reachable_node (struct cgraph_node *);
--- 228,233 ----
Index: cgraphunit.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraphunit.c,v
retrieving revision 1.105
diff -c -3 -p -r1.105 cgraphunit.c
*** cgraphunit.c	17 May 2005 16:56:22 -0000	1.105
--- cgraphunit.c	18 May 2005 21:44:35 -0000
*************** Software Foundation, 59 Temple Place - S
*** 136,168 ****
  	decision on whether function is needed is made more conservative so
  	uninlininable static functions are needed too.  During the call-graph
  	construction the edge destinations are not marked as reachable and it
! 	is completely relied upn assemble_variable to mark them.
! 	
!      Inlining decision heuristics
!         ??? Move this to separate file after tree-ssa merge.
! 
! 	We separate inlining decisions from the inliner itself and store it
! 	inside callgraph as so called inline plan.  Refer to cgraph.c
! 	documentation about particular representation of inline plans in the
! 	callgraph
! 
! 	The implementation of particular heuristics is separated from
! 	the rest of code to make it easier to replace it with more complicated
! 	implementation in the future.  The rest of inlining code acts as a
! 	library aimed to modify the callgraph and verify that the parameters
! 	on code size growth fits.
! 
! 	To mark given call inline, use cgraph_mark_inline function, the
! 	verification is performed by cgraph_default_inline_p and
! 	cgraph_check_inline_limits.
! 
! 	The heuristics implements simple knapsack style algorithm ordering
! 	all functions by their "profitability" (estimated by code size growth)
! 	and inlining them in priority order.
! 
! 	cgraph_decide_inlining implements heuristics taking whole callgraph
! 	into account, while cgraph_decide_inlining_incrementally considers
! 	only one function at a time and is used in non-unit-at-a-time mode.  */
  
  
  #include "config.h"
--- 136,142 ----
  	decision on whether function is needed is made more conservative so
  	uninlininable static functions are needed too.  During the call-graph
  	construction the edge destinations are not marked as reachable and it
! 	is completely relied upn assemble_variable to mark them.  */
  
  
  #include "config.h"
*************** static void cgraph_expand_function (stru
*** 198,203 ****
--- 172,178 ----
  static tree record_call_1 (tree *, int *, void *);
  static void cgraph_mark_local_functions (void);
  static void cgraph_analyze_function (struct cgraph_node *node);
+ static void cgraph_create_edges (struct cgraph_node *node, tree body);
  
  /* Records tree nodes seen in cgraph_create_edges.  Simply using
     walk_tree_without_duplicates doesn't guarantee each node is visited
*************** cgraph_finalize_function (tree decl, boo
*** 460,465 ****
--- 435,443 ----
      do_warn_unused_parameter (decl);
  }
  
+ /* Used only while constructing the callgraph.  */
+ static basic_block current_basic_block;
+ 
  void
  cgraph_lower_function (struct cgraph_node *node)
  {
*************** cgraph_lower_function (struct cgraph_nod
*** 469,475 ****
    node->lowered = true;
  }
  
- 
  /* Walk tree and record all calls.  Called via walk_tree.  */
  static tree
  record_call_1 (tree *tp, int *walk_subtrees, void *data)
--- 447,452 ----
*************** record_call_1 (tree *tp, int *walk_subtr
*** 508,514 ****
  	tree decl = get_callee_fndecl (*tp);
  	if (decl && TREE_CODE (decl) == FUNCTION_DECL)
  	  {
! 	    cgraph_create_edge (data, cgraph_node (decl), *tp);
  
  	    /* When we see a function call, we don't want to look at the
  	       function reference in the ADDR_EXPR that is hanging from
--- 485,493 ----
  	tree decl = get_callee_fndecl (*tp);
  	if (decl && TREE_CODE (decl) == FUNCTION_DECL)
  	  {
! 	    cgraph_create_edge (data, cgraph_node (decl), *tp,
! 			        current_basic_block->count,
! 				current_basic_block->loop_depth);
  
  	    /* When we see a function call, we don't want to look at the
  	       function reference in the ADDR_EXPR that is hanging from
*************** record_call_1 (tree *tp, int *walk_subtr
*** 543,566 ****
  
  /* Create cgraph edges for function calls inside BODY from NODE.  */
  
! void
  cgraph_create_edges (struct cgraph_node *node, tree body)
  {
    /* The nodes we're interested in are never shared, so walk
       the tree ignoring duplicates.  */
    visited_nodes = pointer_set_create ();
    if (TREE_CODE (body) == FUNCTION_DECL)
      {
        struct function *this_cfun = DECL_STRUCT_FUNCTION (body);
-       basic_block this_block;
        block_stmt_iterator bsi;
        tree step;
  
        /* Reach the trees by walking over the CFG, and note the 
  	 enclosing basic-blocks in the call edges.  */
!       FOR_EACH_BB_FN (this_block, this_cfun)
!         for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
  	  walk_tree (bsi_stmt_ptr (bsi), record_call_1, node, visited_nodes);
  
        /* Walk over any private statics that may take addresses of functions.  */
        if (TREE_CODE (DECL_INITIAL (body)) == BLOCK)
--- 522,546 ----
  
  /* Create cgraph edges for function calls inside BODY from NODE.  */
  
! static void
  cgraph_create_edges (struct cgraph_node *node, tree body)
  {
    /* The nodes we're interested in are never shared, so walk
       the tree ignoring duplicates.  */
    visited_nodes = pointer_set_create ();
+   gcc_assert (current_basic_block == NULL);
    if (TREE_CODE (body) == FUNCTION_DECL)
      {
        struct function *this_cfun = DECL_STRUCT_FUNCTION (body);
        block_stmt_iterator bsi;
        tree step;
  
        /* Reach the trees by walking over the CFG, and note the 
  	 enclosing basic-blocks in the call edges.  */
!       FOR_EACH_BB_FN (current_basic_block, this_cfun)
!         for (bsi = bsi_start (current_basic_block); !bsi_end_p (bsi); bsi_next (&bsi))
  	  walk_tree (bsi_stmt_ptr (bsi), record_call_1, node, visited_nodes);
+       current_basic_block = NULL;
  
        /* Walk over any private statics that may take addresses of functions.  */
        if (TREE_CODE (DECL_INITIAL (body)) == BLOCK)
*************** cgraph_create_edges (struct cgraph_node 
*** 586,592 ****
    else
      walk_tree (&body, record_call_1, node, visited_nodes);
      
-   walk_tree (&body, record_call_1, node, visited_nodes);
    pointer_set_destroy (visited_nodes);
    visited_nodes = NULL;
  }
--- 566,571 ----
Index: ipa-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ipa-inline.c,v
retrieving revision 2.3
diff -c -3 -p -r2.3 ipa-inline.c
*** ipa-inline.c	23 Apr 2005 23:01:11 -0000	2.3
--- ipa-inline.c	18 May 2005 21:44:35 -0000
*************** cgraph_clone_inlined_nodes (struct cgrap
*** 123,129 ****
      }
     else if (duplicate)
      {
!       n = cgraph_clone_node (e->callee);
        cgraph_redirect_edge_callee (e, n);
      }
  
--- 123,129 ----
      }
     else if (duplicate)
      {
!       n = cgraph_clone_node (e->callee, e->count, e->loop_nest);
        cgraph_redirect_edge_callee (e, n);
      }
  
*************** cgraph_decide_recursive_inlining (struct
*** 369,375 ****
  	     cgraph_node_name (node));
  
    /* We need original clone to copy around.  */
!   master_clone = cgraph_clone_node (node);
    master_clone->needed = true;
    for (e = master_clone->callees; e; e = e->next_callee)
      if (!e->inline_failed)
--- 369,375 ----
  	     cgraph_node_name (node));
  
    /* We need original clone to copy around.  */
!   master_clone = cgraph_clone_node (node, 0, 1);
    master_clone->needed = true;
    for (e = master_clone->callees; e; e = e->next_callee)
      if (!e->inline_failed)
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.549
diff -c -3 -p -r1.549 rtl.h
*** rtl.h	27 Apr 2005 17:38:17 -0000	1.549
--- rtl.h	18 May 2005 21:44:35 -0000
*************** enum reg_note
*** 706,714 ****
    REG_NOTE_MAX
  };
  
- /* The base value for branch probability notes.  */
- #define REG_BR_PROB_BASE  10000
- 
  /* Define macros to extract and insert the reg-note kind in an EXPR_LIST.  */
  #define REG_NOTE_KIND(LINK) ((enum reg_note) GET_MODE (LINK))
  #define PUT_REG_NOTE_KIND(LINK, KIND) \
--- 706,711 ----
Index: tree-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.c,v
retrieving revision 1.185
diff -c -3 -p -r1.185 tree-inline.c
*** tree-inline.c	17 May 2005 16:56:27 -0000	1.185
--- tree-inline.c	18 May 2005 21:44:36 -0000
*************** copy_body_r (tree *tp, int *walk_subtree
*** 656,662 ****
  		 associate callgraph nodes.  */
  	      edge = cgraph_edge (id->current_node, old_node);
  	      if (edge)
! 		 cgraph_clone_edge (edge, id->node, *tp);
  	    }
  	}
        else if (TREE_CODE (*tp) == RESX_EXPR && id->eh_region_offset)
--- 656,663 ----
  		 associate callgraph nodes.  */
  	      edge = cgraph_edge (id->current_node, old_node);
  	      if (edge)
! 		 cgraph_clone_edge (edge, id->node, *tp,
! 				    REG_BR_PROB_BASE, 1);
  	    }
  	}
        else if (TREE_CODE (*tp) == RESX_EXPR && id->eh_region_offset)
*************** expand_call_inline (basic_block bb, tree
*** 1922,1928 ****
           constant propagating arguments.  In all other cases we hit a bug
           (incorrect node sharing is most common reason for missing edges.  */
        gcc_assert (dest->needed || !flag_unit_at_a_time);
!       cgraph_create_edge (id->node, dest, t)->inline_failed
  	= N_("originally indirect function call not considered for inlining");
        goto egress;
      }
--- 1923,1930 ----
           constant propagating arguments.  In all other cases we hit a bug
           (incorrect node sharing is most common reason for missing edges.  */
        gcc_assert (dest->needed || !flag_unit_at_a_time);
!       cgraph_create_edge (id->node, dest, t,
! 			  bb->count, bb->loop_depth)->inline_failed
  	= N_("originally indirect function call not considered for inlining");
        goto egress;
      }
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.98
diff -c -3 -p -r2.98 tree-optimize.c
*** tree-optimize.c	17 May 2005 20:28:22 -0000	2.98
--- tree-optimize.c	18 May 2005 21:44:36 -0000
*************** tree_rest_of_compilation (tree fndecl)
*** 741,747 ****
  	{
  	  struct cgraph_edge *e;
  
! 	  saved_node = cgraph_clone_node (node);
  	  for (e = saved_node->callees; e; e = e->next_callee)
  	    if (!e->inline_failed)
  	      cgraph_clone_inlined_nodes (e, true);
--- 741,747 ----
  	{
  	  struct cgraph_edge *e;
  
! 	  saved_node = cgraph_clone_node (node, node->count, 1);
  	  for (e = saved_node->callees; e; e = e->next_callee)
  	    if (!e->inline_failed)
  	      cgraph_clone_inlined_nodes (e, true);


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