use crate::dominator_tree::DominatorTree;
use crate::entity::SparseSet;
use crate::ir::{Ebb, Layout};
use std::vec::Vec;
pub struct TopoOrder {
preferred: Vec<Ebb>,
next: usize,
visited: SparseSet<Ebb>,
stack: Vec<Ebb>,
}
impl TopoOrder {
pub fn new() -> Self {
Self {
preferred: Vec::new(),
next: 0,
visited: SparseSet::new(),
stack: Vec::new(),
}
}
pub fn clear(&mut self) {
self.preferred.clear();
self.next = 0;
self.visited.clear();
self.stack.clear();
}
pub fn reset<Ebbs>(&mut self, preferred: Ebbs)
where
Ebbs: IntoIterator<Item = Ebb>,
{
self.preferred.clear();
self.preferred.extend(preferred);
self.next = 0;
self.visited.clear();
self.stack.clear();
}
pub fn next(&mut self, layout: &Layout, domtree: &DominatorTree) -> Option<Ebb> {
while self.stack.is_empty() {
match self.preferred.get(self.next).cloned() {
None => return None,
Some(mut ebb) => {
self.next += 1;
while self.visited.insert(ebb).is_none() {
self.stack.push(ebb);
match domtree.idom(ebb) {
Some(idom) => ebb = layout.inst_ebb(idom).expect("idom not in layout"),
None => break,
}
}
}
}
}
self.stack.pop()
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::cursor::{Cursor, FuncCursor};
use crate::dominator_tree::DominatorTree;
use crate::flowgraph::ControlFlowGraph;
use crate::ir::{Function, InstBuilder};
use core::iter;
#[test]
fn empty() {
let func = Function::new();
let cfg = ControlFlowGraph::with_function(&func);
let domtree = DominatorTree::with_function(&func, &cfg);
let mut topo = TopoOrder::new();
assert_eq!(topo.next(&func.layout, &domtree), None);
topo.reset(func.layout.ebbs());
assert_eq!(topo.next(&func.layout, &domtree), None);
}
#[test]
fn simple() {
let mut func = Function::new();
let ebb0 = func.dfg.make_ebb();
let ebb1 = func.dfg.make_ebb();
{
let mut cur = FuncCursor::new(&mut func);
cur.insert_ebb(ebb0);
cur.ins().jump(ebb1, &[]);
cur.insert_ebb(ebb1);
cur.ins().jump(ebb1, &[]);
}
let cfg = ControlFlowGraph::with_function(&func);
let domtree = DominatorTree::with_function(&func, &cfg);
let mut topo = TopoOrder::new();
topo.reset(iter::once(ebb1));
assert_eq!(topo.next(&func.layout, &domtree), Some(ebb0));
assert_eq!(topo.next(&func.layout, &domtree), Some(ebb1));
assert_eq!(topo.next(&func.layout, &domtree), None);
}
}