lamina_ir/function.rs
1//! # Function Representation
2//!
3//! Structures for representing functions in the Lamina IR.
4//! Functions are the primary unit of code organization and execution, containing
5//! basic blocks which hold the actual instructions.
6//!
7//! ## Key Concepts
8//!
9//! - **Functions**: Complete function definitions with signatures and implementations
10//! - **Basic Blocks**: Linear sequences of instructions ending with a terminator
11//! - **Function Signatures**: Parameter types and return types
12//! - **Annotations**: Metadata that affects function behavior and optimization
13//! - **SSA Variables**: Single Static Assignment form for all variables
14//!
15//! ## Function Structure
16//!
17//! A function consists of:
18//! 1. **Signature** (`FunctionSignature`): Parameters and return type
19//! 2. **Basic Blocks** (`HashMap<&str, BasicBlock>`): The actual implementation
20//! 3. **Entry Block** (`&str`): The first block to execute when called
21//! 4. **Annotations** (`Vec<FunctionAnnotation>`): Metadata like `@inline`, `@export`
22//!
23//! ## Function Signature
24//!
25//! ```rust
26//! // Example function signature in source language
27//! fn add_numbers(a: i32, b: i32) -> i32 { a + b }
28//!
29//! // Corresponding IR structure
30//! # use lamina_ir::{Type, PrimitiveType};
31//! # use lamina_ir::function::{FunctionSignature, FunctionParameter};
32//! let signature = FunctionSignature {
33//! params: vec![
34//! FunctionParameter { name: "a", ty: Type::Primitive(PrimitiveType::I32), annotations: vec![] },
35//! FunctionParameter { name: "b", ty: Type::Primitive(PrimitiveType::I32), annotations: vec![] }
36//! ],
37//! return_type: Type::Primitive(PrimitiveType::I32)
38//! };
39//! ```
40//!
41//! ## Basic Block Organization
42//!
43//! ### Block Structure
44//! ```text
45//! block_name:
46//! instruction1
47//! instruction2
48//! ...
49//! terminator_instruction
50//! ```
51//!
52//! ### Terminator Instructions
53//! Each basic block must end with a **terminator instruction**:
54//! - `Br` (conditional branch): `br %condition, "true_block", "false_block"`
55//! - `Jmp` (unconditional jump): `jmp "target_block"`
56//! - `Ret` (return): `ret.i32 %value` or `ret.void`
57//!
58//! ### Control Flow Rules
59//! - Instructions within a block execute sequentially
60//! - Control flow only changes at block boundaries
61//! - No jumps into the middle of blocks
62//! - All paths must eventually reach a terminator
63//!
64//! ## Function Annotations
65//!
66//! ### Built-in Annotations
67//! - **`@inline`**: Suggest the function should be inlined
68//! - **`@export`**: Make the function visible to other modules
69//! - **`@internal`**: Function is only used within this module
70//! - **`@noreturn`**: Function never returns (e.g., exits the program)
71//!
72//! ### Custom Annotations
73//! Functions can have custom annotations for:
74//! - **Optimization hints**: `@optimize_speed`, `@optimize_size`
75//! - **Debugging**: `@debug_info`, `@trace_calls`
76//! - **Security**: `@trusted`, `@untrusted`
77//! - **Platform-specific**: `@windows_only`, `@linux_only`
78//!
79//! ## Variable Management (SSA Form)
80//!
81//! ### Single Static Assignment
82//! - Each variable is assigned exactly **once** in its lifetime
83//! - Variables are immutable after assignment
84//! - Enables optimizations and analysis
85//!
86//! ### Variable Naming Convention
87//! ```text
88//! %result # Standard variable
89//! %temp_1 # Temporary variable
90//! %cond # Condition variable
91//! %ptr # Pointer variable
92//! ```
93//!
94//! ### Variable Scoping
95//! - Variables are scoped to their function
96//! - Variables from different blocks can be merged using `phi` nodes
97//! - No global variable shadowing within functions
98//!
99//! ## Function Creation Patterns
100//!
101//! ### Simple Function (No Parameters)
102//! ```rust
103//! use lamina_ir::{IRBuilder, Type, PrimitiveType};
104//! use lamina_ir::builder::i32;
105//!
106//! let mut builder = IRBuilder::new();
107//! builder
108//! .function("hello", Type::Void)
109//! .print(i32(42))
110//! .ret_void();
111//! ```
112//!
113//! ### Function with Parameters
114//! ```rust
115//! use lamina_ir::{IRBuilder, Type, PrimitiveType, BinaryOp};
116//! use lamina_ir::builder::{var, i32};
117//!
118//! let mut builder = IRBuilder::new();
119//! builder
120//! .function_with_params("add", vec![
121//! lamina_ir::FunctionParameter {
122//! name: "a",
123//! ty: Type::Primitive(PrimitiveType::I32),
124//! annotations: vec![]
125//! },
126//! lamina_ir::FunctionParameter {
127//! name: "b",
128//! ty: Type::Primitive(PrimitiveType::I32),
129//! annotations: vec![]
130//! }
131//! ], Type::Primitive(PrimitiveType::I32))
132//! .binary(BinaryOp::Add, "result", PrimitiveType::I32, var("a"), var("b"))
133//! .ret(Type::Primitive(PrimitiveType::I32), var("result"));
134//! ```
135//!
136//! ### Function with Control Flow
137//! ```rust
138//! use lamina_ir::{IRBuilder, Type, PrimitiveType, CmpOp};
139//! use lamina_ir::builder::{var, i32};
140//!
141//! let mut builder = IRBuilder::new();
142//! builder
143//! .function("max", Type::Primitive(PrimitiveType::I32))
144//! .cmp(CmpOp::Gt, "a_greater", PrimitiveType::I32, var("a"), var("b"))
145//! .branch(var("a_greater"), "return_a", "return_b")
146//! .block("return_a")
147//! .ret(Type::Primitive(PrimitiveType::I32), var("a"))
148//! .block("return_b")
149//! .ret(Type::Primitive(PrimitiveType::I32), var("b"));
150//! ```
151//!
152//! ## Function Calling Convention
153//!
154//! ### Parameter Passing
155//! - Parameters are passed by value
156//! - Complex types (structs, arrays) are passed by reference
157//! - Variable argument functions are supported
158//!
159//! ### Return Value Handling
160//! - Simple types returned in registers
161//! - Complex types returned via implicit reference parameter
162//! - Void functions have no return value
163//!
164//! ### Stack Frame Management
165//! - Functions automatically manage their stack frames
166//! - Local variables allocated on stack
167//! - Stack frame cleaned up on function return
168//!
169//! ## Advanced
170//!
171//! ### Exception Handling
172//! ```rust
173//! # use lamina_ir::{IRBuilder, Type, PrimitiveType};
174//! // Functions can have exception handling blocks
175//! let mut builder = IRBuilder::new();
176//! builder
177//! .function("safe_divide", Type::Primitive(PrimitiveType::I32))
178//! .block("try");
179//! // ... division code ...
180//! builder.block("catch");
181//! // ... exception handling ...
182//! ```
183//!
184//! ### Tail Recursion
185//! ```rust
186//! # use lamina_ir::{IRBuilder, Type, PrimitiveType};
187//! // Functions can be optimized for tail recursion
188//! let mut builder = IRBuilder::new();
189//! builder
190//! .function("factorial", Type::Primitive(PrimitiveType::I32));
191//! // ... tail recursive implementation ...
192//! ```
193//!
194//! ## Examples
195//!
196//! ### Complete Function Example
197//! ```rust
198//! use lamina_ir::{IRBuilder, Type, PrimitiveType, CmpOp, BinaryOp};
199//! use lamina_ir::builder::{var, i32};
200//!
201//! let mut builder = IRBuilder::new();
202//!
203//! builder
204//! .function_with_params("absolute_value", vec![
205//! lamina_ir::FunctionParameter {
206//! name: "x",
207//! ty: Type::Primitive(PrimitiveType::I32),
208//! annotations: vec![]
209//! }
210//! ], Type::Primitive(PrimitiveType::I32))
211//! .annotate(lamina_ir::FunctionAnnotation::Inline)
212//! .cmp(CmpOp::Lt, "is_negative", PrimitiveType::I32, var("x"), i32(0))
213//! .branch(var("is_negative"), "negate", "return_x")
214//! .block("negate")
215//! .binary(BinaryOp::Sub, "result", PrimitiveType::I32, i32(0), var("x"))
216//! .ret(Type::Primitive(PrimitiveType::I32), var("result"))
217//! .block("return_x")
218//! .ret(Type::Primitive(PrimitiveType::I32), var("x"));
219//!
220//! let module = builder.build();
221//! ```
222
223use std::collections::HashMap; // Using HashMap for basic blocks
224use std::fmt;
225
226use super::instruction::Instruction;
227use super::types::{Identifier, Label, Type};
228
229/// Function annotations that provide metadata about function behavior.
230///
231/// Annotations are hints to the compiler about how to handle a function.
232/// They can affect optimization decisions, calling conventions, and code generation.
233///
234/// # Examples
235///
236/// ```rust
237/// use lamina_ir::{IRBuilder, Type, FunctionAnnotation};
238///
239/// let mut builder = IRBuilder::new();
240/// builder
241/// .function("fast_calc", Type::Void)
242/// .annotate(FunctionAnnotation::Inline) // Hint to inline this function
243/// .annotate(FunctionAnnotation::Cold); // Function is rarely called
244/// ```
245#[derive(Debug, Clone, PartialEq, Eq, Hash)]
246pub enum FunctionAnnotation {
247 /// Hint to the compiler to inline this function at call sites.
248 ///
249 /// Inlining can improve performance by eliminating function call overhead,
250 /// but may increase code size. Use for small, frequently called functions.
251 Inline,
252
253 /// Mark this function as exported (visible to other modules).
254 ///
255 /// Exported functions can be called from other modules or linked against
256 /// by external code. This is typically used for public APIs.
257 Export,
258
259 /// Mark this function as having external linkage (imported from another module).
260 ///
261 /// External functions are declarations without implementation. They represent
262 /// functions defined in other modules or external libraries.
263 Extern,
264
265 /// Indicate that this function never returns normally.
266 ///
267 /// Functions marked with `NoReturn` always terminate the program (e.g., `exit`, `panic`).
268 /// This lets the compiler optimize control flow and eliminate unreachable code.
269 NoReturn,
270
271 /// Hint to the compiler to never inline this function.
272 ///
273 /// Use for large functions or when you want to preserve the function call
274 /// for debugging or profiling purposes.
275 NoInline,
276
277 /// Mark this function as "cold" (rarely executed).
278 ///
279 /// Cold functions are optimized for size rather than speed, and may be
280 /// placed in a separate code section to improve instruction cache usage.
281 Cold,
282
283 /// Mark this function as "hot" (frequently executed).
284 ///
285 /// Hot functions are aggressively optimized for performance and may be
286 /// placed in hot code sections to improve instruction cache usage.
287 Hot,
288
289 /// Mark this function as pure (has no side effects and depends only on inputs).
290 ///
291 /// Pure functions can be optimized more aggressively and may be subject to
292 /// common subexpression elimination, memoization, or other optimizations.
293 Pure,
294
295 /// Mark this function as const (can be evaluated at compile time).
296 ///
297 /// Const functions have no side effects and can be evaluated during compilation.
298 /// This enables compile-time function evaluation and constant folding.
299 Const,
300
301 /// Mark this function as having internal linkage (private to this module).
302 ///
303 /// Internal functions are not visible outside the current module and cannot
304 /// be called from other modules. This enables more aggressive optimizations.
305 Internal,
306
307 /// Mark this function as having private linkage (ELF-specific).
308 ///
309 /// Private symbols are not exported in the dynamic symbol table and are
310 /// only visible within the same shared object. This is stronger than internal linkage.
311 Private,
312
313 /// Mark this function as having hidden visibility (ELF-specific).
314 ///
315 /// Hidden symbols are not exported but may be accessed from other components
316 /// within the same shared object. This improves optimization opportunities
317 /// than protected visibility.
318 Hidden,
319
320 /// Mark this function as having protected visibility (ELF-specific).
321 ///
322 /// Protected symbols are exported but can only be preempted by symbols
323 /// from the same shared object. This lets intra-module function calls
324 /// use direct references while still allowing inter-module calls.
325 Protected,
326
327 /// Mark this function as having weak linkage.
328 ///
329 /// Weak symbols can be overridden by stronger definitions. If multiple
330 /// definitions exist, the strongest one is used.
331 Weak,
332
333 /// Use the C calling convention (system default).
334 ///
335 /// The C calling convention is the most common and portable convention,
336 /// used for interfacing with C libraries and system calls.
337 CCc,
338
339 /// Use the fastcall calling convention (first few arguments in registers).
340 ///
341 /// Fastcall passes the first few arguments in registers rather than on the stack,
342 /// which can improve performance for functions with few arguments.
343 CCfast,
344
345 /// Use the cold calling convention (function is rarely called).
346 ///
347 /// Cold calling convention optimizes for the case where the function is rarely executed,
348 /// potentially using slower but more compact calling sequences.
349 CCcold,
350
351 /// Use the preserve_most calling convention (preserves most registers).
352 ///
353 /// This convention preserves most registers across the call, requiring the caller
354 /// to save fewer registers. Useful for functions that call many other functions.
355 CCpreserveMost,
356
357 /// Use the preserve_all calling convention (preserves all registers).
358 ///
359 /// This convention preserves all registers across the call, minimizing the caller's
360 /// register save/restore overhead. Useful for leaf functions or hot paths.
361 CCpreserveAll,
362
363 /// Use the swift calling convention (for Swift interoperability).
364 ///
365 /// Swift calling convention is used for interfacing with Swift code,
366 /// with special handling for Swift types and error propagation.
367 CCswift,
368
369 /// Use the tail calling convention (enables tail call optimization).
370 ///
371 /// Tail calling convention lets the compiler optimize tail recursive calls
372 /// and function calls in tail position into jumps instead of calls.
373 CCtail,
374
375 /// Specify a custom calling convention by name.
376 ///
377 /// For calling conventions not covered by the above variants, you can specify
378 /// a custom convention by name (e.g., "vectorcall", "thiscall", etc.).
379 CallingConvention(String),
380
381 /// Specify that this function should be placed in a specific section.
382 ///
383 /// Section placement can affect memory layout, performance, and linking.
384 /// Common sections include ".text", ".text.hot", ".text.cold", etc.
385 Section(String),
386
387 /// Specify the minimum alignment for this function in bytes.
388 ///
389 /// Function alignment can improve performance by making the function
390 /// starts at an address that works well for the target architecture.
391 Align(u32),
392
393 /// Mark this function as unsafe (bypasses safety checks).
394 ///
395 /// Unsafe functions may perform operations that violate memory safety
396 /// or other invariants. Use with caution and only when necessary.
397 Unsafe,
398
399 /// Mark this function as deprecated (should not be used).
400 ///
401 /// Deprecated functions may be removed in future versions. The compiler
402 /// may emit warnings when these functions are called.
403 Deprecated(Option<String>),
404}
405
406/// Attributes that can be applied to function parameters and variables.
407#[derive(Debug, Clone, PartialEq, Eq, Hash)]
408pub enum VariableAnnotation {
409 /// Mark this parameter as non-null (never accepts null pointers).
410 ///
411 /// This lets the compiler optimize away null checks and enables
412 /// more aggressive optimizations for pointer operations.
413 NonNull,
414
415 /// Mark this parameter as read-only (not modified by the function).
416 ///
417 /// Read-only parameters can be passed by reference without copying,
418 /// and the compiler can optimize based on the immutability guarantee.
419 ReadOnly,
420
421 /// Mark this parameter as write-only (only written to, never read from).
422 ///
423 /// Write-only parameters are typically used for output parameters.
424 /// The compiler can optimize away reads from these parameters.
425 WriteOnly,
426
427 /// Specify the alignment requirement for this parameter in bytes.
428 ///
429 /// Parameter alignment affects how the parameter is passed and stored.
430 /// This can improve performance on some architectures.
431 Align(u32),
432
433 /// Mark this parameter as sensitive (contains security-critical data).
434 ///
435 /// Sensitive parameters may receive special treatment such as avoiding
436 /// storage in registers or zeroing them after use.
437 Sensitive,
438
439 /// Specify that this parameter should be passed in a specific register.
440 ///
441 /// Register assignment can improve performance but reduces flexibility.
442 /// Only use when you know the target ABI well.
443 Register(String),
444
445 /// Mark this parameter as unused (not used by the function).
446 ///
447 /// Unused parameters may be optimized away or may indicate API compatibility.
448 Unused,
449}
450
451/// A function parameter with its name, type, and attributes.
452///
453/// Function parameters are the inputs to a function and are bound to values
454/// when the function is called. Each parameter has a unique name within the
455/// function scope, a specific type, and optional attributes that provide
456/// additional information to the compiler.
457///
458/// # Examples
459///
460/// ```rust
461/// use lamina_ir::function::FunctionParameter;
462/// use lamina_ir::{Type, PrimitiveType};
463/// use lamina_ir::function::VariableAnnotation;
464///
465/// let param = FunctionParameter {
466/// name: "data",
467/// ty: Type::Primitive(PrimitiveType::Ptr),
468/// annotations: vec![VariableAnnotation::NonNull, VariableAnnotation::ReadOnly],
469/// };
470/// ```
471#[derive(Debug, Clone, PartialEq, Eq, Hash)]
472pub struct FunctionParameter<'a> {
473 /// The parameter name (without the `%` prefix)
474 pub name: Identifier<'a>,
475 /// The parameter's type
476 pub ty: Type<'a>,
477 /// Optional attributes that provide additional information about the parameter
478 pub annotations: Vec<VariableAnnotation>,
479}
480
481/// The signature of a function (parameters and return type).
482///
483/// A function signature defines the interface of a function, including what
484/// parameters it accepts and what type it returns. This is used for type
485/// checking and to ensure function calls are correct.
486///
487/// # Examples
488///
489/// ```rust
490/// use lamina_ir::{FunctionSignature, FunctionParameter, Type, PrimitiveType};
491///
492/// let signature = FunctionSignature {
493/// params: vec![
494/// FunctionParameter { name: "a", ty: Type::Primitive(PrimitiveType::I32), annotations: vec![] },
495/// FunctionParameter { name: "b", ty: Type::Primitive(PrimitiveType::I32), annotations: vec![] },
496/// ],
497/// return_type: Type::Primitive(PrimitiveType::I32),
498/// };
499/// ```
500#[derive(Debug, Clone, PartialEq, Eq, Hash)]
501pub struct FunctionSignature<'a> {
502 /// List of function parameters in order
503 pub params: Vec<FunctionParameter<'a>>,
504 /// The return type of the function (`Type::Void` if it doesn't return)
505 pub return_type: Type<'a>, // Type::Void if it doesn't return
506}
507
508/// A basic block within a function.
509///
510/// A basic block is a sequence of instructions that execute sequentially
511/// and end with a terminator instruction (branch, jump, or return). This
512/// structure supports control flow analysis and optimization.
513///
514/// # Invariants
515///
516/// - The last instruction MUST be a terminator (`Br`, `Jmp`, or `Ret`)
517/// - Instructions within a block execute in order
518/// - Control flow only changes at block boundaries
519///
520/// # Examples
521///
522/// ```rust
523/// use lamina_ir::{IRBuilder, Type, PrimitiveType, BinaryOp};
524/// use lamina_ir::builder::{var, i32};
525///
526/// let mut builder = IRBuilder::new();
527/// builder
528/// .function("example", Type::Void)
529/// .binary(BinaryOp::Add, "sum", PrimitiveType::I32, i32(10), i32(20))
530/// .print(var("sum"))
531/// .ret_void();
532///
533/// let module = builder.build();
534/// let func = &module.functions["example"];
535/// let entry_block = &func.basic_blocks["entry"];
536/// // entry_block.instructions contains: [Binary, Print, Ret]
537/// ```
538#[derive(Debug, Clone, PartialEq)]
539pub struct BasicBlock<'a> {
540 /// Instructions in this block (must end with a terminator)
541 pub instructions: Vec<Instruction<'a>>,
542}
543
544/// A complete function definition.
545///
546/// A function contains its signature, implementation (basic blocks), and
547/// metadata (annotations). Functions are the primary unit of code organization
548/// in the IR.
549///
550/// # Structure
551///
552/// - **Name**: Unique identifier for the function
553/// - **Signature**: Parameters and return type
554/// - **Basic Blocks**: The actual implementation
555/// - **Entry Block**: The first block to execute
556/// - **Annotations**: Metadata affecting behavior
557///
558/// # Examples
559///
560/// ```rust
561/// use lamina_ir::{IRBuilder, Type, PrimitiveType, BinaryOp};
562/// use lamina_ir::builder::{var, i32};
563///
564/// let mut builder = IRBuilder::new();
565/// builder
566/// .function("add", Type::Primitive(PrimitiveType::I32))
567/// .binary(BinaryOp::Add, "result", PrimitiveType::I32, i32(10), i32(20))
568/// .ret(Type::Primitive(PrimitiveType::I32), var("result"));
569///
570/// let module = builder.build();
571/// let func = &module.functions["add"];
572/// // func contains the complete function definition
573/// ```
574#[derive(Debug, Clone, PartialEq)]
575pub struct Function<'a> {
576 /// The function name (without the `@` prefix)
577 pub name: Identifier<'a>,
578 /// The function's signature (parameters and return type)
579 pub signature: FunctionSignature<'a>,
580 /// Annotations that affect function behavior
581 pub annotations: Vec<FunctionAnnotation>,
582 /// Basic blocks in this function, keyed by their label
583 ///
584 /// Using a HashMap enables efficient lookup by label name. The order
585 /// of blocks is implicitly defined by the control flow (branches and jumps).
586 pub basic_blocks: HashMap<Label<'a>, BasicBlock<'a>>,
587 /// Label of the first block to execute when the function is called
588 pub entry_block: Label<'a>,
589}
590
591// ---------------------------------------------------------------------------
592// IR Validation
593// ---------------------------------------------------------------------------
594
595impl<'a> Function<'a> {
596 /// Validate this function's IR for well-formedness.
597 ///
598 /// Checks performed:
599 /// - Entry block exists among the function's basic blocks.
600 /// - Every branch target (in `Br`, `Jmp`, `Switch`) names a block that
601 /// exists in this function.
602 /// - Every block ends with a terminator (`Br`, `Jmp`, or `Ret`).
603 /// - Return instructions carry a value when the return type is non-void,
604 /// and are bare when the return type is void.
605 /// - SSA variables are defined before they are used within each block
606 /// (does not perform cross-block dominance analysis).
607 ///
608 /// Returns `Ok(())` when the function is valid, or a list of diagnostic
609 /// strings describing every violation found.
610 pub fn validate(&self) -> Result<(), Vec<String>> {
611 let mut errors: Vec<String> = Vec::new();
612
613 if !self.basic_blocks.contains_key(self.entry_block) {
614 errors.push(format!(
615 "entry block '{}' does not exist in function '@{}'",
616 self.entry_block, self.name
617 ));
618 }
619
620 for (label, block) in &self.basic_blocks {
621 let last = block.instructions.last();
622 let has_terminator = last.map(|i| i.is_terminator()).unwrap_or(false);
623 if !has_terminator {
624 errors.push(format!(
625 "block '{}' in '@{}' has no terminator instruction",
626 label, self.name
627 ));
628 }
629
630 let mut defined: std::collections::HashSet<&str> =
631 self.signature.params.iter().map(|p| p.name).collect();
632
633 for instr in &block.instructions {
634 match instr {
635 Instruction::Br {
636 true_label,
637 false_label,
638 ..
639 } => {
640 if !self.basic_blocks.contains_key(true_label) {
641 errors.push(format!(
642 "branch true target '{}' in block '{}' of '@{}' not found",
643 true_label, label, self.name
644 ));
645 }
646 if !self.basic_blocks.contains_key(false_label) {
647 errors.push(format!(
648 "branch false target '{}' in block '{}' of '@{}' not found",
649 false_label, label, self.name
650 ));
651 }
652 }
653 Instruction::Jmp { target_label } => {
654 if !self.basic_blocks.contains_key(target_label) {
655 errors.push(format!(
656 "jump target '{}' in block '{}' of '@{}' not found",
657 target_label, label, self.name
658 ));
659 }
660 }
661 Instruction::Switch { default, cases, .. } => {
662 if !self.basic_blocks.contains_key(default) {
663 errors.push(format!(
664 "switch default target '{}' in block '{}' of '@{}' not found",
665 default, label, self.name
666 ));
667 }
668 for (_, case_label) in cases {
669 if !self.basic_blocks.contains_key(case_label) {
670 errors.push(format!(
671 "switch case target '{}' in block '{}' of '@{}' not found",
672 case_label, label, self.name
673 ));
674 }
675 }
676 }
677 Instruction::Ret { ty, value } => {
678 let ret_is_void = matches!(ty, Type::Void);
679 let sig_is_void = matches!(self.signature.return_type, Type::Void);
680 if ret_is_void != sig_is_void {
681 errors.push(format!(
682 "return in block '{}' of '@{}': return type '{}' does not match signature return type '{}'",
683 label, self.name, ty, self.signature.return_type
684 ));
685 }
686 if !ret_is_void && value.is_none() {
687 errors.push(format!(
688 "non-void return in block '{}' of '@{}' has no value",
689 label, self.name
690 ));
691 }
692 if ret_is_void && value.is_some() {
693 errors.push(format!(
694 "void return in block '{}' of '@{}' carries a value",
695 label, self.name
696 ));
697 }
698 }
699 _ => {}
700 }
701
702 // 5. SSA: check uses come after definitions (within-block only).
703 for used in instr.used_vars() {
704 if !defined.contains(used) {
705 errors.push(format!(
706 "use of undefined variable '%{}' in block '{}' of '@{}'",
707 used, label, self.name
708 ));
709 }
710 }
711 if let Some(def) = instr.defined_var() {
712 defined.insert(def);
713 }
714 }
715 }
716
717 if errors.is_empty() {
718 Ok(())
719 } else {
720 Err(errors)
721 }
722 }
723}
724
725// --- Display Implementations ---
726
727impl fmt::Display for FunctionAnnotation {
728 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
729 match self {
730 FunctionAnnotation::Inline => write!(f, "@inline"),
731 FunctionAnnotation::Export => write!(f, "@export"),
732 FunctionAnnotation::Extern => write!(f, "@extern"),
733 FunctionAnnotation::NoReturn => write!(f, "@noreturn"),
734 FunctionAnnotation::NoInline => write!(f, "@noinline"),
735 FunctionAnnotation::Cold => write!(f, "@cold"),
736 FunctionAnnotation::Hot => write!(f, "@hot"),
737 FunctionAnnotation::Pure => write!(f, "@pure"),
738 FunctionAnnotation::Const => write!(f, "@const"),
739 FunctionAnnotation::Internal => write!(f, "@internal"),
740 FunctionAnnotation::Private => write!(f, "@private"),
741 FunctionAnnotation::Hidden => write!(f, "@hidden"),
742 FunctionAnnotation::Protected => write!(f, "@protected"),
743 FunctionAnnotation::Weak => write!(f, "@weak"),
744 FunctionAnnotation::CCc => write!(f, "@cc_c"),
745 FunctionAnnotation::CCfast => write!(f, "@cc_fast"),
746 FunctionAnnotation::CCcold => write!(f, "@cc_cold"),
747 FunctionAnnotation::CCpreserveMost => write!(f, "@cc_preserve_most"),
748 FunctionAnnotation::CCpreserveAll => write!(f, "@cc_preserve_all"),
749 FunctionAnnotation::CCswift => write!(f, "@cc_swift"),
750 FunctionAnnotation::CCtail => write!(f, "@cc_tail"),
751 FunctionAnnotation::CallingConvention(cc) => write!(f, "@calling_convention({})", cc),
752 FunctionAnnotation::Section(section) => write!(f, "@section({})", section),
753 FunctionAnnotation::Align(alignment) => write!(f, "@align({})", alignment),
754 FunctionAnnotation::Unsafe => write!(f, "@unsafe"),
755 FunctionAnnotation::Deprecated(None) => write!(f, "@deprecated"),
756 FunctionAnnotation::Deprecated(Some(msg)) => write!(f, "@deprecated({})", msg),
757 }
758 }
759}
760
761impl fmt::Display for VariableAnnotation {
762 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
763 match self {
764 VariableAnnotation::NonNull => write!(f, "nonnull"),
765 VariableAnnotation::ReadOnly => write!(f, "readonly"),
766 VariableAnnotation::WriteOnly => write!(f, "writeonly"),
767 VariableAnnotation::Align(alignment) => write!(f, "align({})", alignment),
768 VariableAnnotation::Sensitive => write!(f, "sensitive"),
769 VariableAnnotation::Register(reg) => write!(f, "register({})", reg),
770 VariableAnnotation::Unused => write!(f, "unused"),
771 }
772 }
773}
774
775impl fmt::Display for FunctionParameter<'_> {
776 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
777 if self.annotations.is_empty() {
778 write!(f, "{} %{}", self.ty, self.name)
779 } else {
780 write!(f, "{} ", self.ty)?;
781 for (i, annotation) in self.annotations.iter().enumerate() {
782 if i > 0 {
783 write!(f, " ")?;
784 }
785 write!(f, "{}", annotation)?;
786 }
787 write!(f, " %{}", self.name)
788 }
789 }
790}
791
792impl fmt::Display for FunctionSignature<'_> {
793 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
794 write!(f, "(")?;
795 for (i, param) in self.params.iter().enumerate() {
796 write!(f, "{}", param)?;
797 if i < self.params.len() - 1 {
798 write!(f, ", ")?;
799 }
800 }
801 write!(f, ") -> {}", self.return_type)
802 }
803}
804
805impl fmt::Display for BasicBlock<'_> {
806 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
807 for instr in &self.instructions {
808 writeln!(f, " {}", instr)?;
809 }
810 Ok(())
811 }
812}
813
814impl fmt::Display for Function<'_> {
815 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
816 for annotation in &self.annotations {
817 writeln!(f, "{}", annotation)?;
818 }
819 writeln!(f, "fn @{}{} {{", self.name, self.signature)?;
820
821 // We need a consistent order for printing blocks. Let's try to print entry first.
822 if let Some(entry) = self.basic_blocks.get(self.entry_block) {
823 writeln!(f, "{}:", self.entry_block)?;
824 write!(f, "{}", entry)?;
825 }
826
827 // Print remaining blocks (order might not be source order, but good enough for display)
828 for (label, block) in &self.basic_blocks {
829 if *label != self.entry_block {
830 writeln!(f, "{}:", label)?;
831 write!(f, "{}", block)?;
832 }
833 }
834
835 writeln!(f, "}}")
836 }
837}
838
839#[cfg(test)]
840mod tests {
841 use super::*;
842 use crate::instruction::{AllocType, BinaryOp, Instruction};
843 use crate::types::{Literal, PrimitiveType, Type, Value};
844 use std::collections::HashMap;
845
846 #[test]
847 fn test_display_function_annotation() {
848 assert_eq!(format!("{}", FunctionAnnotation::Inline), "@inline");
849 assert_eq!(format!("{}", FunctionAnnotation::Export), "@export");
850 assert_eq!(format!("{}", FunctionAnnotation::NoReturn), "@noreturn");
851 assert_eq!(format!("{}", FunctionAnnotation::NoInline), "@noinline");
852 assert_eq!(format!("{}", FunctionAnnotation::Cold), "@cold");
853 }
854
855 #[test]
856 fn test_display_function_parameter() {
857 let param = FunctionParameter {
858 name: "count",
859 ty: Type::Primitive(PrimitiveType::I64),
860 annotations: vec![],
861 };
862 assert_eq!(format!("{}", param), "i64 %count");
863 }
864
865 #[test]
866 fn test_display_function_signature() {
867 // No params, void return
868 let sig1 = FunctionSignature {
869 params: vec![],
870 return_type: Type::Void,
871 };
872 assert_eq!(format!("{}", sig1), "() -> void");
873
874 // One param, primitive return
875 let sig2 = FunctionSignature {
876 params: vec![FunctionParameter {
877 name: "input",
878 ty: Type::Primitive(PrimitiveType::F32),
879 annotations: vec![],
880 }],
881 return_type: Type::Primitive(PrimitiveType::F32),
882 };
883 assert_eq!(format!("{}", sig2), "(f32 %input) -> f32");
884
885 // Multiple params, named return
886 let sig3 = FunctionSignature {
887 params: vec![
888 FunctionParameter {
889 name: "a",
890 ty: Type::Primitive(PrimitiveType::I32),
891 annotations: vec![],
892 },
893 FunctionParameter {
894 name: "b",
895 ty: Type::Named("MyType"),
896 annotations: vec![],
897 },
898 ],
899 return_type: Type::Named("ResultType"),
900 };
901 assert_eq!(format!("{}", sig3), "(i32 %a, @MyType %b) -> @ResultType");
902 }
903
904 #[test]
905 fn test_display_basic_block() {
906 let block = BasicBlock {
907 instructions: vec![
908 Instruction::Alloc {
909 result: "p",
910 alloc_type: AllocType::Stack,
911 allocated_ty: Type::Primitive(PrimitiveType::I32),
912 },
913 Instruction::Store {
914 ty: Type::Primitive(PrimitiveType::I32),
915 ptr: Value::Variable("p"),
916 value: Value::Constant(Literal::I32(10)),
917 },
918 Instruction::Jmp {
919 target_label: "next_block",
920 },
921 ],
922 };
923 // Expect leading spaces on ALL instruction lines due to writeln!
924 let expected_output = " %p = alloc.ptr.stack i32\n store.i32 %p, 10\n jmp next_block\n";
925 assert_eq!(format!("{}", block), expected_output);
926 }
927
928 #[test]
929 fn test_display_function() {
930 let sig = FunctionSignature {
931 params: vec![FunctionParameter {
932 name: "x",
933 ty: Type::Primitive(PrimitiveType::I32),
934 annotations: vec![],
935 }],
936 return_type: Type::Primitive(PrimitiveType::I32),
937 };
938
939 let mut blocks = HashMap::new();
940 blocks.insert(
941 "entry",
942 BasicBlock {
943 instructions: vec![
944 Instruction::Binary {
945 op: BinaryOp::Add,
946 result: "tmp",
947 ty: PrimitiveType::I32,
948 lhs: Value::Variable("x"),
949 rhs: Value::Constant(Literal::I32(1)),
950 },
951 Instruction::Ret {
952 ty: Type::Primitive(PrimitiveType::I32),
953 value: Some(Value::Variable("tmp")),
954 },
955 ],
956 },
957 );
958
959 let func = Function {
960 name: "increment",
961 signature: sig,
962 annotations: vec![FunctionAnnotation::Inline, FunctionAnnotation::Export],
963 basic_blocks: blocks,
964 entry_block: "entry",
965 };
966
967 // Match actual output - no indentation for instructions
968 let expected_output = "@inline\n@export\nfn @increment(i32 %x) -> i32 {\nentry:\n %tmp = add.i32 %x, 1\n ret.i32 %tmp\n}\n";
969
970 assert_eq!(format!("{}", func), expected_output);
971 }
972
973 #[test]
974 fn test_display_function_multiple_blocks() {
975 let sig = FunctionSignature {
976 params: vec![FunctionParameter {
977 name: "cond",
978 ty: Type::Primitive(PrimitiveType::Bool),
979 annotations: vec![],
980 }],
981 return_type: Type::Primitive(PrimitiveType::I32),
982 };
983
984 let mut blocks = HashMap::new();
985 blocks.insert(
986 "entry",
987 BasicBlock {
988 instructions: vec![Instruction::Br {
989 condition: Value::Variable("cond"),
990 true_label: "if_true",
991 false_label: "if_false",
992 }],
993 },
994 );
995 blocks.insert(
996 "if_true",
997 BasicBlock {
998 instructions: vec![Instruction::Ret {
999 ty: Type::Primitive(PrimitiveType::I32),
1000 value: Some(Value::Constant(Literal::I32(1))),
1001 }],
1002 },
1003 );
1004 blocks.insert(
1005 "if_false",
1006 BasicBlock {
1007 instructions: vec![Instruction::Ret {
1008 ty: Type::Primitive(PrimitiveType::I32),
1009 value: Some(Value::Constant(Literal::I32(0))),
1010 }],
1011 },
1012 );
1013
1014 let func = Function {
1015 name: "branch_test",
1016 signature: sig,
1017 annotations: vec![],
1018 basic_blocks: blocks,
1019 entry_block: "entry",
1020 };
1021
1022 // Match actual output - no indentation for instructions
1023 let output = format!("{}", func);
1024
1025 let expected_order1 = "fn @branch_test(bool %cond) -> i32 {\nentry:\n br %cond, if_true, if_false\nif_false:\n ret.i32 0\nif_true:\n ret.i32 1\n}\n";
1026
1027 let expected_order2 = "fn @branch_test(bool %cond) -> i32 {\n entry:\n br %cond, if_true, if_false\n if_true:\n ret.i32 1\n if_false:\n ret.i32 0\n}\n";
1028 let expected_order3 = "fn @branch_test(bool %cond) -> i32 {\nentry:\n br %cond, if_true, if_false\nif_true:\n ret.i32 1\nif_false:\n ret.i32 0\n}\n";
1029 let expected_order4 = "fn @branch_test(bool %cond) -> i32 {\n entry:\n br %cond, if_true, if_false\n if_true:\n ret.i32 1\n if_false:\n ret.i32 0\n}\n";
1030
1031 assert!(
1032 output == expected_order1
1033 || output == expected_order2
1034 || output == expected_order3
1035 || output == expected_order4,
1036 "Unexpected output:\n{}\nExpected one of:\n{}\nOR\n{}\n",
1037 output,
1038 expected_order1,
1039 expected_order2
1040 );
1041 }
1042
1043 // ---------------------------------------------------------------------------
1044 // validate() tests
1045 // ---------------------------------------------------------------------------
1046
1047 fn simple_func<'a>(
1048 params: Vec<FunctionParameter<'a>>,
1049 return_type: Type<'a>,
1050 blocks: HashMap<&'a str, BasicBlock<'a>>,
1051 entry: &'a str,
1052 ) -> Function<'a> {
1053 Function {
1054 name: "test",
1055 signature: FunctionSignature {
1056 params,
1057 return_type,
1058 },
1059 annotations: vec![],
1060 basic_blocks: blocks,
1061 entry_block: entry,
1062 }
1063 }
1064
1065 #[test]
1066 fn test_validate_valid_void_function() {
1067 let mut blocks = HashMap::new();
1068 blocks.insert(
1069 "entry",
1070 BasicBlock {
1071 instructions: vec![Instruction::Ret {
1072 ty: Type::Void,
1073 value: None,
1074 }],
1075 },
1076 );
1077 let f = simple_func(vec![], Type::Void, blocks, "entry");
1078 assert!(f.validate().is_ok());
1079 }
1080
1081 #[test]
1082 fn test_validate_missing_entry_block() {
1083 let f = simple_func(vec![], Type::Void, HashMap::new(), "entry");
1084 let errs = f.validate().unwrap_err();
1085 assert!(errs.iter().any(|e| e.contains("entry block")));
1086 }
1087
1088 #[test]
1089 fn test_validate_missing_terminator() {
1090 let mut blocks = HashMap::new();
1091 blocks.insert(
1092 "entry",
1093 BasicBlock {
1094 instructions: vec![Instruction::Binary {
1095 op: BinaryOp::Add,
1096 result: "x",
1097 ty: PrimitiveType::I32,
1098 lhs: Value::Constant(Literal::I32(1)),
1099 rhs: Value::Constant(Literal::I32(2)),
1100 }],
1101 },
1102 );
1103 let f = simple_func(vec![], Type::Void, blocks, "entry");
1104 let errs = f.validate().unwrap_err();
1105 assert!(errs.iter().any(|e| e.contains("no terminator")));
1106 }
1107
1108 #[test]
1109 fn test_validate_invalid_branch_target() {
1110 let mut blocks = HashMap::new();
1111 blocks.insert(
1112 "entry",
1113 BasicBlock {
1114 instructions: vec![Instruction::Jmp {
1115 target_label: "nonexistent",
1116 }],
1117 },
1118 );
1119 let f = simple_func(vec![], Type::Void, blocks, "entry");
1120 let errs = f.validate().unwrap_err();
1121 assert!(errs.iter().any(|e| e.contains("nonexistent")));
1122 }
1123
1124 #[test]
1125 fn test_validate_return_type_mismatch() {
1126 let mut blocks = HashMap::new();
1127 blocks.insert(
1128 "entry",
1129 BasicBlock {
1130 instructions: vec![Instruction::Ret {
1131 ty: Type::Void,
1132 value: None,
1133 }],
1134 },
1135 );
1136 let f = simple_func(vec![], Type::Primitive(PrimitiveType::I32), blocks, "entry");
1137 let errs = f.validate().unwrap_err();
1138 assert!(errs.iter().any(|e| e.contains("return type")));
1139 }
1140
1141 #[test]
1142 fn test_validate_undefined_variable() {
1143 let mut blocks = HashMap::new();
1144 blocks.insert(
1145 "entry",
1146 BasicBlock {
1147 instructions: vec![
1148 Instruction::Binary {
1149 op: BinaryOp::Add,
1150 result: "sum",
1151 ty: PrimitiveType::I32,
1152 lhs: Value::Variable("undefined_var"),
1153 rhs: Value::Constant(Literal::I32(1)),
1154 },
1155 Instruction::Ret {
1156 ty: Type::Void,
1157 value: None,
1158 },
1159 ],
1160 },
1161 );
1162 let f = simple_func(vec![], Type::Void, blocks, "entry");
1163 let errs = f.validate().unwrap_err();
1164 assert!(errs.iter().any(|e| e.contains("undefined_var")));
1165 }
1166
1167 #[test]
1168 fn test_validate_ssa_define_then_use() {
1169 let mut blocks = HashMap::new();
1170 blocks.insert(
1171 "entry",
1172 BasicBlock {
1173 instructions: vec![
1174 Instruction::Binary {
1175 op: BinaryOp::Add,
1176 result: "sum",
1177 ty: PrimitiveType::I32,
1178 lhs: Value::Constant(Literal::I32(1)),
1179 rhs: Value::Constant(Literal::I32(2)),
1180 },
1181 Instruction::Ret {
1182 ty: Type::Primitive(PrimitiveType::I32),
1183 value: Some(Value::Variable("sum")),
1184 },
1185 ],
1186 },
1187 );
1188 let f = simple_func(vec![], Type::Primitive(PrimitiveType::I32), blocks, "entry");
1189 assert!(f.validate().is_ok());
1190 }
1191}