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

cranelift_codegen/ir/
layout.rs
