nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
68 kB
1880 lines
1//! WebAssembly codegen from monomorphised MIR.
2//!
3//! # Value representation
4//!
5//! | Gleam type | Wasm |
6//! |------------|------|
7//! | `Int` | `i64` |
8//! | `Bool` | `i32` (`0` / `1`) |
9//! | `Float` | `f64` |
10//! | `String` | `i32` pointer to `{ len: u32, data: [u8; len] }` in linear memory |
11//!
12//! String literals are placed in the data segment. Concatenation allocates new
13//! objects with a simple bump allocator (`$gleam_heap_ptr` global).
14//!
15//! # Running with wasmtime
16//!
17//! If the module defines a zero-argument `main`, the backend also emits a WASI
18//! `_start` entry that calls `main` and prints the result to stdout via
19//! `wasi_snapshot_preview1::fd_write`. Run with:
20//!
21//! ```text
22//! wasmtime path/to/package.wasm
23//! ```
24
25use std::collections::HashMap;
26
27use ecow::EcoString;
28use num_bigint::BigInt;
29use num_traits::ToPrimitive;
30use wasm_encoder::{
31 BlockType, CodeSection, ConstExpr, DataSection, EntityType, ExportKind, ExportSection,
32 Function, FunctionSection, GlobalSection, GlobalType, Ieee64, ImportSection, MemArg,
33 MemorySection, MemoryType, Module, TypeSection, ValType,
34};
35
36use crate::wasm::mir::ast::{self, CompleteType, Expression};
37
38pub mod mir;
39pub mod zed;
40
41/// Bytes reserved at the start of linear memory for WASI iovecs and itoa.
42/// Layout:
43/// - `0..8` — `ciovec { buf: i32, len: i32 }`
44/// - `8..12` — `nwritten: i32`
45/// - `16..56` — decimal formatting buffer
46const SCRATCH_SIZE: u32 = 64;
47const SCRATCH_IOV: u32 = 0;
48const SCRATCH_NWRITTEN: u32 = 8;
49const SCRATCH_ITOA_END: u32 = 56;
50
51/// Compile a monomorphised MIR module into a WebAssembly binary.
52pub fn compile(module: ast::Module<CompleteType>) -> Vec<u8> {
53 Compiler::new(&module).compile()
54}
55
56/// Merge monomorphised modules into a single package module.
57///
58/// Cross-module calls become same-module calls with mangled names
59/// (`{module}__{function}`), so the backend can emit one linked Wasm artifact.
60pub fn link_package(modules: Vec<ast::Module<CompleteType>>) -> ast::Module<CompleteType> {
61 use ecow::eco_format;
62
63 let package_name = modules
64 .first()
65 .map(|module| module.name.clone())
66 .unwrap_or_else(|| "package".into());
67
68 let mut linked = ast::Module {
69 name: package_name,
70 functions: Vec::new(),
71 };
72
73 for module in modules {
74 for mut function in module.functions {
75 function.name = eco_format!("{}__{}", module.name, function.name);
76 if let Some(body) = &mut function.body {
77 mangle_function_refs(body);
78 }
79 linked.functions.push(function);
80 }
81 }
82
83 linked
84}
85
86fn mangle_function_refs(expression: &mut Expression<CompleteType>) {
87 use ecow::eco_format;
88
89 match expression {
90 Expression::FunctionRef { module, name, .. } => {
91 *name = eco_format!("{}__{}", module, name);
92 *module = "".into();
93 }
94 Expression::Block(expressions) => {
95 for expression in expressions {
96 mangle_function_refs(expression);
97 }
98 }
99 Expression::Set { value, .. }
100 | Expression::TupleAccess { value, .. }
101 | Expression::StructTag { value }
102 | Expression::StructAccess { value, .. } => mangle_function_refs(value),
103 Expression::Equals { lhs, rhs }
104 | Expression::NotEquals { lhs, rhs }
105 | Expression::IntGt { lhs, rhs }
106 | Expression::IntGtEq { lhs, rhs }
107 | Expression::IntLt { lhs, rhs }
108 | Expression::IntLtEq { lhs, rhs }
109 | Expression::IntAdd { lhs, rhs }
110 | Expression::IntSub { lhs, rhs }
111 | Expression::IntMul { lhs, rhs }
112 | Expression::IntDiv { lhs, rhs }
113 | Expression::IntRem { lhs, rhs }
114 | Expression::FloatGt { lhs, rhs }
115 | Expression::FloatGtEq { lhs, rhs }
116 | Expression::FloatLt { lhs, rhs }
117 | Expression::FloatLtEq { lhs, rhs }
118 | Expression::FloatAdd { lhs, rhs }
119 | Expression::FloatSub { lhs, rhs }
120 | Expression::FloatMul { lhs, rhs }
121 | Expression::FloatDiv { lhs, rhs }
122 | Expression::StringConcat { lhs, rhs } => {
123 mangle_function_refs(lhs);
124 mangle_function_refs(rhs);
125 }
126 Expression::If { cond, then, else_ } => {
127 mangle_function_refs(cond);
128 mangle_function_refs(then);
129 mangle_function_refs(else_);
130 }
131 Expression::Call { target, args, .. } => {
132 mangle_function_refs(target);
133 for arg in args {
134 mangle_function_refs(arg);
135 }
136 }
137 Expression::List { items, tail, .. } => {
138 for item in items {
139 mangle_function_refs(item);
140 }
141 if let Some(tail) = tail {
142 mangle_function_refs(tail);
143 }
144 }
145 Expression::Tuple { items, .. } | Expression::Struct { items, .. } => {
146 for item in items {
147 mangle_function_refs(item);
148 }
149 }
150 Expression::Var(_)
151 | Expression::Int { .. }
152 | Expression::Float { .. }
153 | Expression::Bool { .. }
154 | Expression::String { .. }
155 | Expression::Panic { .. } => {}
156 }
157}
158
159/// Indices of synthesised runtime helpers (only present when strings are used).
160struct StringRuntime {
161 alloc: u32,
162 concat: u32,
163 eq: u32,
164}
165
166/// WASI command entry for modules that export a zero-arg `main`.
167struct WasiEntry {
168 /// Imported `fd_write` function index (always 0 when present).
169 fd_write: u32,
170 main_index: u32,
171 main_return: CompleteType,
172 print_string: u32,
173 print_i64: u32,
174 start: u32,
175 newline_offset: u32,
176}
177
178struct Compiler<'a> {
179 module: &'a ast::Module<CompleteType>,
180 /// Function name → Wasm function index (including imports).
181 function_indices: HashMap<EcoString, u32>,
182 /// Unique string literal → data offset of its heap object.
183 string_offsets: HashMap<EcoString, u32>,
184 /// Raw bytes written into the active data segment (starting at address 0).
185 static_data: Vec<u8>,
186 /// First free heap address after static data (4-byte aligned).
187 heap_start: u32,
188 /// Offset of the interned empty string (valid pointer for dummies).
189 empty_string_offset: u32,
190 string_runtime: Option<StringRuntime>,
191 wasi_entry: Option<WasiEntry>,
192 /// Number of imported functions (shifts defined-function indices).
193 import_func_count: u32,
194}
195
196impl<'a> Compiler<'a> {
197 fn new(module: &'a ast::Module<CompleteType>) -> Self {
198 let main = module.functions.iter().find(|function| {
199 is_main_function(&function.name)
200 && function.parameters.is_empty()
201 && function.external_wasm.is_none()
202 && function.body.is_some()
203 });
204 let emit_wasi = main.is_some();
205 let needs_heap = module_needs_heap(module) || module_uses_strings(module) || emit_wasi;
206 let uses_strings = module_uses_strings(module) || emit_wasi;
207
208 // Import order: optional WASI fd_write, then `@external(wasm, …)` functions.
209 let external_functions: Vec<_> = module
210 .functions
211 .iter()
212 .filter(|function| function.external_wasm.is_some())
213 .collect();
214 let defined_functions: Vec<_> = module
215 .functions
216 .iter()
217 .filter(|function| function.external_wasm.is_none())
218 .collect();
219
220 let import_func_count = u32::from(emit_wasi) + external_functions.len() as u32;
221
222 let mut function_indices = HashMap::new();
223 let mut next_index = u32::from(emit_wasi);
224 for function in &external_functions {
225 _ = function_indices.insert(function.name.clone(), next_index);
226 next_index += 1;
227 }
228 for function in &defined_functions {
229 _ = function_indices.insert(function.name.clone(), next_index);
230 next_index += 1;
231 }
232
233 let mut compiler = Self {
234 module,
235 function_indices,
236 string_offsets: HashMap::new(),
237 static_data: Vec::new(),
238 heap_start: 0,
239 empty_string_offset: 0,
240 string_runtime: None,
241 wasi_entry: None,
242 import_func_count,
243 };
244
245 if needs_heap {
246 // Reserve scratch so string objects never overlap WASI temp space.
247 compiler.static_data.resize(SCRATCH_SIZE as usize, 0);
248 }
249
250 // Intern every static string *before* freezing `heap_start`, including
251 // the WASI newline, so bump-allocation cannot overwrite them.
252 let mut newline_offset = 0u32;
253 if uses_strings {
254 compiler.empty_string_offset = compiler.intern_string("");
255 for function in &module.functions {
256 if let Some(body) = &function.body {
257 collect_strings_from_expression(body, &mut |value| {
258 let _ = compiler.intern_string(value);
259 });
260 }
261 }
262 }
263 if emit_wasi {
264 newline_offset = compiler.intern_string("\n");
265 }
266
267 if needs_heap {
268 compiler.heap_start = align4(compiler.static_data.len() as u32);
269 }
270
271 if needs_heap {
272 let base = import_func_count + defined_functions.len() as u32;
273 compiler.string_runtime = Some(StringRuntime {
274 alloc: base,
275 concat: base + 1,
276 eq: base + 2,
277 });
278 }
279
280 if emit_wasi {
281 let main = main.expect("main checked above");
282 let mut next = import_func_count + defined_functions.len() as u32;
283 if compiler.string_runtime.is_some() {
284 next += 3;
285 }
286 let print_string = next;
287 let print_i64 = next + 1;
288 let start = next + 2;
289 compiler.wasi_entry = Some(WasiEntry {
290 fd_write: 0,
291 main_index: *compiler
292 .function_indices
293 .get(&main.name)
294 .expect("main index"),
295 main_return: main.return_type.clone(),
296 print_string,
297 print_i64,
298 start,
299 newline_offset,
300 });
301 }
302
303 compiler
304 }
305
306 fn intern_string(&mut self, value: &str) -> u32 {
307 if let Some(&offset) = self.string_offsets.get(value) {
308 return offset;
309 }
310
311 let offset = align4(self.static_data.len() as u32);
312 self.static_data.resize(offset as usize, 0);
313
314 let bytes = value.as_bytes();
315 let len = bytes.len() as u32;
316 self.static_data.extend_from_slice(&len.to_le_bytes());
317 self.static_data.extend_from_slice(bytes);
318
319 _ = self.string_offsets.insert(value.into(), offset);
320 offset
321 }
322
323 fn compile(self) -> Vec<u8> {
324 let mut wasm = Module::new();
325
326 let mut types = TypeSection::new();
327 let mut imports = ImportSection::new();
328 let mut functions = FunctionSection::new();
329 let mut exports = ExportSection::new();
330 let mut codes = CodeSection::new();
331
332 // Predeclare the fd_write type if we need WASI (type index 0).
333 let fd_write_type = if self.wasi_entry.is_some() {
334 let _ = types.ty().function(
335 vec![ValType::I32, ValType::I32, ValType::I32, ValType::I32],
336 vec![ValType::I32],
337 );
338 Some(0u32)
339 } else {
340 None
341 };
342
343 if let Some(fd_type) = fd_write_type {
344 let _ = imports.import(
345 "wasi_snapshot_preview1",
346 "fd_write",
347 EntityType::Function(fd_type),
348 );
349 }
350
351 // External Wasm imports (function types, then import entries).
352 for function in self
353 .module
354 .functions
355 .iter()
356 .filter(|function| function.external_wasm.is_some())
357 {
358 let params: Vec<ValType> = function
359 .parameters
360 .iter()
361 .map(|parameter| val_type(¶meter.type_))
362 .collect();
363 let results = vec![val_type(&function.return_type)];
364 let type_index = types.len();
365 let _ = types.ty().function(params, results);
366 let (module_name, func_name) = function
367 .external_wasm
368 .as_ref()
369 .expect("filtered to external");
370 let _ = imports.import(
371 module_name.as_str(),
372 func_name.as_str(),
373 EntityType::Function(type_index),
374 );
375 }
376
377 // Defined user functions.
378 for function in self
379 .module
380 .functions
381 .iter()
382 .filter(|function| function.external_wasm.is_none())
383 {
384 let params: Vec<ValType> = function
385 .parameters
386 .iter()
387 .map(|parameter| val_type(¶meter.type_))
388 .collect();
389 let results = vec![val_type(&function.return_type)];
390 let type_index = types.len();
391 let _ = types.ty().function(params, results);
392 let _ = functions.function(type_index);
393 let wasm_index = *self
394 .function_indices
395 .get(&function.name)
396 .expect("defined function index");
397 let _ = exports.export(&function.name, ExportKind::Func, wasm_index);
398 let _ = codes.function(&self.compile_function(function));
399 }
400
401 // String / heap runtime helpers.
402 if let Some(runtime) = &self.string_runtime {
403 let alloc_ty = types.len();
404 let _ = types.ty().function(vec![ValType::I32], vec![ValType::I32]);
405 let _ = functions.function(alloc_ty);
406
407 let concat_ty = types.len();
408 let _ = types
409 .ty()
410 .function(vec![ValType::I32, ValType::I32], vec![ValType::I32]);
411 let _ = functions.function(concat_ty);
412
413 let eq_ty = types.len();
414 let _ = types
415 .ty()
416 .function(vec![ValType::I32, ValType::I32], vec![ValType::I32]);
417 let _ = functions.function(eq_ty);
418
419 let _ = codes.function(&compile_alloc());
420 let _ = codes.function(&compile_string_concat(runtime.alloc));
421 let _ = codes.function(&compile_string_eq());
422 }
423
424 // WASI print helpers + _start.
425 if let Some(entry) = &self.wasi_entry {
426 let print_string_ty = types.len();
427 let _ = types.ty().function(vec![ValType::I32], vec![]);
428 let _ = functions.function(print_string_ty);
429
430 let print_i64_ty = types.len();
431 let _ = types.ty().function(vec![ValType::I64], vec![]);
432 let _ = functions.function(print_i64_ty);
433
434 let start_ty = types.len();
435 let _ = types.ty().function(vec![], vec![]);
436 let _ = functions.function(start_ty);
437
438 let _ = codes.function(&compile_print_string(entry.fd_write));
439 let _ = codes.function(&compile_print_i64(entry.fd_write));
440 let _ = codes.function(&compile_start(entry));
441 let _ = exports.export("_start", ExportKind::Func, entry.start);
442 }
443
444 let needs_memory = self.string_runtime.is_some() || self.wasi_entry.is_some();
445
446 let _ = wasm.section(&types);
447 if !imports.is_empty() {
448 let _ = wasm.section(&imports);
449 }
450 let _ = wasm.section(&functions);
451
452 if needs_memory {
453 let mut memories = MemorySection::new();
454 let _ = memories.memory(MemoryType {
455 minimum: 1,
456 maximum: None,
457 memory64: false,
458 shared: false,
459 page_size_log2: None,
460 });
461 let _ = wasm.section(&memories);
462
463 if self.string_runtime.is_some() {
464 let mut globals = GlobalSection::new();
465 let _ = globals.global(
466 GlobalType {
467 val_type: ValType::I32,
468 mutable: true,
469 shared: false,
470 },
471 &ConstExpr::i32_const(self.heap_start as i32),
472 );
473 let _ = wasm.section(&globals);
474 }
475
476 let _ = exports.export("memory", ExportKind::Memory, 0);
477 }
478
479 let _ = wasm.section(&exports);
480 let _ = wasm.section(&codes);
481
482 if needs_memory && !self.static_data.is_empty() {
483 let mut data = DataSection::new();
484 let _ = data.active(
485 0,
486 &ConstExpr::i32_const(0),
487 self.static_data.iter().copied(),
488 );
489 let _ = wasm.section(&data);
490 }
491
492 wasm.finish()
493 }
494
495 fn compile_function(&self, function: &ast::Function<CompleteType>) -> Function {
496 let body_expr = function
497 .body
498 .as_ref()
499 .expect("defined function has a body");
500 let mut locals = LocalAllocator::new(function);
501 locals.collect_from_expression(body_expr);
502 locals.reserve_tmps();
503
504 let mut body = Function::new_with_locals_types(locals.extra_locals.iter().copied());
505 self.emit_expression(&mut body, &mut locals, body_expr);
506 let _ = body.instructions().end();
507 body
508 }
509
510 fn emit_expression(
511 &self,
512 body: &mut Function,
513 locals: &mut LocalAllocator,
514 expression: &Expression<CompleteType>,
515 ) {
516 match expression {
517 Expression::Block(expressions) => {
518 assert!(
519 !expressions.is_empty(),
520 "MIR blocks must contain at least one expression"
521 );
522 let last = expressions.len() - 1;
523 for (index, expression) in expressions.iter().enumerate() {
524 match expression {
525 Expression::Set { name, value } => {
526 self.emit_expression(body, locals, value);
527 let local = locals.index(&name.name);
528 if index == last {
529 let _ = body.instructions().local_tee(local);
530 } else {
531 let _ = body.instructions().local_set(local);
532 }
533 }
534 other => {
535 self.emit_expression(body, locals, other);
536 if index != last {
537 let _ = body.instructions().drop();
538 }
539 }
540 }
541 }
542 }
543
544 Expression::FunctionRef { .. } => {
545 panic!("bare function references are not supported in Wasm yet")
546 }
547
548 Expression::Var(var) => {
549 let local = locals.index(&var.name);
550 let _ = body.instructions().local_get(local);
551 }
552
553 Expression::Int { value } => {
554 let _ = body.instructions().i64_const(bigint_to_i64(value));
555 }
556
557 Expression::Float { value } => {
558 let float: f64 = value
559 .parse()
560 .unwrap_or_else(|_| panic!("invalid float literal: {value}"));
561 let _ = body.instructions().f64_const(Ieee64::from(float));
562 }
563
564 Expression::Bool { value } => {
565 let _ = body.instructions().i32_const(i32::from(*value));
566 }
567
568 Expression::String { value } => {
569 let offset = self
570 .string_offsets
571 .get(value)
572 .unwrap_or_else(|| panic!("string literal was not interned: {value:?}"));
573 let _ = body.instructions().i32_const(*offset as i32);
574 }
575
576 Expression::Equals { lhs, rhs } => {
577 self.emit_eq(body, locals, lhs, rhs, true);
578 }
579
580 Expression::NotEquals { lhs, rhs } => {
581 self.emit_eq(body, locals, lhs, rhs, false);
582 }
583
584 Expression::IntGt { lhs, rhs } => {
585 self.emit_binary(body, locals, lhs, rhs, |b| {
586 let _ = b.instructions().i64_gt_s();
587 });
588 }
589 Expression::IntGtEq { lhs, rhs } => {
590 self.emit_binary(body, locals, lhs, rhs, |b| {
591 let _ = b.instructions().i64_ge_s();
592 });
593 }
594 Expression::IntLt { lhs, rhs } => {
595 self.emit_binary(body, locals, lhs, rhs, |b| {
596 let _ = b.instructions().i64_lt_s();
597 });
598 }
599 Expression::IntLtEq { lhs, rhs } => {
600 self.emit_binary(body, locals, lhs, rhs, |b| {
601 let _ = b.instructions().i64_le_s();
602 });
603 }
604 Expression::IntAdd { lhs, rhs } => {
605 self.emit_binary(body, locals, lhs, rhs, |b| {
606 let _ = b.instructions().i64_add();
607 });
608 }
609 Expression::IntSub { lhs, rhs } => {
610 self.emit_binary(body, locals, lhs, rhs, |b| {
611 let _ = b.instructions().i64_sub();
612 });
613 }
614 Expression::IntMul { lhs, rhs } => {
615 self.emit_binary(body, locals, lhs, rhs, |b| {
616 let _ = b.instructions().i64_mul();
617 });
618 }
619 Expression::IntDiv { lhs, rhs } => {
620 // Gleam integer division truncates toward zero.
621 self.emit_binary(body, locals, lhs, rhs, |b| {
622 let _ = b.instructions().i64_div_s();
623 });
624 }
625 Expression::IntRem { lhs, rhs } => {
626 self.emit_binary(body, locals, lhs, rhs, |b| {
627 let _ = b.instructions().i64_rem_s();
628 });
629 }
630
631 Expression::FloatGt { lhs, rhs } => {
632 self.emit_binary(body, locals, lhs, rhs, |b| {
633 let _ = b.instructions().f64_gt();
634 });
635 }
636 Expression::FloatGtEq { lhs, rhs } => {
637 self.emit_binary(body, locals, lhs, rhs, |b| {
638 let _ = b.instructions().f64_ge();
639 });
640 }
641 Expression::FloatLt { lhs, rhs } => {
642 self.emit_binary(body, locals, lhs, rhs, |b| {
643 let _ = b.instructions().f64_lt();
644 });
645 }
646 Expression::FloatLtEq { lhs, rhs } => {
647 self.emit_binary(body, locals, lhs, rhs, |b| {
648 let _ = b.instructions().f64_le();
649 });
650 }
651 Expression::FloatAdd { lhs, rhs } => {
652 self.emit_binary(body, locals, lhs, rhs, |b| {
653 let _ = b.instructions().f64_add();
654 });
655 }
656 Expression::FloatSub { lhs, rhs } => {
657 self.emit_binary(body, locals, lhs, rhs, |b| {
658 let _ = b.instructions().f64_sub();
659 });
660 }
661 Expression::FloatMul { lhs, rhs } => {
662 self.emit_binary(body, locals, lhs, rhs, |b| {
663 let _ = b.instructions().f64_mul();
664 });
665 }
666 Expression::FloatDiv { lhs, rhs } => {
667 self.emit_binary(body, locals, lhs, rhs, |b| {
668 let _ = b.instructions().f64_div();
669 });
670 }
671
672 Expression::StringConcat { lhs, rhs } => {
673 let runtime = self
674 .string_runtime
675 .as_ref()
676 .expect("string runtime required for concatenation");
677 self.emit_expression(body, locals, lhs);
678 self.emit_expression(body, locals, rhs);
679 let _ = body.instructions().call(runtime.concat);
680 }
681
682 Expression::List { items, tail, type_ } => {
683 self.emit_list(body, locals, items, tail.as_deref(), type_);
684 }
685
686 Expression::Tuple { items, type_ } => {
687 // Tuples share the struct layout with tag 0.
688 self.emit_struct(body, locals, 0, items, type_);
689 }
690
691 Expression::TupleAccess { value, index, type_ } => {
692 self.emit_expression(body, locals, value);
693 // Tuple fields start at offset 4 (after tag).
694 let offset = 4 + *index * 4;
695 self.emit_field_load(body, locals, type_, offset);
696 }
697
698 Expression::Struct { tag, items, type_ } => {
699 self.emit_struct(body, locals, *tag, items, type_);
700 }
701
702 Expression::StructTag { value } => {
703 // Lists use the null pointer as empty; treat pointer 0 as tag 0
704 // is wrong for tag load — StructTag is only used on records.
705 // For lists empty-check we compare pointers, not tags.
706 // Loading tag at offset 0:
707 self.emit_expression(body, locals, value);
708 // Convert to i64 so Equals with Int tags type-checks on the stack
709 // as the MIR type of StructTag is Int.
710 let tmp = locals.alloc_tmp(ValType::I32);
711 let _ = body.instructions().local_tee(tmp);
712 let _ = body.instructions().i32_load(mem_arg(0, 2));
713 let _ = body.instructions().i64_extend_i32_u();
714 let _ = tmp; // keep tmp live for tee side-effect only
715 }
716
717 Expression::StructAccess {
718 value,
719 index,
720 type_,
721 } => {
722 self.emit_expression(body, locals, value);
723 match value.type_() {
724 CompleteType::List(_) => {
725 // Cons cell: head @0, tail @4 (no tag).
726 let offset = *index * 4;
727 self.emit_field_load(body, locals, type_, offset);
728 }
729 _ => {
730 // Record/tuple: tag @0, fields @4 + i*4 (i32 slots).
731 let offset = 4 + *index * 4;
732 self.emit_field_load(body, locals, type_, offset);
733 }
734 }
735 }
736
737 Expression::Set { name, value } => {
738 // Standalone set used as an expression value.
739 self.emit_expression(body, locals, value);
740 let local = locals.index(&name.name);
741 let _ = body.instructions().local_tee(local);
742 }
743
744 Expression::If { cond, then, else_ } => {
745 self.emit_expression(body, locals, cond);
746 let result_type = block_type(&then.type_());
747 let _ = body.instructions().if_(result_type);
748 self.emit_expression(body, locals, then);
749 let _ = body.instructions().else_();
750 self.emit_expression(body, locals, else_);
751 let _ = body.instructions().end();
752 }
753
754 Expression::Call {
755 target,
756 args,
757 type_: _,
758 } => {
759 for arg in args {
760 self.emit_expression(body, locals, arg);
761 }
762
763 match target.as_ref() {
764 Expression::FunctionRef {
765 module: _,
766 name,
767 arity: _,
768 type_: _,
769 } => {
770 let index = self.function_indices.get(name).unwrap_or_else(|| {
771 panic!("unknown function `{name}` in module `{}`", self.module.name)
772 });
773 let _ = body.instructions().call(*index);
774 }
775 _ => panic!("indirect calls are not supported in Wasm yet"),
776 }
777 }
778
779 Expression::Panic { type_ } => {
780 let _ = body.instructions().unreachable();
781 // Keep the stack typed for surrounding expressions.
782 push_dummy_value(body, type_);
783 }
784 }
785 }
786
787 fn emit_binary(
788 &self,
789 body: &mut Function,
790 locals: &mut LocalAllocator,
791 lhs: &Expression<CompleteType>,
792 rhs: &Expression<CompleteType>,
793 op: impl FnOnce(&mut Function),
794 ) {
795 self.emit_expression(body, locals, lhs);
796 self.emit_expression(body, locals, rhs);
797 op(body);
798 }
799
800 fn emit_eq(
801 &self,
802 body: &mut Function,
803 locals: &mut LocalAllocator,
804 lhs: &Expression<CompleteType>,
805 rhs: &Expression<CompleteType>,
806 equal: bool,
807 ) {
808 self.emit_expression(body, locals, lhs);
809 self.emit_expression(body, locals, rhs);
810 match lhs.type_() {
811 CompleteType::Int => {
812 if equal {
813 let _ = body.instructions().i64_eq();
814 } else {
815 let _ = body.instructions().i64_ne();
816 }
817 }
818 CompleteType::Bool => {
819 if equal {
820 let _ = body.instructions().i32_eq();
821 } else {
822 let _ = body.instructions().i32_ne();
823 }
824 }
825 CompleteType::Float => {
826 if equal {
827 let _ = body.instructions().f64_eq();
828 } else {
829 let _ = body.instructions().f64_ne();
830 }
831 }
832 CompleteType::String => {
833 let runtime = self
834 .string_runtime
835 .as_ref()
836 .expect("string runtime required for string equality");
837 let _ = body.instructions().call(runtime.eq);
838 if !equal {
839 let _ = body.instructions().i32_eqz();
840 }
841 }
842 CompleteType::List(_)
843 | CompleteType::Struct { .. }
844 | CompleteType::Tuple { .. }
845 | CompleteType::Func { .. } => {
846 if equal {
847 let _ = body.instructions().i32_eq();
848 } else {
849 let _ = body.instructions().i32_ne();
850 }
851 }
852 }
853 }
854
855 fn emit_struct(
856 &self,
857 body: &mut Function,
858 locals: &mut LocalAllocator,
859 tag: u32,
860 items: &[Expression<CompleteType>],
861 type_: &CompleteType,
862 ) {
863 let runtime = self
864 .string_runtime
865 .as_ref()
866 .expect("heap runtime required for struct allocation");
867
868 // size = 4 (tag) + 4 * nfields (i32 slots). Int/Float fields are
869 // currently stored truncated/reinterpreated as i32 for the zed surface.
870 let size = 4 + items.len() as i32 * 4;
871 let _ = body.instructions().i32_const(size);
872 let _ = body.instructions().call(runtime.alloc);
873 let ptr = locals.alloc_tmp(ValType::I32);
874 let _ = body.instructions().local_set(ptr);
875
876 // Store tag.
877 let _ = body.instructions().local_get(ptr);
878 let _ = body.instructions().i32_const(tag as i32);
879 let _ = body.instructions().i32_store(mem_arg(0, 2));
880
881 for (index, item) in items.iter().enumerate() {
882 let _ = body.instructions().local_get(ptr);
883 self.emit_expression(body, locals, item);
884 self.emit_field_store(body, locals, &item.type_(), 4 + index as u64 * 4);
885 }
886
887 let _ = body.instructions().local_get(ptr);
888 let _ = type_;
889 }
890
891 fn emit_list(
892 &self,
893 body: &mut Function,
894 locals: &mut LocalAllocator,
895 items: &[Expression<CompleteType>],
896 tail: Option<&Expression<CompleteType>>,
897 type_: &CompleteType,
898 ) {
899 // Start from tail (or null for empty).
900 if let Some(tail) = tail {
901 self.emit_expression(body, locals, tail);
902 } else {
903 let _ = body.instructions().i32_const(0);
904 }
905 let acc = locals.alloc_tmp(ValType::I32);
906 let _ = body.instructions().local_set(acc);
907
908 if items.is_empty() {
909 let _ = body.instructions().local_get(acc);
910 let _ = type_;
911 return;
912 }
913
914 let runtime = self
915 .string_runtime
916 .as_ref()
917 .expect("heap runtime required for list allocation");
918
919 // Build right-to-left so the first item ends up at the head.
920 for item in items.iter().rev() {
921 // cons = alloc(8); store head; store tail; acc = cons
922 let _ = body.instructions().i32_const(8);
923 let _ = body.instructions().call(runtime.alloc);
924 let cell = locals.alloc_tmp(ValType::I32);
925 let _ = body.instructions().local_set(cell);
926
927 let _ = body.instructions().local_get(cell);
928 self.emit_expression(body, locals, item);
929 self.emit_field_store(body, locals, &item.type_(), 0);
930
931 let _ = body.instructions().local_get(cell);
932 let _ = body.instructions().local_get(acc);
933 let _ = body.instructions().i32_store(mem_arg(4, 2));
934
935 let _ = body.instructions().local_get(cell);
936 let _ = body.instructions().local_set(acc);
937 }
938
939 let _ = body.instructions().local_get(acc);
940 let _ = type_;
941 }
942
943 fn emit_field_load(
944 &self,
945 body: &mut Function,
946 locals: &mut LocalAllocator,
947 field_type: &CompleteType,
948 offset: u64,
949 ) {
950 // Pointer to object is on the stack.
951 match field_type {
952 CompleteType::Int => {
953 let _ = body.instructions().i32_load(mem_arg(offset, 2));
954 let _ = body.instructions().i64_extend_i32_s();
955 }
956 CompleteType::Float => {
957 let _ = body.instructions().f64_load(mem_arg(offset, 3));
958 }
959 CompleteType::Bool
960 | CompleteType::String
961 | CompleteType::List(_)
962 | CompleteType::Struct { .. }
963 | CompleteType::Tuple { .. }
964 | CompleteType::Func { .. } => {
965 let _ = body.instructions().i32_load(mem_arg(offset, 2));
966 }
967 }
968 let _ = locals;
969 }
970
971 fn emit_field_store(
972 &self,
973 body: &mut Function,
974 locals: &mut LocalAllocator,
975 field_type: &CompleteType,
976 offset: u64,
977 ) {
978 // Stack: base_ptr, field_value
979 match field_type {
980 CompleteType::Int => {
981 let _ = body.instructions().i32_wrap_i64();
982 let _ = body.instructions().i32_store(mem_arg(offset, 2));
983 }
984 CompleteType::Float => {
985 let _ = body.instructions().f64_store(mem_arg(offset, 3));
986 }
987 CompleteType::Bool
988 | CompleteType::String
989 | CompleteType::List(_)
990 | CompleteType::Struct { .. }
991 | CompleteType::Tuple { .. }
992 | CompleteType::Func { .. } => {
993 let _ = body.instructions().i32_store(mem_arg(offset, 2));
994 }
995 }
996 let _ = locals;
997 }
998}
999
1000// ---------------------------------------------------------------------------
1001// Runtime helpers
1002// ---------------------------------------------------------------------------
1003
1004const HEAP_GLOBAL: u32 = 0;
1005
1006fn mem_arg(offset: u64, align: u32) -> MemArg {
1007 MemArg {
1008 offset,
1009 align,
1010 memory_index: 0,
1011 }
1012}
1013
1014/// `print_string(s)` — write a Gleam string to stdout via WASI `fd_write`.
1015fn compile_print_string(fd_write: u32) -> Function {
1016 // param: s=0
1017 let mut f = Function::new([]);
1018 // iov.buf = s + 4
1019 let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
1020 let _ = f.instructions().local_get(0);
1021 let _ = f.instructions().i32_const(4);
1022 let _ = f.instructions().i32_add();
1023 let _ = f.instructions().i32_store(mem_arg(0, 2));
1024 // iov.len = *s
1025 let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
1026 let _ = f.instructions().local_get(0);
1027 let _ = f.instructions().i32_load(mem_arg(0, 2));
1028 let _ = f.instructions().i32_store(mem_arg(4, 2));
1029 // fd_write(1, iov, 1, &nwritten)
1030 let _ = f.instructions().i32_const(1);
1031 let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
1032 let _ = f.instructions().i32_const(1);
1033 let _ = f.instructions().i32_const(SCRATCH_NWRITTEN as i32);
1034 let _ = f.instructions().call(fd_write);
1035 let _ = f.instructions().drop();
1036 let _ = f.instructions().end();
1037 f
1038}
1039
1040/// `print_i64(n)` — write a signed decimal integer to stdout.
1041fn compile_print_i64(fd_write: u32) -> Function {
1042 // param: n=0 (i64)
1043 // locals: i=1 (i32 cursor), neg=2 (i32), tmp=3 (i64)
1044 let mut f = Function::new_with_locals_types([ValType::I32, ValType::I32, ValType::I64]);
1045
1046 // i = ITOA_END
1047 let _ = f.instructions().i32_const(SCRATCH_ITOA_END as i32);
1048 let _ = f.instructions().local_set(1);
1049 // neg = 0; tmp = n
1050 let _ = f.instructions().i32_const(0);
1051 let _ = f.instructions().local_set(2);
1052 let _ = f.instructions().local_get(0);
1053 let _ = f.instructions().local_set(3);
1054
1055 // if n < 0: neg = 1; tmp = -n
1056 let _ = f.instructions().local_get(0);
1057 let _ = f.instructions().i64_const(0);
1058 let _ = f.instructions().i64_lt_s();
1059 let _ = f.instructions().if_(BlockType::Empty);
1060 let _ = f.instructions().i32_const(1);
1061 let _ = f.instructions().local_set(2);
1062 let _ = f.instructions().i64_const(0);
1063 let _ = f.instructions().local_get(0);
1064 let _ = f.instructions().i64_sub();
1065 let _ = f.instructions().local_set(3);
1066 let _ = f.instructions().end();
1067
1068 // do { write digit; tmp /= 10 } while tmp != 0
1069 let _ = f.instructions().loop_(BlockType::Empty);
1070 // i -= 1
1071 let _ = f.instructions().local_get(1);
1072 let _ = f.instructions().i32_const(1);
1073 let _ = f.instructions().i32_sub();
1074 let _ = f.instructions().local_set(1);
1075 // *i = '0' + (tmp % 10)
1076 let _ = f.instructions().local_get(1);
1077 let _ = f.instructions().local_get(3);
1078 let _ = f.instructions().i64_const(10);
1079 let _ = f.instructions().i64_rem_u();
1080 let _ = f.instructions().i32_wrap_i64();
1081 let _ = f.instructions().i32_const(b'0' as i32);
1082 let _ = f.instructions().i32_add();
1083 let _ = f.instructions().i32_store8(mem_arg(0, 0));
1084 // tmp /= 10
1085 let _ = f.instructions().local_get(3);
1086 let _ = f.instructions().i64_const(10);
1087 let _ = f.instructions().i64_div_u();
1088 let _ = f.instructions().local_set(3);
1089 // continue while tmp != 0
1090 let _ = f.instructions().local_get(3);
1091 let _ = f.instructions().i64_const(0);
1092 let _ = f.instructions().i64_ne();
1093 let _ = f.instructions().br_if(0);
1094 let _ = f.instructions().end(); // loop
1095
1096 // if neg: prepend '-'
1097 let _ = f.instructions().local_get(2);
1098 let _ = f.instructions().if_(BlockType::Empty);
1099 let _ = f.instructions().local_get(1);
1100 let _ = f.instructions().i32_const(1);
1101 let _ = f.instructions().i32_sub();
1102 let _ = f.instructions().local_tee(1);
1103 let _ = f.instructions().i32_const(b'-' as i32);
1104 let _ = f.instructions().i32_store8(mem_arg(0, 0));
1105 let _ = f.instructions().end();
1106
1107 // iov.buf = i; iov.len = ITOA_END - i
1108 let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
1109 let _ = f.instructions().local_get(1);
1110 let _ = f.instructions().i32_store(mem_arg(0, 2));
1111 let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
1112 let _ = f.instructions().i32_const(SCRATCH_ITOA_END as i32);
1113 let _ = f.instructions().local_get(1);
1114 let _ = f.instructions().i32_sub();
1115 let _ = f.instructions().i32_store(mem_arg(4, 2));
1116 // fd_write(1, ...)
1117 let _ = f.instructions().i32_const(1);
1118 let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
1119 let _ = f.instructions().i32_const(1);
1120 let _ = f.instructions().i32_const(SCRATCH_NWRITTEN as i32);
1121 let _ = f.instructions().call(fd_write);
1122 let _ = f.instructions().drop();
1123 let _ = f.instructions().end();
1124 f
1125}
1126
1127/// `_start` — call `main`, print the result, print a newline.
1128fn compile_start(entry: &WasiEntry) -> Function {
1129 let mut f = Function::new([]);
1130 let _ = f.instructions().call(entry.main_index);
1131 match entry.main_return {
1132 CompleteType::String => {
1133 let _ = f.instructions().call(entry.print_string);
1134 }
1135 CompleteType::Int => {
1136 let _ = f.instructions().call(entry.print_i64);
1137 }
1138 CompleteType::Bool => {
1139 // Print 0 / 1 as decimal.
1140 let _ = f.instructions().i64_extend_i32_u();
1141 let _ = f.instructions().call(entry.print_i64);
1142 }
1143 CompleteType::Float => {
1144 // Drop the float; print a placeholder.
1145 let _ = f.instructions().drop();
1146 // Fall through to newline only.
1147 }
1148 _ => {
1149 // Unsupported return: drop if needed is already on stack as value.
1150 let _ = f.instructions().drop();
1151 }
1152 }
1153 // print newline
1154 let _ = f.instructions().i32_const(entry.newline_offset as i32);
1155 let _ = f.instructions().call(entry.print_string);
1156 let _ = f.instructions().end();
1157 f
1158}
1159
1160/// `alloc(size) -> ptr` — bump-allocate `size` bytes, 4-byte aligned.
1161fn compile_alloc() -> Function {
1162 // locals: $ptr
1163 let mut f = Function::new_with_locals_types([ValType::I32]);
1164 // ptr = heap
1165 let _ = f.instructions().global_get(HEAP_GLOBAL);
1166 let _ = f.instructions().local_set(1);
1167 // heap = (heap + size + 3) & !3
1168 let _ = f.instructions().global_get(HEAP_GLOBAL);
1169 let _ = f.instructions().local_get(0);
1170 let _ = f.instructions().i32_add();
1171 let _ = f.instructions().i32_const(3);
1172 let _ = f.instructions().i32_add();
1173 let _ = f.instructions().i32_const(-4);
1174 let _ = f.instructions().i32_and();
1175 let _ = f.instructions().global_set(HEAP_GLOBAL);
1176 // return ptr
1177 let _ = f.instructions().local_get(1);
1178 let _ = f.instructions().end();
1179 f
1180}
1181
1182/// `string_concat(a, b) -> ptr`
1183fn compile_string_concat(alloc_index: u32) -> Function {
1184 // params: a=0, b=1
1185 // locals: la=2, lb=3, result=4, i=5
1186 let mut f = Function::new_with_locals_types([
1187 ValType::I32,
1188 ValType::I32,
1189 ValType::I32,
1190 ValType::I32,
1191 ]);
1192
1193 // la = *a
1194 let _ = f.instructions().local_get(0);
1195 let _ = f.instructions().i32_load(mem_arg(0, 2));
1196 let _ = f.instructions().local_set(2);
1197 // lb = *b
1198 let _ = f.instructions().local_get(1);
1199 let _ = f.instructions().i32_load(mem_arg(0, 2));
1200 let _ = f.instructions().local_set(3);
1201 // result = alloc(4 + la + lb)
1202 let _ = f.instructions().local_get(2);
1203 let _ = f.instructions().local_get(3);
1204 let _ = f.instructions().i32_add();
1205 let _ = f.instructions().i32_const(4);
1206 let _ = f.instructions().i32_add();
1207 let _ = f.instructions().call(alloc_index);
1208 let _ = f.instructions().local_set(4);
1209 // *result = la + lb
1210 let _ = f.instructions().local_get(4);
1211 let _ = f.instructions().local_get(2);
1212 let _ = f.instructions().local_get(3);
1213 let _ = f.instructions().i32_add();
1214 let _ = f.instructions().i32_store(mem_arg(0, 2));
1215
1216 // copy a → result+4
1217 emit_memcpy(&mut f, /*dest_base*/ 4, /*src_param*/ 0, /*len_local*/ 2, /*i*/ 5);
1218 // copy b → result+4+la
1219 // i = 0
1220 let _ = f.instructions().i32_const(0);
1221 let _ = f.instructions().local_set(5);
1222 // loop
1223 let _ = f.instructions().loop_(BlockType::Empty);
1224 // if i >= lb: break via br to outer... use if
1225 let _ = f.instructions().local_get(5);
1226 let _ = f.instructions().local_get(3);
1227 let _ = f.instructions().i32_lt_u();
1228 let _ = f.instructions().if_(BlockType::Empty);
1229 // dest = result + 4 + la + i
1230 let _ = f.instructions().local_get(4);
1231 let _ = f.instructions().local_get(2);
1232 let _ = f.instructions().i32_add();
1233 let _ = f.instructions().local_get(5);
1234 let _ = f.instructions().i32_add();
1235 // src byte = *(b + 4 + i)
1236 let _ = f.instructions().local_get(1);
1237 let _ = f.instructions().local_get(5);
1238 let _ = f.instructions().i32_add();
1239 let _ = f.instructions().i32_load8_u(mem_arg(4, 0));
1240 let _ = f.instructions().i32_store8(mem_arg(4, 0));
1241 // i += 1
1242 let _ = f.instructions().local_get(5);
1243 let _ = f.instructions().i32_const(1);
1244 let _ = f.instructions().i32_add();
1245 let _ = f.instructions().local_set(5);
1246 let _ = f.instructions().br(1); // continue loop
1247 let _ = f.instructions().end(); // if
1248 let _ = f.instructions().end(); // loop
1249
1250 let _ = f.instructions().local_get(4);
1251 let _ = f.instructions().end();
1252 f
1253}
1254
1255/// Copy `len` bytes from `src_param+4` to `result_local+4`.
1256/// Uses locals: i for index.
1257fn emit_memcpy(f: &mut Function, result_local: u32, src_param: u32, len_local: u32, i_local: u32) {
1258 let _ = f.instructions().i32_const(0);
1259 let _ = f.instructions().local_set(i_local);
1260 let _ = f.instructions().loop_(BlockType::Empty);
1261 let _ = f.instructions().local_get(i_local);
1262 let _ = f.instructions().local_get(len_local);
1263 let _ = f.instructions().i32_lt_u();
1264 let _ = f.instructions().if_(BlockType::Empty);
1265 // dest address = result + i (store8 uses offset 4)
1266 let _ = f.instructions().local_get(result_local);
1267 let _ = f.instructions().local_get(i_local);
1268 let _ = f.instructions().i32_add();
1269 // src byte
1270 let _ = f.instructions().local_get(src_param);
1271 let _ = f.instructions().local_get(i_local);
1272 let _ = f.instructions().i32_add();
1273 let _ = f.instructions().i32_load8_u(mem_arg(4, 0));
1274 let _ = f.instructions().i32_store8(mem_arg(4, 0));
1275 // i += 1
1276 let _ = f.instructions().local_get(i_local);
1277 let _ = f.instructions().i32_const(1);
1278 let _ = f.instructions().i32_add();
1279 let _ = f.instructions().local_set(i_local);
1280 let _ = f.instructions().br(1);
1281 let _ = f.instructions().end(); // if
1282 let _ = f.instructions().end(); // loop
1283}
1284
1285/// `string_eq(a, b) -> i32` (1 if equal, 0 otherwise).
1286fn compile_string_eq() -> Function {
1287 // params: a=0, b=1
1288 // locals: la=2, i=3
1289 let mut f = Function::new_with_locals_types([ValType::I32, ValType::I32]);
1290
1291 // block $ret (result i32)
1292 let _ = f.instructions().block(BlockType::Result(ValType::I32));
1293
1294 // if a == b: return 1
1295 let _ = f.instructions().local_get(0);
1296 let _ = f.instructions().local_get(1);
1297 let _ = f.instructions().i32_eq();
1298 let _ = f.instructions().if_(BlockType::Empty);
1299 let _ = f.instructions().i32_const(1);
1300 let _ = f.instructions().br(1); // br $ret
1301 let _ = f.instructions().end();
1302
1303 // la = *a
1304 let _ = f.instructions().local_get(0);
1305 let _ = f.instructions().i32_load(mem_arg(0, 2));
1306 let _ = f.instructions().local_tee(2);
1307 // if la != *b: return 0
1308 let _ = f.instructions().local_get(1);
1309 let _ = f.instructions().i32_load(mem_arg(0, 2));
1310 let _ = f.instructions().i32_ne();
1311 let _ = f.instructions().if_(BlockType::Empty);
1312 let _ = f.instructions().i32_const(0);
1313 let _ = f.instructions().br(1);
1314 let _ = f.instructions().end();
1315
1316 // i = 0
1317 let _ = f.instructions().i32_const(0);
1318 let _ = f.instructions().local_set(3);
1319 let _ = f.instructions().loop_(BlockType::Empty);
1320 // if i >= la: return 1
1321 let _ = f.instructions().local_get(3);
1322 let _ = f.instructions().local_get(2);
1323 let _ = f.instructions().i32_ge_u();
1324 let _ = f.instructions().if_(BlockType::Empty);
1325 let _ = f.instructions().i32_const(1);
1326 let _ = f.instructions().br(2); // br $ret
1327 let _ = f.instructions().end();
1328 // if bytes differ: return 0
1329 let _ = f.instructions().local_get(0);
1330 let _ = f.instructions().local_get(3);
1331 let _ = f.instructions().i32_add();
1332 let _ = f.instructions().i32_load8_u(mem_arg(4, 0));
1333 let _ = f.instructions().local_get(1);
1334 let _ = f.instructions().local_get(3);
1335 let _ = f.instructions().i32_add();
1336 let _ = f.instructions().i32_load8_u(mem_arg(4, 0));
1337 let _ = f.instructions().i32_ne();
1338 let _ = f.instructions().if_(BlockType::Empty);
1339 let _ = f.instructions().i32_const(0);
1340 let _ = f.instructions().br(2); // br $ret
1341 let _ = f.instructions().end();
1342 // i += 1; continue
1343 let _ = f.instructions().local_get(3);
1344 let _ = f.instructions().i32_const(1);
1345 let _ = f.instructions().i32_add();
1346 let _ = f.instructions().local_set(3);
1347 let _ = f.instructions().br(0);
1348 let _ = f.instructions().end(); // loop
1349
1350 let _ = f.instructions().unreachable();
1351 let _ = f.instructions().end(); // block $ret
1352 let _ = f.instructions().end();
1353 f
1354}
1355
1356// ---------------------------------------------------------------------------
1357// Locals
1358// ---------------------------------------------------------------------------
1359
1360struct LocalAllocator {
1361 /// Parameter + local name → local index.
1362 names: HashMap<EcoString, u32>,
1363 /// Types of non-parameter locals, in declaration order.
1364 extra_locals: Vec<ValType>,
1365 next_index: u32,
1366 /// Scratch i32 locals reserved for expression lowering (allocated up front
1367 /// so `Function::new_with_locals_types` sees them before emit).
1368 tmp_base: u32,
1369 tmp_count: u32,
1370 tmp_next: u32,
1371}
1372
1373impl LocalAllocator {
1374 const TMP_SLOTS: u32 = 64;
1375
1376 fn new(function: &ast::Function<CompleteType>) -> Self {
1377 let mut names = HashMap::new();
1378 let mut next_index = 0;
1379
1380 for parameter in &function.parameters {
1381 if let Some(name) = ¶meter.name {
1382 _ = names.insert(name.clone(), next_index);
1383 }
1384 next_index += 1;
1385 }
1386
1387 Self {
1388 names,
1389 extra_locals: Vec::new(),
1390 next_index,
1391 tmp_base: 0,
1392 tmp_count: 0,
1393 tmp_next: 0,
1394 }
1395 }
1396
1397 /// Reserve a pool of i32 scratch locals. Call after named locals are known.
1398 fn reserve_tmps(&mut self) {
1399 self.tmp_base = self.next_index;
1400 self.tmp_count = Self::TMP_SLOTS;
1401 self.tmp_next = 0;
1402 for _ in 0..Self::TMP_SLOTS {
1403 self.extra_locals.push(ValType::I32);
1404 self.next_index += 1;
1405 }
1406 }
1407
1408 fn collect_from_expression(&mut self, expression: &Expression<CompleteType>) {
1409 match expression {
1410 Expression::Block(expressions) => {
1411 for expression in expressions {
1412 self.collect_from_expression(expression);
1413 }
1414 }
1415 Expression::Set { name, value } => {
1416 self.ensure_local(&name.name, &name.type_);
1417 self.collect_from_expression(value);
1418 }
1419 Expression::Equals { lhs, rhs }
1420 | Expression::NotEquals { lhs, rhs }
1421 | Expression::IntGt { lhs, rhs }
1422 | Expression::IntGtEq { lhs, rhs }
1423 | Expression::IntLt { lhs, rhs }
1424 | Expression::IntLtEq { lhs, rhs }
1425 | Expression::IntAdd { lhs, rhs }
1426 | Expression::IntSub { lhs, rhs }
1427 | Expression::IntMul { lhs, rhs }
1428 | Expression::IntDiv { lhs, rhs }
1429 | Expression::IntRem { lhs, rhs }
1430 | Expression::FloatGt { lhs, rhs }
1431 | Expression::FloatGtEq { lhs, rhs }
1432 | Expression::FloatLt { lhs, rhs }
1433 | Expression::FloatLtEq { lhs, rhs }
1434 | Expression::FloatAdd { lhs, rhs }
1435 | Expression::FloatSub { lhs, rhs }
1436 | Expression::FloatMul { lhs, rhs }
1437 | Expression::FloatDiv { lhs, rhs }
1438 | Expression::StringConcat { lhs, rhs } => {
1439 self.collect_from_expression(lhs);
1440 self.collect_from_expression(rhs);
1441 }
1442 Expression::If { cond, then, else_ } => {
1443 self.collect_from_expression(cond);
1444 self.collect_from_expression(then);
1445 self.collect_from_expression(else_);
1446 }
1447 Expression::Call { target, args, .. } => {
1448 self.collect_from_expression(target);
1449 for arg in args {
1450 self.collect_from_expression(arg);
1451 }
1452 }
1453 Expression::List { items, tail, .. } => {
1454 for item in items {
1455 self.collect_from_expression(item);
1456 }
1457 if let Some(tail) = tail {
1458 self.collect_from_expression(tail);
1459 }
1460 }
1461 Expression::Tuple { items, .. } | Expression::Struct { items, .. } => {
1462 for item in items {
1463 self.collect_from_expression(item);
1464 }
1465 }
1466 Expression::TupleAccess { value, .. }
1467 | Expression::StructTag { value }
1468 | Expression::StructAccess { value, .. } => {
1469 self.collect_from_expression(value);
1470 }
1471 Expression::FunctionRef { .. }
1472 | Expression::Var(_)
1473 | Expression::Int { .. }
1474 | Expression::Float { .. }
1475 | Expression::Bool { .. }
1476 | Expression::String { .. }
1477 | Expression::Panic { .. } => {}
1478 }
1479 }
1480
1481 fn ensure_local(&mut self, name: &EcoString, type_: &CompleteType) {
1482 if self.names.contains_key(name) {
1483 return;
1484 }
1485 _ = self.names.insert(name.clone(), self.next_index);
1486 self.extra_locals.push(val_type(type_));
1487 self.next_index += 1;
1488 }
1489
1490 fn index(&self, name: &EcoString) -> u32 {
1491 *self
1492 .names
1493 .get(name)
1494 .unwrap_or_else(|| panic!("unknown local `{name}`"))
1495 }
1496
1497 fn alloc_tmp(&mut self, _type_: ValType) -> u32 {
1498 if self.tmp_count == 0 {
1499 panic!("temporary locals were not reserved before emit");
1500 }
1501 if self.tmp_next >= self.tmp_count {
1502 // Wrap around — nested expressions that hold multiple live tmps
1503 // beyond TMP_SLOTS will clobber; raise the pool if that happens.
1504 self.tmp_next = 0;
1505 }
1506 let index = self.tmp_base + self.tmp_next;
1507 self.tmp_next += 1;
1508 index
1509 }
1510}
1511
1512// ---------------------------------------------------------------------------
1513// Helpers
1514// ---------------------------------------------------------------------------
1515
1516fn val_type(type_: &CompleteType) -> ValType {
1517 match type_ {
1518 CompleteType::Int => ValType::I64,
1519 CompleteType::Float => ValType::F64,
1520 CompleteType::Bool
1521 | CompleteType::String
1522 | CompleteType::Tuple { .. }
1523 | CompleteType::Struct { .. }
1524 | CompleteType::List(_)
1525 | CompleteType::Func { .. } => ValType::I32,
1526 }
1527}
1528
1529fn block_type(type_: &CompleteType) -> BlockType {
1530 BlockType::Result(val_type(type_))
1531}
1532
1533fn bigint_to_i64(value: &BigInt) -> i64 {
1534 value
1535 .to_i64()
1536 .unwrap_or_else(|| panic!("integer literal does not fit in i64: {value}"))
1537}
1538
1539fn push_dummy_value(body: &mut Function, type_: &CompleteType) {
1540 match type_ {
1541 CompleteType::Int => {
1542 let _ = body.instructions().i64_const(0);
1543 }
1544 CompleteType::Bool
1545 | CompleteType::String
1546 | CompleteType::Tuple { .. }
1547 | CompleteType::Struct { .. }
1548 | CompleteType::List(_)
1549 | CompleteType::Func { .. } => {
1550 let _ = body.instructions().i32_const(0);
1551 }
1552 CompleteType::Float => {
1553 let _ = body.instructions().f64_const(Ieee64::from(0.0));
1554 }
1555 }
1556}
1557
1558fn align4(value: u32) -> u32 {
1559 (value + 3) & !3
1560}
1561
1562fn is_main_function(name: &str) -> bool {
1563 name == "main" || name.ends_with("__main")
1564}
1565
1566fn module_uses_strings(module: &ast::Module<CompleteType>) -> bool {
1567 module.functions.iter().any(|function| {
1568 type_is_stringy(&function.return_type)
1569 || function
1570 .parameters
1571 .iter()
1572 .any(|parameter| type_is_stringy(¶meter.type_))
1573 || function
1574 .body
1575 .as_ref()
1576 .is_some_and(expression_uses_strings)
1577 })
1578}
1579
1580fn module_needs_heap(module: &ast::Module<CompleteType>) -> bool {
1581 module.functions.iter().any(|function| {
1582 type_needs_heap(&function.return_type)
1583 || function
1584 .parameters
1585 .iter()
1586 .any(|parameter| type_needs_heap(¶meter.type_))
1587 || function.body.as_ref().is_some_and(expression_needs_heap)
1588 })
1589}
1590
1591fn expression_needs_heap(expression: &Expression<CompleteType>) -> bool {
1592 match expression {
1593 Expression::String { .. }
1594 | Expression::StringConcat { .. }
1595 | Expression::List { .. }
1596 | Expression::Tuple { .. }
1597 | Expression::Struct { .. } => true,
1598 Expression::Block(expressions) => expressions.iter().any(expression_needs_heap),
1599 Expression::Set { value, .. }
1600 | Expression::TupleAccess { value, .. }
1601 | Expression::StructTag { value }
1602 | Expression::StructAccess { value, .. } => expression_needs_heap(value),
1603 Expression::Equals { lhs, rhs }
1604 | Expression::NotEquals { lhs, rhs }
1605 | Expression::IntGt { lhs, rhs }
1606 | Expression::IntGtEq { lhs, rhs }
1607 | Expression::IntLt { lhs, rhs }
1608 | Expression::IntLtEq { lhs, rhs }
1609 | Expression::IntAdd { lhs, rhs }
1610 | Expression::IntSub { lhs, rhs }
1611 | Expression::IntMul { lhs, rhs }
1612 | Expression::IntDiv { lhs, rhs }
1613 | Expression::IntRem { lhs, rhs }
1614 | Expression::FloatGt { lhs, rhs }
1615 | Expression::FloatGtEq { lhs, rhs }
1616 | Expression::FloatLt { lhs, rhs }
1617 | Expression::FloatLtEq { lhs, rhs }
1618 | Expression::FloatAdd { lhs, rhs }
1619 | Expression::FloatSub { lhs, rhs }
1620 | Expression::FloatMul { lhs, rhs }
1621 | Expression::FloatDiv { lhs, rhs } => {
1622 expression_needs_heap(lhs) || expression_needs_heap(rhs)
1623 }
1624 Expression::If { cond, then, else_ } => {
1625 expression_needs_heap(cond)
1626 || expression_needs_heap(then)
1627 || expression_needs_heap(else_)
1628 }
1629 Expression::Call { target, args, .. } => {
1630 expression_needs_heap(target) || args.iter().any(expression_needs_heap)
1631 }
1632 Expression::FunctionRef { .. }
1633 | Expression::Var(_)
1634 | Expression::Int { .. }
1635 | Expression::Float { .. }
1636 | Expression::Bool { .. }
1637 | Expression::Panic { .. } => false,
1638 }
1639}
1640
1641fn type_is_stringy(type_: &CompleteType) -> bool {
1642 match type_ {
1643 CompleteType::String => true,
1644 CompleteType::List(inner) => type_is_stringy(inner),
1645 CompleteType::Tuple { elements } | CompleteType::Struct { elements } => {
1646 elements.iter().any(type_is_stringy)
1647 }
1648 CompleteType::Func { arguments, returns } => {
1649 arguments.iter().any(type_is_stringy) || type_is_stringy(returns)
1650 }
1651 _ => false,
1652 }
1653}
1654
1655fn type_needs_heap(type_: &CompleteType) -> bool {
1656 match type_ {
1657 CompleteType::String
1658 | CompleteType::List(_)
1659 | CompleteType::Tuple { .. }
1660 | CompleteType::Struct { .. } => true,
1661 CompleteType::Func { arguments, returns } => {
1662 arguments.iter().any(type_needs_heap) || type_needs_heap(returns)
1663 }
1664 _ => false,
1665 }
1666}
1667
1668fn expression_uses_strings(expression: &Expression<CompleteType>) -> bool {
1669 match expression {
1670 Expression::String { .. } | Expression::StringConcat { .. } => true,
1671 Expression::Block(expressions) => expressions.iter().any(expression_uses_strings),
1672 Expression::Set { value, .. } => expression_uses_strings(value),
1673 Expression::Equals { lhs, rhs }
1674 | Expression::NotEquals { lhs, rhs }
1675 | Expression::IntGt { lhs, rhs }
1676 | Expression::IntGtEq { lhs, rhs }
1677 | Expression::IntLt { lhs, rhs }
1678 | Expression::IntLtEq { lhs, rhs }
1679 | Expression::IntAdd { lhs, rhs }
1680 | Expression::IntSub { lhs, rhs }
1681 | Expression::IntMul { lhs, rhs }
1682 | Expression::IntDiv { lhs, rhs }
1683 | Expression::IntRem { lhs, rhs }
1684 | Expression::FloatGt { lhs, rhs }
1685 | Expression::FloatGtEq { lhs, rhs }
1686 | Expression::FloatLt { lhs, rhs }
1687 | Expression::FloatLtEq { lhs, rhs }
1688 | Expression::FloatAdd { lhs, rhs }
1689 | Expression::FloatSub { lhs, rhs }
1690 | Expression::FloatMul { lhs, rhs }
1691 | Expression::FloatDiv { lhs, rhs } => {
1692 expression_uses_strings(lhs) || expression_uses_strings(rhs)
1693 }
1694 Expression::If { cond, then, else_ } => {
1695 expression_uses_strings(cond)
1696 || expression_uses_strings(then)
1697 || expression_uses_strings(else_)
1698 }
1699 Expression::Call { target, args, .. } => {
1700 expression_uses_strings(target) || args.iter().any(expression_uses_strings)
1701 }
1702 Expression::List { items, tail, type_ } => {
1703 type_is_stringy(type_)
1704 || items.iter().any(expression_uses_strings)
1705 || tail.as_ref().is_some_and(|t| expression_uses_strings(t))
1706 }
1707 Expression::Tuple { items, type_ } | Expression::Struct { items, type_, .. } => {
1708 type_is_stringy(type_) || items.iter().any(expression_uses_strings)
1709 }
1710 Expression::TupleAccess { value, type_, .. }
1711 | Expression::StructAccess { value, type_, .. } => {
1712 type_is_stringy(type_) || expression_uses_strings(value)
1713 }
1714 Expression::StructTag { value } => expression_uses_strings(value),
1715 Expression::FunctionRef { type_, .. } => type_is_stringy(type_),
1716 Expression::Var(var) => type_is_stringy(&var.type_),
1717 Expression::Panic { type_ } => type_is_stringy(type_),
1718 Expression::Int { .. }
1719 | Expression::Float { .. }
1720 | Expression::Bool { .. } => false,
1721 }
1722}
1723
1724fn collect_strings_from_expression(expression: &Expression<CompleteType>, f: &mut dyn FnMut(&str)) {
1725 match expression {
1726 Expression::String { value } => f(value),
1727 Expression::Block(expressions) => {
1728 for expression in expressions {
1729 collect_strings_from_expression(expression, f);
1730 }
1731 }
1732 Expression::Set { value, .. }
1733 | Expression::StructTag { value }
1734 | Expression::TupleAccess { value, .. }
1735 | Expression::StructAccess { value, .. } => {
1736 collect_strings_from_expression(value, f);
1737 }
1738 Expression::Equals { lhs, rhs }
1739 | Expression::NotEquals { lhs, rhs }
1740 | Expression::IntGt { lhs, rhs }
1741 | Expression::IntGtEq { lhs, rhs }
1742 | Expression::IntLt { lhs, rhs }
1743 | Expression::IntLtEq { lhs, rhs }
1744 | Expression::IntAdd { lhs, rhs }
1745 | Expression::IntSub { lhs, rhs }
1746 | Expression::IntMul { lhs, rhs }
1747 | Expression::IntDiv { lhs, rhs }
1748 | Expression::IntRem { lhs, rhs }
1749 | Expression::FloatGt { lhs, rhs }
1750 | Expression::FloatGtEq { lhs, rhs }
1751 | Expression::FloatLt { lhs, rhs }
1752 | Expression::FloatLtEq { lhs, rhs }
1753 | Expression::FloatAdd { lhs, rhs }
1754 | Expression::FloatSub { lhs, rhs }
1755 | Expression::FloatMul { lhs, rhs }
1756 | Expression::FloatDiv { lhs, rhs }
1757 | Expression::StringConcat { lhs, rhs } => {
1758 collect_strings_from_expression(lhs, f);
1759 collect_strings_from_expression(rhs, f);
1760 }
1761 Expression::If { cond, then, else_ } => {
1762 collect_strings_from_expression(cond, f);
1763 collect_strings_from_expression(then, f);
1764 collect_strings_from_expression(else_, f);
1765 }
1766 Expression::Call { target, args, .. } => {
1767 collect_strings_from_expression(target, f);
1768 for arg in args {
1769 collect_strings_from_expression(arg, f);
1770 }
1771 }
1772 Expression::List { items, tail, .. } => {
1773 for item in items {
1774 collect_strings_from_expression(item, f);
1775 }
1776 if let Some(tail) = tail {
1777 collect_strings_from_expression(tail, f);
1778 }
1779 }
1780 Expression::Tuple { items, .. } | Expression::Struct { items, .. } => {
1781 for item in items {
1782 collect_strings_from_expression(item, f);
1783 }
1784 }
1785 Expression::FunctionRef { .. }
1786 | Expression::Var(_)
1787 | Expression::Int { .. }
1788 | Expression::Float { .. }
1789 | Expression::Bool { .. }
1790 | Expression::Panic { .. } => {}
1791 }
1792}
1793
1794#[cfg(test)]
1795mod tests {
1796 use super::*;
1797 use crate::wasm::mir::ast::{Function, FunctionParameter, Module};
1798
1799 #[test]
1800 fn compiles_constant_int_main() {
1801 let module = Module {
1802 name: "project_wasm".into(),
1803 functions: vec![Function {
1804 name: "main".into(),
1805 return_type: CompleteType::Int,
1806 parameters: vec![],
1807 body: Some(Expression::Int {
1808 value: BigInt::from(0),
1809 }),
1810 external_wasm: None,
1811 }],
1812 };
1813
1814 let bytes = compile(module);
1815 assert_eq!(&bytes[..4], b"\0asm");
1816 // version 1
1817 assert_eq!(&bytes[4..8], &[1, 0, 0, 0]);
1818 }
1819
1820 #[test]
1821 fn compiles_add() {
1822 let module = Module {
1823 name: "maths".into(),
1824 functions: vec![Function {
1825 name: "add".into(),
1826 return_type: CompleteType::Int,
1827 parameters: vec![
1828 FunctionParameter {
1829 type_: CompleteType::Int,
1830 name: Some("lhs".into()),
1831 },
1832 FunctionParameter {
1833 type_: CompleteType::Int,
1834 name: Some("rhs".into()),
1835 },
1836 ],
1837 body: Some(Expression::IntAdd {
1838 lhs: Box::new(Expression::Var(ast::Var {
1839 name: "lhs".into(),
1840 type_: CompleteType::Int,
1841 })),
1842 rhs: Box::new(Expression::Var(ast::Var {
1843 name: "rhs".into(),
1844 type_: CompleteType::Int,
1845 })),
1846 }),
1847 external_wasm: None,
1848 }],
1849 };
1850
1851 let bytes = compile(module);
1852 assert_eq!(&bytes[..4], b"\0asm");
1853 }
1854
1855 #[test]
1856 fn compiles_string_literal_and_concat() {
1857 let module = Module {
1858 name: "strings".into(),
1859 functions: vec![Function {
1860 name: "greet".into(),
1861 return_type: CompleteType::String,
1862 parameters: vec![],
1863 body: Some(Expression::StringConcat {
1864 lhs: Box::new(Expression::String {
1865 value: "hello, ".into(),
1866 }),
1867 rhs: Box::new(Expression::String {
1868 value: "world!".into(),
1869 }),
1870 }),
1871 external_wasm: None,
1872 }],
1873 };
1874
1875 let bytes = compile(module);
1876 assert_eq!(&bytes[..4], b"\0asm");
1877 // Must include a memory section / export for host access.
1878 assert!(bytes.len() > 40);
1879 }
1880}