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, RegAllocError, VecExt};
9use alloc::vec::Vec;
10use smallvec::{smallvec, SmallVec};
11
12pub fn calculate<'a, SuccFn: Fn(Block) -> &'a [Block]>(
13    num_blocks: usize,
14    entry: Block,
15    visited_scratch: &mut Vec<bool>,
16    out: &mut Vec<Block>,
17    succ_blocks: SuccFn,
18) -> Result<(), RegAllocError> {
19    // State: visited-block map, and explicit DFS stack.
20    struct State<'a> {
21        block: Block,
22        succs: core::slice::Iter<'a, Block>,
23    }
24
25    let visited = visited_scratch.repopulate(num_blocks, false);
26    let mut stack: SmallVec<[State; 64]> = smallvec![];
27    out.clear();
28
29    let entry_visit = visited
30        .get_mut(entry.index())
31        .ok_or(RegAllocError::BB(entry))?;
32    *entry_visit = true;
33    stack.push(State {
34        block: entry,
35        succs: succ_blocks(entry).iter(),
36    });
37
38    while let Some(ref mut state) = stack.last_mut() {
39        // Perform one action: push to new succ, skip an already-visited succ, or pop.
40        if let Some(&succ) = state.succs.next() {
41            let succ_visit = visited
42                .get_mut(succ.index())
43                .ok_or(RegAllocError::BB(succ))?;
44            if !*succ_visit {
45                *succ_visit = true;
46                stack.push(State {
47                    block: succ,
48                    succs: succ_blocks(succ).iter(),
49                });
50            }
51        } else {
52            out.push(state.block);
53            stack.pop();
54        }
55    }
56    Ok(())
57}
regalloc2/postorder.rs

regalloc2/
postorder.rs
