cranelift_codegen/ir/
dfg.rs

1//! Data flow graph tracking Instructions, Values, and blocks.
2
3use crate::entity::{self, PrimaryMap, SecondaryMap};
4use crate::ir;
5use crate::ir::builder::ReplaceBuilder;
6use crate::ir::dynamic_type::{DynamicTypeData, DynamicTypes};
7use crate::ir::instructions::{CallInfo, InstructionData};
8use crate::ir::pcc::Fact;
9use crate::ir::user_stack_maps::{UserStackMapEntry, UserStackMapEntryVec};
10use crate::ir::{
11    Block, BlockArg, BlockCall, ConstantData, ConstantPool, DynamicType, ExceptionTables,
12    ExtFuncData, FuncRef, Immediate, Inst, JumpTables, RelSourceLoc, SigRef, Signature, Type,
13    Value, ValueLabelAssignments, ValueList, ValueListPool, types,
14};
15use crate::packed_option::ReservedValue;
16use crate::write::write_operands;
17use core::fmt;
18use core::iter;
19use core::mem;
20use core::ops::{Index, IndexMut};
21use core::u16;
22
23use alloc::collections::BTreeMap;
24#[cfg(feature = "enable-serde")]
25use serde_derive::{Deserialize, Serialize};
26use smallvec::SmallVec;
27
28/// Storage for instructions within the DFG.
29#[derive(Clone, PartialEq, Hash)]
30#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
31pub struct Insts(PrimaryMap<Inst, InstructionData>);
32
33/// Allow immutable access to instructions via indexing.
34impl Index<Inst> for Insts {
35    type Output = InstructionData;
36
37    fn index(&self, inst: Inst) -> &InstructionData {
38        self.0.index(inst)
39    }
40}
41
42/// Allow mutable access to instructions via indexing.
43impl IndexMut<Inst> for Insts {
44    fn index_mut(&mut self, inst: Inst) -> &mut InstructionData {
45        self.0.index_mut(inst)
46    }
47}
48
49/// Storage for basic blocks within the DFG.
50#[derive(Clone, PartialEq, Hash)]
51#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
52pub struct Blocks(PrimaryMap<Block, BlockData>);
53
54impl Blocks {
55    /// Create a new basic block.
56    pub fn add(&mut self) -> Block {
57        self.0.push(BlockData::new())
58    }
59
60    /// Get the total number of basic blocks created in this function, whether they are
61    /// currently inserted in the layout or not.
62    ///
63    /// This is intended for use with `SecondaryMap::with_capacity`.
64    pub fn len(&self) -> usize {
65        self.0.len()
66    }
67
68    /// Reserves capacity for at least `additional` more elements to be
69    /// inserted.
70    pub fn reserve(&mut self, additional: usize) {
71        self.0.reserve(additional);
72    }
73
74    /// Returns `true` if the given block reference is valid.
75    pub fn is_valid(&self, block: Block) -> bool {
76        self.0.is_valid(block)
77    }
78
79    /// Iterate over all blocks, regardless whether a block is actually inserted
80    /// in the layout or not.
81    ///
82    /// Iterates in creation order, not layout order.
83    pub fn iter(&self) -> impl Iterator<Item = Block> {
84        self.0.keys()
85    }
86}
87
88impl Index<Block> for Blocks {
89    type Output = BlockData;
90
91    fn index(&self, block: Block) -> &BlockData {
92        &self.0[block]
93    }
94}
95
96impl IndexMut<Block> for Blocks {
97    fn index_mut(&mut self, block: Block) -> &mut BlockData {
98        &mut self.0[block]
99    }
100}
101
102/// A data flow graph defines all instructions and basic blocks in a function as well as
103/// the data flow dependencies between them. The DFG also tracks values which can be either
104/// instruction results or block parameters.
105///
106/// The layout of blocks in the function and of instructions in each block is recorded by the
107/// `Layout` data structure which forms the other half of the function representation.
108///
109#[derive(Clone, PartialEq, Hash)]
110#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
111pub struct DataFlowGraph {
112    /// Data about all of the instructions in the function, including opcodes and operands.
113    /// The instructions in this map are not in program order. That is tracked by `Layout`, along
114    /// with the block containing each instruction.
115    pub insts: Insts,
116
117    /// List of result values for each instruction.
118    ///
119    /// This map gets resized automatically by `make_inst()` so it is always in sync with the
120    /// primary `insts` map.
121    results: SecondaryMap<Inst, ValueList>,
122
123    /// User-defined stack maps.
124    user_stack_maps: alloc::collections::BTreeMap<Inst, UserStackMapEntryVec>,
125
126    /// basic blocks in the function and their parameters.
127    ///
128    /// This map is not in program order. That is handled by `Layout`, and so is the sequence of
129    /// instructions contained in each block.
130    pub blocks: Blocks,
131
132    /// Dynamic types created.
133    pub dynamic_types: DynamicTypes,
134
135    /// Memory pool of value lists.
136    ///
137    /// The `ValueList` references into this pool appear in many places:
138    ///
139    /// - Instructions in `insts` that don't have room for their entire argument list inline.
140    /// - Instruction result values in `results`.
141    /// - block parameters in `blocks`.
142    pub value_lists: ValueListPool,
143
144    /// Primary value table with entries for all values.
145    values: PrimaryMap<Value, ValueDataPacked>,
146
147    /// Facts: proof-carrying-code assertions about values.
148    pub facts: SecondaryMap<Value, Option<Fact>>,
149
150    /// Function signature table. These signatures are referenced by indirect call instructions as
151    /// well as the external function references.
152    pub signatures: PrimaryMap<SigRef, Signature>,
153
154    /// External function references. These are functions that can be called directly.
155    pub ext_funcs: PrimaryMap<FuncRef, ExtFuncData>,
156
157    /// Saves Value labels.
158    pub values_labels: Option<BTreeMap<Value, ValueLabelAssignments>>,
159
160    /// Constants used within the function.
161    pub constants: ConstantPool,
162
163    /// Stores large immediates that otherwise will not fit on InstructionData.
164    pub immediates: PrimaryMap<Immediate, ConstantData>,
165
166    /// Jump tables used in this function.
167    pub jump_tables: JumpTables,
168
169    /// Exception tables used in this function.
170    pub exception_tables: ExceptionTables,
171}
172
173impl DataFlowGraph {
174    /// Create a new empty `DataFlowGraph`.
175    pub fn new() -> Self {
176        Self {
177            insts: Insts(PrimaryMap::new()),
178            results: SecondaryMap::new(),
179            user_stack_maps: alloc::collections::BTreeMap::new(),
180            blocks: Blocks(PrimaryMap::new()),
181            dynamic_types: DynamicTypes::new(),
182            value_lists: ValueListPool::new(),
183            values: PrimaryMap::new(),
184            facts: SecondaryMap::new(),
185            signatures: PrimaryMap::new(),
186            ext_funcs: PrimaryMap::new(),
187            values_labels: None,
188            constants: ConstantPool::new(),
189            immediates: PrimaryMap::new(),
190            jump_tables: JumpTables::new(),
191            exception_tables: ExceptionTables::new(),
192        }
193    }
194
195    /// Clear everything.
196    pub fn clear(&mut self) {
197        self.insts.0.clear();
198        self.results.clear();
199        self.user_stack_maps.clear();
200        self.blocks.0.clear();
201        self.dynamic_types.clear();
202        self.value_lists.clear();
203        self.values.clear();
204        self.signatures.clear();
205        self.ext_funcs.clear();
206        self.values_labels = None;
207        self.constants.clear();
208        self.immediates.clear();
209        self.jump_tables.clear();
210        self.facts.clear();
211    }
212
213    /// Get the total number of instructions created in this function, whether they are currently
214    /// inserted in the layout or not.
215    ///
216    /// This is intended for use with `SecondaryMap::with_capacity`.
217    pub fn num_insts(&self) -> usize {
218        self.insts.0.len()
219    }
220
221    /// Returns `true` if the given instruction reference is valid.
222    pub fn inst_is_valid(&self, inst: Inst) -> bool {
223        self.insts.0.is_valid(inst)
224    }
225
226    /// Get the total number of basic blocks created in this function, whether they are
227    /// currently inserted in the layout or not.
228    ///
229    /// This is intended for use with `SecondaryMap::with_capacity`.
230    pub fn num_blocks(&self) -> usize {
231        self.blocks.len()
232    }
233
234    /// Returns `true` if the given block reference is valid.
235    pub fn block_is_valid(&self, block: Block) -> bool {
236        self.blocks.is_valid(block)
237    }
238
239    /// Make a BlockCall, bundling together the block and its arguments.
240    pub fn block_call<'a>(
241        &mut self,
242        block: Block,
243        args: impl IntoIterator<Item = &'a BlockArg>,
244    ) -> BlockCall {
245        BlockCall::new(block, args.into_iter().copied(), &mut self.value_lists)
246    }
247
248    /// Get the total number of values.
249    pub fn num_values(&self) -> usize {
250        self.values.len()
251    }
252
253    /// Get an iterator over all values and their definitions.
254    pub fn values_and_defs(&self) -> impl Iterator<Item = (Value, ValueDef)> + '_ {
255        self.values().map(|value| (value, self.value_def(value)))
256    }
257
258    /// Starts collection of debug information.
259    pub fn collect_debug_info(&mut self) {
260        if self.values_labels.is_none() {
261            self.values_labels = Some(Default::default());
262        }
263    }
264
265    /// Inserts a `ValueLabelAssignments::Alias` for `to_alias` if debug info
266    /// collection is enabled.
267    pub fn add_value_label_alias(&mut self, to_alias: Value, from: RelSourceLoc, value: Value) {
268        if let Some(values_labels) = self.values_labels.as_mut() {
269            values_labels.insert(to_alias, ir::ValueLabelAssignments::Alias { from, value });
270        }
271    }
272}
273
274/// Resolve value aliases.
275///
276/// Find the original SSA value that `value` aliases, or None if an
277/// alias cycle is detected.
278fn maybe_resolve_aliases(
279    values: &PrimaryMap<Value, ValueDataPacked>,
280    value: Value,
281) -> Option<Value> {
282    let mut v = value;
283
284    // Note that values may be empty here.
285    for _ in 0..=values.len() {
286        if let ValueData::Alias { original, .. } = ValueData::from(values[v]) {
287            v = original;
288        } else {
289            return Some(v);
290        }
291    }
292
293    None
294}
295
296/// Resolve value aliases.
297///
298/// Find the original SSA value that `value` aliases.
299fn resolve_aliases(values: &PrimaryMap<Value, ValueDataPacked>, value: Value) -> Value {
300    if let Some(v) = maybe_resolve_aliases(values, value) {
301        v
302    } else {
303        panic!("Value alias loop detected for {value}");
304    }
305}
306
307/// Iterator over all Values in a DFG.
308pub struct Values<'a> {
309    inner: entity::Iter<'a, Value, ValueDataPacked>,
310}
311
312/// Check for non-values.
313fn valid_valuedata(data: ValueDataPacked) -> bool {
314    let data = ValueData::from(data);
315    if let ValueData::Alias {
316        ty: types::INVALID,
317        original,
318    } = data
319    {
320        if original == Value::reserved_value() {
321            return false;
322        }
323    }
324    true
325}
326
327impl<'a> Iterator for Values<'a> {
328    type Item = Value;
329
330    fn next(&mut self) -> Option<Self::Item> {
331        self.inner
332            .by_ref()
333            .find(|kv| valid_valuedata(*kv.1))
334            .map(|kv| kv.0)
335    }
336}
337
338/// Handling values.
339///
340/// Values are either block parameters or instruction results.
341impl DataFlowGraph {
342    /// Allocate an extended value entry.
343    fn make_value(&mut self, data: ValueData) -> Value {
344        self.values.push(data.into())
345    }
346
347    /// The number of values defined in this DFG.
348    pub fn len_values(&self) -> usize {
349        self.values.len()
350    }
351
352    /// Get an iterator over all values.
353    pub fn values<'a>(&'a self) -> Values<'a> {
354        Values {
355            inner: self.values.iter(),
356        }
357    }
358
359    /// Check if a value reference is valid.
360    pub fn value_is_valid(&self, v: Value) -> bool {
361        self.values.is_valid(v)
362    }
363
364    /// Check whether a value is valid and not an alias.
365    pub fn value_is_real(&self, value: Value) -> bool {
366        // Deleted or unused values are also stored as aliases so this excludes
367        // those as well.
368        self.value_is_valid(value) && !matches!(self.values[value].into(), ValueData::Alias { .. })
369    }
370
371    /// Get the type of a value.
372    pub fn value_type(&self, v: Value) -> Type {
373        self.values[v].ty()
374    }
375
376    /// Get the definition of a value.
377    ///
378    /// This is either the instruction that defined it or the Block that has the value as an
379    /// parameter.
380    pub fn value_def(&self, v: Value) -> ValueDef {
381        match ValueData::from(self.values[v]) {
382            ValueData::Inst { inst, num, .. } => ValueDef::Result(inst, num as usize),
383            ValueData::Param { block, num, .. } => ValueDef::Param(block, num as usize),
384            ValueData::Alias { original, .. } => {
385                // Make sure we only recurse one level. `resolve_aliases` has safeguards to
386                // detect alias loops without overrunning the stack.
387                self.value_def(self.resolve_aliases(original))
388            }
389            ValueData::Union { x, y, .. } => ValueDef::Union(x, y),
390        }
391    }
392
393    /// Determine if `v` is an attached instruction result / block parameter.
394    ///
395    /// An attached value can't be attached to something else without first being detached.
396    ///
397    /// Value aliases are not considered to be attached to anything. Use `resolve_aliases()` to
398    /// determine if the original aliased value is attached.
399    pub fn value_is_attached(&self, v: Value) -> bool {
400        use self::ValueData::*;
401        match ValueData::from(self.values[v]) {
402            Inst { inst, num, .. } => Some(&v) == self.inst_results(inst).get(num as usize),
403            Param { block, num, .. } => Some(&v) == self.block_params(block).get(num as usize),
404            Alias { .. } => false,
405            Union { .. } => false,
406        }
407    }
408
409    /// Resolve value aliases.
410    ///
411    /// Find the original SSA value that `value` aliases.
412    pub fn resolve_aliases(&self, value: Value) -> Value {
413        resolve_aliases(&self.values, value)
414    }
415
416    /// Replace all uses of value aliases with their resolved values, and delete
417    /// the aliases.
418    pub fn resolve_all_aliases(&mut self) {
419        let invalid_value = ValueDataPacked::from(ValueData::Alias {
420            ty: types::INVALID,
421            original: Value::reserved_value(),
422        });
423
424        // Rewrite each chain of aliases. Update every alias along the chain
425        // into an alias directly to the final value. Due to updating every
426        // alias that it looks at, this loop runs in time linear in the number
427        // of values.
428        for mut src in self.values.keys() {
429            let value_data = self.values[src];
430            if value_data == invalid_value {
431                continue;
432            }
433            if let ValueData::Alias { mut original, .. } = value_data.into() {
434                // We don't use the type after this, we just need some place to
435                // store the resolved aliases temporarily.
436                let resolved = ValueDataPacked::from(ValueData::Alias {
437                    ty: types::INVALID,
438                    original: resolve_aliases(&self.values, original),
439                });
440                // Walk the chain again, splatting the new alias everywhere.
441                // resolve_aliases panics if there's an alias cycle, so we don't
442                // need to guard against cycles here.
443                loop {
444                    self.values[src] = resolved;
445                    src = original;
446                    if let ValueData::Alias { original: next, .. } = self.values[src].into() {
447                        original = next;
448                    } else {
449                        break;
450                    }
451                }
452            }
453        }
454
455        // Now aliases don't point to other aliases, so we can replace any use
456        // of an alias with the final value in constant time.
457
458        // Rewrite InstructionData in `self.insts`.
459        for inst in self.insts.0.values_mut() {
460            inst.map_values(
461                &mut self.value_lists,
462                &mut self.jump_tables,
463                &mut self.exception_tables,
464                |arg| {
465                    if let ValueData::Alias { original, .. } = self.values[arg].into() {
466                        original
467                    } else {
468                        arg
469                    }
470                },
471            );
472        }
473
474        // - `results` and block-params in `blocks` are not aliases, by
475        //   definition.
476        // - `dynamic_types` has no values.
477        // - `value_lists` can only be accessed via references from elsewhere.
478        // - `values` only has value references in aliases (which we've
479        //   removed), and unions (but the egraph pass ensures there are no
480        //   aliases before creating unions).
481
482        // Merge `facts` from any alias onto the aliased value. Note that if
483        // there was a chain of aliases, at this point every alias that was in
484        // the chain points to the same final value, so their facts will all be
485        // merged together.
486        for value in self.facts.keys() {
487            if let ValueData::Alias { original, .. } = self.values[value].into() {
488                if let Some(new_fact) = self.facts[value].take() {
489                    match &mut self.facts[original] {
490                        Some(old_fact) => *old_fact = Fact::intersect(old_fact, &new_fact),
491                        old_fact => *old_fact = Some(new_fact),
492                    }
493                }
494            }
495        }
496
497        // - `signatures` and `ext_funcs` have no values.
498
499        if let Some(values_labels) = &mut self.values_labels {
500            // Debug info is best-effort. If any is attached to value aliases,
501            // just discard it.
502            values_labels.retain(|&k, _| !matches!(self.values[k].into(), ValueData::Alias { .. }));
503
504            // If debug-info says a value should have the same labels as another
505            // value, then make sure that target is not a value alias.
506            for value_label in values_labels.values_mut() {
507                if let ValueLabelAssignments::Alias { value, .. } = value_label {
508                    if let ValueData::Alias { original, .. } = self.values[*value].into() {
509                        *value = original;
510                    }
511                }
512            }
513        }
514
515        // - `constants` and `immediates` have no values.
516        // - `jump_tables` is updated together with instruction-data above.
517
518        // Delete all aliases now that there are no uses left.
519        for value in self.values.values_mut() {
520            if let ValueData::Alias { .. } = ValueData::from(*value) {
521                *value = invalid_value;
522            }
523        }
524    }
525
526    /// Turn a value into an alias of another.
527    ///
528    /// Change the `dest` value to behave as an alias of `src`. This means that all uses of `dest`
529    /// will behave as if they used that value `src`.
530    ///
531    /// The `dest` value can't be attached to an instruction or block.
532    pub fn change_to_alias(&mut self, dest: Value, src: Value) {
533        debug_assert!(!self.value_is_attached(dest));
534        // Try to create short alias chains by finding the original source value.
535        // This also avoids the creation of loops.
536        let original = self.resolve_aliases(src);
537        debug_assert_ne!(
538            dest, original,
539            "Aliasing {dest} to {src} would create a loop"
540        );
541        let ty = self.value_type(original);
542        debug_assert_eq!(
543            self.value_type(dest),
544            ty,
545            "Aliasing {} to {} would change its type {} to {}",
546            dest,
547            src,
548            self.value_type(dest),
549            ty
550        );
551        debug_assert_ne!(ty, types::INVALID);
552
553        self.values[dest] = ValueData::Alias { ty, original }.into();
554    }
555
556    /// Replace the results of one instruction with aliases to the results of another.
557    ///
558    /// Change all the results of `dest_inst` to behave as aliases of
559    /// corresponding results of `src_inst`, as if calling change_to_alias for
560    /// each.
561    ///
562    /// After calling this instruction, `dest_inst` will have had its results
563    /// cleared, so it likely needs to be removed from the graph.
564    ///
565    pub fn replace_with_aliases(&mut self, dest_inst: Inst, original_inst: Inst) {
566        debug_assert_ne!(
567            dest_inst, original_inst,
568            "Replacing {dest_inst} with itself would create a loop"
569        );
570
571        let dest_results = self.results[dest_inst].as_slice(&self.value_lists);
572        let original_results = self.results[original_inst].as_slice(&self.value_lists);
573
574        debug_assert_eq!(
575            dest_results.len(),
576            original_results.len(),
577            "Replacing {dest_inst} with {original_inst} would produce a different number of results."
578        );
579
580        for (&dest, &original) in dest_results.iter().zip(original_results) {
581            let ty = self.value_type(original);
582            debug_assert_eq!(
583                self.value_type(dest),
584                ty,
585                "Aliasing {} to {} would change its type {} to {}",
586                dest,
587                original,
588                self.value_type(dest),
589                ty
590            );
591            debug_assert_ne!(ty, types::INVALID);
592
593            self.values[dest] = ValueData::Alias { ty, original }.into();
594        }
595
596        self.clear_results(dest_inst);
597    }
598
599    /// Get the stack map entries associated with the given instruction.
600    pub fn user_stack_map_entries(&self, inst: Inst) -> Option<&[UserStackMapEntry]> {
601        self.user_stack_maps.get(&inst).map(|es| &**es)
602    }
603
604    /// Append a new stack map entry for the given call instruction.
605    ///
606    /// # Panics
607    ///
608    /// Panics if the given instruction is not a (non-tail) call instruction.
609    pub fn append_user_stack_map_entry(&mut self, inst: Inst, entry: UserStackMapEntry) {
610        let opcode = self.insts[inst].opcode();
611        assert!(opcode.is_safepoint());
612        self.user_stack_maps.entry(inst).or_default().push(entry);
613    }
614
615    /// Append multiple stack map entries for the given call instruction.
616    ///
617    /// # Panics
618    ///
619    /// Panics if the given instruction is not a (non-tail) call instruction.
620    pub fn append_user_stack_map_entries(
621        &mut self,
622        inst: Inst,
623        entries: impl IntoIterator<Item = UserStackMapEntry>,
624    ) {
625        for entry in entries {
626            self.append_user_stack_map_entry(inst, entry);
627        }
628    }
629
630    /// Take the stack map entries for a given instruction, leaving the
631    /// instruction without stack maps.
632    pub(crate) fn take_user_stack_map_entries(
633        &mut self,
634        inst: Inst,
635    ) -> Option<UserStackMapEntryVec> {
636        self.user_stack_maps.remove(&inst)
637    }
638}
639
640/// Where did a value come from?
641#[derive(Clone, Copy, Debug, PartialEq, Eq)]
642pub enum ValueDef {
643    /// Value is the n'th result of an instruction.
644    Result(Inst, usize),
645    /// Value is the n'th parameter to a block.
646    Param(Block, usize),
647    /// Value is a union of two other values.
648    Union(Value, Value),
649}
650
651impl ValueDef {
652    /// Unwrap the instruction where the value was defined, or panic.
653    pub fn unwrap_inst(&self) -> Inst {
654        self.inst().expect("Value is not an instruction result")
655    }
656
657    /// Get the instruction where the value was defined, if any.
658    pub fn inst(&self) -> Option<Inst> {
659        match *self {
660            Self::Result(inst, _) => Some(inst),
661            _ => None,
662        }
663    }
664
665    /// Unwrap the block there the parameter is defined, or panic.
666    pub fn unwrap_block(&self) -> Block {
667        match *self {
668            Self::Param(block, _) => block,
669            _ => panic!("Value is not a block parameter"),
670        }
671    }
672
673    /// Get the number component of this definition.
674    ///
675    /// When multiple values are defined at the same program point, this indicates the index of
676    /// this value.
677    pub fn num(self) -> usize {
678        match self {
679            Self::Result(_, n) | Self::Param(_, n) => n,
680            Self::Union(_, _) => 0,
681        }
682    }
683}
684
685/// Internal table storage for extended values.
686#[derive(Clone, Debug, PartialEq, Hash)]
687#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
688enum ValueData {
689    /// Value is defined by an instruction.
690    Inst { ty: Type, num: u16, inst: Inst },
691
692    /// Value is a block parameter.
693    Param { ty: Type, num: u16, block: Block },
694
695    /// Value is an alias of another value.
696    /// An alias value can't be linked as an instruction result or block parameter. It is used as a
697    /// placeholder when the original instruction or block has been rewritten or modified.
698    Alias { ty: Type, original: Value },
699
700    /// Union is a "fork" in representation: the value can be
701    /// represented as either of the values named here. This is used
702    /// for aegraph (acyclic egraph) representation in the DFG.
703    Union { ty: Type, x: Value, y: Value },
704}
705
706/// Bit-packed version of ValueData, for efficiency.
707///
708/// Layout:
709///
710/// ```plain
711///        | tag:2 |  type:14        |    x:24       | y:24          |
712///
713/// Inst       00     ty               inst output     inst index
714/// Param      01     ty               blockparam num  block index
715/// Alias      10     ty               0               value index
716/// Union      11     ty               first value     second value
717/// ```
718#[derive(Clone, Copy, Debug, PartialEq, Hash)]
719#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
720struct ValueDataPacked(u64);
721
722/// Encodes a value in 0..2^32 into 0..2^n, where n is less than 32
723/// (and is implied by `mask`), by translating 2^32-1 (0xffffffff)
724/// into 2^n-1 and panic'ing on 2^n..2^32-1.
725fn encode_narrow_field(x: u32, bits: u8) -> u32 {
726    let max = (1 << bits) - 1;
727    if x == 0xffff_ffff {
728        max
729    } else {
730        debug_assert!(
731            x < max,
732            "{x} does not fit into {bits} bits (must be less than {max} to \
733             allow for a 0xffffffff sentinel)"
734        );
735        x
736    }
737}
738
739/// The inverse of the above `encode_narrow_field`: unpacks 2^n-1 into
740/// 2^32-1.
741fn decode_narrow_field(x: u32, bits: u8) -> u32 {
742    if x == (1 << bits) - 1 { 0xffff_ffff } else { x }
743}
744
745impl ValueDataPacked {
746    const Y_SHIFT: u8 = 0;
747    const Y_BITS: u8 = 24;
748    const X_SHIFT: u8 = Self::Y_SHIFT + Self::Y_BITS;
749    const X_BITS: u8 = 24;
750    const TYPE_SHIFT: u8 = Self::X_SHIFT + Self::X_BITS;
751    const TYPE_BITS: u8 = 14;
752    const TAG_SHIFT: u8 = Self::TYPE_SHIFT + Self::TYPE_BITS;
753    const TAG_BITS: u8 = 2;
754
755    const TAG_INST: u64 = 0;
756    const TAG_PARAM: u64 = 1;
757    const TAG_ALIAS: u64 = 2;
758    const TAG_UNION: u64 = 3;
759
760    fn make(tag: u64, ty: Type, x: u32, y: u32) -> ValueDataPacked {
761        debug_assert!(tag < (1 << Self::TAG_BITS));
762        debug_assert!(ty.repr() < (1 << Self::TYPE_BITS));
763
764        let x = encode_narrow_field(x, Self::X_BITS);
765        let y = encode_narrow_field(y, Self::Y_BITS);
766
767        ValueDataPacked(
768            (tag << Self::TAG_SHIFT)
769                | ((ty.repr() as u64) << Self::TYPE_SHIFT)
770                | ((x as u64) << Self::X_SHIFT)
771                | ((y as u64) << Self::Y_SHIFT),
772        )
773    }
774
775    #[inline(always)]
776    fn field(self, shift: u8, bits: u8) -> u64 {
777        (self.0 >> shift) & ((1 << bits) - 1)
778    }
779
780    #[inline(always)]
781    fn ty(self) -> Type {
782        let ty = self.field(ValueDataPacked::TYPE_SHIFT, ValueDataPacked::TYPE_BITS) as u16;
783        Type::from_repr(ty)
784    }
785
786    #[inline(always)]
787    fn set_type(&mut self, ty: Type) {
788        self.0 &= !(((1 << Self::TYPE_BITS) - 1) << Self::TYPE_SHIFT);
789        self.0 |= (ty.repr() as u64) << Self::TYPE_SHIFT;
790    }
791}
792
793impl From<ValueData> for ValueDataPacked {
794    fn from(data: ValueData) -> Self {
795        match data {
796            ValueData::Inst { ty, num, inst } => {
797                Self::make(Self::TAG_INST, ty, num.into(), inst.as_bits())
798            }
799            ValueData::Param { ty, num, block } => {
800                Self::make(Self::TAG_PARAM, ty, num.into(), block.as_bits())
801            }
802            ValueData::Alias { ty, original } => {
803                Self::make(Self::TAG_ALIAS, ty, 0, original.as_bits())
804            }
805            ValueData::Union { ty, x, y } => {
806                Self::make(Self::TAG_UNION, ty, x.as_bits(), y.as_bits())
807            }
808        }
809    }
810}
811
812impl From<ValueDataPacked> for ValueData {
813    fn from(data: ValueDataPacked) -> Self {
814        let tag = data.field(ValueDataPacked::TAG_SHIFT, ValueDataPacked::TAG_BITS);
815        let ty = u16::try_from(data.field(ValueDataPacked::TYPE_SHIFT, ValueDataPacked::TYPE_BITS))
816            .expect("Mask should ensure result fits in a u16");
817        let x = u32::try_from(data.field(ValueDataPacked::X_SHIFT, ValueDataPacked::X_BITS))
818            .expect("Mask should ensure result fits in a u32");
819        let y = u32::try_from(data.field(ValueDataPacked::Y_SHIFT, ValueDataPacked::Y_BITS))
820            .expect("Mask should ensure result fits in a u32");
821
822        let ty = Type::from_repr(ty);
823        match tag {
824            ValueDataPacked::TAG_INST => ValueData::Inst {
825                ty,
826                num: u16::try_from(x).expect("Inst result num should fit in u16"),
827                inst: Inst::from_bits(decode_narrow_field(y, ValueDataPacked::Y_BITS)),
828            },
829            ValueDataPacked::TAG_PARAM => ValueData::Param {
830                ty,
831                num: u16::try_from(x).expect("Blockparam index should fit in u16"),
832                block: Block::from_bits(decode_narrow_field(y, ValueDataPacked::Y_BITS)),
833            },
834            ValueDataPacked::TAG_ALIAS => ValueData::Alias {
835                ty,
836                original: Value::from_bits(decode_narrow_field(y, ValueDataPacked::Y_BITS)),
837            },
838            ValueDataPacked::TAG_UNION => ValueData::Union {
839                ty,
840                x: Value::from_bits(decode_narrow_field(x, ValueDataPacked::X_BITS)),
841                y: Value::from_bits(decode_narrow_field(y, ValueDataPacked::Y_BITS)),
842            },
843            _ => panic!("Invalid tag {} in ValueDataPacked 0x{:x}", tag, data.0),
844        }
845    }
846}
847
848/// Instructions.
849///
850impl DataFlowGraph {
851    /// Create a new instruction.
852    ///
853    /// The type of the first result is indicated by `data.ty`. If the
854    /// instruction produces multiple results, also call
855    /// `make_inst_results` to allocate value table entries. (It is
856    /// always safe to call `make_inst_results`, regardless of how
857    /// many results the instruction has.)
858    pub fn make_inst(&mut self, data: InstructionData) -> Inst {
859        let n = self.num_insts() + 1;
860        self.results.resize(n);
861        self.insts.0.push(data)
862    }
863
864    /// Declares a dynamic vector type
865    pub fn make_dynamic_ty(&mut self, data: DynamicTypeData) -> DynamicType {
866        self.dynamic_types.push(data)
867    }
868
869    /// Returns an object that displays `inst`.
870    pub fn display_inst<'a>(&'a self, inst: Inst) -> DisplayInst<'a> {
871        DisplayInst(self, inst)
872    }
873
874    /// Returns an object that displays the given `value`'s defining instruction.
875    ///
876    /// Panics if the value is not defined by an instruction (i.e. it is a basic
877    /// block argument).
878    pub fn display_value_inst(&self, value: Value) -> DisplayInst<'_> {
879        match self.value_def(value) {
880            ir::ValueDef::Result(inst, _) => self.display_inst(inst),
881            ir::ValueDef::Param(_, _) => panic!("value is not defined by an instruction"),
882            ir::ValueDef::Union(_, _) => panic!("value is a union of two other values"),
883        }
884    }
885
886    /// Construct a read-only visitor context for the values of this instruction.
887    pub fn inst_values<'dfg>(
888        &'dfg self,
889        inst: Inst,
890    ) -> impl DoubleEndedIterator<Item = Value> + 'dfg {
891        self.inst_args(inst).iter().copied().chain(
892            self.insts[inst]
893                .branch_destination(&self.jump_tables, &self.exception_tables)
894                .into_iter()
895                .flat_map(|branch| {
896                    branch
897                        .args(&self.value_lists)
898                        .filter_map(|arg| arg.as_value())
899                }),
900        )
901    }
902
903    /// Map a function over the values of the instruction.
904    pub fn map_inst_values<F>(&mut self, inst: Inst, body: F)
905    where
906        F: FnMut(Value) -> Value,
907    {
908        self.insts[inst].map_values(
909            &mut self.value_lists,
910            &mut self.jump_tables,
911            &mut self.exception_tables,
912            body,
913        );
914    }
915
916    /// Overwrite the instruction's value references with values from the iterator.
917    /// NOTE: the iterator provided is expected to yield at least as many values as the instruction
918    /// currently has.
919    pub fn overwrite_inst_values<I>(&mut self, inst: Inst, mut values: I)
920    where
921        I: Iterator<Item = Value>,
922    {
923        self.insts[inst].map_values(
924            &mut self.value_lists,
925            &mut self.jump_tables,
926            &mut self.exception_tables,
927            |_| values.next().unwrap(),
928        );
929    }
930
931    /// Get all value arguments on `inst` as a slice.
932    pub fn inst_args(&self, inst: Inst) -> &[Value] {
933        self.insts[inst].arguments(&self.value_lists)
934    }
935
936    /// Get all value arguments on `inst` as a mutable slice.
937    pub fn inst_args_mut(&mut self, inst: Inst) -> &mut [Value] {
938        self.insts[inst].arguments_mut(&mut self.value_lists)
939    }
940
941    /// Get the fixed value arguments on `inst` as a slice.
942    pub fn inst_fixed_args(&self, inst: Inst) -> &[Value] {
943        let num_fixed_args = self.insts[inst]
944            .opcode()
945            .constraints()
946            .num_fixed_value_arguments();
947        &self.inst_args(inst)[..num_fixed_args]
948    }
949
950    /// Get the fixed value arguments on `inst` as a mutable slice.
951    pub fn inst_fixed_args_mut(&mut self, inst: Inst) -> &mut [Value] {
952        let num_fixed_args = self.insts[inst]
953            .opcode()
954            .constraints()
955            .num_fixed_value_arguments();
956        &mut self.inst_args_mut(inst)[..num_fixed_args]
957    }
958
959    /// Get the variable value arguments on `inst` as a slice.
960    pub fn inst_variable_args(&self, inst: Inst) -> &[Value] {
961        let num_fixed_args = self.insts[inst]
962            .opcode()
963            .constraints()
964            .num_fixed_value_arguments();
965        &self.inst_args(inst)[num_fixed_args..]
966    }
967
968    /// Get the variable value arguments on `inst` as a mutable slice.
969    pub fn inst_variable_args_mut(&mut self, inst: Inst) -> &mut [Value] {
970        let num_fixed_args = self.insts[inst]
971            .opcode()
972            .constraints()
973            .num_fixed_value_arguments();
974        &mut self.inst_args_mut(inst)[num_fixed_args..]
975    }
976
977    /// Create result values for an instruction that produces multiple results.
978    ///
979    /// Instructions that produce no result values only need to be created with `make_inst`,
980    /// otherwise call `make_inst_results` to allocate value table entries for the results.
981    ///
982    /// The result value types are determined from the instruction's value type constraints and the
983    /// provided `ctrl_typevar` type for polymorphic instructions. For non-polymorphic
984    /// instructions, `ctrl_typevar` is ignored, and `INVALID` can be used.
985    ///
986    /// The type of the first result value is also set, even if it was already set in the
987    /// `InstructionData` passed to `make_inst`. If this function is called with a single-result
988    /// instruction, that is the only effect.
989    pub fn make_inst_results(&mut self, inst: Inst, ctrl_typevar: Type) -> usize {
990        self.make_inst_results_reusing(inst, ctrl_typevar, iter::empty())
991    }
992
993    /// Create result values for `inst`, reusing the provided detached values.
994    ///
995    /// Create a new set of result values for `inst` using `ctrl_typevar` to determine the result
996    /// types. Any values provided by `reuse` will be reused. When `reuse` is exhausted or when it
997    /// produces `None`, a new value is created.
998    pub fn make_inst_results_reusing<I>(
999        &mut self,
1000        inst: Inst,
1001        ctrl_typevar: Type,
1002        reuse: I,
1003    ) -> usize
1004    where
1005        I: Iterator<Item = Option<Value>>,
1006    {
1007        self.clear_results(inst);
1008
1009        let mut reuse = reuse.fuse();
1010        let result_tys: SmallVec<[_; 16]> = self.inst_result_types(inst, ctrl_typevar).collect();
1011
1012        for (expected, &ty) in result_tys.iter().enumerate() {
1013            let num = u16::try_from(expected).expect("Result value index should fit in u16");
1014            let value_data = ValueData::Inst { ty, num, inst };
1015            let v = if let Some(Some(v)) = reuse.next() {
1016                debug_assert_eq!(self.value_type(v), ty, "Reused {ty} is wrong type");
1017                debug_assert!(!self.value_is_attached(v));
1018                self.values[v] = value_data.into();
1019                v
1020            } else {
1021                self.make_value(value_data)
1022            };
1023            let actual = self.results[inst].push(v, &mut self.value_lists);
1024            debug_assert_eq!(expected, actual);
1025        }
1026
1027        result_tys.len()
1028    }
1029
1030    /// Create a `ReplaceBuilder` that will replace `inst` with a new instruction in place.
1031    pub fn replace(&mut self, inst: Inst) -> ReplaceBuilder<'_> {
1032        ReplaceBuilder::new(self, inst)
1033    }
1034
1035    /// Clear the list of result values from `inst`.
1036    ///
1037    /// This leaves `inst` without any result values. New result values can be created by calling
1038    /// `make_inst_results` or by using a `replace(inst)` builder.
1039    pub fn clear_results(&mut self, inst: Inst) {
1040        self.results[inst].clear(&mut self.value_lists)
1041    }
1042
1043    /// Replace an instruction result with a new value of type `new_type`.
1044    ///
1045    /// The `old_value` must be an attached instruction result.
1046    ///
1047    /// The old value is left detached, so it should probably be changed into something else.
1048    ///
1049    /// Returns the new value.
1050    pub fn replace_result(&mut self, old_value: Value, new_type: Type) -> Value {
1051        let (num, inst) = match ValueData::from(self.values[old_value]) {
1052            ValueData::Inst { num, inst, .. } => (num, inst),
1053            _ => panic!("{old_value} is not an instruction result value"),
1054        };
1055        let new_value = self.make_value(ValueData::Inst {
1056            ty: new_type,
1057            num,
1058            inst,
1059        });
1060        let num = num as usize;
1061        let attached = mem::replace(
1062            self.results[inst]
1063                .get_mut(num, &mut self.value_lists)
1064                .expect("Replacing detached result"),
1065            new_value,
1066        );
1067        debug_assert_eq!(
1068            attached,
1069            old_value,
1070            "{} wasn't detached from {}",
1071            old_value,
1072            self.display_inst(inst)
1073        );
1074        new_value
1075    }
1076
1077    /// Clone an instruction, attaching new result `Value`s and
1078    /// returning them.
1079    pub fn clone_inst(&mut self, inst: Inst) -> Inst {
1080        // First, add a clone of the InstructionData.
1081        let inst_data = self.insts[inst];
1082        // If the `inst_data` has a reference to a ValueList, clone it
1083        // as well, because we can't share these (otherwise mutating
1084        // one would affect the other).
1085        let inst_data = inst_data.deep_clone(&mut self.value_lists);
1086        let new_inst = self.make_inst(inst_data);
1087        // Get the controlling type variable.
1088        let ctrl_typevar = self.ctrl_typevar(inst);
1089        // Create new result values.
1090        let num_results = self.make_inst_results(new_inst, ctrl_typevar);
1091        // Copy over PCC facts, if any.
1092        for i in 0..num_results {
1093            let old_result = self.inst_results(inst)[i];
1094            let new_result = self.inst_results(new_inst)[i];
1095            self.facts[new_result] = self.facts[old_result].clone();
1096        }
1097        new_inst
1098    }
1099
1100    /// Get the first result of an instruction.
1101    ///
1102    /// This function panics if the instruction doesn't have any result.
1103    pub fn first_result(&self, inst: Inst) -> Value {
1104        self.results[inst]
1105            .first(&self.value_lists)
1106            .unwrap_or_else(|| panic!("{inst} has no results"))
1107    }
1108
1109    /// Test if `inst` has any result values currently.
1110    pub fn has_results(&self, inst: Inst) -> bool {
1111        !self.results[inst].is_empty()
1112    }
1113
1114    /// Return all the results of an instruction.
1115    pub fn inst_results(&self, inst: Inst) -> &[Value] {
1116        self.results[inst].as_slice(&self.value_lists)
1117    }
1118
1119    /// Return all the results of an instruction as ValueList.
1120    pub fn inst_results_list(&self, inst: Inst) -> ValueList {
1121        self.results[inst]
1122    }
1123
1124    /// Create a union of two values.
1125    pub fn union(&mut self, x: Value, y: Value) -> Value {
1126        // Get the type.
1127        let ty = self.value_type(x);
1128        debug_assert_eq!(ty, self.value_type(y));
1129        self.make_value(ValueData::Union { ty, x, y })
1130    }
1131
1132    /// Get the call signature of a direct or indirect call instruction.
1133    /// Returns `None` if `inst` is not a call instruction.
1134    pub fn call_signature(&self, inst: Inst) -> Option<SigRef> {
1135        match self.insts[inst].analyze_call(&self.value_lists, &self.exception_tables) {
1136            CallInfo::NotACall => None,
1137            CallInfo::Direct(f, _) => Some(self.ext_funcs[f].signature),
1138            CallInfo::DirectWithSig(_, s, _) => Some(s),
1139            CallInfo::Indirect(s, _) => Some(s),
1140        }
1141    }
1142
1143    /// Like `call_signature` but returns none for tail call
1144    /// instructions and try-call (exception-handling invoke)
1145    /// instructions.
1146    fn non_tail_call_or_try_call_signature(&self, inst: Inst) -> Option<SigRef> {
1147        let sig = self.call_signature(inst)?;
1148        match self.insts[inst].opcode() {
1149            ir::Opcode::ReturnCall | ir::Opcode::ReturnCallIndirect => None,
1150            ir::Opcode::TryCall | ir::Opcode::TryCallIndirect => None,
1151            _ => Some(sig),
1152        }
1153    }
1154
1155    // Only for use by the verifier. Everyone else should just use
1156    // `dfg.inst_results(inst).len()`.
1157    pub(crate) fn num_expected_results_for_verifier(&self, inst: Inst) -> usize {
1158        match self.non_tail_call_or_try_call_signature(inst) {
1159            Some(sig) => self.signatures[sig].returns.len(),
1160            None => {
1161                let constraints = self.insts[inst].opcode().constraints();
1162                constraints.num_fixed_results()
1163            }
1164        }
1165    }
1166
1167    /// Get the result types of the given instruction.
1168    pub fn inst_result_types<'a>(
1169        &'a self,
1170        inst: Inst,
1171        ctrl_typevar: Type,
1172    ) -> impl iter::ExactSizeIterator<Item = Type> + 'a {
1173        return match self.non_tail_call_or_try_call_signature(inst) {
1174            Some(sig) => InstResultTypes::Signature(self, sig, 0),
1175            None => {
1176                let constraints = self.insts[inst].opcode().constraints();
1177                InstResultTypes::Constraints(constraints, ctrl_typevar, 0)
1178            }
1179        };
1180
1181        enum InstResultTypes<'a> {
1182            Signature(&'a DataFlowGraph, SigRef, usize),
1183            Constraints(ir::instructions::OpcodeConstraints, Type, usize),
1184        }
1185
1186        impl Iterator for InstResultTypes<'_> {
1187            type Item = Type;
1188
1189            fn next(&mut self) -> Option<Type> {
1190                match self {
1191                    InstResultTypes::Signature(dfg, sig, i) => {
1192                        let param = dfg.signatures[*sig].returns.get(*i)?;
1193                        *i += 1;
1194                        Some(param.value_type)
1195                    }
1196                    InstResultTypes::Constraints(constraints, ctrl_ty, i) => {
1197                        if *i < constraints.num_fixed_results() {
1198                            let ty = constraints.result_type(*i, *ctrl_ty);
1199                            *i += 1;
1200                            Some(ty)
1201                        } else {
1202                            None
1203                        }
1204                    }
1205                }
1206            }
1207
1208            fn size_hint(&self) -> (usize, Option<usize>) {
1209                let len = match self {
1210                    InstResultTypes::Signature(dfg, sig, i) => {
1211                        dfg.signatures[*sig].returns.len() - *i
1212                    }
1213                    InstResultTypes::Constraints(constraints, _, i) => {
1214                        constraints.num_fixed_results() - *i
1215                    }
1216                };
1217                (len, Some(len))
1218            }
1219        }
1220
1221        impl ExactSizeIterator for InstResultTypes<'_> {}
1222    }
1223
1224    /// Compute the type of an instruction result from opcode constraints and call signatures.
1225    ///
1226    /// This computes the same sequence of result types that `make_inst_results()` above would
1227    /// assign to the created result values, but it does not depend on `make_inst_results()` being
1228    /// called first.
1229    ///
1230    /// Returns `None` if asked about a result index that is too large.
1231    pub fn compute_result_type(
1232        &self,
1233        inst: Inst,
1234        result_idx: usize,
1235        ctrl_typevar: Type,
1236    ) -> Option<Type> {
1237        self.inst_result_types(inst, ctrl_typevar).nth(result_idx)
1238    }
1239
1240    /// Get the controlling type variable, or `INVALID` if `inst` isn't polymorphic.
1241    pub fn ctrl_typevar(&self, inst: Inst) -> Type {
1242        let constraints = self.insts[inst].opcode().constraints();
1243
1244        if !constraints.is_polymorphic() {
1245            types::INVALID
1246        } else if constraints.requires_typevar_operand() {
1247            // Not all instruction formats have a designated operand, but in that case
1248            // `requires_typevar_operand()` should never be true.
1249            self.value_type(
1250                self.insts[inst]
1251                    .typevar_operand(&self.value_lists)
1252                    .unwrap_or_else(|| {
1253                        panic!(
1254                            "Instruction format for {:?} doesn't have a designated operand",
1255                            self.insts[inst]
1256                        )
1257                    }),
1258            )
1259        } else {
1260            self.value_type(self.first_result(inst))
1261        }
1262    }
1263}
1264
1265/// basic blocks.
1266impl DataFlowGraph {
1267    /// Create a new basic block.
1268    pub fn make_block(&mut self) -> Block {
1269        self.blocks.add()
1270    }
1271
1272    /// Get the number of parameters on `block`.
1273    pub fn num_block_params(&self, block: Block) -> usize {
1274        self.blocks[block].params(&self.value_lists).len()
1275    }
1276
1277    /// Get the parameters on `block`.
1278    pub fn block_params(&self, block: Block) -> &[Value] {
1279        self.blocks[block].params(&self.value_lists)
1280    }
1281
1282    /// Get the types of the parameters on `block`.
1283    pub fn block_param_types(&self, block: Block) -> impl Iterator<Item = Type> + '_ {
1284        self.block_params(block).iter().map(|&v| self.value_type(v))
1285    }
1286
1287    /// Append a parameter with type `ty` to `block`.
1288    pub fn append_block_param(&mut self, block: Block, ty: Type) -> Value {
1289        let param = self.values.next_key();
1290        let num = self.blocks[block].params.push(param, &mut self.value_lists);
1291        debug_assert!(num <= u16::MAX as usize, "Too many parameters on block");
1292        self.make_value(ValueData::Param {
1293            ty,
1294            num: num as u16,
1295            block,
1296        })
1297    }
1298
1299    /// Removes `val` from `block`'s parameters by swapping it with the last parameter on `block`.
1300    /// Returns the position of `val` before removal.
1301    ///
1302    /// *Important*: to ensure O(1) deletion, this method swaps the removed parameter with the
1303    /// last `block` parameter. This can disrupt all the branch instructions jumping to this
1304    /// `block` for which you have to change the branch argument order if necessary.
1305    ///
1306    /// Panics if `val` is not a block parameter.
1307    pub fn swap_remove_block_param(&mut self, val: Value) -> usize {
1308        let (block, num) =
1309            if let ValueData::Param { num, block, .. } = ValueData::from(self.values[val]) {
1310                (block, num)
1311            } else {
1312                panic!("{val} must be a block parameter");
1313            };
1314        self.blocks[block]
1315            .params
1316            .swap_remove(num as usize, &mut self.value_lists);
1317        if let Some(last_arg_val) = self.blocks[block]
1318            .params
1319            .get(num as usize, &self.value_lists)
1320        {
1321            // We update the position of the old last arg.
1322            let mut last_arg_data = ValueData::from(self.values[last_arg_val]);
1323            if let ValueData::Param { num: old_num, .. } = &mut last_arg_data {
1324                *old_num = num;
1325                self.values[last_arg_val] = last_arg_data.into();
1326            } else {
1327                panic!("{last_arg_val} should be a Block parameter");
1328            }
1329        }
1330        num as usize
1331    }
1332
1333    /// Removes `val` from `block`'s parameters by a standard linear time list removal which
1334    /// preserves ordering. Also updates the values' data.
1335    pub fn remove_block_param(&mut self, val: Value) {
1336        let (block, num) =
1337            if let ValueData::Param { num, block, .. } = ValueData::from(self.values[val]) {
1338                (block, num)
1339            } else {
1340                panic!("{val} must be a block parameter");
1341            };
1342        self.blocks[block]
1343            .params
1344            .remove(num as usize, &mut self.value_lists);
1345        for index in num..(self.num_block_params(block) as u16) {
1346            let packed = &mut self.values[self.blocks[block]
1347                .params
1348                .get(index as usize, &self.value_lists)
1349                .unwrap()];
1350            let mut data = ValueData::from(*packed);
1351            match &mut data {
1352                ValueData::Param { num, .. } => {
1353                    *num -= 1;
1354                    *packed = data.into();
1355                }
1356                _ => panic!(
1357                    "{} must be a block parameter",
1358                    self.blocks[block]
1359                        .params
1360                        .get(index as usize, &self.value_lists)
1361                        .unwrap()
1362                ),
1363            }
1364        }
1365    }
1366
1367    /// Append an existing value to `block`'s parameters.
1368    ///
1369    /// The appended value can't already be attached to something else.
1370    ///
1371    /// In almost all cases, you should be using `append_block_param()` instead of this method.
1372    pub fn attach_block_param(&mut self, block: Block, param: Value) {
1373        debug_assert!(!self.value_is_attached(param));
1374        let num = self.blocks[block].params.push(param, &mut self.value_lists);
1375        debug_assert!(num <= u16::MAX as usize, "Too many parameters on block");
1376        let ty = self.value_type(param);
1377        self.values[param] = ValueData::Param {
1378            ty,
1379            num: num as u16,
1380            block,
1381        }
1382        .into();
1383    }
1384
1385    /// Replace a block parameter with a new value of type `ty`.
1386    ///
1387    /// The `old_value` must be an attached block parameter. It is removed from its place in the list
1388    /// of parameters and replaced by a new value of type `new_type`. The new value gets the same
1389    /// position in the list, and other parameters are not disturbed.
1390    ///
1391    /// The old value is left detached, so it should probably be changed into something else.
1392    ///
1393    /// Returns the new value.
1394    pub fn replace_block_param(&mut self, old_value: Value, new_type: Type) -> Value {
1395        // Create new value identical to the old one except for the type.
1396        let (block, num) =
1397            if let ValueData::Param { num, block, .. } = ValueData::from(self.values[old_value]) {
1398                (block, num)
1399            } else {
1400                panic!("{old_value} must be a block parameter");
1401            };
1402        let new_arg = self.make_value(ValueData::Param {
1403            ty: new_type,
1404            num,
1405            block,
1406        });
1407
1408        self.blocks[block]
1409            .params
1410            .as_mut_slice(&mut self.value_lists)[num as usize] = new_arg;
1411        new_arg
1412    }
1413
1414    /// Detach all the parameters from `block` and return them as a `ValueList`.
1415    ///
1416    /// This is a quite low-level operation. Sensible things to do with the detached block parameters
1417    /// is to put them back on the same block with `attach_block_param()` or change them into aliases
1418    /// with `change_to_alias()`.
1419    pub fn detach_block_params(&mut self, block: Block) -> ValueList {
1420        self.blocks[block].params.take()
1421    }
1422
1423    /// Detach all of an instruction's result values.
1424    ///
1425    /// This is a quite low-level operation. A sensible thing to do with the
1426    /// detached results is to change them into aliases with
1427    /// `change_to_alias()`.
1428    pub fn detach_inst_results(&mut self, inst: Inst) {
1429        self.results[inst].clear(&mut self.value_lists);
1430    }
1431
1432    /// Merge the facts for two values. If both values have facts and
1433    /// they differ, both values get a special "conflict" fact that is
1434    /// never satisfied.
1435    pub fn merge_facts(&mut self, a: Value, b: Value) {
1436        let a = self.resolve_aliases(a);
1437        let b = self.resolve_aliases(b);
1438        match (&self.facts[a], &self.facts[b]) {
1439            (Some(a), Some(b)) if a == b => { /* nothing */ }
1440            (None, None) => { /* nothing */ }
1441            (Some(a), None) => {
1442                self.facts[b] = Some(a.clone());
1443            }
1444            (None, Some(b)) => {
1445                self.facts[a] = Some(b.clone());
1446            }
1447            (Some(a_fact), Some(b_fact)) => {
1448                assert_eq!(self.value_type(a), self.value_type(b));
1449                let merged = Fact::intersect(a_fact, b_fact);
1450                crate::trace!(
1451                    "facts merge on {} and {}: {:?}, {:?} -> {:?}",
1452                    a,
1453                    b,
1454                    a_fact,
1455                    b_fact,
1456                    merged,
1457                );
1458                self.facts[a] = Some(merged.clone());
1459                self.facts[b] = Some(merged);
1460            }
1461        }
1462    }
1463}
1464
1465/// Contents of a basic block.
1466///
1467/// Parameters on a basic block are values that dominate everything in the block. All
1468/// branches to this block must provide matching arguments, and the arguments to the entry block must
1469/// match the function arguments.
1470#[derive(Clone, PartialEq, Hash)]
1471#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
1472pub struct BlockData {
1473    /// List of parameters to this block.
1474    params: ValueList,
1475}
1476
1477impl BlockData {
1478    fn new() -> Self {
1479        Self {
1480            params: ValueList::new(),
1481        }
1482    }
1483
1484    /// Get the parameters on `block`.
1485    pub fn params<'a>(&self, pool: &'a ValueListPool) -> &'a [Value] {
1486        self.params.as_slice(pool)
1487    }
1488}
1489
1490/// Object that can display an instruction.
1491pub struct DisplayInst<'a>(&'a DataFlowGraph, Inst);
1492
1493impl<'a> fmt::Display for DisplayInst<'a> {
1494    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1495        let dfg = self.0;
1496        let inst = self.1;
1497
1498        if let Some((first, rest)) = dfg.inst_results(inst).split_first() {
1499            write!(f, "{first}")?;
1500            for v in rest {
1501                write!(f, ", {v}")?;
1502            }
1503            write!(f, " = ")?;
1504        }
1505
1506        let typevar = dfg.ctrl_typevar(inst);
1507        if typevar.is_invalid() {
1508            write!(f, "{}", dfg.insts[inst].opcode())?;
1509        } else {
1510            write!(f, "{}.{}", dfg.insts[inst].opcode(), typevar)?;
1511        }
1512        write_operands(f, dfg, inst)
1513    }
1514}
1515
1516/// Parser routines. These routines should not be used outside the parser.
1517impl DataFlowGraph {
1518    /// Set the type of a value. This is only for use in the parser, which needs
1519    /// to create invalid values for index padding which may be reassigned later.
1520    #[cold]
1521    fn set_value_type_for_parser(&mut self, v: Value, t: Type) {
1522        assert_eq!(
1523            self.value_type(v),
1524            types::INVALID,
1525            "this function is only for assigning types to previously invalid values"
1526        );
1527        self.values[v].set_type(t);
1528    }
1529
1530    /// Check that the given concrete `Type` has been defined in the function.
1531    pub fn check_dynamic_type(&mut self, ty: Type) -> Option<Type> {
1532        debug_assert!(ty.is_dynamic_vector());
1533        if self
1534            .dynamic_types
1535            .values()
1536            .any(|dyn_ty_data| dyn_ty_data.concrete().unwrap() == ty)
1537        {
1538            Some(ty)
1539        } else {
1540            None
1541        }
1542    }
1543
1544    /// Create result values for `inst`, reusing the provided detached values.
1545    /// This is similar to `make_inst_results_reusing` except it's only for use
1546    /// in the parser, which needs to reuse previously invalid values.
1547    #[cold]
1548    pub fn make_inst_results_for_parser(
1549        &mut self,
1550        inst: Inst,
1551        ctrl_typevar: Type,
1552        reuse: &[Value],
1553    ) -> usize {
1554        let mut reuse_iter = reuse.iter().copied();
1555        let result_tys: SmallVec<[_; 16]> = self.inst_result_types(inst, ctrl_typevar).collect();
1556        for ty in result_tys {
1557            if ty.is_dynamic_vector() {
1558                self.check_dynamic_type(ty)
1559                    .unwrap_or_else(|| panic!("Use of undeclared dynamic type: {ty}"));
1560            }
1561            if let Some(v) = reuse_iter.next() {
1562                self.set_value_type_for_parser(v, ty);
1563            }
1564        }
1565
1566        self.make_inst_results_reusing(inst, ctrl_typevar, reuse.iter().map(|x| Some(*x)))
1567    }
1568
1569    /// Similar to `append_block_param`, append a parameter with type `ty` to
1570    /// `block`, but using value `val`. This is only for use by the parser to
1571    /// create parameters with specific values.
1572    #[cold]
1573    pub fn append_block_param_for_parser(&mut self, block: Block, ty: Type, val: Value) {
1574        let num = self.blocks[block].params.push(val, &mut self.value_lists);
1575        assert!(num <= u16::MAX as usize, "Too many parameters on block");
1576        self.values[val] = ValueData::Param {
1577            ty,
1578            num: num as u16,
1579            block,
1580        }
1581        .into();
1582    }
1583
1584    /// Create a new value alias. This is only for use by the parser to create
1585    /// aliases with specific values, and the printer for testing.
1586    #[cold]
1587    pub fn make_value_alias_for_serialization(&mut self, src: Value, dest: Value) {
1588        assert_ne!(src, Value::reserved_value());
1589        assert_ne!(dest, Value::reserved_value());
1590
1591        let ty = if self.values.is_valid(src) {
1592            self.value_type(src)
1593        } else {
1594            // As a special case, if we can't resolve the aliasee yet, use INVALID
1595            // temporarily. It will be resolved later in parsing.
1596            types::INVALID
1597        };
1598        let data = ValueData::Alias { ty, original: src };
1599        self.values[dest] = data.into();
1600    }
1601
1602    /// If `v` is already defined as an alias, return its destination value.
1603    /// Otherwise return None. This allows the parser to coalesce identical
1604    /// alias definitions, and the printer to identify an alias's immediate target.
1605    #[cold]
1606    pub fn value_alias_dest_for_serialization(&self, v: Value) -> Option<Value> {
1607        if let ValueData::Alias { original, .. } = ValueData::from(self.values[v]) {
1608            Some(original)
1609        } else {
1610            None
1611        }
1612    }
1613
1614    /// Compute the type of an alias. This is only for use in the parser.
1615    /// Returns false if an alias cycle was encountered.
1616    #[cold]
1617    pub fn set_alias_type_for_parser(&mut self, v: Value) -> bool {
1618        if let Some(resolved) = maybe_resolve_aliases(&self.values, v) {
1619            let old_ty = self.value_type(v);
1620            let new_ty = self.value_type(resolved);
1621            if old_ty == types::INVALID {
1622                self.set_value_type_for_parser(v, new_ty);
1623            } else {
1624                assert_eq!(old_ty, new_ty);
1625            }
1626            true
1627        } else {
1628            false
1629        }
1630    }
1631
1632    /// Create an invalid value, to pad the index space. This is only for use by
1633    /// the parser to pad out the value index space.
1634    #[cold]
1635    pub fn make_invalid_value_for_parser(&mut self) {
1636        let data = ValueData::Alias {
1637            ty: types::INVALID,
1638            original: Value::reserved_value(),
1639        };
1640        self.make_value(data);
1641    }
1642
1643    /// Check if a value reference is valid, while being aware of aliases which
1644    /// may be unresolved while parsing.
1645    #[cold]
1646    pub fn value_is_valid_for_parser(&self, v: Value) -> bool {
1647        if !self.value_is_valid(v) {
1648            return false;
1649        }
1650        if let ValueData::Alias { ty, .. } = ValueData::from(self.values[v]) {
1651            ty != types::INVALID
1652        } else {
1653            true
1654        }
1655    }
1656}
1657
1658#[cfg(test)]
1659mod tests {
1660    use super::*;
1661    use crate::cursor::{Cursor, FuncCursor};
1662    use crate::ir::{Function, Opcode, TrapCode};
1663    use alloc::string::ToString;
1664
1665    #[test]
1666    fn make_inst() {
1667        let mut dfg = DataFlowGraph::new();
1668
1669        let idata = InstructionData::UnaryImm {
1670            opcode: Opcode::Iconst,
1671            imm: 0.into(),
1672        };
1673        let inst = dfg.make_inst(idata);
1674
1675        dfg.make_inst_results(inst, types::I32);
1676        assert_eq!(inst.to_string(), "inst0");
1677        assert_eq!(dfg.display_inst(inst).to_string(), "v0 = iconst.i32 0");
1678
1679        // Immutable reference resolution.
1680        {
1681            let immdfg = &dfg;
1682            let ins = &immdfg.insts[inst];
1683            assert_eq!(ins.opcode(), Opcode::Iconst);
1684        }
1685
1686        // Results.
1687        let val = dfg.first_result(inst);
1688        assert_eq!(dfg.inst_results(inst), &[val]);
1689
1690        assert_eq!(dfg.value_def(val), ValueDef::Result(inst, 0));
1691        assert_eq!(dfg.value_type(val), types::I32);
1692
1693        // Replacing results.
1694        assert!(dfg.value_is_attached(val));
1695        let v2 = dfg.replace_result(val, types::F64);
1696        assert!(!dfg.value_is_attached(val));
1697        assert!(dfg.value_is_attached(v2));
1698        assert_eq!(dfg.inst_results(inst), &[v2]);
1699        assert_eq!(dfg.value_def(v2), ValueDef::Result(inst, 0));
1700        assert_eq!(dfg.value_type(v2), types::F64);
1701    }
1702
1703    #[test]
1704    fn no_results() {
1705        let mut dfg = DataFlowGraph::new();
1706
1707        let idata = InstructionData::Trap {
1708            opcode: Opcode::Trap,
1709            code: TrapCode::unwrap_user(1),
1710        };
1711        let inst = dfg.make_inst(idata);
1712        assert_eq!(dfg.display_inst(inst).to_string(), "trap user1");
1713
1714        // Result slice should be empty.
1715        assert_eq!(dfg.inst_results(inst), &[]);
1716    }
1717
1718    #[test]
1719    fn block() {
1720        let mut dfg = DataFlowGraph::new();
1721
1722        let block = dfg.make_block();
1723        assert_eq!(block.to_string(), "block0");
1724        assert_eq!(dfg.num_block_params(block), 0);
1725        assert_eq!(dfg.block_params(block), &[]);
1726        assert!(dfg.detach_block_params(block).is_empty());
1727        assert_eq!(dfg.num_block_params(block), 0);
1728        assert_eq!(dfg.block_params(block), &[]);
1729
1730        let arg1 = dfg.append_block_param(block, types::F32);
1731        assert_eq!(arg1.to_string(), "v0");
1732        assert_eq!(dfg.num_block_params(block), 1);
1733        assert_eq!(dfg.block_params(block), &[arg1]);
1734
1735        let arg2 = dfg.append_block_param(block, types::I16);
1736        assert_eq!(arg2.to_string(), "v1");
1737        assert_eq!(dfg.num_block_params(block), 2);
1738        assert_eq!(dfg.block_params(block), &[arg1, arg2]);
1739
1740        assert_eq!(dfg.value_def(arg1), ValueDef::Param(block, 0));
1741        assert_eq!(dfg.value_def(arg2), ValueDef::Param(block, 1));
1742        assert_eq!(dfg.value_type(arg1), types::F32);
1743        assert_eq!(dfg.value_type(arg2), types::I16);
1744
1745        // Swap the two block parameters.
1746        let vlist = dfg.detach_block_params(block);
1747        assert_eq!(dfg.num_block_params(block), 0);
1748        assert_eq!(dfg.block_params(block), &[]);
1749        assert_eq!(vlist.as_slice(&dfg.value_lists), &[arg1, arg2]);
1750        dfg.attach_block_param(block, arg2);
1751        let arg3 = dfg.append_block_param(block, types::I32);
1752        dfg.attach_block_param(block, arg1);
1753        assert_eq!(dfg.block_params(block), &[arg2, arg3, arg1]);
1754    }
1755
1756    #[test]
1757    fn replace_block_params() {
1758        let mut dfg = DataFlowGraph::new();
1759
1760        let block = dfg.make_block();
1761        let arg1 = dfg.append_block_param(block, types::F32);
1762
1763        let new1 = dfg.replace_block_param(arg1, types::I64);
1764        assert_eq!(dfg.value_type(arg1), types::F32);
1765        assert_eq!(dfg.value_type(new1), types::I64);
1766        assert_eq!(dfg.block_params(block), &[new1]);
1767
1768        dfg.attach_block_param(block, arg1);
1769        assert_eq!(dfg.block_params(block), &[new1, arg1]);
1770
1771        let new2 = dfg.replace_block_param(arg1, types::I8);
1772        assert_eq!(dfg.value_type(arg1), types::F32);
1773        assert_eq!(dfg.value_type(new2), types::I8);
1774        assert_eq!(dfg.block_params(block), &[new1, new2]);
1775
1776        dfg.attach_block_param(block, arg1);
1777        assert_eq!(dfg.block_params(block), &[new1, new2, arg1]);
1778
1779        let new3 = dfg.replace_block_param(new2, types::I16);
1780        assert_eq!(dfg.value_type(new1), types::I64);
1781        assert_eq!(dfg.value_type(new2), types::I8);
1782        assert_eq!(dfg.value_type(new3), types::I16);
1783        assert_eq!(dfg.block_params(block), &[new1, new3, arg1]);
1784    }
1785
1786    #[test]
1787    fn swap_remove_block_params() {
1788        let mut dfg = DataFlowGraph::new();
1789
1790        let block = dfg.make_block();
1791        let arg1 = dfg.append_block_param(block, types::F32);
1792        let arg2 = dfg.append_block_param(block, types::F32);
1793        let arg3 = dfg.append_block_param(block, types::F32);
1794        assert_eq!(dfg.block_params(block), &[arg1, arg2, arg3]);
1795
1796        dfg.swap_remove_block_param(arg1);
1797        assert_eq!(dfg.value_is_attached(arg1), false);
1798        assert_eq!(dfg.value_is_attached(arg2), true);
1799        assert_eq!(dfg.value_is_attached(arg3), true);
1800        assert_eq!(dfg.block_params(block), &[arg3, arg2]);
1801        dfg.swap_remove_block_param(arg2);
1802        assert_eq!(dfg.value_is_attached(arg2), false);
1803        assert_eq!(dfg.value_is_attached(arg3), true);
1804        assert_eq!(dfg.block_params(block), &[arg3]);
1805        dfg.swap_remove_block_param(arg3);
1806        assert_eq!(dfg.value_is_attached(arg3), false);
1807        assert_eq!(dfg.block_params(block), &[]);
1808    }
1809
1810    #[test]
1811    fn aliases() {
1812        use crate::ir::InstBuilder;
1813        use crate::ir::condcodes::IntCC;
1814
1815        let mut func = Function::new();
1816        let block0 = func.dfg.make_block();
1817        let mut pos = FuncCursor::new(&mut func);
1818        pos.insert_block(block0);
1819
1820        // Build a little test program.
1821        let v1 = pos.ins().iconst(types::I32, 42);
1822
1823        // Make sure we can resolve value aliases even when values is empty.
1824        assert_eq!(pos.func.dfg.resolve_aliases(v1), v1);
1825
1826        let arg0 = pos.func.dfg.append_block_param(block0, types::I32);
1827        let (s, c) = pos.ins().uadd_overflow(v1, arg0);
1828        let iadd = match pos.func.dfg.value_def(s) {
1829            ValueDef::Result(i, 0) => i,
1830            _ => panic!(),
1831        };
1832
1833        // Remove `c` from the result list.
1834        pos.func.stencil.dfg.results[iadd].remove(1, &mut pos.func.stencil.dfg.value_lists);
1835
1836        // Replace `uadd_overflow` with a normal `iadd` and an `icmp`.
1837        pos.func.dfg.replace(iadd).iadd(v1, arg0);
1838        let c2 = pos.ins().icmp(IntCC::Equal, s, v1);
1839        pos.func.dfg.change_to_alias(c, c2);
1840
1841        assert_eq!(pos.func.dfg.resolve_aliases(c2), c2);
1842        assert_eq!(pos.func.dfg.resolve_aliases(c), c2);
1843    }
1844
1845    #[test]
1846    fn cloning() {
1847        use crate::ir::InstBuilder;
1848
1849        let mut func = Function::new();
1850        let mut sig = Signature::new(crate::isa::CallConv::SystemV);
1851        sig.params.push(ir::AbiParam::new(types::I32));
1852        let sig = func.import_signature(sig);
1853        let block0 = func.dfg.make_block();
1854        let mut pos = FuncCursor::new(&mut func);
1855        pos.insert_block(block0);
1856        let v1 = pos.ins().iconst(types::I32, 0);
1857        let v2 = pos.ins().iconst(types::I32, 1);
1858        let call_inst = pos.ins().call_indirect(sig, v1, &[v1]);
1859        let func = pos.func;
1860
1861        let call_inst_dup = func.dfg.clone_inst(call_inst);
1862        func.dfg.inst_args_mut(call_inst)[0] = v2;
1863        assert_eq!(v1, func.dfg.inst_args(call_inst_dup)[0]);
1864    }
1865}