diff options
Diffstat (limited to 'third_party/rust/cranelift-codegen-meta/src/cdsl/ast.rs')
| -rw-r--r-- | third_party/rust/cranelift-codegen-meta/src/cdsl/ast.rs | 753 |
1 files changed, 753 insertions, 0 deletions
diff --git a/third_party/rust/cranelift-codegen-meta/src/cdsl/ast.rs b/third_party/rust/cranelift-codegen-meta/src/cdsl/ast.rs new file mode 100644 index 0000000000..82cdbad762 --- /dev/null +++ b/third_party/rust/cranelift-codegen-meta/src/cdsl/ast.rs @@ -0,0 +1,753 @@ +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(), + } + } +} + +/// An AST definition associates a set of variables with the values produced by an expression. +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); + +/// A definition which would lead to generate a block creation. +#[derive(Clone)] +pub(crate) struct Block { + /// Instruction index after which the block entry is set. + pub location: DefIndex, + /// Variable holding the new created block. + 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() + } +} + +// Implement IntoIterator such that we can iterate over blocks which are in the block pool. +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 { + /// A value of an enumerated immediate operand. + /// + /// Some immediate operand kinds like `intcc` and `floatcc` have an enumerated range of values + /// corresponding to a Rust enum type. An `Enumerator` object is an AST leaf node representing one + /// of the values. + Enumerator { + rust_type: &'static str, + value: &'static str, + }, + + /// A bitwise value of an immediate operand, used for bitwise exact floating point constants. + Bits { rust_type: &'static str, value: u64 }, + + /// A value of an integer immediate operand. + Int(i64), + + /// A empty list of variable set of arguments. + 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, +} + +/// A free variable. +/// +/// When variables are used in `XForms` with source and destination patterns, they are classified +/// as follows: +/// +/// Input values: Uses in the source pattern with no preceding def. These may appear as inputs in +/// the destination pattern too, but no new inputs can be introduced. +/// +/// Output values: Variables that are defined in both the source and destination pattern. These +/// values may have uses outside the source pattern, and the destination pattern must compute the +/// same value. +/// +/// Intermediate values: Values that are defined in the source pattern, but not in the destination +/// pattern. These may have uses outside the source pattern, so the defining instruction can't be +/// deleted immediately. +/// +/// Temporary values are defined only in the destination pattern. +pub(crate) struct Var { + pub name: String, + + /// The `Def` defining this variable in a source pattern. + pub src_def: Option<DefIndex>, + + /// The `Def` defining this variable in a destination pattern. + pub dst_def: Option<DefIndex>, + + /// TypeVar representing the type of this variable. + type_var: Option<TypeVar>, + + /// Is this the original type variable, or has it be redefined with set_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, + } + } + + /// Is this an input value to the src pattern? + pub fn is_input(&self) -> bool { + self.src_def.is_none() && self.dst_def.is_none() + } + + /// Is this an output value, defined in both src and dst patterns? + pub fn is_output(&self) -> bool { + self.src_def.is_some() && self.dst_def.is_some() + } + + /// Is this an intermediate value, defined only in the src pattern? + pub fn is_intermediate(&self) -> bool { + self.src_def.is_some() && self.dst_def.is_none() + } + + /// Is this a temp value, defined only in the dst pattern? + pub fn is_temp(&self) -> bool { + self.src_def.is_none() && self.dst_def.is_some() + } + + /// Get the def of this variable according to the position. + 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); + } + } + } + + /// Get the type variable representing the type of this variable. + pub fn get_or_create_typevar(&mut self) -> TypeVar { + match &self.type_var { + Some(tv) => tv.clone(), + None => { + // Create a new type var in which we allow all types. + 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); + } + + /// Check if this variable has a free type variable. If not, the type of this variable is + /// computed from the type of another variable. + 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())) + } +} + +/// Contains constants created in the AST that must be inserted into the true [ConstantPool] when +/// the legalizer code is generated. The constant data is named in the order it is inserted; +/// inserting data using [insert] will avoid duplicates. +/// +/// [ConstantPool]: ../../../cranelift_codegen/ir/constant/struct.ConstantPool.html +/// [insert]: ConstPool::insert +pub(crate) struct ConstPool { + pool: Vec<Vec<u8>>, +} + +impl ConstPool { + /// Create an empty constant pool. + pub fn new() -> Self { + Self { pool: vec![] } + } + + /// Create a name for a constant from its position in the pool. + fn create_name(position: usize) -> String { + format!("const{}", position) + } + + /// Insert constant data into the pool, returning the name of the variable used to reference it. + /// This method will search for data that matches the new data and return the existing constant + /// name to avoid duplicates. + 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) + } + + /// Iterate over the name/value pairs in the pool. + pub fn iter(&self) -> impl Iterator<Item = (String, &Vec<u8>)> { + self.pool + .iter() + .enumerate() + .map(|(i, v)| (ConstPool::create_name(i), v)) + } +} + +/// Apply an instruction to arguments. +/// +/// An `Apply` AST expression is created by using function call syntax on instructions. This +/// applies to both bound and unbound polymorphic instructions. +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), + }; + + // Apply should only operate on concrete value types, not "any". + let value_types = value_types + .into_iter() + .map(|vt| vt.expect("shouldn't be Any")) + .collect(); + + // Basic check on number of arguments. + assert!( + inst.operands_in.len() == args.len(), + format!("incorrect number of arguments in instruction {}", inst.name) + ); + + // Check that the kinds of Literals arguments match the expected operand. + 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() { + // Ignore free variables for now. + continue; + } + pred = pred.and(InstructionPredicate::new_is_field_equal_ast( + &*self.inst.format, + format_field, + arg.to_rust_code(var_pool), + )); + } + + // Add checks for any bound secondary type variables. We can't check the controlling type + // variable this way since it may not appear as the type of an operand. + 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 + } + + /// Same as `inst_predicate()`, but also check the controlling type variable. + 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(", "); + + // Do we need to pass an explicit type argument? + 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) + } +} + +// Simple helpers for legalize actions construction. + +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(a, b, c) + ($inst:ident($($src:expr),*)) => { + ExprBuilder::apply($inst.into(), vec![$($src.clone().into()),*]) + }; + + // inst.type(a, b, c) + ($inst:ident.$type:ident($($src:expr),*)) => { + ExprBuilder::apply($inst.bind($type).into(), vec![$($src.clone().into()),*]) + }; +} + +// Helper macro to define legalization recipes. +macro_rules! def { + // x = ... + ($dest:ident = $($tt:tt)*) => { + def_rhs!($($tt)*).assign_to(vec![$dest.clone()]) + }; + + // (x, y, ...) = ... + (($($dest:ident),*) = $($tt:tt)*) => { + def_rhs!($($tt)*).assign_to(vec![$($dest.clone()),*]) + }; + + // An instruction with no results. + ($($tt:tt)*) => { + def_rhs!($($tt)*).assign_to(Vec::new()) + } +} + +// Helper macro to define legalization recipes. +macro_rules! block { + // a basic block definition, splitting the current block in 2. + ($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); + } +} |