lib/std/lang/il.rad 17.0 KiB raw
1
//! Radiance Intermediate Language (RIL).
2
//!
3
//! A minimal, low-level, SSA-based intermediate language.
4
//!
5
//! > The single-assignment property simplifies reasoning about variables,
6
//! > since for every value instance its (single) defining assignment is known.
7
//! > Because every assignment creates a new value name it cannot kill
8
//! > (i.e., invalidate) expressions previously computed from other values.
9
//! > In particular, if two expressions are textually the same, they are sure
10
//! > to evaluate the same result.
11
//! >
12
//! >   -- "Single-Pass Generation of Static Single-Assignment Form for
13
//! >       Structured Languages", by Marc M. Brandis and Hanspeter Mossenbock
14
//!
15
//! # Type System
16
//!
17
//! Primitive types: `W8`, `W16`, `W32` (word sizes).
18
//! Signedness is encoded in operations (e.g., `Sdiv` vs `Udiv`), not types.
19
//!
20
//! Types on arithmetic operations indicate logical width but don't
21
//! change code generation. Arithmetic is always machine word sized,
22
//! no 8-bit or 16-bit add instruction.
23
//!
24
//! # Truncation and Narrowing
25
//!
26
//! There is no truncation instruction.
27
//! * Narrow values are stored in word-sized registers with undefined high bits.
28
//! * Truncation happens implicitly via narrow store instructions.
29
//! * To normalize a narrow value, mask explicitly via a bitwise `and`.
30
//!
31
//! # Widerning
32
//!
33
//! `Zext`/`Sext` widen values when loading from memory.
34
//!
35
//! # Aggregate Types
36
//!
37
//! The IL provides no aggregate types. Records, slices, optionals, and unions
38
//! are represented as bytes in memory with explicit layout computed during
39
//! lowering. Access is via explicit address arithmetic plus load/store/blit.
40
//!
41
//! # Lowering Strategy
42
//!
43
//! * Slices lower to a pointer+length layout in memory.
44
//! * Optionals lower to a tag+value layout in memory.
45
//! * Tagged unions lower to a tag+payload layout in memory.
46
//! * Results lower to a tag+payload layout in memory.
47
//!
48
//! Field access is expressed as address arithmetic plus load/store.
49
//!
50
//! Bounds check elimination and nullable pointer optimization happen during
51
//! this lowering phase.
52
//!
53
//! # Control Flow
54
//!
55
//! Uses block parameters instead of phi nodes (like MLIR/SIL). Each block
56
//! can declare parameters, and jumps/branches pass arguments to their targets.
57
58
// TODO: Labels should have their own type.
59
// TODO: Blocks should have an instruction in `Instr`.
60
61
export mod printer;
62
export mod binary;
63
64
use std::mem;
65
use std::lang::alloc;
66
67
/// Source location for debug info.
68
///
69
/// Associates an IL instruction with its originating source module and
70
/// byte offset.
71
export record SrcLoc: Copy {
72
    /// Module identifier.
73
    moduleId: u16,
74
    /// Byte offset into the module's source file.
75
    offset: u32,
76
}
77
78
///////////////////////
79
// Name Formatting   //
80
///////////////////////
81
82
/// Separator for qualified symbol names.
83
export constant PATH_SEPARATOR: *[u8] = "::";
84
85
/// Format a qualified symbol name: `pkg::mod::path::name`.
86
export unsafe fn formatQualifiedName(arena: &mut alloc::Arena, path: &[*[u8]], name: *[u8]) -> *[u8] {
87
    let mut totalLen: u32 = name.len;
88
    for segment in path {
89
        set totalLen += segment.len + PATH_SEPARATOR.len;
90
    }
91
    let buf = try! alloc::allocSlice(arena, 1, 1, totalLen) as *mut [u8];
92
    let mut pos: u32 = 0;
93
94
    for segment in path {
95
        set pos += try! mem::copy(&mut buf[pos..], segment);
96
        set pos += try! mem::copy(&mut buf[pos..], PATH_SEPARATOR);
97
    }
98
    try! mem::copy(&mut buf[pos..], name);
99
100
    return &buf[..totalLen];
101
}
102
103
///////////
104
// Types //
105
///////////
106
107
/// IL type representation. Integer signedness is encoded in operations, not types.
108
export union Type: Copy {
109
    /// 8-bit value.
110
    W8,
111
    /// 16-bit value.
112
    W16,
113
    /// 32-bit value.
114
    W32,
115
    /// 64-bit value (used for pointers on RV64).
116
    W64,
117
}
118
119
/// Get the size of a type in bytes.
120
export fn typeSize(t: Type) -> u32 {
121
    match t {
122
        case Type::W8 => return 1,
123
        case Type::W16 => return 2,
124
        case Type::W32 => return 4,
125
        case Type::W64 => return 8,
126
    }
127
}
128
129
/// SSA register reference.
130
export record Reg: Copy { n: u32 }
131
132
/// Instruction value.
133
export union Val: Copy {
134
    /// Register reference.
135
    Reg(Reg),
136
    /// Immediate integer value.
137
    Imm(i64),
138
    /// Data symbol address (globals, constants, string literals).
139
    DataSym(*[u8]),
140
    /// Function address by symbol name. Used directly in call instructions
141
    /// for direct calls, or stored first for indirect calls.
142
    FnAddr(*[u8]),
143
    /// Undefined value. Used when the value is to be discarded,
144
    /// eg. in void returns.
145
    Undef,
146
}
147
148
/// Comparison operation for compare-and-branch.
149
export union CmpOp: Copy { Eq, Ne, Slt, Ult }
150
151
/// Binary ALU operation kind.
152
export union BinOp: Copy {
153
    // Arithmetic.
154
    Add, Sub, Mul, Sdiv, Udiv, Srem, Urem,
155
    // Comparison.
156
    Eq, Ne, Slt, Sge, Ult, Uge,
157
    // Bitwise.
158
    And, Or, Xor, Shl, Sshr, Ushr,
159
}
160
161
/// Unary ALU operation kind.
162
export union UnOp: Copy {
163
    Neg, Not,
164
}
165
166
//////////////////
167
// Instructions //
168
//////////////////
169
170
/// Block parameter.
171
export record Param: Copy {
172
    /// SSA register.
173
    value: Reg,
174
    /// Parameter type.
175
    type: Type,
176
}
177
178
/// Switch case mapping a constant value to a branch target.
179
export record SwitchCase: Copy {
180
    /// The constant value to match against.
181
    value: i64,
182
    /// The target block index.
183
    target: u32,
184
    /// Arguments to pass to the target block.
185
    args: *unsafe mut [Val],
186
}
187
188
/// IL instruction.
189
/// SSA registers are represented as `Reg`, values as `Val`.
190
export union Instr: Copy {
191
    ///////////////////////
192
    // Memory operations //
193
    ///////////////////////
194
195
    /// Allocate space on the stack: `reserve %dst <size> <alignment>;`
196
    /// Size can be a register for dynamic stack allocation (eg. VLAs).
197
    Reserve { dst: Reg, size: Val, alignment: u32 },
198
    /// Load a value from memory (zero-extending): `load <type> %dst %src <offset>;`
199
    Load { typ: Type, dst: Reg, src: Reg, offset: i32 },
200
    /// Signed load from memory (sign-extending): `sload <type> %dst %src <offset>;`
201
    Sload { typ: Type, dst: Reg, src: Reg, offset: i32 },
202
    /// Store a value to memory: `store <type> <src> %dst <offset>;`
203
    Store {
204
        /// Type being stored.
205
        typ: Type,
206
        /// Value being stored.
207
        src: Val,
208
        /// Destination address.
209
        dst: Reg,
210
        /// Byte offset from the base address.
211
        offset: i32
212
    },
213
    /// Copy memory region: `blit %dst %src <size>;`
214
    /// Size can be an immediate or a register (eg. for generics).
215
    Blit {
216
        /// Destination address.
217
        dst: Reg,
218
        /// Source address.
219
        src: Reg,
220
        /// Size to copy in bytes.
221
        size: Val
222
    },
223
    /// Copy a value into a register: `copy %dst <val>;`.
224
    Copy { dst: Reg, val: Val },
225
226
    /////////////////////
227
    // ALU operations  //
228
    /////////////////////
229
230
    /// Binary ALU operation: `<op> <type> %dst <a> <b>;`
231
    BinOp { op: BinOp, typ: Type, dst: Reg, a: Val, b: Val },
232
    /// Unary ALU operation: `<op> <type> %dst <a>;`
233
    UnOp { op: UnOp, typ: Type, dst: Reg, a: Val },
234
235
    /////////////////
236
    // Conversions //
237
    /////////////////
238
239
    /// Zero-extend from narrower type to word: `zext <type> %dst <val>;`
240
    Zext {
241
        /// Source type (I8 or I16).
242
        typ: Type,
243
        /// Destination register, always I32.
244
        dst: Reg,
245
        /// Source value.
246
        val: Val,
247
    },
248
    /// Sign-extend from narrower type to word: `sext <type> %dst <val>;`
249
    Sext {
250
        /// Source type (I8 or I16).
251
        typ: Type,
252
        /// Destination register, always I32.
253
        dst: Reg,
254
        /// Source value.
255
        val: Val,
256
    },
257
258
    ////////////////////
259
    // Function calls //
260
    ////////////////////
261
262
    /// Call a function: `call <type> %dst $func(<arg>...);`
263
    Call {
264
        /// Return type.
265
        retTy: Type,
266
        /// Holds return value, for non-void function.
267
        dst: ?Reg,
268
        /// Function value, either a symbol or an address in a register.
269
        func: Val,
270
        /// Function arguments.
271
        args: *unsafe [Val]
272
    },
273
274
    /////////////////
275
    // Terminators //
276
    /////////////////
277
278
    /// Return from function: `ret <val>;` or `ret;`
279
    Ret { val: ?Val },
280
    /// Unconditional jump: `jmp @block(<arg>...);`
281
    Jmp { target: u32, args: *unsafe mut [Val] },
282
    /// Compare-and-branch: `br.<op> <type> <a> <b> @then @else;`
283
    Br { op: CmpOp, typ: Type, a: Val, b: Val, thenTarget: u32, thenArgs: *unsafe mut [Val], elseTarget: u32, elseArgs: *unsafe mut [Val] },
284
    /// Multi-way branch: `switch <val> (<n> @block) ... @default;`
285
    Switch { val: Val, defaultTarget: u32, defaultArgs: *unsafe mut [Val], cases: *unsafe mut [SwitchCase] },
286
    /// Unreachable code marker: `unreachable;`
287
    /// Indicates control flow cannot reach this point to allow for optimizations.
288
    Unreachable,
289
290
    /////////////////
291
    // Intrinsics  //
292
    /////////////////
293
294
    /// Environment call: `ecall %dst <num> <a0> <a1> <a2> <a3>;`
295
    Ecall { dst: Reg, num: Val, a0: Val, a1: Val, a2: Val, a3: Val },
296
    /// Environment break: `ebreak;`.
297
    /// Triggers a breakpoint exception for debugging.
298
    Ebreak,
299
    /// Full acquire/release memory fence.
300
    MemoryFence,
301
    /// Read one register through a live Device handle.
302
    DeviceRead {
303
        /// Register access width.
304
        typ: Type,
305
        /// Destination for the zero-extended register value.
306
        dst: Reg,
307
        /// Domain-relative Device capability.
308
        handle: Val,
309
        /// Byte offset within the device region.
310
        offset: Val,
311
    },
312
    /// Write one register through a live Device handle.
313
    DeviceWrite {
314
        /// Register access width.
315
        typ: Type,
316
        /// Domain-relative Device capability.
317
        handle: Val,
318
        /// Byte offset within the device region.
319
        offset: Val,
320
        /// Value whose low bits are written at the selected width.
321
        value: Val,
322
    },
323
}
324
325
//////////////////////////
326
// Blocks and Functions //
327
//////////////////////////
328
329
/// A basic block in a function.
330
///
331
/// Basic blocks are instruction sequences with a single entry point and no branch
332
/// instruction, except possibly at the end of the sequence, where a terminator
333
/// may be found, ie. an instruction that terminates the sequence by jumping
334
/// to another sequence.
335
export record Block: Copy {
336
    /// Block label.
337
    label: *[u8],
338
    /// Block parameters.
339
    params: *unsafe [Param],
340
    /// Instructions in the block. The last instruction must be a terminator.
341
    instrs: *unsafe mut [Instr],
342
    /// Source locations for debugging and error reporting.
343
    /// One entry per instruction when debug info is enabled, empty otherwise.
344
    locs: *unsafe [SrcLoc],
345
    /// Predecessor block indices. Used for control flow analysis.
346
    preds: *unsafe [u32],
347
    /// Loop nesting depth.
348
    /// Used for spill cost weighting in register allocation.
349
    loopDepth: u32,
350
}
351
352
/// An IL function.
353
export record Fn: Copy {
354
    /// Qualified function name (e.g. `$mod$path$func`).
355
    name: *[u8],
356
    /// Function parameters.
357
    params: *unsafe [Param],
358
    /// Return type.
359
    returnType: Type,
360
    /// Whether the function is extern (no body).
361
    isExtern: bool,
362
    /// Whether the function is a leaf (contains no call or ecall instructions).
363
    isLeaf: bool,
364
    /// Basic blocks. Empty for extern functions.
365
    blocks: *unsafe [Block],
366
}
367
368
/////////////
369
// Program //
370
/////////////
371
372
/// Data initializer item.
373
export union DataItem: Copy {
374
    /// Typed value: `w32 42;` or `w8 255;`
375
    Val { typ: Type, val: i64 },
376
    /// Symbol reference: `$symbol`
377
    Sym(*[u8]),
378
    /// Function reference: `$fnName`
379
    Fn(*[u8]),
380
    /// String literal bytes: `"hello"` (no auto null-terminator)
381
    Str(*[u8]),
382
    /// Undefined value. Used for padding and `void` returns.
383
    Undef,
384
}
385
386
/// Data initializer value with optional repeat count.
387
export record DataValue: Copy {
388
    /// The item contained in the value.
389
    item: DataItem,
390
    /// The number of times the item should be repeated.
391
    count: u32,
392
}
393
394
/// Global data definition.
395
export record Data: Copy {
396
    /// Data name.
397
    name: *[u8],
398
    /// Size in bytes.
399
    size: u32,
400
    /// Alignment requirement.
401
    alignment: u32,
402
    /// Whether this is read-only data.
403
    /// Typically, `constant` declaration are read-only, while `static`
404
    /// declarations are not.
405
    readOnly: bool,
406
    /// Whether writable data can be represented by zero-filled memory.
407
    /// Zero-initialized data doesn't need to be written to the sidecar image.
408
    isZeroInit: bool,
409
    /// Initializer values.
410
    values: *[DataValue],
411
}
412
413
/// An IL program (compilation unit).
414
export record Program: Copy {
415
    /// Immutable global data.
416
    data: *[Data],
417
    /// Functions.
418
    fns: *unsafe [*unsafe Fn],
419
}
420
421
///////////////////////
422
// Utility Functions //
423
///////////////////////
424
425
/// Compiler-generated metadata call for one MMIO access.
426
/// a0 is the handle, a1 the offset, and a2 the byte width plus bit 8 for a write.
427
/// a3 holds a write value and is preserved. Success returns the address in a0.
428
/// Any failure terminates the caller before the user-mode register access.
429
export constant DEVICE_ACCESS: u32 = 74;
430
431
/// Get the destination register of an instruction, if any.
432
export fn instrDst(instr: Instr) -> ?Reg {
433
    match instr {
434
        case Instr::Reserve { dst, .. } => return dst,
435
        case Instr::Load { dst, .. } => return dst,
436
        case Instr::Sload { dst, .. } => return dst,
437
        case Instr::Copy { dst, .. } => return dst,
438
        case Instr::BinOp { dst, .. } => return dst,
439
        case Instr::UnOp { dst, .. } => return dst,
440
        case Instr::Zext { dst, .. } => return dst,
441
        case Instr::Sext { dst, .. } => return dst,
442
        case Instr::Call { dst, .. } => return dst,
443
        case Instr::Ecall { dst, .. } => return dst,
444
        case Instr::DeviceRead { dst, .. } => return dst,
445
        else => return nil,
446
    }
447
}
448
449
/// Check if an instruction is a function call.
450
export fn isCall(instr: Instr) -> bool {
451
    match instr {
452
        case Instr::Call { .. },
453
             Instr::Ecall { .. }, Instr::DeviceRead { .. }, Instr::DeviceWrite { .. } => return true,
454
        else => return false,
455
    }
456
}
457
458
/// Call a function for each register used by an instruction.
459
/// This is called by the register allocator to analyze register usage.
460
export unsafe fn forEachReg(instr: Instr, f: unsafe fn(Reg, &mut opaque), ctx: &mut opaque) {
461
    match instr {
462
        case Instr::Reserve { size, .. } =>
463
            withReg(size, f, ctx),
464
        case Instr::Load { src, .. } => f(src, ctx),
465
        case Instr::Sload { src, .. } => f(src, ctx),
466
        case Instr::Store { src, dst, .. } => {
467
            withReg(src, f, ctx);
468
            f(dst, ctx);
469
        },
470
        case Instr::Blit { dst, src, size } => {
471
            f(dst, ctx);
472
            f(src, ctx);
473
            withReg(size, f, ctx);
474
        },
475
        case Instr::Copy { val, .. } =>
476
            withReg(val, f, ctx),
477
        case Instr::BinOp { a, b, .. } => {
478
            withReg(a, f, ctx);
479
            withReg(b, f, ctx);
480
        },
481
        case Instr::UnOp { a, .. } =>
482
            withReg(a, f, ctx),
483
        case Instr::Zext { val, .. } =>
484
            withReg(val, f, ctx),
485
        case Instr::Sext { val, .. } =>
486
            withReg(val, f, ctx),
487
        case Instr::Call { func, args, .. } => {
488
            withReg(func, f, ctx);
489
            for arg in args {
490
                withReg(arg, f, ctx);
491
            }
492
        },
493
        case Instr::Ret { val } => {
494
            if let v = val {
495
                withReg(v, f, ctx);
496
            }
497
        },
498
        case Instr::Jmp { args, .. } => {
499
            for arg in args {
500
                withReg(arg, f, ctx);
501
            }
502
        },
503
        case Instr::Br { a, b, thenArgs, elseArgs, .. } => {
504
            withReg(a, f, ctx);
505
            withReg(b, f, ctx);
506
            for arg in thenArgs {
507
                withReg(arg, f, ctx);
508
            }
509
            for arg in elseArgs {
510
                withReg(arg, f, ctx);
511
            }
512
        },
513
        case Instr::Switch { val, defaultArgs, cases, .. } => {
514
            withReg(val, f, ctx);
515
            for arg in defaultArgs {
516
                withReg(arg, f, ctx);
517
            }
518
            for c in cases {
519
                for arg in c.args {
520
                    withReg(arg, f, ctx);
521
                }
522
            }
523
        },
524
        case Instr::Ecall { num, a0, a1, a2, a3, .. } => {
525
            withReg(num, f, ctx);
526
            withReg(a0, f, ctx);
527
            withReg(a1, f, ctx);
528
            withReg(a2, f, ctx);
529
            withReg(a3, f, ctx);
530
        },
531
        case Instr::DeviceRead { handle, offset, .. } => {
532
            withReg(handle, f, ctx); withReg(offset, f, ctx);
533
        },
534
        case Instr::DeviceWrite { handle, offset, value, .. } => {
535
            withReg(handle, f, ctx); withReg(offset, f, ctx); withReg(value, f, ctx);
536
        },
537
        case Instr::Unreachable,
538
             Instr::Ebreak,
539
             Instr::MemoryFence => {},
540
    }
541
}
542
543
/// Call callback if value is a register.
544
unsafe fn withReg(val: Val, callback: unsafe fn(Reg, &mut opaque), ctx: &mut opaque) {
545
    if let case Val::Reg(r) = val {
546
        callback(r, ctx);
547
    }
548
}