An overhaul of the SRT representation

Summary:
- Previously we would hvae a single big table of pointers per module,
  with a set of bitmaps to reference entries within it. The new
  representation is identical to a static constructor, which is much
  simpler for the GC to traverse, and we get to remove the complicated
  bitmap-traversal code from the GC.

- Rewrite all the code to generate SRTs in CmmBuildInfoTables, and
  document it much better (see Note [SRTs]). This has been something
  I've wanted to do since we moved to the new code generator, I
  finally had the opportunity to finish it while on a transatlantic
  flight recently :)

There are a series of 4 diffs:

1. D4632 (this one), which does the bulk of the changes

2. D4633 which adds support for smaller `CmmLabelDiffOff` constants

3. D4634 which takes advantage of D4632 and D4633 to save a word in
   info tables that have an SRT on x86_64. This is where most of the
   binary size improvement comes from.

4. D4637 which makes a further optimisation to merge some SRTs with
   static FUN closures.  This adds some complexity and the benefits
   are fairly modest, so it's not clear yet whether we should do this.

Results (after (3), on x86_64)

- GHC itself (staticaly linked) is 5.2% smaller

- -1.7% binary sizes in nofib, -2.9% module sizes. Full nofib results: P176

- I measured the overhead of traversing all the static objects in a
  major GC in GHC itself by doing `replicateM_ 1000 performGC` as the
  first thing in `Main.main`.  The new version was 5-10% faster, but
  the results did vary quite a bit.

- I'm not sure if there's a compile-time difference, the results are
  too unreliable.

Test Plan: validate

Reviewers: bgamari, michalt, niteria, simonpj, erikd, osa1

Subscribers: thomie, carter

Differential Revision: https://phabricator.haskell.org/D4632

3 files changed, 32 insertions, 39 deletions

diff --git a/includes/rts/storage/ClosureMacros.h b/includes/rts/storage/ClosureMacros.h
index be1569ba8e..2b78ab44b8 100644
--- a/includes/rts/storage/ClosureMacros.h
+++ b/includes/rts/storage/ClosureMacros.h
@@ -109,7 +109,7 @@ INLINE_HEADER const StgConInfoTable *get_con_itbl(const StgClosure *c)
 
 INLINE_HEADER StgHalfWord GET_TAG(const StgClosure *con)
 {
-    return get_itbl(con)->srt_bitmap;
+    return get_itbl(con)->has_srt;
 }
 
 /* -----------------------------------------------------------------------------
diff --git a/includes/rts/storage/InfoTables.h b/includes/rts/storage/InfoTables.h
index c621e5e749..0e25e14c8e 100644
--- a/includes/rts/storage/InfoTables.h
+++ b/includes/rts/storage/InfoTables.h
@@ -124,31 +124,6 @@ typedef struct {
   StgWord bitmap[];
 } StgLargeBitmap;
 
-/* -----------------------------------------------------------------------------
-   SRTs  (Static Reference Tables)
-
-   These tables are used to keep track of the static objects referred
-   to by the code for a closure or stack frame, so that we can follow
-   static data references from code and thus accurately
-   garbage-collect CAFs.
-   -------------------------------------------------------------------------- */
-
-/* An SRT is just an array of closure pointers: */
-typedef StgClosure* StgSRT[];
-
-/*
- * Each info table refers to some subset of the closure pointers in an
- * SRT.  It does this using a pair of an StgSRT pointer and a
- * half-word bitmap.  If the half-word bitmap isn't large enough, then
- * we fall back to a large SRT, including an unbounded bitmap.  If the
- * half-word bitmap is set to all ones (0xffff), then the StgSRT
- * pointer instead points to an StgLargeSRT:
- */
-typedef struct StgLargeSRT_ {
-    StgSRT *srt;
-    StgLargeBitmap l;
-} StgLargeSRT;
-
 /* ----------------------------------------------------------------------------
    Info Tables
    ------------------------------------------------------------------------- */
@@ -194,11 +169,11 @@ typedef struct StgInfoTable_ {
     StgClosureInfo  layout;     /* closure layout info (one word) */
 
     StgHalfWord     type;       /* closure type */
-    StgHalfWord     srt_bitmap;
+    StgHalfWord     has_srt;
        /* In a CONSTR:
             - the constructor tag
           In a FUN/THUNK
-            - a bitmap of SRT entries
+            - non-zero if there is an SRT
        */
 
 #if defined(TABLES_NEXT_TO_CODE)
@@ -217,7 +192,7 @@ typedef struct StgInfoTable_ {
       and bitmap fields may be left out (they are at the end, so omitting
       them doesn't affect the layout).
 
-   -  If srt_bitmap (in the std info table part) is zero, then the srt
+   -  If has_srt (in the std info table part) is zero, then the srt
       field needn't be set.  This only applies if the slow_apply and
       bitmap fields have also been omitted.
    -------------------------------------------------------------------------- */
@@ -239,7 +214,7 @@ typedef struct StgFunInfoExtraRev_ {
         StgWord bitmap;
         OFFSET_FIELD(bitmap_offset);    /* arg ptr/nonptr bitmap */
     } b;
-    OFFSET_FIELD(srt_offset);   /* pointer to the SRT table */
+    OFFSET_FIELD(srt_offset);   /* pointer to the SRT closure */
     StgHalfWord    fun_type;    /* function type */
     StgHalfWord    arity;       /* function arity */
 } StgFunInfoExtraRev;
@@ -247,7 +222,7 @@ typedef struct StgFunInfoExtraRev_ {
 typedef struct StgFunInfoExtraFwd_ {
     StgHalfWord    fun_type;    /* function type */
     StgHalfWord    arity;       /* function arity */
-    StgSRT         *srt;        /* pointer to the SRT table */
+    StgClosure    *srt;         /* pointer to the SRT closure */
     union { /* union for compat. with TABLES_NEXT_TO_CODE version */
         StgWord        bitmap;  /* arg ptr/nonptr bitmap */
     } b;
@@ -273,16 +248,16 @@ extern const StgWord stg_arg_bitmaps[];
 
 /*
  * When info tables are laid out backwards, we can omit the SRT
- * pointer iff srt_bitmap is zero.
+ * pointer iff has_srt is zero.
  */
 
 typedef struct {
 #if defined(TABLES_NEXT_TO_CODE)
-    OFFSET_FIELD(srt_offset);   /* offset to the SRT table */
+    OFFSET_FIELD(srt_offset);   /* offset to the SRT closure */
     StgInfoTable i;
 #else
     StgInfoTable i;
-    StgSRT      *srt;   /* pointer to the SRT table */
+    StgClosure  *srt;           /* pointer to the SRT closure */
 #endif
 } StgRetInfoTable;
 
@@ -292,7 +267,7 @@ typedef struct {
 
 /*
  * When info tables are laid out backwards, we can omit the SRT
- * pointer iff srt_bitmap is zero.
+ * pointer iff has_srt is zero.
  */
 
 typedef struct StgThunkInfoTable_ {
@@ -300,9 +275,9 @@ typedef struct StgThunkInfoTable_ {
     StgInfoTable i;
 #endif
 #if defined(TABLES_NEXT_TO_CODE)
-    OFFSET_FIELD(srt_offset);   /* offset to the SRT table */
+    OFFSET_FIELD(srt_offset);   /* offset to the SRT closure */
 #else
-    StgSRT         *srt;        /* pointer to the SRT table */
+    StgClosure  *srt;           /* pointer to the SRT closure */
 #endif
 #if defined(TABLES_NEXT_TO_CODE)
     StgInfoTable i;
@@ -340,7 +315,8 @@ typedef struct StgConInfoTable_ {
  * info must be a Stg[Ret|Thunk]InfoTable* (an info table that has a SRT)
  */
 #if defined(TABLES_NEXT_TO_CODE)
-#define GET_SRT(info) ((StgSRT*) (((StgWord) ((info)+1)) + (info)->srt_offset))
+#define GET_SRT(info) \
+  ((StgClosure*) (((StgWord) ((info)+1)) + (info)->srt_offset))
 #else
 #define GET_SRT(info) ((info)->srt)
 #endif
@@ -361,7 +337,8 @@ typedef struct StgConInfoTable_ {
  * info must be a StgFunInfoTable*
  */
 #if defined(TABLES_NEXT_TO_CODE)
-#define GET_FUN_SRT(info) ((StgSRT*) (((StgWord) ((info)+1)) + (info)->f.srt_offset))
+#define GET_FUN_SRT(info) \
+  ((StgClosure*) (((StgWord) ((info)+1)) + (info)->f.srt_offset))
 #else
 #define GET_FUN_SRT(info) ((info)->f.srt)
 #endif
diff --git a/includes/stg/MiscClosures.h b/includes/stg/MiscClosures.h
index 1fbfab9fbe..758ec1f51e 100644
--- a/includes/stg/MiscClosures.h
+++ b/includes/stg/MiscClosures.h
@@ -153,6 +153,22 @@ RTS_ENTRY(stg_END_STM_CHUNK_LIST);
 RTS_ENTRY(stg_NO_TREC);
 RTS_ENTRY(stg_COMPACT_NFDATA_CLEAN);
 RTS_ENTRY(stg_COMPACT_NFDATA_DIRTY);
+RTS_ENTRY(stg_SRT_1);
+RTS_ENTRY(stg_SRT_2);
+RTS_ENTRY(stg_SRT_3);
+RTS_ENTRY(stg_SRT_4);
+RTS_ENTRY(stg_SRT_5);
+RTS_ENTRY(stg_SRT_6);
+RTS_ENTRY(stg_SRT_7);
+RTS_ENTRY(stg_SRT_8);
+RTS_ENTRY(stg_SRT_9);
+RTS_ENTRY(stg_SRT_10);
+RTS_ENTRY(stg_SRT_11);
+RTS_ENTRY(stg_SRT_12);
+RTS_ENTRY(stg_SRT_13);
+RTS_ENTRY(stg_SRT_14);
+RTS_ENTRY(stg_SRT_15);
+RTS_ENTRY(stg_SRT_16);
 
 /* closures */