Static Reference Tables (SRTs) are the mechanism by which the garbage collector
can determine the live CAFs in the program. An SRT is a static table associated
with a CAFfy closure which record which CAFfy objects are reachable from
the closure's code.
Representation
^^^^^^^^^^^^^^
+------+
| info |
| | +-----+---+---+---+
| -------->|SRT_2| | | | | 0 |
|------| +-----+-|-+-|-+---+
| | | |
| code | | |
| | v v
An SRT is simply an object in the program's data segment. It has the
same representation as a static constructor. There are 16
pre-compiled SRT info tables: stg_SRT_1_info, .. stg_SRT_16_info,
representing SRT objects with 1-16 pointers, respectively.
The entries of an SRT object point to static closures, which are either
- FUN_STATIC, THUNK_STATIC or CONSTR
- Another SRT (actually just a CONSTR)
The final field of the SRT is the static link field, used by the
garbage collector to chain together static closures that it visits and
to determine whether a static closure has been visited or not. (see
Note [STATIC_LINK fields])
By traversing the transitive closure of an SRT, the GC will reach all
of the CAFs that are reachable from the code associated with this SRT.
If we need to create an SRT with more than 16 entries, we build a
chain of SRT objects with all but the last having 16 entries.
+-----+---+- -+---+---+
|SRT16| | | | | | 0 |
+-----+-|-+- -+-|-+---+
| |
v v
+----+---+---+---+
|SRT2| | | | | 0 |
+----+-|-+-|-+---+
| |
| |
v v
Referring to an SRT from the info table
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The following things have SRTs:
- Static functions (FUN)
- Static thunks (THUNK), ie. CAFs
- Continuations (RET_SMALL, etc.)
In each case, the info table points to the SRT, if there is one.
- info->srt is 0 if there's no SRT
- otherwise, there are three ways which we may encode the location of the SRT in
the info table, described below.
USE_SRT_POINTER
Most general implementation. Can always be used, but other ways are more efficient.
- info->srt is a pointer
We encode an **absolute pointer** to the SRT in info->srt. e.g. for a FUN
with an SRT:
StgInfoTable +------+
info->layout.ptrs | ... |
info->layout.nptrs | ... |
info->srt | ------------> pointer to SRT object
info->type | ... |
|------|
USE_SRT_OFFSET
Requires:
- tables-next-to-code enabled
In this case we use the info->srt to encode whether or not there is an SRT and
if so encode the offset to its location in info->f.srt_offset:
- info->srt is a half-word
- info->f.srt_offset is a 32-bit int
- info->srt is 0 if there's no SRT, otherwise,
- info->srt == 1 and info->f.srt_offset is a offset to the SRT, relative to the
field address itself
e.g. for a FUN with an SRT:
StgFunInfoTable +------+
info->f.srt_offset | ------------> offset to SRT object
StgInfoTable +------+
info->layout.ptrs | ... |
info->layout.nptrs | ... |
info->srt | 1 |
info->type | ... |
|------|
USE_INLINE_SRT_FIELD
Requires:
- tables-next-to-code enabled
- 64-bit architecture
- small memory model
We optimise the info table representation further. The offset to the SRT can
be stored in 32 bits (all code lives within a 2GB region in x86_64's small
memory model), so we can save a word in the info table by storing the
srt_offset in the srt field, which is half a word.
- info->srt is a half-word
- info->srt is 0 if there's no SRT, otherwise:
- info->srt is an offset from the info pointer to the SRT object
StgInfoTable +------+
info->layout.ptrs | |
info->layout.nptrs | |
info->srt | ------------> offset to SRT object
|------|
EXAMPLE
^^^^^^^
f = \x. ... g ...
where
g = \y. ... h ... c1 ...
h = \z. ... c2 ...
c1 & c2 are CAFs
g and h are local functions, but they have no static closures. When
we generate code for f, we start with a CmmGroup of four CmmDecls:
[ f_closure, f_entry, g_entry, h_entry ]
we process each CmmDecl separately in cpsTop, giving us a list of
CmmDecls. e.g. for f_entry, we might end up with
[ f_entry, f1_ret, f2_proc ]
where f1_ret is a return point, and f2_proc is a proc-point. We have
a CAFSet for each of these CmmDecls, let's suppose they are
[ f_entry{g_info}, f1_ret{g_info}, f2_proc{} ]
[ g_entry{h_info, c1_closure} ]
[ h_entry{c2_closure} ]
Next, we make an SRT for each of these functions:
f_srt : [g_info]
g_srt : [h_info, c1_closure]
h_srt : [c2_closure]
Now, for g_info and h_info, we want to refer to the SRTs for g and h
respectively, which we'll label g_srt and h_srt:
f_srt : [g_srt]
g_srt : [h_srt, c1_closure]
h_srt : [c2_closure]
Now, when an SRT has a single entry, we don't actually generate an SRT
closure for it, instead we just replace references to it with its
single element. So, since h_srt == c2_closure, we have
f_srt : [g_srt]
g_srt : [c2_closure, c1_closure]
h_srt : [c2_closure]
and the only SRT closure we generate is
g_srt = SRT_2 [c2_closure, c1_closure]
Algorithm
^^^^^^^^^
0. let srtMap :: Map CAFfyLabel (Maybe SRTEntry) = {}
Maps closures to their SRT entries (i.e. how they appear in a SRT payload)
1. Start with decls :: [CmmDecl]. This corresponds to an SCC of bindings in STG
after code-generation.
2. CPS-convert each CmmDecl (GHC.Cmm.Pipeline.cpsTop), resulting in a list
[CmmDecl]. There might be multiple CmmDecls in the result, due to proc-point
splitting.
3. In cpsTop, *before* proc-point splitting, when we still have a single
CmmDecl, we do cafAnal for procs:
* cafAnal performs a backwards analysis on the code blocks
* For each labelled block, the analysis produces a CAFSet (= Set CAFfyLabel),
representing all the CAFfyLabels reachable from this label.
* A label is added to the set if it refers to a FUN, THUNK, or RET,
and its CafInfo /= NoCafRefs.
(NB. all CafInfo for Ids in the current module should be initialised to
MayHaveCafRefs)
* The result is CAFEnv = LabelMap CAFSet
(Why *before* proc-point splitting? Because the analysis needs to propagate
information across branches, and proc-point splitting turns branches into
CmmCalls to top-level CmmDecls. The analysis would fail to find all the
references to CAFFY labels if we did it after proc-point splitting.)
For static data, cafAnalData simply returns set of all labels that refer to a
FUN, THUNK, and RET whose CafInfos /= NoCafRefs.
4. The result of cpsTop is (CAFEnv, [CmmDecl]) for procs and (CAFSet, CmmDecl)
for static data. So after `mapM cpsTop decls` we have
[Either (CAFEnv, [CmmDecl]) (CAFSet, CmmDecl)]
5. For procs concat the decls and union the CAFEnvs to get (CAFEnv, [CmmDecl])
6. For static data generate a Map CLabel CAFSet (maps static data to their CAFSets)
7. Dependency-analyse the decls using CAFEnv and CAFSets, giving us SCC CAFfyLabel
8. For each SCC in dependency order
- Let lbls :: [CAFfyLabel] be the non-recursive labels in this SCC
- Apply CAFEnv to each label and concat the result :: [CAFfyLabel]
- For each CAFfyLabel in the set apply srtMap (and ignore Nothing) to get
srt :: [SRTEntry]
- Make a label for this SRT, call it l
- If the SRT is not empty (i.e. the group is CAFFY) add FUN_STATICs in the
group to the SRT (see Note [Invalid optimisation: shortcutting])
- Add to srtMap: lbls -> if null srt then Nothing else Just l
9. At the end, update the IdInfo for every top-level binding x:
if srtMap x == Nothing, then the binding is non-CAFFY, otherwise it is
CAFFY.
Optimisations
^^^^^^^^^^^^^
To reduce the code size overhead and the cost of traversing SRTs in
the GC, we want to simplify SRTs where possible. We therefore apply
the following optimisations. Each has a [keyword]; search for the
keyword in the code below to see where the optimisation is
implemented.
1. [Inline] we never create an SRT with a single entry, instead we
point to the single entry directly from the info table.
i.e. instead of
+------+
| info |
| | +-----+---+---+
| -------->|SRT_1| | | 0 |
|------| +-----+-|-+---+
| | |
| code | |
| | v
C
we can point directly to the closure:
+------+
| info |
| |
| -------->C
|------|
| |
| code |
| |
Furthermore, the SRT for any code that refers to this info table
can point directly to C.
The exception to this is when we're doing dynamic linking. In that
case, if the closure is not locally defined then we can't point to
it directly from the info table, because this is the text section
which cannot contain runtime relocations. In this case we skip this
optimisation and generate the singleton SRT, because SRTs are in the
data section and *can* have relocatable references.
2. [FUN] A static function closure can also be an SRT, we simply put
the SRT entries as fields in the static closure. This makes a lot
of sense: the static references are just like the free variables of
the FUN closure.
i.e. instead of
f_closure:
+-----+---+
| | | 0 |
+- |--+---+
| +------+
| | info | f_srt:
| | | +-----+---+---+---+
| | -------->|SRT_2| | | | + 0 |
`----------->|------| +-----+-|-+-|-+---+
| | | |
| code | | |
| | v v
We can generate:
f_closure:
+-----+---+---+---+
| | | | | | | 0 |
+- |--+-|-+-|-+---+
| | | +------+
| v v | info |
| | |
| | 0 |
`----------->|------|
| |
| code |
| |
(note: we can't do this for THUNKs, because the thunk gets
overwritten when it is entered, so we wouldn't be able to share
this SRT with other info tables that want to refer to it (see
[Common] below). FUNs are immutable so don't have this problem.)
3. [Common] Identical SRTs can be commoned up.
4. [Filter] If an SRT A refers to an SRT B and a closure C, and B also
refers to C (perhaps transitively), then we can omit the reference
to C from A.
Note that there are many other optimisations that we could do, but
aren't implemented. In general, we could omit any reference from an
SRT if everything reachable from it is also reachable from the other
fields in the SRT. Our [Filter] optimisation is a special case of
this.
Another opportunity we don't exploit is this:
A = {X,Y,Z}
B = {Y,Z}
C = {X,B}
Here we could use C = {A} and therefore [Inline] C = A.