llhd/ir/
layout.rs

1// Copyright (c) 2017-2021 Fabian Schuiki
2
3//! Instruction and BB ordering.
4
5use crate::{
6    ir::{Block, Inst},
7    table::SecondaryTable,
8};
9use std::collections::HashMap;
10
11/// Determines the order of instructions and BBs in a `Function` or `Process`.
12#[derive(Default, Serialize, Deserialize)]
13pub(super) struct FunctionLayout {
14    /// A linked list of BBs in layout order.
15    pub(super) bbs: SecondaryTable<Block, BlockNode>,
16    /// The first BB in the layout.
17    pub(super) first_bb: Option<Block>,
18    /// The last BB in the layout.
19    pub(super) last_bb: Option<Block>,
20    /// Lookup table to find the BB that contains an instruction.
21    pub(super) inst_map: HashMap<Inst, Block>,
22}
23
24/// A node in the layout's double-linked list of BBs.
25#[derive(Default, Serialize, Deserialize)]
26pub(super) struct BlockNode {
27    pub(super) prev: Option<Block>,
28    pub(super) next: Option<Block>,
29    pub(super) layout: InstLayout,
30}
31
32/// Determines the order of instructions.
33#[derive(Default, Serialize, Deserialize)]
34pub(super) struct InstLayout {
35    /// A linked list of instructions in layout order.
36    insts: SecondaryTable<Inst, InstNode>,
37    /// The first instruction in the layout.
38    first_inst: Option<Inst>,
39    /// The last instruction in the layout.
40    last_inst: Option<Inst>,
41}
42
43/// A node in the layout's double-linked list of BBs.
44#[derive(Default, Serialize, Deserialize)]
45struct InstNode {
46    prev: Option<Inst>,
47    next: Option<Inst>,
48}
49
50impl FunctionLayout {
51    /// Add a mapping from an instruction to the block that contains it.
52    pub(super) fn map_inst(&mut self, inst: Inst, bb: Block) {
53        match self.inst_map.insert(inst, bb) {
54            Some(old_bb) => panic!(
55                "inst {} already inserted in {}, now being inserted into {}",
56                inst, old_bb, bb
57            ),
58            None => (),
59        }
60    }
61
62    /// Remove a mapping from an instruction to the block that contains it.
63    pub(super) fn unmap_inst(&mut self, inst: Inst) {
64        match self.inst_map.remove(&inst) {
65            Some(_) => (),
66            None => panic!("inst {} was not inserted", inst),
67        }
68    }
69}
70
71impl InstLayout {
72    /// Append an instruction to the end of the function.
73    pub fn append_inst(&mut self, inst: Inst) {
74        self.insts.add(
75            inst,
76            InstNode {
77                prev: self.last_inst,
78                next: None,
79            },
80        );
81        if let Some(prev) = self.last_inst {
82            self.insts[prev].next = Some(inst);
83        }
84        if self.first_inst.is_none() {
85            self.first_inst = Some(inst);
86        }
87        self.last_inst = Some(inst);
88    }
89
90    /// Prepend an instruction to the beginning of the function.
91    pub fn prepend_inst(&mut self, inst: Inst) {
92        self.insts.add(
93            inst,
94            InstNode {
95                prev: None,
96                next: self.first_inst,
97            },
98        );
99        if let Some(next) = self.first_inst {
100            self.insts[next].prev = Some(inst);
101        }
102        if self.last_inst.is_none() {
103            self.last_inst = Some(inst);
104        }
105        self.first_inst = Some(inst);
106    }
107
108    /// Insert an instruction after another instruction.
109    pub fn insert_inst_after(&mut self, inst: Inst, after: Inst) {
110        self.insts.add(
111            inst,
112            InstNode {
113                prev: Some(after),
114                next: self.insts[after].next,
115            },
116        );
117        if let Some(next) = self.insts[after].next {
118            self.insts[next].prev = Some(inst);
119        }
120        self.insts[after].next = Some(inst);
121        if self.last_inst == Some(after) {
122            self.last_inst = Some(inst);
123        }
124    }
125
126    /// Insert an instruction before another instruction.
127    pub fn insert_inst_before(&mut self, inst: Inst, before: Inst) {
128        self.insts.add(
129            inst,
130            InstNode {
131                prev: self.insts[before].prev,
132                next: Some(before),
133            },
134        );
135        if let Some(prev) = self.insts[before].prev {
136            self.insts[prev].next = Some(inst);
137        }
138        self.insts[before].prev = Some(inst);
139        if self.first_inst == Some(before) {
140            self.first_inst = Some(inst);
141        }
142    }
143
144    /// Remove an instruction from the function.
145    pub fn remove_inst(&mut self, inst: Inst) {
146        let node = self.insts.remove(inst).unwrap();
147        if let Some(next) = node.next {
148            self.insts[next].prev = node.prev;
149        }
150        if let Some(prev) = node.prev {
151            self.insts[prev].next = node.next;
152        }
153        if self.first_inst == Some(inst) {
154            self.first_inst = node.next;
155        }
156        if self.last_inst == Some(inst) {
157            self.last_inst = node.prev;
158        }
159    }
160
161    /// Return an iterator over all instructions in layout order.
162    pub fn insts<'a>(&'a self) -> impl Iterator<Item = Inst> + 'a {
163        std::iter::successors(self.first_inst, move |&inst| self.next_inst(inst))
164    }
165
166    /// Get the first instruction in the layout.
167    pub fn first_inst(&self) -> Option<Inst> {
168        self.first_inst
169    }
170
171    /// Get the last instruction in the layout.
172    pub fn last_inst(&self) -> Option<Inst> {
173        self.last_inst
174    }
175
176    /// Get the instruction preceding `inst` in the layout.
177    pub fn prev_inst(&self, inst: Inst) -> Option<Inst> {
178        self.insts[inst].prev
179    }
180
181    /// Get the instruction following `inst` in the layout.
182    pub fn next_inst(&self, inst: Inst) -> Option<Inst> {
183        self.insts[inst].next
184    }
185}
llhd/ir/layout.rs

llhd/ir/
layout.rs
