Re: [PATCH][4.1] Fix PR27882, GC bug during inlining

[Jan Hubicka <hubicka at ucw dot cz>]

> 
> This is one possible fix for the GC collecting a node which we
> will continue to visit.  I verified we do not regress in terms
> of memory usage for tramp3d, DLV or mico.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> 
> Ok for the 4.1 branch?  (The problem looks latent on the mainline)
> 
> Thanks,
> Richard.
> 
> 2006-07-20  Richard Guenther  <rguenther@suse.de>
> 
> 	PR tree-optimization/27882
> 	* ipa-inline.c (cgraph_early_inlining): Collect at
> 	callgraph root and tail nodes only.

We discussed this patch on IRC and it looks like it is not engouht (ie
in postorder and presence of cycles, there is nothing preventing leaf
nodes appearing in the middle of cycle).  Best sollution I can come with
is the attached rather ugly patch making order garbage collected.  To
make garbage collection grok the reachable removed node,
cgraph_remove_node needs to be updated to clear next/prev pointers that
in turn needs some updating in loops removing cgraph nodes and walking
the list at same time.

Concerning the garbage collecting, it should not be weakened by any
considerable amount by exposing the order - most of memory we collect is
garbage produced by inliner or function bodies of fully inlined
functions.  This should still happen since cgraph_remove_node kills the
decl pointer.

I am going to bootstrap/regtest this with gcac so there is some time for
better ideas.

Honza

2006-07-20  Jan Hubicka  <jh@suse.cz>
	* cgraph.c (cgraph_remove_node): Clear needed, reachable, next, previous
	and decl fields.
	* cgraphunit.c (cgraph_reset_node): Expect cgraph_remove_node to kill
	next pointer
	(cgraph_analyze_compilation_unit): Likewise.
	* ipa.c (cgraph_remove_unreachable_nodes): Likewise.
	* ipa-inline.c (cgraph_decide_recursive_inlining): Likewise.
	(cgraph_early_inlinine): Make order garbage collected.
	* Makefile.in (gt-ipa-inline): New garbagecollected file.
Index: cgraph.c
===================================================================
*** cgraph.c	(revision 115597)
--- cgraph.c	(working copy)
*************** cgraph_remove_node (struct cgraph_node *
*** 422,427 ****
--- 422,430 ----
  
    cgraph_node_remove_callers (node);
    cgraph_node_remove_callees (node);
+   /* Incremental inlining access removed nodes stored in the postorder list.
+      */
+   node->needed = node->reachable = false;
    while (node->nested)
      cgraph_remove_node (node->nested);
    if (node->origin)
*************** cgraph_remove_node (struct cgraph_node *
*** 438,443 ****
--- 441,448 ----
      cgraph_nodes = node->next;
    if (node->next)
      node->next->previous = node->previous;
+   node->next = NULL;
+   node->previous = NULL;
    slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
    if (*slot == node)
      {
*************** cgraph_remove_node (struct cgraph_node *
*** 485,490 ****
--- 490,496 ----
        DECL_STRUCT_FUNCTION (node->decl) = NULL;
        DECL_INITIAL (node->decl) = error_mark_node;
      }
+   node->decl = NULL;
    cgraph_n_nodes--;
    /* Do not free the structure itself so the walk over chain can continue.  */
  }
Index: cgraphunit.c
===================================================================
*** cgraphunit.c	(revision 115597)
--- cgraphunit.c	(working copy)
*************** cgraph_reset_node (struct cgraph_node *n
*** 387,397 ****
  
    if (!flag_unit_at_a_time)
      {
!       struct cgraph_node *n;
  
!       for (n = cgraph_nodes; n; n = n->next)
! 	if (n->global.inlined_to == node)
! 	  cgraph_remove_node (n);
      }
  
    cgraph_node_remove_callees (node);
--- 387,400 ----
  
    if (!flag_unit_at_a_time)
      {
!       struct cgraph_node *n, *next;
  
!       for (n = cgraph_nodes; n; n = next)
! 	{
! 	  next = n->next;
! 	  if (n->global.inlined_to == node)
! 	    cgraph_remove_node (n);
! 	}
      }
  
    cgraph_node_remove_callees (node);
*************** cgraph_analyze_function (struct cgraph_n
*** 882,888 ****
  void
  cgraph_finalize_compilation_unit (void)
  {
!   struct cgraph_node *node;
    /* Keep track of already processed nodes when called multiple times for
       intermodule optimization.  */
    static struct cgraph_node *first_analyzed;
--- 885,891 ----
  void
  cgraph_finalize_compilation_unit (void)
  {
!   struct cgraph_node *node, *next;
    /* Keep track of already processed nodes when called multiple times for
       intermodule optimization.  */
    static struct cgraph_node *first_analyzed;
*************** cgraph_finalize_compilation_unit (void)
*** 961,969 ****
    if (cgraph_dump_file)
      fprintf (cgraph_dump_file, "\nReclaiming functions:");
  
!   for (node = cgraph_nodes; node != first_analyzed; node = node->next)
      {
        tree decl = node->decl;
  
        if (node->local.finalized && !DECL_SAVED_TREE (decl))
          cgraph_reset_node (node);
--- 964,973 ----
    if (cgraph_dump_file)
      fprintf (cgraph_dump_file, "\nReclaiming functions:");
  
!   for (node = cgraph_nodes; node != first_analyzed; node = next)
      {
        tree decl = node->decl;
+       next = node->next;
  
        if (node->local.finalized && !DECL_SAVED_TREE (decl))
          cgraph_reset_node (node);
Index: ipa-inline.c
===================================================================
*** ipa-inline.c	(revision 115597)
--- ipa-inline.c	(working copy)
*************** cgraph_decide_recursive_inlining (struct
*** 543,549 ****
    int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
    fibheap_t heap;
    struct cgraph_edge *e;
!   struct cgraph_node *master_clone;
    int depth = 0;
    int n = 0;
  
--- 543,549 ----
    int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
    fibheap_t heap;
    struct cgraph_edge *e;
!   struct cgraph_node *master_clone, *next;
    int depth = 0;
    int n = 0;
  
*************** cgraph_decide_recursive_inlining (struct
*** 644,652 ****
       into master clone gets queued just before master clone so we don't
       need recursion.  */
    for (node = cgraph_nodes; node != master_clone;
!        node = node->next)
!     if (node->global.inlined_to == master_clone)
!       cgraph_remove_node (node);
    cgraph_remove_node (master_clone);
    /* FIXME: Recursive inlining actually reduces number of calls of the
       function.  At this place we should probably walk the function and
--- 644,655 ----
       into master clone gets queued just before master clone so we don't
       need recursion.  */
    for (node = cgraph_nodes; node != master_clone;
!        node = next)
!     {
!       next = node->next;
!       if (node->global.inlined_to == master_clone)
! 	cgraph_remove_node (node);
!     }
    cgraph_remove_node (master_clone);
    /* FIXME: Recursive inlining actually reduces number of calls of the
       function.  At this place we should probably walk the function and
*************** struct tree_opt_pass pass_ipa_inline = 
*** 1122,1127 ****
--- 1125,1136 ----
    0					/* letter */
  };
  
+ /* Because inlining might remove no-longer reachable nodes, we need to
+    keep the array visible to garbage collector to avoid reading collected
+    out nodes.  */
+ static int nnodes;
+ static GTY ((length ("nnodes"))) struct cgraph_node **order;
+ 
  /* Do inlining of small functions.  Doing so early helps profiling and other
     passes to be somewhat more effective and avoids some code duplication in
     later real inlining pass for testcases with very many function calls.  */
*************** static void
*** 1129,1137 ****
  cgraph_early_inlining (void)
  {
    struct cgraph_node *node;
-   int nnodes;
-   struct cgraph_node **order =
-     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
    int i;
  
    if (sorrycount || errorcount)
--- 1138,1143 ----
*************** cgraph_early_inlining (void)
*** 1141,1146 ****
--- 1147,1153 ----
      gcc_assert (!node->aux);
  #endif
  
+   order = ggc_alloc (sizeof (*order) * cgraph_n_nodes);
    nnodes = cgraph_postorder (order);
    for (i = nnodes - 1; i >= 0; i--)
      {
*************** cgraph_early_inlining (void)
*** 1158,1164 ****
    for (node = cgraph_nodes; node; node = node->next)
      gcc_assert (!node->global.inlined_to);
  #endif
!   free (order);
  }
  
  /* When inlining shall be performed.  */
--- 1165,1173 ----
    for (node = cgraph_nodes; node; node = node->next)
      gcc_assert (!node->global.inlined_to);
  #endif
!   ggc_free (order);
!   order = NULL;
!   nnodes = 0;
  }
  
  /* When inlining shall be performed.  */
*************** struct tree_opt_pass pass_early_ipa_inli
*** 1184,1186 ****
--- 1193,1197 ----
    TODO_dump_cgraph | TODO_dump_func,	/* todo_flags_finish */
    0					/* letter */
  };
+ 
+ #include "gt-ipa-inline.h"
Index: Makefile.in
===================================================================
*** Makefile.in	(revision 115597)
--- Makefile.in	(working copy)
*************** ipa-cp.o : ipa-cp.c $(CONFIG_H) $(SYSTEM
*** 2185,2191 ****
  ipa-inline.o : ipa-inline.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
     $(TREE_H) langhooks.h tree-inline.h $(FLAGS_H) $(CGRAPH_H) intl.h \
     $(DIAGNOSTIC_H) $(FIBHEAP_H) $(PARAMS_H) $(TIMEVAR_H) tree-pass.h \
!    $(COVERAGE_H) $(HASHTAB_H)
  ipa-utils.o : ipa-utils.c $(IPA_UTILS_H) $(CONFIG_H) $(SYSTEM_H) \
     coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) tree-inline.h langhooks.h \
     pointer-set.h $(GGC_H) $(C_COMMON_H) $(TREE_GIMPLE_H) \
--- 2185,2191 ----
  ipa-inline.o : ipa-inline.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
     $(TREE_H) langhooks.h tree-inline.h $(FLAGS_H) $(CGRAPH_H) intl.h \
     $(DIAGNOSTIC_H) $(FIBHEAP_H) $(PARAMS_H) $(TIMEVAR_H) tree-pass.h \
!    $(COVERAGE_H) $(HASHTAB_H) gt-ipa-inline.h
  ipa-utils.o : ipa-utils.c $(IPA_UTILS_H) $(CONFIG_H) $(SYSTEM_H) \
     coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) tree-inline.h langhooks.h \
     pointer-set.h $(GGC_H) $(C_COMMON_H) $(TREE_GIMPLE_H) \
*************** GTFILES = $(srcdir)/input.h $(srcdir)/co
*** 2742,2748 ****
    $(srcdir)/cselib.h $(srcdir)/basic-block.h  $(srcdir)/cgraph.h \
    $(srcdir)/c-common.h $(srcdir)/c-tree.h $(srcdir)/reload.h \
    $(srcdir)/alias.c $(srcdir)/bitmap.c $(srcdir)/cselib.c $(srcdir)/cgraph.c \
!   $(srcdir)/ipa-prop.c $(srcdir)/ipa-cp.c\
    $(srcdir)/dbxout.c $(srcdir)/dwarf2out.c $(srcdir)/dwarf2asm.c \
    $(srcdir)/dojump.c $(srcdir)/tree-profile.c \
    $(srcdir)/emit-rtl.c $(srcdir)/except.c $(srcdir)/explow.c $(srcdir)/expr.c \
--- 2742,2748 ----
    $(srcdir)/cselib.h $(srcdir)/basic-block.h  $(srcdir)/cgraph.h \
    $(srcdir)/c-common.h $(srcdir)/c-tree.h $(srcdir)/reload.h \
    $(srcdir)/alias.c $(srcdir)/bitmap.c $(srcdir)/cselib.c $(srcdir)/cgraph.c \
!   $(srcdir)/ipa-prop.c $(srcdir)/ipa-cp.c $(srcdir)/ipa-inline.c \
    $(srcdir)/dbxout.c $(srcdir)/dwarf2out.c $(srcdir)/dwarf2asm.c \
    $(srcdir)/dojump.c $(srcdir)/tree-profile.c \
    $(srcdir)/emit-rtl.c $(srcdir)/except.c $(srcdir)/explow.c $(srcdir)/expr.c \
*************** gt-tree-profile.h gt-tree-ssa-address.h 
*** 2784,2790 ****
  gt-tree-ssanames.h gt-tree-iterator.h gt-gimplify.h \
  gt-tree-phinodes.h gt-tree-nested.h \
  gt-tree-ssa-operands.h gt-tree-ssa-propagate.h \
! gt-tree-ssa-structalias.h \
  gt-stringpool.h gt-targhooks.h : s-gtype ; @true
  
  define echo_quoted_to_gtyp
--- 2784,2790 ----
  gt-tree-ssanames.h gt-tree-iterator.h gt-gimplify.h \
  gt-tree-phinodes.h gt-tree-nested.h \
  gt-tree-ssa-operands.h gt-tree-ssa-propagate.h \
! gt-tree-ssa-structalias.h gp-ipa-inline.h \
  gt-stringpool.h gt-targhooks.h : s-gtype ; @true
  
  define echo_quoted_to_gtyp
Index: ipa.c
===================================================================
*** ipa.c	(revision 115597)
--- ipa.c	(working copy)
*************** bool
*** 97,103 ****
  cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *dump_file)
  {
    struct cgraph_node *first = (void *) 1;
!   struct cgraph_node *node;
    bool changed = false;
    int insns = 0;
  
--- 97,103 ----
  cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *dump_file)
  {
    struct cgraph_node *first = (void *) 1;
!   struct cgraph_node *node, *next;
    bool changed = false;
    int insns = 0;
  
*************** cgraph_remove_unreachable_nodes (bool be
*** 151,158 ****
       unanalyzed nodes so they look like for true extern functions to the rest
       of code.  Body of such functions is released via remove_node once the
       inline clones are eliminated.  */
!   for (node = cgraph_nodes; node; node = node->next)
      {
        if (!node->aux)
  	{
  	  int local_insns;
--- 151,159 ----
       unanalyzed nodes so they look like for true extern functions to the rest
       of code.  Body of such functions is released via remove_node once the
       inline clones are eliminated.  */
!   for (node = cgraph_nodes; node; node = next)
      {
+       next = node->next;
        if (!node->aux)
  	{
  	  int local_insns;