fe_mir/analysis/
post_domtree.rs

1//! This module contains implementation of `Post Dominator Tree`.
2
3use id_arena::{ArenaBehavior, DefaultArenaBehavior};
4
5use super::{cfg::ControlFlowGraph, domtree::DomTree};
6
7use crate::ir::{BasicBlock, BasicBlockId, FunctionBody};
8
9#[derive(Debug)]
10pub struct PostDomTree {
11    /// Dummy entry block to calculate post dom tree.
12    dummy_entry: BasicBlockId,
13    /// Canonical dummy exit block to calculate post dom tree. All blocks ends
14    /// with `return` has an edge to this block.
15    dummy_exit: BasicBlockId,
16
17    /// Dominator tree of reverse control flow graph.
18    domtree: DomTree,
19}
20
21impl PostDomTree {
22    pub fn compute(func: &FunctionBody) -> Self {
23        let mut rcfg = ControlFlowGraph::compute(func);
24
25        let real_entry = rcfg.entry();
26
27        let dummy_entry = Self::make_dummy_block();
28        let dummy_exit = Self::make_dummy_block();
29        // Add edges from dummy entry block to real entry block and dummy exit block.
30        rcfg.add_edge(dummy_entry, real_entry);
31        rcfg.add_edge(dummy_entry, dummy_exit);
32
33        // Add edges from real exit blocks to dummy exit block.
34        for exit in std::mem::take(&mut rcfg.exits) {
35            rcfg.add_edge(exit, dummy_exit);
36        }
37
38        rcfg.reverse_edge(dummy_exit, vec![dummy_entry]);
39        let domtree = DomTree::compute(&rcfg);
40
41        Self {
42            dummy_entry,
43            dummy_exit,
44            domtree,
45        }
46    }
47
48    pub fn post_idom(&self, block: BasicBlockId) -> PostIDom {
49        match self.domtree.idom(block).unwrap() {
50            block if block == self.dummy_entry => PostIDom::DummyEntry,
51            block if block == self.dummy_exit => PostIDom::DummyExit,
52            other => PostIDom::Block(other),
53        }
54    }
55
56    /// Returns `true` if block is reachable from the exit blocks.
57    pub fn is_reachable(&self, block: BasicBlockId) -> bool {
58        self.domtree.is_reachable(block)
59    }
60
61    fn make_dummy_block() -> BasicBlockId {
62        let arena_id = DefaultArenaBehavior::<BasicBlock>::new_arena_id();
63        DefaultArenaBehavior::new_id(arena_id, 0)
64    }
65}
66
67#[derive(Debug, Clone, Copy, PartialEq, Eq)]
68pub enum PostIDom {
69    DummyEntry,
70    DummyExit,
71    Block(BasicBlockId),
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    use crate::ir::{body_builder::BodyBuilder, FunctionId, SourceInfo, TypeId};
79
80    fn body_builder() -> BodyBuilder {
81        BodyBuilder::new(FunctionId(0), SourceInfo::dummy())
82    }
83
84    #[test]
85    fn test_if_else_merge() {
86        let mut builder = body_builder();
87        let then_block = builder.make_block();
88        let else_block = builder.make_block();
89        let merge_block = builder.make_block();
90
91        let dummy_ty = TypeId(0);
92        let v0 = builder.make_imm_from_bool(true, dummy_ty);
93        builder.branch(v0, then_block, else_block, SourceInfo::dummy());
94
95        builder.move_to_block(then_block);
96        builder.jump(merge_block, SourceInfo::dummy());
97
98        builder.move_to_block(else_block);
99        builder.jump(merge_block, SourceInfo::dummy());
100
101        builder.move_to_block(merge_block);
102        let dummy_value = builder.make_unit(dummy_ty);
103        builder.ret(dummy_value, SourceInfo::dummy());
104
105        let func = builder.build();
106
107        let post_dom_tree = PostDomTree::compute(&func);
108        let entry_block = func.order.entry();
109        assert_eq!(
110            post_dom_tree.post_idom(entry_block),
111            PostIDom::Block(merge_block)
112        );
113        assert_eq!(
114            post_dom_tree.post_idom(then_block),
115            PostIDom::Block(merge_block)
116        );
117        assert_eq!(
118            post_dom_tree.post_idom(else_block),
119            PostIDom::Block(merge_block)
120        );
121        assert_eq!(post_dom_tree.post_idom(merge_block), PostIDom::DummyExit);
122    }
123
124    #[test]
125    fn test_if_else_return() {
126        let mut builder = body_builder();
127        let then_block = builder.make_block();
128        let else_block = builder.make_block();
129        let merge_block = builder.make_block();
130
131        let dummy_ty = TypeId(0);
132        let dummy_value = builder.make_unit(dummy_ty);
133        let v0 = builder.make_imm_from_bool(true, dummy_ty);
134        builder.branch(v0, then_block, else_block, SourceInfo::dummy());
135
136        builder.move_to_block(then_block);
137        builder.jump(merge_block, SourceInfo::dummy());
138
139        builder.move_to_block(else_block);
140        builder.ret(dummy_value, SourceInfo::dummy());
141
142        builder.move_to_block(merge_block);
143        builder.ret(dummy_value, SourceInfo::dummy());
144
145        let func = builder.build();
146
147        let post_dom_tree = PostDomTree::compute(&func);
148        let entry_block = func.order.entry();
149        assert_eq!(post_dom_tree.post_idom(entry_block), PostIDom::DummyExit,);
150        assert_eq!(
151            post_dom_tree.post_idom(then_block),
152            PostIDom::Block(merge_block),
153        );
154        assert_eq!(post_dom_tree.post_idom(else_block), PostIDom::DummyExit);
155        assert_eq!(post_dom_tree.post_idom(merge_block), PostIDom::DummyExit);
156    }
157
158    #[test]
159    fn test_if_non_else() {
160        let mut builder = body_builder();
161        let then_block = builder.make_block();
162        let merge_block = builder.make_block();
163
164        let dummy_ty = TypeId(0);
165        let dummy_value = builder.make_unit(dummy_ty);
166        let v0 = builder.make_imm_from_bool(true, dummy_ty);
167        builder.branch(v0, then_block, merge_block, SourceInfo::dummy());
168
169        builder.move_to_block(then_block);
170        builder.jump(merge_block, SourceInfo::dummy());
171
172        builder.move_to_block(merge_block);
173        builder.ret(dummy_value, SourceInfo::dummy());
174
175        let func = builder.build();
176
177        let post_dom_tree = PostDomTree::compute(&func);
178        let entry_block = func.order.entry();
179        assert_eq!(
180            post_dom_tree.post_idom(entry_block),
181            PostIDom::Block(merge_block),
182        );
183        assert_eq!(
184            post_dom_tree.post_idom(then_block),
185            PostIDom::Block(merge_block),
186        );
187        assert_eq!(post_dom_tree.post_idom(merge_block), PostIDom::DummyExit);
188    }
189
190    #[test]
191    fn test_loop() {
192        let mut builder = body_builder();
193        let block1 = builder.make_block();
194        let block2 = builder.make_block();
195        let block3 = builder.make_block();
196        let block4 = builder.make_block();
197
198        let dummy_ty = TypeId(0);
199        let v0 = builder.make_imm_from_bool(true, dummy_ty);
200
201        builder.branch(v0, block1, block2, SourceInfo::dummy());
202
203        builder.move_to_block(block1);
204        builder.jump(block3, SourceInfo::dummy());
205
206        builder.move_to_block(block2);
207        builder.branch(v0, block3, block4, SourceInfo::dummy());
208
209        builder.move_to_block(block3);
210        let dummy_value = builder.make_unit(dummy_ty);
211        builder.ret(dummy_value, SourceInfo::dummy());
212
213        builder.move_to_block(block4);
214        builder.jump(block2, SourceInfo::dummy());
215
216        let func = builder.build();
217
218        let post_dom_tree = PostDomTree::compute(&func);
219        let entry_block = func.order.entry();
220        assert_eq!(
221            post_dom_tree.post_idom(entry_block),
222            PostIDom::Block(block3),
223        );
224        assert_eq!(post_dom_tree.post_idom(block1), PostIDom::Block(block3));
225        assert_eq!(post_dom_tree.post_idom(block2), PostIDom::Block(block3));
226        assert_eq!(post_dom_tree.post_idom(block3), PostIDom::DummyExit);
227        assert_eq!(post_dom_tree.post_idom(block4), PostIDom::Block(block2));
228    }
229
230    #[test]
231    fn test_pd_complex() {
232        let mut builder = body_builder();
233        let block1 = builder.make_block();
234        let block2 = builder.make_block();
235        let block3 = builder.make_block();
236        let block4 = builder.make_block();
237        let block5 = builder.make_block();
238        let block6 = builder.make_block();
239        let block7 = builder.make_block();
240
241        let dummy_ty = TypeId(0);
242        let v0 = builder.make_imm_from_bool(true, dummy_ty);
243
244        builder.branch(v0, block1, block2, SourceInfo::dummy());
245
246        builder.move_to_block(block1);
247        builder.jump(block6, SourceInfo::dummy());
248
249        builder.move_to_block(block2);
250        builder.branch(v0, block3, block4, SourceInfo::dummy());
251
252        builder.move_to_block(block3);
253        builder.jump(block5, SourceInfo::dummy());
254
255        builder.move_to_block(block4);
256        builder.jump(block5, SourceInfo::dummy());
257
258        builder.move_to_block(block5);
259        builder.jump(block6, SourceInfo::dummy());
260
261        builder.move_to_block(block6);
262        builder.jump(block7, SourceInfo::dummy());
263
264        builder.move_to_block(block7);
265        let dummy_value = builder.make_unit(dummy_ty);
266        builder.ret(dummy_value, SourceInfo::dummy());
267
268        let func = builder.build();
269
270        let post_dom_tree = PostDomTree::compute(&func);
271        let entry_block = func.order.entry();
272        assert_eq!(
273            post_dom_tree.post_idom(entry_block),
274            PostIDom::Block(block6),
275        );
276        assert_eq!(post_dom_tree.post_idom(block1), PostIDom::Block(block6));
277        assert_eq!(post_dom_tree.post_idom(block2), PostIDom::Block(block5));
278        assert_eq!(post_dom_tree.post_idom(block3), PostIDom::Block(block5));
279        assert_eq!(post_dom_tree.post_idom(block4), PostIDom::Block(block5));
280        assert_eq!(post_dom_tree.post_idom(block5), PostIDom::Block(block6));
281        assert_eq!(post_dom_tree.post_idom(block6), PostIDom::Block(block7));
282        assert_eq!(post_dom_tree.post_idom(block7), PostIDom::DummyExit);
283    }
284}
fe_mir/analysis/post_domtree.rs

fe_mir/analysis/
post_domtree.rs
