IPA profile propagation

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
this patch implements simple IPA pass to propagate profile interprocedurally,
so local functions that are called only via cold calls are marked cold.
I also added profile flag EXECUTED_ONCE that if set for functions that are
known to execute once (or constantly bounded number of times).
It is set automatically for main and static constructors and propagated
(i.e. functions called only from executed_once functions and not called
from loops).

These functions are optimized for size outside loops, I expect this to be able
to track quite a lot of startup/exit code with whole-program.

Also I noticed that we don't handle comdat very well so I fixed -fwhole-program
to bring comdat functions locals unless their address is taken (so we would end up with
multiple functions if library had same comdat).

Patch saves about 10% of size of tramp3d when compiled with -fwhole-program.  I
am going to commit this to pretty-ipa for some extra testing and if it works
well, I will addd worklist for the propagation and prepare mainline version.

Honza

	* tree-pass.h (pass_ipa_profile): New.
	* predict.c (maybe_hot_frequency_p): Support executed once.
	(cgraph_maybe_hot_edge_p): Likewise; handle function profile.
	(compute_function_frequency): Likewise.
	* function.h (enum function_frequency): Add
	FUNCTION_FREQUENCY_EXECUTED_ONCE.
	* ipa.c (function_and_variable_visibility): Be more aggressive wrt
	comdat and -fwhole-program.
	* ipa-profile.c: New file.
	* Makefile.in: Add ipa-profile.o.
	* passes.c (init_optimization_passes): Add ipa_profile pass.
	(pass_init_dump_file): Handle FUNCTION_FREQUENCY_EXECUTED_ONCE.
	(execute_ipa_summary_passes): When generate_summary is NULL, don't call
	it.
Index: tree-pass.h
===================================================================
*** tree-pass.h	(revision 147439)
--- tree-pass.h	(working copy)
*************** extern struct gimple_opt_pass pass_trace
*** 404,409 ****
--- 404,410 ----
  extern struct ipa_opt_pass pass_ipa_inline;
  extern struct ipa_opt_pass pass_ipa_cp;
  extern struct ipa_opt_pass pass_ipa_reference;
+ extern struct ipa_opt_pass pass_ipa_profile;
  extern struct ipa_opt_pass pass_ipa_pure_const;
  
  extern struct simple_ipa_opt_pass pass_ipa_matrix_reorg;
Index: predict.c
===================================================================
*** predict.c	(revision 147439)
--- predict.c	(working copy)
*************** maybe_hot_frequency_p (int freq)
*** 123,128 ****
--- 123,131 ----
      }
    if (profile_status == PROFILE_ABSENT)
      return true;
+   if (cfun->function_frequency == FUNCTION_FREQUENCY_EXECUTED_ONCE
+       && freq <= (ENTRY_BLOCK_PTR->frequency * 2 / 3))
+     return false;
    if (freq < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
      return false;
    return true;
*************** cgraph_maybe_hot_edge_p (struct cgraph_e
*** 167,174 ****
      return false;
    if (lookup_attribute ("hot", DECL_ATTRIBUTES (edge->caller->decl)))
      return true;
    if (flag_guess_branch_prob
!       && edge->frequency < (CGRAPH_FREQ_MAX
        			    / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
      return false;
    return true;
--- 170,188 ----
      return false;
    if (lookup_attribute ("hot", DECL_ATTRIBUTES (edge->caller->decl)))
      return true;
+   if (DECL_STRUCT_FUNCTION (edge->caller->decl))
+     {
+       struct function *fun = DECL_STRUCT_FUNCTION (edge->caller->decl);
+       if (fun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
+         return false;
+       if (fun->function_frequency == FUNCTION_FREQUENCY_HOT)
+         return true;
+       if (fun->function_frequency == FUNCTION_FREQUENCY_EXECUTED_ONCE
+           && edge->frequency < CGRAPH_FREQ_BASE * 3 / 2)
+ 	return false;
+     }
    if (flag_guess_branch_prob
!       && edge->frequency < (CGRAPH_FREQ_BASE
        			    / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
      return false;
    return true;
*************** compute_function_frequency (void)
*** 2124,2129 ****
--- 2138,2146 ----
  {
    basic_block bb;
  
+   if (cfun->function_frequency == FUNCTION_FREQUENCY_EXECUTED_ONCE)
+     return;
+ 
    if (!profile_info || !flag_branch_probabilities)
      {
        if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
*************** compute_function_frequency (void)
*** 2132,2137 ****
--- 2149,2159 ----
        else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
  	       != NULL)
          cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
+       else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
+         cfun->function_frequency = FUNCTION_FREQUENCY_EXECUTED_ONCE;
+       else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
+ 	       || DECL_STATIC_DESTRUCTOR (current_function_decl))
+         cfun->function_frequency = FUNCTION_FREQUENCY_EXECUTED_ONCE;
        return;
      }
    cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
Index: function.h
===================================================================
*** function.h	(revision 147439)
--- function.h	(working copy)
*************** enum function_frequency {
*** 183,188 ****
--- 183,191 ----
    /* This function most likely won't be executed at all.
       (set only when profile feedback is available or via function attribute). */
    FUNCTION_FREQUENCY_UNLIKELY_EXECUTED,
+   /* For functions that are known to be executed once (i.e. constructors, destructors
+      and main function.  */
+   FUNCTION_FREQUENCY_EXECUTED_ONCE,
    /* The default value.  */
    FUNCTION_FREQUENCY_NORMAL,
    /* Optimize this function hard
Index: ipa.c
===================================================================
*** ipa.c	(revision 147439)
--- ipa.c	(working copy)
*************** function_and_variable_visibility (void)
*** 263,277 ****
    for (node = cgraph_nodes; node; node = node->next)
      {
        if (node->reachable
! 	  && (DECL_COMDAT (node->decl)
  	      || (!flag_whole_program
! 		  && TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl))))
  	node->local.externally_visible = true;
        if (!node->local.externally_visible && node->analyzed
  	  && !DECL_EXTERNAL (node->decl))
  	{
  	  gcc_assert (flag_whole_program || !TREE_PUBLIC (node->decl));
  	  TREE_PUBLIC (node->decl) = 0;
  	}
        node->local.local = (!node->needed
  			   && node->analyzed
--- 263,284 ----
    for (node = cgraph_nodes; node; node = node->next)
      {
        if (node->reachable
! 	  /* COMDAT functions must be shared only if they have address taken,
! 	     otherwise we can produce our own private implementation with
! 	     -fwhole-program.  */
! 	  && ((DECL_COMDAT (node->decl) && (node->address_taken || !node->analyzed))
  	      || (!flag_whole_program
! 		  && TREE_PUBLIC (node->decl)
! 		  && (!DECL_EXTERNAL (node->decl)))))
  	node->local.externally_visible = true;
        if (!node->local.externally_visible && node->analyzed
  	  && !DECL_EXTERNAL (node->decl))
  	{
  	  gcc_assert (flag_whole_program || !TREE_PUBLIC (node->decl));
  	  TREE_PUBLIC (node->decl) = 0;
+ 	  DECL_COMDAT (node->decl) = 0;
+ 	  DECL_WEAK (node->decl) = 0;
+ 	  DECL_ONE_ONLY (node->decl) = 0;
  	}
        node->local.local = (!node->needed
  			   && node->analyzed
Index: ipa-profile.c
===================================================================
*** ipa-profile.c	(revision 0)
--- ipa-profile.c	(revision 0)
***************
*** 0 ****
--- 1,149 ----
+ /* Propagate local profiles into IPA profiles.
+    Copyright (C) 2009 Free Software Foundation, Inc.
+ 
+ This file is part of GCC.
+ 
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 3, or (at your option) any later
+ version.
+ 
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+ 
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING3.  If not see
+ <http://www.gnu.org/licenses/>.  */
+ 
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "timevar.h"
+ #include "tree-pass.h"
+ #include "cgraph.h"
+ #include "tree.h"
+ 
+ #define CGRAPH_NODE_FREQUENCY(node)  (DECL_STRUCT_FUNCTION((node)->decl)->function_frequency)
+ 
+ static bool
+ try_update (struct cgraph_node *node)
+ {
+   bool maybe_unlikely_executed = true, maybe_executed_once = true;
+   struct cgraph_edge *edge;
+   if (node->local.externally_visible
+       || DECL_STATIC_CONSTRUCTOR (node->decl)
+       || DECL_STATIC_DESTRUCTOR (node->decl))
+     return false;
+   if (node->address_taken)
+     return false;
+   if (!node->analyzed)
+     return false;
+   if (CGRAPH_NODE_FREQUENCY (node) == FUNCTION_FREQUENCY_HOT)
+     return false;
+   if (CGRAPH_NODE_FREQUENCY (node) == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
+     return false;
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     fprintf (dump_file, "Processing %s\n", cgraph_node_name (node));
+   for (edge = node->callers;
+        edge && (maybe_unlikely_executed || maybe_executed_once);
+        edge = edge->next_caller)
+     {
+       switch (CGRAPH_NODE_FREQUENCY (edge->caller))
+         {
+ 	case FUNCTION_FREQUENCY_UNLIKELY_EXECUTED:
+ 	  break;
+ 	case FUNCTION_FREQUENCY_EXECUTED_ONCE:
+ 	  if (edge->frequency == 0)
+ 	    break;
+ 	  if (dump_file && (dump_flags & TDF_DETAILS))
+ 	    fprintf (dump_file, "  Called by %s that is executed once\n", cgraph_node_name (node));
+ 	  maybe_unlikely_executed = false;
+ 	  if (edge->loop_nest)
+ 	    {
+ 	      maybe_executed_once = false;
+ 	      if (dump_file && (dump_flags & TDF_DETAILS))
+ 	        fprintf (dump_file, "  Called in loop\n");
+ 	    }
+ 	  break;
+ 	case FUNCTION_FREQUENCY_HOT:
+ 	case FUNCTION_FREQUENCY_NORMAL:
+ 	  if (!edge->frequency)
+ 	    continue;
+ 	  if (dump_file && (dump_flags & TDF_DETAILS))
+ 	    fprintf (dump_file, "  Called by %s that is normal or hot\n", cgraph_node_name (node));
+ 	  maybe_unlikely_executed = false;
+ 	  maybe_executed_once = false;
+ 	  break;
+ 	}
+     }
+    if (maybe_unlikely_executed)
+      {
+        CGRAPH_NODE_FREQUENCY (node) = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
+        if (dump_file)
+          fprintf (dump_file, "Node %s promoted to unlikely executed.\n", cgraph_node_name (node));
+        return true;
+      }
+    if (maybe_executed_once && CGRAPH_NODE_FREQUENCY (node) != FUNCTION_FREQUENCY_EXECUTED_ONCE)
+      {
+        CGRAPH_NODE_FREQUENCY (node) = FUNCTION_FREQUENCY_EXECUTED_ONCE;
+        if (dump_file)
+          fprintf (dump_file, "Node %s promoted to executed once.\n", cgraph_node_name (node));
+        return true;
+      }
+    return false;
+ }
+ 
+ static unsigned int
+ propagate (void)
+ {
+   struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
+   int order_pos;
+   bool something_changed = true;
+   int i;
+ 
+   order_pos = cgraph_postorder (order);
+ 
+   while (something_changed)
+     {
+       something_changed = false;
+       for (i = order_pos - 1; i >= 0; i--)
+         something_changed |= try_update (order[i]);
+     }
+   free (order);
+   return 0;
+ }
+ 
+ static bool
+ gate_profile (void)
+ {
+   return true;
+ }
+ 
+ struct ipa_opt_pass pass_ipa_profile =
+ {
+  {
+   IPA_PASS,
+   "ipa-profile",				/* name */
+   gate_profile,			/* gate */
+   propagate,			        /* execute */
+   NULL,					/* sub */
+   NULL,					/* next */
+   0,					/* static_pass_number */
+   TV_IPA_REFERENCE,		        /* tv_id */
+   0,	                                /* properties_required */
+   0,					/* properties_provided */
+   0,					/* properties_destroyed */
+   0,					/* todo_flags_start */
+   0                                     /* todo_flags_finish */
+  },
+  NULL,				        /* generate_summary */
+  NULL,					/* write_summary */
+  NULL,					/* read_summary */
+  NULL,					/* function_read_summary */
+  0,					/* TODOs */
+  NULL,			                /* function_transform */
+  NULL					/* variable_transform */
+ };
Index: Makefile.in
===================================================================
*** Makefile.in	(revision 147439)
--- Makefile.in	(working copy)
*************** OBJS-archive = \
*** 1314,1319 ****
--- 1314,1320 ----
  	ipa-prop.o \
  	ipa-pure-const.o \
  	ipa-reference.o \
+ 	ipa-profile.o \
  	ipa-struct-reorg.o \
  	ipa-type-escape.o \
  	ipa-utils.o \
*************** ipa-reference.o : ipa-reference.c $(CONF
*** 2653,2658 ****
--- 2654,2661 ----
     pointer-set.h $(GGC_H) $(IPA_REFERENCE_H) $(IPA_UTILS_H) $(C_COMMON_H) \
     $(GIMPLE_H) $(CGRAPH_H) output.h $(FLAGS_H) $(TREE_PASS_H) \
     $(TIMEVAR_H) $(DIAGNOSTIC_H) $(FUNCTION_H)
+ ipa-profile.o : ipa-profile.c $(CONFIG_H) $(SYSTEM_H) $(CGRAPH_H) coretypes.h \
+    $(TIMEVAR_H) $(TREE_PASS_H)
  
  ipa-pure-const.o : ipa-pure-const.c $(CONFIG_H) $(SYSTEM_H) \
     coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) $(TREE_INLINE_H) langhooks.h \
Index: passes.c
===================================================================
*** passes.c	(revision 147439)
--- passes.c	(working copy)
*************** init_optimization_passes (void)
*** 569,574 ****
--- 569,575 ----
        NEXT_PASS (pass_rebuild_cgraph_edges);
        NEXT_PASS (pass_inline_parameters);
      }
+   NEXT_PASS (pass_ipa_profile);
    NEXT_PASS (pass_ipa_increase_alignment);
    NEXT_PASS (pass_ipa_matrix_reorg);
    NEXT_PASS (pass_ipa_cp);
*************** pass_init_dump_file (struct opt_pass *pa
*** 1107,1112 ****
--- 1108,1115 ----
  	  fprintf (dump_file, "\n;; Function %s (%s)%s\n\n", dname, aname,
  	     cfun->function_frequency == FUNCTION_FREQUENCY_HOT
  	     ? " (hot)"
+ 	     : cfun->function_frequency == FUNCTION_FREQUENCY_EXECUTED_ONCE
+ 	     ? " (executed once)"
  	     : cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
  	     ? " (unlikely executed)"
  	     : "");
*************** execute_ipa_summary_passes (struct ipa_o
*** 1167,1173 ****
  
        /* Execute all of the IPA_PASSes in the list.  */
        if (ipa_pass->pass.type == IPA_PASS 
! 	  && (!pass->gate || pass->gate ()))
  	{
  	  pass_init_dump_file (pass);
  	  ipa_pass->generate_summary ();
--- 1170,1177 ----
  
        /* Execute all of the IPA_PASSes in the list.  */
        if (ipa_pass->pass.type == IPA_PASS 
! 	  && (!pass->gate || pass->gate ())
! 	  && ipa_pass->generate_summary)
  	{
  	  pass_init_dump_file (pass);
  	  ipa_pass->generate_summary ();