gruel_cfg/
inst.rs

1//! CFG instruction definitions.
2//!
3//! Unlike AIR, the CFG has explicit basic blocks and terminators.
4//! Control flow only happens at block boundaries via terminators.
5//!
6//! # Place Expressions (ADR-0030)
7//!
8//! Memory locations are represented using [`Place`], which consists of:
9//! - A base ([`PlaceBase`]): either a local variable slot or parameter slot
10//! - A list of projections ([`Projection`]): field accesses and array indices
11//!
12//! This design follows Rust MIR's proven approach and eliminates redundant
13//! Load instructions for nested access patterns like `arr[i].field`.
14
15use std::fmt;
16
17// Compile-time size assertions to prevent silent size growth during refactoring.
18// These limits are set slightly above current sizes to allow minor changes,
19// but will catch significant size regressions.
20//
21// Current sizes (as of 2025-12):
22// - CfgInst: 40 bytes (CfgInstData + Type + Span)
23// - CfgInstData: 24 bytes
24const _: () = assert!(std::mem::size_of::<CfgInst>() <= 48);
25const _: () = assert!(std::mem::size_of::<CfgInstData>() <= 32);
26
27use gruel_air::{EnumId, StructId, Type};
28use gruel_span::Span;
29use lasso::{Key, Spur};
30
31// ============================================================================
32// Place Expressions (ADR-0030)
33// ============================================================================
34
35/// A memory location that can be read from or written to.
36///
37/// A place represents a path to a memory location, consisting of a base
38/// (local variable or parameter) and zero or more projections (field access,
39/// array indexing).
40///
41/// # Examples
42///
43/// - `x` → `Place { base: Local(0), proj_start: 0, proj_len: 0 }`
44/// - `arr[i]` → `Place { base: Local(0), proj_start: 0, proj_len: 1 }` with `Index` projection
45/// - `point.x` → `Place { base: Local(0), proj_start: 0, proj_len: 1 }` with `Field` projection
46/// - `arr[i].x` → `Place { base: Local(0), proj_start: 0, proj_len: 2 }` with `Index` then `Field`
47#[derive(Debug, Clone, Copy, PartialEq, Eq)]
48pub struct Place {
49    /// The base of the place - either a local slot or parameter slot
50    pub base: PlaceBase,
51    /// Start index into Cfg's projections array
52    pub proj_start: u32,
53    /// Number of projections
54    pub proj_len: u32,
55}
56
57impl Place {
58    /// Create a place for a local variable with no projections.
59    #[inline]
60    pub const fn local(slot: u32) -> Self {
61        Self {
62            base: PlaceBase::Local(slot),
63            proj_start: 0,
64            proj_len: 0,
65        }
66    }
67
68    /// Create a place for a parameter with no projections.
69    #[inline]
70    pub const fn param(slot: u32) -> Self {
71        Self {
72            base: PlaceBase::Param(slot),
73            proj_start: 0,
74            proj_len: 0,
75        }
76    }
77
78    /// Returns true if this place has no projections (is just a variable).
79    #[inline]
80    pub const fn is_simple(&self) -> bool {
81        self.proj_len == 0
82    }
83
84    /// Returns the local slot if this is a simple local place with no projections.
85    #[inline]
86    pub const fn as_local(&self) -> Option<u32> {
87        if self.proj_len == 0 {
88            match self.base {
89                PlaceBase::Local(slot) => Some(slot),
90                PlaceBase::Param(_) => None,
91            }
92        } else {
93            None
94        }
95    }
96
97    /// Returns the param slot if this is a simple param place with no projections.
98    #[inline]
99    pub const fn as_param(&self) -> Option<u32> {
100        if self.proj_len == 0 {
101            match self.base {
102                PlaceBase::Param(slot) => Some(slot),
103                PlaceBase::Local(_) => None,
104            }
105        } else {
106            None
107        }
108    }
109}
110
111impl fmt::Display for Place {
112    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
113        match self.base {
114            PlaceBase::Local(slot) => write!(f, "${}", slot)?,
115            PlaceBase::Param(slot) => write!(f, "%{}", slot)?,
116        }
117        if self.proj_len > 0 {
118            write!(
119                f,
120                "[{}..{}]",
121                self.proj_start,
122                self.proj_start + self.proj_len
123            )?;
124        }
125        Ok(())
126    }
127}
128
129/// The base of a place - where the memory location starts.
130#[derive(Debug, Clone, Copy, PartialEq, Eq)]
131pub enum PlaceBase {
132    /// Local variable slot
133    Local(u32),
134    /// Parameter slot (for parameters, including inout)
135    Param(u32),
136}
137
138/// A projection applied to a place to reach a nested location.
139///
140/// Projections are stored in `Cfg::projections` and referenced by
141/// `Place::proj_start` and `Place::proj_len`.
142#[derive(Debug, Clone, Copy, PartialEq, Eq)]
143pub enum Projection {
144    /// Field access: `.field_name`
145    ///
146    /// The struct_id identifies the struct type, and field_index is the
147    /// 0-based index of the field in declaration order.
148    Field {
149        struct_id: StructId,
150        field_index: u32,
151    },
152    /// Array index: `[index]`
153    ///
154    /// The array_type is needed for bounds checking and element size calculation.
155    /// The index is a CfgValue that will be evaluated at runtime.
156    Index { array_type: Type, index: CfgValue },
157}
158
159/// A basic block identifier.
160#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
161pub struct BlockId(pub(crate) u32);
162
163impl BlockId {
164    /// Create a new block ID from a raw index.
165    #[inline]
166    pub const fn from_raw(index: u32) -> Self {
167        Self(index)
168    }
169
170    /// Get the raw index.
171    #[inline]
172    pub const fn as_u32(self) -> u32 {
173        self.0
174    }
175}
176
177impl fmt::Display for BlockId {
178    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
179        write!(f, "bb{}", self.0)
180    }
181}
182
183/// A reference to a value (instruction result) in the CFG.
184#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
185pub struct CfgValue(u32);
186
187impl CfgValue {
188    /// Create a new value reference from a raw index.
189    #[inline]
190    pub const fn from_raw(index: u32) -> Self {
191        Self(index)
192    }
193
194    /// Get the raw index.
195    #[inline]
196    pub const fn as_u32(self) -> u32 {
197        self.0
198    }
199}
200
201impl fmt::Display for CfgValue {
202    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
203        write!(f, "v{}", self.0)
204    }
205}
206
207/// A single CFG instruction with its metadata.
208#[derive(Debug, Clone)]
209pub struct CfgInst {
210    pub data: CfgInstData,
211    pub ty: Type,
212    pub span: Span,
213}
214
215/// Argument passing mode in CFG.
216#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
217pub enum CfgArgMode {
218    /// Normal pass-by-value argument
219    #[default]
220    Normal,
221    /// Inout argument - mutated in place
222    Inout,
223    /// Borrow argument - immutable borrow
224    Borrow,
225}
226
227impl From<gruel_air::AirArgMode> for CfgArgMode {
228    fn from(mode: gruel_air::AirArgMode) -> Self {
229        match mode {
230            gruel_air::AirArgMode::Normal => CfgArgMode::Normal,
231            gruel_air::AirArgMode::Inout => CfgArgMode::Inout,
232            gruel_air::AirArgMode::Borrow => CfgArgMode::Borrow,
233        }
234    }
235}
236
237/// An argument in a function call.
238#[derive(Debug, Clone, Copy)]
239pub struct CfgCallArg {
240    /// The argument value
241    pub value: CfgValue,
242    /// The passing mode for this argument
243    pub mode: CfgArgMode,
244}
245
246impl CfgCallArg {
247    /// Returns true if this argument is passed as inout (mutable by reference).
248    pub fn is_inout(&self) -> bool {
249        self.mode == CfgArgMode::Inout
250    }
251
252    /// Returns true if this argument is passed as borrow (immutable by reference).
253    pub fn is_borrow(&self) -> bool {
254        self.mode == CfgArgMode::Borrow
255    }
256
257    /// Returns true if this argument is passed by reference (either inout or borrow).
258    pub fn is_by_ref(&self) -> bool {
259        matches!(self.mode, CfgArgMode::Inout | CfgArgMode::Borrow)
260    }
261}
262
263/// CFG instruction data.
264///
265/// Unlike AIR, there are NO control flow instructions here.
266/// Control flow is handled entirely by terminators.
267#[derive(Debug, Clone)]
268pub enum CfgInstData {
269    /// Integer constant (typed)
270    Const(u64),
271
272    /// Floating-point constant, stored as f64 bits via `f64::to_bits()`.
273    FloatConst(u64),
274
275    /// Boolean constant
276    BoolConst(bool),
277
278    /// String constant (index into string table)
279    StringConst(u32),
280
281    /// Reference to a function parameter
282    Param {
283        index: u32,
284    },
285
286    /// Block parameter (like phi, but explicit)
287    /// Only valid at the start of a block
288    BlockParam {
289        index: u32,
290    },
291
292    // Binary arithmetic operations
293    Add(CfgValue, CfgValue),
294    Sub(CfgValue, CfgValue),
295    Mul(CfgValue, CfgValue),
296    Div(CfgValue, CfgValue),
297    Mod(CfgValue, CfgValue),
298
299    // Comparison operations (return bool)
300    Eq(CfgValue, CfgValue),
301    Ne(CfgValue, CfgValue),
302    Lt(CfgValue, CfgValue),
303    Gt(CfgValue, CfgValue),
304    Le(CfgValue, CfgValue),
305    Ge(CfgValue, CfgValue),
306
307    // Bitwise operations
308    BitAnd(CfgValue, CfgValue),
309    BitOr(CfgValue, CfgValue),
310    BitXor(CfgValue, CfgValue),
311    Shl(CfgValue, CfgValue),
312    Shr(CfgValue, CfgValue),
313
314    // Unary operations
315    Neg(CfgValue),
316    Not(CfgValue),
317    BitNot(CfgValue),
318
319    // Variable operations
320    /// Allocate local variable with initial value
321    Alloc {
322        slot: u32,
323        init: CfgValue,
324    },
325    /// Load value from local variable
326    Load {
327        slot: u32,
328    },
329    /// Store value to local variable
330    Store {
331        slot: u32,
332        value: CfgValue,
333    },
334    /// Store value to a parameter (for inout params)
335    ParamStore {
336        param_slot: u32,
337        value: CfgValue,
338    },
339
340    // Place operations (ADR-0030)
341    /// Read a value from a memory location.
342    ///
343    /// This unifies Load, IndexGet, and FieldGet into a single instruction
344    /// that can handle arbitrarily nested access patterns like `arr[i].field`.
345    PlaceRead {
346        place: Place,
347    },
348
349    /// Write a value to a memory location.
350    ///
351    /// This unifies Store, IndexSet, ParamIndexSet, FieldSet, and ParamFieldSet
352    /// into a single instruction that can handle nested writes.
353    PlaceWrite {
354        place: Place,
355        value: CfgValue,
356    },
357
358    // Function calls
359    /// Function call. Arguments are stored in the Cfg's call_args array.
360    /// Use `Cfg::get_call_args(args_start, args_len)` to retrieve them.
361    Call {
362        /// Function name (interned symbol)
363        name: Spur,
364        /// Start index into Cfg's call_args array
365        args_start: u32,
366        /// Number of arguments
367        args_len: u32,
368    },
369
370    /// Intrinsic call (e.g., @dbg). Arguments are stored in the Cfg's extra array.
371    /// Use `Cfg::get_extra(args_start, args_len)` to retrieve them.
372    Intrinsic {
373        /// Intrinsic name (interned symbol)
374        name: Spur,
375        /// Start index into Cfg's extra array
376        args_start: u32,
377        /// Number of arguments
378        args_len: u32,
379    },
380
381    // Struct operations
382    /// Struct initialization. Field values are stored in the Cfg's extra array.
383    /// Use `Cfg::get_extra(fields_start, fields_len)` to retrieve them.
384    StructInit {
385        struct_id: StructId,
386        /// Start index into Cfg's extra array
387        fields_start: u32,
388        /// Number of fields
389        fields_len: u32,
390    },
391    FieldSet {
392        slot: u32,
393        struct_id: StructId,
394        field_index: u32,
395        value: CfgValue,
396    },
397    /// Store a value to a struct field (for parameters, including inout)
398    ParamFieldSet {
399        /// The parameter's ABI slot (relative to params, not locals)
400        param_slot: u32,
401        /// Offset within the struct for nested field access
402        inner_offset: u32,
403        struct_id: StructId,
404        field_index: u32,
405        value: CfgValue,
406    },
407
408    // Array operations
409    /// Array initialization. Element values are stored in the Cfg's extra array.
410    /// Use `Cfg::get_extra(elements_start, elements_len)` to retrieve them.
411    /// The array type is stored in `CfgInst.ty`.
412    ArrayInit {
413        /// Start index into Cfg's extra array
414        elements_start: u32,
415        /// Number of elements
416        elements_len: u32,
417    },
418    /// Store a value to an array element.
419    IndexSet {
420        slot: u32,
421        /// The array type (for bounds checking and element size)
422        array_type: Type,
423        index: CfgValue,
424        value: CfgValue,
425    },
426    /// Store a value to an array element of an inout parameter
427    ParamIndexSet {
428        /// The parameter's ABI slot (relative to params, not locals)
429        param_slot: u32,
430        /// The array type (for bounds checking and element size)
431        array_type: Type,
432        /// Index expression
433        index: CfgValue,
434        /// Value to store
435        value: CfgValue,
436    },
437
438    // Enum operations
439    /// Create an enum variant (discriminant value) for unit-only enums.
440    EnumVariant {
441        enum_id: EnumId,
442        variant_index: u32,
443    },
444
445    /// Create a data enum variant with associated field values.
446    /// Used when the enum has at least one data variant.
447    /// Field values are stored in the Cfg's extra array.
448    EnumCreate {
449        enum_id: EnumId,
450        variant_index: u32,
451        /// Start index into Cfg's extra array for field CfgValues
452        fields_start: u32,
453        /// Number of field values
454        fields_len: u32,
455    },
456
457    /// Extract a field value from an enum variant's payload.
458    /// Used in data variant match arm bodies to bind pattern variables.
459    EnumPayloadGet {
460        /// The enum value to extract from
461        base: CfgValue,
462        /// The variant index (must match the arm's pattern)
463        variant_index: u32,
464        /// The field index within the variant
465        field_index: u32,
466    },
467
468    // Type conversion operations
469    /// Integer cast: convert between integer types with runtime range check.
470    /// Panics if the value cannot be represented in the target type.
471    /// The target type is stored in CfgInst.ty.
472    IntCast {
473        /// The value to cast
474        value: CfgValue,
475        /// The source type (for determining signedness and size)
476        from_ty: Type,
477    },
478
479    /// Float cast: convert between floating-point types (fptrunc/fpext).
480    /// The target type is stored in CfgInst.ty.
481    FloatCast {
482        /// The value to cast
483        value: CfgValue,
484        /// The source float type
485        from_ty: Type,
486    },
487
488    /// Integer to float conversion (sitofp/uitofp).
489    /// The target type is stored in CfgInst.ty.
490    IntToFloat {
491        /// The integer value to convert
492        value: CfgValue,
493        /// The source integer type (for determining signedness)
494        from_ty: Type,
495    },
496
497    /// Float to integer conversion (fptosi/fptoui) with runtime range check.
498    /// Panics if the value is NaN or out of range of the target integer type.
499    /// The target type is stored in CfgInst.ty.
500    FloatToInt {
501        /// The float value to convert
502        value: CfgValue,
503        /// The source float type
504        from_ty: Type,
505    },
506
507    // Drop/destructor operations
508    /// Drop a value, running its destructor if the type has one.
509    /// For trivially droppable types, this is a no-op that will be elided.
510    Drop {
511        value: CfgValue,
512    },
513
514    // Storage liveness operations (for drop elaboration and stack allocation)
515    /// Marks that a local slot becomes live (storage allocated).
516    /// The slot is now valid to write to.
517    StorageLive {
518        slot: u32,
519    },
520
521    /// Marks that a local slot becomes dead (storage can be deallocated).
522    /// The slot is now invalid to read from.
523    /// Drop elaboration inserts Drop before this if the type needs drop.
524    StorageDead {
525        slot: u32,
526    },
527}
528
529/// Block terminator - how control leaves a basic block.
530///
531/// Terminators are the ONLY place where control flow happens in the CFG.
532///
533/// Block arguments are stored in the CFG's `extra` array for efficiency.
534/// Use `Cfg::get_goto_args()`, `Cfg::get_branch_then_args()`, and
535/// `Cfg::get_branch_else_args()` to retrieve the arguments.
536#[derive(Debug, Clone, Copy)]
537pub enum Terminator {
538    /// Unconditional jump to another block.
539    /// Arguments are stored in Cfg's extra array.
540    Goto {
541        target: BlockId,
542        /// Start index into Cfg's extra array
543        args_start: u32,
544        /// Number of arguments
545        args_len: u32,
546    },
547
548    /// Conditional branch.
549    /// Arguments for each branch are stored in Cfg's extra array.
550    Branch {
551        cond: CfgValue,
552        then_block: BlockId,
553        /// Start index into Cfg's extra array for then branch args
554        then_args_start: u32,
555        /// Number of arguments for then branch
556        then_args_len: u32,
557        else_block: BlockId,
558        /// Start index into Cfg's extra array for else branch args
559        else_args_start: u32,
560        /// Number of arguments for else branch
561        else_args_len: u32,
562    },
563
564    /// Multi-way branch (switch/match).
565    /// Cases are stored in Cfg's switch_cases array.
566    Switch {
567        /// The value to switch on
568        scrutinee: CfgValue,
569        /// Start index into Cfg's switch_cases array
570        cases_start: u32,
571        /// Number of cases
572        cases_len: u32,
573        /// Default block (for wildcard pattern)
574        default: BlockId,
575    },
576
577    /// Return from function (None for unit-returning functions).
578    Return { value: Option<CfgValue> },
579
580    /// Unreachable - control never reaches here.
581    /// Used after diverging expressions.
582    Unreachable,
583
584    /// Placeholder for blocks under construction.
585    /// Should not exist in a valid CFG.
586    None,
587}
588
589/// A basic block in the CFG.
590#[derive(Debug, Clone)]
591pub struct BasicBlock {
592    /// Block identifier
593    pub id: BlockId,
594    /// Block parameters (receive values from predecessors)
595    pub params: Vec<(CfgValue, Type)>,
596    /// Instructions in this block (straight-line, no control flow)
597    pub insts: Vec<CfgValue>,
598    /// How this block exits
599    pub terminator: Terminator,
600    /// Predecessor blocks (filled in after construction)
601    pub preds: Vec<BlockId>,
602}
603
604impl BasicBlock {
605    /// Create a new empty basic block.
606    pub fn new(id: BlockId) -> Self {
607        Self {
608            id,
609            params: Vec::new(),
610            insts: Vec::new(),
611            terminator: Terminator::None,
612            preds: Vec::new(),
613        }
614    }
615}
616
617/// The complete CFG for a function.
618#[derive(Debug)]
619pub struct Cfg {
620    /// All basic blocks
621    blocks: Vec<BasicBlock>,
622    /// Entry block
623    pub entry: BlockId,
624    /// Return type
625    return_type: Type,
626    /// All instructions (values) - blocks reference these by CfgValue
627    values: Vec<CfgInst>,
628    /// Extra storage for variable-length CfgValue data (struct fields, array elements, intrinsic args,
629    /// and terminator block arguments). Instructions and terminators store (start, len) indices into this array.
630    extra: Vec<CfgValue>,
631    /// Extra storage for call arguments (CfgCallArg).
632    /// Call instructions store (start, len) indices into this array.
633    call_args: Vec<CfgCallArg>,
634    /// Extra storage for switch cases (value, target block pairs).
635    /// Switch terminators store (start, len) indices into this array.
636    switch_cases: Vec<(i64, BlockId)>,
637    /// Extra storage for place projections (ADR-0030).
638    /// Place instructions store (start, len) indices into this array.
639    projections: Vec<Projection>,
640    /// Number of local variable slots
641    num_locals: u32,
642    /// Number of parameter slots
643    num_params: u32,
644    /// Function name
645    fn_name: String,
646    /// Whether each parameter slot is inout (passed by reference)
647    param_modes: Vec<bool>,
648    /// Type of each parameter slot (parallel to param_modes).
649    /// Retained here so that backends can declare function signatures even when
650    /// DCE has removed unused `Param { index }` instructions from the body.
651    param_types: Vec<Type>,
652}
653
654impl Cfg {
655    /// Create a new CFG.
656    pub fn new(
657        return_type: Type,
658        num_locals: u32,
659        num_params: u32,
660        fn_name: String,
661        param_modes: Vec<bool>,
662        param_types: Vec<Type>,
663    ) -> Self {
664        Self {
665            blocks: Vec::new(),
666            entry: BlockId(0),
667            return_type,
668            values: Vec::new(),
669            extra: Vec::new(),
670            call_args: Vec::new(),
671            switch_cases: Vec::new(),
672            projections: Vec::new(),
673            num_locals,
674            num_params,
675            fn_name,
676            param_modes,
677            param_types,
678        }
679    }
680
681    /// Get the return type.
682    #[inline]
683    pub fn return_type(&self) -> Type {
684        self.return_type
685    }
686
687    /// Get the number of local variable slots.
688    #[inline]
689    pub fn num_locals(&self) -> u32 {
690        self.num_locals
691    }
692
693    /// Allocate a new temporary local slot for spilling computed values.
694    ///
695    /// This is used during CFG construction when a computed value (e.g., method
696    /// call result) needs to be accessed via a place expression. The value is
697    /// spilled to this temporary slot.
698    ///
699    /// Returns the slot number for the new local.
700    #[inline]
701    pub fn alloc_temp_local(&mut self) -> u32 {
702        let slot = self.num_locals;
703        self.num_locals += 1;
704        slot
705    }
706
707    /// Get the number of parameter slots.
708    #[inline]
709    pub fn num_params(&self) -> u32 {
710        self.num_params
711    }
712
713    /// Get the function name.
714    #[inline]
715    pub fn fn_name(&self) -> &str {
716        &self.fn_name
717    }
718
719    /// Get whether a parameter slot is inout.
720    #[inline]
721    pub fn is_param_inout(&self, slot: u32) -> bool {
722        self.param_modes
723            .get(slot as usize)
724            .copied()
725            .unwrap_or(false)
726    }
727
728    /// Get the parameter modes slice.
729    #[inline]
730    pub fn param_modes(&self) -> &[bool] {
731        &self.param_modes
732    }
733
734    /// Get the type of a parameter slot.
735    ///
736    /// Returns `None` if the slot index is out of range.
737    #[inline]
738    pub fn param_type(&self, slot: u32) -> Option<Type> {
739        self.param_types.get(slot as usize).copied()
740    }
741
742    /// Create a new basic block and return its ID.
743    pub fn new_block(&mut self) -> BlockId {
744        let id = BlockId(self.blocks.len() as u32);
745        self.blocks.push(BasicBlock::new(id));
746        id
747    }
748
749    /// Get a block by ID.
750    #[inline]
751    pub fn get_block(&self, id: BlockId) -> &BasicBlock {
752        &self.blocks[id.0 as usize]
753    }
754
755    /// Get a block mutably by ID.
756    #[inline]
757    pub fn get_block_mut(&mut self, id: BlockId) -> &mut BasicBlock {
758        &mut self.blocks[id.0 as usize]
759    }
760
761    /// Add an instruction and return its value reference.
762    pub fn add_inst(&mut self, inst: CfgInst) -> CfgValue {
763        let value = CfgValue::from_raw(self.values.len() as u32);
764        self.values.push(inst);
765        value
766    }
767
768    /// Get an instruction by value reference.
769    #[inline]
770    pub fn get_inst(&self, value: CfgValue) -> &CfgInst {
771        &self.values[value.0 as usize]
772    }
773
774    /// Get a mutable instruction by value reference.
775    #[inline]
776    pub fn get_inst_mut(&mut self, value: CfgValue) -> &mut CfgInst {
777        &mut self.values[value.0 as usize]
778    }
779
780    /// Get the total number of values (instructions) in the CFG.
781    #[inline]
782    pub fn value_count(&self) -> usize {
783        self.values.len()
784    }
785
786    /// Add values to the extra array and return (start, len).
787    ///
788    /// Used for StructInit fields, ArrayInit elements, and Intrinsic args.
789    pub fn push_extra(&mut self, values: impl IntoIterator<Item = CfgValue>) -> (u32, u32) {
790        let start = self.extra.len() as u32;
791        self.extra.extend(values);
792        let len = self.extra.len() as u32 - start;
793        (start, len)
794    }
795
796    /// Get a slice from the extra array.
797    #[inline]
798    pub fn get_extra(&self, start: u32, len: u32) -> &[CfgValue] {
799        &self.extra[start as usize..(start + len) as usize]
800    }
801
802    /// Add call arguments to the call_args array and return (start, len).
803    ///
804    /// Used for Call instruction arguments.
805    pub fn push_call_args(&mut self, args: impl IntoIterator<Item = CfgCallArg>) -> (u32, u32) {
806        let start = self.call_args.len() as u32;
807        self.call_args.extend(args);
808        let len = self.call_args.len() as u32 - start;
809        (start, len)
810    }
811
812    /// Get a slice from the call_args array.
813    #[inline]
814    pub fn get_call_args(&self, start: u32, len: u32) -> &[CfgCallArg] {
815        &self.call_args[start as usize..(start + len) as usize]
816    }
817
818    /// Add switch cases to the switch_cases array and return (start, len).
819    ///
820    /// Used for Switch terminator cases.
821    pub fn push_switch_cases(
822        &mut self,
823        cases: impl IntoIterator<Item = (i64, BlockId)>,
824    ) -> (u32, u32) {
825        let start = self.switch_cases.len() as u32;
826        self.switch_cases.extend(cases);
827        let len = self.switch_cases.len() as u32 - start;
828        (start, len)
829    }
830
831    /// Get a slice from the switch_cases array.
832    #[inline]
833    pub fn get_switch_cases(&self, start: u32, len: u32) -> &[(i64, BlockId)] {
834        &self.switch_cases[start as usize..(start + len) as usize]
835    }
836
837    /// Add projections to the projections array and return (start, len).
838    ///
839    /// Used for PlaceRead and PlaceWrite instructions (ADR-0030).
840    pub fn push_projections(&mut self, projs: impl IntoIterator<Item = Projection>) -> (u32, u32) {
841        let start = self.projections.len() as u32;
842        self.projections.extend(projs);
843        let len = self.projections.len() as u32 - start;
844        (start, len)
845    }
846
847    /// Get a slice from the projections array.
848    #[inline]
849    pub fn get_projections(&self, start: u32, len: u32) -> &[Projection] {
850        &self.projections[start as usize..(start + len) as usize]
851    }
852
853    /// Get projections for a place.
854    #[inline]
855    pub fn get_place_projections(&self, place: &Place) -> &[Projection] {
856        self.get_projections(place.proj_start, place.proj_len)
857    }
858
859    /// Create a place with the given base and projections.
860    ///
861    /// This adds the projections to the projections array and returns a Place
862    /// that references them.
863    pub fn make_place(
864        &mut self,
865        base: PlaceBase,
866        projs: impl IntoIterator<Item = Projection>,
867    ) -> Place {
868        let (proj_start, proj_len) = self.push_projections(projs);
869        Place {
870            base,
871            proj_start,
872            proj_len,
873        }
874    }
875
876    /// Get the block arguments from a Goto terminator.
877    ///
878    /// # Panics
879    ///
880    /// Panics if the terminator is not a Goto.
881    #[inline]
882    pub fn get_goto_args(&self, term: &Terminator) -> &[CfgValue] {
883        match term {
884            Terminator::Goto {
885                args_start,
886                args_len,
887                ..
888            } => self.get_extra(*args_start, *args_len),
889            _ => panic!("get_goto_args called on non-Goto terminator"),
890        }
891    }
892
893    /// Get the then branch arguments from a Branch terminator.
894    ///
895    /// # Panics
896    ///
897    /// Panics if the terminator is not a Branch.
898    #[inline]
899    pub fn get_branch_then_args(&self, term: &Terminator) -> &[CfgValue] {
900        match term {
901            Terminator::Branch {
902                then_args_start,
903                then_args_len,
904                ..
905            } => self.get_extra(*then_args_start, *then_args_len),
906            _ => panic!("get_branch_then_args called on non-Branch terminator"),
907        }
908    }
909
910    /// Get the else branch arguments from a Branch terminator.
911    ///
912    /// # Panics
913    ///
914    /// Panics if the terminator is not a Branch.
915    #[inline]
916    pub fn get_branch_else_args(&self, term: &Terminator) -> &[CfgValue] {
917        match term {
918            Terminator::Branch {
919                else_args_start,
920                else_args_len,
921                ..
922            } => self.get_extra(*else_args_start, *else_args_len),
923            _ => panic!("get_branch_else_args called on non-Branch terminator"),
924        }
925    }
926
927    /// Add an instruction to a block.
928    pub fn add_inst_to_block(&mut self, block: BlockId, inst: CfgInst) -> CfgValue {
929        let value = self.add_inst(inst);
930        self.blocks[block.0 as usize].insts.push(value);
931        value
932    }
933
934    /// Add a block parameter and return its value.
935    pub fn add_block_param(&mut self, block: BlockId, ty: Type) -> CfgValue {
936        let param_index = self.blocks[block.0 as usize].params.len() as u32;
937        let inst = CfgInst {
938            data: CfgInstData::BlockParam { index: param_index },
939            ty,
940            span: Span::new(0, 0),
941        };
942        let value = self.add_inst(inst);
943        self.blocks[block.0 as usize].params.push((value, ty));
944        value
945    }
946
947    /// Set the terminator for a block.
948    pub fn set_terminator(&mut self, block: BlockId, term: Terminator) {
949        self.blocks[block.0 as usize].terminator = term;
950    }
951
952    /// Get all blocks.
953    pub fn blocks(&self) -> &[BasicBlock] {
954        &self.blocks
955    }
956
957    /// Get the number of blocks.
958    #[inline]
959    pub fn block_count(&self) -> usize {
960        self.blocks.len()
961    }
962
963    /// Iterate over block IDs.
964    pub fn block_ids(&self) -> impl Iterator<Item = BlockId> {
965        (0..self.blocks.len() as u32).map(BlockId)
966    }
967
968    /// Compute predecessor lists for all blocks.
969    pub fn compute_predecessors(&mut self) {
970        // Clear existing predecessors
971        for block in &mut self.blocks {
972            block.preds.clear();
973        }
974
975        // Collect edges
976        let mut edges: Vec<(BlockId, BlockId)> = Vec::new();
977        for block in &self.blocks {
978            match &block.terminator {
979                Terminator::Goto { target, .. } => {
980                    edges.push((block.id, *target));
981                }
982                Terminator::Branch {
983                    then_block,
984                    else_block,
985                    ..
986                } => {
987                    edges.push((block.id, *then_block));
988                    edges.push((block.id, *else_block));
989                }
990                Terminator::Switch {
991                    cases_start,
992                    cases_len,
993                    default,
994                    ..
995                } => {
996                    for (_, target) in self.get_switch_cases(*cases_start, *cases_len) {
997                        edges.push((block.id, *target));
998                    }
999                    edges.push((block.id, *default));
1000                }
1001                Terminator::Return { .. } | Terminator::Unreachable | Terminator::None => {}
1002            }
1003        }
1004
1005        // Add predecessors
1006        for (from, to) in edges {
1007            self.blocks[to.0 as usize].preds.push(from);
1008        }
1009    }
1010}
1011
1012impl fmt::Display for Cfg {
1013    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1014        writeln!(
1015            f,
1016            "cfg {} (return_type: {}) {{",
1017            self.fn_name,
1018            self.return_type.name()
1019        )?;
1020        for block in &self.blocks {
1021            write!(f, "  {}:", block.id)?;
1022            if !block.params.is_empty() {
1023                write!(f, "(")?;
1024                for (i, (val, ty)) in block.params.iter().enumerate() {
1025                    if i > 0 {
1026                        write!(f, ", ")?;
1027                    }
1028                    write!(f, "{}: {}", val, ty.name())?;
1029                }
1030                write!(f, ")")?;
1031            }
1032            writeln!(f)?;
1033
1034            // Print predecessors
1035            if !block.preds.is_empty() {
1036                write!(f, "    ; preds: ")?;
1037                for (i, pred) in block.preds.iter().enumerate() {
1038                    if i > 0 {
1039                        write!(f, ", ")?;
1040                    }
1041                    write!(f, "{}", pred)?;
1042                }
1043                writeln!(f)?;
1044            }
1045
1046            // Print instructions
1047            for &val in &block.insts {
1048                let inst = self.get_inst(val);
1049                write!(f, "    {} : {} = ", val, inst.ty.name())?;
1050                self.fmt_inst_data(f, &inst.data)?;
1051                writeln!(f)?;
1052            }
1053
1054            // Print terminator
1055            write!(f, "    ")?;
1056            match &block.terminator {
1057                Terminator::Goto {
1058                    target,
1059                    args_start,
1060                    args_len,
1061                } => {
1062                    write!(f, "goto {}", target)?;
1063                    let args = self.get_extra(*args_start, *args_len);
1064                    if !args.is_empty() {
1065                        write!(f, "(")?;
1066                        for (i, arg) in args.iter().enumerate() {
1067                            if i > 0 {
1068                                write!(f, ", ")?;
1069                            }
1070                            write!(f, "{}", arg)?;
1071                        }
1072                        write!(f, ")")?;
1073                    }
1074                }
1075                Terminator::Branch {
1076                    cond,
1077                    then_block,
1078                    then_args_start,
1079                    then_args_len,
1080                    else_block,
1081                    else_args_start,
1082                    else_args_len,
1083                } => {
1084                    write!(f, "branch {}, {}", cond, then_block)?;
1085                    let then_args = self.get_extra(*then_args_start, *then_args_len);
1086                    if !then_args.is_empty() {
1087                        write!(f, "(")?;
1088                        for (i, arg) in then_args.iter().enumerate() {
1089                            if i > 0 {
1090                                write!(f, ", ")?;
1091                            }
1092                            write!(f, "{}", arg)?;
1093                        }
1094                        write!(f, ")")?;
1095                    }
1096                    write!(f, ", {}", else_block)?;
1097                    let else_args = self.get_extra(*else_args_start, *else_args_len);
1098                    if !else_args.is_empty() {
1099                        write!(f, "(")?;
1100                        for (i, arg) in else_args.iter().enumerate() {
1101                            if i > 0 {
1102                                write!(f, ", ")?;
1103                            }
1104                            write!(f, "{}", arg)?;
1105                        }
1106                        write!(f, ")")?;
1107                    }
1108                }
1109                Terminator::Switch {
1110                    scrutinee,
1111                    cases_start,
1112                    cases_len,
1113                    default,
1114                } => {
1115                    write!(f, "switch {} [", scrutinee)?;
1116                    let cases = self.get_switch_cases(*cases_start, *cases_len);
1117                    for (i, (val, target)) in cases.iter().enumerate() {
1118                        if i > 0 {
1119                            write!(f, ", ")?;
1120                        }
1121                        write!(f, "{} => {}", val, target)?;
1122                    }
1123                    write!(f, "], default: {}", default)?;
1124                }
1125                Terminator::Return { value } => {
1126                    if let Some(value) = value {
1127                        write!(f, "return {}", value)?;
1128                    } else {
1129                        write!(f, "return")?;
1130                    }
1131                }
1132                Terminator::Unreachable => {
1133                    write!(f, "unreachable")?;
1134                }
1135                Terminator::None => {
1136                    write!(f, "<no terminator>")?;
1137                }
1138            }
1139            writeln!(f)?;
1140            writeln!(f)?;
1141        }
1142        writeln!(f, "}}")
1143    }
1144}
1145
1146impl Cfg {
1147    fn fmt_inst_data(&self, f: &mut fmt::Formatter<'_>, data: &CfgInstData) -> fmt::Result {
1148        match data {
1149            CfgInstData::Const(v) => write!(f, "const {}", v),
1150            CfgInstData::FloatConst(bits) => write!(f, "const {}", f64::from_bits(*bits)),
1151            CfgInstData::BoolConst(v) => write!(f, "const {}", v),
1152            CfgInstData::StringConst(idx) => write!(f, "string_const @{}", idx),
1153            CfgInstData::Param { index } => write!(f, "param {}", index),
1154            CfgInstData::BlockParam { index } => write!(f, "block_param {}", index),
1155            CfgInstData::Add(lhs, rhs) => write!(f, "add {}, {}", lhs, rhs),
1156            CfgInstData::Sub(lhs, rhs) => write!(f, "sub {}, {}", lhs, rhs),
1157            CfgInstData::Mul(lhs, rhs) => write!(f, "mul {}, {}", lhs, rhs),
1158            CfgInstData::Div(lhs, rhs) => write!(f, "div {}, {}", lhs, rhs),
1159            CfgInstData::Mod(lhs, rhs) => write!(f, "mod {}, {}", lhs, rhs),
1160            CfgInstData::Eq(lhs, rhs) => write!(f, "eq {}, {}", lhs, rhs),
1161            CfgInstData::Ne(lhs, rhs) => write!(f, "ne {}, {}", lhs, rhs),
1162            CfgInstData::Lt(lhs, rhs) => write!(f, "lt {}, {}", lhs, rhs),
1163            CfgInstData::Gt(lhs, rhs) => write!(f, "gt {}, {}", lhs, rhs),
1164            CfgInstData::Le(lhs, rhs) => write!(f, "le {}, {}", lhs, rhs),
1165            CfgInstData::Ge(lhs, rhs) => write!(f, "ge {}, {}", lhs, rhs),
1166            CfgInstData::BitAnd(lhs, rhs) => write!(f, "bit_and {}, {}", lhs, rhs),
1167            CfgInstData::BitOr(lhs, rhs) => write!(f, "bit_or {}, {}", lhs, rhs),
1168            CfgInstData::BitXor(lhs, rhs) => write!(f, "bit_xor {}, {}", lhs, rhs),
1169            CfgInstData::Shl(lhs, rhs) => write!(f, "shl {}, {}", lhs, rhs),
1170            CfgInstData::Shr(lhs, rhs) => write!(f, "shr {}, {}", lhs, rhs),
1171            CfgInstData::Neg(v) => write!(f, "neg {}", v),
1172            CfgInstData::Not(v) => write!(f, "not {}", v),
1173            CfgInstData::BitNot(v) => write!(f, "bit_not {}", v),
1174            CfgInstData::Alloc { slot, init } => write!(f, "alloc ${} = {}", slot, init),
1175            CfgInstData::Load { slot } => write!(f, "load ${}", slot),
1176            CfgInstData::Store { slot, value } => write!(f, "store ${} = {}", slot, value),
1177            CfgInstData::ParamStore { param_slot, value } => {
1178                write!(f, "param_store %{} = {}", param_slot, value)
1179            }
1180            CfgInstData::PlaceRead { place } => {
1181                write!(f, "place_read ")?;
1182                self.fmt_place(f, place)
1183            }
1184            CfgInstData::PlaceWrite { place, value } => {
1185                write!(f, "place_write ")?;
1186                self.fmt_place(f, place)?;
1187                write!(f, " = {}", value)
1188            }
1189            CfgInstData::Call {
1190                name,
1191                args_start,
1192                args_len,
1193            } => {
1194                // Display symbol as @{id} since we don't have interner access here
1195                write!(f, "call @{}(", name.into_usize())?;
1196                let args = self.get_call_args(*args_start, *args_len);
1197                for (i, arg) in args.iter().enumerate() {
1198                    if i > 0 {
1199                        write!(f, ", ")?;
1200                    }
1201                    match arg.mode {
1202                        CfgArgMode::Inout => write!(f, "inout {}", arg.value)?,
1203                        CfgArgMode::Borrow => write!(f, "borrow {}", arg.value)?,
1204                        CfgArgMode::Normal => write!(f, "{}", arg.value)?,
1205                    }
1206                }
1207                write!(f, ")")
1208            }
1209            CfgInstData::Intrinsic {
1210                name,
1211                args_start,
1212                args_len,
1213            } => {
1214                // Display symbol as @{id} since we don't have interner access here
1215                write!(f, "intrinsic @{}(", name.into_usize())?;
1216                let args = self.get_extra(*args_start, *args_len);
1217                for (i, arg) in args.iter().enumerate() {
1218                    if i > 0 {
1219                        write!(f, ", ")?;
1220                    }
1221                    write!(f, "{}", arg)?;
1222                }
1223                write!(f, ")")
1224            }
1225            CfgInstData::StructInit {
1226                struct_id,
1227                fields_start,
1228                fields_len,
1229            } => {
1230                write!(f, "struct_init #{} {{", struct_id.0)?;
1231                let fields = self.get_extra(*fields_start, *fields_len);
1232                for (i, field) in fields.iter().enumerate() {
1233                    if i > 0 {
1234                        write!(f, ", ")?;
1235                    }
1236                    write!(f, "{}", field)?;
1237                }
1238                write!(f, "}}")
1239            }
1240            CfgInstData::FieldSet {
1241                slot,
1242                struct_id,
1243                field_index,
1244                value,
1245            } => {
1246                write!(
1247                    f,
1248                    "field_set ${}.#{}.{} = {}",
1249                    slot, struct_id.0, field_index, value
1250                )
1251            }
1252            CfgInstData::ParamFieldSet {
1253                param_slot,
1254                inner_offset,
1255                struct_id,
1256                field_index,
1257                value,
1258            } => {
1259                write!(
1260                    f,
1261                    "param_field_set %{}+{}.#{}.{} = {}",
1262                    param_slot, inner_offset, struct_id.0, field_index, value
1263                )
1264            }
1265            CfgInstData::ArrayInit {
1266                elements_start,
1267                elements_len,
1268            } => {
1269                write!(f, "array_init [")?;
1270                let elements = self.get_extra(*elements_start, *elements_len);
1271                for (i, elem) in elements.iter().enumerate() {
1272                    if i > 0 {
1273                        write!(f, ", ")?;
1274                    }
1275                    write!(f, "{}", elem)?;
1276                }
1277                write!(f, "]")
1278            }
1279            CfgInstData::IndexSet {
1280                slot,
1281                array_type,
1282                index,
1283                value,
1284            } => {
1285                write!(
1286                    f,
1287                    "index_set ${}({})[{}] = {}",
1288                    slot,
1289                    array_type.name(),
1290                    index,
1291                    value
1292                )
1293            }
1294            CfgInstData::ParamIndexSet {
1295                param_slot,
1296                array_type,
1297                index,
1298                value,
1299            } => {
1300                write!(
1301                    f,
1302                    "param_index_set %{}({})[{}] = {}",
1303                    param_slot,
1304                    array_type.name(),
1305                    index,
1306                    value
1307                )
1308            }
1309            CfgInstData::EnumVariant {
1310                enum_id,
1311                variant_index,
1312            } => {
1313                write!(f, "enum_variant #{}::{}", enum_id.0, variant_index)
1314            }
1315            CfgInstData::EnumCreate {
1316                enum_id,
1317                variant_index,
1318                fields_start,
1319                fields_len,
1320            } => {
1321                let fields = self.get_extra(*fields_start, *fields_len);
1322                let field_strs: Vec<String> = fields.iter().map(|v| format!("{}", v)).collect();
1323                write!(
1324                    f,
1325                    "enum_create #{}::{}({})",
1326                    enum_id.0,
1327                    variant_index,
1328                    field_strs.join(", ")
1329                )
1330            }
1331            CfgInstData::EnumPayloadGet {
1332                base,
1333                variant_index,
1334                field_index,
1335            } => {
1336                write!(
1337                    f,
1338                    "enum_payload_get {} variant={} field={}",
1339                    base, variant_index, field_index
1340                )
1341            }
1342            CfgInstData::IntCast { value, from_ty } => {
1343                write!(f, "intcast {} from {}", value, from_ty.name())
1344            }
1345            CfgInstData::FloatCast { value, from_ty } => {
1346                write!(f, "floatcast {} from {}", value, from_ty.name())
1347            }
1348            CfgInstData::IntToFloat { value, from_ty } => {
1349                write!(f, "int_to_float {} from {}", value, from_ty.name())
1350            }
1351            CfgInstData::FloatToInt { value, from_ty } => {
1352                write!(f, "float_to_int {} from {}", value, from_ty.name())
1353            }
1354            CfgInstData::Drop { value } => {
1355                write!(f, "drop {}", value)
1356            }
1357            CfgInstData::StorageLive { slot } => {
1358                write!(f, "storage_live ${}", slot)
1359            }
1360            CfgInstData::StorageDead { slot } => {
1361                write!(f, "storage_dead ${}", slot)
1362            }
1363        }
1364    }
1365
1366    /// Format a place for display, showing the base and projections.
1367    fn fmt_place(&self, f: &mut fmt::Formatter<'_>, place: &Place) -> fmt::Result {
1368        // Write the base
1369        match place.base {
1370            PlaceBase::Local(slot) => write!(f, "${}", slot)?,
1371            PlaceBase::Param(slot) => write!(f, "param%{}", slot)?,
1372        }
1373
1374        // Write the projections
1375        let projections = self.get_place_projections(place);
1376        for proj in projections {
1377            match proj {
1378                Projection::Field {
1379                    struct_id,
1380                    field_index,
1381                } => {
1382                    write!(f, ".#{}.{}", struct_id.0, field_index)?;
1383                }
1384                Projection::Index { array_type, index } => {
1385                    write!(f, "({})[{}]", array_type.name(), index)?;
1386                }
1387            }
1388        }
1389
1390        Ok(())
1391    }
1392}
1393
1394#[cfg(test)]
1395mod tests {
1396    use super::*;
1397
1398    #[test]
1399    fn test_block_id_size() {
1400        assert_eq!(std::mem::size_of::<BlockId>(), 4);
1401    }
1402
1403    #[test]
1404    fn test_cfg_value_size() {
1405        assert_eq!(std::mem::size_of::<CfgValue>(), 4);
1406    }
1407
1408    #[test]
1409    fn test_cfg_inst_size() {
1410        // Document actual sizes for future reference.
1411        // If this test fails, update the const assertions at the top of this file.
1412        let cfg_inst_size = std::mem::size_of::<CfgInst>();
1413        let cfg_inst_data_size = std::mem::size_of::<CfgInstData>();
1414
1415        // These assertions document the current sizes.
1416        // If the layout changes, update both these values and the const assertions.
1417        assert!(
1418            cfg_inst_size <= 48,
1419            "CfgInst grew beyond 48 bytes: {}",
1420            cfg_inst_size
1421        );
1422        assert!(
1423            cfg_inst_data_size <= 32,
1424            "CfgInstData grew beyond 32 bytes: {}",
1425            cfg_inst_data_size
1426        );
1427    }
1428
1429    #[test]
1430    fn test_terminator_size() {
1431        // Terminator should be a reasonable size (no heap allocations inside)
1432        // 32 bytes: 8 (CfgValue cond) + 4+4+4+4 (BlockId, start, len x2) + 4+4+4 (else) = 36, rounded to 40
1433        // Actually: Branch is the largest with cond(4) + then_block(4) + then_start(4) + then_len(4) + else_block(4) + else_start(4) + else_len(4) = 28 bytes + discriminant
1434        let size = std::mem::size_of::<Terminator>();
1435        assert!(size <= 40, "Terminator is {} bytes, expected <= 40", size);
1436    }
1437
1438    #[test]
1439    fn test_create_cfg() {
1440        let mut cfg = Cfg::new(Type::I32, 0, 0, "test".to_string(), vec![], vec![]);
1441        let entry = cfg.new_block();
1442        cfg.entry = entry;
1443
1444        let const_val = cfg.add_inst_to_block(
1445            entry,
1446            CfgInst {
1447                data: CfgInstData::Const(42),
1448                ty: Type::I32,
1449                span: Span::new(0, 2),
1450            },
1451        );
1452
1453        cfg.set_terminator(
1454            entry,
1455            Terminator::Return {
1456                value: Some(const_val),
1457            },
1458        );
1459
1460        assert_eq!(cfg.block_count(), 1);
1461    }
1462}
gruel_cfg/inst.rs

gruel_cfg/
inst.rs
