seed/README 8.8 KiB raw
1
2
3
Radiance is a self-hosted compiler: the compiler is written in Radiance
4
and compiles itself. This creates a bootstrapping problem: you need a
5
working compiler to build the compiler. The solution is the "seed" -- a
6
trusted, checked-in binary that can compile the current source.
7
8
This document describes the workflows for developing the compiler,
9
updating the seed, and maintaining reproducibility.
10
11
12
CONCEPTS
13
14
  Seed            A known-good compiler binary checked into the repository
15
                  (`seed/radiance.rv64`). It can compile the current source
16
                  code into a working compiler.
17
18
  Stage           One round of self-compilation. Stage N uses the stage N-1
19
                  binary to compile the source. Stage 0 is the seed itself.
20
21
  Fixed point     When two consecutive stages produce bit-for-bit identical
22
                  binaries. This proves the compiler faithfully
23
                  reproduces itself.
24
25
  "Dev" binary    `bin/radiance.rv64.dev` -- built by `make` from the seed.
26
                  This is the working compiler used during development.
27
                  It is not checked in.
28
29
  Breaking        A source change that the current seed cannot compile.
30
  change          Eg. new syntax, changed calling conventions, removed
31
                  features the compiler uses during self-compilation. This
32
                  requires generating a new seed.
33
34
  Compatible      A source change that the current seed can still compile.
35
  change          Eg. bug fixes, new optimizations, new library code that
36
                  the compiler itself doesn't use, or isn't meaningfully
37
                  affected by.
38
39
40
FILES
41
42
  seed/radiance.rv64           Self-contained RV64 image containing the seed's
43
                               text, read-only data, and read-write data.
44
  seed/radiance.rv64.git       Full Git tree ID of the source commit that
45
                               was compiled to produce this seed.
46
  seed/update                  Tool that finds the fixed point and
47
                               updates the seed.
48
49
50
EVERYDAY DEVELOPMENT
51
52
Most compiler work -- bug fixes, optimizations, new standard library
53
features, new backends -- does not require a seed update. The workflow is
54
simply:
55
56
  1. Edit source code
57
  2. Build the dev binary (produces a new `bin/radiance.rv64.dev`)
58
59
      make
60
61
  3. Run tests
62
63
      make test
64
65
  4. Commit source changes only. The seed is untouched.
66
67
The `dev` binary is ephemeral and rebuilt from the seed on every `make`. As
68
long as the seed can compile the current source, no seed update is needed.
69
70
71
WHEN TO UPDATE THE SEED
72
73
Some compiler work requires an update to the seed.
74
75
  * When a breaking change is introduced, i.e. a change that breaks the
76
    seed's ability to compile the source. You must update the seed *before*
77
    committing the breaking change. See "Breaking changes" below.
78
79
  * You want the benefits of compiler improvements (better code generation,
80
    faster compilation) to apply to the build itself. This is optional
81
    but often a good idea.
82
83
  * The fixed-point property needs re-verification after significant
84
    changes. Even compatible changes can alter the output binary, and
85
    reaching a fixed point confirms the compiler is self-consistent and
86
    deterministic.
87
88
Do *not* update the seed casually. Each seed update adds a large binary
89
diff to the repository.
90
91
92
BREAKING CHANGES
93
94
A breaking change is one where the new source cannot be compiled by the
95
old seed. Examples: new syntax the compiler uses on itself, changed
96
data structures in the AST, removed intrinsics.
97
98
The fundamental constraint is:
99
100
    The checked-in seed must always be able to compile the
101
    checked-in source.
102
103
This means you cannot simply commit a breaking change and update the
104
seed afterward, there would be a commit where the seed cannot build
105
the source. Instead:
106
107
    1. Add support for the new feature to the source, but don't use it
108
       in the compiler's own source yet. Ensure old syntax/behavior
109
       still works.
110
111
    2. Run `seed/update` to produce a new seed that understands the
112
       new feature.
113
114
    3. Commit source + updated seed together.
115
116
The seed now understands the new feature. From here, switching the
117
compiler's own source to use it is just a compatible change: the
118
seed can already compile it. No further seed update is required.
119
120
121
HOW UPDATING THE SEED WORKS
122
123
  seed/update [--seed <path>]
124
125
  1. Stage 1: Runs the seed to compile the current source.
126
     Outputs `seed/radiance.rv64.s1`.
127
  2. Compares the SEED with S1. If identical, done (fixed point reached).
128
  3. Stage 2: Runs S1 to compile the source. Outputs S2.
129
  4. Compares S1 and S2. If identical, done.
130
  5. Continues up to a certain number of stages. Fails if no fixed point is reached.
131
132
When a fixed point is found, it copies the converged binary to
133
`seed/radiance.rv64` and writes the full tree ID of HEAD in
134
`seed/radiance.rv64.git`. Commit source changes before running the updater.
135
The updater compiles an archive of that complete committed tree.
136
137
Why might it take multiple stages?
138
139
  * Stage 1 differs from seed: The source changed, so the compiler
140
    binary changed. Normal.
141
142
  * Stage 2 differs from Stage 1: The source changes affected how the
143
    compiler generates code for itself. The S1 compiler (built by the
144
    old seed) generates slightly different code than the S2 compiler
145
    (built by S1, which incorporates the changes). Usually converges
146
    at Stage 2 or 3.
147
148
  * No convergence after 3+ stages: Something is non-deterministic in
149
    code generation (memory addresses leaking into output, hash map
150
    iteration order, etc.). This is a bug that must be fixed.
151
152
153
VERIFYING THE SEED
154
155
The seed is an opaque binary checked into the repository. Since binaries
156
can't be reviewed like source code, trust relies on reproducibility: anyone
157
can rebuild the seed from source and verify it matches.
158
159
  Verify the fixed-point property
160
161
    Run `seed/update`. If the seed is already at a fixed point, Stage 1
162
    will report IDENTICAL immediately. This confirms that compiling the
163
    current source with the seed produces the seed itself -- the compiler
164
    faithfully reproduces its own binary.
165
166
  Verify from an independent build
167
168
    If you have a separately-obtained Radiance compiler (e.g. built from
169
    a different trusted seed, or received from another party), use it as
170
    the starting point:
171
172
      seed/update --seed /path/to/trusted/radiance.rv64
173
174
    If this converges to the same fixed point as the checked-in seed,
175
    you have strong evidence that the seed is a faithful product of the
176
    source code and not a tampered binary. A backdoored seed cannot survive
177
    independent compilation.
178
179
    The bootstrapping compiler can serve as this independent second compiler.
180
    Its source can be audited, and any C99 compiler can be used to compile it.
181
    To use it as seed, pass `--from-s0` like so:
182
183
      seed/update --from-s0 --seed ./radiance.s0
184
185
  Verify the source tree
186
187
    The file `seed/radiance.rv64.git` records the complete tree of the
188
    actual source commit used to build the seed. This can be an earlier
189
    source snapshot when source and seed changes share one final commit.
190
    The source commit is identified in the seed commit message.
191
192
      git rev-parse 'SOURCE_COMMIT^{tree}'
193
194
    Compare that result with the recorded tree ID. The title uses the
195
    first eight characters: Create new seed from `<tree ID>`.
196
    The recorded object must be inspectable with `git cat-file -p TREE_ID`.
197
198
199
BOOTSTRAPPING THE HISTORY
200
201
  Every commit in the history builds with its own checked-in seed. Each
202
  seed commit has its source as its parent: `seed/radiance.rv64.git`
203
  names that parent commit, or its tree in later seeds. The seed is the
204
  fixed point of that source, reached from the previous seed. The first
205
  seed is the fixed point reached from `radiance.s0`, the bootstrapping
206
  compiler at its commit 7834d3a.
207
208
  To verify the whole chain, build the first seed with `--from-s0`.
209
  Then, for each later seed commit in order, check out its parent, run
210
  `seed/update --seed <previous seed>`, and compare the result with the
211
  seed that the seed commit checks in.
212
213
  Breaking changes
214
215
    A change that the previous seed cannot compile is staged. First the
216
    compiler supports the new form without requiring it, and a seed
217
    follows. Then the compiler's own source moves to the new form, and
218
    finally a commit requires it. The ownership rewrite instead follows a
219
    bridge commit, "Bootstrap ownership syntax", which extends the
220
    previous compiler just enough to compile the rewrite.
221
222
223
224
TROUBLESHOOTING
225
226
  "No fixed point reached after N stages"
227
228
    The compiler output is non-deterministic. Diff the binaries
229
    to find what's changing. Common causes:
230
231
    * Pointer values or addresses leaking into generated code
232
    * Hash table iteration order affecting output
233
    * Uninitialized memory read during compilation