1use alloc::{rc::Rc, vec::Vec};
2
3use midenc_dialect_arith as arith;
4use midenc_dialect_cf as cf;
5use midenc_dialect_hir as hir;
6use midenc_dialect_scf as scf;
7use midenc_dialect_ub as ub;
8use midenc_dialect_wasm as wasm;
9use midenc_hir::{
10 Context, EntityMut, Op, Operation, OperationName, OperationRef, Report, Symbol, SymbolRef,
11 Visibility, WalkResult,
12 conversion::{
13 ConversionConfig, ConversionPatternSet, ConversionTarget, DynamicLegalityResult,
14 apply_full_conversion,
15 },
16 dialects::{builtin, debuginfo},
17 pass::{Pass, PassExecutionState, PostPassStatus},
18};
19use midenc_session::diagnostics::{Severity, Spanned};
20
21use crate::HirLowering;
22
23const OPERAND_STACK_WINDOW_FELTS: usize = miden_core::program::MIN_STACK_DEPTH;
28
29pub(crate) fn validate_procedure_roots(root: &Operation) -> Result<(), Report> {
37 root.prewalk(|op| {
38 let Some(procedure_root) = op.downcast_ref::<hir::ProcedureRoot>() else {
39 return WalkResult::Continue(());
40 };
41 match validate_procedure_root(procedure_root) {
42 Ok(_) => WalkResult::Continue(()),
43 Err(err) => WalkResult::Break(err),
44 }
45 })
46 .into_result()
47}
48
49pub(crate) fn validate_procedure_root(
58 procedure_root: &hir::ProcedureRoot,
59) -> Result<SymbolRef, Report> {
60 let op = procedure_root.as_operation();
61 let context = op.context();
62 let caller_symbol_table = op.nearest_symbol_table().ok_or_else(|| {
63 context
64 .diagnostics()
65 .diagnostic(Severity::Error)
66 .with_message("invalid procedure_root operation: no containing symbol table")
67 .with_primary_label(
68 procedure_root.span(),
69 "this operation must be nested in a symbol table",
70 )
71 .into_report()
72 })?;
73 let callee = {
74 let symbol_table = caller_symbol_table.borrow();
75 symbol_table
76 .as_symbol_table()
77 .expect("nearest_symbol_table returned a non-symbol-table operation")
78 .resolve(procedure_root.callee().path())
79 }
80 .ok_or_else(|| {
81 context
82 .diagnostics()
83 .diagnostic(Severity::Error)
84 .with_message("invalid procedure_root operation: unable to resolve callee")
85 .with_primary_label(
86 procedure_root.span(),
87 "this symbol path is not resolvable from this operation",
88 )
89 .into_report()
90 })?;
91
92 let callee_op = callee.borrow();
93
94 if op.get_attribute(hir::ProcedureRoot::NOTE_SCRIPT_ROOT_ATTR).is_some()
98 && callee_op
99 .as_symbol_operation()
100 .get_attribute(hir::NOTE_SCRIPT_EXPORT_ATTR)
101 .is_none()
102 {
103 return Err(context
104 .diagnostics()
105 .diagnostic(Severity::Error)
106 .with_message(
107 "invalid procedure_root operation: expected the note script root, but the callee \
108 is not the `note_script`-attributed export",
109 )
110 .with_primary_label(
111 procedure_root.span(),
112 "this operation must reference the lifted note-script export",
113 )
114 .with_help(
115 "the containing component must define a note-script export, and operations marked \
116 as the note script root must be retargeted at it during component export lifting",
117 )
118 .into_report());
119 }
120
121 let callee_symbol_table = callee_op.as_symbol_operation().nearest_symbol_table();
122 if callee_op.visibility() == Visibility::Private
123 && callee_symbol_table
124 .is_none_or(|callee_owner| !share_masm_module(caller_symbol_table, callee_owner))
125 {
126 return Err(context
127 .diagnostics()
128 .diagnostic(Severity::Error)
129 .with_message(format!(
130 "invalid hir.procedure_root: private callee '{}' is not linkable from another \
131 Miden Assembly module",
132 callee_op.path()
133 ))
134 .with_primary_label(
135 procedure_root.span(),
136 "this reference crosses a Miden Assembly module boundary",
137 )
138 .with_secondary_label(
139 callee_op.as_symbol_operation().span(),
140 "this callee is private to its defining module",
141 )
142 .with_help(
143 "declare the callee internal or public and ensure any intervening module is \
144 public, or materialize the root within its defining module",
145 )
146 .into_report());
147 }
148
149 if let Some(callee_symbol_table) = callee_symbol_table
150 && let Some(inaccessible_module) =
151 first_inaccessible_callee_module(caller_symbol_table, callee_symbol_table)
152 {
153 let inaccessible_module = inaccessible_module.borrow();
154 let module = inaccessible_module
155 .downcast_ref::<builtin::Module>()
156 .expect("only a module can make a MASM module path inaccessible");
157 return Err(context
158 .diagnostics()
159 .diagnostic(Severity::Error)
160 .with_message(format!(
161 "invalid hir.procedure_root: callee '{}' is nested beneath private module '{}'",
162 callee_op.path(),
163 module.path()
164 ))
165 .with_primary_label(
166 procedure_root.span(),
167 "this reference cannot reach the callee's Miden Assembly module",
168 )
169 .with_secondary_label(
170 module.as_operation().span(),
171 "this module is private outside its parent and sibling modules",
172 )
173 .with_help(
174 "declare the intervening module public, or materialize the root within its parent \
175 or a sibling module",
176 )
177 .into_report());
178 }
179
180 drop(callee_op);
181 Ok(callee)
182}
183
184fn share_masm_module(lhs: OperationRef, rhs: OperationRef) -> bool {
186 if lhs == rhs {
187 return true;
188 }
189
190 fn is_the_only_module_of_world(module: OperationRef, world: OperationRef) -> bool {
191 if module.borrow().parent_op() != Some(world) {
192 return false;
193 }
194 let world = world.borrow();
195 let Some(world) = world.downcast_ref::<builtin::World>() else {
196 return false;
197 };
198 let body = world.body();
199 let entry = body.entry();
200 let ops = entry.body();
201 let mut modules = ops.iter().filter(|op| op.is::<builtin::Module>());
202 modules.next().is_some_and(|only| only.as_operation_ref() == module)
203 && modules.next().is_none()
204 && !ops.iter().any(|op| op.is::<builtin::Component>())
205 }
206
207 (lhs.borrow().is::<builtin::World>() && is_the_only_module_of_world(rhs, lhs))
208 || (rhs.borrow().is::<builtin::World>() && is_the_only_module_of_world(lhs, rhs))
209}
210
211fn first_inaccessible_callee_module(
217 caller_owner: OperationRef,
218 callee_owner: OperationRef,
219) -> Option<OperationRef> {
220 fn owner_ancestry(mut owner: OperationRef) -> Vec<OperationRef> {
221 let mut ancestry = Vec::new();
222 loop {
223 ancestry.push(owner);
224 let parent = owner.borrow().nearest_symbol_table();
225 let Some(parent) = parent else {
226 break;
227 };
228 owner = parent;
229 }
230 ancestry.reverse();
231 ancestry
232 }
233
234 let caller_ancestry = owner_ancestry(caller_owner);
235 let callee_ancestry = owner_ancestry(callee_owner);
236 let common_len = caller_ancestry
237 .iter()
238 .zip(callee_ancestry.iter())
239 .take_while(|(caller, callee)| caller == callee)
240 .count();
241 callee_ancestry[common_len..].iter().enumerate().find_map(|(index, owner)| {
242 let owner_op = owner.borrow();
243 let module = owner_op.downcast_ref::<builtin::Module>()?;
244 let private_in_masm = !modules_form_the_artifact_interface(*owner)
245 && *module.get_visibility() != Visibility::Public;
246 (private_in_masm && index != 0).then_some(*owner)
247 })
248}
249
250fn modules_form_the_artifact_interface(mut owner: OperationRef) -> bool {
252 loop {
253 let op = owner.borrow();
254 if let Some(component) = op.downcast_ref::<builtin::Component>() {
255 return component.is_synthetic_wrapper();
256 }
257 if let Some(world) = op.downcast_ref::<builtin::World>() {
258 let body = world.body();
259 return !body.entry().body().iter().any(|op| op.is::<builtin::Component>());
260 }
261 let Some(parent) = op.parent_op() else {
262 return false;
263 };
264 drop(op);
265 owner = parent;
266 }
267}
268
269midenc_hir::inventory::submit!(::midenc_hir::pass::registry::PassInfo::new::<LegalizeForMasm>(
270 LegalizeForMasm::ARGUMENT,
271 "legalize HIR for MASM codegen"
272));
273
274#[derive(Default)]
281pub struct LegalizeForMasm;
282
283impl LegalizeForMasm {
284 pub const ARGUMENT: &'static str = "legalize-for-masm";
286}
287
288impl Pass for LegalizeForMasm {
289 type Target = Operation;
290
291 fn name(&self) -> &'static str {
292 "legalize-for-masm"
293 }
294
295 fn argument(&self) -> &'static str {
296 Self::ARGUMENT
297 }
298
299 fn description(&self) -> &'static str {
300 "Legalizes HIR to the set of operations supported by MASM codegen"
301 }
302
303 fn can_schedule_on(&self, _name: &OperationName) -> bool {
304 true
305 }
306
307 fn initialize(&mut self, context: Rc<Context>) -> Result<(), Report> {
308 register_masm_legalization_dialects(&context);
309 Ok(())
310 }
311
312 fn run_on_operation(
313 &mut self,
314 op: EntityMut<'_, Self::Target>,
315 state: &mut PassExecutionState,
316 ) -> Result<(), Report> {
317 let root = op.as_operation_ref();
318 let context = op.context_rc();
319 drop(op);
320
321 let target = masm_legalization_target(context.clone());
322 let patterns = ConversionPatternSet::new(context);
323 let result = apply_full_conversion(root, target, patterns, ConversionConfig::default())?;
324
325 let changed = PostPassStatus::from(result.changed());
326 state.set_post_pass_status(changed);
327 if !changed.ir_changed() {
328 state.preserved_analyses_mut().preserve_all();
329 }
330
331 Ok(())
332 }
333}
334
335pub fn masm_legalization_target(context: Rc<Context>) -> ConversionTarget {
342 register_masm_legalization_dialects(&context);
343 let mut target = ConversionTarget::new(context);
344 populate_masm_legalization_target(&mut target);
345 target
346}
347
348pub fn populate_masm_legalization_target(target: &mut ConversionTarget) {
353 target
354 .add_legal_op::<builtin::World>()
355 .add_legal_op::<builtin::Component>()
356 .add_legal_op::<builtin::Module>()
357 .add_legal_op::<builtin::Interface>()
358 .add_legal_op::<builtin::Function>()
359 .add_legal_op::<builtin::GlobalVariable>()
360 .add_legal_op::<builtin::Segment>()
361 .add_dynamically_legal_op::<builtin::FunctionTable, _>(|op| {
362 let inside_module =
363 op.parent_op().is_some_and(|parent| parent.borrow().is::<builtin::Module>());
364 if inside_module {
365 DynamicLegalityResult::legal()
366 } else {
367 DynamicLegalityResult::illegal_with_reason(Report::msg(format!(
368 "operation '{}' is only permitted in the body of a 'builtin.module', the one \
369 place the linker's memory layout visits",
370 op.name()
371 )))
372 }
373 })
374 .add_dynamically_legal_op::<builtin::FunctionTableEntry, _>(|op| {
375 let entry = op
376 .downcast_ref::<builtin::FunctionTableEntry>()
377 .expect("this legality rule is registered for builtin.function_table_entry");
378 let Some(parent) = op.parent_op() else {
379 return DynamicLegalityResult::illegal_with_reason(Report::msg(format!(
380 "operation '{}' is only permitted in the entries region of a \
381 'builtin.function_table'",
382 op.name()
383 )));
384 };
385 let parent = parent.borrow();
386 let Some(table) = parent.downcast_ref::<builtin::FunctionTable>() else {
387 return DynamicLegalityResult::illegal_with_reason(Report::msg(format!(
388 "operation '{}' is only permitted in the entries region of a \
389 'builtin.function_table'",
390 op.name()
391 )));
392 };
393 let slot = *entry.get_index();
394 let num_slots = *table.get_num_slots();
395 if slot >= num_slots {
396 return DynamicLegalityResult::illegal_with_reason(Report::msg(format!(
397 "operation '{}' initializes slot {slot}, which is out of bounds for table \
398 '{}' with {num_slots} slots",
399 op.name(),
400 table.get_name().as_str()
401 )));
402 }
403 if *entry.get_type_tag() == 0 {
404 return DynamicLegalityResult::illegal_with_reason(Report::msg(format!(
405 "operation '{}' uses signature tag 0, which is reserved for null slots",
406 op.name()
407 )));
408 }
409 if entry.resolve_callee().is_none() {
410 return DynamicLegalityResult::illegal_with_reason(Report::msg(format!(
411 "operation '{}' names callee '{}', which does not resolve",
412 op.name(),
413 entry.callee().path()
414 )));
415 }
416 DynamicLegalityResult::legal()
417 })
418 .add_dynamically_legal_op::<hir::ExecIndirect, _>(|op| {
419 let exec = op
420 .downcast_ref::<hir::ExecIndirect>()
421 .expect("this legality rule is registered for hir.exec_indirect");
422 let signature = exec.get_signature();
423 if let Some(index) = signature.params.iter().position(|param| {
426 !matches!(
427 param.extension(),
428 midenc_hir::dialects::builtin::attributes::ArgumentExtension::None
429 )
430 }) {
431 return DynamicLegalityResult::illegal_with_reason(Report::msg(format!(
432 "operation '{}' does not support argument extension, which parameter {index} \
433 requires",
434 op.name()
435 )));
436 }
437 let arg_felts: usize =
438 signature.params.iter().map(|param| param.ty.size_in_felts()).sum();
439 if arg_felts + 1 > OPERAND_STACK_WINDOW_FELTS {
440 return DynamicLegalityResult::illegal_with_reason(Report::msg(format!(
441 "operation '{}' schedules {arg_felts} argument field elements plus the table \
442 index, which exceeds the {OPERAND_STACK_WINDOW_FELTS}-element operand stack \
443 window",
444 op.name()
445 )));
446 }
447 DynamicLegalityResult::legal()
448 })
449 .add_dynamically_legal_op::<builtin::UnrealizedConversionCast, _>(|op| {
450 DynamicLegalityResult::illegal_with_reason(Report::msg(format!(
451 "operation '{}' is temporary dialect-conversion scaffolding and must be \
452 reconciled or lowered to a real cast before MASM codegen",
453 op.name()
454 )))
455 })
456 .add_dynamically_legal_dialect::<builtin::BuiltinDialect, _>(masm_lowerable_op)
457 .add_dynamically_legal_dialect::<arith::ArithDialect, _>(masm_lowerable_op)
458 .add_dynamically_legal_dialect::<cf::ControlFlowDialect, _>(masm_lowerable_op)
459 .add_dynamically_legal_dialect::<scf::ScfDialect, _>(masm_lowerable_op)
460 .add_dynamically_legal_dialect::<ub::UndefinedBehaviorDialect, _>(masm_lowerable_op)
461 .add_dynamically_legal_dialect::<hir::HirDialect, _>(masm_lowerable_op)
462 .add_dynamically_legal_dialect::<wasm::WasmDialect, _>(masm_lowerable_op)
463 .add_dynamically_legal_dialect::<debuginfo::DebugInfoDialect, _>(masm_lowerable_op);
464}
465
466fn register_masm_legalization_dialects(context: &Rc<Context>) {
467 context.get_or_register_dialect::<builtin::BuiltinDialect>();
468 context.get_or_register_dialect::<arith::ArithDialect>();
469 context.get_or_register_dialect::<cf::ControlFlowDialect>();
470 context.get_or_register_dialect::<scf::ScfDialect>();
471 context.get_or_register_dialect::<ub::UndefinedBehaviorDialect>();
472 context.get_or_register_dialect::<hir::HirDialect>();
473 context.get_or_register_dialect::<wasm::WasmDialect>();
474 context.get_or_register_dialect::<debuginfo::DebugInfoDialect>();
475}
476
477fn masm_lowerable_op(op: &Operation) -> DynamicLegalityResult {
478 if op.implements::<dyn HirLowering>() {
479 DynamicLegalityResult::legal()
480 } else {
481 DynamicLegalityResult::illegal_with_reason(Report::msg(format!(
482 "operation '{}' is in a MASM-supported dialect but does not implement HirLowering",
483 op.name()
484 )))
485 }
486}
487
488#[cfg(test)]
489mod tests {
490 use alloc::{boxed::Box, format};
491
492 use midenc_dialect_arith::ArithOpBuilder;
493 use midenc_dialect_hir::HirOpBuilder;
494 use midenc_hir::{
495 Ident, SourceSpan, Type, ValueRef, Visibility,
496 dialects::builtin::{
497 BuiltinOpBuilder, ModuleBuilder,
498 attributes::{AbiParam, Signature},
499 },
500 testing::Test,
501 };
502
503 use super::*;
504
505 #[test]
506 fn masm_supported_ops_pass_legalization() {
507 let mut test = Test::new("masm_supported_ops_pass_legalization", &[], &[Type::U32]);
508 {
509 let mut builder = test.function_builder();
510 let value = builder.u32(7, SourceSpan::UNKNOWN);
511 builder.ret([value], SourceSpan::UNKNOWN).unwrap();
512 }
513
514 test.apply_pass::<LegalizeForMasm>(true).unwrap();
515 }
516
517 #[test]
518 fn unsupported_hir_ops_fail_legalization() {
519 let mut test = Test::new("unsupported_hir_ops_fail_legalization", &[], &[]);
520 {
521 let mut builder = test.function_builder();
522 let _bytes = builder.bytes(&[1, 2, 3, 4], SourceSpan::UNKNOWN).unwrap();
523 builder.ret(None, SourceSpan::UNKNOWN).unwrap();
524 }
525
526 let err = test.apply_pass::<LegalizeForMasm>(false).unwrap_err();
527 let message = format!("{err}");
528 assert!(message.contains("hir.bytes"));
529 assert!(message.contains("does not implement HirLowering"));
530 }
531
532 #[test]
533 fn unreconciled_unrealized_conversion_casts_fail_legalization() {
534 let mut test = Test::new(
535 "unreconciled_unrealized_conversion_casts_fail_legalization",
536 &[Type::U32],
537 &[Type::I32],
538 );
539 {
540 let mut builder = test.function_builder();
541 let entry = builder.entry_block();
542 let arg = entry.borrow().arguments()[0].borrow().as_value_ref();
543 let cast =
544 builder.unrealized_conversion_cast(arg, Type::I32, SourceSpan::UNKNOWN).unwrap();
545 builder.ret([cast], SourceSpan::UNKNOWN).unwrap();
546 }
547
548 let err = test.apply_pass::<LegalizeForMasm>(false).unwrap_err();
549 let message = format!("{err}");
550 assert!(message.contains("builtin.unrealized_conversion_cast"));
551 assert!(message.contains("temporary dialect-conversion scaffolding"));
552 }
553
554 #[test]
557 fn function_tables_outside_a_module_fail_legalization() {
558 let mut test = Test::new("function_tables_outside_a_module_fail_legalization", &[], &[]);
559 {
560 let mut builder = test.function_builder();
561 builder
562 .create_function_table(Ident::from("tbl"), Visibility::Private, 2)
563 .unwrap();
564 builder.ret(None, SourceSpan::UNKNOWN).unwrap();
565 }
566
567 let err = test.apply_pass::<LegalizeForMasm>(false).unwrap_err();
568 let message = format!("{err}");
569 assert!(message.contains("builtin.function_table"), "{message}");
570 assert!(message.contains("body of a 'builtin.module'"), "{message}");
571 }
572
573 fn legalize_module(test: &Test) -> Result<(), Report> {
579 use midenc_hir::pass::{Nesting, PassManager};
580
581 let mut pm = PassManager::on::<builtin::Module>(test.context_rc(), Nesting::Implicit);
582 pm.add_pass(Box::new(LegalizeForMasm));
583 pm.enable_verifier(false);
584 pm.run(test.module().as_operation_ref())
585 }
586
587 #[test]
590 fn out_of_bounds_function_table_entries_fail_legalization() {
591 let mut test = Test::named("out_of_bounds_entry").in_module("m");
592 test.with_function("dispatch", &[], &[]);
593 let table = ModuleBuilder::new(test.module())
594 .define_function_table(Ident::from("tbl"), Visibility::Private, 1)
595 .unwrap();
596 ModuleBuilder::new(test.module())
597 .append_function_table_entry(table, 0, 1, test.function(), SourceSpan::UNKNOWN)
598 .unwrap();
599 {
602 let mut entry_op = {
603 let table = table.borrow();
604 let entries = table.entries();
605 entries.entry().body().into_iter().next().unwrap().as_operation_ref()
606 };
607 let mut entry_op = entry_op.borrow_mut();
608 entry_op
609 .downcast_mut::<builtin::FunctionTableEntry>()
610 .expect("a function table's entries region holds only entries")
611 .set_index(9u32);
612 }
613
614 let err = legalize_module(&test).unwrap_err();
615 let message = format!("{err}");
616 assert!(message.contains("builtin.function_table_entry"), "{message}");
617 assert!(message.contains("out of bounds"), "{message}");
618 }
619
620 fn test_with_exec_indirect(test: &mut Test, signature: Signature) {
623 test.with_function("dispatch", &[Type::U32], &[]);
624 let table = ModuleBuilder::new(test.module())
625 .define_function_table(Ident::from("tbl"), Visibility::Private, 2)
626 .unwrap();
627 let arity = signature.params.len();
628 let mut builder = test.function_builder();
629 let index = builder.entry_block().borrow().arguments()[0] as ValueRef;
630 let args = (0..arity)
631 .map(|_| builder.u32(0, SourceSpan::UNKNOWN))
632 .collect::<alloc::vec::Vec<_>>();
633 builder
634 .exec_indirect(table, signature, 1, index, args, SourceSpan::UNKNOWN)
635 .unwrap();
636 builder.ret(None, SourceSpan::UNKNOWN).unwrap();
637 }
638
639 #[test]
643 fn oversized_exec_indirect_arguments_fail_legalization() {
644 let mut test = Test::named("oversized_exec_indirect").in_module("m");
645 let signature = Signature::new(&test.context_rc(), vec![Type::U32; 16], []);
646 test_with_exec_indirect(&mut test, signature);
647
648 let err = test.apply_pass::<LegalizeForMasm>(false).unwrap_err();
649 let message = format!("{err}");
650 assert!(message.contains("hir.exec_indirect"), "{message}");
651 assert!(message.contains("operand stack window"), "{message}");
652 }
653
654 #[test]
657 fn extension_requiring_exec_indirect_arguments_fail_legalization() {
658 let mut test = Test::named("extension_exec_indirect").in_module("m");
659 let mut signature = Signature::new(&test.context_rc(), [Type::U32], []);
660 signature.params[0] = AbiParam::sext(Type::U32, &test.context_rc());
661 test_with_exec_indirect(&mut test, signature);
662
663 let err = test.apply_pass::<LegalizeForMasm>(false).unwrap_err();
664 let message = format!("{err}");
665 assert!(message.contains("hir.exec_indirect"), "{message}");
666 assert!(message.contains("argument extension"), "{message}");
667 }
668}