[IPA] Inline before other IPA optimizations

[Jan Hubicka <jh at suse dot cz>]

Hi,
this patch makes the long promised (and now finally easy ;) change to
inline everything during the IPA inline pass instead of deferring it to
tree_rest_of_compilation.  The advantage of this scheme is mainly in the
fact that other IPA passes don't need to worry about the possibly
numberous inline clones around cgraph and we also order functions in a
way so saving is done seldomly instead of usually so we produce fewer
garbage.

The disadvantage is increase of peak memory usage just after inlining.
It is about 50% for Gerald's testcase (as the inline-unit-groth suggest
after all), but don't seems to be as bad as I anticipated.

Bootstrapped/regtested i686-pc-gnu-linux, comitted to IPA branch.

2005-08-14  Jan Hubicka  <jh@suse.cz>
	* cgraph.h (cgraph_preserve_function_body_p): New argument.
	* cgraphunit.c (cgraph_expand_function): Update call of
	cgraph_preserve_function_body_p.
	(cgraph_preserve_function_body_p): New argument.
	* ipa-inline.c (cgraph_apply_inline_plan): New function.
	(cgraph_decide_inlining): Use it; remove unreachable nodes.
	(cgraph_decide_inlining_incrementally): Update call of
	optimize_inline_calls.
	* tree-inline.c (inline_data): New field early_inlining_p.
	(expand_call_inline): Use it.
	(optimize_inline_calls): New argument.
	* tree-inline.h (optimize_inline_calls): Declare.
	* tree-optimize.c (update_inlined_to_pointers): Kill
	(tree_rest_of_compilation): Don't perform inlining.
Index: cgraph.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraph.h,v
retrieving revision 1.64.2.1
diff -c -3 -p -r1.64.2.1 cgraph.h
*** cgraph.h	13 Aug 2005 10:51:39 -0000	1.64.2.1
--- cgraph.h	14 Aug 2005 13:51:39 -0000
*************** void cgraph_optimize (void);
*** 279,285 ****
  void cgraph_mark_needed_node (struct cgraph_node *);
  void cgraph_mark_reachable_node (struct cgraph_node *);
  bool cgraph_inline_p (struct cgraph_edge *, const char **reason);
! bool cgraph_preserve_function_body_p (tree);
  void verify_cgraph (void);
  void verify_cgraph_node (struct cgraph_node *);
  void cgraph_mark_inline_edge (struct cgraph_edge *e);
--- 279,285 ----
  void cgraph_mark_needed_node (struct cgraph_node *);
  void cgraph_mark_reachable_node (struct cgraph_node *);
  bool cgraph_inline_p (struct cgraph_edge *, const char **reason);
! bool cgraph_preserve_function_body_p (tree, bool);
  void verify_cgraph (void);
  void verify_cgraph_node (struct cgraph_node *);
  void cgraph_mark_inline_edge (struct cgraph_edge *e);
Index: cgraphunit.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraphunit.c,v
retrieving revision 1.126.2.1
diff -c -3 -p -r1.126.2.1 cgraphunit.c
*** cgraphunit.c	13 Aug 2005 10:51:39 -0000	1.126.2.1
--- cgraphunit.c	14 Aug 2005 13:51:40 -0000
*************** cgraph_expand_function (struct cgraph_no
*** 1039,1045 ****
    gcc_assert (TREE_ASM_WRITTEN (node->decl));
  
    current_function_decl = NULL;
!   if (!cgraph_preserve_function_body_p (node->decl))
      {
        DECL_SAVED_TREE (node->decl) = NULL;
        DECL_STRUCT_FUNCTION (node->decl) = NULL;
--- 1039,1045 ----
    gcc_assert (TREE_ASM_WRITTEN (node->decl));
  
    current_function_decl = NULL;
!   if (!cgraph_preserve_function_body_p (node->decl, cgraph_global_info_ready))
      {
        DECL_SAVED_TREE (node->decl) = NULL;
        DECL_STRUCT_FUNCTION (node->decl) = NULL;
*************** cgraph_function_and_variable_visibility 
*** 1177,1188 ****
  }
  
  /* Return true when function body of DECL still needs to be kept around
!    for later re-use.  */
  bool
! cgraph_preserve_function_body_p (tree decl)
  {
    struct cgraph_node *node;
!   if (!cgraph_global_info_ready)
      return (DECL_INLINE (decl) && !flag_really_no_inline);
    /* Look if there is any clone around.  */
    for (node = cgraph_node (decl); node; node = node->next_clone)
--- 1177,1190 ----
  }
  
  /* Return true when function body of DECL still needs to be kept around
!    for later re-use.  When GLOBAL is false assume that inlining decisions
!    was not fixed yet and thus any inline candidate might get inlined later
!    on.  */
  bool
! cgraph_preserve_function_body_p (tree decl, bool global)
  {
    struct cgraph_node *node;
!   if (!global)
      return (DECL_INLINE (decl) && !flag_really_no_inline);
    /* Look if there is any clone around.  */
    for (node = cgraph_node (decl); node; node = node->next_clone)
Index: ipa-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ipa-inline.c,v
retrieving revision 2.15.2.1
diff -c -3 -p -r2.15.2.1 ipa-inline.c
*** ipa-inline.c	13 Aug 2005 10:51:40 -0000	2.15.2.1
--- ipa-inline.c	14 Aug 2005 13:51:40 -0000
*************** cgraph_find_cycles (struct cgraph_node *
*** 505,510 ****
--- 505,555 ----
    node->aux = 0;
  }
  
+ 
+ static void
+ cgraph_apply_inline_plan (void)
+ {
+   struct cgraph_node *node;
+   struct cgraph_node **order =
+     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
+   int order_pos = 0, new_order_pos = 0;
+   int i;
+ 
+   timevar_push (TV_INTEGRATION);
+   order_pos = cgraph_postorder (order);
+   gcc_assert (order_pos == cgraph_n_nodes);
+ 
+   /* Garbage collector may remove inline clones we eliminate during
+      optimization.  So we must be sure to not reference them.  */
+   for (i = 0; i < order_pos; i++)
+     if (!order[i]->global.inlined_to)
+       order[new_order_pos++] = order[i];
+ 
+   for (i = 0; i < new_order_pos; i++)
+     {
+       struct cgraph_edge *e;
+ 
+       node = order[i];
+       for (e = node->callees; e; e = e->next_callee)
+ 	if (!e->inline_failed || warn_inline)
+ 	  break;
+       if (e)
+ 	{
+ 	  if (cgraph_preserve_function_body_p (node->decl, true))
+ 	    save_inline_function_body (node);
+ 	  push_cfun (DECL_STRUCT_FUNCTION (node->decl));
+ 	  tree_register_cfg_hooks ();
+           current_function_decl = node->decl;
+ 	  optimize_inline_calls (node->decl, false);
+ 	  node->local.self_insns = node->global.insns;
+ 	  pop_cfun ();
+ 	  ggc_collect ();
+ 	}
+     }
+   free (order);
+   timevar_pop (TV_INTEGRATION);
+ }
+ 
  /* Leafify the cgraph node.  We have to be careful in recursing
     as to not run endlessly in circles of the callgraph.
     We do so by using a hashtab of cycle entering nodes as generated
*************** cgraph_decide_inlining (void)
*** 1011,1016 ****
--- 1056,1065 ----
  	}
      }
  
+   cgraph_remove_unreachable_nodes (false, dump_file);
+   cgraph_apply_inline_plan ();
+   cgraph_remove_unreachable_nodes (false, dump_file);
+ 
    if (dump_file)
      fprintf (dump_file,
  	     "\nInlined %i calls, eliminated %i functions, "
*************** cgraph_decide_inlining_incrementally (st
*** 1071,1082 ****
  	  else if (!early)
  	    e->inline_failed = failed_reason;
  	}
!   if (early && inlined)
      {
        push_cfun (DECL_STRUCT_FUNCTION (node->decl));
        tree_register_cfg_hooks ();
        current_function_decl = node->decl;
!       optimize_inline_calls (current_function_decl);
        node->local.self_insns = node->global.insns;
        current_function_decl = NULL;
        pop_cfun ();
--- 1120,1131 ----
  	  else if (!early)
  	    e->inline_failed = failed_reason;
  	}
!   if (inlined || (warn_inline && !early))
      {
        push_cfun (DECL_STRUCT_FUNCTION (node->decl));
        tree_register_cfg_hooks ();
        current_function_decl = node->decl;
!       optimize_inline_calls (current_function_decl, early);
        node->local.self_insns = node->global.insns;
        current_function_decl = NULL;
        pop_cfun ();
Index: tree-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.c,v
retrieving revision 1.210.2.1
diff -c -3 -p -r1.210.2.1 tree-inline.c
*** tree-inline.c	13 Aug 2005 10:51:40 -0000	1.210.2.1
--- tree-inline.c	14 Aug 2005 13:51:40 -0000
*************** typedef struct inline_data
*** 138,143 ****
--- 138,146 ----
    /* Take region number in the function being copied, add this value and
       get eh region number of the duplicate in the function we inline into.  */
    int eh_region_offset;
+ 
+   /* In early inlining the warnings are supressed.  */
+   bool early_inlining_p;
  } inline_data;
  
  /* Prototypes.  */
*************** expand_call_inline (basic_block bb, tree
*** 1956,1962 ****
      {
        if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn))
  	  /* Avoid warnings during early inline pass. */
! 	  && (!flag_unit_at_a_time || cgraph_global_info_ready))
  	{
  	  sorry ("inlining failed in call to %q+F: %s", fn, reason);
  	  sorry ("called from here");
--- 1959,1965 ----
      {
        if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn))
  	  /* Avoid warnings during early inline pass. */
! 	  && !id->early_inlining_p)
  	{
  	  sorry ("inlining failed in call to %q+F: %s", fn, reason);
  	  sorry ("called from here");
*************** expand_call_inline (basic_block bb, tree
*** 1966,1972 ****
  	       && strlen (reason)
  	       && !lookup_attribute ("noinline", DECL_ATTRIBUTES (fn))
  	       /* Avoid warnings during early inline pass. */
! 	       && (!flag_unit_at_a_time || cgraph_global_info_ready))
  	{
  	  warning (OPT_Winline, "inlining failed in call to %q+F: %s",
  		   fn, reason);
--- 1969,1975 ----
  	       && strlen (reason)
  	       && !lookup_attribute ("noinline", DECL_ATTRIBUTES (fn))
  	       /* Avoid warnings during early inline pass. */
! 	       && !id->early_inlining_p)
  	{
  	  warning (OPT_Winline, "inlining failed in call to %q+F: %s",
  		   fn, reason);
*************** gimple_expand_calls_inline (basic_block 
*** 2176,2182 ****
  /* Expand calls to inline functions in the body of FN.  */
  
  void
! optimize_inline_calls (tree fn)
  {
    inline_data id;
    tree prev_fn;
--- 2179,2185 ----
  /* Expand calls to inline functions in the body of FN.  */
  
  void
! optimize_inline_calls (tree fn, bool early)
  {
    inline_data id;
    tree prev_fn;
*************** optimize_inline_calls (tree fn)
*** 2192,2197 ****
--- 2195,2201 ----
  
    id.current_node = id.node = cgraph_node (fn);
    id.caller = fn;
+   id.early_inlining_p = early;
    /* Or any functions that aren't finished yet.  */
    prev_fn = NULL_TREE;
    if (current_function_decl)
Index: tree-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.h,v
retrieving revision 1.19.2.1
diff -c -3 -p -r1.19.2.1 tree-inline.h
*** tree-inline.h	13 Aug 2005 10:51:40 -0000	1.19.2.1
--- tree-inline.h	14 Aug 2005 13:51:40 -0000
*************** Boston, MA 02110-1301, USA.  */
*** 25,31 ****
  #include "varray.h"
  /* Function prototypes.  */
  
! void optimize_inline_calls (tree);
  bool tree_inlinable_function_p (tree);
  tree copy_tree_r (tree *, int *, void *);
  void clone_body (tree, tree, void *);
--- 25,31 ----
  #include "varray.h"
  /* Function prototypes.  */
  
! void optimize_inline_calls (tree, bool);
  bool tree_inlinable_function_p (tree);
  tree copy_tree_r (tree *, int *, void *);
  void clone_body (tree, tree, void *);
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.121.2.1
diff -c -3 -p -r2.121.2.1 tree-optimize.c
*** tree-optimize.c	13 Aug 2005 10:51:40 -0000	2.121.2.1
--- tree-optimize.c	14 Aug 2005 13:51:40 -0000
*************** tree_lowering_passes (tree fn)
*** 316,339 ****
    bitmap_obstack_release (NULL);
    pop_cfun ();
  }
- 
- /* Update recursively all inlined_to pointers of functions
-    inlined into NODE to INLINED_TO.  */
- static void
- update_inlined_to_pointers (struct cgraph_node *node,
- 			    struct cgraph_node *inlined_to)
- {
-   struct cgraph_edge *e;
-   for (e = node->callees; e; e = e->next_callee)
-     {
-       if (e->callee->global.inlined_to)
- 	{
- 	  e->callee->global.inlined_to = inlined_to;
- 	  update_inlined_to_pointers (e->callee, inlined_to);
- 	}
-     }
- }
- 
  
  /* For functions-as-trees languages, this performs all optimization and
     compilation for FNDECL.  */
--- 316,321 ----
*************** tree_rest_of_compilation (tree fndecl)
*** 350,361 ****
  
    node = cgraph_node (fndecl);
  
-   /* We might need the body of this function so that we can expand
-      it inline somewhere else.  This means not lowering some constructs
-      such as exception handling.  */
-   if (cgraph_preserve_function_body_p (fndecl))
-     save_inline_function_body (node);
- 
    /* Initialize the RTL code for the function.  */
    current_function_decl = fndecl;
    saved_loc = input_location;
--- 332,337 ----
*************** tree_rest_of_compilation (tree fndecl)
*** 369,387 ****
    cfun->x_dont_save_pending_sizes_p = 1;
    cfun->after_inlining = true;
  
-   if (flag_inline_trees)
-     {
-       struct cgraph_edge *e;
-       for (e = node->callees; e; e = e->next_callee)
- 	if (!e->inline_failed || warn_inline)
- 	  break;
-       if (e)
- 	{
- 	  timevar_push (TV_INTEGRATION);
- 	  optimize_inline_calls (fndecl);
- 	  timevar_pop (TV_INTEGRATION);
- 	}
-     }
    /* We are not going to maintain the cgraph edges up to date.
       Kill it so it won't confuse us.  */
    while (node->callees)
--- 345,350 ----
*************** tree_rest_of_compilation (tree fndecl)
*** 438,457 ****
  	}
      }
  
!   if (!flag_inline_trees)
      {
!       DECL_SAVED_TREE (fndecl) = NULL;
!       if (DECL_STRUCT_FUNCTION (fndecl) == 0
! 	  && !cgraph_node (fndecl)->origin)
! 	{
! 	  /* Stop pointing to the local nodes about to be freed.
! 	     But DECL_INITIAL must remain nonzero so we know this
! 	     was an actual function definition.
! 	     For a nested function, this is done in c_pop_function_context.
! 	     If rest_of_compilation set this to 0, leave it 0.  */
! 	  if (DECL_INITIAL (fndecl) != 0)
! 	    DECL_INITIAL (fndecl) = error_mark_node;
! 	}
      }
  
    input_location = saved_loc;
--- 401,417 ----
  	}
      }
  
!   DECL_SAVED_TREE (fndecl) = NULL;
!   if (DECL_STRUCT_FUNCTION (fndecl) == 0
!       && !cgraph_node (fndecl)->origin)
      {
!       /* Stop pointing to the local nodes about to be freed.
! 	 But DECL_INITIAL must remain nonzero so we know this
! 	 was an actual function definition.
! 	 For a nested function, this is done in c_pop_function_context.
! 	 If rest_of_compilation set this to 0, leave it 0.  */
!       if (DECL_INITIAL (fndecl) != 0)
! 	DECL_INITIAL (fndecl) = error_mark_node;
      }
  
    input_location = saved_loc;