use crate::dominator_tree::DominatorTree;
use crate::entity::entity_impl;
use crate::entity::SecondaryMap;
use crate::entity::{Keys, PrimaryMap};
use crate::flowgraph::{BasicBlock, ControlFlowGraph};
use crate::ir::{Ebb, Function, Layout};
use crate::packed_option::PackedOption;
use crate::timing;
use std::vec::Vec;
#[derive(Copy, Clone, PartialEq, Eq, Hash)]
pub struct Loop(u32);
entity_impl!(Loop, "loop");
pub struct LoopAnalysis {
loops: PrimaryMap<Loop, LoopData>,
ebb_loop_map: SecondaryMap<Ebb, PackedOption<Loop>>,
valid: bool,
}
struct LoopData {
header: Ebb,
parent: PackedOption<Loop>,
}
impl LoopData {
pub fn new(header: Ebb, parent: Option<Loop>) -> Self {
Self {
header,
parent: parent.into(),
}
}
}
impl LoopAnalysis {
pub fn new() -> Self {
Self {
valid: false,
loops: PrimaryMap::new(),
ebb_loop_map: SecondaryMap::new(),
}
}
pub fn loops(&self) -> Keys<Loop> {
self.loops.keys()
}
pub fn loop_header(&self, lp: Loop) -> Ebb {
self.loops[lp].header
}
pub fn loop_parent(&self, lp: Loop) -> Option<Loop> {
self.loops[lp].parent.expand()
}
pub fn is_in_loop(&self, ebb: Ebb, lp: Loop) -> bool {
let ebb_loop = self.ebb_loop_map[ebb];
match ebb_loop.expand() {
None => false,
Some(ebb_loop) => self.is_child_loop(ebb_loop, lp),
}
}
pub fn is_child_loop(&self, child: Loop, parent: Loop) -> bool {
let mut finger = Some(child);
while let Some(finger_loop) = finger {
if finger_loop == parent {
return true;
}
finger = self.loop_parent(finger_loop);
}
false
}
}
impl LoopAnalysis {
pub fn compute(&mut self, func: &Function, cfg: &ControlFlowGraph, domtree: &DominatorTree) {
let _tt = timing::loop_analysis();
self.loops.clear();
self.ebb_loop_map.clear();
self.ebb_loop_map.resize(func.dfg.num_ebbs());
self.find_loop_headers(cfg, domtree, &func.layout);
self.discover_loop_blocks(cfg, domtree, &func.layout);
self.valid = true;
}
pub fn is_valid(&self) -> bool {
self.valid
}
pub fn clear(&mut self) {
self.loops.clear();
self.ebb_loop_map.clear();
self.valid = false;
}
fn find_loop_headers(
&mut self,
cfg: &ControlFlowGraph,
domtree: &DominatorTree,
layout: &Layout,
) {
for &ebb in domtree.cfg_postorder().iter().rev() {
for BasicBlock {
inst: pred_inst, ..
} in cfg.pred_iter(ebb)
{
if domtree.dominates(ebb, pred_inst, layout) {
let lp = self.loops.push(LoopData::new(ebb, None));
self.ebb_loop_map[ebb] = lp.into();
break;
}
}
}
}
fn discover_loop_blocks(
&mut self,
cfg: &ControlFlowGraph,
domtree: &DominatorTree,
layout: &Layout,
) {
let mut stack: Vec<Ebb> = Vec::new();
for lp in self.loops().rev() {
for BasicBlock {
ebb: pred,
inst: pred_inst,
} in cfg.pred_iter(self.loops[lp].header)
{
if domtree.dominates(self.loops[lp].header, pred_inst, layout) {
stack.push(pred);
}
}
while let Some(node) = stack.pop() {
let continue_dfs: Option<Ebb>;
match self.ebb_loop_map[node].expand() {
None => {
self.ebb_loop_map[node] = PackedOption::from(lp);
continue_dfs = Some(node);
}
Some(node_loop) => {
let mut node_loop = node_loop;
let mut node_loop_parent_option = self.loops[node_loop].parent;
while let Some(node_loop_parent) = node_loop_parent_option.expand() {
if node_loop_parent == lp {
break;
} else {
node_loop = node_loop_parent;
node_loop_parent_option = self.loops[node_loop].parent;
}
}
match node_loop_parent_option.expand() {
Some(_) => continue_dfs = None,
None => {
if node_loop != lp {
self.loops[node_loop].parent = lp.into();
continue_dfs = Some(self.loops[node_loop].header)
} else {
continue_dfs = None
}
}
}
}
}
if let Some(continue_dfs) = continue_dfs {
for BasicBlock { ebb: pred, .. } in cfg.pred_iter(continue_dfs) {
stack.push(pred)
}
}
}
}
}
}
#[cfg(test)]
mod tests {
use crate::cursor::{Cursor, FuncCursor};
use crate::dominator_tree::DominatorTree;
use crate::flowgraph::ControlFlowGraph;
use crate::ir::{types, Function, InstBuilder};
use crate::loop_analysis::{Loop, LoopAnalysis};
use std::vec::Vec;
#[test]
fn nested_loops_detection() {
let mut func = Function::new();
let ebb0 = func.dfg.make_ebb();
let ebb1 = func.dfg.make_ebb();
let ebb2 = func.dfg.make_ebb();
let ebb3 = func.dfg.make_ebb();
let cond = func.dfg.append_ebb_param(ebb0, types::I32);
{
let mut cur = FuncCursor::new(&mut func);
cur.insert_ebb(ebb0);
cur.ins().jump(ebb1, &[]);
cur.insert_ebb(ebb1);
cur.ins().jump(ebb2, &[]);
cur.insert_ebb(ebb2);
cur.ins().brnz(cond, ebb1, &[]);
cur.ins().jump(ebb3, &[]);
cur.insert_ebb(ebb3);
cur.ins().brnz(cond, ebb0, &[]);
}
let mut loop_analysis = LoopAnalysis::new();
let mut cfg = ControlFlowGraph::new();
let mut domtree = DominatorTree::new();
cfg.compute(&func);
domtree.compute(&func, &cfg);
loop_analysis.compute(&func, &cfg, &domtree);
let loops = loop_analysis.loops().collect::<Vec<Loop>>();
assert_eq!(loops.len(), 2);
assert_eq!(loop_analysis.loop_header(loops[0]), ebb0);
assert_eq!(loop_analysis.loop_header(loops[1]), ebb1);
assert_eq!(loop_analysis.loop_parent(loops[1]), Some(loops[0]));
assert_eq!(loop_analysis.loop_parent(loops[0]), None);
assert_eq!(loop_analysis.is_in_loop(ebb0, loops[0]), true);
assert_eq!(loop_analysis.is_in_loop(ebb0, loops[1]), false);
assert_eq!(loop_analysis.is_in_loop(ebb1, loops[1]), true);
assert_eq!(loop_analysis.is_in_loop(ebb1, loops[0]), true);
assert_eq!(loop_analysis.is_in_loop(ebb2, loops[1]), true);
assert_eq!(loop_analysis.is_in_loop(ebb2, loops[0]), true);
assert_eq!(loop_analysis.is_in_loop(ebb3, loops[0]), true);
assert_eq!(loop_analysis.is_in_loop(ebb0, loops[1]), false);
}
#[test]
fn complex_loop_detection() {
let mut func = Function::new();
let ebb0 = func.dfg.make_ebb();
let ebb1 = func.dfg.make_ebb();
let ebb2 = func.dfg.make_ebb();
let ebb3 = func.dfg.make_ebb();
let ebb4 = func.dfg.make_ebb();
let ebb5 = func.dfg.make_ebb();
let cond = func.dfg.append_ebb_param(ebb0, types::I32);
{
let mut cur = FuncCursor::new(&mut func);
cur.insert_ebb(ebb0);
cur.ins().brnz(cond, ebb1, &[]);
cur.ins().jump(ebb3, &[]);
cur.insert_ebb(ebb1);
cur.ins().jump(ebb2, &[]);
cur.insert_ebb(ebb2);
cur.ins().brnz(cond, ebb1, &[]);
cur.ins().jump(ebb5, &[]);
cur.insert_ebb(ebb3);
cur.ins().jump(ebb4, &[]);
cur.insert_ebb(ebb4);
cur.ins().brnz(cond, ebb3, &[]);
cur.ins().jump(ebb5, &[]);
cur.insert_ebb(ebb5);
cur.ins().brnz(cond, ebb0, &[]);
}
let mut loop_analysis = LoopAnalysis::new();
let mut cfg = ControlFlowGraph::new();
let mut domtree = DominatorTree::new();
cfg.compute(&func);
domtree.compute(&func, &cfg);
loop_analysis.compute(&func, &cfg, &domtree);
let loops = loop_analysis.loops().collect::<Vec<Loop>>();
assert_eq!(loops.len(), 3);
assert_eq!(loop_analysis.loop_header(loops[0]), ebb0);
assert_eq!(loop_analysis.loop_header(loops[1]), ebb1);
assert_eq!(loop_analysis.loop_header(loops[2]), ebb3);
assert_eq!(loop_analysis.loop_parent(loops[1]), Some(loops[0]));
assert_eq!(loop_analysis.loop_parent(loops[2]), Some(loops[0]));
assert_eq!(loop_analysis.loop_parent(loops[0]), None);
assert_eq!(loop_analysis.is_in_loop(ebb0, loops[0]), true);
assert_eq!(loop_analysis.is_in_loop(ebb1, loops[1]), true);
assert_eq!(loop_analysis.is_in_loop(ebb2, loops[1]), true);
assert_eq!(loop_analysis.is_in_loop(ebb3, loops[2]), true);
assert_eq!(loop_analysis.is_in_loop(ebb4, loops[2]), true);
assert_eq!(loop_analysis.is_in_loop(ebb5, loops[0]), true);
}
}