cranelift_codegen/ir/
layout.rs

1//! Function layout.
2//!
3//! The order of basic blocks in a function and the order of instructions in a block is
4//! determined by the `Layout` data structure defined in this module.
5
6use crate::entity::SecondaryMap;
7use crate::ir::progpoint::ProgramPoint;
8use crate::ir::{Block, Inst};
9use crate::packed_option::PackedOption;
10use crate::{timing, trace};
11use core::cmp;
12
13/// The `Layout` struct determines the layout of blocks and instructions in a function. It does not
14/// contain definitions of instructions or blocks, but depends on `Inst` and `Block` entity references
15/// being defined elsewhere.
16///
17/// This data structure determines:
18///
19/// - The order of blocks in the function.
20/// - Which block contains a given instruction.
21/// - The order of instructions with a block.
22///
23/// While data dependencies are not recorded, instruction ordering does affect control
24/// dependencies, so part of the semantics of the program are determined by the layout.
25///
26#[derive(Debug, Clone, PartialEq, Hash)]
27pub struct Layout {
28    /// Linked list nodes for the layout order of blocks Forms a doubly linked list, terminated in
29    /// both ends by `None`.
30    blocks: SecondaryMap<Block, BlockNode>,
31
32    /// Linked list nodes for the layout order of instructions. Forms a double linked list per block,
33    /// terminated in both ends by `None`.
34    insts: SecondaryMap<Inst, InstNode>,
35
36    /// First block in the layout order, or `None` when no blocks have been laid out.
37    first_block: Option<Block>,
38
39    /// Last block in the layout order, or `None` when no blocks have been laid out.
40    last_block: Option<Block>,
41}
42
43impl Layout {
44    /// Create a new empty `Layout`.
45    pub fn new() -> Self {
46        Self {
47            blocks: SecondaryMap::new(),
48            insts: SecondaryMap::new(),
49            first_block: None,
50            last_block: None,
51        }
52    }
53
54    /// Clear the layout.
55    pub fn clear(&mut self) {
56        self.blocks.clear();
57        self.insts.clear();
58        self.first_block = None;
59        self.last_block = None;
60    }
61
62    /// Returns the capacity of the `BlockData` map.
63    pub fn block_capacity(&self) -> usize {
64        self.blocks.capacity()
65    }
66}
67
68/// Sequence numbers.
69///
70/// All instructions are given a sequence number that can be used to quickly determine
71/// their relative position in a block. The sequence numbers are not contiguous, but are assigned
72/// like line numbers in BASIC: 10, 20, 30, ...
73///
74/// Sequence numbers are strictly increasing within a block, but are reset between blocks.
75///
76/// The result is that sequence numbers work like BASIC line numbers for the textual form of the IR.
77type SequenceNumber = u32;
78
79/// Initial stride assigned to new sequence numbers.
80const MAJOR_STRIDE: SequenceNumber = 10;
81
82/// Secondary stride used when renumbering locally.
83const MINOR_STRIDE: SequenceNumber = 2;
84
85/// Limit on the sequence number range we'll renumber locally. If this limit is exceeded, we'll
86/// switch to a full block renumbering.
87const LOCAL_LIMIT: SequenceNumber = 100 * MINOR_STRIDE;
88
89/// Compute the midpoint between `a` and `b`.
90/// Return `None` if the midpoint would be equal to either.
91fn midpoint(a: SequenceNumber, b: SequenceNumber) -> Option<SequenceNumber> {
92    debug_assert!(a < b);
93    // Avoid integer overflow.
94    let m = a + (b - a) / 2;
95    if m > a { Some(m) } else { None }
96}
97
98impl Layout {
99    /// Compare the program points `a` and `b` in the same block relative to this program order.
100    ///
101    /// Return `Less` if `a` appears in the program before `b`.
102    ///
103    /// This is declared as a generic such that it can be called with `Inst` and `Block` arguments
104    /// directly. Depending on the implementation, there is a good chance performance will be
105    /// improved for those cases where the type of either argument is known statically.
106    pub fn pp_cmp<A, B>(&self, a: A, b: B) -> cmp::Ordering
107    where
108        A: Into<ProgramPoint>,
109        B: Into<ProgramPoint>,
110    {
111        let a = a.into();
112        let b = b.into();
113        debug_assert_eq!(self.pp_block(a), self.pp_block(b));
114        let a_seq = match a {
115            ProgramPoint::Block(_block) => 0,
116            ProgramPoint::Inst(inst) => self.insts[inst].seq,
117        };
118        let b_seq = match b {
119            ProgramPoint::Block(_block) => 0,
120            ProgramPoint::Inst(inst) => self.insts[inst].seq,
121        };
122        a_seq.cmp(&b_seq)
123    }
124}
125
126// Private methods for dealing with sequence numbers.
127impl Layout {
128    /// Assign a valid sequence number to `inst` such that the numbers are still monotonic. This may
129    /// require renumbering.
130    fn assign_inst_seq(&mut self, inst: Inst) {
131        // Get the sequence number immediately before `inst`.
132        let prev_seq = match self.insts[inst].prev.expand() {
133            Some(prev_inst) => self.insts[prev_inst].seq,
134            None => 0,
135        };
136
137        // Get the sequence number immediately following `inst`.
138        let next_seq = if let Some(next_inst) = self.insts[inst].next.expand() {
139            self.insts[next_inst].seq
140        } else {
141            // There is nothing after `inst`. We can just use a major stride.
142            self.insts[inst].seq = prev_seq + MAJOR_STRIDE;
143            return;
144        };
145
146        // Check if there is room between these sequence numbers.
147        if let Some(seq) = midpoint(prev_seq, next_seq) {
148            self.insts[inst].seq = seq;
149        } else {
150            // No available integers between `prev_seq` and `next_seq`. We have to renumber.
151            self.renumber_insts(inst, prev_seq + MINOR_STRIDE, prev_seq + LOCAL_LIMIT);
152        }
153    }
154
155    /// Renumber instructions starting from `inst` until the end of the block or until numbers catch
156    /// up.
157    ///
158    /// If sequence numbers exceed `limit`, switch to a full block renumbering.
159    fn renumber_insts(&mut self, inst: Inst, seq: SequenceNumber, limit: SequenceNumber) {
160        let mut inst = inst;
161        let mut seq = seq;
162
163        loop {
164            self.insts[inst].seq = seq;
165
166            // Next instruction.
167            inst = match self.insts[inst].next.expand() {
168                None => return,
169                Some(next) => next,
170            };
171
172            if seq < self.insts[inst].seq {
173                // Sequence caught up.
174                return;
175            }
176
177            if seq > limit {
178                // We're pushing too many instructions in front of us.
179                // Switch to a full block renumbering to make some space.
180                self.full_block_renumber(
181                    self.inst_block(inst)
182                        .expect("inst must be inserted before assigning an seq"),
183                );
184                return;
185            }
186
187            seq += MINOR_STRIDE;
188        }
189    }
190
191    /// Renumber all instructions in a block.
192    ///
193    /// This doesn't affect the position of anything, but it gives more room in the internal
194    /// sequence numbers for inserting instructions later.
195    fn full_block_renumber(&mut self, block: Block) {
196        let _tt = timing::layout_renumber();
197        // Avoid 0 as this is reserved for the program point indicating the block itself
198        let mut seq = MAJOR_STRIDE;
199        let mut next_inst = self.blocks[block].first_inst.expand();
200        while let Some(inst) = next_inst {
201            self.insts[inst].seq = seq;
202            seq += MAJOR_STRIDE;
203            next_inst = self.insts[inst].next.expand();
204        }
205
206        trace!("Renumbered {} program points", seq / MAJOR_STRIDE);
207    }
208}
209
210/// Methods for laying out blocks.
211///
212/// An unknown block starts out as *not inserted* in the block layout. The layout is a linear order of
213/// inserted blocks. Once a block has been inserted in the layout, instructions can be added. A block
214/// can only be removed from the layout when it is empty.
215///
216/// Since every block must end with a terminator instruction which cannot fall through, the layout of
217/// blocks do not affect the semantics of the program.
218///
219impl Layout {
220    /// Is `block` currently part of the layout?
221    pub fn is_block_inserted(&self, block: Block) -> bool {
222        Some(block) == self.first_block || self.blocks[block].prev.is_some()
223    }
224
225    /// Insert `block` as the last block in the layout.
226    pub fn append_block(&mut self, block: Block) {
227        debug_assert!(
228            !self.is_block_inserted(block),
229            "Cannot append block that is already in the layout"
230        );
231        {
232            let node = &mut self.blocks[block];
233            debug_assert!(node.first_inst.is_none() && node.last_inst.is_none());
234            node.prev = self.last_block.into();
235            node.next = None.into();
236        }
237        if let Some(last) = self.last_block {
238            self.blocks[last].next = block.into();
239        } else {
240            self.first_block = Some(block);
241        }
242        self.last_block = Some(block);
243    }
244
245    /// Insert `block` in the layout before the existing block `before`.
246    pub fn insert_block(&mut self, block: Block, before: Block) {
247        debug_assert!(
248            !self.is_block_inserted(block),
249            "Cannot insert block that is already in the layout"
250        );
251        debug_assert!(
252            self.is_block_inserted(before),
253            "block Insertion point not in the layout"
254        );
255        let after = self.blocks[before].prev;
256        {
257            let node = &mut self.blocks[block];
258            node.next = before.into();
259            node.prev = after;
260        }
261        self.blocks[before].prev = block.into();
262        match after.expand() {
263            None => self.first_block = Some(block),
264            Some(a) => self.blocks[a].next = block.into(),
265        }
266    }
267
268    /// Insert `block` in the layout *after* the existing block `after`.
269    pub fn insert_block_after(&mut self, block: Block, after: Block) {
270        debug_assert!(
271            !self.is_block_inserted(block),
272            "Cannot insert block that is already in the layout"
273        );
274        debug_assert!(
275            self.is_block_inserted(after),
276            "block Insertion point not in the layout"
277        );
278        let before = self.blocks[after].next;
279        {
280            let node = &mut self.blocks[block];
281            node.next = before;
282            node.prev = after.into();
283        }
284        self.blocks[after].next = block.into();
285        match before.expand() {
286            None => self.last_block = Some(block),
287            Some(b) => self.blocks[b].prev = block.into(),
288        }
289    }
290
291    /// Remove all instructions from `block` and then remove it from
292    /// the layout.
293    pub fn remove_block_and_insts(&mut self, block: Block) {
294        while let Some(inst) = self.first_inst(block) {
295            self.remove_inst(inst);
296        }
297        self.remove_block(block);
298    }
299
300    /// Remove `block` from the layout.
301    pub fn remove_block(&mut self, block: Block) {
302        debug_assert!(self.is_block_inserted(block), "block not in the layout");
303        debug_assert!(self.first_inst(block).is_none(), "block must be empty.");
304
305        // Clear the `block` node and extract links.
306        let prev;
307        let next;
308        {
309            let n = &mut self.blocks[block];
310            prev = n.prev;
311            next = n.next;
312            n.prev = None.into();
313            n.next = None.into();
314        }
315        // Fix up links to `block`.
316        match prev.expand() {
317            None => self.first_block = next.expand(),
318            Some(p) => self.blocks[p].next = next,
319        }
320        match next.expand() {
321            None => self.last_block = prev.expand(),
322            Some(n) => self.blocks[n].prev = prev,
323        }
324    }
325
326    /// Return an iterator over all blocks in layout order.
327    pub fn blocks(&self) -> Blocks<'_> {
328        Blocks {
329            layout: self,
330            next: self.first_block,
331        }
332    }
333
334    /// Get the function's entry block.
335    /// This is simply the first block in the layout order.
336    pub fn entry_block(&self) -> Option<Block> {
337        self.first_block
338    }
339
340    /// Get the last block in the layout.
341    pub fn last_block(&self) -> Option<Block> {
342        self.last_block
343    }
344
345    /// Get the block preceding `block` in the layout order.
346    pub fn prev_block(&self, block: Block) -> Option<Block> {
347        self.blocks[block].prev.expand()
348    }
349
350    /// Get the block following `block` in the layout order.
351    pub fn next_block(&self, block: Block) -> Option<Block> {
352        self.blocks[block].next.expand()
353    }
354
355    /// Mark a block as "cold".
356    ///
357    /// This will try to move it out of the ordinary path of execution
358    /// when lowered to machine code.
359    pub fn set_cold(&mut self, block: Block) {
360        self.blocks[block].cold = true;
361    }
362
363    /// Is the given block cold?
364    pub fn is_cold(&self, block: Block) -> bool {
365        self.blocks[block].cold
366    }
367}
368
369/// A single node in the linked-list of blocks.
370// **Note:** Whenever you add new fields here, don't forget to update the custom serializer for `Layout` too.
371#[derive(Clone, Debug, Default, PartialEq, Hash)]
372struct BlockNode {
373    prev: PackedOption<Block>,
374    next: PackedOption<Block>,
375    first_inst: PackedOption<Inst>,
376    last_inst: PackedOption<Inst>,
377    cold: bool,
378}
379
380/// Iterate over blocks in layout order. See [crate::ir::layout::Layout::blocks].
381pub struct Blocks<'f> {
382    layout: &'f Layout,
383    next: Option<Block>,
384}
385
386impl<'f> Iterator for Blocks<'f> {
387    type Item = Block;
388
389    fn next(&mut self) -> Option<Block> {
390        match self.next {
391            Some(block) => {
392                self.next = self.layout.next_block(block);
393                Some(block)
394            }
395            None => None,
396        }
397    }
398}
399
400/// Use a layout reference in a for loop.
401impl<'f> IntoIterator for &'f Layout {
402    type Item = Block;
403    type IntoIter = Blocks<'f>;
404
405    fn into_iter(self) -> Blocks<'f> {
406        self.blocks()
407    }
408}
409
410/// Methods for arranging instructions.
411///
412/// An instruction starts out as *not inserted* in the layout. An instruction can be inserted into
413/// a block at a given position.
414impl Layout {
415    /// Get the block containing `inst`, or `None` if `inst` is not inserted in the layout.
416    pub fn inst_block(&self, inst: Inst) -> Option<Block> {
417        self.insts[inst].block.into()
418    }
419
420    /// Get the block containing the program point `pp`. Panic if `pp` is not in the layout.
421    pub fn pp_block(&self, pp: ProgramPoint) -> Block {
422        match pp {
423            ProgramPoint::Block(block) => block,
424            ProgramPoint::Inst(inst) => self.inst_block(inst).expect("Program point not in layout"),
425        }
426    }
427
428    /// Append `inst` to the end of `block`.
429    pub fn append_inst(&mut self, inst: Inst, block: Block) {
430        debug_assert_eq!(self.inst_block(inst), None);
431        debug_assert!(
432            self.is_block_inserted(block),
433            "Cannot append instructions to block not in layout"
434        );
435        {
436            let block_node = &mut self.blocks[block];
437            {
438                let inst_node = &mut self.insts[inst];
439                inst_node.block = block.into();
440                inst_node.prev = block_node.last_inst;
441                debug_assert!(inst_node.next.is_none());
442            }
443            if block_node.first_inst.is_none() {
444                block_node.first_inst = inst.into();
445            } else {
446                self.insts[block_node.last_inst.unwrap()].next = inst.into();
447            }
448            block_node.last_inst = inst.into();
449        }
450        self.assign_inst_seq(inst);
451    }
452
453    /// Fetch a block's first instruction.
454    pub fn first_inst(&self, block: Block) -> Option<Inst> {
455        self.blocks[block].first_inst.into()
456    }
457
458    /// Fetch a block's last instruction.
459    pub fn last_inst(&self, block: Block) -> Option<Inst> {
460        self.blocks[block].last_inst.into()
461    }
462
463    /// Fetch the instruction following `inst`.
464    pub fn next_inst(&self, inst: Inst) -> Option<Inst> {
465        self.insts[inst].next.expand()
466    }
467
468    /// Fetch the instruction preceding `inst`.
469    pub fn prev_inst(&self, inst: Inst) -> Option<Inst> {
470        self.insts[inst].prev.expand()
471    }
472
473    /// Insert `inst` before the instruction `before` in the same block.
474    pub fn insert_inst(&mut self, inst: Inst, before: Inst) {
475        debug_assert_eq!(self.inst_block(inst), None);
476        let block = self
477            .inst_block(before)
478            .expect("Instruction before insertion point not in the layout");
479        let after = self.insts[before].prev;
480        {
481            let inst_node = &mut self.insts[inst];
482            inst_node.block = block.into();
483            inst_node.next = before.into();
484            inst_node.prev = after;
485        }
486        self.insts[before].prev = inst.into();
487        match after.expand() {
488            None => self.blocks[block].first_inst = inst.into(),
489            Some(a) => self.insts[a].next = inst.into(),
490        }
491        self.assign_inst_seq(inst);
492    }
493
494    /// Remove `inst` from the layout.
495    pub fn remove_inst(&mut self, inst: Inst) {
496        let block = self.inst_block(inst).expect("Instruction already removed.");
497        // Clear the `inst` node and extract links.
498        let prev;
499        let next;
500        {
501            let n = &mut self.insts[inst];
502            prev = n.prev;
503            next = n.next;
504            n.block = None.into();
505            n.prev = None.into();
506            n.next = None.into();
507        }
508        // Fix up links to `inst`.
509        match prev.expand() {
510            None => self.blocks[block].first_inst = next,
511            Some(p) => self.insts[p].next = next,
512        }
513        match next.expand() {
514            None => self.blocks[block].last_inst = prev,
515            Some(n) => self.insts[n].prev = prev,
516        }
517    }
518
519    /// Iterate over the instructions in `block` in layout order.
520    pub fn block_insts(&self, block: Block) -> Insts<'_> {
521        Insts {
522            layout: self,
523            head: self.blocks[block].first_inst.into(),
524            tail: self.blocks[block].last_inst.into(),
525        }
526    }
527
528    /// Does the given block contain exactly one instruction?
529    pub fn block_contains_exactly_one_inst(&self, block: Block) -> bool {
530        let block = &self.blocks[block];
531        block.first_inst.is_some() && block.first_inst == block.last_inst
532    }
533
534    /// Split the block containing `before` in two.
535    ///
536    /// Insert `new_block` after the old block and move `before` and the following instructions to
537    /// `new_block`:
538    ///
539    /// ```text
540    /// old_block:
541    ///     i1
542    ///     i2
543    ///     i3 << before
544    ///     i4
545    /// ```
546    /// becomes:
547    ///
548    /// ```text
549    /// old_block:
550    ///     i1
551    ///     i2
552    /// new_block:
553    ///     i3 << before
554    ///     i4
555    /// ```
556    pub fn split_block(&mut self, new_block: Block, before: Inst) {
557        let old_block = self
558            .inst_block(before)
559            .expect("The `before` instruction must be in the layout");
560        debug_assert!(!self.is_block_inserted(new_block));
561
562        // Insert new_block after old_block.
563        let next_block = self.blocks[old_block].next;
564        let last_inst = self.blocks[old_block].last_inst;
565        {
566            let node = &mut self.blocks[new_block];
567            node.prev = old_block.into();
568            node.next = next_block;
569            node.first_inst = before.into();
570            node.last_inst = last_inst;
571        }
572        self.blocks[old_block].next = new_block.into();
573
574        // Fix backwards link.
575        if Some(old_block) == self.last_block {
576            self.last_block = Some(new_block);
577        } else {
578            self.blocks[next_block.unwrap()].prev = new_block.into();
579        }
580
581        // Disconnect the instruction links.
582        let prev_inst = self.insts[before].prev;
583        self.insts[before].prev = None.into();
584        self.blocks[old_block].last_inst = prev_inst;
585        match prev_inst.expand() {
586            None => self.blocks[old_block].first_inst = None.into(),
587            Some(pi) => self.insts[pi].next = None.into(),
588        }
589
590        // Fix the instruction -> block pointers.
591        let mut opt_i = Some(before);
592        while let Some(i) = opt_i {
593            debug_assert_eq!(self.insts[i].block.expand(), Some(old_block));
594            self.insts[i].block = new_block.into();
595            opt_i = self.insts[i].next.into();
596        }
597    }
598}
599
600#[derive(Clone, Debug, Default)]
601struct InstNode {
602    /// The Block containing this instruction, or `None` if the instruction is not yet inserted.
603    block: PackedOption<Block>,
604    prev: PackedOption<Inst>,
605    next: PackedOption<Inst>,
606    seq: SequenceNumber,
607}
608
609impl PartialEq for InstNode {
610    fn eq(&self, other: &Self) -> bool {
611        // Ignore the sequence number as it is an optimization used by pp_cmp and may be different
612        // even for equivalent layouts.
613        self.block == other.block && self.prev == other.prev && self.next == other.next
614    }
615}
616
617impl core::hash::Hash for InstNode {
618    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
619        // Ignore the sequence number as it is an optimization used by pp_cmp and may be different
620        // even for equivalent layouts.
621        self.block.hash(state);
622        self.prev.hash(state);
623        self.next.hash(state);
624    }
625}
626
627/// Iterate over instructions in a block in layout order. See `Layout::block_insts()`.
628pub struct Insts<'f> {
629    layout: &'f Layout,
630    head: Option<Inst>,
631    tail: Option<Inst>,
632}
633
634impl<'f> Iterator for Insts<'f> {
635    type Item = Inst;
636
637    fn next(&mut self) -> Option<Inst> {
638        let rval = self.head;
639        if let Some(inst) = rval {
640            if self.head == self.tail {
641                self.head = None;
642                self.tail = None;
643            } else {
644                self.head = self.layout.insts[inst].next.into();
645            }
646        }
647        rval
648    }
649}
650
651impl<'f> DoubleEndedIterator for Insts<'f> {
652    fn next_back(&mut self) -> Option<Inst> {
653        let rval = self.tail;
654        if let Some(inst) = rval {
655            if self.head == self.tail {
656                self.head = None;
657                self.tail = None;
658            } else {
659                self.tail = self.layout.insts[inst].prev.into();
660            }
661        }
662        rval
663    }
664}
665
666/// A custom serialize and deserialize implementation for [`Layout`].
667///
668/// This doesn't use a derived implementation as [`Layout`] is a manual implementation of a linked
669/// list. Storing it directly as a regular list saves a lot of space.
670///
671/// The following format is used. (notated in EBNF form)
672///
673/// ```plain
674/// data = block_data * ;
675/// block_data = "block_id" , "cold" , "inst_count" , ( "inst_id" * ) ;
676/// ```
677#[cfg(feature = "enable-serde")]
678mod serde {
679    use ::serde::de::{Deserializer, Error, SeqAccess, Visitor};
680    use ::serde::ser::{SerializeSeq, Serializer};
681    use ::serde::{Deserialize, Serialize};
682    use core::fmt;
683    use core::marker::PhantomData;
684
685    use super::*;
686
687    impl Serialize for Layout {
688        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
689        where
690            S: Serializer,
691        {
692            let size = self.blocks().count() * 3
693                + self
694                    .blocks()
695                    .map(|block| self.block_insts(block).count())
696                    .sum::<usize>();
697            let mut seq = serializer.serialize_seq(Some(size))?;
698            for block in self.blocks() {
699                seq.serialize_element(&block)?;
700                seq.serialize_element(&self.blocks[block].cold)?;
701                seq.serialize_element(&u32::try_from(self.block_insts(block).count()).unwrap())?;
702                for inst in self.block_insts(block) {
703                    seq.serialize_element(&inst)?;
704                }
705            }
706            seq.end()
707        }
708    }
709
710    impl<'de> Deserialize<'de> for Layout {
711        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
712        where
713            D: Deserializer<'de>,
714        {
715            deserializer.deserialize_seq(LayoutVisitor {
716                marker: PhantomData,
717            })
718        }
719    }
720
721    struct LayoutVisitor {
722        marker: PhantomData<fn() -> Layout>,
723    }
724
725    impl<'de> Visitor<'de> for LayoutVisitor {
726        type Value = Layout;
727
728        fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
729            write!(formatter, "a `cranelift_codegen::ir::Layout`")
730        }
731
732        fn visit_seq<M>(self, mut access: M) -> Result<Self::Value, M::Error>
733        where
734            M: SeqAccess<'de>,
735        {
736            let mut layout = Layout::new();
737
738            while let Some(block) = access.next_element::<Block>()? {
739                layout.append_block(block);
740
741                let cold = access
742                    .next_element::<bool>()?
743                    .ok_or_else(|| Error::missing_field("cold"))?;
744                layout.blocks[block].cold = cold;
745
746                let count = access
747                    .next_element::<u32>()?
748                    .ok_or_else(|| Error::missing_field("count"))?;
749
750                for _ in 0..count {
751                    let inst = access
752                        .next_element::<Inst>()?
753                        .ok_or_else(|| Error::missing_field("inst"))?;
754                    layout.append_inst(inst, block);
755                }
756            }
757
758            Ok(layout)
759        }
760    }
761}
762
763#[cfg(test)]
764mod tests {
765    use super::*;
766    use crate::cursor::{Cursor, CursorPosition};
767    use crate::entity::EntityRef;
768    use crate::ir::{Block, Inst, SourceLoc};
769    use alloc::vec::Vec;
770    use core::cmp::Ordering;
771
772    #[test]
773    fn test_midpoint() {
774        assert_eq!(midpoint(0, 1), None);
775        assert_eq!(midpoint(0, 2), Some(1));
776        assert_eq!(midpoint(0, 3), Some(1));
777        assert_eq!(midpoint(0, 4), Some(2));
778        assert_eq!(midpoint(1, 4), Some(2));
779        assert_eq!(midpoint(2, 4), Some(3));
780        assert_eq!(midpoint(3, 4), None);
781        assert_eq!(midpoint(3, 4), None);
782    }
783
784    struct LayoutCursor<'f> {
785        /// Borrowed function layout. Public so it can be re-borrowed from this cursor.
786        pub layout: &'f mut Layout,
787        pos: CursorPosition,
788    }
789
790    impl<'f> Cursor for LayoutCursor<'f> {
791        fn position(&self) -> CursorPosition {
792            self.pos
793        }
794
795        fn set_position(&mut self, pos: CursorPosition) {
796            self.pos = pos;
797        }
798
799        fn srcloc(&self) -> SourceLoc {
800            unimplemented!()
801        }
802
803        fn set_srcloc(&mut self, _srcloc: SourceLoc) {
804            unimplemented!()
805        }
806
807        fn layout(&self) -> &Layout {
808            self.layout
809        }
810
811        fn layout_mut(&mut self) -> &mut Layout {
812            self.layout
813        }
814    }
815
816    impl<'f> LayoutCursor<'f> {
817        /// Create a new `LayoutCursor` for `layout`.
818        /// The cursor holds a mutable reference to `layout` for its entire lifetime.
819        pub fn new(layout: &'f mut Layout) -> Self {
820            Self {
821                layout,
822                pos: CursorPosition::Nowhere,
823            }
824        }
825    }
826
827    fn verify(layout: &mut Layout, blocks: &[(Block, &[Inst])]) {
828        // Check that blocks are inserted and instructions belong the right places.
829        // Check forward linkage with iterators.
830        // Check that layout sequence numbers are strictly monotonic.
831        {
832            let mut block_iter = layout.blocks();
833            for &(block, insts) in blocks {
834                assert!(layout.is_block_inserted(block));
835                assert_eq!(block_iter.next(), Some(block));
836
837                let mut seq = 0;
838                let mut inst_iter = layout.block_insts(block);
839                for &inst in insts {
840                    assert_eq!(layout.inst_block(inst), Some(block));
841                    assert_eq!(inst_iter.next(), Some(inst));
842                    assert!(layout.insts[inst].seq > seq);
843                    seq = layout.insts[inst].seq;
844                }
845                assert_eq!(inst_iter.next(), None);
846            }
847            assert_eq!(block_iter.next(), None);
848        }
849
850        // Check backwards linkage with a cursor.
851        let mut cur = LayoutCursor::new(layout);
852        for &(block, insts) in blocks.into_iter().rev() {
853            assert_eq!(cur.prev_block(), Some(block));
854            for &inst in insts.into_iter().rev() {
855                assert_eq!(cur.prev_inst(), Some(inst));
856            }
857            assert_eq!(cur.prev_inst(), None);
858        }
859        assert_eq!(cur.prev_block(), None);
860    }
861
862    #[test]
863    fn append_block() {
864        let mut layout = Layout::new();
865        let e0 = Block::new(0);
866        let e1 = Block::new(1);
867        let e2 = Block::new(2);
868
869        {
870            let imm = &layout;
871            assert!(!imm.is_block_inserted(e0));
872            assert!(!imm.is_block_inserted(e1));
873        }
874        verify(&mut layout, &[]);
875
876        layout.append_block(e1);
877        assert!(!layout.is_block_inserted(e0));
878        assert!(layout.is_block_inserted(e1));
879        assert!(!layout.is_block_inserted(e2));
880        let v: Vec<Block> = layout.blocks().collect();
881        assert_eq!(v, [e1]);
882
883        layout.append_block(e2);
884        assert!(!layout.is_block_inserted(e0));
885        assert!(layout.is_block_inserted(e1));
886        assert!(layout.is_block_inserted(e2));
887        let v: Vec<Block> = layout.blocks().collect();
888        assert_eq!(v, [e1, e2]);
889
890        layout.append_block(e0);
891        assert!(layout.is_block_inserted(e0));
892        assert!(layout.is_block_inserted(e1));
893        assert!(layout.is_block_inserted(e2));
894        let v: Vec<Block> = layout.blocks().collect();
895        assert_eq!(v, [e1, e2, e0]);
896
897        {
898            let imm = &layout;
899            let mut v = Vec::new();
900            for e in imm {
901                v.push(e);
902            }
903            assert_eq!(v, [e1, e2, e0]);
904        }
905
906        // Test cursor positioning.
907        let mut cur = LayoutCursor::new(&mut layout);
908        assert_eq!(cur.position(), CursorPosition::Nowhere);
909        assert_eq!(cur.next_inst(), None);
910        assert_eq!(cur.position(), CursorPosition::Nowhere);
911        assert_eq!(cur.prev_inst(), None);
912        assert_eq!(cur.position(), CursorPosition::Nowhere);
913
914        assert_eq!(cur.next_block(), Some(e1));
915        assert_eq!(cur.position(), CursorPosition::Before(e1));
916        assert_eq!(cur.next_inst(), None);
917        assert_eq!(cur.position(), CursorPosition::After(e1));
918        assert_eq!(cur.next_inst(), None);
919        assert_eq!(cur.position(), CursorPosition::After(e1));
920        assert_eq!(cur.next_block(), Some(e2));
921        assert_eq!(cur.prev_inst(), None);
922        assert_eq!(cur.position(), CursorPosition::Before(e2));
923        assert_eq!(cur.next_block(), Some(e0));
924        assert_eq!(cur.next_block(), None);
925        assert_eq!(cur.position(), CursorPosition::Nowhere);
926
927        // Backwards through the blocks.
928        assert_eq!(cur.prev_block(), Some(e0));
929        assert_eq!(cur.position(), CursorPosition::After(e0));
930        assert_eq!(cur.prev_block(), Some(e2));
931        assert_eq!(cur.prev_block(), Some(e1));
932        assert_eq!(cur.prev_block(), None);
933        assert_eq!(cur.position(), CursorPosition::Nowhere);
934    }
935
936    #[test]
937    fn insert_block() {
938        let mut layout = Layout::new();
939        let e0 = Block::new(0);
940        let e1 = Block::new(1);
941        let e2 = Block::new(2);
942
943        {
944            let imm = &layout;
945            assert!(!imm.is_block_inserted(e0));
946            assert!(!imm.is_block_inserted(e1));
947
948            let v: Vec<Block> = layout.blocks().collect();
949            assert_eq!(v, []);
950        }
951
952        layout.append_block(e1);
953        assert!(!layout.is_block_inserted(e0));
954        assert!(layout.is_block_inserted(e1));
955        assert!(!layout.is_block_inserted(e2));
956        verify(&mut layout, &[(e1, &[])]);
957
958        layout.insert_block(e2, e1);
959        assert!(!layout.is_block_inserted(e0));
960        assert!(layout.is_block_inserted(e1));
961        assert!(layout.is_block_inserted(e2));
962        verify(&mut layout, &[(e2, &[]), (e1, &[])]);
963
964        layout.insert_block(e0, e1);
965        assert!(layout.is_block_inserted(e0));
966        assert!(layout.is_block_inserted(e1));
967        assert!(layout.is_block_inserted(e2));
968        verify(&mut layout, &[(e2, &[]), (e0, &[]), (e1, &[])]);
969    }
970
971    #[test]
972    fn insert_block_after() {
973        let mut layout = Layout::new();
974        let e0 = Block::new(0);
975        let e1 = Block::new(1);
976        let e2 = Block::new(2);
977
978        layout.append_block(e1);
979        layout.insert_block_after(e2, e1);
980        verify(&mut layout, &[(e1, &[]), (e2, &[])]);
981
982        layout.insert_block_after(e0, e1);
983        verify(&mut layout, &[(e1, &[]), (e0, &[]), (e2, &[])]);
984    }
985
986    #[test]
987    fn append_inst() {
988        let mut layout = Layout::new();
989        let e1 = Block::new(1);
990
991        layout.append_block(e1);
992        let v: Vec<Inst> = layout.block_insts(e1).collect();
993        assert_eq!(v, []);
994
995        let i0 = Inst::new(0);
996        let i1 = Inst::new(1);
997        let i2 = Inst::new(2);
998
999        assert_eq!(layout.inst_block(i0), None);
1000        assert_eq!(layout.inst_block(i1), None);
1001        assert_eq!(layout.inst_block(i2), None);
1002
1003        layout.append_inst(i1, e1);
1004        assert_eq!(layout.inst_block(i0), None);
1005        assert_eq!(layout.inst_block(i1), Some(e1));
1006        assert_eq!(layout.inst_block(i2), None);
1007        let v: Vec<Inst> = layout.block_insts(e1).collect();
1008        assert_eq!(v, [i1]);
1009
1010        layout.append_inst(i2, e1);
1011        assert_eq!(layout.inst_block(i0), None);
1012        assert_eq!(layout.inst_block(i1), Some(e1));
1013        assert_eq!(layout.inst_block(i2), Some(e1));
1014        let v: Vec<Inst> = layout.block_insts(e1).collect();
1015        assert_eq!(v, [i1, i2]);
1016
1017        // Test double-ended instruction iterator.
1018        let v: Vec<Inst> = layout.block_insts(e1).rev().collect();
1019        assert_eq!(v, [i2, i1]);
1020
1021        layout.append_inst(i0, e1);
1022        verify(&mut layout, &[(e1, &[i1, i2, i0])]);
1023
1024        // Test cursor positioning.
1025        let mut cur = LayoutCursor::new(&mut layout).at_top(e1);
1026        assert_eq!(cur.position(), CursorPosition::Before(e1));
1027        assert_eq!(cur.prev_inst(), None);
1028        assert_eq!(cur.position(), CursorPosition::Before(e1));
1029        assert_eq!(cur.next_inst(), Some(i1));
1030        assert_eq!(cur.position(), CursorPosition::At(i1));
1031        assert_eq!(cur.next_inst(), Some(i2));
1032        assert_eq!(cur.next_inst(), Some(i0));
1033        assert_eq!(cur.prev_inst(), Some(i2));
1034        assert_eq!(cur.position(), CursorPosition::At(i2));
1035        assert_eq!(cur.next_inst(), Some(i0));
1036        assert_eq!(cur.position(), CursorPosition::At(i0));
1037        assert_eq!(cur.next_inst(), None);
1038        assert_eq!(cur.position(), CursorPosition::After(e1));
1039        assert_eq!(cur.next_inst(), None);
1040        assert_eq!(cur.position(), CursorPosition::After(e1));
1041        assert_eq!(cur.prev_inst(), Some(i0));
1042        assert_eq!(cur.prev_inst(), Some(i2));
1043        assert_eq!(cur.prev_inst(), Some(i1));
1044        assert_eq!(cur.prev_inst(), None);
1045        assert_eq!(cur.position(), CursorPosition::Before(e1));
1046
1047        // Test remove_inst.
1048        cur.goto_inst(i2);
1049        assert_eq!(cur.remove_inst(), i2);
1050        verify(cur.layout, &[(e1, &[i1, i0])]);
1051        assert_eq!(cur.layout.inst_block(i2), None);
1052        assert_eq!(cur.remove_inst(), i0);
1053        verify(cur.layout, &[(e1, &[i1])]);
1054        assert_eq!(cur.layout.inst_block(i0), None);
1055        assert_eq!(cur.position(), CursorPosition::After(e1));
1056        cur.layout.remove_inst(i1);
1057        verify(cur.layout, &[(e1, &[])]);
1058        assert_eq!(cur.layout.inst_block(i1), None);
1059    }
1060
1061    #[test]
1062    fn insert_inst() {
1063        let mut layout = Layout::new();
1064        let e1 = Block::new(1);
1065
1066        layout.append_block(e1);
1067        let v: Vec<Inst> = layout.block_insts(e1).collect();
1068        assert_eq!(v, []);
1069
1070        let i0 = Inst::new(0);
1071        let i1 = Inst::new(1);
1072        let i2 = Inst::new(2);
1073
1074        assert_eq!(layout.inst_block(i0), None);
1075        assert_eq!(layout.inst_block(i1), None);
1076        assert_eq!(layout.inst_block(i2), None);
1077
1078        layout.append_inst(i1, e1);
1079        assert_eq!(layout.inst_block(i0), None);
1080        assert_eq!(layout.inst_block(i1), Some(e1));
1081        assert_eq!(layout.inst_block(i2), None);
1082        let v: Vec<Inst> = layout.block_insts(e1).collect();
1083        assert_eq!(v, [i1]);
1084
1085        layout.insert_inst(i2, i1);
1086        assert_eq!(layout.inst_block(i0), None);
1087        assert_eq!(layout.inst_block(i1), Some(e1));
1088        assert_eq!(layout.inst_block(i2), Some(e1));
1089        let v: Vec<Inst> = layout.block_insts(e1).collect();
1090        assert_eq!(v, [i2, i1]);
1091
1092        layout.insert_inst(i0, i1);
1093        verify(&mut layout, &[(e1, &[i2, i0, i1])]);
1094    }
1095
1096    #[test]
1097    fn multiple_blocks() {
1098        let mut layout = Layout::new();
1099
1100        let e0 = Block::new(0);
1101        let e1 = Block::new(1);
1102
1103        assert_eq!(layout.entry_block(), None);
1104        layout.append_block(e0);
1105        assert_eq!(layout.entry_block(), Some(e0));
1106        layout.append_block(e1);
1107        assert_eq!(layout.entry_block(), Some(e0));
1108
1109        let i0 = Inst::new(0);
1110        let i1 = Inst::new(1);
1111        let i2 = Inst::new(2);
1112        let i3 = Inst::new(3);
1113
1114        layout.append_inst(i0, e0);
1115        layout.append_inst(i1, e0);
1116        layout.append_inst(i2, e1);
1117        layout.append_inst(i3, e1);
1118
1119        let v0: Vec<Inst> = layout.block_insts(e0).collect();
1120        let v1: Vec<Inst> = layout.block_insts(e1).collect();
1121        assert_eq!(v0, [i0, i1]);
1122        assert_eq!(v1, [i2, i3]);
1123    }
1124
1125    #[test]
1126    fn split_block() {
1127        let mut layout = Layout::new();
1128
1129        let e0 = Block::new(0);
1130        let e1 = Block::new(1);
1131        let e2 = Block::new(2);
1132
1133        let i0 = Inst::new(0);
1134        let i1 = Inst::new(1);
1135        let i2 = Inst::new(2);
1136        let i3 = Inst::new(3);
1137
1138        layout.append_block(e0);
1139        layout.append_inst(i0, e0);
1140        assert_eq!(layout.inst_block(i0), Some(e0));
1141        layout.split_block(e1, i0);
1142        assert_eq!(layout.inst_block(i0), Some(e1));
1143
1144        {
1145            let mut cur = LayoutCursor::new(&mut layout);
1146            assert_eq!(cur.next_block(), Some(e0));
1147            assert_eq!(cur.next_inst(), None);
1148            assert_eq!(cur.next_block(), Some(e1));
1149            assert_eq!(cur.next_inst(), Some(i0));
1150            assert_eq!(cur.next_inst(), None);
1151            assert_eq!(cur.next_block(), None);
1152
1153            // Check backwards links.
1154            assert_eq!(cur.prev_block(), Some(e1));
1155            assert_eq!(cur.prev_inst(), Some(i0));
1156            assert_eq!(cur.prev_inst(), None);
1157            assert_eq!(cur.prev_block(), Some(e0));
1158            assert_eq!(cur.prev_inst(), None);
1159            assert_eq!(cur.prev_block(), None);
1160        }
1161
1162        layout.append_inst(i1, e0);
1163        layout.append_inst(i2, e0);
1164        layout.append_inst(i3, e0);
1165        layout.split_block(e2, i2);
1166
1167        assert_eq!(layout.inst_block(i0), Some(e1));
1168        assert_eq!(layout.inst_block(i1), Some(e0));
1169        assert_eq!(layout.inst_block(i2), Some(e2));
1170        assert_eq!(layout.inst_block(i3), Some(e2));
1171
1172        {
1173            let mut cur = LayoutCursor::new(&mut layout);
1174            assert_eq!(cur.next_block(), Some(e0));
1175            assert_eq!(cur.next_inst(), Some(i1));
1176            assert_eq!(cur.next_inst(), None);
1177            assert_eq!(cur.next_block(), Some(e2));
1178            assert_eq!(cur.next_inst(), Some(i2));
1179            assert_eq!(cur.next_inst(), Some(i3));
1180            assert_eq!(cur.next_inst(), None);
1181            assert_eq!(cur.next_block(), Some(e1));
1182            assert_eq!(cur.next_inst(), Some(i0));
1183            assert_eq!(cur.next_inst(), None);
1184            assert_eq!(cur.next_block(), None);
1185
1186            assert_eq!(cur.prev_block(), Some(e1));
1187            assert_eq!(cur.prev_inst(), Some(i0));
1188            assert_eq!(cur.prev_inst(), None);
1189            assert_eq!(cur.prev_block(), Some(e2));
1190            assert_eq!(cur.prev_inst(), Some(i3));
1191            assert_eq!(cur.prev_inst(), Some(i2));
1192            assert_eq!(cur.prev_inst(), None);
1193            assert_eq!(cur.prev_block(), Some(e0));
1194            assert_eq!(cur.prev_inst(), Some(i1));
1195            assert_eq!(cur.prev_inst(), None);
1196            assert_eq!(cur.prev_block(), None);
1197        }
1198
1199        // Check `ProgramOrder`.
1200        assert_eq!(layout.pp_cmp(e2, e2), Ordering::Equal);
1201        assert_eq!(layout.pp_cmp(e2, i2), Ordering::Less);
1202        assert_eq!(layout.pp_cmp(i3, i2), Ordering::Greater)
1203    }
1204}
cranelift_codegen/ir/layout.rs

cranelift_codegen/ir/
layout.rs
