use crate::{
analysis::{TemporalRegion, TemporalRegionGraph},
ir::{prelude::*, InstData},
opt::prelude::*,
value::IntValue,
};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
pub struct Desequentialization;
impl Pass for Desequentialization {
fn run_on_cfg(ctx: &PassContext, unit: &mut UnitBuilder) -> bool {
if unit.kind() == UnitKind::Process {
match deseq_process(ctx, unit) {
Some(entity) => {
*unit.data() = entity;
true
}
_ => false,
}
} else {
false
}
}
}
fn deseq_process(ctx: &PassContext, unit: &mut UnitBuilder) -> Option<UnitData> {
info!("Deseq [{}]", unit.name());
let trg = unit.trg();
if trg.regions().count() != 2 {
trace!("Skipping (incorrect number of TRs)");
return None;
}
let (tr0, tr1) = {
let mut it = trg.regions();
(it.next().unwrap().id, it.next().unwrap().id)
};
if !trg[tr0].entry {
trace!("Skipping (TR0 is not entry)");
return None;
}
if trg[tr1].entry {
trace!("Skipping (TR1 is entry)");
return None;
}
trace!("Head region {}, trigger region {}", tr0, tr1);
let (wait_inst, sensitivity) = {
let mut it = trg[tr0].tail_insts();
let inst = match it.next() {
Some(i) => i,
None => {
trace!("Skipping ({} has no tail inst)", tr0);
return None;
}
};
let data = &unit[inst];
let sensitivity: BTreeSet<_> = match data.opcode() {
Opcode::Wait => data.args().iter().cloned().collect(),
Opcode::WaitTime => data.args().iter().skip(1).cloned().collect(),
_ => {
trace!("Skipping ({} tail inst is not a wait)", tr0);
return None;
}
};
(inst, sensitivity)
};
trace!("Wait Inst: {}", wait_inst.dump(&unit));
trace!("Sensitivity: {:?}", sensitivity);
let tr0_num_bb = trg[tr0].blocks().count();
let tr1_num_bb = trg[tr1].blocks().count();
if tr0_num_bb != 1 || tr1_num_bb != 1 {
trace!(
"Skipping ({} TR0 blocks, {} TR1 blocks, instead of 1 each)",
tr0_num_bb,
tr1_num_bb
);
return None;
}
let mut all_drives = HashSet::new();
let mut conds = vec![];
for bb in unit.blocks() {
for inst in unit.insts(bb) {
let data = &unit[inst];
if data.opcode() == Opcode::DrvCond {
trace!("Canonicalizing condition of {}", inst.dump(&unit));
conds.push((
inst,
bb,
canonicalize(ctx, unit, &trg, data.args()[3], false),
));
all_drives.insert(inst);
} else if data.opcode() == Opcode::Drv {
all_drives.insert(inst);
}
}
}
let triggers: Vec<(Inst, Block, Vec<Trigger>)> = conds
.iter()
.flat_map(|(inst, bb, dnf)| {
detect_triggers(ctx, unit, tr0, tr1, dnf).map(|trig| (*inst, *bb, trig))
})
.collect();
let mut entity = UnitData::new(UnitKind::Entity, unit.name().clone(), unit.sig().clone());
let mut builder = UnitBuilder::new_anonymous(&mut entity);
for arg in unit.unit().sig().args() {
if let Some(name) = unit.get_name(unit.arg_value(arg)) {
let v = builder.arg_value(arg);
builder.set_name(v, name.to_string());
}
}
let mut mig = Migrator::new(unit, &mut builder, &trg, tr0, tr1);
let mut migrated = true;
for (inst, bb, trigs) in triggers {
migrated &= mig.migrate_drive(inst, bb, &trigs);
}
all_drives
.difference(&mig.migrated_drives)
.for_each(|inst| {
migrated = false;
trace!("Skipping ({} not migrated)", inst.dump(&unit));
});
if migrated {
Some(entity)
} else {
trace!("Process {} not migrated", unit.name());
None
}
}
fn canonicalize(
ctx: &PassContext,
unit: &UnitBuilder,
trg: &TemporalRegionGraph,
cond: Value,
inv: bool,
) -> Dnf {
let dnf = canonicalize_inner(ctx, unit, trg, cond, inv);
let desc = if let Some(inst) = unit.get_value_inst(cond) {
inst.dump(&unit).to_string()
} else {
cond.dump(&unit).to_string()
};
trace!(
" {} {{ {} }} => {}",
if inv { "neg" } else { "pos" },
desc,
dnf.dump(&unit),
);
dnf
}
fn canonicalize_inner(
ctx: &PassContext,
unit: &UnitBuilder,
trg: &TemporalRegionGraph,
cond: Value,
inv: bool,
) -> Dnf {
let dfg = unit;
let ty = unit.value_type(cond);
if ty != crate::ty::int_ty(1) {
return Dnf::single(Term::Invalid(cond), inv);
}
if let Some(inst) = unit.get_value_inst(cond) {
let data = &dfg[inst];
match data.opcode() {
Opcode::ConstInt => {
return Dnf::single(Term::Zero, data.get_const_int().unwrap().is_one() ^ inv);
}
Opcode::Not => return canonicalize(ctx, unit, trg, data.args()[0], !inv),
Opcode::And | Opcode::Or => {
let lhs = canonicalize(ctx, unit, trg, data.args()[0], inv);
let rhs = canonicalize(ctx, unit, trg, data.args()[1], inv);
let out = match (data.opcode(), inv) {
(Opcode::And, false) | (Opcode::Or, true) => Dnf::and(&lhs, &rhs),
(Opcode::And, true) | (Opcode::Or, false) => Dnf::or(&lhs, &rhs),
_ => unreachable!(),
};
return out;
}
Opcode::Xor | Opcode::Eq | Opcode::Neq => {
let lhs_pos = canonicalize(ctx, unit, trg, data.args()[0], false);
let rhs_pos = canonicalize(ctx, unit, trg, data.args()[1], false);
let lhs_neg = canonicalize(ctx, unit, trg, data.args()[0], true);
let rhs_neg = canonicalize(ctx, unit, trg, data.args()[1], true);
let polarity = match data.opcode() {
Opcode::Eq => !inv,
_ => inv,
};
let out = if polarity {
Dnf::or(&Dnf::and(&lhs_pos, &rhs_pos), &Dnf::and(&lhs_neg, &rhs_neg))
} else {
Dnf::or(&Dnf::and(&lhs_pos, &rhs_neg), &Dnf::and(&lhs_neg, &rhs_pos))
};
return out;
}
Opcode::Prb => {
let bb = unit.inst_block(inst).unwrap();
return Dnf::single(Term::Signal(data.args()[0], trg[bb]), inv);
}
_ => (),
}
}
Dnf::single(Term::Invalid(cond), inv)
}
struct Dnf(BTreeSet<BTreeMap<Term, bool>>);
impl Dnf {
pub fn zero() -> Dnf {
Dnf(BTreeSet::new())
}
pub fn one() -> Dnf {
let mut set = BTreeSet::new();
set.insert(Default::default());
Dnf(set)
}
pub fn single(term: Term, inv: bool) -> Dnf {
match term {
Term::Zero if inv => Self::one(),
Term::Zero => Self::zero(),
_ => {
let mut set = BTreeSet::new();
set.insert(Some((term, inv)).into_iter().collect());
Dnf(set)
}
}
}
pub fn dump<'a>(&'a self, unit: &Unit<'a>) -> DnfDumper<'a> {
DnfDumper(self, *unit)
}
pub fn dump_term<'a>(term: &'a BTreeMap<Term, bool>, unit: &Unit<'a>) -> DnfTermDumper<'a> {
DnfTermDumper(term, *unit)
}
pub fn or(lhs: &Dnf, rhs: &Dnf) -> Dnf {
let lhs = lhs.0.iter().cloned();
let rhs = rhs.0.iter().cloned();
Dnf(lhs.chain(rhs).collect())
}
pub fn and(lhs: &Dnf, rhs: &Dnf) -> Dnf {
let mut set = BTreeSet::new();
for lhs_term in &lhs.0 {
for rhs_term in &rhs.0 {
if let Some(term) = Self::and_term(lhs_term, rhs_term) {
set.insert(term);
}
}
}
Dnf(set)
}
fn and_term(
lhs: &BTreeMap<Term, bool>,
rhs: &BTreeMap<Term, bool>,
) -> Option<BTreeMap<Term, bool>> {
let mut out = BTreeMap::new();
for (term, &inv) in lhs.iter().chain(rhs.iter()) {
if out.insert(term.clone(), inv) == Some(!inv) {
return None;
}
}
Some(out)
}
}
struct DnfDumper<'a>(&'a Dnf, Unit<'a>);
impl std::fmt::Display for DnfDumper<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
use std::iter::{once, repeat};
if (self.0).0.is_empty() {
return write!(f, "0");
}
if (self.0).0.len() == 1 {
if (self.0).0.iter().next().unwrap().is_empty() {
return write!(f, "1");
}
}
for (vs, sep) in (self.0).0.iter().zip(once("").chain(repeat(" | "))) {
write!(f, "{}({})", sep, Dnf::dump_term(vs, &self.1))?;
}
Ok(())
}
}
struct DnfTermDumper<'a>(&'a BTreeMap<Term, bool>, Unit<'a>);
impl std::fmt::Display for DnfTermDumper<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
use std::iter::{once, repeat};
if (self.0).is_empty() {
return write!(f, "1");
}
for ((term, inv), sep) in self.0.iter().zip(once("").chain(repeat(" & "))) {
write!(f, "{}", sep)?;
if *inv {
write!(f, "!")?;
}
match term {
Term::Zero => write!(f, "0")?,
Term::Signal(sig, tr) => write!(f, "{}@{}", sig.dump(&self.1), tr)?,
Term::Invalid(v) => write!(f, "{}?", v.dump(&self.1))?,
}
}
Ok(())
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
enum Term {
Zero,
Signal(Value, TemporalRegion),
Invalid(Value),
}
fn detect_triggers(
ctx: &PassContext,
unit: &UnitBuilder,
tr0: TemporalRegion,
tr1: TemporalRegion,
dnf: &Dnf,
) -> Option<Vec<Trigger>> {
trace!("Detecting triggers in {}", dnf.dump(&unit));
let mut trigs = vec![];
for conds in &dnf.0 {
let trig = match detect_term_triggers(ctx, unit, tr0, tr1, conds) {
Some(trig) => trig,
None => return None,
};
trigs.push(trig);
}
Some(trigs)
}
fn detect_term_triggers(
_ctx: &PassContext,
unit: &UnitBuilder,
tr0: TemporalRegion,
tr1: TemporalRegion,
conds: &BTreeMap<Term, bool>,
) -> Option<Trigger> {
trace!(" Analyzing {}", Dnf::dump_term(conds, &unit));
let mut edges = BTreeMap::new();
let mut levels = BTreeMap::new();
for (term, &inv) in conds {
match *term {
Term::Signal(sig, tr) if tr == tr0 => {
if conds.get(&Term::Signal(sig, tr1)).cloned() == Some(!inv) {
trace!(
" {} {}",
if inv { "rising" } else { "falling" },
sig.dump(&unit)
);
edges.insert(
sig,
match inv {
true => TriggerEdge::Rise,
false => TriggerEdge::Fall,
},
);
} else {
trace!(
" Skipping ({}@{} without corresponding {}@{})",
sig.dump(&unit),
tr0,
sig.dump(&unit),
tr1
);
return None;
}
}
Term::Signal(sig, tr) if tr == tr1 => {
if conds.get(&Term::Signal(sig, tr0)).cloned() != Some(!inv) {
trace!(
" {} {}",
if inv { "low" } else { "high" },
sig.dump(&unit)
);
levels.insert(
sig,
match inv {
false => TriggerLevel::High,
true => TriggerLevel::Low,
},
);
}
}
_ => {
trace!(" Skipping (invalid term)");
return None;
}
}
}
if edges.len() > 1 {
trace!(" Skipping (multiple edge triggers)");
return None;
}
if let Some((sig, edge)) = edges.into_iter().next() {
Some(Trigger::Edge(sig, edge, levels))
} else {
Some(Trigger::Level(levels))
}
}
#[derive(Debug)]
enum Trigger {
Edge(Value, TriggerEdge, BTreeMap<Value, TriggerLevel>),
Level(BTreeMap<Value, TriggerLevel>),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum TriggerEdge {
Rise,
Fall,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum TriggerLevel {
Low,
High,
}
struct Migrator<'a, 'b> {
src: &'a UnitBuilder<'b>,
dst: &'a mut UnitBuilder<'b>,
trg: &'a TemporalRegionGraph,
tr0: TemporalRegion,
tr1: TemporalRegion,
cache: HashMap<InstData, Value>,
migrated_drives: HashSet<Inst>,
}
impl<'a, 'b> Migrator<'a, 'b> {
pub fn new(
src: &'a UnitBuilder<'b>,
dst: &'a mut UnitBuilder<'b>,
trg: &'a TemporalRegionGraph,
tr0: TemporalRegion,
tr1: TemporalRegion,
) -> Self {
Self {
src,
dst,
trg,
tr0,
tr1,
cache: Default::default(),
migrated_drives: Default::default(),
}
}
pub fn migrate_drive(&mut self, drive: Inst, _bb: Block, trigs: &Vec<Trigger>) -> bool {
trace!("Migrating {}", drive.dump(&self.src));
let drive_target = self.src[drive].args()[0];
let drive_value = self.src[drive].args()[1];
let mig_target = match self.migrate_value(drive_target, &Default::default()) {
Some(v) => v,
None => return false,
};
let mut reg_triggers = vec![];
for trig in trigs {
trace!(" Migrating {:?}", trig);
match trig {
Trigger::Edge(sig, edge, conds) => {
let mut ties = BTreeMap::new();
let (l0, l1) = match edge {
TriggerEdge::Rise => (TriggerLevel::Low, TriggerLevel::High),
TriggerEdge::Fall => (TriggerLevel::High, TriggerLevel::Low),
};
ties.insert((*sig, self.tr0), l0);
ties.insert((*sig, self.tr1), l1);
let mut gate = None;
for (&sig, &level) in conds {
ties.insert((sig, self.tr1), level);
let value = self.dst.ins().prb(sig);
let value = match level {
TriggerLevel::Low => self.dst.ins().not(value),
TriggerLevel::High => value,
};
gate = Some(match gate {
Some(gate) => self.dst.ins().and(gate, value),
None => value,
});
}
let data = match self.migrate_value(drive_value, &ties) {
Some(v) => v,
None => return false,
};
let trigger = self.dst.ins().prb(*sig);
let mode = match edge {
TriggerEdge::Rise => RegMode::Rise,
TriggerEdge::Fall => RegMode::Fall,
};
reg_triggers.push(RegTrigger {
data,
mode,
trigger,
gate,
});
}
Trigger::Level(conds) => {
let mut ties = BTreeMap::new();
let mut trigger = None;
for (&sig, &level) in conds {
ties.insert((sig, self.tr1), level);
let value = self.dst.ins().prb(sig);
let value = match level {
TriggerLevel::Low => self.dst.ins().not(value),
TriggerLevel::High => value,
};
trigger = Some(match trigger {
Some(trigger) => self.dst.ins().and(trigger, value),
None => value,
});
}
let trigger = match trigger {
Some(c) => c,
None => {
trace!(
" Skipping {} (level-sensitive with no trigger)",
drive.dump(&self.src)
);
return false;
}
};
let data = match self.migrate_value(drive_value, &ties) {
Some(v) => v,
None => return false,
};
reg_triggers.push(RegTrigger {
data,
mode: RegMode::High,
trigger,
gate: None,
});
}
}
}
self.dst.ins().reg(mig_target, reg_triggers);
self.migrated_drives.insert(drive);
true
}
pub fn migrate_value(
&mut self,
value: Value,
ties: &BTreeMap<(Value, TemporalRegion), TriggerLevel>,
) -> Option<Value> {
if let Some(arg) = self.src.get_value_arg(value) {
return Some(self.dst.arg_value(arg));
}
if let Some(inst) = self.src.get_value_inst(value) {
let bb = self.src.inst_block(inst)?;
let tr = self.trg[bb];
if self.src[inst].opcode() == Opcode::Prb {
let sig = self.src[inst].args()[0];
if let Some(&level) = ties.get(&(sig, tr)) {
let data = InstData::ConstInt {
opcode: Opcode::ConstInt,
imm: IntValue::from_usize(
1,
match level {
TriggerLevel::High => 1,
TriggerLevel::Low => 0,
},
),
};
return Some(self.migrate_inst_data(data, value));
}
if tr != self.tr1 {
trace!(" Skipping {} (probe in wrong TR)", inst.dump(&self.src));
return None;
}
}
let mut data = self.src[inst].clone();
#[allow(deprecated)]
for arg in data.args_mut() {
*arg = self.migrate_value(*arg, ties)?;
}
return Some(self.migrate_inst_data(data, value));
}
trace!(
" Skipping {} (cannot be migrated)",
value.dump(&self.src)
);
None
}
fn migrate_inst_data(&mut self, data: InstData, src_value: Value) -> Value {
if let Some(&v) = self.cache.get(&data) {
v
} else {
trace!(" Migrated {}", src_value.dump(&self.src));
let ty = self.src.value_type(src_value);
let inst = self.dst.ins().build(data.clone(), ty);
let value = self.dst.inst_result(inst);
self.cache.insert(data, value);
if let Some(name) = self.src.get_name(src_value) {
self.dst.set_name(value, name.to_string());
}
value
}
}
}