blob: fb589527768f60a51b6dc99d24afaf4ceda2e403 [file] [log] [blame] [view]
dan sinclaireee8d882022-10-28 01:22:58 +00001# Intermediate Representation
2
3As Tint has grown the number of transforms on the AST has grown. This
4growth has lead to several issues:
5
61. Transforms rebuild the AST and SEM which causes slowness
71. Transforming in AST can be difficult as the AST is hard to work with
8
9In order to address these goals, an IR is being introduced into Tint.
10The IR is mutable, it holds the needed state in order to be transformed.
11The IR is also translatable back into AST. It will be possible to
12generate an AST, convert to IR, transform, and then rebuild a new AST.
13This round-trip ability provides a few features:
14
151. Easy to integrate into current system by replacing AST transforms
16 piecemeal
171. Easier to test as the resulting AST can be emitted as WGSL and
18 compared.
19
20The IR helps with the complexity of the AST transforms by limiting the
21representations seen in the IR form. For example, instead of `for`,
22`while` and `loop` constructs there is a single `loop` construct.
Ben Claytonc98d57d2023-01-24 14:59:43 +000023`alias` and `const_assert` nodes are not emitted into IR. Dead code is
dan sinclaireee8d882022-10-28 01:22:58 +000024eliminated during the IR construction.
25
26As the IR can convert into AST, we could potentially simplify the
27SPIRV-Reader by generating IR directly. The IR is closer to what SPIR-V
28looks like, so maybe a simpler transform.
29
30## Design
31
32The IR breaks down into two fundamental pieces, the control flow and the
33expression lists. While these can be thought of as separate pieces they
34are linked in that the control flow blocks contain the expression lists.
35A control flow block may use the result of an expression as the
36condition.
37
38The IR works together with the AST/SEM. There is an underlying
39assumption that the source `Program` will live as long as the IR. The IR
40holds pointers to data from the `Program`. This includes things like SEM
41types, variables, statements, etc.
42
43Transforming from AST to IR and back to AST is a lossy operation.
44The resulting AST when converting back will not be the same as the
45AST being provided. (e.g. all `for`, `while` and `loop` constructs coming
46in will become `while` loops going out). This is intentional as it
47greatly simplifies the number of things to consider in the IR. For
48instance:
49
50* No `alias` nodes
Ben Claytonc98d57d2023-01-24 14:59:43 +000051* No `const_assert` nodes
dan sinclaireee8d882022-10-28 01:22:58 +000052* All loops become `while` loops
53* `if` statements may all become `if/else`
54
55### Code Structure
56The code is contained in the `src/tint/ir` folder and is broken down
57into several classes. Note, the IR is a Tint _internal_ representation
58and these files should _never_ appear in the public API.
59
60#### Builder
61The `Builder` class provides useful helper routines for creating IR
62content. The Builder owns an `ir::Module`, it can be created with an
63existing Module by moving it into the builder. The Module is moved from
64the builder when it is complete.
65
66#### Module
67The top level of the IR is the `Module`. The module stores a list of
68`functions`, `entry_points`, allocators and various other bits of
69information needed by the IR. The `Module` also contains a pointer to
70the `Program` which the IR was created from. The `Program` must outlive
71the `Module`.
72
73The `Module` provides two methods from moving two and from a `Program`.
74The `Module::FromProgram` static method will take a `Program` and
75construct an `ir::Module` from the contents. The resulting module class
76then has a `ToProgram` method which will construct a new `Program` from
77the `Module` contents.
78
79#### BuilderImpl
80The `BuilderImpl` is internally used by the `Module` to do the
81conversion from a `Program` to a `Module`. This class should not be used
82outside the `src/tint/ir` folder.
83
84### Transforms
85Similar to the AST a transform system is available for IR. The transform
86has the same setup as the AST (and inherits from the same base transform
87class.)
88
89Note, not written yet.
90
91### Scoping
92The IR flattens scopes. This also means that the IR will rename shadow
93variables to be uniquely named in the larger scoped block.
94
95For an example of flattening:
96
97```
98{
99 var x = 1;
100 {
101 var y = 2;
102 }
103}
104```
105
106becomes:
107
108```
109{
110 var x = 1;
111 var y = 2;
112}
113```
114
115For an example of shadowing:
116
117```
118{
119 var x = 1;
120 if (true) {
121 var x = 2;
122 }
123}
124```
125
126becomes:
127
128```
129{
130 var x = 1;
131 if true {
132 var x_1 = 2;
133 }
134}
135```
136
137### Control Flow Blocks
138
139At the top level, the AST is broken into a series of control flow nodes.
140There are a limited set of flow nodes as compared to AST:
141
1421. Block
1431. Function
1441. If statement
1451. Loop statement
1461. Switch statement
1471. Terminator
148
149As the IR is built a stack of control flow blocks is maintained. The
150stack contains `function`, `loop`, `if` and `switch` control flow
151blocks. A `function` is always the bottom element in the flow control
152stack.
153
154The current instruction block is tracked. The tracking is reset to
155`nullptr` when a branch happens. This is used in the statement processing
156in order to eliminate dead code. If the current block does not exist, or
157has a branch target, then no further instructions can be added, which
158means all control flow has branched and any subsequent statements can be
159disregarded.
160
161Note, this does have the effect that the inspector _must_ be run to
162retrieve the module interface before converting to IR. This is because
163phony assignments in dead code add variables into the interface.
164
165```
166var<storage> b;
167
168fn a() {
169 return;
170 _ = b; // This pulls b into the module interface but would be
171 // dropped due to dead code removal.
172}
173```
174
175#### Control Flow Block
176A block is the simplest control flow node. It contains the instruction
177lists for a given linear section of codes. A block only has one branch
178statement which always happens at the end of the block. Note, the branch
179statement is implicit, it doesn't show up in the expression list but is
180encoded in the `branch_target`.
181
182In almost every case a block does not branch to another block. It will
183always branch to another control flow node. The exception to this rule
184is blocks branching to the function end block.
185
186#### Control Flow Function
187A function control flow block has two targets associated with it, the
188`start_target` and the `end_target`. Function flow starts at the
189`start_target` and ends just before the `end_target`. The `end_target`
190is always a terminator, it just marks the end of the function
191(a return is a branch to the function `end_target`).
192
193#### Control Flow If
194The if flow node is an `if-else` structure. There are no `else-if`
195entries, they get moved into the `else` of the `if`. The if control flow
196node has three targets, the `true_target`, `false_target` and possibly a
197`merge_target`.
198
199The `merge_target` is possibly `nullptr`. This can happen if both
200branches of the `if` call `return` for instance as the internal branches
201would jump to the function `end_target`.
202
203In all cases, the if node will have a `true_target` and a
204`false_target`, the target block maybe just a branch to the
205`merge_target` in the case where that branch of the if was empty.
206
207#### Control Flow Loop
208All of the loop structures in AST merge down to a single loop control
209flow node. The loop contains the `start_target`, `continuing_target` and
210a `merge_target`.
211
212In the case of a loop, the `merge_target` always exists, but may
213actually not exist in the control flow. The target is created in order
214to have a branch for `continue` to branch too, but if the loop body does
215a `return` then control flow may jump over that block completely.
216
217The chain of blocks from the `start_target`, as long as it does not
218`break` or `return` will branch to the `continuing_target`. The
219`continuing_target` will possibly branch to the `merge_target` and will
220branch to the `start_target` for the loop.
221
222A while loop is decomposed as listed in the WGSL spec:
223
224```
225while (a < b) {
226 c += 1;
227}
228```
229
230becomes:
231
232```
233loop {
234 if (!(a < b)) {
235 break;
236 }
237 c += 1;
238}
239```
240
241A for loop is decomposed as listed in the WGSL spec:
242```
243for (var i = 0; i < 10; i++) {
244 c += 1;
245}
246```
247
248becomes:
249
250```
251var i = 0;
252loop {
253 if (!(i < 10)) {
254 break;
255 }
256
257 c += 1;
258
259 continuing {
260 i++;
261 }
262}
263```
264
265#### Control Flow Switch
266The switch control flow has a target block for each of the
267`case/default` labels along with a `merge_target`. The `merge_target`
268while existing, maybe outside the control flow if all of the `case`
269branches `return`. The target exists in order to provide a `break`
270target.
271
272#### Control Flow Terminator
273The terminator control flow is only used as the `end_target` of a
274function. It does not contain instructions and is only used as a marker
275for the exit of a function.
276
277### Expression Lists.
278Note, this section isn't fully formed as this has not been written at
279this point.
280
281The expression lists are all in SSA form. The SSA variables will keep
282pointers back to the source AST variables in order for us to not require
283PHI nodes and to make it easier to move back out of SSA form.
284
285#### Expressions
286All expressions in IR are single operations. There are no complex
287expressions. Any complex expression in the AST is broke apart into the
288simpler single operation components.
289
290```
291var a = b + c - (4 * k);
292```
293
294becomes:
295
296```
297%t0 = b + c
298%t1 = 4 * k
299%v0 = %t0 - %t1
300```
301
302This also means that many of the short forms `i += 1`, `i++` get
303expanded into the longer form of `i = i + 1`.
304
305##### Short-Circuit Expressions
306The short-circuit expressions (e.g. `a && b`) will be convert into an
307`if` structure control flow.
308
309```
310let c = a() && b()
311```
312
313becomes
314
315```
316let c = a();
317if (c) {
318 c = b();
319}
320```
321
322#### Registers
323There are several types of registers used in the SSA form.
324
3251. Constant Register
3261. Temporary Register
3271. Variable Register
3281. Return Register
3291. Function Argument Register
330
331##### Constant Register
332The constant register `%c` holds a constant value. All values in IR are
333concrete, there are no abstract values as materialization has already
334happened. Each constant register holds a single constant value (e.g.
335`3.14`) and a pointee to the type (maybe? If needed.)
336
337##### Temporary Register
338The temporary register `%t` hold the results of a simple operation. The
339temporaries are created as complex expressions are broken down into
340pieces. The temporary register tracks the usage count for the register.
341This allows a portion of a calculation to be pulled out when rebuilding
342AST as a common calculation. If the temporary is used once it can be
343re-combine back into a large expression.
344
345##### Variable Register
346The variable register `%v` potentially holds a pointer back to source
347variables. So, while each value is written only once, if the pointer
348back to an AST variable exists we can rebuild the variable that value
349was originally created from and can assign back when converting to AST.
350
351##### Return Register
352Each function has a return register `%r` where the return value will be
353stored before the final block branches to the `end_target`.
354
355##### Function Argument Register
356The function argument registers `%a` are used to store the values being
357passed into a function call.
358
359#### Type Information
360The IR shares type information with the SEM. The types are the same, but
361they may exist in different block allocations. The SEM types will be
362re-used if they exist, but if the IR needs to create a new type it will
363be created in the IRs type block allocator.
364
365#### Loads / Stores and Deref
366Note, have not thought about this. We should probably have explicit
367load/store operations injected in the right spot, but don't know yet.
368
369## Alternatives
370Instead of going to a custom IR there are several possible other roads
371that could be travelled.
372
373### Mutable AST
374Tint originally contained a mutable AST. This was converted to immutable
375in order to allow processing over multiple threads and for safety
376properties. Those desires still hold, the AST is public API, and we want
377it to be as safe as possible, so keeping it immutable provides that
378guarantee.
379
380### Multiple Transforms With One Program Builder
381Instead of generating an immutable AST after each transform, running
382multiple transforms on the single program builder would remove some of
383the performance penalties of going to and from immutable AST. While this
384is true, the transforms use a combination of AST and SEM information.
385When they transform they _do not_ create new SEM information. That
386means, after a given transform, the SEM is out of date. In order to
387re-generate the SEM the resolver needs to be rerun. Supporting this
388would require being very careful on what transforms run together and
389how they modify the AST.
390
391### Adopt An Existing IR
392There are already several IRs in the while, Mesa has NIR, LLVM has
393LLVM IR. There are others, adopting one of those would remove the
394requirements of writing and maintaining our own IR. While that is true,
395there are several downsides to this re-use. The IRs are internal to the
396library, so the API isn't public, LLVM IR changes with each iteration of
397LLVM. This would require us to adapt the AST -> IR -> AST transform for
398each modification of the IR.
399
400They also end up being lower level then is strictly useful for us. While
401the IR in Tint is a simplified form, we still have to be able to go back
402to the high level structured form in order to emit the resulting HLSL,
403MSL, GLSL, etc. (Only SPIR-V is a good match for the lowered IR form).
404This transformation back is not a direction other IRs maybe interested
405in so may have lost information, or require re-determining (determining
406variables from SSA and PHI nodes for example).
407
408Other technical reasons are the maintenance of BUILD.gn and CMake files
409in order to integrate into our build systems, along with resulting
410binary size questions from pulling in external systems.
411