Memory Management in MELT
This page explains the peculiarities of memory management in the MELT branch, both for using MELT (notably coding in MELT) and for a MELT oriented discussion about memory management (inside the GCC compiler)1 and GCC plugins
This page is for
- people using MELT and coding some passes in MELT
- general GCC developers, notably those interested in plugins and GGC etc..
Why memory management is so important to MELT?
MELT is a Lisp dialect specific to coding GCC passes. Its major value is to be very tightly integrated to GCC middle end 2, and since GCC won't have any stable API, it is required to be strongly related to GCC internal data structures (like GIMPLE tuples etc...). The way to facilitate this tight integration is to generate C code and to offer idioms to ease, to tune, to parametrize this C code generation (using the code_chunk defprimitive defciterator defcmatcher ... MELT operators).
MELT handles both MELT specific data, which we call MELT values (like MELT closures or lists or hashtables etc...) and existing GCC stuff like gimple or edge etc... Some values are boxing3 stuff, for instance it is possible to box a gimple as a MELT value. To make MELT less intrusive (in particular, when MELT is not explicitly enabled, the MELT branch behaves as the trunk) no MELT specific fields has been added inside existing GCC stuff (e.g. the gimple or edge structures remain the same as in trunk and have no MELT specific extra fields). Since MELT passes need to associate some information to some stuff (e.g. to gimple) MELT provides many hash tables as MELT values. In practice, to add MELT information associated to some gimple one would allocate some MELT gimple hash table[s], which is a MELT value mapping gimple-s to other MELT values, and use that/these hash table[s] to associate MELT value to gimple. By keeping this MELT gimple hash table one can transmit information associated to some gimple-s from one MELT pass to another one.
As in all Lisp (or other high level languages like Scheme, Prolog, ML or Java, etc...) automatic memory management is of paramount importance: the programmer (in MELT, Common Lisp, Scheme, ML, Prolog, Java, ...) is not expecting to systematically and explicitly code the release of allocated memory (like free in C or delete in C++). In turn, providing such facilities (implemented by some kind of garbage collector) makes this programmer more productive, but also may change his coding style: programmers allocate a lot of data, and most of it is temporary, and not often mutated. Such a programming style profits of garbage collectors able to allocate quickly lots of temporary memory4.
MELT being a branch of GCC 5 it should be compatible with GCC habits, in particular with GCC garbage collector memory management. Hence, allocating stuff in MELT which would be later freed by some other existing GCC passes or by the GCC pass manager is possible and easy. This means that MELT GC should tightly cooperate with GGC (the GCC Garbage Collector implemented in files gcc/ggc*.[ch]). In particular, it would not be possible to use some other garbage collector (unrelated to GGC, like Boehm's one) inside MELT. MELT can also be compiled as a gcc-4.5 (i.e. gcc trunk) plugin.
The MELT heap should be kept between various MELT passes (and even afterward, since some MELT code is called after passes at finalisation from basilys_finalize), since it can be useful for one MELT pass to build data which would be used by further MELT passes or finally 6. Also, many important MELT data is initialized early when MELT modules are loaded, and should be kept as long as needed. In fact, there are few global MELT data, but data can shared between several MELT closures and be passed from one pass to another.
How does MELT manage its memory?
MELT has its own memory management implemented in files gcc/basilys.c and gcc/basilys.h which is a generational copying collector built above the existing GGC framework: so MELT garbage collection is backed up and compatible with GGC garbage collection. More precisely, all data allocated by MELT (using its inlined basilysgc_allocate function) is allocated inside the MELT young allocation zone7. When the young allocation zone is full (or when explicitly asked, e.g. at end of every MELT pass), a MELT minor garbage collection occurs : it copies live young MELT values out of the young allocation zone, and into the GGC heap. When the cumulative size of MELT allocated data has increased above a certain threshold 8 a MELT full garbage collection occurs: after the copying out of the allocation zone into the GGC heap, the GGC collector is explicitly invoked in basilysgc_garbcoll (and would reclaim unused memory inside its heap).
Notice that, in contrast with GGC usage, the MELT garbage collector is most often invoked implicitly (from basilysgc_allocate only when the young allocation zone is full) and unpredictably (it is also always invoked at end of every MELT pass, so that the GGC heap would be clean, and the MELT allocation young zone would be empty, once the MELT pass is ended and GCC resumes the other usual processing in existing passes).
Since MELT minor collector is a generational copying one, the MELT GC needs to know reliably and handle all the local and global MELT roots (to update them when copying out of the young allocation zone). This is a burden in hand-written C code 9 but is easily handled in generated C code. Actually, MELT call frames are explicited (as linked C struct-s on the machine stack), and code to traverse them and mark them is automatically generated. The young allocation zone is used only to allocate MELT values; when MELT code allocates usual GCC stuff like tree or gimple etc. it uses primitives wrapping the existing GCC functions like gimple_build_call etc.. which in turn does some GGC allocation.
Sometimes the MELT garbage collector is a full garbage collection, which triggers the existing ggc_collect 10 (after having copied live MELT values out of MELT young allocation zone), and handling carefully MELT local data (i.e. local pointers inside MELT call frames to MELT values or new GCC stuff). In contrast to other GCC passes, MELT can call the GGC collector at almost any time (including inside passes) but deals carefully with local pointers.
So MELT depends critically on the ability, for the GGC garbage collector, to mark some extra data (any GGC-ed pointer, be it MELT values or GCC stuff like gimple-s, tree-s, edge-s, basic_block-s etc) from inside GGC. This marking is mostly generated C code, and is invoked from basilys_marking_callback (registered thru PLUGIN_GGC_MARKING); but this is a requirement for MELT to extend the marking of GGC. In addition, other plugins would profit of the ability to register their own GTY-ed data. a patch to gengtype has been proposed to generate the extra GGC root table(s) in plugins for registration thru PLUGIN_REGISTER_GGC_ROOTS
MELT as a meta-plugin
I BasileStarynkevitch hope to progressively transform MELT into a big plugin (which will itself load MELT code as MELT specific plugins). This requires the PLUGIN_*GGC* events (already accepted in the trunk) and the ability for gengtype to handle plugin code as proposed in the patch to gengtype.
If a strong relation with GCC internals is not essential, there is no point in MELT! (2)
To box a stuff means to allocate a MELT value containing that stuff. (3)
For that purpose of dealing efficiently with lots of temporary data, the existing GGC garbage collector is inadequate: it does not deal with local variables on the call stack, and it does not handle efficiently very temporary data, because GGC was not designed for such goals! (4)
MELT follows quite closely the GCC trunk; practically the trunk is merged into the MELT branch at least every week, and usually more. (5)
For example, many static analysis compute data for each function in non IPA passes and would synthesize results in a further pass. (6)
The usual size of the young allocation zone is a half mega-word so it could fit inside your L3 cache; it can be tuned with the basilys-minor-zone parameter eg by passing --param basilys-minor-zone=2048 to the MELT GCC driver program gcc or gcc-melt to request a two mega-words young allocation zone. (7)
this threshold defaults to 2048 kilo-words and can be set to e.g. 4Mwords with --param basilys-full-threshold=4096. (8)
See the numerous routines in gcc/basilys.c using the BASILYS_ENTERFRAME and BASILYS_EXITFRAME macros, and the definitions of these macros in gcc/basilys.h (9)
Actually, basilys_garbcoll may call ggc_collect and needs to invoke the GGC collector with marking all the local data -both "old" MELT values and GCC stuff like gimple- by scanning the MELT call frames' list starting from basilys_topframe using the basilys_marking_callback routine (registered using PLUGIN_GGC_MARKING) which calls generated code to scan each MELT call frame. (10)