[LLVMdev] Improving Garbage Collection
Talin
viridia at gmail.com
Thu Jul 7 13:08:27 PDT 2011
My thoughts are many, and inline below:
On Thu, Jul 7, 2011 at 10:55 AM, Anderson, Todd A <todd.a.anderson at intel.com
> wrote:
> For the past few years, my group in Intel Labs has been working on a
> project similar to LLVM and C--, and perhaps our experience in handling
> roots and stack walking could be useful in deciding how LLVM should evolve
> in the GC area. Our project is called Pillar (you can see our paper
> "Pillar: A Parallel Implementation Language" in Languages and Compilers for
> Parallel Computing 2008 for a general overview). Pillar is a generic
> language and runtime designed to support managed languages and parallel
> languages although most of our work so far has been on the managed side.
> We've implemented a JVM and a functional language on top of Pillar so it has
> evidenced some generality.****
>
> ** **
>
> In the Pillar language, we have a generalized ref (similar to llvm.gcroot)
> data type that encompases different kinds of pointers and types into the
> managed heap. This could be regular pointers, a couple varieties of
> interior pointers, or user-defined pointer types. The underlying compiler
> then generates per-callsite stack maps. Those stack maps can indicate when
> a live ref (local or parameter) is at a known offset from the start of the
> frame and can also indicate when a live ref is present in a register.****
>
> **
>
I assume that by interior pointer you mean a pointer to the inside of
another object?
> **
>
> If we want to enumerate the refs of a call stack, we call a runtime
> function, prtYoungestActivation, and that gives us back a stack iterator for
> the sequence of activations. The iterator contains the value for esp and
> pointers to the memory locations where ebp, eip, edi, esi, and ebx were last
> saved to the stack. (For architectures other than 32-bit x86, the
> register-specific contents of the activation would of course be defined
> differently.) In the eip case, this is saved for every activation as part
> of the call sequence and so provides you with the ability to determine which
> call site you are at. The other registers may have been saved by the
> current frame or a subsequent frame. The stack iterator also contains a
> virtual frame number that basically allows an unwinder to see logical
> activations instead of physical activations that may combine multiple
> logical activations via inlining.****
>
> **
>
That all makes sense.
I would say that your framework is at a somewhat higher level than I would
expect LLVM to support - by that, I mean that ideally it should be possible
to use the primitives that LLVM supplies to build exactly what you have
described. My own use case has slightly different requirements, and as a
result I could not adopt your framework as it is - but I see no reason why I
should not be able to use the same LLVM primitives to build what I need.
The main difference has to do with the handling of disjoint types in my
language. For example, if I declare a variable using the following syntax:
var a:String or float or int;
What the compiler generates is a data structure that looks like this (as it
would appear in C):
struct {
int disc:2; // 0 = String, 1 = int, 2 = float
union {
String * s;
int i;
float f;
};
};
The garbage collector needs to examine the 'disc' field in order to know
whether to trace 's' or not. The way I handle this is by treating the entire
structure as a root, rather than just the pointer field, so that what the
garbage collector sees is a pointer to the beginning of the struct.
I suspect that register maps wouldn't be able to handle this case very well.
SInce the data structure can't fit into a single register, it would have to
be 'sliced' - half in one register and half in another - and the register
map would need some way to communicate to the collector which half of the
struct is in which register. (Or worse, what if only one half was in a
register and the other half on the stack?) I'm guessing that the right
answer is "don't do that" - meaning, don't allow this data structure to be
sliced in that way, at least not during a safe point.
**
You can then call another runtime function, prtEnumerateRootsOfActivation,
to ask for the roots associated with the given stack iterator's current
activation to be enumerated. To this function, you pass a PrtRseInfo struct
that contains a callback that gets invoked once per live ref found and a
opaque environment variable passed (unexamined) onto the callback function.
To go to the next activation on the call stack, you then call the runtime's
prtNextActivation. There are routines to determine when you've got to the
bottom of the call stack as well. In addition, there are routines for
performing other (non-GC) operations the stack iterator's activation, such
as looking up data associated with the SPAN construct (taken from C--) or
exception handlers.****
In my own case, I don't have an iterator for roots within a single
activation, rather I have a static data structure that describes how to find
all of the roots within the call frame. One of my design goals is to
minimize the number of function calls required to trace a pointer, so the
different parts of my code accept whole stack maps as arguments instead of
single pointers.
However, the LLVM approach to generating stack maps is flexible enough to
handle either case - your GCStrategy plugin gets a list of all stack roots
for each safe point, and you can transform that into whatever data
structures you need.
We have a couple of associated constructs in this regard. The first is the
concept of code regions. We can define regions of code and define different
owners for each region. A typical configuration is for most code to be in a
region associated with our compiler, another region for code implemented in
the Pillar runtime, and another region for code implemented in our GC. You
first register a code info manager with the Pillar runtime and then
associate regions of code with that manager. When you register, you provide
a set of callback functions to enumerate roots, unwind to the next
activation, etc. So, the Pillar compiler's code info manager uses a
callback that consults the previously generated stack maps in order to
enumerate roots. The GC could optimize its barriers and provide its own
code info manager to handle enumerating roots in those barriers.****
** **
Thoughts?****
** **
Todd****
** **
** **
Below are the relevant portions from our runtime’s include files.****
** **
** **
/* This is essentially a pointer-sized integer. */****
typedef char *PrtRegister;****
** **
/* These are used to document function parameters to indicate whether they
are IN, OUT, or INOUT. */****
#define PRT_IN****
#define PRT_OUT****
#define PRT_INOUT****
** **
/*****
***********************************************************************************************
****
* Basic constants, definitions, and types.****
***********************************************************************************************
****
*/****
** **
/* These are tags that the GC uses to interpret roots that are enumerated.**
**
Some tags require additional parameters that need to be passed in as
well.****
The interface includes a single argument that can be used directly for a**
**
single parameter, or treated as an array or struct pointer if multiple***
*
parameters are required.****
Several tags are predefined for the compiler's benefit, but the
high-level****
language is free to use them as well.****
"Default": The root points to the canonical object address (usually the
base).****
No additional parameters are used, and the argument is
ignored.****
"Offset": The root is at a known offset from the canonical object
address.****
Subtract the int-type parameter from the root to get the
canonical****
object address. Example: the root points to a specific field
of****
an object.****
"Base": The root is related to an object whose canonical address is
found as****
the ref-type parameter. Example: the root points to some array
element****
contained within the object.****
Any tag value starting from UserDefined and beyond can be defined and
used****
by the high-level language and its associated GC implementation. ****
*/****
typedef enum { PrtGcTagDefault = 0, PrtGcTagOffset = 1, PrtGcTagBase = 2,
PrtGcTagUserDefined = 3 } PrtGcTag;****
** **
/* Points to executable code. It is "unsigned char *" so that arithmetic is
valid. */****
typedef unsigned char *PrtCodeAddress;****
** **
/* Points to a sequence of data bytes. It is "unsigned char *" so that
arithmetic is valid. */****
typedef unsigned char *PrtDataPointer;****
** **
/* Forward declarations of nonexistent structures, to avoid typedef'ing to
void*. */****
struct PrtCimSpecificDataStruct;****
struct PrtCodeInfoManagerStruct;****
** **
/*****
* The context for stack frames that is used during stack walking. We use
pointers in place of ****
* direct values to support root set enumeration.****
*/****
struct PrtStackIterator ****
{****
/* Stack pointer, eip, and frame pointer */****
PrtRegister esp;****
PrtRegister *ebpPtr;****
PrtCodeAddress *eipPtr;****
/* Callee-save registers */****
PrtRegister *ediPtr;****
PrtRegister *esiPtr;****
PrtRegister *ebxPtr;****
/* The Pillar compiler may inline several "virtual" frames into a single
"physical" frame.****
However, the stack iterator should maintain the illusion that no
inlining was done.****
This field keeps track of which virtual frame we are at within the
physical frame.****
The value 0 means the newest, innermost frame, and the value is
incremented when****
doing a virtual unwind within the same physical frame. */****
unsigned virtualFrameNumber;****
}; /* struct PrtStackIterator */****
** **
/*****
* Type of procedures called once for each enumerated root. "rootAddr" is the
address of a pointer-sized field****
* containing either a reference to a heap object or a managed pointer. "env"
is an (opaque to Pillar) value ****
* that the client passed in a PrtRseInfo structure in the call****
*/****
typedef void (*PrtRseCallback)(void *env, void **rootAddr, PrtGcTag tag,
void *parameter);****
** **
struct PrtRseInfo ****
{****
PrtRseCallback callback; /* invoked for each enumerated root */****
void *env; /* opaque value to be passed in each call to
the callback function */****
}; /* struct PrtRseInfo */****
** **
/*****
**********************************************************************************************************
****
* Stack iteration functions****
**********************************************************************************************************
****
*/****
** **
/* ****
* Create a stack iterator for the current task. "si" points to
client-allocated storage.****
*/****
void prtYoungestActivation(PRT_OUT struct PrtStackIterator *si);****
** **
/* Go to the activation previous to (older than) the current one. */****
void prtNextActivation(PRT_INOUT struct PrtStackIterator *si);****
** **
/* Return True iff no activations remain on the stack. */****
#define prtIsActivationPastEnd(si) (((si)->eipPtr == NULL)? PrtTrue :
PrtFalse)****
** **
/* Return the ip for the current activation. */****
#define prtGetActivationIP(si) ((PrtCodeAddress)((si)->eipPtr ?
*(si)->eipPtr : 0))****
** **
/* Convenience function for updating all writable fields of a stack iterator
at once.****
The advantage of using this consistently is that if the PrtStackIterator*
***
ever changes, this function can be changed accordingly, and all calls to*
***
it can be easily found and modified.****
*/****
void prtSetStackIteratorFields(PRT_OUT struct PrtStackIterator *context,****
PRT_IN PrtCodeAddress *eipPtr,****
PRT_IN PrtRegister esp,****
PRT_IN PrtRegister *ebxPtr,****
PRT_IN PrtRegister *ebpPtr,****
PRT_IN PrtRegister *esiPtr,****
PRT_IN PrtRegister *ediPtr,****
PRT_IN unsigned virtualFrameNumber);****
** **
/* ****
* Returns the value associated with the smallest span tagged with "key" and
containing the program point ****
* where "si" is suspended. Returns (PrtDataPointer)NULL if there is no
such span. ****
*/ ****
PrtDataPointer prtGetSpanDescriptor(PRT_IN struct PrtStackIterator *si,
PRT_IN unsigned key);****
** **
/* Enumerate the roots of a frame given by the specified stack iterator. */*
***
void prtEnumerateRootsOfActivation(PRT_IN struct PrtStackIterator *si,
PRT_IN struct PrtRseInfo *rootSetInfo);****
** **
/* ****
***********************************************************************************************
****
* Code Info Manager functions ****
***********************************************************************************************
****
*/****
** **
typedef struct PrtCodeInfoManagerStruct *PrtCodeInfoManager;****
/* Type of client-specified data that a client can associate with each code
range with a prtCodeInfoManager. */****
typedef struct PrtCimSpecificDataStruct *PrtCimSpecificDataType;****
** **
/* ****
* A set of callback functions implemented by a producer of managed code
(e.g., a JIT or static compiler) that the PRT****
* can call as part of its implementation of stack walking, root set
enumeration, exception handling, etc. These are****
* used to define a CodeInfoManager.****
*/****
struct PrtCodeInfoManagerFunctions {****
/* Returns a string describing the current frame. */****
char * ( *cimGetStringForFrame)(PRT_IN struct PrtStackIterator *si,****
PRT_OUT char *buffer,****
PRT_IN size_t bufferSize,****
PRT_IN PrtCimSpecificDataType
opaqueData);****
/* Modifies si to hold information about the frame previous to the
current one. Returns True if this was successful,****
and False if not. opaqueData is the same as the opaqueData that was
passed to Pillar when the CIM registered ****
this code region. */****
void ( *cimGetPreviousFrame)(PRT_INOUT struct PrtStackIterator *si, ***
*
PRT_IN PrtCimSpecificDataType
opaqueData);****
/* Enumerates the live GC roots of the current stack frame. The
activation is guaranteed to be****
suspended at a call site. */****
void ( *cimEnumerateRoots)(PRT_IN struct PrtStackIterator *si, ****
PRT_IN struct PrtRseInfo *rootSetInfo,
****
PRT_IN PrtCimSpecificDataType
opaqueData);****
/* Returns the value associated with the smallest span tagged with "key"
and containing the program point ****
where "si" is suspended. "opaqueData" is the same data that the CIM
passed to Pillar when it registered ****
the code region containing si's program point. Returns
(PrtDataPointer)NULL if there is no such span. */****
PrtDataPointer ( *cimGetSpanDescriptor)(PRT_IN struct PrtStackIterator
*si, ****
PRT_IN unsigned key, ****
PRT_IN PrtCimSpecificDataType
opaqueData);****
}; /* struct PrtCodeInfoManagerFunctions */****
** **
** **
/* Creates a new PrtCodeInfoManager and registers a set of callback
functions belonging to it. */****
PrtCodeInfoManager prtRegisterCodeInfoManager(PRT_IN const char *theCimName,
PRT_IN struct PrtCodeInfoManagerFunctions theCimFns);****
** **
/*****
* Register the block of code in [start..end] with the given
PrtCodeInfoManager. ****
* Returns True on success and False on failure (e.g., if the code's region
overlaps that of already-registered code).****
* The opaqueData parameter is associated with this code region and passed
back to the Cim during each of the calls ****
* to the Cim for this code region.****
*/****
void prtAddCodeRegion(PRT_IN PrtCodeInfoManager theCim, ****
PRT_IN PrtCodeAddress start, ****
PRT_IN PrtCodeAddress end, ****
PRT_IN PrtCimSpecificDataType opaqueData);****
** **
_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
--
-- Talin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110707/87a6bc84/attachment.html>
More information about the llvm-dev
mailing list