[patch] Move loop structures to gc memory

[patch] Move loop structures to gc memory

[Zdenek Dvorak]

Hello,

all the loop structures are now malloc-ed.  Since trees may be
referenced from the loop structures, this prevents garbage collection
from being run while loop structures are present.  This is going to be
impossible once we preserve the loop information across larger portion
of middle-end.

This patch makes all loop structures gc-allocated.  In addition to
the changes in GTY markup and replacing XNEW with GGC_NEW, the following
change was necessary:  Head of the exits double linked list is currently
stored as a part of the struct loop structure; gc marking would not like
that, so the patch makes this head to be allocated separately, and we
only keep a pointer to it in struct loop.

Since all the loop structures used to be deallocated manually, I have
just rewritten all the frees to ggc_frees; I hope this won't cause any
problems (in general, we are pretty sure what the life ranges of loop
structures and associated objects are).

Bootstrapped & regtested on i686 and ppc64-linux.  I have also run
a c-only bootstrap on i686 with --enable-checking=gc,gcac
I will wait for some time for comments before commiting this patch.

Zdenek

	* tree-ssa-loop-niter.c (record_estimate): Use GGC_NEW to allocate
	struct nb_iter_bound.
	(free_numbers_of_iterations_estimates_loop): Use ggc_free.
	* gengtype.c (open_base_files): Add cfhloop.h to the list of includes.
	* cfgloopmanip.c (place_new_loop): Vector larray is gc-allocated.
	* tree-scalar-evolution.c: Include gt-tree-scalar-evolution.h.
	(struct scev_info_str, scalar_evolution_info): Add GTY markers.
	(new_scev_info_str): Use GGC_NEW to allocate struct scev_info_str.
	(del_scev_info): Use ggc_free.
	(scev_initialize): Allocate scalar_evolution_info in gc memory.
	* loop-init.c: Include ggc.h.
	(loop_optimizer_init): Use GGC_CNEW to allocate struct loops.
	(loop_optimizer_finalize): Use ggc_free.
	* tree-ssa-loop.c (pass_tree_unswitch, pass_vectorize,
	pass_linear_transfom, pass_empty_loop, pass_complete_unroll,
	pass_iv_optimize): Add TODO_ggc_collect.
	* function.h (struct function): Remove skip marker from x_current_loops.
	* cfgloop.c: Include ggc.h.
	(flow_loops_free, flow_loop_free): Free the loop descriptions in gc
	memory.
	(establish_preds): Vector superloops is gc allocated.
	(alloc_loop): Allocate loop using GGC_CNEW.  Allocate head of
	loop->exits list.
	(flow_loops_find): Vector larray is gc allocated.
	(loop_exit_free): Use ggc_free.
	(rescan_loop_exit): Use GGC_NEW to allocate struct loop_exit.  Reflect
	that head of exits list is now not a part of struct loop.
	(record_loop_exits): Allocate exits table in gc memory.
	(get_loop_exit_edges, verify_loop_structure, single_exit): Reflect that
	head of exits list is now not a part of struct loop.
	* cfgloop.h (struct lpt_decision, struct nb_iter_bound,
	struct loop_exit): Add GTY marker.
	(struct loop): Add GTY marker.  Make superloops vector gc allocated.
	Add skip marker to aux field.  Make head of exits list a separate
	object.
	(struct loops): Add GTY marker.  Make larray vector gc allocated.
	Add param marker to exits table.
	(get_loops): Type changed.
	* Makefile.in (tree-scalar-evolution.o): Add gt-tree-scalar-evolution.h
	dependency.
	(cfgloop.o, loop-init.o): Add ggc.h dependency.
	(GTFILES): Add cfgloop.h and tree-scalar-evolution.c.
	* basic-block.h (struct basic_block_def): Remove skip marker from
	loop_father field.

Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c	(revision 124655)
--- tree-ssa-loop-niter.c	(working copy)
*************** record_estimate (struct loop *loop, tree
*** 2364,2370 ****
       list.  */
    if (upper)
      {
!       struct nb_iter_bound *elt = XNEW (struct nb_iter_bound);
  
        elt->bound = i_bound;
        elt->stmt = at_stmt;
--- 2364,2370 ----
       list.  */
    if (upper)
      {
!       struct nb_iter_bound *elt = GGC_NEW (struct nb_iter_bound);
  
        elt->bound = i_bound;
        elt->stmt = at_stmt;
*************** free_numbers_of_iterations_estimates_loo
*** 3023,3029 ****
    for (bound = loop->bounds; bound; bound = next)
      {
        next = bound->next;
!       free (bound);
      }
  
    loop->bounds = NULL;
--- 3023,3029 ----
    for (bound = loop->bounds; bound; bound = next)
      {
        next = bound->next;
!       ggc_free (bound);
      }
  
    loop->bounds = NULL;
Index: gengtype.c
===================================================================
*** gengtype.c	(revision 124655)
--- gengtype.c	(working copy)
*************** open_base_files (void)
*** 1535,1541 ****
        "hard-reg-set.h", "basic-block.h", "cselib.h", "insn-addr.h",
        "optabs.h", "libfuncs.h", "debug.h", "ggc.h", "cgraph.h",
        "tree-flow.h", "reload.h", "cpp-id-data.h", "tree-chrec.h",
!       "cfglayout.h", "except.h", "output.h", NULL
      };
      const char *const *ifp;
      outf_p gtype_desc_c;
--- 1535,1541 ----
        "hard-reg-set.h", "basic-block.h", "cselib.h", "insn-addr.h",
        "optabs.h", "libfuncs.h", "debug.h", "ggc.h", "cgraph.h",
        "tree-flow.h", "reload.h", "cpp-id-data.h", "tree-chrec.h",
!       "cfglayout.h", "except.h", "output.h", "cfgloop.h", NULL
      };
      const char *const *ifp;
      outf_p gtype_desc_c;
Index: cfgloopmanip.c
===================================================================
*** cfgloopmanip.c	(revision 124655)
--- cfgloopmanip.c	(working copy)
*************** static void
*** 399,405 ****
  place_new_loop (struct loop *loop)
  {
    loop->num = number_of_loops ();
!   VEC_safe_push (loop_p, heap, current_loops->larray, loop);
  }
  
  /* Given LOOP structure with filled header and latch, find the body of the
--- 399,405 ----
  place_new_loop (struct loop *loop)
  {
    loop->num = number_of_loops ();
!   VEC_safe_push (loop_p, gc, current_loops->larray, loop);
  }
  
  /* Given LOOP structure with filled header and latch, find the body of the
Index: tree-scalar-evolution.c
===================================================================
*** tree-scalar-evolution.c	(revision 124655)
--- tree-scalar-evolution.c	(working copy)
*************** static tree analyze_scalar_evolution_1 (
*** 258,264 ****
  /* The cached information about a ssa name VAR, claiming that inside LOOP,
     the value of VAR can be expressed as CHREC.  */
  
! struct scev_info_str
  {
    tree var;
    tree chrec;
--- 258,264 ----
  /* The cached information about a ssa name VAR, claiming that inside LOOP,
     the value of VAR can be expressed as CHREC.  */
  
! struct scev_info_str GTY(())
  {
    tree var;
    tree chrec;
*************** tree chrec_known;
*** 285,291 ****
  
  static bitmap already_instantiated;
  
! static htab_t scalar_evolution_info;
  
  \f
  /* Constructs a new SCEV_INFO_STR structure.  */
--- 285,291 ----
  
  static bitmap already_instantiated;
  
! static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
  
  \f
  /* Constructs a new SCEV_INFO_STR structure.  */
*************** new_scev_info_str (tree var)
*** 295,301 ****
  {
    struct scev_info_str *res;
    
!   res = XNEW (struct scev_info_str);
    res->var = var;
    res->chrec = chrec_not_analyzed_yet;
    
--- 295,301 ----
  {
    struct scev_info_str *res;
    
!   res = GGC_NEW (struct scev_info_str);
    res->var = var;
    res->chrec = chrec_not_analyzed_yet;
    
*************** eq_scev_info (const void *e1, const void
*** 326,332 ****
  static void
  del_scev_info (void *e)
  {
!   free (e);
  }
  
  /* Get the index corresponding to VAR in the current LOOP.  If
--- 326,332 ----
  static void
  del_scev_info (void *e)
  {
!   ggc_free (e);
  }
  
  /* Get the index corresponding to VAR in the current LOOP.  If
*************** scev_initialize (void)
*** 2746,2753 ****
    loop_iterator li;
    struct loop *loop;
  
!   scalar_evolution_info = htab_create (100, hash_scev_info,
! 				       eq_scev_info, del_scev_info);
    already_instantiated = BITMAP_ALLOC (NULL);
    
    initialize_scalar_evolutions_analyzer ();
--- 2746,2757 ----
    loop_iterator li;
    struct loop *loop;
  
!   scalar_evolution_info = htab_create_alloc (100,
! 					     hash_scev_info,
! 					     eq_scev_info,
! 					     del_scev_info,
! 					     ggc_calloc,
! 					     ggc_free);
    already_instantiated = BITMAP_ALLOC (NULL);
    
    initialize_scalar_evolutions_analyzer ();
*************** scev_const_prop (void)
*** 3008,3010 ****
--- 3012,3016 ----
      }
    return 0;
  }
+ 
+ #include "gt-tree-scalar-evolution.h"
Index: loop-init.c
===================================================================
*** loop-init.c	(revision 124655)
--- loop-init.c	(working copy)
*************** Software Foundation, 51 Franklin Street,
*** 31,36 ****
--- 31,37 ----
  #include "tree-pass.h"
  #include "timevar.h"
  #include "flags.h"
+ #include "ggc.h"
  
  \f
  /* Initialize loop structures.  This is used by the tree and RTL loop
*************** loop_optimizer_init (unsigned flags)
*** 43,49 ****
    struct loops *loops;
  
    gcc_assert (!current_loops);
!   loops = XCNEW (struct loops);
  
    /* Find the loops.  */
  
--- 44,50 ----
    struct loops *loops;
  
    gcc_assert (!current_loops);
!   loops = GGC_CNEW (struct loops);
  
    /* Find the loops.  */
  
*************** loop_optimizer_finalize (void)
*** 116,122 ****
    if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
      release_recorded_exits ();
    flow_loops_free (current_loops);
!   free (current_loops);
    current_loops = NULL;
  
    FOR_ALL_BB (bb)
--- 117,123 ----
    if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
      release_recorded_exits ();
    flow_loops_free (current_loops);
!   ggc_free (current_loops);
    current_loops = NULL;
  
    FOR_ALL_BB (bb)
Index: tree-ssa-loop.c
===================================================================
*** tree-ssa-loop.c	(revision 124655)
--- tree-ssa-loop.c	(working copy)
*************** struct tree_opt_pass pass_tree_unswitch 
*** 171,177 ****
    0,					/* properties_provided */
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
!   TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
    0					/* letter */
  };
  
--- 171,178 ----
    0,					/* properties_provided */
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
!   TODO_ggc_collect | TODO_dump_func
!     | TODO_verify_loops,		/* todo_flags_finish */
    0					/* letter */
  };
  
*************** struct tree_opt_pass pass_vectorize =
*** 202,208 ****
    0,                                    /* properties_provided */
    0,                                    /* properties_destroyed */
    TODO_verify_loops,			/* todo_flags_start */
!   TODO_dump_func | TODO_update_ssa,	/* todo_flags_finish */
    0					/* letter */
  };
  
--- 203,210 ----
    0,                                    /* properties_provided */
    0,                                    /* properties_destroyed */
    TODO_verify_loops,			/* todo_flags_start */
!   TODO_dump_func | TODO_update_ssa
!     | TODO_ggc_collect,			/* todo_flags_finish */
    0					/* letter */
  };
  
*************** struct tree_opt_pass pass_linear_transfo
*** 237,243 ****
    0,					/* properties_provided */
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
!   TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
    0				        /* letter */	
  };
  
--- 239,246 ----
    0,					/* properties_provided */
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
!   TODO_dump_func | TODO_verify_loops
!     | TODO_ggc_collect,			/* todo_flags_finish */
    0				        /* letter */	
  };
  
*************** struct tree_opt_pass pass_empty_loop =
*** 361,367 ****
    0,					/* properties_provided */
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
!   TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
    0					/* letter */
  };
  
--- 364,371 ----
    0,					/* properties_provided */
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
!   TODO_dump_func | TODO_verify_loops 
!     | TODO_ggc_collect,			/* todo_flags_finish */
    0					/* letter */
  };
  
*************** struct tree_opt_pass pass_complete_unrol
*** 427,433 ****
    0,					/* properties_provided */
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
!   TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
    0					/* letter */
  };
  
--- 431,438 ----
    0,					/* properties_provided */
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
!   TODO_dump_func | TODO_verify_loops
!     | TODO_ggc_collect,			/* todo_flags_finish */
    0					/* letter */
  };
  
*************** struct tree_opt_pass pass_iv_optimize =
*** 496,504 ****
    0,					/* properties_provided */
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
!   TODO_dump_func
!   | TODO_verify_loops
!   | TODO_update_ssa,			/* todo_flags_finish */
    0					/* letter */
  };
  
--- 501,508 ----
    0,					/* properties_provided */
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
!   TODO_dump_func | TODO_verify_loops
!   | TODO_update_ssa | TODO_ggc_collect,	/* todo_flags_finish */
    0					/* letter */
  };
  
Index: function.h
===================================================================
*** function.h	(revision 124655)
--- function.h	(working copy)
*************** struct function GTY(())
*** 191,197 ****
    struct gimple_df *gimple_df;
  
    /* The loops in this function.  */
!   struct loops * GTY((skip)) x_current_loops;
  
    /* Value histograms attached to particular statements.  */
    htab_t GTY((skip)) value_histograms;
--- 191,197 ----
    struct gimple_df *gimple_df;
  
    /* The loops in this function.  */
!   struct loops *x_current_loops;
  
    /* Value histograms attached to particular statements.  */
    htab_t GTY((skip)) value_histograms;
Index: cfgloop.c
===================================================================
*** cfgloop.c	(revision 124655)
--- cfgloop.c	(working copy)
*************** Software Foundation, 51 Franklin Street,
*** 34,39 ****
--- 34,40 ----
  #include "tree-flow.h"
  #include "pointer-set.h"
  #include "output.h"
+ #include "ggc.h"
  
  static void flow_loops_cfg_dump (FILE *);
  \f
*************** flow_loops_dump (FILE *file, void (*loop
*** 174,198 ****
  }
  
  /* Free data allocated for LOOP.  */
  void
  flow_loop_free (struct loop *loop)
  {
    struct loop_exit *exit, *next;
  
!   VEC_free (loop_p, heap, loop->superloops);
  
    /* Break the list of the loop exit records.  They will be freed when the
       corresponding edge is rescanned or removed, and this avoids
       accessing the (already released) head of the list stored in the
       loop structure.  */
!   for (exit = loop->exits.next; exit != &loop->exits; exit = next)
      {
        next = exit->next;
        exit->next = exit;
        exit->prev = exit;
      }
!     
!   free (loop);
  }
  
  /* Free all the memory allocated for LOOPS.  */
--- 175,201 ----
  }
  
  /* Free data allocated for LOOP.  */
+ 
  void
  flow_loop_free (struct loop *loop)
  {
    struct loop_exit *exit, *next;
  
!   VEC_free (loop_p, gc, loop->superloops);
  
    /* Break the list of the loop exit records.  They will be freed when the
       corresponding edge is rescanned or removed, and this avoids
       accessing the (already released) head of the list stored in the
       loop structure.  */
!   for (exit = loop->exits->next; exit != loop->exits; exit = next)
      {
        next = exit->next;
        exit->next = exit;
        exit->prev = exit;
      }
! 
!   ggc_free (loop->exits);
!   ggc_free (loop);
  }
  
  /* Free all the memory allocated for LOOPS.  */
*************** flow_loops_free (struct loops *loops)
*** 214,221 ****
  	  flow_loop_free (loop);
  	}
  
!       VEC_free (loop_p, heap, loops->larray);
!       loops->larray = NULL;
      }
  }
  
--- 217,223 ----
  	  flow_loop_free (loop);
  	}
  
!       VEC_free (loop_p, gc, loops->larray);
      }
  }
  
*************** establish_preds (struct loop *loop, stru
*** 286,292 ****
    cfun->max_loop_depth = MAX (cfun->max_loop_depth, (int) depth);
  
    VEC_truncate (loop_p, loop->superloops, 0);
!   VEC_reserve (loop_p, heap, loop->superloops, depth);
    for (i = 0; VEC_iterate (loop_p, father->superloops, i, ploop); i++)
      VEC_quick_push (loop_p, loop->superloops, ploop);
    VEC_quick_push (loop_p, loop->superloops, father);
--- 288,294 ----
    cfun->max_loop_depth = MAX (cfun->max_loop_depth, (int) depth);
  
    VEC_truncate (loop_p, loop->superloops, 0);
!   VEC_reserve (loop_p, gc, loop->superloops, depth);
    for (i = 0; VEC_iterate (loop_p, father->superloops, i, ploop); i++)
      VEC_quick_push (loop_p, loop->superloops, ploop);
    VEC_quick_push (loop_p, loop->superloops, father);
*************** flow_loop_tree_node_remove (struct loop 
*** 335,343 ****
  struct loop *
  alloc_loop (void)
  {
!   struct loop *loop = XCNEW (struct loop);
  
-   loop->exits.next = loop->exits.prev = &loop->exits;
    return loop;
  }
  
--- 337,347 ----
  struct loop *
  alloc_loop (void)
  {
!   struct loop *loop = GGC_CNEW (struct loop);
! 
!   loop->exits = GGC_CNEW (struct loop_exit);
!   loop->exits->next = loop->exits->prev = loop->exits;
  
    return loop;
  }
  
*************** flow_loops_find (struct loops *loops)
*** 417,423 ****
      }
  
    /* Allocate loop structures.  */
!   loops->larray = VEC_alloc (loop_p, heap, num_loops + 1);
  
    /* Dummy loop containing whole function.  */
    root = alloc_loop ();
--- 421,427 ----
      }
  
    /* Allocate loop structures.  */
!   loops->larray = VEC_alloc (loop_p, gc, num_loops + 1);
  
    /* Dummy loop containing whole function.  */
    root = alloc_loop ();
*************** loop_exit_free (void *ex)
*** 961,967 ****
        exit->next->prev = exit->prev;
        exit->prev->next = exit->next;
  
!       free (exit);
      }
  }
  
--- 965,971 ----
        exit->next->prev = exit->prev;
        exit->prev->next = exit->next;
  
!       ggc_free (exit);
      }
  }
  
*************** rescan_loop_exit (edge e, bool new_edge,
*** 1000,1010 ****
  	   aloop != cloop;
  	   aloop = loop_outer (aloop))
  	{
! 	  exit = XNEW (struct loop_exit);
  	  exit->e = e;
  
! 	  exit->next = aloop->exits.next;
! 	  exit->prev = &aloop->exits;
  	  exit->next->prev = exit;
  	  exit->prev->next = exit;
  
--- 1004,1014 ----
  	   aloop != cloop;
  	   aloop = loop_outer (aloop))
  	{
! 	  exit = GGC_NEW (struct loop_exit);
  	  exit->e = e;
  
! 	  exit->next = aloop->exits->next;
! 	  exit->prev = aloop->exits;
  	  exit->next->prev = exit;
  	  exit->prev->next = exit;
  
*************** record_loop_exits (void)
*** 1050,1059 ****
    current_loops->state |= LOOPS_HAVE_RECORDED_EXITS;
  
    gcc_assert (current_loops->exits == NULL);
!   current_loops->exits = htab_create (2 * number_of_loops (),
! 				      loop_exit_hash,
! 				      loop_exit_eq,
! 				      loop_exit_free);
  
    FOR_EACH_BB (bb)
      {
--- 1054,1064 ----
    current_loops->state |= LOOPS_HAVE_RECORDED_EXITS;
  
    gcc_assert (current_loops->exits == NULL);
!   current_loops->exits = htab_create_alloc (2 * number_of_loops (),
! 					    loop_exit_hash,
! 					    loop_exit_eq,
! 					    loop_exit_free,
! 					    ggc_calloc, ggc_free);
  
    FOR_EACH_BB (bb)
      {
*************** get_loop_exit_edges (const struct loop *
*** 1123,1129 ****
       scan the body of the loop.  */
    if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
      {
!       for (exit = loop->exits.next; exit->e; exit = exit->next)
  	VEC_safe_push (edge, heap, edges, exit->e);
      }
    else
--- 1128,1134 ----
       scan the body of the loop.  */
    if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
      {
!       for (exit = loop->exits->next; exit->e; exit = exit->next)
  	VEC_safe_push (edge, heap, edges, exit->e);
      }
    else
*************** verify_loop_structure (void)
*** 1441,1447 ****
    /* Check the recorded loop exits.  */
    FOR_EACH_LOOP (li, loop, 0)
      {
!       if (loop->exits.e != NULL)
  	{
  	  error ("corrupted head of the exits list of loop %d",
  		 loop->num);
--- 1446,1452 ----
    /* Check the recorded loop exits.  */
    FOR_EACH_LOOP (li, loop, 0)
      {
!       if (!loop->exits || loop->exits->e != NULL)
  	{
  	  error ("corrupted head of the exits list of loop %d",
  		 loop->num);
*************** verify_loop_structure (void)
*** 1451,1457 ****
  	{
  	  /* Check that the list forms a cycle, and all elements except
  	     for the head are nonnull.  */
! 	  for (mexit = &loop->exits, exit = mexit->next, i = 0;
  	       exit->e && exit != mexit;
  	       exit = exit->next)
  	    {
--- 1456,1462 ----
  	{
  	  /* Check that the list forms a cycle, and all elements except
  	     for the head are nonnull.  */
! 	  for (mexit = loop->exits, exit = mexit->next, i = 0;
  	       exit->e && exit != mexit;
  	       exit = exit->next)
  	    {
*************** verify_loop_structure (void)
*** 1459,1465 ****
  		mexit = mexit->next;
  	    }
  
! 	  if (exit != &loop->exits)
  	    {
  	      error ("corrupted exits list of loop %d", loop->num);
  	      err = 1;
--- 1464,1470 ----
  		mexit = mexit->next;
  	    }
  
! 	  if (exit != loop->exits)
  	    {
  	      error ("corrupted exits list of loop %d", loop->num);
  	      err = 1;
*************** verify_loop_structure (void)
*** 1468,1474 ****
  
        if ((current_loops->state & LOOPS_HAVE_RECORDED_EXITS) == 0)
  	{
! 	  if (loop->exits.next != &loop->exits)
  	    {
  	      error ("nonempty exits list of loop %d, but exits are not recorded",
  		     loop->num);
--- 1473,1479 ----
  
        if ((current_loops->state & LOOPS_HAVE_RECORDED_EXITS) == 0)
  	{
! 	  if (loop->exits->next != loop->exits)
  	    {
  	      error ("nonempty exits list of loop %d, but exits are not recorded",
  		     loop->num);
*************** verify_loop_structure (void)
*** 1530,1536 ****
        FOR_EACH_LOOP (li, loop, 0)
  	{
  	  eloops = 0;
! 	  for (exit = loop->exits.next; exit->e; exit = exit->next)
  	    eloops++;
  	  if (eloops != sizes[loop->num])
  	    {
--- 1535,1541 ----
        FOR_EACH_LOOP (li, loop, 0)
  	{
  	  eloops = 0;
! 	  for (exit = loop->exits->next; exit->e; exit = exit->next)
  	    eloops++;
  	  if (eloops != sizes[loop->num])
  	    {
*************** loop_exit_edge_p (const struct loop *loo
*** 1585,1596 ****
  edge
  single_exit (const struct loop *loop)
  {
!   struct loop_exit *exit = loop->exits.next;
  
    if ((current_loops->state & LOOPS_HAVE_RECORDED_EXITS) == 0)
      return NULL;
  
!   if (exit->e && exit->next == &loop->exits)
      return exit->e;
    else
      return NULL;
--- 1590,1601 ----
  edge
  single_exit (const struct loop *loop)
  {
!   struct loop_exit *exit = loop->exits->next;
  
    if ((current_loops->state & LOOPS_HAVE_RECORDED_EXITS) == 0)
      return NULL;
  
!   if (exit->e && exit->next == loop->exits)
      return exit->e;
    else
      return NULL;
Index: cfgloop.h
===================================================================
*** cfgloop.h	(revision 124655)
--- cfgloop.h	(working copy)
*************** enum lpt_dec
*** 39,45 ****
    LPT_UNROLL_STUPID
  };
  
! struct lpt_decision
  {
    enum lpt_dec decision;
    unsigned times;
--- 39,45 ----
    LPT_UNROLL_STUPID
  };
  
! struct lpt_decision GTY (())
  {
    enum lpt_dec decision;
    unsigned times;
*************** struct lpt_decision
*** 47,53 ****
  
  /* The structure describing a bound on number of iterations of a loop.  */
  
! struct nb_iter_bound
  {
    /* The statement STMT is executed at most ...  */
    tree stmt;
--- 47,53 ----
  
  /* The structure describing a bound on number of iterations of a loop.  */
  
! struct nb_iter_bound GTY ((chain_next ("%h.next")))
  {
    /* The statement STMT is executed at most ...  */
    tree stmt;
*************** struct nb_iter_bound
*** 72,81 ****
  
  /* Description of the loop exit.  */
  
! struct loop_exit
  {
    /* The exit edge.  */
!   edge e;
  
    /* Previous and next exit in the list of the exits of the loop.  */
    struct loop_exit *prev;
--- 72,81 ----
  
  /* Description of the loop exit.  */
  
! struct loop_exit GTY (())
  {
    /* The exit edge.  */
!   struct edge_def *e;
  
    /* Previous and next exit in the list of the exits of the loop.  */
    struct loop_exit *prev;
*************** struct loop_exit
*** 88,105 ****
  typedef struct loop *loop_p;
  DEF_VEC_P (loop_p);
  DEF_VEC_ALLOC_P (loop_p, heap);
  
  /* Structure to hold information for each natural loop.  */
! struct loop
  {
    /* Index into loops array.  */
    int num;
  
    /* Basic block of loop header.  */
!   basic_block header;
  
    /* Basic block of loop latch.  */
!   basic_block latch;
  
    /* For loop unrolling/peeling decision.  */
    struct lpt_decision lpt_decision;
--- 88,106 ----
  typedef struct loop *loop_p;
  DEF_VEC_P (loop_p);
  DEF_VEC_ALLOC_P (loop_p, heap);
+ DEF_VEC_ALLOC_P (loop_p, gc);
  
  /* Structure to hold information for each natural loop.  */
! struct loop GTY ((chain_next ("%h.next")))
  {
    /* Index into loops array.  */
    int num;
  
    /* Basic block of loop header.  */
!   struct basic_block_def *header;
  
    /* Basic block of loop latch.  */
!   struct basic_block_def *latch;
  
    /* For loop unrolling/peeling decision.  */
    struct lpt_decision lpt_decision;
*************** struct loop
*** 114,120 ****
    unsigned num_nodes;
  
    /* Superloops of the loop, starting with the outermost loop.  */
!   VEC (loop_p, heap) *superloops;
  
    /* The first inner (child) loop or NULL if innermost loop.  */
    struct loop *inner;
--- 115,121 ----
    unsigned num_nodes;
  
    /* Superloops of the loop, starting with the outermost loop.  */
!   VEC (loop_p, gc) *superloops;
  
    /* The first inner (child) loop or NULL if innermost loop.  */
    struct loop *inner;
*************** struct loop
*** 126,132 ****
    struct loop *copy;
  
    /* Auxiliary info specific to a pass.  */
!   void *aux;
  
    /* The number of times the latch of the loop is executed.
       This is an INTEGER_CST or an expression containing symbolic
--- 127,133 ----
    struct loop *copy;
  
    /* Auxiliary info specific to a pass.  */
!   PTR GTY ((skip (""))) aux;
  
    /* The number of times the latch of the loop is executed.
       This is an INTEGER_CST or an expression containing symbolic
*************** struct loop
*** 158,164 ****
    struct nb_iter_bound *bounds;
  
    /* Head of the cyclic list of the exits of the loop.  */
!   struct loop_exit exits;
  };
  
  /* Flags for state of loop structure.  */
--- 159,165 ----
    struct nb_iter_bound *bounds;
  
    /* Head of the cyclic list of the exits of the loop.  */
!   struct loop_exit *exits;
  };
  
  /* Flags for state of loop structure.  */
*************** enum
*** 177,194 ****
  #define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
  
  /* Structure to hold CFG information about natural loops within a function.  */
! struct loops
  {
    /* State of loops.  */
    int state;
  
    /* Array of the loops.  */
!   VEC (loop_p, heap) *larray;
  
    /* Maps edges to the list of their descriptions as loop exits.  Edges
       whose sources or destinations have loop_father == NULL (which may
       happen during the cfg manipulations) should not appear in EXITS.  */
!   htab_t exits;
  
    /* Pointer to root of loop hierarchy tree.  */
    struct loop *tree_root;
--- 178,195 ----
  #define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
  
  /* Structure to hold CFG information about natural loops within a function.  */
! struct loops GTY (())
  {
    /* State of loops.  */
    int state;
  
    /* Array of the loops.  */
!   VEC (loop_p, gc) *larray;
  
    /* Maps edges to the list of their descriptions as loop exits.  Edges
       whose sources or destinations have loop_father == NULL (which may
       happen during the cfg manipulations) should not appear in EXITS.  */
!   htab_t GTY((param_is (struct loop_exit))) exits;
  
    /* Pointer to root of loop hierarchy tree.  */
    struct loop *tree_root;
*************** loop_outer (const struct loop *loop)
*** 428,434 ****
  
  /* Returns the list of loops in current_loops.  */
  
! static inline VEC (loop_p, heap) *
  get_loops (void)
  {
    if (!current_loops)
--- 429,435 ----
  
  /* Returns the list of loops in current_loops.  */
  
! static inline VEC (loop_p, gc) *
  get_loops (void)
  {
    if (!current_loops)
Index: Makefile.in
===================================================================
*** Makefile.in	(revision 124655)
--- Makefile.in	(working copy)
*************** tree-chrec.o: tree-chrec.c $(CONFIG_H) $
*** 2188,2194 ****
  tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \
     coretypes.h $(TM_H) $(GGC_H) $(TREE_H) $(REAL_H) $(RTL_H) \
     $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) \
!    $(TIMEVAR_H) $(CFGLOOP_H) $(SCEV_H) tree-pass.h $(FLAGS_H) tree-chrec.h
  tree-data-ref.o: tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
     $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \
     $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
--- 2188,2195 ----
  tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \
     coretypes.h $(TM_H) $(GGC_H) $(TREE_H) $(REAL_H) $(RTL_H) \
     $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) \
!    $(TIMEVAR_H) $(CFGLOOP_H) $(SCEV_H) tree-pass.h $(FLAGS_H) tree-chrec.h \
!    gt-tree-scalar-evolution.h
  tree-data-ref.o: tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
     $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \
     $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
*************** cfgcleanup.o : cfgcleanup.c $(CONFIG_H) 
*** 2571,2577 ****
     $(REGS_H) $(EMIT_RTL_H) $(CFGLAYOUT_H) tree-pass.h $(CFGLOOP_H) $(EXPR_H)
  cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) coretypes.h $(TM_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(FLAGS_H) $(FUNCTION_H) \
!    $(OBSTACK_H) toplev.h $(TREE_FLOW_H) $(TREE_H) pointer-set.h output.h
  cfgloopanal.o : cfgloopanal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(EXPR_H) coretypes.h $(TM_H) \
     $(OBSTACK_H) output.h
--- 2572,2579 ----
     $(REGS_H) $(EMIT_RTL_H) $(CFGLAYOUT_H) tree-pass.h $(CFGLOOP_H) $(EXPR_H)
  cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) coretypes.h $(TM_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(FLAGS_H) $(FUNCTION_H) \
!    $(OBSTACK_H) toplev.h $(TREE_FLOW_H) $(TREE_H) pointer-set.h output.h \
!    $(GGC_H)
  cfgloopanal.o : cfgloopanal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(EXPR_H) coretypes.h $(TM_H) \
     $(OBSTACK_H) output.h
*************** loop-invariant.o : loop-invariant.c $(CO
*** 2589,2595 ****
  cfgloopmanip.o : cfgloopmanip.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) output.h \
     coretypes.h $(TM_H) cfghooks.h $(OBSTACK_H)
! loop-init.o : loop-init.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) \
     coretypes.h $(TM_H) $(OBSTACK_H) tree-pass.h $(TIMEVAR_H) $(FLAGS_H)
  loop-unswitch.o : loop-unswitch.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TM_H) \
--- 2591,2597 ----
  cfgloopmanip.o : cfgloopmanip.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) output.h \
     coretypes.h $(TM_H) cfghooks.h $(OBSTACK_H)
! loop-init.o : loop-init.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(GGC_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) \
     coretypes.h $(TM_H) $(OBSTACK_H) tree-pass.h $(TIMEVAR_H) $(FLAGS_H)
  loop-unswitch.o : loop-unswitch.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TM_H) \
*************** GTFILES = $(srcdir)/input.h $(srcdir)/co
*** 2977,2983 ****
    $(srcdir)/coverage.c $(srcdir)/rtl.h \
    $(srcdir)/optabs.h $(srcdir)/tree.h $(srcdir)/function.h $(srcdir)/libfuncs.h $(SYMTAB_H) \
    $(srcdir)/real.h $(srcdir)/varray.h $(srcdir)/insn-addr.h $(srcdir)/hwint.h \
!   $(srcdir)/ipa-reference.h $(srcdir)/output.h \
    $(srcdir)/cselib.h $(srcdir)/basic-block.h  $(srcdir)/cgraph.h \
    $(srcdir)/reload.h \
    $(srcdir)/alias.c $(srcdir)/bitmap.c $(srcdir)/cselib.c $(srcdir)/cgraph.c \
--- 2979,2985 ----
    $(srcdir)/coverage.c $(srcdir)/rtl.h \
    $(srcdir)/optabs.h $(srcdir)/tree.h $(srcdir)/function.h $(srcdir)/libfuncs.h $(SYMTAB_H) \
    $(srcdir)/real.h $(srcdir)/varray.h $(srcdir)/insn-addr.h $(srcdir)/hwint.h \
!   $(srcdir)/ipa-reference.h $(srcdir)/output.h $(srcdir)/cfgloop.h \
    $(srcdir)/cselib.h $(srcdir)/basic-block.h  $(srcdir)/cgraph.h \
    $(srcdir)/reload.h \
    $(srcdir)/alias.c $(srcdir)/bitmap.c $(srcdir)/cselib.c $(srcdir)/cgraph.c \
*************** GTFILES = $(srcdir)/input.h $(srcdir)/co
*** 2991,2997 ****
    $(srcdir)/reg-stack.c $(srcdir)/cfglayout.c $(srcdir)/cfglayout.h \
    $(srcdir)/sdbout.c $(srcdir)/stor-layout.c \
    $(srcdir)/stringpool.c $(srcdir)/tree.c $(srcdir)/varasm.c \
!   $(srcdir)/tree-mudflap.c $(srcdir)/tree-flow.h \
    $(srcdir)/tree-ssanames.c $(srcdir)/tree-eh.c $(srcdir)/tree-ssa-address.c \
    $(srcdir)/tree-phinodes.c $(srcdir)/tree-cfg.c \
    $(srcdir)/tree-dfa.c $(srcdir)/tree-ssa-propagate.c \
--- 2993,2999 ----
    $(srcdir)/reg-stack.c $(srcdir)/cfglayout.c $(srcdir)/cfglayout.h \
    $(srcdir)/sdbout.c $(srcdir)/stor-layout.c \
    $(srcdir)/stringpool.c $(srcdir)/tree.c $(srcdir)/varasm.c \
!   $(srcdir)/tree-mudflap.c $(srcdir)/tree-flow.h $(srcdir)/tree-scalar-evolution.c \
    $(srcdir)/tree-ssanames.c $(srcdir)/tree-eh.c $(srcdir)/tree-ssa-address.c \
    $(srcdir)/tree-phinodes.c $(srcdir)/tree-cfg.c \
    $(srcdir)/tree-dfa.c $(srcdir)/tree-ssa-propagate.c \
Index: basic-block.h
===================================================================
*** basic-block.h	(revision 124655)
--- basic-block.h	(working copy)
*************** struct basic_block_def GTY((chain_next (
*** 221,227 ****
    PTR GTY ((skip (""))) aux;
  
    /* Innermost loop containing the block.  */
!   struct loop * GTY ((skip (""))) loop_father;
  
    /* The dominance and postdominance information node.  */
    struct et_node * GTY ((skip (""))) dom[2];
--- 221,227 ----
    PTR GTY ((skip (""))) aux;
  
    /* Innermost loop containing the block.  */
!   struct loop *loop_father;
  
    /* The dominance and postdominance information node.  */
    struct et_node * GTY ((skip (""))) dom[2];

Re: [patch] Move loop structures to gc memory

[Richard Guenther]

On 5/13/07, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> Hello,
>
> all the loop structures are now malloc-ed.  Since trees may be
> referenced from the loop structures, this prevents garbage collection
> from being run while loop structures are present.  This is going to be
> impossible once we preserve the loop information across larger portion
> of middle-end.
>
> This patch makes all loop structures gc-allocated.

I suppose it is not possible (or practicable) to mark these references
as new GC roots?  Otherwise, oh well ;)

Richard.

Re: [patch] Move loop structures to gc memory

[Zdenek Dvorak]

Hello,

> >all the loop structures are now malloc-ed.  Since trees may be
> >referenced from the loop structures, this prevents garbage collection
> >from being run while loop structures are present.  This is going to be
> >impossible once we preserve the loop information across larger portion
> >of middle-end.
> >
> >This patch makes all loop structures gc-allocated.
> 
> I suppose it is not possible (or practicable) to mark these references
> as new GC roots?

not really (well, it would be possible to make them reachable by some
other means, but it would be a really dirty hack).

Zdenek

Re: [patch] Move loop structures to gc memory

[Daniel Berlin]

On 5/13/07, Richard Guenther <richard.guenther@gmail.com> wrote:
> On 5/13/07, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> > Hello,
> >
> > all the loop structures are now malloc-ed.  Since trees may be
> > referenced from the loop structures, this prevents garbage collection
> > from being run while loop structures are present.  This is going to be
> > impossible once we preserve the loop information across larger portion
> > of middle-end.
> >
> > This patch makes all loop structures gc-allocated.
>
> I suppose it is not possible (or practicable) to mark these references
> as new GC roots?

This is one of the many deficiencies of our GC.  There is no way to
mark roots that are not in GC memory, so anything pointing to anything
gc'd has to be GC'd itself :(

Otherwise, the marking code just crashes.

Re: [patch] Move loop structures to gc memory

[Ian Lance Taylor]

Zdenek Dvorak <rakdver@kam.mff.cuni.cz> writes:

> Since all the loop structures used to be deallocated manually, I have
> just rewritten all the frees to ggc_frees; I hope this won't cause any
> problems (in general, we are pretty sure what the life ranges of loop
> structures and associated objects are).

This makes me uncomfortable.  I expect that it is correct for now.
But it sets us up for later confusion as accesses to the structures
change.  In general I don't like any use of ggc_free.

Ian

Re: [patch] Move loop structures to gc memory

[Zdenek Dvorak]

Hello,

> Zdenek Dvorak <rakdver@kam.mff.cuni.cz> writes:
> 
> > Since all the loop structures used to be deallocated manually, I have
> > just rewritten all the frees to ggc_frees; I hope this won't cause any
> > problems (in general, we are pretty sure what the life ranges of loop
> > structures and associated objects are).
> 
> This makes me uncomfortable.  I expect that it is correct for now.
> But it sets us up for later confusion as accesses to the structures
> change.  In general I don't like any use of ggc_free.

I guess opinions may differ here; I would somewhat prefer to use
ggc_free as much as possible, as it prevents memory leaks through
dangling pointers.  If I am sure some memory should not be accessible
any more, I prefer to be told that I am wrong to silently keeping
the memory allocated by mistake.

Of course, you get this result with ggc_free only with gc checking
enabled, which is somewhat annoying.

Zdenek

Re: [patch] Move loop structures to gc memory

[Mike Stump]

On May 14, 2007, at 11:12 AM, Ian Lance Taylor wrote:
> In general I don't like any use of ggc_free.

Do you prefer a slower compiler?

Re: [patch] Move loop structures to gc memory

[Ian Lance Taylor]

Mike Stump <mrs@apple.com> writes:

> On May 14, 2007, at 11:12 AM, Ian Lance Taylor wrote:
> > In general I don't like any use of ggc_free.
> 
> Do you prefer a slower compiler?

I prefer moving data structures out of GC space.  Unfortunately doing
this fully requires fixing our GC implementation.  Or, preferably,
eliminating it.

Using ggc_free with GC just puts us on the road back to the problems
which led us to introduce GC in the first place: we didn't track our
memory allocations properly, so we got confused and got weird crashes.
We introduced GC so that it didn't matter whether we tracked our
memory allocations properly or not.  There was no other reason for GC.
When we use ggc_free, we lose the whole point of having GC.  It just
does not make sense.

Ian

Re: [patch] Move loop structures to gc memory

[Zdenek Dvorak]

Hello,

> Mike Stump <mrs@apple.com> writes:
> 
> > On May 14, 2007, at 11:12 AM, Ian Lance Taylor wrote:
> > > In general I don't like any use of ggc_free.
> > 
> > Do you prefer a slower compiler?
> 
> I prefer moving data structures out of GC space.  Unfortunately doing
> this fully requires fixing our GC implementation.  Or, preferably,
> eliminating it.
> 
> Using ggc_free with GC just puts us on the road back to the problems
> which led us to introduce GC in the first place: we didn't track our
> memory allocations properly, so we got confused and got weird crashes.
> We introduced GC so that it didn't matter whether we tracked our
> memory allocations properly or not.  There was no other reason for GC.
> When we use ggc_free, we lose the whole point of having GC.  It just
> does not make sense.

well, sort of.  There are some structures that are hard to keep track of
(trees and rtl, and maybe a few others), and I think it is OK to have gc
for them.  I guess most of the other thinks that are currently kept in
GC should not be, but it would be a bit hard to keep track of all GC
roots if we moved them out.  Using ggc_free of course is not a nice
solution, but not using it for structures for that we are sure that they
are no longer reachable is wasteful.

Zdenek

Re: [patch] Move loop structures to gc memory

[Daniel Jacobowitz]

On Mon, May 14, 2007 at 02:26:39PM -0700, Ian Lance Taylor wrote:
> Using ggc_free with GC just puts us on the road back to the problems
> which led us to introduce GC in the first place: we didn't track our
> memory allocations properly, so we got confused and got weird crashes.

That's no more true than it would be if we used malloc instead for any
particular allocation.  We have lots of allocation strategies in
today's GCC (whether that's a good thing or not); I think "GC with
explicit death marking" is just as valid as "plain GC".

And it makes it easier to move them out of GC again later.

> We introduced GC so that it didn't matter whether we tracked our
> memory allocations properly or not.  There was no other reason for GC.
> When we use ggc_free, we lose the whole point of having GC.  It just
> does not make sense.

No, we lose the original motivation.  That original motivation was
mostly for RTL.  Explicitly managed structures aren't the same problem
at all.

-- 
Daniel Jacobowitz
CodeSourcery

Re: [patch] Move loop structures to gc memory

[Ian Lance Taylor]

Zdenek Dvorak <rakdver@kam.mff.cuni.cz> writes:

> > > On May 14, 2007, at 11:12 AM, Ian Lance Taylor wrote:
> > Using ggc_free with GC just puts us on the road back to the problems
> > which led us to introduce GC in the first place: we didn't track our
> > memory allocations properly, so we got confused and got weird crashes.
> > We introduced GC so that it didn't matter whether we tracked our
> > memory allocations properly or not.  There was no other reason for GC.
> > When we use ggc_free, we lose the whole point of having GC.  It just
> > does not make sense.
> 
> well, sort of.  There are some structures that are hard to keep track of
> (trees and rtl, and maybe a few others), and I think it is OK to have gc
> for them.  I guess most of the other thinks that are currently kept in
> GC should not be, but it would be a bit hard to keep track of all GC
> roots if we moved them out.  Using ggc_free of course is not a nice
> solution, but not using it for structures for that we are sure that they
> are no longer reachable is wasteful.

I think that correctly keeping track of the various GC roots is
precisely as hard as correctly using ggc_free.  Both are cases where
we need to correctly determine whether we have a live pointer into GC
memory.  And indeed we've had a series of bugs over the years in which
static variables were not correctly annotated as being GC roots, just
as we've had several bugs in which ggc_free was used incorrectly.

Setting a pointer to NULL is always safe.

Ian

Re: [patch] Move loop structures to gc memory

[Ian Lance Taylor]

Daniel Jacobowitz <drow@false.org> writes:

> On Mon, May 14, 2007 at 02:26:39PM -0700, Ian Lance Taylor wrote:
> > Using ggc_free with GC just puts us on the road back to the problems
> > which led us to introduce GC in the first place: we didn't track our
> > memory allocations properly, so we got confused and got weird crashes.
> 
> That's no more true than it would be if we used malloc instead for any
> particular allocation.  We have lots of allocation strategies in
> today's GCC (whether that's a good thing or not); I think "GC with
> explicit death marking" is just as valid as "plain GC".

We have different allocation strategies for different reasons.

Why do we need the strategy of "GC with explicit death marking?"  What
goal does that serve?

Except to work around a bug in our GC implementation?  And in that
case, why not fix the bug?

Ian

Re: [patch] Move loop structures to gc memory

[Zdenek Dvorak]

Hello,

> Except to work around a bug in our GC implementation?  And in that
> case, why not fix the bug?

how?

Zdenek

Re: [patch] Move loop structures to gc memory

[Daniel Jacobowitz]

On Mon, May 14, 2007 at 03:37:40PM -0700, Ian Lance Taylor wrote:
> Why do we need the strategy of "GC with explicit death marking?"  What
> goal does that serve?

Exactly this problem.  Which comes up several times a year.

> Except to work around a bug in our GC implementation?  And in that
> case, why not fix the bug?

Would you like to try?  Last time I looked at this I had just spent a
month hacking on the GC, and I didn't see any way to do it.  I'm sure
it's possible, though.

-- 
Daniel Jacobowitz
CodeSourcery

Re: [patch] Move loop structures to gc memory

[Ian Lance Taylor]

Daniel Jacobowitz <drow@false.org> writes:

> On Mon, May 14, 2007 at 03:37:40PM -0700, Ian Lance Taylor wrote:
> > Why do we need the strategy of "GC with explicit death marking?"  What
> > goal does that serve?
> 
> Exactly this problem.  Which comes up several times a year.

How would you characterize the problem being solved?  (It's a serious
question.)

Ian

Re: [patch] Move loop structures to gc memory

[Mike Stump]

On May 14, 2007, at 3:37 PM, Ian Lance Taylor wrote:
> Why do we need the strategy of "GC with explicit death marking?"   
> What goal does that serve?

I want it mostly for speed, a secondary concern would be for size  
reasons.  Setting a variable to NULL_TREE doesn't help speed as much  
as ggc_free.


> Except to work around a bug in our GC implementation?  And in that  
> case, why not fix the bug?

We look forward to your contribution.  Until then and as long as size  
and speed are of concern, I think that things like skip and ggc_free  
can make sense in some cases.  Any case where we get >%1 speedup,  
personally, I'm interested in.  Personally, I'm willing to hit a few  
of the hard memory memory allocation problems caused by the attempted  
use of ggc_free in order to see a 20% speedup.  Now, let me explain  
why.  In the past, when you hit a hard memory problem, there was  
little to help you out on how and why, and even once you found it,  
some of them were simply impossible to fix short of permanently  
allocating things.  With ggc_free, it is possible to fix any of these  
issues by removing ggc_free calls.  This isn't too hard, and the  
penalty for doing this is generally less than permanently allocating  
things.  In addition, I think it is possible to have ggc_free help out  
on what went wrong and why, in a way that is safer and more  
understandable than memory overwrites of yesteryear.

Sure managing memory is harder than not, sure you can have bugs.  But  
I don't see GC a panacea.  With infinite ram and/or infinite compile  
time, there is no reason to use ggc_free, ever.  When either are  
limited, it can make sense.

Re: [patch] Move loop structures to gc memory

[Daniel Jacobowitz]

On Mon, May 14, 2007 at 04:24:45PM -0700, Ian Lance Taylor wrote:
> Daniel Jacobowitz <drow@false.org> writes:
> 
> > On Mon, May 14, 2007 at 03:37:40PM -0700, Ian Lance Taylor wrote:
> > > Why do we need the strategy of "GC with explicit death marking?"  What
> > > goal does that serve?
> > 
> > Exactly this problem.  Which comes up several times a year.
> 
> How would you characterize the problem being solved?  (It's a serious
> question.)

I would characterize it as data with a precisely identifiable
lifetime, where there is some other advantage to storing it in GC
memory.

Case A: Every "struct foo" has precisely known lifetime, but they
contain GC'd pointers and we want to collect while they're live.
This case.  A bit tricky to get around; there could be a lot of them,
and the roots list would not scale well if we had to add and remove
them dynamically.  It'd have to be a pointer set instead except we
need type info too.

Case B: Some "struct foo" have precisely known lifetimes, others
don't.  For instance, suppose we built up information about
interesting loops in GC memory; we might want to save the data until
indefinitely later, except that during the build-up process we
disqualify some loops from interestingness.  We could ggc_free
them, and as a bonus with appropriate checking this would make sure
later passes weren't bogusly looking at boring loops.

Does that clarify the need I see?

-- 
Daniel Jacobowitz
CodeSourcery

Re: [patch] Move loop structures to gc memory

[Steven Bosscher]

On Tuesday 15 May 2007 01:57, Mike Stump wrote:
> On May 14, 2007, at 3:37 PM, Ian Lance Taylor wrote:
> > Why do we need the strategy of "GC with explicit death marking?"
> > What goal does that serve?
>
> I want it mostly for speed, a secondary concern would be for size
> reasons.  Setting a variable to NULL_TREE doesn't help speed as much
> as ggc_free.
>
> > Except to work around a bug in our GC implementation?  And in that
> > case, why not fix the bug?
>
> We look forward to your contribution.

Wait, wasn't it Apple who once promissed to speed up GCC 6 times by
looking into this issue?  Here's a great place to start for you, Mike! ;-)

Gr.
Steven

Re: [patch] Move loop structures to gc memory

[Mike Stump]

On May 14, 2007, at 9:07 PM, Steven Bosscher wrote:
>> We look forward to your contribution.
>
> Wait, wasn't it Apple who once promissed to speed up GCC 6 times by  
> looking into this issue?

I don't recall that promise, maybe you have a quote handy?  :-)   
We're about at 2x slower right now as I recall.  I'd call that in the  
shooting match.

Re: [patch] Move loop structures to gc memory

[Paolo Bonzini]

Mike Stump wrote:
> On May 14, 2007, at 9:07 PM, Steven Bosscher wrote:
>>> We look forward to your contribution.
>>
>> Wait, wasn't it Apple who once promissed to speed up GCC 6 times by 
>> looking into this issue?
> 
> I don't recall that promise, maybe you have a quote handy?  :-)

Since Steven has just beaten me to answering, I'll provide the quotes :-)

http://gcc.gnu.org/ml/gcc/2002-08/msg00498.html
http://gcc.gnu.org/ml/gcc/2002-08/msg00519.html

Paolo

Re: [patch] Move loop structures to gc memory

[Mike Stump]

On May 15, 2007, at 12:02 AM, Paolo Bonzini wrote:
> Mike Stump wrote:
>> On May 14, 2007, at 9:07 PM, Steven Bosscher wrote:
>>>> We look forward to your contribution.
>>>
>>> Wait, wasn't it Apple who once promissed to speed up GCC 6 times  
>>> by looking into this issue?
>> I don't recall that promise, maybe you have a quote handy?  :-)
>
> Since Steven has just beaten me to answering, I'll provide the  
> quotes :-)
>
> http://gcc.gnu.org/ml/gcc/2002-08/msg00498.html
> http://gcc.gnu.org/ml/gcc/2002-08/msg00519.html

First, I don't really understand to what bug Ian refers to, so, I  
couldn't fix it, even if I wanted to.  Second, I'd predict at this  
point, that even if the bug were fixed, it would not be as fast as  
ggc_free.  If it isn't faster, I don't see what relevance it has to  
the two quoted above.  And lastly, I don't think this issue was  
contained in either of those two messages, just for the record.

Re: [patch] Move loop structures to gc memory

[Ian Lance Taylor]

Mike Stump <mrs@apple.com> writes:

> First, I don't really understand to what bug Ian refers to, so, I
> couldn't fix it, even if I wanted to.  Second, I'd predict at this
> point, that even if the bug were fixed, it would not be as fast as
> ggc_free.  If it isn't faster, I don't see what relevance it has to
> the two quoted above.  And lastly, I don't think this issue was
> contained in either of those two messages, just for the record.

The bug, if it is indeed a bug, is that the set of GC roots is static.
If you want to have a dynamically allocated pointer into GC memory,
you must put that pointer into GC memory itself.

Fixing that, and using it for the loop structures, would not be slower
than using ggc_free.  It would be a trade between recording the
dynamic root in some fashion on the one hand, and manipulating the
more complex data structures required by GC allocation on the other.

Ian

Re: [patch] Move loop structures to gc memory

[Michael Matz]

Hi,

On Tue, 15 May 2007, Ian Lance Taylor wrote:

> > First, I don't really understand to what bug Ian refers to, so, I
> > couldn't fix it, even if I wanted to.  Second, I'd predict at this
> > point, that even if the bug were fixed, it would not be as fast as
> > ggc_free.  If it isn't faster, I don't see what relevance it has to
> > the two quoted above.  And lastly, I don't think this issue was
> > contained in either of those two messages, just for the record.
> 
> The bug, if it is indeed a bug, is that the set of GC roots is static.
> If you want to have a dynamically allocated pointer into GC memory,
> you must put that pointer into GC memory itself.
> 
> Fixing that, and using it for the loop structures, would not be slower
> than using ggc_free.

But it also wouldn't be different the slightest.  You just move the 
problem of when to call ggc_free to when to remove that pointer from the 
set of additional roots.  Unless of course you don't want to remove them 
once allocated.  But that would be wasteful again, just like every memory 
leak.

> It would be a trade between recording the dynamic root in some fashion 
> on the one hand, and manipulating the more complex data structures 
> required by GC allocation on the other.

The problem isn't so much recording the new pointer, but removing it again 
in some sensible way, when unused, as you can't have the GC marking do 
that for you anymore with non-GC pointers.  I.e. exactly what ggc_free 
does.


Ciao,
Michael.

Re: [patch] Move loop structures to gc memory

[Ian Lance Taylor]

Michael Matz <matz@suse.de> writes:

> > > First, I don't really understand to what bug Ian refers to, so, I
> > > couldn't fix it, even if I wanted to.  Second, I'd predict at this
> > > point, that even if the bug were fixed, it would not be as fast as
> > > ggc_free.  If it isn't faster, I don't see what relevance it has to
> > > the two quoted above.  And lastly, I don't think this issue was
> > > contained in either of those two messages, just for the record.
> > 
> > The bug, if it is indeed a bug, is that the set of GC roots is static.
> > If you want to have a dynamically allocated pointer into GC memory,
> > you must put that pointer into GC memory itself.
> > 
> > Fixing that, and using it for the loop structures, would not be slower
> > than using ggc_free.
> 
> But it also wouldn't be different the slightest.  You just move the 
> problem of when to call ggc_free to when to remove that pointer from the 
> set of additional roots.  Unless of course you don't want to remove them 
> once allocated.  But that would be wasteful again, just like every memory 
> leak.

No, for example, we could enhance the GTY markings to say "this field
in cfun points to a linked list of structs, linked by this field.  For
each instance of the struct, these fields in the struct point into GC
memory."  Then a list of, e.g., loop structs would automatically
become GC roots with no additional work required.  That is simple and
safe.

Ian

Re: [patch] Move loop structures to gc memory

[Mark Mitchell]

Daniel Jacobowitz wrote:
> On Mon, May 14, 2007 at 04:24:45PM -0700, Ian Lance Taylor wrote:
>> Daniel Jacobowitz <drow@false.org> writes:
>>
>>> On Mon, May 14, 2007 at 03:37:40PM -0700, Ian Lance Taylor wrote:
>>>> Why do we need the strategy of "GC with explicit death marking?"  What
>>>> goal does that serve?
>>> Exactly this problem.  Which comes up several times a year.
>> How would you characterize the problem being solved?  (It's a serious
>> question.)
> 
> I would characterize it as data with a precisely identifiable
> lifetime, where there is some other advantage to storing it in GC
> memory.

Right.

As a concrete example, I used gcc_free to get a significant (1%?)
speedup in the C++ front end by freeing duplicated FUNCTION_DECLs in
duplicate_decls.  I knew at this point that that the nodes were garbage,
but by ggc_free'ing them, I got much better reuse of memory.  (The next
FUNCTION_DECL allocated ended up in the same memory location.)  Since
FUNCTION_DECLs clearly need to be in GC'd space (until we eliminate GC
altogether, which I'm all for, in principle!), this is, AFAICT, the only
way to get this performance advantage.

I fully agree that avoiding GC space is a good thing.  Furthermore, I
agree that putting things into GC space just because they point to GC
things (even though they themselves have obvious lifetimes) is a
lameness of our GC.  But, I don't think that the use of ggc_free itself
is inherently a mistake.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [patch] Move loop structures to gc memory

[Mike Stump]

On May 15, 2007, at 7:59 AM, Ian Lance Taylor wrote:
> The bug, if it is indeed a bug, is that the set of GC roots is static.

I've been known to have a file static TREE_LIST of nodes that have  
have pointers to from non-GCed memory.  Works just fine[1], though,  
kinda gross.  While there is a single static head, the runtime list   
_is_ dynamic in nature.  The list keeps GC from collecting any node  
of the list, and freeing is possible by just removing it from the  
list.  Simple, easy to manage, arbitrarily extensible and does exact  
what you seem to want to do.  For performance, one could have a  
vector, a splay, a hash or a red black tree...  One is not limited to  
just a list.

So, either, I don't yet understand what you want to do, or that is  
the solution to the problem and this isn't a bug?  I'd grant you that  
it is maybe inelegant.

> If you want to have a dynamically allocated pointer into GC memory,  
> you must put that pointer into GC memory itself.

Yes, this is true, but it doesn't mean you can't also have a pointer  
from non-GCed memory[1], which is the entire point of wanting to  
modify the set of GC roots?

> Fixing that, and using it for the loop structures, would not be  
> slower than using ggc_free.

I'd expect that to be about right.  There are a couple of reasons why  
one may prefer ggc_free instead.  If one wants to do a generation  
collector in the future, not having the objects managed by GC could  
make things tricky, or if one needs correctness across PCH writing  
and reading, letting GC manage is easiest way to go.


1 - You cannot do this across PCH write/read.

Re: [patch] Move loop structures to gc memory

[Mike Stump]

On May 15, 2007, at 2:49 PM, Ian Lance Taylor wrote:
> No, for example, we could enhance the GTY markings to say "this field
> in cfun points to a linked list of structs, linked by this field.

But, you can already do that.

> For each instance of the struct, these fields in the struct point  
> into GC
> memory."

And this.

> Then a list of, e.g., loop structs would automatically become GC  
> roots with no additional work required.

And this.

?  Now I am confused again.  :-)

my_data {
	my_data *next;
	char *otherfied ((GTY("skip")));
};

struct cfun_t GTY(()) {
	my_data *next;
	bla otherdata;
} *cfun;

?

Re: [patch] Move loop structures to gc memory

[Mike Stump]

On May 15, 2007, at 6:22 PM, Mark Mitchell wrote:
> Furthermore, I agree that putting things into GC space just because  
> they point to GC things (even though they themselves have obvious  
> lifetimes) is a lameness of our GC.

But, one doesn't have to do that if you don't need it to span across  
PCH write-read boundaries?  If you do need it to span across this  
boundary, then this isn't a lameness, it is just a requirement, that,  
or you need to do a whole of work to write/write and relocate and  
update stuff.  Generally that is frowned upon as it makes using PCH  
slower.

Re: [patch] Move loop structures to gc memory

[Ian Lance Taylor]

Mike Stump <mrs@apple.com> writes:

> On May 15, 2007, at 2:49 PM, Ian Lance Taylor wrote:
> > No, for example, we could enhance the GTY markings to say "this field
> > in cfun points to a linked list of structs, linked by this field.
> 
> But, you can already do that.

Can you do it for a linked list of structs which are not themselves in
GC memory?

Ian

Re: [patch] Move loop structures to gc memory

[Mike Stump]

On May 15, 2007, at 9:41 PM, Ian Lance Taylor wrote:
> Mike Stump <mrs@apple.com> writes:
>
>> On May 15, 2007, at 2:49 PM, Ian Lance Taylor wrote:
>>> No, for example, we could enhance the GTY markings to say "this  
>>> field
>>> in cfun points to a linked list of structs, linked by this field.
>>
>> But, you can already do that.
>
> Can you do it for a linked list of structs which are not themselves  
> in GC memory?

Ah, I see what you want, you want to go back one more ply.  No, you'd  
need to have a duplicate data structure in GCed memory or add a some  
code to ggc itself (see ggc_mark_stringpool in ggc-common.c for an  
example of a non-standard marker) or some other mechanism like a GTY  
scanner upgrade.

For a well known data structure, I don't think it would be the end of  
the world to just mark it in ggc_mark_roots, certainly that's easier  
than a general mechanism.  Also, it prevents people from going hog  
wild with the general mechanism (say a misuse in a port file) as they  
then have to have a ggc person Ok it.

Re: [patch] Move loop structures to gc memory

[Alexandre Oliva]

On May 15, 2007, Mark Mitchell <mark@codesourcery.com> wrote:

> I agree that putting things into GC space just because they point to
> GC things (even though they themselves have obvious lifetimes) is a
> lameness of our GC.

I'm not sure I understand what you mean.  Not doing so implies either
pinning the pointed-at objects by hand (yuck) or adding the "things"
as GC roots, which is really not that different from GC-allocating
them as roots in the first place.  What am I missing?

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [patch] Move loop structures to gc memory

[Daniel Berlin]

On 5/16/07, Alexandre Oliva <aoliva@redhat.com> wrote:
> On May 15, 2007, Mark Mitchell <mark@codesourcery.com> wrote:
>
> > I agree that putting things into GC space just because they point to
> > GC things (even though they themselves have obvious lifetimes) is a
> > lameness of our GC.
>
> I'm not sure I understand what you mean.  Not doing so implies either
> pinning the pointed-at objects by hand (yuck) or adding the "things"
> as GC roots, which is really not that different from GC-allocating
> them as roots in the first place.

Except that you lose all the benefits of it *not* being in GC.

As a concrete example:

Our basic blocks were pool allocated using alloc_pool's.
Because they started pointing to GC'd structures directly (in order to
simplify things), we switched them to be gc alloced.

We lost about 1-2% compile time from doing this (see the archives),
because alloc pools are contiguous in memory, and our gc was just
handing out random free memory that happened to be around the same
size.

Things that have a very well defined lifetime (which are basic blocks
do, for example), should not have to be in GC memory simply because
they point to GC objects.

You can argue that "well, it doesn't really hurt most of the time",
"we could improve the GC to get better locality" etc, but it doesn't
change that basic premise.  No one in this thread has yet given a good
reason we should have to GC things that we don't want to GC, just to
get things they point to GC'd without really ugly hacks/workarounds.

The only reason i've seen is "well, it's hard".

Speed wise, profiles of the GC have never shown the actual root list
walking to be slow, only the actual mark lookups and sets.  Adding
dynamic roots would make the root list walking slightly slower, but if
we have *less* things in GC overall, we will do less mark setting,
which is where most of GC time goes.
So it should be a win overall.

Re: [patch] Move loop structures to gc memory

[Alexandre Oliva]

On May 16, 2007, "Daniel Berlin" <dberlin@dberlin.org> wrote:

> Except that you lose all the benefits of it *not* being in GC.

> As a concrete example:

> Our basic blocks were pool allocated using alloc_pool's.

I don't follow the logic.  Why couldn't pools be in GC memory, again,
so as to reap the benefits without complicating the logic?

I do understand the benefits of locality, I just don't understand how
GC allegedly gets in the way of the techniques we use to improve
locality.

And then, one way or another, if you don't want GC to collect objects
pointed to by objects in these pools, there are two ways to approach
the issue: either the referring objects are in GC memory and
referenced by roots (or roots themselves), or they're in non-GC memory
and the GC machinery must be able to walk objects (or at least roots,
which would require all such referring objects to be registered as
roots) in non-GC memory.

This bit is mostly a matter of drawing the line of what it means to be
GC memory or not (as in, is it GC-allocated or just GC-walkable).

I don't see that allocation patterns that improve locality are
necessarily forbidden by GC machinery.  Maybe they're hard to model in
our current machinery (I don't know), but I got the impression the
discussion here was about GC in general, not about GGC in particular.
Maybe I misunderstood.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [patch] Move loop structures to gc memory

[Mark Mitchell]

Alexandre Oliva wrote:

> This bit is mostly a matter of drawing the line of what it means to be
> GC memory or not (as in, is it GC-allocated or just GC-walkable).

Rather, between GC-allocated and points-to-GC-allocated.  The point is
that these are logically distinct concepts; our implementation conflates
them.

To see why this is undesirable, consider suppose that you want to
allocate some temporary memory, which an obvious lifetime, which will
point to TREEs.  Some of the TREEs may be pointed to *only* from this
temporary memory.  You want to be able to run the collector while this
temporary memory is allocated.  So, it's important that the GC system
know that there are roots in this temporary memory.

In our current system, you must GC-allocate this temporary memory.  (For
example, you can't use alloca, or obstacks, both of which are very fast
allocation schemes.)  Then, when you're done with the temporary memory,
you must wait for the collector to collect it -- or explicitly ggc_free
it.

If you're in the camp that wants to avoid ggc_free, you have to wait for
this memory to be collected, by which point you'll probably have
allocated more stuff, which could have been more efficiently put in the
in-cache now-garbage memory, but wasn't put there because that memory
hadn't been collected yet.

If you're willing to use ggc_free, you can reclaim the memory in timely
fashion, and thus avoid the locality problem, but you still have to use
our relatively expensive GC-allocation/deallocation functions, rather
than the more efficient alloca/obstack (or, even, probably, malloc)
family of functions.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [patch] Move loop structures to gc memory

[Ian Lance Taylor]

Alexandre Oliva <aoliva@redhat.com> writes:

> On May 16, 2007, "Daniel Berlin" <dberlin@dberlin.org> wrote:
> 
> > Except that you lose all the benefits of it *not* being in GC.
> 
> > As a concrete example:
> 
> > Our basic blocks were pool allocated using alloc_pool's.
> 
> I don't follow the logic.  Why couldn't pools be in GC memory, again,
> so as to reap the benefits without complicating the logic?

Putting something in GC memory unnecessarily is inevitably slower than
not putting it in GC memory, if only because GC requires overhead to
track objects.

> This bit is mostly a matter of drawing the line of what it means to be
> GC memory or not (as in, is it GC-allocated or just GC-walkable).

What matters for us is GC-allocated.  We don't collect very often, so
it is fine to have a reasonably small increase in the amount of time
it takes to collect in exchange for a speedup in allocation or
deallocation or access.

> I don't see that allocation patterns that improve locality are
> necessarily forbidden by GC machinery.  Maybe they're hard to model in
> our current machinery (I don't know), but I got the impression the
> discussion here was about GC in general, not about GGC in particular.
> Maybe I misunderstood.

I am talking specifically about gcc's implementation and use of GC.

Ian

Re: [patch] Move loop structures to gc memory

[Alexandre Oliva]

On May 16, 2007, Ian Lance Taylor <iant@google.com> wrote:

> Alexandre Oliva <aoliva@redhat.com> writes:
>> On May 16, 2007, "Daniel Berlin" <dberlin@dberlin.org> wrote:
>> 
>> > Except that you lose all the benefits of it *not* being in GC.
>> 
>> > As a concrete example:
>> 
>> > Our basic blocks were pool allocated using alloc_pool's.
>> 
>> I don't follow the logic.  Why couldn't pools be in GC memory, again,
>> so as to reap the benefits without complicating the logic?

> Putting something in GC memory unnecessarily is inevitably slower than
> not putting it in GC memory, if only because GC requires overhead to
> track objects.

I'm not sure this follows.  If you have to scan it for pointers to
live objects, then you have to track it either as a regular object or
as a root.  Tracking it as a root might be slightly cheaper, but it's
not without overheads.

>> I don't see that allocation patterns that improve locality are
>> necessarily forbidden by GC machinery.  Maybe they're hard to model in
>> our current machinery (I don't know)

> I am talking specifically about gcc's implementation and use of GC.

So is it indeed true that current GGC machinery prevents allocation
patterns that improve locality?  And, if so, is this harder to fix
than maintaining non-GC-controlled roots for all cases in which we'd
like to have better-locality allocation patterns and explicit death
marking than what the default allocation pattern would provide?

I.e., instead of:

  fastobjcollection = alloc (bigenough);
  ...
  obj = new_obj_in_collection (fastobjcollection, size);
  ggc_add_root (obj, typedescriptor);
  ...
  ggc_remove_root (obj);
  remove_obj_from_collection (obj);
  ...
  free (fastobjcollection);

is there any reason we can't have:

  fastobjcollection = ggc_alloc (bigenough);
  ggc_add_root (fastobjcollection, objcollectiondescriptor);
  ...
  obj = new_obj_in_collection (fastobjcollection, size);
  ...
  remove_obj_from_collection (obj);
  ...
  ggc_free (fastobjcollection);
  
In other words, what does moving the objects out of GCable memory
really buy us?  If the issue is the allocation pattern, we can do
that, and it's not like we can escape completely *some* kind of
object tracking if we need to be able to collect garbage while this
non-GC structure still exists.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [patch] Move loop structures to gc memory

[Alexandre Oliva]

On May 16, 2007, Mark Mitchell <mark@codesourcery.com> wrote:

> So, it's important that the GC system know that there are roots in
> this temporary memory.

Yup.

> In our current system, you must GC-allocate this temporary memory.

This doesn't seem like the single root cause of the problem to me.

AFAICT, the root cause of the problem is that you can't dynamically
register and deregister GC roots.

If you could, then you could allocate objects in however way it seemed
reasonable to you, and you could register these objects with whatever
walk functions or GGC types you'd like to use for them, such that
GCable objects reachable from them would be marked as live.

You'd then have to be careful to decide which pointers in such objects
might point to GC-able memory and which must not, because our
collector is not conservative.  And you'd have to remember that such
dynamic roots wouldn't be preserved across PCH, because, well, they're
not managed by GGC.


So how about we introduce a new type:

struct ggc_dynroot_tab {
  void *base;
  gt_pointer_walker cb;
  struct ggc_dynroot_tab *next;
};

such that we could use it like this:

struct mydynroot {
  struct ggc_dynroot_tab gcroot;
  tree whatever;
};

  struct mydynroot *p = alloca (sizeof (*p));
  memset (p, 0, sizeof (*p));
  ggc_add_dynroot (&p->gcroot, p, walk_mydynroot);

  ...

  ggc_remove_dynroot (&p->gcroot);

or like this:

  struct ggc_dynroot_tab gcroot;
  tree whatever = NULL_TREE;

  ggc_add_dynroot (&gcroot, &whatever, walk_ind_tree);

  ...

  ggc_remove_dynroot (&gcroot);
  
FAICT all this would take in ggc-common would be trivial headless
linked-list implementations of ggc_add_dynroot and ggc_remove_dynroot,
and an additional look in ggc_mark_roots to call the callback for each
dynroot.


Using obstacks might be trickier, since you have to know the structure
of what you're supposed to walk.  But if you can write a walk function
for that, or get gengtype to do so for you, you're fine.


> If you're in the camp that wants to avoid ggc_free,

I'm not, I don't have any qualms at all with explicit lifetime
termination, especially when locality is known to be favorable to this
kind of memory management.

I was just trying to understand what the problem with allocating GGC
memory was.  I was only thinking obstacks, and that didn't seem
unworkable to me.  I hadn't considered alloca, but now I can see where
you're coming from, and I think the above will deal with it, no?

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [patch] Move loop structures to gc memory

[Mark Mitchell]

Alexandre Oliva wrote:

>> In our current system, you must GC-allocate this temporary memory.
> 
> This doesn't seem like the single root cause of the problem to me.
> 
> AFAICT, the root cause of the problem is that you can't dynamically
> register and deregister GC roots.

It's both. :-)

You've nailed one of the key problems: you need to dynamically register
and deregister roots.  But, one of the reasons you need that ability is
precisely so that you can have the roots live in non-GC memory, so that
you can use faster allocation/deallocation methods.

What you want to do is like:

  struct s {
    ...
    tree t;
    ...
  };

  struct s* p = some_alloc (sizeof (s));
  p->t = build1 (...);
  ggc_register_root (&p->t);
  ...
  ggc_collect ();
  ...
  ggc_deregister_root (&p->t);
  some_free (p);

In order to be able to use some_{alloc,free} (presumed to be faster, or
otherwise better, that ggc_alloc/ggc_free), you have to have
ggc_{register,deregister}_root.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [patch] Move loop structures to gc memory

[Daniel Berlin]

On 5/16/07, Alexandre Oliva <aoliva@redhat.com> wrote:
> On May 16, 2007, Ian Lance Taylor <iant@google.com> wrote:
>
> > Alexandre Oliva <aoliva@redhat.com> writes:
> >> On May 16, 2007, "Daniel Berlin" <dberlin@dberlin.org> wrote:
> >>
> >> > Except that you lose all the benefits of it *not* being in GC.
> >>
> >> > As a concrete example:
> >>
> >> > Our basic blocks were pool allocated using alloc_pool's.
> >>
> >> I don't follow the logic.  Why couldn't pools be in GC memory, again,
> >> so as to reap the benefits without complicating the logic?
>
> > Putting something in GC memory unnecessarily is inevitably slower than
> > not putting it in GC memory, if only because GC requires overhead to
> > track objects.
>
> I'm not sure this follows.  If you have to scan it for pointers to
> live objects, then you have to track it either as a regular object or
> as a root.  Tracking it as a root might be slightly cheaper, but it's
> not without overheads.

Slightly?

For basic blocks you are talking about having to mark thousands of
objects (which includes the root somewhere in it) versus having to
start at just the root.  That's a *lot* of page/cache line touching
for no good reason.

>
> >> I don't see that allocation patterns that improve locality are
> >> necessarily forbidden by GC machinery.  Maybe they're hard to model in
> >> our current machinery (I don't know)
>
> > I am talking specifically about gcc's implementation and use of GC.
>
> So is it indeed true that current GGC machinery prevents allocation
> patterns that improve locality?
Yes

>   And, if so, is this harder to fix
> than maintaining non-GC-controlled roots for all cases in which we'd
> like to have better-locality allocation patterns and explicit death
> marking than what the default allocation pattern would provide?
These are orthogonal problems, not the same problem.

The fact that you can improve GC locality doesn't mean you should GC
everything.
>
> I.e., instead of:
>
>   fastobjcollection = alloc (bigenough);
>   ...
>   obj = new_obj_in_collection (fastobjcollection, size);
>   ggc_add_root (obj, typedescriptor);
>   ...
>   ggc_remove_root (obj);
>   remove_obj_from_collection (obj);
>   ...
>   free (fastobjcollection);
>
> is there any reason we can't have:
>
>   fastobjcollection = ggc_alloc (bigenough);
>   ggc_add_root (fastobjcollection, objcollectiondescriptor);
>   ...
>   obj = new_obj_in_collection (fastobjcollection, size);
>   ...
>   remove_obj_from_collection (obj);
>   ...
>   ggc_free (fastobjcollection);
>

GGC page tracks large pages explicitly, and does not expect there to
be an exceptionally large number of them.

Because it does not compact memory, doing the second will cause you a
large amount of gc heap fragmentation
Not to mention it would mean the GC would still have to track objects
we don't need it to, unless you are going to extend gengtype and
friends, so you can specify which part you want to be a root, and
which parts you just want to never die.

> In other words, what does moving the objects out of GCable memory
> really buy us?

Less overhead + less gc heap fragmentation + less objects for gc to
mark marking= compiler uses less memory and is faster.

There is no point in having a 30% solution here when it's going to be
just as much work as a 100% one.

Re: [patch] Move loop structures to gc memory

[Alexandre Oliva]

On May 17, 2007, Mark Mitchell <mark@codesourcery.com> wrote:

>   ggc_register_root (&p->t);

The reason I didn't propose this simpler-to-use idiom, and rather
proposed the GC-root data structure to be allocated by the caller, is
that your simpler construct would likely involve either additional
memory allocations, whose overhead we're trying to avoid, or a more
complex data structure, which also comes with its overheads in terms
of memory and computation.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [patch] Move loop structures to gc memory

[Alexandre Oliva]

On May 17, 2007, "Daniel Berlin" <dberlin@dberlin.org> wrote:

> On 5/16/07, Alexandre Oliva <aoliva@redhat.com> wrote:

>> I'm not sure this follows.  If you have to scan it for pointers to
>> live objects, then you have to track it either as a regular object or
>> as a root.  Tracking it as a root might be slightly cheaper, but it's
>> not without overheads.

> Slightly?

> For basic blocks you are talking about having to mark thousands of
> objects (which includes the root somewhere in it) versus having to
> start at just the root.

It seems to me like you're comparing apples and oranges, so I'll
assume instead that I don't understand what you're getting at.

What I was trying to compare is the overheads of maintaining it as
either a GC root out of GC memory, that requires some explicit or
internal-to-GC data structure to keep it as part of the set of dynamic
GC roots, and some internal-to-memory-mgmt data structure to keep it
as part of the non-GC memory pool, or a regular GC-able object, which
requires something to keep it from being collected (perhaps some
gc_dynamic_roots linked list) and some internal-to-GC data structure
to keep it as part of the GC memory pool.

Both require similar walking functions, so this doesn't make much of a
difference.  I don't see that the overheads in terms of memory are
significantly different for the two cases.  If you get to run a pass
of garbage collection, you're going to walk all live objects,
including all roots, just the same, so I don't see that this pushes
the balance one way or another either.

So I still don't see that the issue is whether the object is a regular
GC object or a GC root.  The issue is whether you can alleviate the
overhead of the memory allocator.  And there are ways to do this, for
which it doesn't matter at all whether the involved objects are GC
roots or non-roots.

What overhead do you see in maintaining the object [pool] as a regular
GC object, that is not present in identical or similar form when it's
a GC root?

>> So is it indeed true that current GGC machinery prevents allocation
>> patterns that improve locality?

> Yes

I don't see what stops you from constructing say an obstack in GC
memory.  What are the obstacles you see?

I now see that using alloca is not a viable option, but you don't want
to allocate big object pools with alloca anyway, which is what I
thought the locality issue was about.

> The fact that you can improve GC locality doesn't mean you should GC
> everything.

"GC everything" may have many different meanings, and I can't tell
which one you mean.

> Because it does not compact memory, doing the second will cause you a
> large amount of gc heap fragmentation

Got it.  A limitation of the internal GGC memory allocator.  Probably
not trivial to fix.

> Not to mention it would mean the GC would still have to track objects
> we don't need it to,

Rather than tracking them as roots, which you seem to regard as
infinitely cheaper but I'm yet to understand why.

> unless you are going to extend gengtype and
> friends, so you can specify which part you want to be a root,

That was the point of the explicit typedescriptor, which presumably
comes with a walk function that specifies how to walk the object.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [patch] Move loop structures to gc memory

[Zdenek Dvorak]

Hello,

> Except that you lose all the benefits of it *not* being in GC.
> 
> As a concrete example:
> 
> Our basic blocks were pool allocated using alloc_pool's.
> Because they started pointing to GC'd structures directly (in order to
> simplify things), we switched them to be gc alloced.
> 
> We lost about 1-2% compile time from doing this (see the archives),
> because alloc pools are contiguous in memory, and our gc was just
> handing out random free memory that happened to be around the same
> size.
> 
> Things that have a very well defined lifetime (which are basic blocks
> do, for example), should not have to be in GC memory simply because
> they point to GC objects.
> 
> You can argue that "well, it doesn't really hurt most of the time",
> "we could improve the GC to get better locality" etc, but it doesn't
> change that basic premise.  No one in this thread has yet given a good
> reason we should have to GC things that we don't want to GC, just to
> get things they point to GC'd without really ugly hacks/workarounds.
> 
> The only reason i've seen is "well, it's hard".
> 
> Speed wise, profiles of the GC have never shown the actual root list
> walking to be slow, only the actual mark lookups and sets.  Adding
> dynamic roots would make the root list walking slightly slower, but if
> we have *less* things in GC overall, we will do less mark setting,
> which is where most of GC time goes.
> So it should be a win overall.

something like the patch below?  It allows you:

-- to specify a custom marking routine for a particular type, that is
   called instead of the one provided by garbage collector.  This
   enables the objects of this type not to be allocated by gc, and
   still survive ggc_collect even if gc collected things point to
   them
-- adds dynamic roots to ggc-common
-- implements a particular instance of considering all objects allocated
   in an alloc pool to be roots
-- and applies it to make basic blocks pool allocated

I guess this covers most of the profitable cases (basic blocks, edges,
loop structures), but it is easy to extend for other modes of
allocation.  For simplicity, the patch allocates all basic blocks from
a single pool; it might be better to use per-function pools instead
(that would however need some more changes, in particular the way
omp code moves basic blocks between functions would break).

Of course, the patch is not quite finished (in particular, I am fairly
sure it breaks pch), but I would like to know whether we are both
thinking about the same thing, or if you imagine something different.

Zdenek

Index: doc/gty.texi
===================================================================
*** doc/gty.texi	(revision 124785)
--- doc/gty.texi	(working copy)
*************** reachable. This routine should not chang
*** 292,297 ****
--- 292,304 ----
  routine. Its only argument is a pointer to the just marked (const)
  structure or union.
  
+ @findex custom_mark
+ @item custom_mark ("@var{marking-routine-name}")
+ 
+ If provided for a structure or union type, the given
+ @var{marking-routine-name} (between double-quotes) is the name of a
+ routine called to mark the object instead of ggc_set_mark.
+ 
  @findex maybe_undef
  @item maybe_undef
  
Index: gengtype.c
===================================================================
*** gengtype.c	(revision 124785)
--- gengtype.c	(working copy)
*************** walk_type (type_p t, struct walk_type_da
*** 1914,1919 ****
--- 1914,1921 ----
        desc = oo->info;
      else if (strcmp (oo->name, "mark_hook") == 0)
        ;
+     else if (strcmp (oo->name, "custom_mark") == 0)
+       ;
      else if (strcmp (oo->name, "nested_ptr") == 0)
        nested_ptr_d = (const struct nested_ptr_data *) oo->info;
      else if (strcmp (oo->name, "dot") == 0)
*************** write_func_for_structure (type_p orig_s,
*** 2416,2421 ****
--- 2418,2424 ----
    const char *chain_next = NULL;
    const char *chain_prev = NULL;
    const char *mark_hook_name = NULL;
+   const char *marker_routine = wtd->marker_routine;
    options_p opt;
    struct walk_type_data d;
  
*************** write_func_for_structure (type_p orig_s,
*** 2435,2440 ****
--- 2438,2447 ----
        chain_prev = opt->info;
      else if (strcmp (opt->name, "mark_hook") == 0)
        mark_hook_name = opt->info;
+     else if (strcmp (opt->name, "custom_mark") == 0
+ 	     /* FIXME -- this will break pch.  */
+ 	     && !wtd->param_prefix)
+       marker_routine = opt->info;
  
    if (chain_prev != NULL && chain_next == NULL)
      error_at_line (&s->u.s.line, "chain_prev without chain_next");
*************** write_func_for_structure (type_p orig_s,
*** 2471,2477 ****
  	     s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
    if (chain_next == NULL)
      {
!       oprintf (d.of, "  if (%s (x", wtd->marker_routine);
        if (wtd->param_prefix)
  	{
  	  oprintf (d.of, ", x, gt_%s_", wtd->param_prefix);
--- 2478,2484 ----
  	     s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
    if (chain_next == NULL)
      {
!       oprintf (d.of, "  if (%s (x", marker_routine);
        if (wtd->param_prefix)
  	{
  	  oprintf (d.of, ", x, gt_%s_", wtd->param_prefix);
*************** write_func_for_structure (type_p orig_s,
*** 2482,2488 ****
      }
    else
      {
!       oprintf (d.of, "  while (%s (xlimit", wtd->marker_routine);
        if (wtd->param_prefix)
  	{
  	  oprintf (d.of, ", xlimit, gt_%s_", wtd->param_prefix);
--- 2489,2495 ----
      }
    else
      {
!       oprintf (d.of, "  while (%s (xlimit", marker_routine);
        if (wtd->param_prefix)
  	{
  	  oprintf (d.of, ", xlimit, gt_%s_", wtd->param_prefix);
*************** write_func_for_structure (type_p orig_s,
*** 2514,2521 ****
  	  oprintf (d.of, ");\n");
  	  oprintf (d.of, "        if (xprev == NULL) break;\n");
  	  oprintf (d.of, "        x = xprev;\n");
! 	  oprintf (d.of, "        (void) %s (xprev",
! 		   wtd->marker_routine);
  	  if (wtd->param_prefix)
  	    {
  	      oprintf (d.of, ", xprev, gt_%s_", wtd->param_prefix);
--- 2521,2527 ----
  	  oprintf (d.of, ");\n");
  	  oprintf (d.of, "        if (xprev == NULL) break;\n");
  	  oprintf (d.of, "        x = xprev;\n");
! 	  oprintf (d.of, "        (void) %s (xprev", marker_routine);
  	  if (wtd->param_prefix)
  	    {
  	      oprintf (d.of, ", xprev, gt_%s_", wtd->param_prefix);
Index: cfg.c
===================================================================
*** cfg.c	(revision 124785)
--- cfg.c	(working copy)
*************** static void free_edge (edge);
*** 76,92 ****
  \f
  #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
  
  /* Called once at initialization time.  */
  
  void
  init_flow (void)
  {
    if (!cfun->cfg)
      cfun->cfg = ggc_alloc_cleared (sizeof (struct control_flow_graph));
    n_edges = 0;
!   ENTRY_BLOCK_PTR = ggc_alloc_cleared (sizeof (struct basic_block_def));
    ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
!   EXIT_BLOCK_PTR = ggc_alloc_cleared (sizeof (struct basic_block_def));
    EXIT_BLOCK_PTR->index = EXIT_BLOCK;
    ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
    EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
--- 76,110 ----
  \f
  #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
  
+ /* Pool for bb allocation.  */
+ 
+ static alloc_pool bb_pool;
+ 
+ /* Description of the roots in this alloc pool.  */
+ 
+ static struct alloc_pool_gc_description gc_bb_pool;
+ 
  /* Called once at initialization time.  */
  
  void
  init_flow (void)
  {
+   if (!bb_pool)
+     {
+       bb_pool = create_alloc_pool ("basic blocks",
+ 				   sizeof (struct basic_block_def), 100);
+       gc_bb_pool.pool = bb_pool;
+       gc_bb_pool.mark = gt_ggc_mx_basic_block_def;
+       register_dynamic_root (alloc_pool_gc_root, &gc_bb_pool);
+     }
+ 
    if (!cfun->cfg)
      cfun->cfg = ggc_alloc_cleared (sizeof (struct control_flow_graph));
+ 
    n_edges = 0;
!   ENTRY_BLOCK_PTR = alloc_block ();
    ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
!   EXIT_BLOCK_PTR = alloc_block ();
    EXIT_BLOCK_PTR->index = EXIT_BLOCK;
    ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
    EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
*************** clear_edges (void)
*** 132,139 ****
  basic_block
  alloc_block (void)
  {
!   basic_block bb;
!   bb = ggc_alloc_cleared (sizeof (*bb));
    return bb;
  }
  
--- 150,157 ----
  basic_block
  alloc_block (void)
  {
!   basic_block bb = pool_alloc (bb_pool);
!   memset (bb, 0, sizeof (*bb));
    return bb;
  }
  
*************** expunge_block (basic_block b)
*** 191,201 ****
    unlink_block (b);
    SET_BASIC_BLOCK (b->index, NULL);
    n_basic_blocks--;
!   /* We should be able to ggc_free here, but we are not.
!      The dead SSA_NAMES are left pointing to dead statements that are pointing
!      to dead basic blocks making garbage collector to die.
!      We should be able to release all dead SSA_NAMES and at the same time we should
!      clear out BB pointer of dead statements consistently.  */
  }
  \f
  /* Connect E to E->src.  */
--- 209,215 ----
    unlink_block (b);
    SET_BASIC_BLOCK (b->index, NULL);
    n_basic_blocks--;
!   pool_free (bb_pool, b);
  }
  \f
  /* Connect E to E->src.  */
Index: alloc-pool.c
===================================================================
*** alloc-pool.c	(revision 124785)
--- alloc-pool.c	(working copy)
*************** Software Foundation, 51 Franklin Street,
*** 24,29 ****
--- 24,31 ----
  #include "system.h"
  #include "alloc-pool.h"
  #include "hashtab.h"
+ #include "pointer-set.h"
+ #include "ggc.h"
  
  #define align_eight(x) (((x+7) >> 3) << 3)
  
*************** create_alloc_pool (const char *name, siz
*** 180,185 ****
--- 182,226 ----
    return (pool);
  }
  
+ /* Mark elements of pool described in struct alloc_pool_gc_description
+    as gc roots.  */
+ 
+ void
+ alloc_pool_gc_root (void *data)
+ {
+   struct alloc_pool_gc_description *desc = data;
+   struct pointer_set_t *free_elts = pointer_set_create ();
+   alloc_pool_list elt, block_header;
+   char *block;
+   alloc_pool pool = desc->pool;
+   unsigned i;
+ 
+   /* Find the allocated elements of the pool.  This is somewhat tricky, as
+      we do not track those, but it suffices to traverse all elements of the
+      pool and ignore the free ones.  */
+   for (elt = pool->free_list; elt != NULL; elt = elt->next)
+     pointer_set_insert (free_elts, elt);
+ 
+   for (block_header = pool->block_list;
+        block_header != NULL;
+        block_header = block_header->next)
+     {
+       block = (char *) block_header;
+       block += align_eight (sizeof (struct alloc_pool_list_def));
+ 
+       for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size)
+ 	{
+ 	  elt = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
+ 	  if (pointer_set_contains (free_elts, elt))
+ 	    continue;
+ 
+ 	  ggc_mark_dynamic_root (desc->mark, (void *) elt);
+ 	}
+     }
+ 
+   pointer_set_destroy (free_elts);
+ }
+ 
  /* Free all memory allocated for the given memory pool.  */
  void
  free_alloc_pool (alloc_pool pool)
Index: alloc-pool.h
===================================================================
*** alloc-pool.h	(revision 124785)
--- alloc-pool.h	(working copy)
*************** typedef struct alloc_pool_def
*** 47,56 ****
--- 47,69 ----
  }
   *alloc_pool;
  
+ /* Description of the alloc pool for marking gc roots.  */
+  
+ struct alloc_pool_gc_description
+ {
+   /* The pool.  */
+   alloc_pool pool;
+   
+   /* The function used to traverse the elements of the pool.  */
+   void (*mark) (void *);
+ };
+  
  extern alloc_pool create_alloc_pool (const char *, size_t, size_t);
  extern void free_alloc_pool (alloc_pool);
  extern void free_alloc_pool_if_empty (alloc_pool *);
  extern void *pool_alloc (alloc_pool);
  extern void pool_free (alloc_pool, void *);
  extern void dump_alloc_pool_statistics (void);
+ extern void alloc_pool_gc_root (void *);
+ 
  #endif
Index: ggc.h
===================================================================
*** ggc.h	(revision 124785)
--- ggc.h	(working copy)
*************** extern void ggc_mark_stringpool	(void);
*** 125,130 ****
--- 125,149 ----
  
  extern void ggc_mark_roots (void);
  
+ /* Dynamic root management.  */
+ 
+ struct dynamic_root
+ {
+   /* Double linked list of roots.  */
+   struct dynamic_root *prev, *next;
+ 
+   /* Function called to mark the root.  */
+   void (*mark) (void *);
+ 
+   /* Data of the root.  */
+   void *data;
+ };
+ 
+ int ggc_set_dynamic_root_mark (const void *);
+ void ggc_mark_dynamic_root (void (*) (void *), void *);
+ struct dynamic_root *register_dynamic_root (void (*) (void *), void *);
+ void unregister_dynamic_root (struct dynamic_root *);
+ 
  /* Save and restore the string pool entries for PCH.  */
  
  extern void gt_pch_save_stringpool (void);
Index: ggc-common.c
===================================================================
*** ggc-common.c	(revision 124785)
--- ggc-common.c	(working copy)
*************** bool ggc_force_collect;
*** 67,72 ****
--- 67,76 ----
  /* Statistics about the allocation.  */
  static ggc_statistics *ggc_stats;
  
+ /* Dynamic roots.  */
+ 
+ static struct dynamic_root *dynamic_roots;
+ 
  struct traversal_state;
  
  static int ggc_htab_delete (void **, void *);
*************** ggc_htab_delete (void **slot, void *info
*** 97,102 ****
--- 101,166 ----
    return 1;
  }
  
+ /* Mark function for objects that serve as dynamic ggc roots.  Returns
+    1 if it is called because of invocation of the gc traversal function
+    from ggc_mark_dynamic_root, and 0 otherwise.  */
+ 
+ static bool called_from_ggc_mark_dynamic_root;
+ int
+ ggc_set_dynamic_root_mark (const void *p ATTRIBUTE_UNUSED)
+ {
+   if (called_from_ggc_mark_dynamic_root)
+     {
+       called_from_ggc_mark_dynamic_root = false;
+       return 1;
+     }
+ 
+   return 0;
+ }
+ 
+ /* Marks dynamic root ROOT, and traverse it using MARK_FUNCTION.  */
+ 
+ void
+ ggc_mark_dynamic_root (void (*mark_function) (void *), void *root)
+ {
+   called_from_ggc_mark_dynamic_root = true;
+   mark_function (root);
+   called_from_ggc_mark_dynamic_root = false;
+ }
+ 
+ /* Registers and returns a dynamic root with marking function MARK.  DATA are
+    passed to MARK when it is run.  */
+ 
+ struct dynamic_root *
+ register_dynamic_root (void (*mark) (void *), void *data)
+ {
+   struct dynamic_root *dr = XNEW (struct dynamic_root);
+ 
+   dr->mark = mark;
+   dr->data = data;
+   dr->next = dynamic_roots;
+   dr->prev = NULL;
+   if (dr->next)
+     dr->next->prev = dr;
+   dynamic_roots = dr;
+ 
+   return dr;
+ }
+ 
+ /* Unregisters and releases a dynamic root DR.  */
+ 
+ void
+ unregister_dynamic_root (struct dynamic_root *dr)
+ {
+   if (dr->next)
+     dr->next->prev = dr->prev;
+ 
+   if (dr->prev)
+     dr->prev->next = dr->next;
+   else
+     dynamic_roots = dr->next;
+ }
+ 
  /* Iterate through all registered roots and mark each element.  */
  
  void
*************** ggc_mark_roots (void)
*** 106,111 ****
--- 170,176 ----
    const struct ggc_root_tab *rti;
    const struct ggc_cache_tab *const *ct;
    const struct ggc_cache_tab *cti;
+   struct dynamic_root *dr;
    size_t i;
  
    for (rt = gt_ggc_deletable_rtab; *rt; rt++)
*************** ggc_mark_roots (void)
*** 117,122 ****
--- 182,190 ----
        for (i = 0; i < rti->nelt; i++)
  	(*rti->cb)(*(void **)((char *)rti->base + rti->stride * i));
  
+   for (dr = dynamic_roots; dr; dr = dr->next)
+     dr->mark (dr->data);
+ 
    ggc_mark_stringpool ();
  
    /* Now scan all hash tables that have objects which are to be deleted if
Index: Makefile.in
===================================================================
*** Makefile.in	(revision 124785)
--- Makefile.in	(working copy)
*************** value-prof.o : value-prof.c $(CONFIG_H) 
*** 2510,2516 ****
  loop-doloop.o : loop-doloop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
     $(RTL_H) $(FLAGS_H) $(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) $(TM_P_H) \
     toplev.h $(CFGLOOP_H) output.h $(PARAMS_H) $(TARGET_H)
! alloc-pool.o : alloc-pool.c $(CONFIG_H) $(SYSTEM_H) alloc-pool.h $(HASHTAB_H)
  flow.o : flow.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
     $(TREE_H) $(FLAGS_H) insn-config.h $(BASIC_BLOCK_H) $(REGS_H) \
     hard-reg-set.h output.h toplev.h $(RECOG_H) $(FUNCTION_H) except.h \
--- 2510,2517 ----
  loop-doloop.o : loop-doloop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
     $(RTL_H) $(FLAGS_H) $(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) $(TM_P_H) \
     toplev.h $(CFGLOOP_H) output.h $(PARAMS_H) $(TARGET_H)
! alloc-pool.o : alloc-pool.c $(CONFIG_H) $(SYSTEM_H) alloc-pool.h $(HASHTAB_H) \
!    pointer-set.h $(GGC_H)
  flow.o : flow.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
     $(TREE_H) $(FLAGS_H) insn-config.h $(BASIC_BLOCK_H) $(REGS_H) \
     hard-reg-set.h output.h toplev.h $(RECOG_H) $(FUNCTION_H) except.h \
Index: basic-block.h
===================================================================
*** basic-block.h	(revision 124786)
--- basic-block.h	(working copy)
*************** struct rtl_bb_info;
*** 211,217 ****
     basic blocks.  */
  
  /* Basic block information indexed by block number.  */
! struct basic_block_def GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb")))
  {
    /* The edges into and out of the block.  */
    VEC(edge,gc) *preds;
--- 211,217 ----
     basic blocks.  */
  
  /* Basic block information indexed by block number.  */
! struct basic_block_def GTY((custom_mark ("ggc_set_dynamic_root_mark")))
  {
    /* The edges into and out of the block.  */
    VEC(edge,gc) *preds;

Re: [patch] Move loop structures to gc memory

[Ian Lance Taylor]

Alexandre Oliva <aoliva@redhat.com> writes:

> What I was trying to compare is the overheads of maintaining it as
> either a GC root out of GC memory, that requires some explicit or
> internal-to-GC data structure to keep it as part of the set of dynamic
> GC roots, and some internal-to-memory-mgmt data structure to keep it
> as part of the non-GC memory pool, or a regular GC-able object, which
> requires something to keep it from being collected (perhaps some
> gc_dynamic_roots linked list) and some internal-to-GC data structure
> to keep it as part of the GC memory pool.
> 
> Both require similar walking functions, so this doesn't make much of a
> difference.  I don't see that the overheads in terms of memory are
> significantly different for the two cases.  If you get to run a pass
> of garbage collection, you're going to walk all live objects,
> including all roots, just the same, so I don't see that this pushes
> the balance one way or another either.

1) It is cheaper to call pool_alloc than it is to call ggc_alloc.
   *_alloc will be called far more often than the walking function.
   pool_alloc will provide contiguous memory which will make
   traversing the basic blocks--a common operation in gcc--cheaper.

2) When you do walk, the walking function is going to be cheaper at
   runtime if the structures being walked are allocated contiguously.


> I don't see what stops you from constructing say an obstack in GC
> memory.  What are the obstacles you see?

The GC code needs to know the complete type of every object you put
into GC, so I think this can only work for obstacks that only hold one
type of object.  And obstacks routinely have unused data in the middle
of the obstack, because it is cheaper to leave it there than to dig it
out; how will the GC walk know the data is free?


I don't really know where you're going with this.

The dynamic registration of walking functions you proposed does seem
like a positive step to me.  It seems that we could use that
functionality to move basic blocks out of GC memory and keep the loop
structures out of GC memory.

Ian

Re: [patch] Move loop structures to gc memory

[Mike Stump]

On May 16, 2007, at 5:47 PM, Ian Lance Taylor wrote:
>> I don't follow the logic.  Why couldn't pools be in GC memory, again,
>> so as to reap the benefits without complicating the logic?
>
> Putting something in GC memory unnecessarily is inevitably slower than
> not putting it in GC memory, if only because GC requires overhead to
> track objects.

But, the cost can be as cheap as:

	if (ptr >= end_ptr) grow(&ptr_base, &ptr);
	*ptr = data;
	++ptr;

	play with data;
		
	--ptr = 0;

or roughly 10 machine instruction.  I don't consider that very costly  
in the grand scheme of things.  The above is enough to have at least  
one pointer in GCed memory, which is all that is necessary, not that  
all pointers are in GCed memory.

Re: [patch] Move loop structures to gc memory

[Daniel Berlin]

On 5/17/07, Mike Stump <mrs@apple.com> wrote:
> On May 16, 2007, at 5:47 PM, Ian Lance Taylor wrote:
> >> I don't follow the logic.  Why couldn't pools be in GC memory, again,
> >> so as to reap the benefits without complicating the logic?
> >
> > Putting something in GC memory unnecessarily is inevitably slower than
> > not putting it in GC memory, if only because GC requires overhead to
> > track objects.
>
> But, the cost can be as cheap as:
>
>         if (ptr >= end_ptr) grow(&ptr_base, &ptr);
>         *ptr = data;
>         ++ptr;
>
>         play with data;
>
>         --ptr = 0;
>
> or roughly 10 machine instruction.  I don't consider that very costly
> in the grand scheme of things.  The above is enough to have at least
> one pointer in GCed memory, which is all that is necessary, not that
> all pointers are in GCed memory.
>
It's not that cheap right now.
Unless you are going to make it this cheap, can we please stop
pretending it's this cheap?

When we need a new object in ggc-page, we currently try to see if we
can fit one on the last page that was left around, using hints left
from previous allocations.  Even when that works, we may end up
scanning the entire in-use object bitmap for that page to find the
place of the free object.
When that fails, and we go to allocate a new page, we look at the
entire list of free pages to see if there is one we can use.
If *that* fails, then we finally allocate a new page (or group of pages).

For ggc-zone, it has explicit large page support, with the caveat that
large pages live or die as a single object (regardless of how many
objects they are broken up into).  ggc-zone also does more or less
like you've suggested, and 90+% of allocations fall into that.

However, all of this is kinda irrelevant, IMHO.
It's simply not hard to implement any of these schemes than it would
be to make roots dynamic.
Why should we do something that puts more things in GC memory,   when
it's just as easy code-wise, and faster in reality, to do what seems
to be the right thing (allocate them however the hell we want, and
just say, 'hey, there are some gc roots over here').

Heck, zdenek already worked up a patch.

Re: [patch] Move loop structures to gc memory

[Daniel Berlin]

On 5/17/07, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> Hello,
>
> > The only reason i've seen is "well, it's hard".
> >
> > Speed wise, profiles of the GC have never shown the actual root list
> > walking to be slow, only the actual mark lookups and sets.  Adding
> > dynamic roots would make the root list walking slightly slower, but if
> > we have *less* things in GC overall, we will do less mark setting,
> > which is where most of GC time goes.
> > So it should be a win overall.
>
> something like the patch below?  It allows you:
>
> -- to specify a custom marking routine for a particular type, that is
>    called instead of the one provided by garbage collector.  This
>    enables the objects of this type not to be allocated by gc, and
>    still survive ggc_collect even if gc collected things point to
>    them
> -- adds dynamic roots to ggc-common
> -- implements a particular instance of considering all objects allocated
>    in an alloc pool to be roots
> -- and applies it to make basic blocks pool allocated
>
> I guess this covers most of the profitable cases (basic blocks, edges,
> loop structures), but it is easy to extend for other modes of
> allocation.  For simplicity, the patch allocates all basic blocks from
> a single pool; it might be better to use per-function pools instead
> (that would however need some more changes, in particular the way
> omp code moves basic blocks between functions would break).
>
> Of course, the patch is not quite finished (in particular, I am fairly
> sure it breaks pch), but I would like to know whether we are both
> thinking about the same thing, or if you imagine something different.
>
No, this is exactly what i'm thinking about.

You may want to change the subject line so that it gets noticed by
people not reading this hellhole of a thread :)

Re: [patch] Move loop structures to gc memory

[Richard Guenther]

On 5/17/07, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> Hello,
>
> > Except that you lose all the benefits of it *not* being in GC.
> >
> > As a concrete example:
> >
> > Our basic blocks were pool allocated using alloc_pool's.
> > Because they started pointing to GC'd structures directly (in order to
> > simplify things), we switched them to be gc alloced.
> >
> > We lost about 1-2% compile time from doing this (see the archives),
> > because alloc pools are contiguous in memory, and our gc was just
> > handing out random free memory that happened to be around the same
> > size.
> >
> > Things that have a very well defined lifetime (which are basic blocks
> > do, for example), should not have to be in GC memory simply because
> > they point to GC objects.
> >
> > You can argue that "well, it doesn't really hurt most of the time",
> > "we could improve the GC to get better locality" etc, but it doesn't
> > change that basic premise.  No one in this thread has yet given a good
> > reason we should have to GC things that we don't want to GC, just to
> > get things they point to GC'd without really ugly hacks/workarounds.
> >
> > The only reason i've seen is "well, it's hard".
> >
> > Speed wise, profiles of the GC have never shown the actual root list
> > walking to be slow, only the actual mark lookups and sets.  Adding
> > dynamic roots would make the root list walking slightly slower, but if
> > we have *less* things in GC overall, we will do less mark setting,
> > which is where most of GC time goes.
> > So it should be a win overall.
>
> something like the patch below?  It allows you:
>
> -- to specify a custom marking routine for a particular type, that is
>    called instead of the one provided by garbage collector.  This
>    enables the objects of this type not to be allocated by gc, and
>    still survive ggc_collect even if gc collected things point to
>    them
> -- adds dynamic roots to ggc-common
> -- implements a particular instance of considering all objects allocated
>    in an alloc pool to be roots
> -- and applies it to make basic blocks pool allocated
>
> I guess this covers most of the profitable cases (basic blocks, edges,
> loop structures), but it is easy to extend for other modes of
> allocation.  For simplicity, the patch allocates all basic blocks from
> a single pool; it might be better to use per-function pools instead
> (that would however need some more changes, in particular the way
> omp code moves basic blocks between functions would break).
>
> Of course, the patch is not quite finished (in particular, I am fairly
> sure it breaks pch), but I would like to know whether we are both
> thinking about the same thing, or if you imagine something different.

Heh, I like this.  PCH should be the last thing to care about.

Richard.

Re: [patch] Move loop structures to gc memory

[Alexandre Oliva]

On May 17, 2007, Ian Lance Taylor <iant@google.com> wrote:

> 1) It is cheaper to call pool_alloc than it is to call ggc_alloc.
>    *_alloc will be called far more often than the walking function.
>    pool_alloc will provide contiguous memory which will make
>    traversing the basic blocks--a common operation in gcc--cheaper.

> 2) When you do walk, the walking function is going to be cheaper at
>    runtime if the structures being walked are allocated contiguously.

Which once again brings to the point that the issue is not so much
whether memory is in the GC memory pool or not, but rather to how it's
allocated.

If we could allocate object pools in GC memory such that they are
contiguous and a single allocation is involved, then ggc_alloc might
still be more expensive than pool_alloc, and so much so that the need
to register and deregister the object as a root wouldn't make up for
it.  It just so happens that the GGC design doesn't make it exactly
trivial to manage pools of objects.

The other take-out point is that ggc_alloc seems to suck rocks, so
perhaps improving it should have much higher priority than moving
stuff out of GC memory, since this would then benefit everything else
*while* accomplishing the goal of speeding up manual memory
management, such that the issue of whether or not the object is in GC
memory (a mere consequence of the allocation function was selected to
allocate it) becomes less relevant.

>> I don't see what stops you from constructing say an obstack in GC
>> memory.  What are the obstacles you see?

> The GC code needs to know the complete type of every object you put
> into GC,

For PCH, yes.  For GC only, all we need is the ability to walk such
objects and mark those referenced from it.  This might require some
additional meta-information, but it's far from unworkable.

Of course just using an obstack or some such is trivial in comparison,
but when you take into account that pointing to GC objects requires
you to explicitly register and deregister every pointer to GC objects
stored in the obstack, you realize that this is the same additional
meta-information mentioned in the previous paragraph.

How to express it is "just a matter of programming" ;-)

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [patch] Move loop structures to gc memory

[Alexandre Oliva]

On May 17, 2007, "Daniel Berlin" <dberlin@dberlin.org> wrote:

> On 5/17/07, Mike Stump <mrs@apple.com> wrote:
>> On May 16, 2007, at 5:47 PM, Ian Lance Taylor wrote:
>> > Putting something in GC memory unnecessarily is inevitably slower than
>> > not putting it in GC memory, if only because GC requires overhead to
>> > track objects.

>> But, the cost can be as cheap as:

> It's not that cheap right now.
> Unless you are going to make it this cheap, can we please stop
> pretending it's this cheap?

This argument seems backwards.

If our GC memory allocator is slow, this affects *every* call of
ggc_alloc.

Moving objects out of the GC pool because ggc_alloc is slow is a
local, limited fix, that merely papers over the real problem.

It seems quite obvious to me that speeding up ggc_alloc such that it's
on par with other, faster allocators, would achieve not only the
intended benefit of moving objects out of GC (except for alloca(),
which is truly unbeatable), but also speed everything else up.

Surely it is possible to allocate memory faster, since other
allocators do it, and it's not like doing so in a GC-enabling way
requires significant overhead.

Then why paper over the problem that slows all of GCC down?

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [patch] Move loop structures to gc memory

[Zdenek Dvorak]

Hello,

> > On 5/17/07, Mike Stump <mrs@apple.com> wrote:
> >> On May 16, 2007, at 5:47 PM, Ian Lance Taylor wrote:
> >> > Putting something in GC memory unnecessarily is inevitably slower than
> >> > not putting it in GC memory, if only because GC requires overhead to
> >> > track objects.
> 
> >> But, the cost can be as cheap as:
> 
> > It's not that cheap right now.
> > Unless you are going to make it this cheap, can we please stop
> > pretending it's this cheap?
> 
> This argument seems backwards.
> 
> If our GC memory allocator is slow, this affects *every* call of
> ggc_alloc.
> 
> Moving objects out of the GC pool because ggc_alloc is slow is a
> local, limited fix, that merely papers over the real problem.

no, it is a proper fix -- it makes us avoid using GC for purposes for
that it is not suitable.

Of course, making GC faster is not a bad idea, but using GC for objects
for that you know exactly the lifetime and the expected usage pattern
at best wastes this extra information you have.

Zdenek

Re: [patch] Move loop structures to gc memory

[Daniel Jacobowitz]

On Thu, May 17, 2007 at 04:55:40PM -0300, Alexandre Oliva wrote:
> Surely it is possible to allocate memory faster, since other
> allocators do it, and it's not like doing so in a GC-enabling way
> requires significant overhead.

I invite you.  It took me a month of work to get the zone allocator as
fast as page; maybe someone else could make it faster.

-- 
Daniel Jacobowitz
CodeSourcery

Re: [patch] Move loop structures to gc memory

[Alexandre Oliva]

On May 17, 2007, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:

> no, it is a proper fix -- it makes us avoid using GC for purposes for
> that it is not suitable.

Why is it not suitable?

So far the only justification presented is that ggc_alloc is slower.
I'm not aware of any fundamental reason why ggc_alloc must be slower
than other memory allocators (other than alloca).

If we could make ggc_alloc faster, would it still be unsuitable?

> using GC for objects for that you know exactly the lifetime and the
> expected usage pattern at best wastes this extra information you
> have.

You're not taking into account the need for tracking the pointers
inside these very objects into objects in GC memory.  It's not at all
obvious that, after adding in this extra information, you're still
saving anything.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [patch] Move loop structures to gc memory

[Daniel Berlin]

On 5/18/07, Alexandre Oliva <aoliva@redhat.com> wrote:
> On May 17, 2007, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
>
> > no, it is a proper fix -- it makes us avoid using GC for purposes for
> > that it is not suitable.
>
> Why is it not suitable?
Because it's garbage collected memory for something that doesn't need
to, care about, or will ever be, garbage collected?

>
> So far the only justification presented is that ggc_alloc is slower.
> I'm not aware of any fundamental reason why ggc_alloc must be slower
> than other memory allocators (other than alloca).

Well, first, have fun producing some patches to make it that way. I
know Dan Jacobowitz spend > 1 month working on this.
>
Second the main justification is that the memory doesn't need to be
garbage collected, it just has some roots in it.

Why should things that don't need to be garbage collected, be in
garbage collected memory?
In other words, why would we put it there just because we could make
it possible to be there?
It doesn't make anything *better*, but it sure (currently, and for the
forseeable future) makes things worse!
> If we could make ggc_alloc faster, would it still be unsuitable?


>
> > using GC for objects for that you know exactly the lifetime and the
> > expected usage pattern at best wastes this extra information you
> > have.
>
> You're not taking into account the need for tracking the pointers
> inside these very objects into objects in GC memory.  It's not at all
> obvious that, after adding in this extra information, you're still
> saving anything.
>
We'll just have to agree to disagree until numbers are produced, I guess.

Re: [patch] Move loop structures to gc memory

[Alexandre Oliva]

On May 18, 2007, "Daniel Berlin" <dberlin@dberlin.org> wrote:

> On 5/18/07, Alexandre Oliva <aoliva@redhat.com> wrote:

>> Why is it not suitable?

> Because it's garbage collected memory for something that doesn't need
> to, care about, or will ever be, garbage collected?

> the memory doesn't need to be garbage collected, it just has some
> roots in it.

Do you not realize the contradiction between your two statements
above?

It evidently cares about garbage collection, because it points to
GC-able objects.

> Why should things that don't need to be garbage collected, be in
> garbage collected memory?

They don't have to.  But they can.  It's the logical nonsequitur that
"GC is unsuitable" that I'm disputing.

I have no qualms whatsoever about moving it out of GC right now, even
more so after I learned how hard it was to try to get incremental
speedups to the current implementation.

But I do take issue with the general claim that GC memory in general
is unsuitable for this, or any, purpose.

>> If we could make ggc_alloc faster, would it still be unsuitable?

This was the critial question.  And, in spite of all of your
reasoning, it was left unanswered.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: [patch] Move loop structures to gc memory

[Daniel Berlin]

On 5/18/07, Alexandre Oliva <aoliva@redhat.com> wrote:
> On May 18, 2007, "Daniel Berlin" <dberlin@dberlin.org> wrote:
>
> > On 5/18/07, Alexandre Oliva <aoliva@redhat.com> wrote:
>
> >> Why is it not suitable?
>
> > Because it's garbage collected memory for something that doesn't need
> > to, care about, or will ever be, garbage collected?
>
> > the memory doesn't need to be garbage collected, it just has some
> > roots in it.
>
> Do you not realize the contradiction between your two statements
> above?
>
> It evidently cares about garbage collection, because it points to
> GC-able objects.

There is no contradiction, if you think there is, you have either
misread of put words in my mouth,

You apparently have misread. It doesn't need to care about, or will
ever be, garbage collected.
Only something it points to is garbage collected.  That is what cares.

>
> > Why should things that don't need to be garbage collected, be in
> > garbage collected memory?
>
> They don't have to.  But they can.  It's the logical nonsequitur that
> "GC is unsuitable" that I'm disputing.

Whatever.
>
> I have no qualms whatsoever about moving it out of GC right now, even
> more so after I learned how hard it was to try to get incremental
> speedups to the current implementation.
>
> But I do take issue with the general claim that GC memory in general
> is unsuitable for this, or any, purpose.
>
> >> If we could make ggc_alloc faster, would it still be unsuitable?
>
> This was the critial question.  And, in spite of all of your
> reasoning, it was left unanswered.

It's been answered many times, so it wasn't answered again.
No matter how fast ggc_alloc becomes, there are still other advantages
to having the memory not be garbage collected, and their always will
be.

Not that it matters, since nobody has volunteered or produced  a patch
to do anything significant to  ggc-page in 2+ years!

--Dan

>

Yes
> --
> Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
> FSF Latin America Board Member         http://www.fsfla.org/
> Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
> Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
>

Re: [patch] Move loop structures to gc memory

[Michael Matz]

Hi,

On Fri, 18 May 2007, Alexandre Oliva wrote:

> >> Why is it not suitable?
> 
> > Because it's garbage collected memory for something that doesn't need
> > to, care about, or will ever be, garbage collected?
> 
> > the memory doesn't need to be garbage collected, it just has some
> > roots in it.
> 
> Do you not realize the contradiction between your two statements
> above?

There is none, as "unsuitable" != "impossible".

> It evidently cares about garbage collection, because it points to 
> GC-able objects.

Unsuitable is no absolute term, which means there are multiple 
interpretation of what is and what is not unsuitable.  It also means that 
you can't dispute the claim of someone finding something unsuitable.  At 
best something like a majority feeling can be obtained.

> > Why should things that don't need to be garbage collected, be in 
> > garbage collected memory?
> 
> They don't have to.  But they can.  It's the logical nonsequitur that
> "GC is unsuitable" that I'm disputing.

But just because they can doesn't mean that "GC is suitable".  It's the 
logical nonsequitur that most are disputing :-)

> But I do take issue with the general claim that GC memory in general is 
> unsuitable for this, or any, purpose.

I'm not sure if anyone here claimed that GC is unsuitable in general for 
any purpose.

> >> If we could make ggc_alloc faster, would it still be unsuitable?
> 
> This was the critial question.  And, in spite of all of your
> reasoning, it was left unanswered.

The answer to that question is "yes".  That reflects my opinion about what 
influences suitability, and what doesn't.  IMHO suitability of 
feature X depends on the most "important" sub-features of X, and if those 
sub-features indeed are necessary.  For GC the most important feature is 
the ability to garbage collect, in order to deal with reclaiming memory 
for stuff whose life-time can't be known precisely.

So, if that ability inherently is not necessary for the implementation, 
then by that definition GC in unsuitable.

If GC also has other sub-features (fastness, inability to handle dynamic 
roots) doesn't matter, if those other sub-features are much less important 
than the most important ones.  IMHO they are, so even those don't make GC 
more suitable.  They might make using GC necessary (as in our very case 
because of the dynamic roots), so there's a mismatch between suitability 
and necessity, which normally are called QoI bugs.  As no matter what you 
do to GC, it still will stay GC (otherwise you've made a non-collecting 
allocator), you can't change the suitability of GC, hence you can only 
try to remove the necessity of GC to fix this QoI bug.  Even the fastest, 
best compacting, rule-the-world GC will still be unsuitable (because for 
one, you could remove the GC part of that allocator and would end up with 
something even faster and smaller, which would be more suitable).

Which is what Zdenek started to do.  Hooray :)


Ciao,
Michael.

Re: [patch] Move loop structures to gc memory

[Mike Stump]

On May 18, 2007, at 10:45 AM, Michael Matz wrote:
> Which is what Zdenek started to do.  Hooray :)

I endorse such refinements to gcc...