Sha256: c23499b5eb8efd1b6df939255888e00d91259f9867abfdad2fd55339001cce9d
Contents?: true
Size: 1.43 KB
Versions: 29
Compression:
Stored size: 1.43 KB
Contents
/*
* Released under the terms of the Apache 2.0 license with LLVM
* exception. See `LICENSE` for details.
*/
//! Fast postorder computation.
use crate::Block;
use alloc::vec;
use alloc::vec::Vec;
use smallvec::{smallvec, SmallVec};
pub fn calculate<'a, SuccFn: Fn(Block) -> &'a [Block]>(
num_blocks: usize,
entry: Block,
succ_blocks: SuccFn,
) -> Vec<Block> {
let mut ret = vec![];
// State: visited-block map, and explicit DFS stack.
let mut visited = vec![false; num_blocks];
struct State<'a> {
block: Block,
succs: &'a [Block],
next_succ: usize,
}
let mut stack: SmallVec<[State; 64]> = smallvec![];
visited[entry.index()] = true;
stack.push(State {
block: entry,
succs: succ_blocks(entry),
next_succ: 0,
});
while let Some(ref mut state) = stack.last_mut() {
// Perform one action: push to new succ, skip an already-visited succ, or pop.
if state.next_succ < state.succs.len() {
let succ = state.succs[state.next_succ];
state.next_succ += 1;
if !visited[succ.index()] {
visited[succ.index()] = true;
stack.push(State {
block: succ,
succs: succ_blocks(succ),
next_succ: 0,
});
}
} else {
ret.push(state.block);
stack.pop();
}
}
ret
}
Version data entries
29 entries across 29 versions & 1 rubygems