regalloc2/
postorder.rs

1/*
2 * Released under the terms of the Apache 2.0 license with LLVM
3 * exception. See `LICENSE` for details.
4 */
5
6//! Fast postorder computation.
7
8use crate::Block;
9use smallvec::{smallvec, SmallVec};
10
11pub fn calculate<'a, SuccFn: Fn(Block) -> &'a [Block]>(
12    num_blocks: usize,
13    entry: Block,
14    succ_blocks: SuccFn,
15) -> Vec<Block> {
16    let mut ret = vec![];
17
18    // State: visited-block map, and explicit DFS stack.
19    let mut visited = vec![];
20    visited.resize(num_blocks, false);
21
22    struct State<'a> {
23        block: Block,
24        succs: &'a [Block],
25        next_succ: usize,
26    }
27    let mut stack: SmallVec<[State; 64]> = smallvec![];
28
29    visited[entry.index()] = true;
30    stack.push(State {
31        block: entry,
32        succs: succ_blocks(entry),
33        next_succ: 0,
34    });
35
36    while let Some(ref mut state) = stack.last_mut() {
37        // Perform one action: push to new succ, skip an already-visited succ, or pop.
38        if state.next_succ < state.succs.len() {
39            let succ = state.succs[state.next_succ];
40            state.next_succ += 1;
41            if !visited[succ.index()] {
42                visited[succ.index()] = true;
43                stack.push(State {
44                    block: succ,
45                    succs: succ_blocks(succ),
46                    next_succ: 0,
47                });
48            }
49        } else {
50            ret.push(state.block);
51            stack.pop();
52        }
53    }
54
55    ret
56}
regalloc2/postorder.rs

regalloc2/
postorder.rs
