use crate::ir::prelude::*;
use crate::ir::{DataFlowGraph, FunctionLayout, InstData};
use crate::opt::prelude::*;
use crate::pass::tcm::TemporalRegionGraph;
use std::{
collections::{HashMap, HashSet},
iter::once,
};
pub struct GlobalCommonSubexprElim;
impl Pass for GlobalCommonSubexprElim {
fn run_on_cfg(_ctx: &PassContext, unit: &mut impl UnitBuilder) -> bool {
info!("GCSE [{}]", unit.unit().name());
let pred = PredecessorTable::new(unit.dfg(), unit.func_layout());
let dt = DominatorTree::new(unit.func_layout(), &pred);
let temp_pt = PredecessorTable::new_temporal(unit.dfg(), unit.func_layout());
let temp_dt = DominatorTree::new(unit.func_layout(), &temp_pt);
let trg = TemporalRegionGraph::new(unit.dfg(), unit.func_layout());
let mut insts = vec![];
for bb in unit.func_layout().blocks() {
for inst in unit.func_layout().insts(bb) {
insts.push(inst);
}
}
let mut modified = false;
let mut values = HashMap::<InstData, HashSet<Value>>::new();
'outer: for inst in insts {
let opcode = unit.dfg()[inst].opcode();
if !unit.dfg().has_result(inst)
|| opcode == Opcode::Ld
|| opcode == Opcode::Var
|| opcode == Opcode::Sig
{
continue;
}
let value = unit.dfg().inst_result(inst);
trace!("Examining {}", inst.dump(unit.dfg(), unit.try_cfg()));
if let Some(aliases) = values.get_mut(&unit.dfg()[inst]) {
'inner: for &cv in aliases.iter() {
trace!(" Trying {}", cv.dump(unit.dfg()));
let cv_inst = unit.dfg().value_inst(cv);
let inst_bb = unit.func_layout().inst_block(inst).unwrap();
let cv_bb = unit.func_layout().inst_block(cv_inst).unwrap();
if trg[inst_bb] != trg[cv_bb] {
trace!(" Skipping because in other temporal region");
continue;
}
let which_dt = if opcode == Opcode::Prb { &temp_dt } else { &dt };
if which_dt.dominates(cv_bb, inst_bb) {
debug!(
"Replace {} with {}",
inst.dump(unit.dfg(), unit.try_cfg()),
cv.dump(unit.dfg()),
);
unit.dfg_mut().replace_use(value, cv);
unit.prune_if_unused(inst);
modified = true;
continue 'outer;
}
if which_dt.dominates(inst_bb, cv_bb) {
debug!(
"Replace {} with {}",
cv.dump(unit.dfg()),
value.dump(unit.dfg()),
);
unit.dfg_mut().replace_use(cv, value);
unit.prune_if_unused(cv_inst);
aliases.remove(&cv);
modified = true;
break 'inner;
}
trace!(
" Intersect(Dom({}), Dom({})):",
inst_bb.dump(unit.cfg()),
cv_bb.dump(unit.cfg())
);
for bb in which_dt
.dominators(inst_bb)
.intersection(&which_dt.dominators(cv_bb))
{
trace!(" {}", bb.dump(unit.cfg()));
}
let target_bb = which_dt
.dominators(inst_bb)
.intersection(which_dt.dominators(cv_bb))
.max_by(|&&bb_a, &&bb_b| {
if which_dt.dominates(bb_a, bb_b) {
std::cmp::Ordering::Less
} else {
std::cmp::Ordering::Greater
}
});
let target_bb = match target_bb {
Some(&bb) => bb,
None => continue,
};
trace!(
" Latest common dominator: {}",
target_bb.dump(unit.cfg())
);
debug!(
"Hoist {} up into {}",
inst.dump(unit.dfg(), unit.try_cfg()),
target_bb.dump(unit.cfg())
);
let fl = unit.func_layout_mut();
let term = fl.terminator(target_bb);
fl.remove_inst(inst);
fl.insert_inst_before(inst, term);
debug!(
"Replace {} with {}",
cv.dump(unit.dfg()),
value.dump(unit.dfg()),
);
unit.dfg_mut().replace_use(cv, value);
unit.prune_if_unused(cv_inst);
aliases.remove(&cv);
modified = true;
break 'inner;
}
}
values
.entry(unit.dfg()[inst].clone())
.or_insert_with(Default::default)
.insert(value);
}
modified
}
fn run_on_entity(_ctx: &PassContext, unit: &mut EntityBuilder) -> bool {
info!("GCSE [{}]", unit.unit().name());
let mut insts = vec![];
for inst in unit.inst_layout().insts() {
insts.push(inst);
}
let mut modified = false;
let mut values = HashMap::<InstData, Value>::new();
'outer: for inst in insts {
let opcode = unit.dfg()[inst].opcode();
if !unit.dfg().has_result(inst) || opcode == Opcode::Var || opcode == Opcode::Sig {
continue;
}
let value = unit.dfg().inst_result(inst);
trace!("Examining {}", inst.dump(unit.dfg(), unit.try_cfg()));
if let Some(&cv) = values.get(&unit.dfg()[inst]) {
debug!(
"Replace {} with {}",
inst.dump(unit.dfg(), unit.try_cfg()),
cv.dump(unit.dfg()),
);
unit.dfg_mut().replace_use(value, cv);
unit.prune_if_unused(inst);
modified = true;
}
else {
values.insert(unit.dfg()[inst].clone(), value);
}
}
modified
}
}
#[derive(Debug, Clone)]
pub struct PredecessorTable {
pred: HashMap<Block, HashSet<Block>>,
succ: HashMap<Block, HashSet<Block>>,
}
impl PredecessorTable {
pub fn new(dfg: &DataFlowGraph, layout: &FunctionLayout) -> Self {
let mut pred = HashMap::new();
let mut succ = HashMap::new();
for bb in layout.blocks() {
pred.insert(bb, HashSet::new());
}
for bb in layout.blocks() {
let term = layout.terminator(bb);
for to_bb in dfg[term].blocks() {
pred.get_mut(&to_bb).unwrap().insert(bb);
}
succ.insert(bb, dfg[term].blocks().iter().cloned().collect());
}
Self { pred, succ }
}
pub fn new_temporal(dfg: &DataFlowGraph, layout: &FunctionLayout) -> Self {
let mut pred = HashMap::new();
let mut succ = HashMap::new();
for bb in layout.blocks() {
pred.insert(bb, HashSet::new());
}
for bb in layout.blocks() {
let term = layout.terminator(bb);
if !dfg[term].opcode().is_temporal() {
for to_bb in dfg[term].blocks() {
pred.get_mut(&to_bb).unwrap().insert(bb);
}
succ.insert(bb, dfg[term].blocks().iter().cloned().collect());
}
}
Self { pred, succ }
}
pub fn pred_set(&self, bb: Block) -> &HashSet<Block> {
&self.pred[&bb]
}
pub fn succ_set(&self, bb: Block) -> &HashSet<Block> {
&self.succ[&bb]
}
pub fn pred(&self, bb: Block) -> impl Iterator<Item = Block> + Clone + '_ {
self.pred[&bb].iter().cloned()
}
pub fn succ(&self, bb: Block) -> impl Iterator<Item = Block> + Clone + '_ {
self.succ[&bb].iter().cloned()
}
pub fn is_sole_pred(&self, bb: Block, pred_of: Block) -> bool {
self.pred(pred_of).all(|x| x == bb)
}
pub fn is_sole_succ(&self, bb: Block, succ_of: Block) -> bool {
self.succ(succ_of).all(|x| x == bb)
}
}
#[derive(Debug, Clone)]
pub struct DominatorTree {
dominates: HashMap<Block, HashSet<Block>>,
dominated: HashMap<Block, HashSet<Block>>,
}
impl DominatorTree {
pub fn new(layout: &FunctionLayout, pred: &PredecessorTable) -> Self {
let all_blocks: HashSet<Block> = layout.blocks().collect();
let mut dominated = HashMap::<Block, HashSet<Block>>::new();
let entry_bb = layout.entry();
dominated.insert(entry_bb, Some(entry_bb).into_iter().collect());
for &bb in all_blocks.iter().filter(|&&bb| bb != entry_bb) {
dominated.insert(bb, all_blocks.clone());
}
loop {
let mut changes = false;
for &bb in all_blocks.iter().filter(|&&bb| bb != entry_bb) {
let mut isect = HashMap::<Block, usize>::new();
for &p in pred.pred(bb).flat_map(|p| dominated[&p].iter()) {
*isect.entry(p).or_insert_with(Default::default) += 1;
}
let isect = isect
.into_iter()
.filter(|&(_, c)| c == pred.pred_set(bb).len())
.map(|(bb, _)| bb);
let new_dom: HashSet<Block> = isect.chain(once(bb)).collect();
if dominated[&bb] != new_dom {
changes |= true;
dominated.insert(bb, new_dom);
}
}
if !changes {
break;
}
}
let mut dominates: HashMap<Block, HashSet<Block>> =
all_blocks.iter().map(|&bb| (bb, HashSet::new())).collect();
for (&bb, dom) in &dominated {
for d in dom {
dominates.get_mut(d).unwrap().insert(bb);
}
}
Self {
dominates,
dominated,
}
}
pub fn dominates(&self, dominator: Block, follower: Block) -> bool {
self.dominates
.get(&dominator)
.map(|d| d.contains(&follower))
.unwrap_or(false)
}
pub fn dominators(&self, follower: Block) -> &HashSet<Block> {
&self.dominated[&follower]
}
pub fn dominated_by(&self, dominator: Block) -> &HashSet<Block> {
&self.dominates[&dominator]
}
}