compiler/
lib/
examples/
std/
arch/
char/
collections/
lang/
alloc/
ast/
gen/
il/
module/
parser/
resolver/
scanner/
alloc.rad
5.4 KiB
ast.rad
23.1 KiB
gen.rad
507 B
il.rad
15.3 KiB
lower.rad
271.6 KiB
module.rad
13.5 KiB
package.rad
1.2 KiB
parser.rad
78.7 KiB
resolver.rad
314.0 KiB
scanner.rad
17.4 KiB
sexpr.rad
6.3 KiB
strings.rad
2.2 KiB
types.rad
280 B
sys/
arch.rad
68 B
char.rad
855 B
collections.rad
39 B
fmt.rad
8.1 KiB
intrinsics.rad
683 B
io.rad
1.4 KiB
lang.rad
360 B
mem.rad
2.2 KiB
sys.rad
173 B
testing.rad
2.4 KiB
tests.rad
15.4 KiB
vec.rad
4.8 KiB
std.rad
358 B
scripts/
seed/
sublime/
test/
vim/
.gitignore
336 B
.gitsigners
112 B
LICENSE
1.1 KiB
Makefile
3.7 KiB
README
2.5 KiB
STYLE
2.5 KiB
std.lib
1.2 KiB
std.lib.test
373 B
lib/std/lang/il.rad
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 | |
| 63 | /// Unit tests for intermediate language traversal. |
| 64 | @test mod tests; |
| 65 | |
| 66 | use std::mem; |
| 67 | use std::lang::alloc; |
| 68 | |
| 69 | /// Source location for debug info. |
| 70 | /// |
| 71 | /// Associates an IL instruction with its originating source module and |
| 72 | /// byte offset. |
| 73 | export record SrcLoc { |
| 74 | /// Module identifier. |
| 75 | moduleId: u16, |
| 76 | /// Byte offset into the module's source file. |
| 77 | offset: u32, |
| 78 | } |
| 79 | |
| 80 | /////////////////////// |
| 81 | // Name Formatting // |
| 82 | /////////////////////// |
| 83 | |
| 84 | /// Separator for qualified symbol names. |
| 85 | export unsafe constant PATH_SEPARATOR: *[u8] = "::"; |
| 86 | |
| 87 | /// Format a qualified symbol name: `pkg::mod::path::name`. |
| 88 | export fn formatQualifiedName(arena: *mut alloc::Arena, path: *[*[u8]], name: *[u8]) -> *[u8] { |
| 89 | let mut totalLen: u32 = name.len; |
| 90 | for segment in path { |
| 91 | set totalLen += segment.len + PATH_SEPARATOR.len; |
| 92 | } |
| 93 | let buf = try! alloc::allocSlice(arena, 1, 1, totalLen) as *mut [u8]; |
| 94 | let mut pos: u32 = 0; |
| 95 | |
| 96 | for segment in path { |
| 97 | set pos += try! mem::copy(&mut buf[pos..], segment); |
| 98 | set pos += try! mem::copy(&mut buf[pos..], PATH_SEPARATOR); |
| 99 | } |
| 100 | try! mem::copy(&mut buf[pos..], name); |
| 101 | |
| 102 | return &buf[..totalLen]; |
| 103 | } |
| 104 | |
| 105 | /////////// |
| 106 | // Types // |
| 107 | /////////// |
| 108 | |
| 109 | /// IL type representation. Integer signedness is encoded in operations, not types. |
| 110 | export union Type { |
| 111 | /// 8-bit value. |
| 112 | W8, |
| 113 | /// 16-bit value. |
| 114 | W16, |
| 115 | /// 32-bit value. |
| 116 | W32, |
| 117 | /// 64-bit value (used for pointers on RV64). |
| 118 | W64, |
| 119 | } |
| 120 | |
| 121 | /// Get the size of a type in bytes. |
| 122 | export fn typeSize(t: Type) -> u32 { |
| 123 | match t { |
| 124 | case Type::W8 => return 1, |
| 125 | case Type::W16 => return 2, |
| 126 | case Type::W32 => return 4, |
| 127 | case Type::W64 => return 8, |
| 128 | } |
| 129 | } |
| 130 | |
| 131 | /// SSA register reference. |
| 132 | export record Reg { n: u32 } |
| 133 | |
| 134 | /// Instruction value. |
| 135 | export union Val { |
| 136 | /// Register reference. |
| 137 | Reg(Reg), |
| 138 | /// Immediate integer value. |
| 139 | Imm(i64), |
| 140 | /// Data symbol address (globals, constants, string literals). |
| 141 | DataSym(*[u8]), |
| 142 | /// Function address by symbol name. Used directly in call instructions |
| 143 | /// for direct calls, or stored first for indirect calls. |
| 144 | FnAddr(*[u8]), |
| 145 | /// Undefined value. Used when the value is to be discarded, |
| 146 | /// eg. in void returns. |
| 147 | Undef, |
| 148 | } |
| 149 | |
| 150 | /// Comparison operation for compare-and-branch. |
| 151 | export union CmpOp { Eq, Ne, Slt, Ult } |
| 152 | |
| 153 | /// Binary ALU operation kind. |
| 154 | export union BinOp { |
| 155 | // Arithmetic. |
| 156 | Add, Sub, Mul, Sdiv, Udiv, Srem, Urem, |
| 157 | // Comparison. |
| 158 | Eq, Ne, Slt, Sge, Ult, Uge, |
| 159 | // Bitwise. |
| 160 | And, Or, Xor, Shl, Sshr, Ushr, |
| 161 | } |
| 162 | |
| 163 | /// Unary ALU operation kind. |
| 164 | export union UnOp { |
| 165 | Neg, Not, |
| 166 | } |
| 167 | |
| 168 | ////////////////// |
| 169 | // Instructions // |
| 170 | ////////////////// |
| 171 | |
| 172 | /// Block parameter. |
| 173 | export record Param { |
| 174 | /// SSA register. |
| 175 | value: Reg, |
| 176 | /// Parameter type. |
| 177 | type: Type, |
| 178 | } |
| 179 | |
| 180 | /// Switch case mapping a constant value to a branch target. |
| 181 | export record SwitchCase { |
| 182 | /// The constant value to match against. |
| 183 | value: i64, |
| 184 | /// The target block index. |
| 185 | target: u32, |
| 186 | /// Arguments to pass to the target block. |
| 187 | args: *mut [Val], |
| 188 | } |
| 189 | |
| 190 | /// IL instruction. |
| 191 | /// SSA registers are represented as `Reg`, values as `Val`. |
| 192 | export union Instr { |
| 193 | /////////////////////// |
| 194 | // Memory operations // |
| 195 | /////////////////////// |
| 196 | |
| 197 | /// Allocate space on the stack: `reserve %dst <size> <alignment>;` |
| 198 | /// Size can be a register for dynamic stack allocation (eg. VLAs). |
| 199 | Reserve { dst: Reg, size: Val, alignment: u32 }, |
| 200 | /// Load a value from memory (zero-extending): `load <type> %dst %src <offset>;` |
| 201 | Load { typ: Type, dst: Reg, src: Reg, offset: i32 }, |
| 202 | /// Signed load from memory (sign-extending): `sload <type> %dst %src <offset>;` |
| 203 | Sload { typ: Type, dst: Reg, src: Reg, offset: i32 }, |
| 204 | /// Store a value to memory: `store <type> <src> %dst <offset>;` |
| 205 | Store { |
| 206 | /// Type being stored. |
| 207 | typ: Type, |
| 208 | /// Value being stored. |
| 209 | src: Val, |
| 210 | /// Destination address. |
| 211 | dst: Reg, |
| 212 | /// Byte offset from the base address. |
| 213 | offset: i32 |
| 214 | }, |
| 215 | /// Copy memory region: `blit %dst %src <size>;` |
| 216 | /// Size can be an immediate or a register (eg. for generics). |
| 217 | Blit { |
| 218 | /// Destination address. |
| 219 | dst: Reg, |
| 220 | /// Source address. |
| 221 | src: Reg, |
| 222 | /// Size to copy in bytes. |
| 223 | size: Val |
| 224 | }, |
| 225 | /// Copy a value into a register: `copy %dst <val>;`. |
| 226 | Copy { dst: Reg, val: Val }, |
| 227 | |
| 228 | ///////////////////// |
| 229 | // ALU operations // |
| 230 | ///////////////////// |
| 231 | |
| 232 | /// Binary ALU operation: `<op> <type> %dst <a> <b>;` |
| 233 | BinOp { op: BinOp, typ: Type, dst: Reg, a: Val, b: Val }, |
| 234 | /// Unary ALU operation: `<op> <type> %dst <a>;` |
| 235 | UnOp { op: UnOp, typ: Type, dst: Reg, a: Val }, |
| 236 | |
| 237 | ///////////////// |
| 238 | // Conversions // |
| 239 | ///////////////// |
| 240 | |
| 241 | /// Zero-extend from narrower type to word: `zext <type> %dst <val>;` |
| 242 | Zext { |
| 243 | /// Source type (I8 or I16). |
| 244 | typ: Type, |
| 245 | /// Destination register, always I32. |
| 246 | dst: Reg, |
| 247 | /// Source value. |
| 248 | val: Val, |
| 249 | }, |
| 250 | /// Sign-extend from narrower type to word: `sext <type> %dst <val>;` |
| 251 | Sext { |
| 252 | /// Source type (I8 or I16). |
| 253 | typ: Type, |
| 254 | /// Destination register, always I32. |
| 255 | dst: Reg, |
| 256 | /// Source value. |
| 257 | val: Val, |
| 258 | }, |
| 259 | |
| 260 | //////////////////// |
| 261 | // Function calls // |
| 262 | //////////////////// |
| 263 | |
| 264 | /// Call a function: `call <type> %dst $func(<arg>...);` |
| 265 | Call { |
| 266 | /// Return type. |
| 267 | retTy: Type, |
| 268 | /// Holds return value, for non-void function. |
| 269 | dst: ?Reg, |
| 270 | /// Function value, either a symbol or an address in a register. |
| 271 | func: Val, |
| 272 | /// Function arguments. |
| 273 | args: *[Val] |
| 274 | }, |
| 275 | |
| 276 | ///////////////// |
| 277 | // Terminators // |
| 278 | ///////////////// |
| 279 | |
| 280 | /// Return from function: `ret <val>;` or `ret;` |
| 281 | Ret { val: ?Val }, |
| 282 | /// Unconditional jump: `jmp @block(<arg>...);` |
| 283 | Jmp { target: u32, args: *mut [Val] }, |
| 284 | /// Compare-and-branch: `br.<op> <type> <a> <b> @then @else;` |
| 285 | Br { op: CmpOp, typ: Type, a: Val, b: Val, thenTarget: u32, thenArgs: *mut [Val], elseTarget: u32, elseArgs: *mut [Val] }, |
| 286 | /// Multi-way branch: `switch <val> (<n> @block) ... @default;` |
| 287 | Switch { val: Val, defaultTarget: u32, defaultArgs: *mut [Val], cases: *mut [SwitchCase] }, |
| 288 | /// Unreachable code marker: `unreachable;` |
| 289 | /// Indicates control flow cannot reach this point to allow for optimizations. |
| 290 | Unreachable, |
| 291 | |
| 292 | ///////////////// |
| 293 | // Intrinsics // |
| 294 | ///////////////// |
| 295 | |
| 296 | /// Environment call: `ecall %dst <num> <a0> <a1> <a2> <a3>;` |
| 297 | Ecall { dst: Reg, num: Val, a0: Val, a1: Val, a2: Val, a3: Val }, |
| 298 | /// Environment break: `ebreak;`. |
| 299 | /// Triggers a breakpoint exception for debugging. |
| 300 | Ebreak, |
| 301 | /// Full acquire/release memory fence. |
| 302 | MemoryFence, |
| 303 | } |
| 304 | |
| 305 | ////////////////////////// |
| 306 | // Blocks and Functions // |
| 307 | ////////////////////////// |
| 308 | |
| 309 | /// A basic block in a function. |
| 310 | /// |
| 311 | /// Basic blocks are instruction sequences with a single entry point and no branch |
| 312 | /// instruction, except possibly at the end of the sequence, where a terminator |
| 313 | /// may be found, ie. an instruction that terminates the sequence by jumping |
| 314 | /// to another sequence. |
| 315 | export record Block { |
| 316 | /// Block label. |
| 317 | label: *[u8], |
| 318 | /// Block parameters. |
| 319 | params: *[Param], |
| 320 | /// Instructions in the block. The last instruction must be a terminator. |
| 321 | instrs: *mut [Instr], |
| 322 | /// Source locations for debugging and error reporting. |
| 323 | /// One entry per instruction when debug info is enabled, empty otherwise. |
| 324 | locs: *[SrcLoc], |
| 325 | /// Predecessor block indices. Used for control flow analysis. |
| 326 | preds: *[u32], |
| 327 | /// Loop nesting depth. |
| 328 | /// Used for spill cost weighting in register allocation. |
| 329 | loopDepth: u32, |
| 330 | } |
| 331 | |
| 332 | /// An IL function. |
| 333 | export record Fn { |
| 334 | /// Qualified function name (e.g. `$mod$path$func`). |
| 335 | name: *[u8], |
| 336 | /// Function parameters. |
| 337 | params: *[Param], |
| 338 | /// Return type. |
| 339 | returnType: Type, |
| 340 | /// Whether the function is extern (no body). |
| 341 | isExtern: bool, |
| 342 | /// Whether the function is a leaf (contains no call or ecall instructions). |
| 343 | isLeaf: bool, |
| 344 | /// Basic blocks. Empty for extern functions. |
| 345 | blocks: *[Block], |
| 346 | } |
| 347 | |
| 348 | ///////////// |
| 349 | // Program // |
| 350 | ///////////// |
| 351 | |
| 352 | /// Data initializer item. |
| 353 | export union DataItem { |
| 354 | /// Typed value: `w32 42;` or `w8 255;` |
| 355 | Val { typ: Type, val: i64 }, |
| 356 | /// Symbol reference: `$symbol` |
| 357 | Sym(*[u8]), |
| 358 | /// Function reference: `$fnName` |
| 359 | Fn(*[u8]), |
| 360 | /// String literal bytes: `"hello"` (no auto null-terminator) |
| 361 | Str(*[u8]), |
| 362 | /// Undefined value. Used for padding and `void` returns. |
| 363 | Undef, |
| 364 | } |
| 365 | |
| 366 | /// Data initializer value with optional repeat count. |
| 367 | export record DataValue { |
| 368 | /// The item contained in the value. |
| 369 | item: DataItem, |
| 370 | /// The number of times the item should be repeated. |
| 371 | count: u32, |
| 372 | } |
| 373 | |
| 374 | /// Global data definition. |
| 375 | export record Data { |
| 376 | /// Data name. |
| 377 | name: *[u8], |
| 378 | /// Size in bytes. |
| 379 | size: u32, |
| 380 | /// Alignment requirement. |
| 381 | alignment: u32, |
| 382 | /// Whether this is read-only data. |
| 383 | /// Typically, `constant` declaration are read-only, while `static` |
| 384 | /// declarations are not. |
| 385 | readOnly: bool, |
| 386 | /// Whether writable data can be represented by zero-filled memory. |
| 387 | /// Zero-initialized data doesn't need to be written to the sidecar image. |
| 388 | isZeroInit: bool, |
| 389 | /// Initializer values. |
| 390 | values: *[DataValue], |
| 391 | } |
| 392 | |
| 393 | /// An IL program (compilation unit). |
| 394 | export record Program { |
| 395 | /// Global data. |
| 396 | data: *[Data], |
| 397 | /// Functions. |
| 398 | fns: *[*Fn], |
| 399 | } |
| 400 | |
| 401 | /////////////////////// |
| 402 | // Utility Functions // |
| 403 | /////////////////////// |
| 404 | |
| 405 | /// Get the destination register of an instruction, if any. |
| 406 | export fn instrDst(instr: Instr) -> ?Reg { |
| 407 | match instr { |
| 408 | case Instr::Reserve { dst, .. } => return dst, |
| 409 | case Instr::Load { dst, .. } => return dst, |
| 410 | case Instr::Sload { dst, .. } => return dst, |
| 411 | case Instr::Copy { dst, .. } => return dst, |
| 412 | case Instr::BinOp { dst, .. } => return dst, |
| 413 | case Instr::UnOp { dst, .. } => return dst, |
| 414 | case Instr::Zext { dst, .. } => return dst, |
| 415 | case Instr::Sext { dst, .. } => return dst, |
| 416 | case Instr::Call { dst, .. } => return dst, |
| 417 | case Instr::Ecall { dst, .. } => return dst, |
| 418 | else => return nil, |
| 419 | } |
| 420 | } |
| 421 | |
| 422 | /// Check if an instruction is a function call. |
| 423 | export fn isCall(instr: Instr) -> bool { |
| 424 | match instr { |
| 425 | case Instr::Call { .. }, |
| 426 | Instr::Ecall { .. } => return true, |
| 427 | else => return false, |
| 428 | } |
| 429 | } |
| 430 | |
| 431 | /// Call a function for each register used by an instruction. |
| 432 | /// This is called by the register allocator to analyze register usage. |
| 433 | export fn forEachReg(instr: Instr, f: fn(Reg, &mut opaque), ctx: &mut opaque) { |
| 434 | match instr { |
| 435 | case Instr::Reserve { size, .. } => |
| 436 | withReg(size, f, ctx), |
| 437 | case Instr::Load { src, .. } => f(src, ctx), |
| 438 | case Instr::Sload { src, .. } => f(src, ctx), |
| 439 | case Instr::Store { src, dst, .. } => { |
| 440 | withReg(src, f, ctx); |
| 441 | f(dst, ctx); |
| 442 | }, |
| 443 | case Instr::Blit { dst, src, size } => { |
| 444 | f(dst, ctx); |
| 445 | f(src, ctx); |
| 446 | withReg(size, f, ctx); |
| 447 | }, |
| 448 | case Instr::Copy { val, .. } => |
| 449 | withReg(val, f, ctx), |
| 450 | case Instr::BinOp { a, b, .. } => { |
| 451 | withReg(a, f, ctx); |
| 452 | withReg(b, f, ctx); |
| 453 | }, |
| 454 | case Instr::UnOp { a, .. } => |
| 455 | withReg(a, f, ctx), |
| 456 | case Instr::Zext { val, .. } => |
| 457 | withReg(val, f, ctx), |
| 458 | case Instr::Sext { val, .. } => |
| 459 | withReg(val, f, ctx), |
| 460 | case Instr::Call { func, args, .. } => { |
| 461 | withReg(func, f, ctx); |
| 462 | for arg in args { |
| 463 | withReg(arg, f, ctx); |
| 464 | } |
| 465 | }, |
| 466 | case Instr::Ret { val } => { |
| 467 | if let v = val { |
| 468 | withReg(v, f, ctx); |
| 469 | } |
| 470 | }, |
| 471 | case Instr::Jmp { args, .. } => { |
| 472 | for arg in args { |
| 473 | withReg(arg, f, ctx); |
| 474 | } |
| 475 | }, |
| 476 | case Instr::Br { a, b, thenArgs, elseArgs, .. } => { |
| 477 | withReg(a, f, ctx); |
| 478 | withReg(b, f, ctx); |
| 479 | for arg in thenArgs { |
| 480 | withReg(arg, f, ctx); |
| 481 | } |
| 482 | for arg in elseArgs { |
| 483 | withReg(arg, f, ctx); |
| 484 | } |
| 485 | }, |
| 486 | case Instr::Switch { val, defaultArgs, cases, .. } => { |
| 487 | withReg(val, f, ctx); |
| 488 | for arg in defaultArgs { |
| 489 | withReg(arg, f, ctx); |
| 490 | } |
| 491 | for c in cases { |
| 492 | for arg in c.args { |
| 493 | withReg(arg, f, ctx); |
| 494 | } |
| 495 | } |
| 496 | }, |
| 497 | case Instr::Ecall { num, a0, a1, a2, a3, .. } => { |
| 498 | withReg(num, f, ctx); |
| 499 | withReg(a0, f, ctx); |
| 500 | withReg(a1, f, ctx); |
| 501 | withReg(a2, f, ctx); |
| 502 | withReg(a3, f, ctx); |
| 503 | }, |
| 504 | case Instr::Unreachable, |
| 505 | Instr::Ebreak, |
| 506 | Instr::MemoryFence => {}, |
| 507 | } |
| 508 | } |
| 509 | |
| 510 | /// Call callback if value is a register. |
| 511 | fn withReg(val: Val, callback: fn(Reg, &mut opaque), ctx: &mut opaque) { |
| 512 | if let case Val::Reg(r) = val { |
| 513 | callback(r, ctx); |
| 514 | } |
| 515 | } |