Populate WordLang's non-GCed cutsets with known non-pointers
- Dominant language
- Standard ML
- Stars
- 1.2k
- Forks
- 104
- Avg merge
- 2d 21h
- Merged PRs (30d)
- 16
Description
# Populate WordLang's non-GCed cutsets with known non-pointers
## Summary
WordLang cutsets already distinguish a non-GCed set from a GCed set:
```sml
Type cutsets = “:num_set # num_set” (* non-GCed cutset, GCed cutset *)
```
However, `data_to_word` currently constructs them as:
```sml
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
```sml
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:
```text
(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:
```text
(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`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/wordLangScript.sml#L33) already has the required two components.
- [`data_to_word$adjust_sets`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/data_to_wordScript.sml#L43-L50) is where all ordinary live variables are currently put in `SND`.
- [`wordSem$push_env`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/semantics/wordSemScript.sml#L517-L535) preserves the two components separately.
- [`word_to_stack$wLive`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/word_to_stackScript.sml#L253-L257) writes a bitmap from `SND live` only.
- The stack GC's bitmap loop processes the selected roots in [`stack_allocScript.sml`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/stack_allocScript.sml#L98-L110).
## 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)._
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with data_to_wordScript.sml:43-50 and inspect how adjust_sets builds cutsets, then trace wordSem$push_env and word_to_stack$wLive. Use the audit_f example as a regression case; done means proven non-pointers reach FST, unknown values remain in SND, the sets stay disjoint and complete, and existing collectors continue to work.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 48/100