Skip to content

Literals v3

Jump to bottom
John Reppy edited this page Sep 23, 2026 · 10 revisions

Overview

This document describes Version 3 of the bytecode for generating heap-allocated literals in the SML/NJ compiler. It replaces the previous bytecode and was introduced as part of the support for future improvements, such as 64-bit support, Real32, and better Int64 and IntInf integration.

The Literal Bytecode Machine

The runtime system implements a simple stack machine for constructing a per-compilation-unit literal record. The stack contains five kinds of values: tagged integers, raw numbers (either integers or reals), heap-allocated bignums, heap-allocated vectors (both polymorphic and monomorphic), and heap-allocated records (uniform, mixed, or raw). We distinguish between uniform values (i.e., tagged ints and heap objects) and raw values. Sharing of heap-allocated objects is supported using a scratch memory.

The result of running a correct literal program should be either the tagged integer 0 (i.e., the representation of the unit value) or a record object. The final instruction of the program should be a RETURN operation that returns the value on the top of the stack.

Note that construction of "wrapped" literals will be represented by the combination of a raw value followed by creation of a raw record containing the value.

Compilation

The compiler extracts the literal values from the CPS IR and generates a program for building a record of literal values. Direct references to literal values in the CPS code are replaced by references to components of the literal record. The binary data representing the literal-construction program is packaged as part of the [[Binfile|New-Binfile-Format-and-Linking]] generated by the compiler.

Endianness

Multiple byte quantities are represented in big-endian form (most-significant byte first).

Header

The first four 32-bit words of the literal representation correspond to the following C struct:

struct literal_header {
    uint32_t    magic;
    uint32_t    maxstk;
    uint32_t    wordsz;
    uint32_t    maxsaved;
};

where

  • magic contains the version ID (which should be 0x20260912)

  • maxstk is the maximum stack depth required, and

  • wordsz is the size of an ML value (should be 64)

  • maxsaved is the number of saved literals (used for sharing)

Note that Version 1 files have the version ID 0x19981022 and have the first two header fields, but not the wordsz or numsaved fields. Version 2 files have the same header structure, but the version ID will be 0x20190921. The Version 3 format was introduced in SML/NJ Version 2026.3.

Opcode Semantics

The following is a list of the symbolic opcodes used in the interpreter and their semantics. When constructing an aggregate value (e.g., a record) from values on the stack, the topmost value will be the last element in the aggregate. The encoding of these is described below.

  • INT63($n$) push a tagged integer literal. The value n should be in the range $-2^{62}$ to $2^{62}-1$ when encoded as a $63$-bit 2’s complement integer.

  • INT64($n$) push raw 64-bit integer literal. The value n should be in the range $-2^{63}$ to $2^{63}-1$ when encoded as a $64$-bit 2’s complement integer.

  • RAWINT($64,n$) push a raw 64-bit integer literal. The value n should be in the range $-2^{63}$ to $2^{63}-1$ when encoded as a $w$-bit 2’s complement integer.

  • STR8($n$) construct a $n$-character string literal from the instruction stream and pushes it on the stack.

  • REAL64($d$) push a raw 64-bit floating-point literal, which is taken from the instruction stream.

  • RECORD($n$) pop $n$ values, construct a record from them, and push it on the stack. The values should be uniform values.

  • RAW($n$) pop $n$ values, construct a raw vector from them, and push it on the stack. The values should be raw values.

  • MIXED($n,m$) pop $n+m$ values, construct a mixed record from them, and push it on the stack. The topmost $m$ values should be either raw or tagged integers (i.e., not heap objects). The next $n$ values should be uniform values.

  • VEC($n$) pop $n$ values, construct a vector from them, and push it on the stack. The values should be uniform values.

  • CONCAT($n$) pop $n$ records/vectors from the stack, concatenate them into a single record/vector, and push the result on the stack. This operation allows the implementation to avoid excessively large stacks when building very large record/vector literals.

  • SAVE($i$) save the top of the stack in the ith save slot, which allows it to be shared by some subsequent aggregate literal. The saved value should be a heap object. Note that this operation does not pop the stack.

  • LOAD($i$) push the ith saved literal on the stack.

  • RETURN signals the end of the program; the stack depth should be one and that value is popped and returned as the result.

  • UNUSED represents unused opcodes.

Future extensions

The following opcodes are not currently generated by the compiler, but are reserved for future use.

  • RAWINT($k,n$) pushes a raw $k$-bit integer literal, where $k$ is one of $8$, $16$, or $32$. The value n should be in the range $-2^{k-1}$ to $2^{k-1}-1$ when encoded as a $w$-bit 2’s complement integer.

  • BIGINT($sgn,n$) pop $n$ integer literals, and then create and push a bignum from them; $sgn$ is true for negative numbers and false for positive numbers (currently not used).

  • REAL32($f$) pushes a raw 32-bit floating-point literal, which is taken from the instruction stream.

  • UTF8($n$) constructs an $n$-character wide-string literal from the instruction stream and pushes it on the stack. The string literal is encoded using the UTF-8 variable-length encoding.

  • RAWVEC($k,n$) construct a raw vector of $n$ $k$-bit elements from the instruction stream and push it on the stack.

Instruction encoding

Opcode Format

The opcodes are organized into three classes based on the two most-significant bits (MSB):

  • 00 — these are small tagged integers. The remaining six bits are treated as a 2’s complement 6-bit integer.

  • 01 — these are small 64-bit integers. The remaining six bits are treated as a 2’s complement 6-bit integer.

  • 10 and 11 — all other opcodes

Notation

In the encoding below, we use the following conventions:

  • b represents a signed 8-bit integer.

  • ub represents an unsigned 8-bit integer.

  • c represents a 8-bit character.

  • h represents a signed 16-bit integer.

  • uh represents an unsigned 16-bit integer.

  • w represents a signed 32-bit integer.

  • uw represents an unsigned 32-bit integer.

  • l represents a signed 64-bit integer.

  • ul represents an unsigned 64-bit integer.

  • f represents a 32-bit floating-point literal.

  • d represents a 64-bit floating-point literal.

Encoding

Opcode (bits) Opcode (hex) Length Operation Description

00000000

0x00

$1$

INT63(0)

push tagged literal value 0

00000001

0x01

$1$

INT63(1)

push tagged literal value 1

00000010

0x02

$1$

INT63(2)

push tagged literal value 2

00000011

0x03

$1$

INT63(3)

push tagged literal value 3

00000100

0x04

$1$

INT63(4)

push tagged literal value 4

00000101

0x05

$1$

INT63(5)

push tagged literal value 5

00000110

0x06

$1$

INT63(6)

push tagged literal value 6

00000111

0x07

$1$

INT63(7)

push tagged literal value 7

00001000

0x08

$1$

INT63(8)

push tagged literal value 8

00001001

0x09

$1$

INT63(9)

push tagged literal value 9

00001010

0x0A

$1$

INT63(10)

push tagged literal value 10

00001011

0x0B

$1$

INT63(11)

push tagged literal value 11

00001100

0x0C

$1$

INT63(12)

push tagged literal value 12

00001101

0x0D

$1$

INT63(13)

push tagged literal value 13

00001110

0x0E

$1$

INT63(14)

push tagged literal value 14

00001111

0x0F

$1$

INT63(15)

push tagged literal value 15

00010000

0x10

$1$

INT63(16)

push tagged literal value 16

00010001

0x11

$1$

INT63(17)

push tagged literal value 17

00010010

0x12

$1$

INT63(18)

push tagged literal value 18

00010011

0x13

$1$

INT63(19)

push tagged literal value 19

00010100

0x14

$1$

INT63(20)

push tagged literal value 20

00010101

0x15

$1$

INT63(21)

push tagged literal value 21

00010110

0x16

$1$

INT63(22)

push tagged literal value 22

00010111

0x17

$1$

INT63(23)

push tagged literal value 23

00011000

0x18

$1$

INT63(24)

push tagged literal value 24

00011001

0x19

$1$

INT63(25)

push tagged literal value 25

00011010

0x1A

$1$

INT63(26)

push tagged literal value 26

00011011

0x1B

$1$

INT63(27)

push tagged literal value 27

00011100

0x1C

$1$

INT63(28)

push tagged literal value 28

00011101

0x1D

$1$

INT63(29)

push tagged literal value 29

00011110

0x1E

$1$

INT63(30)

push tagged literal value 30

00011111

0x1F

$1$

INT63(31)

push tagged literal value 31

00100000

0x20

$1$

INT63(~32)

push tagged literal value ~32

00100001

0x21

$1$

INT63(~31)

push tagged literal value ~31

00100010

0x22

$1$

INT63(~30)

push tagged literal value ~30

00100011

0x23

$1$

INT63(~29)

push tagged literal value ~29

00100100

0x24

$1$

INT63(~28)

push tagged literal value ~28

00100101

0x25

$1$

INT63(~27)

push tagged literal value ~27

00100110

0x26

$1$

INT63(~26)

push tagged literal value ~26

00100111

0x27

$1$

INT63(~25)

push tagged literal value ~25

00101000

0x28

$1$

INT63(~24)

push tagged literal value ~24

00101001

0x29

$1$

INT63(~23)

push tagged literal value ~23

00101010

0x2A

$1$

INT63(~22)

push tagged literal value ~22

00101011

0x2B

$1$

INT63(~21)

push tagged literal value ~21

00101100

0x2C

$1$

INT63(~20)

push tagged literal value ~20

00101101

0x2D

$1$

INT63(~19)

push tagged literal value ~19

00101110

0x2E

$1$

INT63(~18)

push tagged literal value ~18

00101111

0x2F

$1$

INT63(~17)

push tagged literal value ~17

00110000

0x30

$1$

INT63(~16)

push tagged literal value ~16

00110001

0x31

$1$

INT63(~15)

push tagged literal value ~15

00110010

0x32

$1$

INT63(~14)

push tagged literal value ~14

00110011

0x33

$1$

INT63(~13)

push tagged literal value ~13

00110100

0x34

$1$

INT63(~12)

push tagged literal value ~12

00110101

0x35

$1$

INT63(~11)

push tagged literal value ~11

00110110

0x36

$1$

INT63(~10)

push tagged literal value ~10

00110111

0x37

$1$

INT63(~9)

push tagged literal value ~9

00111000

0x38

$1$

INT63(~8)

push tagged literal value ~8

00111001

0x39

$1$

INT63(~7)

push tagged literal value ~7

00111010

0x3A

$1$

INT63(~6)

push tagged literal value ~6

00111011

0x3B

$1$

INT63(~5)

push tagged literal value ~5

00111100

0x3C

$1$

INT63(~4)

push tagged literal value ~4

00111101

0x3D

$1$

INT63(~3)

push tagged literal value ~3

00111110

0x3E

$1$

INT63(~2)

push tagged literal value ~2

00111111

0x3F

$1$

INT63(~1)

push tagged literal value ~1

01000000

0x40

$1$

INT64(0)

push 64-bit raw literal value 0

01000001

0x41

$1$

INT64(1)

push 64-bit raw literal value 1

01000010

0x42

$1$

INT64(2)

push 64-bit raw literal value 2

01000011

0x43

$1$

INT64(3)

push 64-bit raw literal value 3

01000100

0x44

$1$

INT64(4)

push 64-bit raw literal value 4

01000101

0x45

$1$

INT64(5)

push 64-bit raw literal value 5

01000110

0x46

$1$

INT64(6)

push 64-bit raw literal value 6

01000111

0x47

$1$

INT64(7)

push 64-bit raw literal value 7

01001000

0x48

$1$

INT64(8)

push 64-bit raw literal value 8

01001001

0x49

$1$

INT64(9)

push 64-bit raw literal value 9

01001010

0x4A

$1$

INT64(10)

push 64-bit raw literal value 10

01001011

0x4B

$1$

INT64(11)

push 64-bit raw literal value 11

01001100

0x4C

$1$

INT64(12)

push 64-bit raw literal value 12

01001101

0x4D

$1$

INT64(13)

push 64-bit raw literal value 13

01001110

0x4E

$1$

INT64(14)

push 64-bit raw literal value 14

01001111

0x4F

$1$

INT64(15)

push 64-bit raw literal value 15

01010000

0x50

$1$

INT64(16)

push 64-bit raw literal value 16

01010001

0x51

$1$

INT64(17)

push 64-bit raw literal value 17

01010010

0x52

$1$

INT64(18)

push 64-bit raw literal value 18

01010011

0x53

$1$

INT64(19)

push 64-bit raw literal value 19

01010100

0x54

$1$

INT64(20)

push 64-bit raw literal value 20

01010101

0x55

$1$

INT64(21)

push 64-bit raw literal value 21

01010110

0x56

$1$

INT64(22)

push 64-bit raw literal value 22

01010111

0x57

$1$

INT64(23)

push 64-bit raw literal value 23

01011000

0x58

$1$

INT64(24)

push 64-bit raw literal value 24

01011001

0x59

$1$

INT64(25)

push 64-bit raw literal value 25

01011010

0x5A

$1$

INT64(26)

push 64-bit raw literal value 26

01011011

0x5B

$1$

INT64(27)

push 64-bit raw literal value 27

01011100

0x5C

$1$

INT64(28)

push 64-bit raw literal value 28

01011101

0x5D

$1$

INT64(29)

push 64-bit raw literal value 29

01011110

0x5E

$1$

INT64(30)

push 64-bit raw literal value 30

01011111

0x5F

$1$

INT64(31)

push 64-bit raw literal value 31

01100000

0x60

$1$

INT64(~32)

push 64-bit raw literal value ~32

01100001

0x61

$1$

INT64(~31)

push 64-bit raw literal value ~31

01100010

0x62

$1$

INT64(~30)

push 64-bit raw literal value ~30

01100011

0x63

$1$

INT64(~29)

push 64-bit raw literal value ~29

01100100

0x64

$1$

INT64(~28)

push 64-bit raw literal value ~28

01100101

0x65

$1$

INT64(~27)

push 64-bit raw literal value ~27

01100110

0x66

$1$

INT64(~26)

push 64-bit raw literal value ~26

01100111

0x67

$1$

INT64(~25)

push 64-bit raw literal value ~25

01101000

0x68

$1$

INT64(~24)

push 64-bit raw literal value ~24

01101001

0x69

$1$

INT64(~23)

push 64-bit raw literal value ~23

01101010

0x6A

$1$

INT64(~22)

push 64-bit raw literal value ~22

01101011

0x6B

$1$

INT64(~21)

push 64-bit raw literal value ~21

01101100

0x6C

$1$

INT64(~20)

push 64-bit raw literal value ~20

01101101

0x6D

$1$

INT64(~19)

push 64-bit raw literal value ~19

01101110

0x6E

$1$

INT64(~18)

push 64-bit raw literal value ~18

01101111

0x6F

$1$

INT64(~17)

push 64-bit raw literal value ~17

01110000

0x70

$1$

INT64(~16)

push 64-bit raw literal value ~16

01110001

0x71

$1$

INT64(~15)

push 64-bit raw literal value ~15

01110010

0x72

$1$

INT64(~14)

push 64-bit raw literal value ~14

01110011

0x73

$1$

INT64(~13)

push 64-bit raw literal value ~13

01110100

0x74

$1$

INT64(~12)

push 64-bit raw literal value ~12

01110101

0x75

$1$

INT64(~11)

push 64-bit raw literal value ~11

01110110

0x76

$1$

INT64(~10)

push 64-bit raw literal value ~10

01110111

0x77

$1$

INT64(~9)

push 64-bit raw literal value ~9

01111000

0x78

$1$

INT64(~8)

push 64-bit raw literal value ~8

01111001

0x79

$1$

INT64(~7)

push 64-bit raw literal value ~7

01111010

0x7A

$1$

INT64(~6)

push 64-bit raw literal value ~6

01111011

0x7B

$1$

INT64(~5)

push 64-bit raw literal value ~5

01111100

0x7C

$1$

INT64(~4)

push 64-bit raw literal value ~4

01111101

0x7D

$1$

INT64(~3)

push 64-bit raw literal value ~3

01111110

0x7E

$1$

INT64(~2)

push 64-bit raw literal value ~2

01111111

0x7F

$1$

INT64(~1)

push 64-bit raw literal value ~1

10000000

0x80

$2$

INT63($b$)

10000001

0x81

$3$

INT63($h$)

10000010

0x82

$5$

INT63($w$)

10000011

0x83

$9$

INT63($l$)

10000100

0x84

$5$

REAL32($f$)

10000101

0x85

$9$

REAL64($d$)

10000110

0x86

$3$

BIGINT(false, $uh$)

10000111

0x87

$3$

BIGINT(true, $uh$)

10001000

0x88

1

STR8(0)

10001001

0x89

$2+ub$

STR8($ub$)

build an empty string

10001010

0x8A

$2+uh$

STR8($uh$)

build a string

10001011

0x8B

$2+uw$

STR8($uw$)

build a string

10001100

0x8C

$1$

UTF8(0)

build a UTF8 empty wide-string

10001101

0x8D

$2+n$

UTF8($ub$)

build a UTF8 encoded wide-string

10001110

0x8E

$3+n$

UTF8($uh$)

build a UTF8 encoded wide-string

10001111

0x8F

$5+n$

UTF8($uw$)

build a UTF8 encoded wide-string

10010000

0x90

$2$

RAWINT(8,8)

10010001

0x91

$1$

UNUSED

10010010

0x92

$1$

UNUSED

10010011

0x93

$1$

UNUSED

10010100

0x94

$2$

RAWINT(16,8)

10010101

0x95

$3$

RAWINT(16,16)

10010110

0x96

$1$

UNUSED

10010111

0x97

$1$

UNUSED

10011000

0x98

$2$

RAWINT(32,8)

10011001

0x99

$3$

RAWINT(32,16)

10011010

0x9A

$5$

RAWINT(32,32)

10011011

0x9B

$1$

UNUSED

10011100

0x9C

$2$

RAWINT(64,8)

10011101

0x9D

$3$

RAWINT(64,16)

10011110

0x9E

$5$

RAWINT(64,32)

10011111

0x9F

$9$

RAWINT(64,64)

10100000

0xA0

$1$

RECORD(1)

build a one-element record

10100001

0xA1

$1$

RECORD(2)

build a two-element record

10100010

0xA2

$1$

RECORD(3)

build a three-element record

10100011

0xA3

$1$

RECORD(4)

build a four-element record

10100100

0xA4

$1$

RECORD(5)

build a five-element record

10100101

0xA5

$1$

RECORD(6)

build a six-element record

10100110

0xA6

$1$

RECORD(7)

build a seven-element record

10100111

0xA7

$1$

RECORD(8)

build an eight-element record

10101000

0xA8

$1$

RECORD(9)

build a nine-element record

10101001

0xA9

$1$

RECORD(10)

build a 10-element record

10101010

0xAA

$1$

RECORD(11)

build a 11-element record

10101011

0xAB

$1$

RECORD(12)

build a 12-element record

10101100

0xAC

$1$

RECORD(13)

build a 13-element record

10101101

0xAD

$1$

RECORD(14)

build a 14-element record

10101110

0xAE

$2$

RECORD($ub$)

build a $ub$-element record

10101111

0xAF

$3$

RECORD($uh$)

build a $uh$-element record

10110000

0xB0

$1$

RAW(1)

build a one-element raw record

10110001

0xB1

$1$

RAW(2)

build a two-element raw record

10110010

0xB2

$1$

RAW(3)

build a three-element raw record

10110011

0xB3

$1$

RAW(4)

build a four-element raw record

10110100

0xB4

$1$

RAW(5)

build a five-element raw record

10110101

0xB5

$1$

RAW(6)

build a six-element raw record

10110110

0xB6

$1$

RAW(7)

build a seven-element raw record

10110111

0xB7

$1$

RAW(8)

build an eight-element raw record

10111000

0xB8

$1$

RAW(9)

build a nine-element raw record

10111001

0xB9

$1$

RAW(10)

build a 10-element raw record

10111010

0xBA

$1$

RAW(11)

build a 11-element raw record

10111011

0xBB

$1$

RAW(12)

build a 12-element raw record

10111100

0xBC

$1$

RAW(13)

build a 13-element raw record

10111101

0xBD

$1$

RAW(14)

build a 14-element raw record

10111110

0xBE

$2 + ub$

RAW($ub$)

build a $ub$-element raw record

10111111

0xBF

$3 + uh$

RAW($uh$)

build a $uh$-element raw record

11000000

0xC0

$3$

MIXED($ub_1,ub_2$)

build a mixed record with $ub_1+ub_2$ elements

11000001

0xC1

$5$

MIXED($uh_1,uh_2$)

build a mixed record with $uh_1+uh_2$ elements

11000010

0xC2

$1$

UNUSED

11000011

0xC3

$1$

UNUSED

11000100

0xC4

$1$

UNUSED

11000101

0xC5

$1$

UNUSED

11000110

0xC6

$1$

UNUSED

11000111

0xC7

$1$

UNUSED

11001000

0xC8

$1$

VEC(0)

build a zero-length vector

11001001

0xC9

$2$

VEC($ub$)

build a $ub$-element vector

11001010

0xCA

$3$

VEC($uh$)

build a $uh$-element vector

11001011

0xCB

$1$

UNUSED

11001100

0xCC

$1$

UNUSED

11001101

0xCD

$1$

UNUSED

11001110

0xCE

$1$

UNUSED

11001111

0xCF

$1$

UNUSED

11010000

0xD0

$1$

UNUSED

11010001

0xD1

$1$

UNUSED

11010010

0xD2

$1$

UNUSED

11010011

0xD3

$1$

UNUSED

11010100

0xD4

$1$

UNUSED

11010101

0xD5

$1$

UNUSED

11010110

0xD6

$1$

UNUSED

11010111

0xD7

$1$

UNUSED

11011000

0xD8

$2+ub$

RAWVEC($8,ub$)

11011001

0xD9

$2+2*ub$

RAWVEC($16,ub$)

11011010

0xDA

$2+4*ub$

RAWVEC($32,ub$)

11011011

0xDB

$2+8*ub$

RAWVEC($64,ub$)

11011100

0xDC

$3+uh$

RAWVEC($8,uh$)

11011101

0xDD

$3+2*uh$

RAWVEC($16,uh$)

11011110

0xDE

$3+4*uh$

RAWVEC($32,uh$)

11011111

0xDF

$3+8*uh$

RAWVEC($64,uh$)

11100000

0xE0

$5+uw$

RAWVEC($8,uw$)

11100001

0xE1

$5+2*uw$

RAWVEC($16,uw$)

11100010

0xE2

$5+4*uw$

RAWVEC($32,uw$)

11100011

0xE3

$5+8*uw$

RAWVEC($64,uw$)

11100100

0xE4

$1$

UNUSED

11100101

0xE5

$1$

UNUSED

11100110

0xE6

$1$

UNUSED

11100111

0xE7

$1$

UNUSED

11101000

0xE8

$1$

STORE(0)

11101001

0xE9

$1$

STORE(1)

11101010

0xEA

$1$

STORE(2)

11101011

0xEB

$1$

STORE(3)

11101100

0xEC

$1$

STORE(4)

11101101

0xED

$1$

STORE(5)

11101110

0xEE

$1$

STORE(6)

11101111

0xEF

$3$

STORE($uh$)

11110000

0xF0

$1$

LOAD(0)

11110001

0xF1

$1$

LOAD(1)

11110010

0xF2

$1$

LOAD(2)

11110011

0xF3

$1$

LOAD(3)

11110100

0xF4

$1$

LOAD(4)

11110101

0xF5

$1$

LOAD(5)

11110110

0xF6

$1$

LOAD(6)

11110111

0xF7

$3$

LOAD($uh$)

11111000

0xF8

$1$

CONCAT(2)

pop and concatenate two records

11111001

0xF9

$1$

CONCAT(3)

pop and concatenate three records

11111010

0xFA

$1$

CONCAT(4)

pop and concatenate four records

11111011

0xFB

$1$

CONCAT(5)

pop and concatenate five records

11111100

0xFC

$1$

CONCAT(6)

pop and concatenate six records

11111101

0xFD

$1$

CONCAT(7)

pop and concatenate seven records

11111110

0xFE

$1$

CONCAT(8)

pop and concatenate eight records

11111111

0xFF

$1$

RETURN

pop and return the top of the stack

Clone this wiki locally