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.

A full C parser would be too overcomplicated 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.  The parser can also detect simple typedefs of the form typedef struct ID1 *ID2; and typedef int ID3;, and these don't need to be specially marked.

The two forms that do need to be marked are:
struct ID1 GTY(([options]))
{
  [fields]
};

typedef struct ID2 GTY(([options]))
{
  [fields]
} ID3;

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

Sometimes the C code is not enough to fully describe the type structure. Extra information can be provided by using more GTY markers. These markers can be placed:

  * 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.

The format of a marker is
GTY (([name] ([param]), [name] ([param]) ...))
The parameter is either a string or a type name.

When the parameter is a string, often it is a fragment of C code.  Three special escapes may be available:

%h
     This expands to an expression that evaluates to the current structure.

%1
     This expands to an expression that evaluates to the structure that immediately contains the current structure.

%0
     This expands to an expression that evaluates to the outermost structure that contains the current structure.

%a
     This expands to the string of the form [i1][i2]... that indexes the array item currently being marked.  For instance, if the field being marked is foo, then %1.foo%a is the same as %h.

The available options are:

length

     There are two places the type machinery will need to be explicitly told the length of an array.  The first case is when a structure ends in a variable-length array, like this:
     struct rtvec_def GTY(()) {
       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:

          tree *
            GTY ((length ("%h.regno_pointer_align_length"))) regno_decl;

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

            x->regno_decl =
              ggc_alloc (x->regno_pointer_align_length * sizeof (tree));

     and the length provides the length of the field.

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

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.

desc
tag
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.  For example,

          struct tree_binding GTY(())
          {
            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)"))) scope;
            tree value;
          };

     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's supposed to be a constant.)

     Each tag 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.

param_is
use_param

     Sometimes it's convenient to define some data structure to work on generic pointers (that is, PTR) and then use it with a specific type.  param_is specifies the real type pointed to, and use_param says where in the generic data structure that type should be put.

     For instance, to have a htab_t that points to trees, one should write
       htab_t GTY ((param_is (union tree_node))) ict;

paramN_is
use_paramN

     In more complicated cases, the data structure might need to work on several different types, which might not necessarily all be pointers. For this, param1_is through param9_is may be used to specify the real type of a field identified by use_param1 through use_param9.

use_params

     When a structure contains another structure that is parameterized, there's no need to do anything special, the inner structure inherits the parameters of the outer one.  When a structure contains a pointer to a parameterized structure, the type machinery won't automatically detect this (it could, it just doesn't yet), so it's necessary to tell it that the pointed-to structure should use the same parameters as the outer structure.  This is done by marking the pointer with the use_params option.

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.

if_marked

     Suppose you want some kinds of object to be unique, and so you put them in a hash table.  If garbage collection marks the hash table, these objects will never be freed, even if the last other reference to them goes away.  GGC has special handling to deal with this: if you use the if_marked option on a global hash table, GGC will call the routine whose name is the parameter to the option on each hash table entry.  If the routine returns nonzero, the hash table entry will be marked as usual.  If the routine returns zero, the hash table entry will be deleted.

     The routine ggc_marked_p can be used to determine if an element has been marked already; in fact, the usual case is to use if_marked ("ggc_marked_p").

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.

special

     The special option is used for those bizarre cases that are just too hard to deal with otherwise.  Don't use it for new code.

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

In addition to keeping track of types, the type machinery also locates the global variables that the garbage collector starts at.  There are two syntaxes it accepts to indicate a root:

 1. extern GTY (([options])) [type] ID;

 2. static GTY (([options])) [type] ID;

These are the only syntaxes that are accepted.  In particular, if you want to mark a variable that is only declared as
int ID;
or similar, you should either make it static or you should create a extern declaration in a header file somewhere.

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

Whenever you add GTY markers to a new source file, 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 three 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, this is done by adding the filename to the GTFILES variable in Makefile.in.

      c. For any other file used by a front end, this is done by adding the filename to the gtfiles variable defined in config-lang.in.  For C, the file is c-config-lang.in. This list should include all files that have GTY macros in them that are used in that front end, other than those defined in the previous list items.  For example, it is common for front end writers to use c-common.c and other files from the C front end, and these should be included in the gtfiles variable for such front ends.

 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.c, which is a generated file, so add it to ifiles in open_base_file in gengtype.c.

     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 objc/objc-parse.c is called gt-objc-objc-parse.c.  The generated header file should be included after everything else in the source file.  Don't forget to mention this file as a dependency in the Makefile!

 3. If a new gt-PATH.h file is needed, you need to arrange to add a Makefile rule that will ensure this file can be built. This is done by making it a dependency of s-gtype, like this:
     gt-path.h : s-gtype ; @true

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. It will need Makefile rules just like the other generated files.