use crate::cdsl::instructions::{InstSpec, Instruction, InstructionPredicate};
use crate::cdsl::operands::{OperandKind, OperandKindFields};
use crate::cdsl::types::ValueType;
use crate::cdsl::typevar::{TypeSetBuilder, TypeVar};
use cranelift_entity::{entity_impl, PrimaryMap, SparseMap, SparseMapValue};
use std::fmt;
use std::iter::IntoIterator;
pub(crate) enum Expr {
Var(VarIndex),
Literal(Literal),
}
impl Expr {
pub fn maybe_literal(&self) -> Option<&Literal> {
match &self {
Expr::Literal(lit) => Some(lit),
_ => None,
}
}
pub fn maybe_var(&self) -> Option<VarIndex> {
if let Expr::Var(var) = &self {
Some(*var)
} else {
None
}
}
pub fn unwrap_var(&self) -> VarIndex {
self.maybe_var()
.expect("tried to unwrap a non-Var content in Expr::unwrap_var")
}
pub fn to_rust_code(&self, var_pool: &VarPool) -> String {
match self {
Expr::Var(var_index) => var_pool.get(*var_index).to_rust_code(),
Expr::Literal(literal) => literal.to_rust_code(),
}
}
}
pub(crate) struct Def {
pub apply: Apply,
pub defined_vars: Vec<VarIndex>,
}
impl Def {
pub fn to_comment_string(&self, var_pool: &VarPool) -> String {
let results = self
.defined_vars
.iter()
.map(|&x| var_pool.get(x).name.as_str())
.collect::<Vec<_>>();
let results = if results.len() == 1 {
results[0].to_string()
} else {
format!("({})", results.join(", "))
};
format!("{} := {}", results, self.apply.to_comment_string(var_pool))
}
}
pub(crate) struct DefPool {
pool: PrimaryMap<DefIndex, Def>,
}
impl DefPool {
pub fn new() -> Self {
Self {
pool: PrimaryMap::new(),
}
}
pub fn get(&self, index: DefIndex) -> &Def {
self.pool.get(index).unwrap()
}
pub fn next_index(&self) -> DefIndex {
self.pool.next_key()
}
pub fn create_inst(&mut self, apply: Apply, defined_vars: Vec<VarIndex>) -> DefIndex {
self.pool.push(Def {
apply,
defined_vars,
})
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub(crate) struct DefIndex(u32);
entity_impl!(DefIndex);
#[derive(Clone)]
pub(crate) struct Block {
pub location: DefIndex,
pub name: VarIndex,
}
pub(crate) struct BlockPool {
pool: SparseMap<DefIndex, Block>,
}
impl SparseMapValue<DefIndex> for Block {
fn key(&self) -> DefIndex {
self.location
}
}
impl BlockPool {
pub fn new() -> Self {
Self {
pool: SparseMap::new(),
}
}
pub fn get(&self, index: DefIndex) -> Option<&Block> {
self.pool.get(index)
}
pub fn create_block(&mut self, name: VarIndex, location: DefIndex) {
if self.pool.contains_key(location) {
panic!("Attempt to insert 2 blocks after the same instruction")
}
self.pool.insert(Block { location, name });
}
pub fn is_empty(&self) -> bool {
self.pool.is_empty()
}
}
impl<'a> IntoIterator for &'a BlockPool {
type Item = <&'a SparseMap<DefIndex, Block> as IntoIterator>::Item;
type IntoIter = <&'a SparseMap<DefIndex, Block> as IntoIterator>::IntoIter;
fn into_iter(self) -> Self::IntoIter {
self.pool.into_iter()
}
}
#[derive(Clone, Debug)]
pub(crate) enum Literal {
Enumerator {
rust_type: &'static str,
value: &'static str,
},
Bits { rust_type: &'static str, value: u64 },
Int(i64),
EmptyVarArgs,
}
impl Literal {
pub fn enumerator_for(kind: &OperandKind, value: &'static str) -> Self {
let value = match &kind.fields {
OperandKindFields::ImmEnum(values) => values.get(value).unwrap_or_else(|| {
panic!(
"nonexistent value '{}' in enumeration '{}'",
value, kind.rust_type
)
}),
_ => panic!("enumerator is for enum values"),
};
Literal::Enumerator {
rust_type: kind.rust_type,
value,
}
}
pub fn bits(kind: &OperandKind, bits: u64) -> Self {
match kind.fields {
OperandKindFields::ImmValue => {}
_ => panic!("bits_of is for immediate scalar types"),
}
Literal::Bits {
rust_type: kind.rust_type,
value: bits,
}
}
pub fn constant(kind: &OperandKind, value: i64) -> Self {
match kind.fields {
OperandKindFields::ImmValue => {}
_ => panic!("constant is for immediate scalar types"),
}
Literal::Int(value)
}
pub fn empty_vararg() -> Self {
Literal::EmptyVarArgs
}
pub fn to_rust_code(&self) -> String {
match self {
Literal::Enumerator { rust_type, value } => format!("{}::{}", rust_type, value),
Literal::Bits { rust_type, value } => format!("{}::with_bits({:#x})", rust_type, value),
Literal::Int(val) => val.to_string(),
Literal::EmptyVarArgs => "&[]".into(),
}
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum PatternPosition {
Source,
Destination,
}
pub(crate) struct Var {
pub name: String,
pub src_def: Option<DefIndex>,
pub dst_def: Option<DefIndex>,
type_var: Option<TypeVar>,
is_original_type_var: bool,
}
impl Var {
fn new(name: String) -> Self {
Self {
name,
src_def: None,
dst_def: None,
type_var: None,
is_original_type_var: false,
}
}
pub fn is_input(&self) -> bool {
self.src_def.is_none() && self.dst_def.is_none()
}
pub fn is_output(&self) -> bool {
self.src_def.is_some() && self.dst_def.is_some()
}
pub fn is_intermediate(&self) -> bool {
self.src_def.is_some() && self.dst_def.is_none()
}
pub fn is_temp(&self) -> bool {
self.src_def.is_none() && self.dst_def.is_some()
}
pub fn get_def(&self, position: PatternPosition) -> Option<DefIndex> {
match position {
PatternPosition::Source => self.src_def,
PatternPosition::Destination => self.dst_def,
}
}
pub fn set_def(&mut self, position: PatternPosition, def: DefIndex) {
assert!(
self.get_def(position).is_none(),
format!("redefinition of variable {}", self.name)
);
match position {
PatternPosition::Source => {
self.src_def = Some(def);
}
PatternPosition::Destination => {
self.dst_def = Some(def);
}
}
}
pub fn get_or_create_typevar(&mut self) -> TypeVar {
match &self.type_var {
Some(tv) => tv.clone(),
None => {
let tv = TypeVar::new(
format!("typeof_{}", self.name),
format!("Type of the pattern variable {:?}", self),
TypeSetBuilder::all(),
);
self.type_var = Some(tv.clone());
self.is_original_type_var = true;
tv
}
}
}
pub fn get_typevar(&self) -> Option<TypeVar> {
self.type_var.clone()
}
pub fn set_typevar(&mut self, tv: TypeVar) {
self.is_original_type_var = if let Some(previous_tv) = &self.type_var {
*previous_tv == tv
} else {
false
};
self.type_var = Some(tv);
}
pub fn has_free_typevar(&self) -> bool {
match &self.type_var {
Some(tv) => tv.base.is_none() && self.is_original_type_var,
None => false,
}
}
pub fn to_rust_code(&self) -> String {
self.name.clone()
}
fn rust_type(&self) -> String {
self.type_var.as_ref().unwrap().to_rust_code()
}
}
impl fmt::Debug for Var {
fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
fmt.write_fmt(format_args!(
"Var({}{}{})",
self.name,
if self.src_def.is_some() { ", src" } else { "" },
if self.dst_def.is_some() { ", dst" } else { "" }
))
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub(crate) struct VarIndex(u32);
entity_impl!(VarIndex);
pub(crate) struct VarPool {
pool: PrimaryMap<VarIndex, Var>,
}
impl VarPool {
pub fn new() -> Self {
Self {
pool: PrimaryMap::new(),
}
}
pub fn get(&self, index: VarIndex) -> &Var {
self.pool.get(index).unwrap()
}
pub fn get_mut(&mut self, index: VarIndex) -> &mut Var {
self.pool.get_mut(index).unwrap()
}
pub fn create(&mut self, name: impl Into<String>) -> VarIndex {
self.pool.push(Var::new(name.into()))
}
}
pub(crate) struct ConstPool {
pool: Vec<Vec<u8>>,
}
impl ConstPool {
pub fn new() -> Self {
Self { pool: vec![] }
}
fn create_name(position: usize) -> String {
format!("const{}", position)
}
pub fn insert(&mut self, data: Vec<u8>) -> String {
let possible_position = self.pool.iter().position(|d| d == &data);
let position = if let Some(found_position) = possible_position {
found_position
} else {
let new_position = self.pool.len();
self.pool.push(data);
new_position
};
ConstPool::create_name(position)
}
pub fn iter(&self) -> impl Iterator<Item = (String, &Vec<u8>)> {
self.pool
.iter()
.enumerate()
.map(|(i, v)| (ConstPool::create_name(i), v))
}
}
pub(crate) struct Apply {
pub inst: Instruction,
pub args: Vec<Expr>,
pub value_types: Vec<ValueType>,
}
impl Apply {
pub fn new(target: InstSpec, args: Vec<Expr>) -> Self {
let (inst, value_types) = match target {
InstSpec::Inst(inst) => (inst, Vec::new()),
InstSpec::Bound(bound_inst) => (bound_inst.inst, bound_inst.value_types),
};
let value_types = value_types
.into_iter()
.map(|vt| vt.expect("shouldn't be Any"))
.collect();
assert!(
inst.operands_in.len() == args.len(),
format!("incorrect number of arguments in instruction {}", inst.name)
);
for &imm_index in &inst.imm_opnums {
let arg = &args[imm_index];
if let Some(literal) = arg.maybe_literal() {
let op = &inst.operands_in[imm_index];
match &op.kind.fields {
OperandKindFields::ImmEnum(values) => {
if let Literal::Enumerator { value, .. } = literal {
assert!(
values.iter().any(|(_key, v)| v == value),
"Nonexistent enum value '{}' passed to field of kind '{}' -- \
did you use the right enum?",
value,
op.kind.rust_type
);
} else {
panic!(
"Passed non-enum field value {:?} to field of kind {}",
literal, op.kind.rust_type
);
}
}
OperandKindFields::ImmValue => match &literal {
Literal::Enumerator { value, .. } => panic!(
"Expected immediate value in immediate field of kind '{}', \
obtained enum value '{}'",
op.kind.rust_type, value
),
Literal::Bits { .. } | Literal::Int(_) | Literal::EmptyVarArgs => {}
},
_ => {
panic!(
"Literal passed to non-literal field of kind {}",
op.kind.rust_type
);
}
}
}
}
Self {
inst,
args,
value_types,
}
}
fn to_comment_string(&self, var_pool: &VarPool) -> String {
let args = self
.args
.iter()
.map(|arg| arg.to_rust_code(var_pool))
.collect::<Vec<_>>()
.join(", ");
let mut inst_and_bound_types = vec![self.inst.name.to_string()];
inst_and_bound_types.extend(self.value_types.iter().map(|vt| vt.to_string()));
let inst_name = inst_and_bound_types.join(".");
format!("{}({})", inst_name, args)
}
pub fn inst_predicate(&self, var_pool: &VarPool) -> InstructionPredicate {
let mut pred = InstructionPredicate::new();
for (format_field, &op_num) in self
.inst
.format
.imm_fields
.iter()
.zip(self.inst.imm_opnums.iter())
{
let arg = &self.args[op_num];
if arg.maybe_var().is_some() {
continue;
}
pred = pred.and(InstructionPredicate::new_is_field_equal_ast(
&*self.inst.format,
format_field,
arg.to_rust_code(var_pool),
));
}
if self.value_types.len() > 1 {
let poly = self
.inst
.polymorphic_info
.as_ref()
.expect("must have polymorphic info if it has bounded types");
for (bound_type, type_var) in
self.value_types[1..].iter().zip(poly.other_typevars.iter())
{
pred = pred.and(InstructionPredicate::new_typevar_check(
&self.inst, type_var, bound_type,
));
}
}
pred
}
pub fn inst_predicate_with_ctrl_typevar(&self, var_pool: &VarPool) -> InstructionPredicate {
let mut pred = self.inst_predicate(var_pool);
if !self.value_types.is_empty() {
let bound_type = &self.value_types[0];
let poly = self.inst.polymorphic_info.as_ref().unwrap();
let type_check = if poly.use_typevar_operand {
InstructionPredicate::new_typevar_check(&self.inst, &poly.ctrl_typevar, bound_type)
} else {
InstructionPredicate::new_ctrl_typevar_check(&bound_type)
};
pred = pred.and(type_check);
}
pred
}
pub fn rust_builder(&self, defined_vars: &[VarIndex], var_pool: &VarPool) -> String {
let mut args = self
.args
.iter()
.map(|expr| expr.to_rust_code(var_pool))
.collect::<Vec<_>>()
.join(", ");
if let Some(poly) = &self.inst.polymorphic_info {
if !poly.use_typevar_operand {
args = format!("{}, {}", var_pool.get(defined_vars[0]).rust_type(), args);
}
}
format!("{}({})", self.inst.snake_name(), args)
}
}
pub(crate) enum DummyExpr {
Var(DummyVar),
Literal(Literal),
Constant(DummyConstant),
Apply(InstSpec, Vec<DummyExpr>),
Block(DummyVar),
}
#[derive(Clone)]
pub(crate) struct DummyVar {
pub name: String,
}
impl Into<DummyExpr> for DummyVar {
fn into(self) -> DummyExpr {
DummyExpr::Var(self)
}
}
impl Into<DummyExpr> for Literal {
fn into(self) -> DummyExpr {
DummyExpr::Literal(self)
}
}
#[derive(Clone)]
pub(crate) struct DummyConstant(pub(crate) Vec<u8>);
pub(crate) fn constant(data: Vec<u8>) -> DummyConstant {
DummyConstant(data)
}
impl Into<DummyExpr> for DummyConstant {
fn into(self) -> DummyExpr {
DummyExpr::Constant(self)
}
}
pub(crate) fn var(name: &str) -> DummyVar {
DummyVar {
name: name.to_owned(),
}
}
pub(crate) struct DummyDef {
pub expr: DummyExpr,
pub defined_vars: Vec<DummyVar>,
}
pub(crate) struct ExprBuilder {
expr: DummyExpr,
}
impl ExprBuilder {
pub fn apply(inst: InstSpec, args: Vec<DummyExpr>) -> Self {
let expr = DummyExpr::Apply(inst, args);
Self { expr }
}
pub fn assign_to(self, defined_vars: Vec<DummyVar>) -> DummyDef {
DummyDef {
expr: self.expr,
defined_vars,
}
}
pub fn block(name: DummyVar) -> Self {
let expr = DummyExpr::Block(name);
Self { expr }
}
}
macro_rules! def_rhs {
($inst:ident($($src:expr),*)) => {
ExprBuilder::apply($inst.into(), vec![$($src.clone().into()),*])
};
($inst:ident.$type:ident($($src:expr),*)) => {
ExprBuilder::apply($inst.bind($type).into(), vec![$($src.clone().into()),*])
};
}
macro_rules! def {
($dest:ident = $($tt:tt)*) => {
def_rhs!($($tt)*).assign_to(vec![$dest.clone()])
};
(($($dest:ident),*) = $($tt:tt)*) => {
def_rhs!($($tt)*).assign_to(vec![$($dest.clone()),*])
};
($($tt:tt)*) => {
def_rhs!($($tt)*).assign_to(Vec::new())
}
}
macro_rules! block {
($block: ident) => {
ExprBuilder::block($block).assign_to(Vec::new())
};
}
#[cfg(test)]
mod tests {
use crate::cdsl::ast::ConstPool;
#[test]
fn const_pool_returns_var_names() {
let mut c = ConstPool::new();
assert_eq!(c.insert([0, 1, 2].to_vec()), "const0");
assert_eq!(c.insert([1, 2, 3].to_vec()), "const1");
}
#[test]
fn const_pool_avoids_duplicates() {
let data = [0, 1, 2].to_vec();
let mut c = ConstPool::new();
assert_eq!(c.pool.len(), 0);
assert_eq!(c.insert(data.clone()), "const0");
assert_eq!(c.pool.len(), 1);
assert_eq!(c.insert(data), "const0");
assert_eq!(c.pool.len(), 1);
}
#[test]
fn const_pool_iterates() {
let mut c = ConstPool::new();
c.insert([0, 1, 2].to_vec());
c.insert([3, 4, 5].to_vec());
let mut iter = c.iter();
assert_eq!(iter.next(), Some(("const0".to_owned(), &vec![0, 1, 2])));
assert_eq!(iter.next(), Some(("const1".to_owned(), &vec![3, 4, 5])));
assert_eq!(iter.next(), None);
}
}