Memory Management and Type Information
**************************************

GCC uses some fairly sophisticated memory management techniques, which involve determining information about GCC's data structures from GCC's source code and using this information to perform garbage collection and implement precompiled headers.

A full C++ parser would be too complicated for this task, so a limited subset of C++ is interpreted and special markers are used to determine what parts of the source to look at.  All struct, union and template structure declarations that define data structures that are allocated under control of the garbage collector must be marked.  All global variables that hold pointers to garbage-collected memory must also be marked.  Finally, all global variables that need to be saved and restored by a precompiled header must be marked.  (The precompiled header mechanism can only save static variables if they're scalar. Complex data structures must be allocated in garbage-collected memory to be saved in a precompiled header.)

The full format of a marker is

     GTY (([OPTION] [(PARAM)], [OPTION] [(PARAM)] ...))

but in most cases no options are needed.  The outer double parentheses are still necessary, though: GTY(()).  Markers can appear:

  * In a structure definition, before the open brace;

  * In a global variable declaration, after the keyword static or extern; and

  * In a structure field definition, before the name of the field.

Here are some examples of marking simple data structures and globals.

     struct GTY(()) TAG
     {
       FIELDS...
     };

     typedef struct GTY(()) TAG
     {
       FIELDS...
     } *TYPENAME;

     static GTY(()) struct TAG *LIST;   /* points to GC memory */
     static GTY(()) int COUNTER;        /* save counter in a PCH */

The parser understands simple typedefs such as typedef struct TAG *NAME; and typedef int NAME;. These don't need to be marked.

However, in combination with GTY, avoid using typedefs such as typedef int_hash<...> NAME; for these generate infinite-recursion code. See PR103157 (https://gcc.gnu.org/PR103157). Instead, you may use struct NAME : int_hash<...> {};, for example.

Since gengtype's understanding of C++ is limited, there are several constructs and declarations that are not supported inside classes/structures marked for automatic GC code generation.  The following C++ constructs produce a gengtype error on structures/classes marked for automatic GC code generation:

  * Type definitions inside classes/structures are not supported.

  * Enumerations inside classes/structures are not supported.

If you have a class or structure using any of the above constructs, you need to mark that class as GTY ((user)) and provide your own marking routines (see section User GC for details).

It is always valid to include function definitions inside classes. Those are always ignored by gengtype, as it only cares about data members.

The Inside of a GTY(())
=======================

Sometimes the C code is not enough to fully describe the type structure.  Extra information can be provided with GTY options and additional markers.  Some options take a parameter, which may be either a string or a type name, depending on the parameter.  If an option takes no parameter, it is acceptable either to omit the parameter entirely, or to provide an empty string as a parameter.  For example, GTY ((skip)) and GTY ((skip (""))) are equivalent.

When the parameter is a string, often it is a fragment of C code.  Four special escapes may be used in these strings, to refer to pieces of the data structure being marked:

%h
     The current structure.

%1
     The structure that immediately contains the current structure.

%0
     The outermost structure that contains the current structure.

%a
     A partial expression of the form [i1][i2]... that indexes the array item currently being marked.

For instance, suppose that you have a structure of the form

     struct A {
       ...
     };
     struct B {
       struct A foo[12];
     };

and b is a variable of type struct B.  When marking b.foo[11], %h would expand to b.foo[11], %0 and %1 would both expand to b, and %a would expand to [11].

As in ordinary C, adjacent strings will be concatenated; this is helpful when you have a complicated expression.

     GTY ((chain_next ("TREE_CODE (&%h.generic) == INTEGER_TYPE"
                       " ? TYPE_NEXT_VARIANT (&%h.generic)"
                       " : TREE_CHAIN (&%h.generic)")))

The available options are:

length ("EXPRESSION")

     There are two places the type machinery will need to be explicitly told the length of an array of non-atomic objects.  The first case is when a structure ends in a variable-length array, like this:

          struct GTY(()) rtvec_def {
            int num_elem;         /* number of elements */
            rtx GTY ((length ("%h.num_elem"))) elem[1];
          };

     In this case, the length option is used to override the specified array length (which should usually be 1).  The parameter of the option is a fragment of C code that calculates the length.

     The second case is when a structure or a global variable contains a pointer to an array, like this:

          struct gimple_omp_for_iter * GTY((length ("%h.collapse"))) iter;

     In this case, iter has been allocated by writing something like

            x->iter = ggc_alloc_cleared_vec_gimple_omp_for_iter (collapse);

     and the collapse provides the length of the field.

     This second use of length also works on global variables, like:
     static GTY((length("reg_known_value_size"))) rtx *reg_known_value;

     Note that the length option is only meant for use with arrays of non-atomic objects, that is, objects that contain pointers pointing to other GTY-managed objects.  For other GC-allocated arrays and strings you should use atomic.

skip

     If skip is applied to a field, the type machinery will ignore it. This is somewhat dangerous; the only safe use is in a union when one field really isn't ever used.

callback

     callback should be applied to fields with pointer to function type and causes the field to be ignored similarly to skip, except when writing PCH and the field is non-NULL it will remember the field's address for relocation purposes if the process writing PCH has different load base from a process reading PCH.

for_user

     Use this to mark types that need to be marked by user gc routines, but are not refered to in a template argument.  So if you have some user gc type T1 and a non user gc type T2 you can give T2 the for_user option so that the marking functions for T1 can call non mangled functions to mark T2.

desc ("EXPRESSION")
tag ("CONSTANT")
default

     The type machinery needs to be told which field of a union is currently active.  This is done by giving each field a constant tag value, and then specifying a discriminator using desc. The value of the expression given by desc is compared against each tag value, each of which should be different.  If no tag is matched, the field marked with default is used if there is one, otherwise no field in the union will be marked.

     In the desc option, the ``current structure'' is the union that it discriminates.  Use %1 to mean the structure containing it. There are no escapes available to the tag option, since it is a constant.

     For example,

          struct GTY(()) tree_binding
          {
            struct tree_common common;
            union tree_binding_u {
              tree GTY ((tag ("0"))) scope;
              struct cp_binding_level * GTY ((tag ("1"))) level;
            } GTY ((desc ("BINDING_HAS_LEVEL_P ((tree)&%0)"))) xscope;
            tree value;
          };

     In this example, the value of BINDING_HAS_LEVEL_P when applied to a struct tree_binding * is presumed to be 0 or 1.  If 1, the type mechanism will treat the field level as being present and if 0, will treat the field scope as being present.

     The desc and tag options can also be used for inheritance to denote which subclass an instance is.  See Inheritance and GTY for more information.

cache

     When the cache option is applied to a global variable gt_cleare_cache is called on that variable between the mark and sweep phases of garbage collection.  The gt_clear_cache function is free to mark blocks as used, or to clear pointers in the variable.

deletable

     deletable, when applied to a global variable, indicates that when garbage collection runs, there's no need to mark anything pointed to by this variable, it can just be set to NULL instead.  This is used to keep a list of free structures around for re-use.

maybe_undef

     When applied to a field, maybe_undef indicates that it's OK if the structure that this fields points to is never defined, so long as this field is always NULL.  This is used to avoid requiring backends to define certain optional structures.  It doesn't work with language frontends.

nested_ptr (TYPE, "TO EXPRESSION", "FROM EXPRESSION")

     The type machinery expects all pointers to point to the start of an object.  Sometimes for abstraction purposes it's convenient to have a pointer which points inside an object.  So long as it's possible to convert the original object to and from the pointer, such pointers can still be used.  TYPE is the type of the original object, the TO EXPRESSION returns the pointer given the original object, and the FROM EXPRESSION returns the original object given the pointer.  The pointer will be available using the %h escape.

chain_next ("EXPRESSION")
chain_prev ("EXPRESSION")
chain_circular ("EXPRESSION")

     It's helpful for the type machinery to know if objects are often chained together in long lists; this lets it generate code that uses less stack space by iterating along the list instead of recursing down it.  chain_next is an expression for the next item in the list, chain_prev is an expression for the previous item.  For singly linked lists, use only chain_next; for doubly linked lists, use both.  The machinery requires that taking the next item of the previous item gives the original item.  chain_circular is similar to chain_next, but can be used for circular single linked lists.

reorder ("FUNCTION NAME")

     Some data structures depend on the relative ordering of pointers.  If the precompiled header machinery needs to change that ordering, it will call the function referenced by the reorder option, before changing the pointers in the object that's pointed to by the field the option applies to.  The function must take four arguments, with the signature void *, void *, gt_pointer_operator, void *. The first parameter is a pointer to the structure that contains the object being updated, or the object itself if there is no containing structure.  The second parameter is a cookie that should be ignored. The third parameter is a routine that, given a pointer, will update it to its correct new value.  The fourth parameter is a cookie that must be passed to the second parameter.

     PCH cannot handle data structures that depend on the absolute values of pointers.  reorder functions can be expensive.  When possible, it is better to depend on properties of the data, like an ID number or the hash of a string instead.

atomic

     The atomic option can only be used with pointers.  It informs the GC machinery that the memory that the pointer points to does not contain any pointers, and hence it should be treated by the GC and PCH machinery as an ``atomic'' block of memory that does not need to be examined when scanning memory for pointers.  In particular, the machinery will not scan that memory for pointers to mark them as reachable (when marking pointers for GC) or to relocate them (when writing a PCH file).

     The atomic option differs from the skip option. atomic keeps the memory under Garbage Collection, but makes the GC ignore the contents of the memory.  skip is more drastic in that it causes the pointer and the memory to be completely ignored by the Garbage Collector.  So, memory marked as atomic is automatically freed when no longer reachable, while memory marked as skip is not.

     The atomic option must be used with great care, because all sorts of problem can occur if used incorrectly, that is, if the memory the pointer points to does actually contain a pointer.

     Here is an example of how to use it:

          struct GTY(()) my_struct {
            int number_of_elements;
            unsigned int * GTY ((atomic)) elements;
          };

     In this case, elements is a pointer under GC, and the memory it points to needs to be allocated using the Garbage Collector, and will be freed automatically by the Garbage Collector when it is no longer referenced.  But the memory that the pointer points to is an array of unsigned int elements, and the GC must not try to scan it to find pointers to mark or relocate, which is why it is marked with the atomic option.

     Note that, currently, global variables cannot be marked with atomic; only fields of a struct can.  This is a known limitation.  It would be useful to be able to mark global pointers with atomic to make the PCH machinery aware of them so that they are saved and restored correctly to PCH files.

special ("NAME")

     The special option is used to mark types that have to be dealt with by special case machinery.  The parameter is the name of the special case.  See gengtype.cc for further details.  Avoid adding new special cases unless there is no other alternative.

user

     The user option indicates that the code to mark structure fields is completely handled by user-provided routines.  See section User GC for details on what functions need to be provided.

Support for inheritance
=======================

gengtype has some support for simple class hierarchies.  You can use this to have gengtype autogenerate marking routines, provided:

  * There must be a concrete base class, with a discriminator expression that can be used to identify which subclass an instance is.

  * Only single inheritance is used.

  * None of the classes within the hierarchy are templates.

If your class hierarchy does not fit in this pattern, you must use User GC instead.

The base class and its discriminator must be identified using the ``desc'' option.  Each concrete subclass must use the ``tag'' option to identify which value of the discriminator it corresponds to.

Every class in the hierarchy must have a GTY(()) marker, as gengtype will only attempt to parse classes that have such a marker (Classes lacking such a marker will not be identified as being part of the hierarchy, and so the marking routines will not handle them, leading to a assertion failure within the marking routines due to an unknown tag value (assuming that assertions are enabled).).

     class GTY((desc("%h.kind"), tag("0"))) example_base
     {
     public:
         int kind;
         tree a;
     };

     class GTY((tag("1"))) some_subclass : public example_base
     {
     public:
         tree b;
     };

     class GTY((tag("2"))) some_other_subclass : public example_base
     {
     public:
         tree c;
     };

The generated marking routines for the above will contain a ``switch'' on ``kind'', visiting all appropriate fields.  For example, if kind is 2, it will cast to ``some_other_subclass'' and visit fields a, b, and c.

Support for user-provided GC marking routines
=============================================

The garbage collector supports types for which no automatic marking code is generated.  For these types, the user is required to provide three functions: one to act as a marker for garbage collection, and two functions to act as marker and pointer walker for pre-compiled headers.

Given a structure struct GTY((user)) my_struct, the following functions should be defined to mark my_struct:

     void gt_ggc_mx (my_struct *p)
     {
       /* This marks field 'fld'.  */
       gt_ggc_mx (p->fld);
     }

     void gt_pch_nx (my_struct *p)
     {
       /* This marks field 'fld'.  */
       gt_pch_nx (tp->fld);
     }

     void gt_pch_nx (my_struct *p, gt_pointer_operator op, void *cookie)
     {
       /* For every field 'fld', call the given pointer operator.  */
       op (&(tp->fld), NULL, cookie);
     }

In general, each marker M should call M for every pointer field in the structure.  Fields that are not allocated in GC or are not pointers must be ignored.

For embedded lists (e.g., structures with a next or prev pointer), the marker must follow the chain and mark every element in it.

Note that the rules for the pointer walker gt_pch_nx (my_struct *, gt_pointer_operator, void *) are slightly different.  In this case, the operation op must be applied to the address of every pointer field.

User-provided marking routines for template types
-------------------------------------------------

When a template type TP is marked with GTY, all instances of that type are considered user-provided types.  This means that the individual instances of TP do not need to be marked with GTY.  The user needs to provide template functions to mark all the fields of the type.

The following code snippets represent all the functions that need to be provided. Note that type TP may reference to more than one type. In these snippets, there is only one type T, but there could be more.

     template<typename T>
     void gt_ggc_mx (TP<T> *tp)
     {
       extern void gt_ggc_mx (T&);

       /* This marks field 'fld' of type 'T'.  */
       gt_ggc_mx (tp->fld);
     }

     template<typename T>
     void gt_pch_nx (TP<T> *tp)
     {
       extern void gt_pch_nx (T&);

       /* This marks field 'fld' of type 'T'.  */
       gt_pch_nx (tp->fld);
     }

     template<typename T>
     void gt_pch_nx (TP<T *> *tp, gt_pointer_operator op, void *cookie)
     {
       /* For every field 'fld' of 'tp' with type 'T *', call the given
          pointer operator.  */
       op (&(tp->fld), NULL, cookie);
     }

     template<typename T>
     void gt_pch_nx (TP<T> *tp, gt_pointer_operator, void *cookie)
     {
       extern void gt_pch_nx (T *, gt_pointer_operator, void *);

       /* For every field 'fld' of 'tp' with type 'T', call the pointer
          walker for all the fields of T.  */
       gt_pch_nx (&(tp->fld), op, cookie);
     }

Support for user-defined types is currently limited. The following restrictions apply:

 1. Type TP and all the argument types T must be marked with GTY.

 2. Type TP can only have type names in its argument list.

 3. The pointer walker functions are different for TP<T> and TP<T *>. In the case of TP<T>, references to T must be handled by calling gt_pch_nx (which will, in turn, walk all the pointers inside fields of T). In the case of TP<T *>, references to T * must be handled by calling the op function on the address of the pointer (see the code snippets above).

Marking Roots for the Garbage Collector
=======================================

In addition to keeping track of types, the type machinery also locates the global variables (roots) that the garbage collector starts at.  Roots must be declared using one of the following syntaxes:

  * extern GTY(([OPTIONS])) TYPE NAME;

  * static GTY(([OPTIONS])) TYPE NAME;

The syntax

  * GTY(([OPTIONS])) TYPE NAME;

is not accepted.  There should be an extern declaration of such a variable in a header somewhere---mark that, not the definition.  Or, if the variable is only used in one file, make it static.

Source Files Containing Type Information
========================================

Whenever you add GTY markers to a source file that previously had none, or create a new source file containing GTY markers, there are three things you need to do:

 1. You need to add the file to the list of source files the type machinery scans.  There are four cases:

      a. For a back-end file, this is usually done automatically; if not, you should add it to target_gtfiles in the appropriate port's entries in config.gcc.

      b. For files shared by all front ends, add the filename to the GTFILES variable in Makefile.in.

      c. For files that are part of one front end, add the filename to the gtfiles variable defined in the appropriate config-lang.in. Headers should appear before non-headers in this list.

      d. For files that are part of some but not all front ends, add the filename to the gtfiles variable of all the front ends that use it.

 2. If the file was a header file, you'll need to check that it's included in the right place to be visible to the generated files.  For a back-end header file, this should be done automatically.  For a front-end header file, it needs to be included by the same file that includes gtype-LANG.h.  For other header files, it needs to be included in gtype-desc.cc, which is a generated file, so add it to ifiles in open_base_file in gengtype.cc.

     For source files that aren't header files, the machinery will generate a header file that should be included in the source file you just changed. The file will be called gt-PATH.h where PATH is the pathname relative to the gcc directory with slashes replaced by -, so for example the header file to be included in cp/parser.cc is called gt-cp-parser.h.  The generated header file should be included after everything else in the source file.

For language frontends, there is another file that needs to be included somewhere.  It will be called gtype-LANG.h, where LANG is the name of the subdirectory the language is contained in.

Plugins can add additional root tables.  Run the gengtype utility in plugin mode as gengtype -P pluginout.h SOURCE-DIR FILE-LIST PLUGIN*.C with your plugin files PLUGIN*.C using GTY to generate the PLUGINOUT.H file. The GCC build tree is needed to be present in that mode.

How to invoke the garbage collector
===================================

The GCC garbage collector GGC is only invoked explicitly. In contrast with many other garbage collectors, it is not implicitly invoked by allocation routines when a lot of memory has been consumed. So the only way to have GGC reclaim storage is to call the ggc_collect function explicitly. With MODE GGC_COLLECT_FORCE or otherwise (default GGC_COLLECT_HEURISTIC) when the internal heuristic decides to collect, this call is potentially an expensive operation, as it may have to scan the entire heap.  Beware that local variables (on the GCC call stack) are not followed by such an invocation (as many other garbage collectors do): you should reference all your data from static or external GTY-ed variables, and it is advised to call ggc_collect with a shallow call stack.  The GGC is an exact mark and sweep garbage collector (so it does not scan the call stack for pointers).  In practice GCC passes don't often call ggc_collect themselves, because it is called by the pass manager between passes.

At the time of the ggc_collect call all pointers in the GC-marked structures must be valid or NULL.  In practice this means that there should not be uninitialized pointer fields in the structures even if your code never reads or writes those fields at a particular instance.  One way to ensure this is to use cleared versions of allocators unless all the fields are initialized manually immediately after allocation.

Troubleshooting the garbage collector
=====================================

With the current garbage collector implementation, most issues should show up as GCC compilation errors.  Some of the most commonly encountered issues are described below.

  * Gengtype does not produce allocators for a GTY-marked type. Gengtype checks if there is at least one possible path from GC roots to at least one instance of each type before outputting allocators.  If there is no such path, the GTY markers will be ignored and no allocators will be output.  Solve this by making sure that there exists at least one such path.  If creating it is unfeasible or raises a ``code smell'', consider if you really must use GC for allocating such type.

  * Link-time errors about undefined gt_ggc_r_foo_bar and similarly-named symbols.  Check if your foo_bar source file has #include "gt-foo_bar.h" as its very last line.