CakeML / CakeML/cakeml

Reduce DataLang cutsets by rematerialising constants closer to use

Open
#1,455 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Standard ML
Stars
1.2k
Forks
104
Avg merge
2d 21h
Merged PRs (30d)
16

Description

# Reduce DataLang cutsets by rematerialising constants closer to use

This follow-up was originally reported in a comment on #1042. The original
problem in #1042 has been fixed, but this is a separate remaining opportunity.

`bvi_to_data` can compute cheap constant arguments early, leaving them live
across later operations which carry cutsets. For example, this BVI tail call:

```text
(func parse_vb_string@3246 (a)
(call parse_vb_string_aux@3240 (op (Cons 0))
(op (Const 0)) (op (Const 1))
(let
(b <- (op Add (op LengthByte (var a)) (op (Const ~1))))
(if (op Less (op (Const 0)) (var b)) (op (Const 0)) (var b)))
(op (Const 0)) (var a)))
```

was lowered to DataLang in this shape:

```text
(func parse_vb_string@3246 (0)
(seq
(1 := (Cons 0) () none)
(2 := (Const 0) () none)
(3 := (Const 1) () none)
(4 := LengthByte (0) none)
(5 := (Const ~1) () none)
(6 := Add (5 4) (some {0,1,2,3,4,5}))
(7 := (Const 0) () none)
(8 := Less (6 7) (some {0,1,2,3,6,7}))
(if 8
(seq
(9 := (Const 0) () none)
(10 := 9))
(10 := 6))
(11 := (Const 0) () none)
(call none parse_vb_string_aux@3240 (1 2 3 10 11 0) none)))
```

The constants in variables `1`, `2`, and `3` are created before the
`LengthByte`, `Add`, and `Less` computations, so they unnecessarily remain in
the intervening cutsets even though they are cheap to construct immediately
before the final call.

One approach discussed with @myreen was constant propagation/rematerialisation
before `data_live`. Another related opportunity is for `bvi_to_data` to compute
arguments which induce cutsets before cheap arguments that can safely be
computed later. Any reordering must, of course, preserve the language's
evaluation-order, exception, and effect requirements.

The expected result for examples of this form is that cheap constants are
materialised near their eventual use and do not enlarge unrelated intervening
cutsets.

_Original observation and example by @tanyongkiam; issue text organized by Codex (OpenAI)._

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reading the bvi_to_data lowering around data_live and inspect how cutsets are formed for the shown tail-call example. Compare constant propagation/rematerialisation with argument reordering, while checking evaluation order, exceptions, and effects. Done means cheap constants are materialised near their eventual call use without enlarging unrelated intervening cutsets.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.