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

cranelift_codegen/ir/
layout.rs
