luaur_code_gen/functions/
compute_block_ordering.rs

1use crate::functions::successors::successors;
2use crate::macros::codegen_assert::CODEGEN_ASSERT;
3use crate::records::block_ordering::BlockOrdering;
4use crate::records::ir_function::IrFunction;
5
6pub fn compute_block_ordering(
7    function: &mut IrFunction,
8    ordering: &mut Vec<BlockOrdering>,
9    pre_order: Option<&mut Vec<u32>>,
10    post_order: Option<&mut Vec<u32>>,
11) {
12    CODEGEN_ASSERT!(function.cfg.idoms.len() == function.blocks.len());
13
14    ordering.clear();
15    ordering.resize(function.blocks.len(), BlockOrdering::default());
16
17    let mut pre_order = pre_order;
18    let mut post_order = post_order;
19
20    if let Some(pre_order) = pre_order.as_deref_mut() {
21        pre_order.reserve(function.blocks.len());
22    }
23    if let Some(post_order) = post_order.as_deref_mut() {
24        post_order.reserve(function.blocks.len());
25    }
26
27    if function.blocks.is_empty() {
28        return;
29    }
30
31    let mut stack: Vec<(u32, u32)> = Vec::new();
32    let mut next_pre_order = 0u32;
33    let mut next_post_order = 0u32;
34
35    stack.push((0, 0));
36    ordering[0].visited = true;
37    ordering[0].preOrder = next_pre_order;
38    next_pre_order += 1;
39
40    while let Some((block_idx, mut it_pos)) = stack.pop() {
41        let children = successors(&function.cfg, block_idx);
42
43        if it_pos < children.size() as u32 {
44            let child_idx = children.operator_index(it_pos as usize);
45            it_pos += 1;
46            stack.push((block_idx, it_pos));
47
48            let child_ordering = &mut ordering[child_idx as usize];
49
50            if !child_ordering.visited {
51                child_ordering.visited = true;
52                child_ordering.depth = stack.len() as u32;
53                child_ordering.preOrder = next_pre_order;
54                next_pre_order += 1;
55
56                if let Some(pre_order) = pre_order.as_deref_mut() {
57                    pre_order.push(block_idx);
58                }
59
60                stack.push((child_idx, 0));
61            }
62        } else {
63            ordering[block_idx as usize].postOrder = next_post_order;
64            next_post_order += 1;
65
66            if let Some(post_order) = post_order.as_deref_mut() {
67                post_order.push(block_idx);
68            }
69        }
70    }
71}
luaur_code_gen/functions/compute_block_ordering.rs

luaur_code_gen/functions/
compute_block_ordering.rs
