nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
20 kB
571 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{}{}R{}", arguments.len(), arguments, returns)
79 }
80 ast::CompleteType::Struct { 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!("C{}{}", elements.len(), elements)
88 }
89 ast::CompleteType::List(element_type) => {
90 let element = mangle_type_name(element_type);
91
92 eco_format!("L{}{}", element.len(), element)
93 }
94 }
95}
96
97fn mangled_function_name(
98 module: EcoString,
99 name: EcoString,
100 arguments: &[ast::CompleteType],
101 returns: &ast::CompleteType,
102) -> EcoString {
103 let arguments = arguments.iter().map(mangle_type_name).join(",");
104 let returns = mangle_type_name(returns);
105
106 eco_format!(
107 "M{}{}_{}{}_A{}{}_R{}",
108 module.len(),
109 module.replace("/", "_"),
110 name.len(),
111 name,
112 arguments.len(),
113 arguments,
114 returns,
115 )
116}
117
118impl<'m, M: Module> FunctionTranslator<'m, M> {
119 fn new(cg: &'m mut CodeGen<M>) -> Self {
120 Self { cg }
121 }
122
123 fn translate(self, module: EcoString, function: ast::Function<ast::CompleteType>) {
124 let arguments: Vec<_> = function
125 .parameters
126 .iter()
127 .map(|parameter| parameter.type_.clone())
128 .collect();
129
130 let name = mangled_function_name(
131 module,
132 function.name.clone(),
133 &arguments,
134 &function.return_type,
135 );
136
137 self.cg.context.func.signature = self.signature_from_function(&function);
138
139 let mut builder =
140 FunctionBuilder::new(&mut self.cg.context.func, &mut self.cg.function_context);
141
142 let entry = builder.create_block();
143 builder.append_block_params_for_function_params(entry);
144 builder.switch_to_block(entry);
145 builder.seal_block(entry);
146
147 let value = {
148 let mut translator = ExpressionTranslator::new(&mut self.cg.module, &mut builder);
149
150 for (index, parameter) in function.parameters.iter().enumerate() {
151 if let Some(name) = ¶meter.name {
152 let var_type = translate_type(¶meter.type_);
153 let var = translator.builder.declare_var(var_type);
154 _ = translator.vars.insert(name.clone(), var);
155
156 let val = translator.builder.block_params(entry)[index];
157 translator.builder.def_var(var, val);
158 }
159 }
160
161 translator.translate(function.body)
162 };
163
164 _ = builder.ins().return_(&[value]);
165
166 builder.finalize();
167
168 let id = self
169 .cg
170 .module
171 .declare_function(&name, Linkage::Export, &self.cg.context.func.signature)
172 .expect("unable to declare function");
173
174 self.cg
175 .module
176 .define_function(id, &mut self.cg.context)
177 .expect("unable to define function");
178
179 self.cg.module.clear_context(&mut self.cg.context);
180 }
181
182 fn signature_from_function(&self, function: &ast::Function<ast::CompleteType>) -> Signature {
183 let mut sig = self.cg.module.make_signature();
184
185 for parameter in &function.parameters {
186 sig.params
187 .push(AbiParam::new(translate_type(¶meter.type_)));
188 }
189
190 sig.returns
191 .push(AbiParam::new(translate_type(&function.return_type)));
192
193 return sig;
194 }
195}
196
197fn translate_type(type_: &ast::CompleteType) -> Type {
198 match type_ {
199 ast::CompleteType::Int => types::I64,
200 ast::CompleteType::Float => types::F64,
201 ast::CompleteType::Bool => types::I64, // wasteful but whatever
202 ast::CompleteType::String => types::I64,
203 ast::CompleteType::Func {
204 arguments: _,
205 returns: _,
206 } => types::I64,
207 ast::CompleteType::Struct { elements: _ } => types::I64,
208 ast::CompleteType::List(_complete_type) => types::I64,
209 }
210}
211
212struct ExpressionTranslator<'m, 'b, M: Module> {
213 module: &'m mut M,
214 builder: &'m mut FunctionBuilder<'b>,
215 vars: HashMap<EcoString, Variable>,
216}
217
218impl<'m, 'b, M: Module> ExpressionTranslator<'m, 'b, M> {
219 fn new(module: &'m mut M, builder: &'m mut FunctionBuilder<'b>) -> Self {
220 Self {
221 module,
222 builder,
223 vars: Default::default(),
224 }
225 }
226
227 fn translate(&mut self, expression: ast::Expression<ast::CompleteType>) -> Value {
228 _ = self.module;
229
230 match expression {
231 ast::Expression::Block(expressions) => expressions
232 .into_iter()
233 .map(|expression| self.translate(expression))
234 .last()
235 .expect("block should be non-empty"),
236 ast::Expression::FunctionRef {
237 module,
238 name,
239 arity: _,
240 type_,
241 } => {
242 let ast::CompleteType::Func { arguments, returns } = type_ else {
243 unreachable!("function ref should have func type")
244 };
245
246 let name = mangled_function_name(module, name, &arguments, &returns);
247 let sig = {
248 let mut sig = self.module.make_signature();
249 for argument in arguments {
250 sig.params.push(AbiParam::new(translate_type(&argument)));
251 }
252 sig.returns.push(AbiParam::new(translate_type(&returns)));
253 sig
254 };
255
256 let id = self
257 .module
258 .declare_function(&name, Linkage::Import, &sig)
259 .expect("unable to declare function for import");
260
261 let func = self.module.declare_func_in_func(id, self.builder.func);
262
263 self.builder.ins().func_addr(types::I64, func)
264 }
265 ast::Expression::Var(var) => {
266 let var = self
267 .vars
268 .get(&var.name)
269 .cloned()
270 .expect("variable to be defined");
271
272 self.builder.use_var(var)
273 }
274 ast::Expression::Int { value } => {
275 let value = i64::try_from(value).expect("integer value too large");
276
277 self.builder.ins().iconst(types::I64, value)
278 }
279 ast::Expression::Float { value } => {
280 let value: f64 = value.parse().expect("invalid float value");
281
282 self.builder.ins().f64const(value)
283 }
284 ast::Expression::Bool { value } => match value {
285 true => self.builder.ins().iconst(types::I64, 1),
286 false => self.builder.ins().iconst(types::I64, 0),
287 },
288 ast::Expression::String { value: _ } => todo!(),
289 ast::Expression::Equals { lhs, rhs } => match lhs.type_() {
290 ast::CompleteType::Int => {
291 let lhs = self.translate(*lhs);
292 let rhs = self.translate(*rhs);
293
294 self.builder.ins().icmp(IntCC::Equal, lhs, rhs)
295 }
296 ast::CompleteType::Float => todo!(),
297 ast::CompleteType::Bool => todo!(),
298 ast::CompleteType::String => todo!(),
299 ast::CompleteType::Func {
300 arguments: _,
301 returns: _,
302 } => todo!(),
303 ast::CompleteType::Struct { elements: _ } => todo!(),
304 ast::CompleteType::List(_complete_type) => todo!(),
305 },
306 ast::Expression::NotEquals { lhs: _, rhs: _ } => todo!(),
307 ast::Expression::IntGt { lhs, rhs } => {
308 let lhs = self.translate(*lhs);
309 let rhs = self.translate(*rhs);
310
311 self.builder.ins().icmp(IntCC::SignedGreaterThan, lhs, rhs)
312 }
313 ast::Expression::IntGtEq { lhs, rhs } => {
314 let lhs = self.translate(*lhs);
315 let rhs = self.translate(*rhs);
316
317 self.builder
318 .ins()
319 .icmp(IntCC::SignedGreaterThanOrEqual, lhs, rhs)
320 }
321 ast::Expression::IntLt { lhs, rhs } => {
322 let lhs = self.translate(*lhs);
323 let rhs = self.translate(*rhs);
324
325 self.builder.ins().icmp(IntCC::SignedLessThan, lhs, rhs)
326 }
327 ast::Expression::IntLtEq { lhs, rhs } => {
328 let lhs = self.translate(*lhs);
329 let rhs = self.translate(*rhs);
330
331 self.builder
332 .ins()
333 .icmp(IntCC::SignedLessThanOrEqual, lhs, rhs)
334 }
335 ast::Expression::IntAdd { lhs, rhs } => {
336 let lhs = self.translate(*lhs);
337 let rhs = self.translate(*rhs);
338
339 self.builder.ins().iadd(lhs, rhs)
340 }
341 ast::Expression::IntSub { lhs, rhs } => {
342 let lhs = self.translate(*lhs);
343 let rhs = self.translate(*rhs);
344
345 self.builder.ins().isub(lhs, rhs)
346 }
347 ast::Expression::IntMul { lhs, rhs } => {
348 let lhs = self.translate(*lhs);
349 let rhs = self.translate(*rhs);
350
351 self.builder.ins().imul(lhs, rhs)
352 }
353 ast::Expression::IntDiv { lhs, rhs } => {
354 let lhs = self.translate(*lhs);
355 let rhs = self.translate(*rhs);
356
357 self.builder.ins().sdiv(lhs, rhs)
358 }
359 ast::Expression::IntRem { lhs, rhs } => {
360 let lhs = self.translate(*lhs);
361 let rhs = self.translate(*rhs);
362
363 self.builder.ins().srem(lhs, rhs)
364 }
365 ast::Expression::FloatGt { lhs, rhs } => {
366 let lhs = self.translate(*lhs);
367 let rhs = self.translate(*rhs);
368
369 self.builder.ins().fcmp(FloatCC::GreaterThan, lhs, rhs)
370 }
371 ast::Expression::FloatGtEq { lhs, rhs } => {
372 let lhs = self.translate(*lhs);
373 let rhs = self.translate(*rhs);
374
375 self.builder
376 .ins()
377 .fcmp(FloatCC::GreaterThanOrEqual, lhs, rhs)
378 }
379 ast::Expression::FloatLt { lhs, rhs } => {
380 let lhs = self.translate(*lhs);
381 let rhs = self.translate(*rhs);
382
383 self.builder.ins().fcmp(FloatCC::LessThan, lhs, rhs)
384 }
385 ast::Expression::FloatLtEq { lhs, rhs } => {
386 let lhs = self.translate(*lhs);
387 let rhs = self.translate(*rhs);
388
389 self.builder.ins().fcmp(FloatCC::LessThanOrEqual, lhs, rhs)
390 }
391 ast::Expression::FloatAdd { lhs, rhs } => {
392 let lhs = self.translate(*lhs);
393 let rhs = self.translate(*rhs);
394
395 self.builder.ins().fadd(lhs, rhs)
396 }
397 ast::Expression::FloatSub { lhs, rhs } => {
398 let lhs = self.translate(*lhs);
399 let rhs = self.translate(*rhs);
400
401 self.builder.ins().fsub(lhs, rhs)
402 }
403 ast::Expression::FloatMul { lhs, rhs } => {
404 let lhs = self.translate(*lhs);
405 let rhs = self.translate(*rhs);
406
407 self.builder.ins().fmul(lhs, rhs)
408 }
409 ast::Expression::FloatDiv { lhs, rhs } => {
410 let lhs = self.translate(*lhs);
411 let rhs = self.translate(*rhs);
412
413 self.builder.ins().fdiv(lhs, rhs)
414 }
415 ast::Expression::StringConcat { lhs: _, rhs: _ } => todo!(),
416 ast::Expression::List {
417 items: _,
418 tail: _,
419 type_: _,
420 } => todo!(),
421 ast::Expression::Struct {
422 tag,
423 items,
424 type_: _,
425 } => {
426 let mut sig = self.module.make_signature();
427 sig.params.push(AbiParam::new(types::I64));
428 sig.returns.push(AbiParam::new(types::I64));
429
430 let id = self
431 .module
432 .declare_function("malloc", Linkage::Import, &sig)
433 .expect("failed to declare malloc");
434
435 let malloc = self.module.declare_func_in_func(id, &mut self.builder.func);
436
437 let size_arg = self
438 .builder
439 .ins()
440 .iconst(types::I64, (items.len() as i64) * 8 + 8);
441
442 let call = self.builder.ins().call(malloc, &[size_arg]);
443 let ptr = self.builder.inst_results(call)[0];
444
445 let tag = i64::from(tag.unwrap_or_default());
446 let tag = self.builder.ins().iconst(types::I64, tag);
447 _ = self
448 .builder
449 .ins()
450 .store(MemFlags::new(), tag, ptr, Offset32::new(0));
451
452 for (index, item) in items.into_iter().enumerate() {
453 let index = index as i32 + 1;
454
455 let value = self.translate(item);
456
457 _ = self.builder.ins().store(
458 MemFlags::new(),
459 value,
460 ptr,
461 Offset32::new(index * 8),
462 );
463 }
464
465 ptr
466 }
467 ast::Expression::StructTag { value } => {
468 let ptr = self.translate(*value);
469
470 self.builder
471 .ins()
472 .load(types::I64, MemFlags::new(), ptr, Offset32::new(0))
473 }
474 ast::Expression::StructAccess {
475 value,
476 index,
477 type_,
478 } => {
479 let ptr = self.translate(*value);
480
481 self.builder.ins().load(
482 translate_type(&type_),
483 MemFlags::new(),
484 ptr,
485 Offset32::new(index as i32 * 8 + 8),
486 )
487 }
488 ast::Expression::Set { name, value } => {
489 let var = self.builder.declare_var(translate_type(&value.type_()));
490 _ = self.vars.insert(name.name, var);
491
492 let val = self.translate(*value);
493 self.builder.def_var(var, val);
494 self.builder.use_var(var)
495 }
496 ast::Expression::If { cond, then, else_ } => {
497 let cond = self.translate(*cond);
498
499 let then_block = self.builder.create_block();
500 let else_block = self.builder.create_block();
501 let merge_block = self.builder.create_block();
502
503 _ = self
504 .builder
505 .append_block_param(merge_block, translate_type(&then.type_()));
506
507 _ = self
508 .builder
509 .ins()
510 .brif(cond, then_block, &[], else_block, &[]);
511
512 self.builder.switch_to_block(then_block);
513 self.builder.seal_block(then_block);
514
515 let then_return = self.translate(*then);
516 _ = self
517 .builder
518 .ins()
519 .jump(merge_block, &[BlockArg::Value(then_return)]);
520
521 self.builder.switch_to_block(else_block);
522 self.builder.seal_block(else_block);
523
524 let else_return = self.translate(*else_);
525 _ = self
526 .builder
527 .ins()
528 .jump(merge_block, &[BlockArg::Value(else_return)]);
529
530 self.builder.switch_to_block(merge_block);
531 self.builder.seal_block(merge_block);
532
533 self.builder.block_params(merge_block)[0]
534 }
535 ast::Expression::Call {
536 target,
537 args,
538 type_,
539 } => {
540 let mut signature = self.module.make_signature();
541
542 for arg in &args {
543 signature
544 .params
545 .push(AbiParam::new(translate_type(&arg.type_())));
546 }
547 signature
548 .returns
549 .push(AbiParam::new(translate_type(&type_)));
550
551 let target = self.translate(*target);
552 let args: Vec<_> = args.into_iter().map(|arg| self.translate(arg)).collect();
553
554 let sig = self.builder.import_signature(signature);
555 let call = self.builder.ins().call_indirect(sig, target, &args);
556
557 self.builder.inst_results(call)[0]
558 }
559 ast::Expression::Panic { type_, .. } => match type_ {
560 ast::CompleteType::Func { .. }
561 | ast::CompleteType::Struct { .. }
562 | ast::CompleteType::List(_)
563 | ast::CompleteType::String
564 | ast::CompleteType::Bool
565 | ast::CompleteType::Int => self.builder.ins().iconst(types::I64, 0),
566
567 ast::CompleteType::Float => self.builder.ins().f64const(0.0),
568 },
569 }
570 }
571}