nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
22 kB
635 lines
1use std::collections::HashMap;
2
3use cranelift::{
4 codegen::{
5 Context,
6 ir::{BlockArg, immediates::Offset32},
7 },
8 prelude::*,
9};
10use cranelift_module::{Linkage, Module, default_libcall_names};
11use cranelift_object::{ObjectBuilder, ObjectModule};
12use ecow::{EcoString, eco_format};
13use itertools::Itertools as _;
14
15use crate::cranelift::mir::ast;
16
17pub mod mir;
18
19struct CodeGen<M: Module> {
20 module: M,
21 context: Context,
22 function_context: FunctionBuilderContext,
23}
24
25pub fn compile(module: ast::Module<ast::CompleteType>) -> Vec<u8> {
26 let mut flag_builder = settings::builder();
27
28 flag_builder
29 .set("is_pic", "true")
30 .expect("unable to set `is_pic` to false");
31
32 let isa = cranelift_native::builder()
33 .unwrap_or_else(|reason| panic!("host machine not support: {reason}"))
34 .finish(settings::Flags::new(flag_builder))
35 .expect("unable to build isa target");
36
37 let mut cranelift = {
38 let module = ObjectModule::new(
39 ObjectBuilder::new(isa, module.name.to_string(), default_libcall_names())
40 .expect("unable to build object builder"),
41 );
42
43 CodeGen {
44 function_context: FunctionBuilderContext::new(),
45 context: module.make_context(),
46 module,
47 }
48 };
49
50 for function in module.functions {
51 FunctionTranslator::new(&mut cranelift).translate(module.name.clone(), function);
52 }
53
54 let product = cranelift.module.finish();
55
56 product.emit().expect("unable to emit finished product")
57}
58
59struct FunctionTranslator<'m, M: Module> {
60 cg: &'m mut CodeGen<M>,
61}
62
63fn mangle_type_name(type_: &ast::CompleteType) -> EcoString {
64 match type_ {
65 ast::CompleteType::Int => "I".into(),
66 ast::CompleteType::Float => "F".into(),
67 ast::CompleteType::Bool => "B".into(),
68 ast::CompleteType::String => "S".into(),
69 ast::CompleteType::Func { arguments, returns } => {
70 let arguments = arguments
71 .iter()
72 .map(mangle_type_name)
73 .map(|s| eco_format!("{}{}", s.len(), s))
74 .join("");
75
76 let returns = mangle_type_name(returns);
77
78 eco_format!("F{}f{}R{}", arguments.len(), arguments, returns)
79 }
80 ast::CompleteType::Tuple { elements } => {
81 let elements = elements
82 .iter()
83 .map(mangle_type_name)
84 .map(|s| eco_format!("{}{}", s.len(), s))
85 .join("");
86
87 eco_format!("T{}t{}", elements.len(), elements)
88 }
89 ast::CompleteType::Struct { elements } => {
90 let elements = elements
91 .iter()
92 .map(mangle_type_name)
93 .map(|s| eco_format!("{}{}", s.len(), s))
94 .join("");
95
96 eco_format!("C{}c{}", elements.len(), elements)
97 }
98 ast::CompleteType::List(element_type) => {
99 let element = mangle_type_name(element_type);
100
101 eco_format!("L{}{}", element.len(), element)
102 }
103 }
104}
105
106fn mangled_function_name(
107 module: EcoString,
108 name: EcoString,
109 arguments: &[ast::CompleteType],
110 returns: &ast::CompleteType,
111) -> EcoString {
112 let arguments = arguments
113 .iter()
114 .map(mangle_type_name)
115 .map(|s| eco_format!("{}{}", s.len(), s))
116 .join("");
117 let returns = mangle_type_name(returns);
118
119 eco_format!(
120 "M{}{}_{}{}_A{}a{}_R{}",
121 module.len(),
122 module.replace("/", "_"),
123 name.len(),
124 name,
125 arguments.len(),
126 arguments,
127 returns,
128 )
129}
130
131impl<'m, M: Module> FunctionTranslator<'m, M> {
132 fn new(cg: &'m mut CodeGen<M>) -> Self {
133 Self { cg }
134 }
135
136 fn translate(self, module: EcoString, function: ast::Function<ast::CompleteType>) {
137 let arguments: Vec<_> = function
138 .parameters
139 .iter()
140 .map(|parameter| parameter.type_.clone())
141 .collect();
142
143 let name = mangled_function_name(
144 module,
145 function.name.clone(),
146 &arguments,
147 &function.return_type,
148 );
149
150 self.cg.context.func.signature = self.signature_from_function(&function);
151
152 let mut builder =
153 FunctionBuilder::new(&mut self.cg.context.func, &mut self.cg.function_context);
154
155 let entry = builder.create_block();
156 builder.append_block_params_for_function_params(entry);
157 builder.switch_to_block(entry);
158 builder.seal_block(entry);
159
160 let value = {
161 let mut translator = ExpressionTranslator::new(&mut self.cg.module, &mut builder);
162
163 for (index, parameter) in function.parameters.iter().enumerate() {
164 if let Some(name) = ¶meter.name {
165 let var_type = translate_type(¶meter.type_);
166 let var = translator.builder.declare_var(var_type);
167 _ = translator.vars.insert(name.clone(), var);
168
169 let val = translator.builder.block_params(entry)[index];
170 translator.builder.def_var(var, val);
171 }
172 }
173
174 translator.translate(function.body)
175 };
176
177 _ = builder.ins().return_(&[value]);
178
179 builder.finalize();
180
181 let id = self
182 .cg
183 .module
184 .declare_function(&name, Linkage::Export, &self.cg.context.func.signature)
185 .expect("unable to declare function");
186
187 self.cg
188 .module
189 .define_function(id, &mut self.cg.context)
190 .expect("unable to define function");
191
192 self.cg.module.clear_context(&mut self.cg.context);
193 }
194
195 fn signature_from_function(&self, function: &ast::Function<ast::CompleteType>) -> Signature {
196 let mut sig = self.cg.module.make_signature();
197
198 for parameter in &function.parameters {
199 sig.params
200 .push(AbiParam::new(translate_type(¶meter.type_)));
201 }
202
203 sig.returns
204 .push(AbiParam::new(translate_type(&function.return_type)));
205
206 return sig;
207 }
208}
209
210fn translate_type(type_: &ast::CompleteType) -> Type {
211 match type_ {
212 ast::CompleteType::Int => types::I64,
213 ast::CompleteType::Float => types::F64,
214 ast::CompleteType::Bool => types::I64, // wasteful but whatever
215 ast::CompleteType::String => types::I64,
216 ast::CompleteType::Func {
217 arguments: _,
218 returns: _,
219 } => types::I64,
220 ast::CompleteType::Tuple { elements: _ } => types::I64,
221 ast::CompleteType::Struct { elements: _ } => types::I64,
222 ast::CompleteType::List(_complete_type) => types::I64,
223 }
224}
225
226struct ExpressionTranslator<'m, 'b, M: Module> {
227 module: &'m mut M,
228 builder: &'m mut FunctionBuilder<'b>,
229 vars: HashMap<EcoString, Variable>,
230}
231
232impl<'m, 'b, M: Module> ExpressionTranslator<'m, 'b, M> {
233 fn new(module: &'m mut M, builder: &'m mut FunctionBuilder<'b>) -> Self {
234 Self {
235 module,
236 builder,
237 vars: Default::default(),
238 }
239 }
240
241 fn translate(&mut self, expression: ast::Expression<ast::CompleteType>) -> Value {
242 _ = self.module;
243
244 match expression {
245 ast::Expression::Block(expressions) => expressions
246 .into_iter()
247 .map(|expression| self.translate(expression))
248 .last()
249 .expect("block should be non-empty"),
250 ast::Expression::FunctionRef {
251 module,
252 name,
253 arity: _,
254 type_,
255 } => {
256 let ast::CompleteType::Func { arguments, returns } = type_ else {
257 unreachable!("function ref should have func type")
258 };
259
260 let name = mangled_function_name(module, name, &arguments, &returns);
261 let sig = {
262 let mut sig = self.module.make_signature();
263 for argument in arguments {
264 sig.params.push(AbiParam::new(translate_type(&argument)));
265 }
266 sig.returns.push(AbiParam::new(translate_type(&returns)));
267 sig
268 };
269
270 let id = self
271 .module
272 .declare_function(&name, Linkage::Import, &sig)
273 .expect("unable to declare function for import");
274
275 let func = self.module.declare_func_in_func(id, self.builder.func);
276
277 self.builder.ins().func_addr(types::I64, func)
278 }
279 ast::Expression::Var(var) => {
280 let var = self
281 .vars
282 .get(&var.name)
283 .cloned()
284 .expect("variable to be defined");
285
286 self.builder.use_var(var)
287 }
288 ast::Expression::Int { value } => {
289 let value = i64::try_from(value).expect("integer value too large");
290
291 self.builder.ins().iconst(types::I64, value)
292 }
293 ast::Expression::Float { value } => {
294 let value: f64 = value.parse().expect("invalid float value");
295
296 self.builder.ins().f64const(value)
297 }
298 ast::Expression::Bool { value } => match value {
299 true => self.builder.ins().iconst(types::I64, 1),
300 false => self.builder.ins().iconst(types::I64, 0),
301 },
302 ast::Expression::String { value: _ } => todo!(),
303 ast::Expression::Equals { lhs, rhs } => match lhs.type_() {
304 ast::CompleteType::Int => {
305 let lhs = self.translate(*lhs);
306 let rhs = self.translate(*rhs);
307
308 self.builder.ins().icmp(IntCC::Equal, lhs, rhs)
309 }
310 ast::CompleteType::Float => todo!(),
311 ast::CompleteType::Bool => todo!(),
312 ast::CompleteType::String => todo!(),
313 ast::CompleteType::Func {
314 arguments: _,
315 returns: _,
316 } => todo!(),
317 ast::CompleteType::Tuple { elements: _ } => todo!(),
318 ast::CompleteType::Struct { elements: _ } => todo!(),
319 ast::CompleteType::List(_complete_type) => todo!(),
320 },
321 ast::Expression::NotEquals { lhs: _, rhs: _ } => todo!(),
322 ast::Expression::IntGt { lhs, rhs } => {
323 let lhs = self.translate(*lhs);
324 let rhs = self.translate(*rhs);
325
326 self.builder.ins().icmp(IntCC::SignedGreaterThan, lhs, rhs)
327 }
328 ast::Expression::IntGtEq { lhs, rhs } => {
329 let lhs = self.translate(*lhs);
330 let rhs = self.translate(*rhs);
331
332 self.builder
333 .ins()
334 .icmp(IntCC::SignedGreaterThanOrEqual, lhs, rhs)
335 }
336 ast::Expression::IntLt { lhs, rhs } => {
337 let lhs = self.translate(*lhs);
338 let rhs = self.translate(*rhs);
339
340 self.builder.ins().icmp(IntCC::SignedLessThan, lhs, rhs)
341 }
342 ast::Expression::IntLtEq { lhs, rhs } => {
343 let lhs = self.translate(*lhs);
344 let rhs = self.translate(*rhs);
345
346 self.builder
347 .ins()
348 .icmp(IntCC::SignedLessThanOrEqual, lhs, rhs)
349 }
350 ast::Expression::IntAdd { lhs, rhs } => {
351 let lhs = self.translate(*lhs);
352 let rhs = self.translate(*rhs);
353
354 self.builder.ins().iadd(lhs, rhs)
355 }
356 ast::Expression::IntSub { lhs, rhs } => {
357 let lhs = self.translate(*lhs);
358 let rhs = self.translate(*rhs);
359
360 self.builder.ins().isub(lhs, rhs)
361 }
362 ast::Expression::IntMul { lhs, rhs } => {
363 let lhs = self.translate(*lhs);
364 let rhs = self.translate(*rhs);
365
366 self.builder.ins().imul(lhs, rhs)
367 }
368 ast::Expression::IntDiv { lhs, rhs } => {
369 let lhs = self.translate(*lhs);
370 let rhs = self.translate(*rhs);
371
372 self.builder.ins().sdiv(lhs, rhs)
373 }
374 ast::Expression::IntRem { lhs, rhs } => {
375 let lhs = self.translate(*lhs);
376 let rhs = self.translate(*rhs);
377
378 self.builder.ins().srem(lhs, rhs)
379 }
380 ast::Expression::FloatGt { lhs, rhs } => {
381 let lhs = self.translate(*lhs);
382 let rhs = self.translate(*rhs);
383
384 self.builder.ins().fcmp(FloatCC::GreaterThan, lhs, rhs)
385 }
386 ast::Expression::FloatGtEq { lhs, rhs } => {
387 let lhs = self.translate(*lhs);
388 let rhs = self.translate(*rhs);
389
390 self.builder
391 .ins()
392 .fcmp(FloatCC::GreaterThanOrEqual, lhs, rhs)
393 }
394 ast::Expression::FloatLt { lhs, rhs } => {
395 let lhs = self.translate(*lhs);
396 let rhs = self.translate(*rhs);
397
398 self.builder.ins().fcmp(FloatCC::LessThan, lhs, rhs)
399 }
400 ast::Expression::FloatLtEq { lhs, rhs } => {
401 let lhs = self.translate(*lhs);
402 let rhs = self.translate(*rhs);
403
404 self.builder.ins().fcmp(FloatCC::LessThanOrEqual, lhs, rhs)
405 }
406 ast::Expression::FloatAdd { lhs, rhs } => {
407 let lhs = self.translate(*lhs);
408 let rhs = self.translate(*rhs);
409
410 self.builder.ins().fadd(lhs, rhs)
411 }
412 ast::Expression::FloatSub { lhs, rhs } => {
413 let lhs = self.translate(*lhs);
414 let rhs = self.translate(*rhs);
415
416 self.builder.ins().fsub(lhs, rhs)
417 }
418 ast::Expression::FloatMul { lhs, rhs } => {
419 let lhs = self.translate(*lhs);
420 let rhs = self.translate(*rhs);
421
422 self.builder.ins().fmul(lhs, rhs)
423 }
424 ast::Expression::FloatDiv { lhs, rhs } => {
425 let lhs = self.translate(*lhs);
426 let rhs = self.translate(*rhs);
427
428 self.builder.ins().fdiv(lhs, rhs)
429 }
430 ast::Expression::StringConcat { lhs: _, rhs: _ } => todo!(),
431 ast::Expression::List {
432 items: _,
433 tail: _,
434 type_: _,
435 } => todo!(),
436 ast::Expression::Tuple { items, type_: _ } => {
437 let mut sig = self.module.make_signature();
438 sig.params.push(AbiParam::new(types::I64));
439 sig.returns.push(AbiParam::new(types::I64));
440
441 let id = self
442 .module
443 .declare_function("malloc", Linkage::Import, &sig)
444 .expect("failed to declare malloc");
445
446 let malloc = self.module.declare_func_in_func(id, &mut self.builder.func);
447
448 let size_arg = self
449 .builder
450 .ins()
451 .iconst(types::I64, (items.len() as i64) * 8);
452
453 let call = self.builder.ins().call(malloc, &[size_arg]);
454 let ptr = self.builder.inst_results(call)[0];
455
456 for (index, item) in items.into_iter().enumerate() {
457 let index = index as i32;
458
459 let value = self.translate(item);
460
461 _ = self.builder.ins().store(
462 MemFlags::new(),
463 value,
464 ptr,
465 Offset32::new(index * 8),
466 );
467 }
468
469 ptr
470 }
471 ast::Expression::TupleAccess {
472 value,
473 index,
474 type_,
475 } => {
476 let ptr = self.translate(*value);
477
478 self.builder.ins().load(
479 translate_type(&type_),
480 MemFlags::new(),
481 ptr,
482 Offset32::new(index as i32 * 8),
483 )
484 }
485 ast::Expression::Struct {
486 tag,
487 items,
488 type_: _,
489 } => {
490 let mut sig = self.module.make_signature();
491 sig.params.push(AbiParam::new(types::I64));
492 sig.returns.push(AbiParam::new(types::I64));
493
494 let id = self
495 .module
496 .declare_function("malloc", Linkage::Import, &sig)
497 .expect("failed to declare malloc");
498
499 let malloc = self.module.declare_func_in_func(id, &mut self.builder.func);
500
501 let size_arg = self
502 .builder
503 .ins()
504 .iconst(types::I64, (items.len() as i64) * 8 + 8);
505
506 let call = self.builder.ins().call(malloc, &[size_arg]);
507 let ptr = self.builder.inst_results(call)[0];
508
509 let tag = self.builder.ins().iconst(types::I64, i64::from(tag));
510 _ = self
511 .builder
512 .ins()
513 .store(MemFlags::new(), tag, ptr, Offset32::new(0));
514
515 for (index, item) in items.into_iter().enumerate() {
516 let index = index as i32 + 1;
517
518 let value = self.translate(item);
519
520 _ = self.builder.ins().store(
521 MemFlags::new(),
522 value,
523 ptr,
524 Offset32::new(index * 8),
525 );
526 }
527
528 ptr
529 }
530 ast::Expression::StructTag { value } => {
531 let ptr = self.translate(*value);
532
533 self.builder
534 .ins()
535 .load(types::I64, MemFlags::new(), ptr, Offset32::new(0))
536 }
537 ast::Expression::StructAccess {
538 value,
539 index,
540 type_,
541 } => {
542 let ptr = self.translate(*value);
543
544 self.builder.ins().load(
545 translate_type(&type_),
546 MemFlags::new(),
547 ptr,
548 Offset32::new(index as i32 * 8 + 8),
549 )
550 }
551 ast::Expression::Set { name, value } => {
552 let var = self.builder.declare_var(translate_type(&value.type_()));
553 _ = self.vars.insert(name.name, var);
554
555 let val = self.translate(*value);
556 self.builder.def_var(var, val);
557 self.builder.use_var(var)
558 }
559 ast::Expression::If { cond, then, else_ } => {
560 let cond = self.translate(*cond);
561
562 let then_block = self.builder.create_block();
563 let else_block = self.builder.create_block();
564 let merge_block = self.builder.create_block();
565
566 _ = self
567 .builder
568 .append_block_param(merge_block, translate_type(&then.type_()));
569
570 _ = self
571 .builder
572 .ins()
573 .brif(cond, then_block, &[], else_block, &[]);
574
575 self.builder.switch_to_block(then_block);
576 self.builder.seal_block(then_block);
577
578 let then_return = self.translate(*then);
579 _ = self
580 .builder
581 .ins()
582 .jump(merge_block, &[BlockArg::Value(then_return)]);
583
584 self.builder.switch_to_block(else_block);
585 self.builder.seal_block(else_block);
586
587 let else_return = self.translate(*else_);
588 _ = self
589 .builder
590 .ins()
591 .jump(merge_block, &[BlockArg::Value(else_return)]);
592
593 self.builder.switch_to_block(merge_block);
594 self.builder.seal_block(merge_block);
595
596 self.builder.block_params(merge_block)[0]
597 }
598 ast::Expression::Call {
599 target,
600 args,
601 type_,
602 } => {
603 let mut signature = self.module.make_signature();
604
605 for arg in &args {
606 signature
607 .params
608 .push(AbiParam::new(translate_type(&arg.type_())));
609 }
610 signature
611 .returns
612 .push(AbiParam::new(translate_type(&type_)));
613
614 let target = self.translate(*target);
615 let args: Vec<_> = args.into_iter().map(|arg| self.translate(arg)).collect();
616
617 let sig = self.builder.import_signature(signature);
618 let call = self.builder.ins().call_indirect(sig, target, &args);
619
620 self.builder.inst_results(call)[0]
621 }
622 ast::Expression::Panic { type_, .. } => match type_ {
623 ast::CompleteType::Func { .. }
624 | ast::CompleteType::Tuple { .. }
625 | ast::CompleteType::Struct { .. }
626 | ast::CompleteType::List(_)
627 | ast::CompleteType::String
628 | ast::CompleteType::Bool
629 | ast::CompleteType::Int => self.builder.ins().iconst(types::I64, 0),
630
631 ast::CompleteType::Float => self.builder.ins().f64const(0.0),
632 },
633 }
634 }
635}