Populate WordLang's non-GCed cutsets with known non-pointers

[tanyongkiam]

Populate WordLang's non-GCed cutsets with known non-pointers

Summary

WordLang cutsets already distinguish a non-GCed set from a GCed set:

Type cutsets = “:num_set # num_set” (* non-GCed cutset, GCed cutset *)

However, data_to_word currently constructs them as:

adjust_sets names = (LS (), adjust_set names)

Thus, apart from the special return-location entry in FST, every live
DataLang variable is placed in SND, including values statically known to be
tagged immediates. Populate FST with live values that are proven not to be
movable heap pointers, leaving all unknown values in SND.

This is useful independently of any change to register allocation or calling
conventions: word_to_stack$wLive constructs GC stack bitmaps from SND only.
Removing known non-pointers from that set prevents the collector from loading,
testing, and writing back those stack entries at every collection.

Example

datatype audit_box = AuditBox int;
datatype audit_flag = AuditNo | AuditYes;
datatype audit_result = AuditNeither audit_box
                      | AuditFirst audit_box
                      | AuditBoth audit_box;

fun audit_f x =
  let
    val first = case x of 10 => AuditYes | _ => AuditNo
    val second = case x of 20 => AuditYes | _ => AuditNo
    val box = AuditBox x
  in
    case first of
      AuditYes =>
        (case second of
           AuditYes => AuditBoth box
         | AuditNo => AuditFirst box)
    | AuditNo => AuditNeither box
  end;

val audit_result = audit_f 1;

For x64-64, the current data_to_word output contains:

(if (Equal 2 (Imm 0x28)) ... (12 := (Const 0x12)) ... (12 := (Const 0x2)))
(if (Equal 2 (Imm 0x50)) ... (22 := (Const 0x12)) ... (22 := (Const 0x2)))
...
(alloc 1 ({0} {2,12,22}))

Variables 12 and 22 can only contain 0x2 or 0x12, the immediate
representations of the two nullary constructors. They cannot be heap pointers
and cannot be changed by GC. Variable 2, on the other hand, is the unknown
integer argument and may be represented by a heap-allocated bignum.

The useful cutset partition at this allocation is therefore:

(alloc 1 ({0,12,22} {2}))

In this small example that reduces the source-variable root set at the
allocation from three entries to one. Similar cases occur when booleans,
nullary constructors, Word8 values, lengths, comparison results, and other
known immediates remain live across an allocation or returning call.

Correctness requirement

Membership in FST must mean that the represented word is guaranteed to be
unchanged by GC on every path reaching that cutset. It is not enough for a
value merely to look unlike a tagged pointer at one program point. In
particular, a raw address derived from a movable heap pointer must remain GCed
or must not survive the collection at all.

A conservative analysis can start with operations whose lowering guarantees
an immediate result, propagate the property through moves, retain it at a join
only when it holds on every incoming path, and treat unknown function
parameters and call results as GCed. Ordinary integer arithmetic must remain
unknown unless a separate fact proves its result is a small integer.

For every cutset, the new sets should be disjoint and their union should equal
the live set that the compiler preserves today. Unsound or unavailable facts
must simply leave a variable in SND.

Existing infrastructure

• wordLang$cutsets already has the required two components.
• data_to_word$adjust_sets is where all ordinary live variables are currently put in SND.
• wordSem$push_env preserves the two components separately.
• word_to_stack$wLive writes a bitmap from SND live only.
• The stack GC's bitmap loop processes the selected roots in stack_allocScript.sml.

Relationship to existing issues

The original problem reported in #1042 was fixed by CakeML commits
21c979ff8 and 63b46f568, and #1042 is now closed. The separate opportunity
to rematerialise constants closer to their uses is tracked by #1455. Those
issues reduce which variables are live at a cut point; neither partitions
variables which really are live between the non-GCed and GCed components
proposed here.

It is also a prerequisite that could later help #761 use proven non-pointers in
call-saved registers under full GC, but no calling-convention or register-allocation
change is needed to obtain the GC-root-scanning benefit described here.

Expected result

• Definitely GC-invariant live values are placed in FST at allocations,
  returning calls, FFI operations, and installation points.
• Potential heap pointers remain in SND.
• Existing simple and generational collectors continue to work unchanged.
• A regression based on the example above shows 12 and 22 in FST and
  only 2 in SND at the first allocation.
• GC-heavy benchmarks are used to measure the reduction in processed stack
  roots and its runtime effect.

Written by Codex (OpenAI).