use alloc::vec::Vec;
use core::convert::{TryFrom, TryInto};
use core::fmt::{self, Display, Formatter};
use core::num::NonZeroU32;
use core::ops::{Deref, DerefMut};
use core::str::FromStr;
use crate::ir::{self, trapcode::TrapCode, types, Block, FuncRef, JumpTable, SigRef, Type, Value};
use crate::isa;
use crate::bitset::BitSet;
use crate::data_value::DataValue;
use crate::entity;
use ir::condcodes::{FloatCC, IntCC};
pub type ValueList = entity::EntityList<Value>;
pub type ValueListPool = entity::ListPool<Value>;
include!(concat!(env!("OUT_DIR"), "/opcodes.rs"));
impl Display for Opcode {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "{}", opcode_name(*self))
}
}
impl Opcode {
pub fn format(self) -> InstructionFormat {
OPCODE_FORMAT[self as usize - 1]
}
pub fn constraints(self) -> OpcodeConstraints {
OPCODE_CONSTRAINTS[self as usize - 1]
}
pub fn is_resumable_trap(&self) -> bool {
match self {
Opcode::ResumableTrap | Opcode::ResumableTrapnz => true,
_ => false,
}
}
}
impl TryFrom<NonZeroU32> for Opcode {
type Error = ();
#[inline]
fn try_from(x: NonZeroU32) -> Result<Self, ()> {
let x: u16 = x.get().try_into().map_err(|_| ())?;
Self::try_from(x)
}
}
impl From<Opcode> for NonZeroU32 {
#[inline]
fn from(op: Opcode) -> NonZeroU32 {
let x = op as u8;
NonZeroU32::new(x as u32).unwrap()
}
}
impl FromStr for Opcode {
type Err = &'static str;
fn from_str(s: &str) -> Result<Self, &'static str> {
use crate::constant_hash::{probe, simple_hash, Table};
impl<'a> Table<&'a str> for [Option<Opcode>] {
fn len(&self) -> usize {
self.len()
}
fn key(&self, idx: usize) -> Option<&'a str> {
self[idx].map(opcode_name)
}
}
match probe::<&str, [Option<Self>]>(&OPCODE_HASH_TABLE, s, simple_hash(s)) {
Err(_) => Err("Unknown opcode"),
Ok(i) => Ok(OPCODE_HASH_TABLE[i].unwrap()),
}
}
}
#[derive(Clone, Debug)]
pub struct VariableArgs(Vec<Value>);
impl VariableArgs {
pub fn new() -> Self {
Self(Vec::new())
}
pub fn push(&mut self, v: Value) {
self.0.push(v)
}
pub fn is_empty(&self) -> bool {
self.0.is_empty()
}
pub fn into_value_list(self, fixed: &[Value], pool: &mut ValueListPool) -> ValueList {
let mut vlist = ValueList::default();
vlist.extend(fixed.iter().cloned(), pool);
vlist.extend(self.0, pool);
vlist
}
}
impl Deref for VariableArgs {
type Target = [Value];
fn deref(&self) -> &[Value] {
&self.0
}
}
impl DerefMut for VariableArgs {
fn deref_mut(&mut self) -> &mut [Value] {
&mut self.0
}
}
impl Display for VariableArgs {
fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
for (i, val) in self.0.iter().enumerate() {
if i == 0 {
write!(fmt, "{}", val)?;
} else {
write!(fmt, ", {}", val)?;
}
}
Ok(())
}
}
impl Default for VariableArgs {
fn default() -> Self {
Self::new()
}
}
impl InstructionData {
pub fn analyze_branch<'a>(&'a self, pool: &'a ValueListPool) -> BranchInfo<'a> {
match *self {
Self::Jump {
destination,
ref args,
..
} => BranchInfo::SingleDest(destination, args.as_slice(pool)),
Self::BranchInt {
destination,
ref args,
..
}
| Self::BranchFloat {
destination,
ref args,
..
}
| Self::Branch {
destination,
ref args,
..
} => BranchInfo::SingleDest(destination, &args.as_slice(pool)[1..]),
Self::BranchIcmp {
destination,
ref args,
..
} => BranchInfo::SingleDest(destination, &args.as_slice(pool)[2..]),
Self::BranchTable {
table, destination, ..
} => BranchInfo::Table(table, Some(destination)),
Self::IndirectJump { table, .. } => BranchInfo::Table(table, None),
_ => {
debug_assert!(!self.opcode().is_branch());
BranchInfo::NotABranch
}
}
}
pub fn branch_destination(&self) -> Option<Block> {
match *self {
Self::Jump { destination, .. }
| Self::Branch { destination, .. }
| Self::BranchInt { destination, .. }
| Self::BranchFloat { destination, .. }
| Self::BranchIcmp { destination, .. } => Some(destination),
Self::BranchTable { .. } | Self::IndirectJump { .. } => None,
_ => {
debug_assert!(!self.opcode().is_branch());
None
}
}
}
pub fn branch_destination_mut(&mut self) -> Option<&mut Block> {
match *self {
Self::Jump {
ref mut destination,
..
}
| Self::Branch {
ref mut destination,
..
}
| Self::BranchInt {
ref mut destination,
..
}
| Self::BranchFloat {
ref mut destination,
..
}
| Self::BranchIcmp {
ref mut destination,
..
} => Some(destination),
Self::BranchTable { .. } | Self::IndirectJump { .. } => None,
_ => {
debug_assert!(!self.opcode().is_branch());
None
}
}
}
pub fn imm_value(&self) -> Option<DataValue> {
match self {
&InstructionData::UnaryBool { imm, .. } => Some(DataValue::from(imm)),
&InstructionData::BinaryImm8 { imm, .. }
| &InstructionData::BranchTableEntry { imm, .. } => Some(DataValue::from(imm as i8)),
&InstructionData::UnaryIeee32 { imm, .. } => Some(DataValue::from(imm)),
&InstructionData::HeapAddr { imm, .. } => {
let imm: u32 = imm.into();
Some(DataValue::from(imm as i32))
}
&InstructionData::Load { offset, .. }
| &InstructionData::LoadComplex { offset, .. }
| &InstructionData::Store { offset, .. }
| &InstructionData::StoreComplex { offset, .. }
| &InstructionData::StackLoad { offset, .. }
| &InstructionData::StackStore { offset, .. }
| &InstructionData::TableAddr { offset, .. } => Some(DataValue::from(offset)),
&InstructionData::UnaryImm { imm, .. }
| &InstructionData::BinaryImm64 { imm, .. }
| &InstructionData::IntCompareImm { imm, .. } => Some(DataValue::from(imm.bits())),
&InstructionData::UnaryIeee64 { imm, .. } => Some(DataValue::from(imm)),
&InstructionData::Shuffle { mask: _, .. } => None,
_ => None,
}
}
pub fn trap_code(&self) -> Option<TrapCode> {
match *self {
Self::CondTrap { code, .. }
| Self::FloatCondTrap { code, .. }
| Self::IntCondTrap { code, .. }
| Self::Trap { code, .. } => Some(code),
_ => None,
}
}
pub fn cond_code(&self) -> Option<IntCC> {
match self {
&InstructionData::IntCond { cond, .. }
| &InstructionData::BranchIcmp { cond, .. }
| &InstructionData::IntCompare { cond, .. }
| &InstructionData::IntCondTrap { cond, .. }
| &InstructionData::BranchInt { cond, .. }
| &InstructionData::IntSelect { cond, .. }
| &InstructionData::IntCompareImm { cond, .. } => Some(cond),
_ => None,
}
}
pub fn fp_cond_code(&self) -> Option<FloatCC> {
match self {
&InstructionData::BranchFloat { cond, .. }
| &InstructionData::FloatCompare { cond, .. }
| &InstructionData::FloatCond { cond, .. }
| &InstructionData::FloatCondTrap { cond, .. } => Some(cond),
_ => None,
}
}
pub fn trap_code_mut(&mut self) -> Option<&mut TrapCode> {
match self {
Self::CondTrap { code, .. }
| Self::FloatCondTrap { code, .. }
| Self::IntCondTrap { code, .. }
| Self::Trap { code, .. } => Some(code),
_ => None,
}
}
pub fn atomic_rmw_op(&self) -> Option<ir::AtomicRmwOp> {
match self {
&InstructionData::AtomicRmw { op, .. } => Some(op),
_ => None,
}
}
pub fn load_store_offset(&self) -> Option<i32> {
match self {
&InstructionData::Load { offset, .. }
| &InstructionData::StackLoad { offset, .. }
| &InstructionData::LoadComplex { offset, .. }
| &InstructionData::Store { offset, .. }
| &InstructionData::StackStore { offset, .. }
| &InstructionData::StoreComplex { offset, .. } => Some(offset.into()),
_ => None,
}
}
pub fn analyze_call<'a>(&'a self, pool: &'a ValueListPool) -> CallInfo<'a> {
match *self {
Self::Call {
func_ref, ref args, ..
} => CallInfo::Direct(func_ref, args.as_slice(pool)),
Self::CallIndirect {
sig_ref, ref args, ..
} => CallInfo::Indirect(sig_ref, &args.as_slice(pool)[1..]),
_ => {
debug_assert!(!self.opcode().is_call());
CallInfo::NotACall
}
}
}
#[inline]
pub(crate) fn sign_extend_immediates(&mut self, ctrl_typevar: Type) {
if ctrl_typevar.is_invalid() {
return;
}
let bit_width = ctrl_typevar.bits();
match self {
Self::BinaryImm64 {
opcode,
arg: _,
imm,
} => {
if *opcode == Opcode::SdivImm || *opcode == Opcode::SremImm {
imm.sign_extend_from_width(bit_width);
}
}
Self::IntCompareImm {
opcode,
arg: _,
cond,
imm,
} => {
debug_assert_eq!(*opcode, Opcode::IcmpImm);
if cond.unsigned() != *cond {
imm.sign_extend_from_width(bit_width);
}
}
_ => {}
}
}
}
pub enum BranchInfo<'a> {
NotABranch,
SingleDest(Block, &'a [Value]),
Table(JumpTable, Option<Block>),
}
pub enum CallInfo<'a> {
NotACall,
Direct(FuncRef, &'a [Value]),
Indirect(SigRef, &'a [Value]),
}
#[derive(Clone, Copy)]
pub struct OpcodeConstraints {
flags: u8,
typeset_offset: u8,
constraint_offset: u16,
}
impl OpcodeConstraints {
pub fn use_typevar_operand(self) -> bool {
(self.flags & 0x8) != 0
}
pub fn requires_typevar_operand(self) -> bool {
(self.flags & 0x10) != 0
}
pub fn num_fixed_results(self) -> usize {
(self.flags & 0x7) as usize
}
pub fn num_fixed_value_arguments(self) -> usize {
((self.flags >> 5) & 0x7) as usize
}
fn typeset_offset(self) -> Option<usize> {
let offset = usize::from(self.typeset_offset);
if offset < TYPE_SETS.len() {
Some(offset)
} else {
None
}
}
fn constraint_offset(self) -> usize {
self.constraint_offset as usize
}
pub fn result_type(self, n: usize, ctrl_type: Type) -> Type {
debug_assert!(n < self.num_fixed_results(), "Invalid result index");
if let ResolvedConstraint::Bound(t) =
OPERAND_CONSTRAINTS[self.constraint_offset() + n].resolve(ctrl_type)
{
t
} else {
panic!("Result constraints can't be free");
}
}
pub fn value_argument_constraint(self, n: usize, ctrl_type: Type) -> ResolvedConstraint {
debug_assert!(
n < self.num_fixed_value_arguments(),
"Invalid value argument index"
);
let offset = self.constraint_offset() + self.num_fixed_results();
OPERAND_CONSTRAINTS[offset + n].resolve(ctrl_type)
}
pub fn ctrl_typeset(self) -> Option<ValueTypeSet> {
self.typeset_offset().map(|offset| TYPE_SETS[offset])
}
pub fn is_polymorphic(self) -> bool {
self.ctrl_typeset().is_some()
}
}
type BitSet8 = BitSet<u8>;
type BitSet16 = BitSet<u16>;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct ValueTypeSet {
pub lanes: BitSet16,
pub ints: BitSet8,
pub floats: BitSet8,
pub bools: BitSet8,
pub refs: BitSet8,
}
impl ValueTypeSet {
fn is_base_type(self, scalar: Type) -> bool {
let l2b = scalar.log2_lane_bits();
if scalar.is_int() {
self.ints.contains(l2b)
} else if scalar.is_float() {
self.floats.contains(l2b)
} else if scalar.is_bool() {
self.bools.contains(l2b)
} else if scalar.is_ref() {
self.refs.contains(l2b)
} else {
false
}
}
pub fn contains(self, typ: Type) -> bool {
let l2l = typ.log2_lane_count();
self.lanes.contains(l2l) && self.is_base_type(typ.lane_type())
}
pub fn example(self) -> Type {
let t = if self.ints.max().unwrap_or(0) > 5 {
types::I32
} else if self.floats.max().unwrap_or(0) > 5 {
types::F32
} else if self.bools.max().unwrap_or(0) > 5 {
types::B32
} else {
types::B1
};
t.by(1 << self.lanes.min().unwrap()).unwrap()
}
}
enum OperandConstraint {
Concrete(Type),
Free(u8),
Same,
LaneOf,
AsBool,
HalfWidth,
DoubleWidth,
HalfVector,
DoubleVector,
SplitLanes,
MergeLanes,
}
impl OperandConstraint {
pub fn resolve(&self, ctrl_type: Type) -> ResolvedConstraint {
use self::OperandConstraint::*;
use self::ResolvedConstraint::Bound;
match *self {
Concrete(t) => Bound(t),
Free(vts) => ResolvedConstraint::Free(TYPE_SETS[vts as usize]),
Same => Bound(ctrl_type),
LaneOf => Bound(ctrl_type.lane_of()),
AsBool => Bound(ctrl_type.as_bool()),
HalfWidth => Bound(ctrl_type.half_width().expect("invalid type for half_width")),
DoubleWidth => Bound(
ctrl_type
.double_width()
.expect("invalid type for double_width"),
),
HalfVector => Bound(
ctrl_type
.half_vector()
.expect("invalid type for half_vector"),
),
DoubleVector => Bound(ctrl_type.by(2).expect("invalid type for double_vector")),
SplitLanes => Bound(
ctrl_type
.split_lanes()
.expect("invalid type for split_lanes"),
),
MergeLanes => Bound(
ctrl_type
.merge_lanes()
.expect("invalid type for merge_lanes"),
),
}
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum ResolvedConstraint {
Bound(Type),
Free(ValueTypeSet),
}
#[cfg(test)]
mod tests {
use super::*;
use alloc::string::ToString;
#[test]
fn opcodes() {
use core::mem;
let x = Opcode::Iadd;
let mut y = Opcode::Isub;
assert!(x != y);
y = Opcode::Iadd;
assert_eq!(x, y);
assert_eq!(x.format(), InstructionFormat::Binary);
assert_eq!(format!("{:?}", Opcode::IaddImm), "IaddImm");
assert_eq!(Opcode::IaddImm.to_string(), "iadd_imm");
assert_eq!("iadd".parse::<Opcode>(), Ok(Opcode::Iadd));
assert_eq!("iadd_imm".parse::<Opcode>(), Ok(Opcode::IaddImm));
assert_eq!("iadd\0".parse::<Opcode>(), Err("Unknown opcode"));
assert_eq!("".parse::<Opcode>(), Err("Unknown opcode"));
assert_eq!("\0".parse::<Opcode>(), Err("Unknown opcode"));
assert_eq!(mem::size_of::<Opcode>(), mem::size_of::<Option<Opcode>>());
}
#[test]
fn instruction_data() {
use core::mem;
assert_eq!(mem::size_of::<InstructionData>(), 16);
}
#[test]
fn constraints() {
let a = Opcode::Iadd.constraints();
assert!(a.use_typevar_operand());
assert!(!a.requires_typevar_operand());
assert_eq!(a.num_fixed_results(), 1);
assert_eq!(a.num_fixed_value_arguments(), 2);
assert_eq!(a.result_type(0, types::I32), types::I32);
assert_eq!(a.result_type(0, types::I8), types::I8);
assert_eq!(
a.value_argument_constraint(0, types::I32),
ResolvedConstraint::Bound(types::I32)
);
assert_eq!(
a.value_argument_constraint(1, types::I32),
ResolvedConstraint::Bound(types::I32)
);
let b = Opcode::Bitcast.constraints();
assert!(!b.use_typevar_operand());
assert!(!b.requires_typevar_operand());
assert_eq!(b.num_fixed_results(), 1);
assert_eq!(b.num_fixed_value_arguments(), 1);
assert_eq!(b.result_type(0, types::I32), types::I32);
assert_eq!(b.result_type(0, types::I8), types::I8);
match b.value_argument_constraint(0, types::I32) {
ResolvedConstraint::Free(vts) => assert!(vts.contains(types::F32)),
_ => panic!("Unexpected constraint from value_argument_constraint"),
}
let c = Opcode::Call.constraints();
assert_eq!(c.num_fixed_results(), 0);
assert_eq!(c.num_fixed_value_arguments(), 0);
let i = Opcode::CallIndirect.constraints();
assert_eq!(i.num_fixed_results(), 0);
assert_eq!(i.num_fixed_value_arguments(), 1);
let cmp = Opcode::Icmp.constraints();
assert!(cmp.use_typevar_operand());
assert!(cmp.requires_typevar_operand());
assert_eq!(cmp.num_fixed_results(), 1);
assert_eq!(cmp.num_fixed_value_arguments(), 2);
}
#[test]
fn value_set() {
use crate::ir::types::*;
let vts = ValueTypeSet {
lanes: BitSet16::from_range(0, 8),
ints: BitSet8::from_range(4, 7),
floats: BitSet8::from_range(0, 0),
bools: BitSet8::from_range(3, 7),
refs: BitSet8::from_range(5, 7),
};
assert!(!vts.contains(I8));
assert!(vts.contains(I32));
assert!(vts.contains(I64));
assert!(vts.contains(I32X4));
assert!(!vts.contains(F32));
assert!(!vts.contains(B1));
assert!(vts.contains(B8));
assert!(vts.contains(B64));
assert!(vts.contains(R32));
assert!(vts.contains(R64));
assert_eq!(vts.example().to_string(), "i32");
let vts = ValueTypeSet {
lanes: BitSet16::from_range(0, 8),
ints: BitSet8::from_range(0, 0),
floats: BitSet8::from_range(5, 7),
bools: BitSet8::from_range(3, 7),
refs: BitSet8::from_range(0, 0),
};
assert_eq!(vts.example().to_string(), "f32");
let vts = ValueTypeSet {
lanes: BitSet16::from_range(1, 8),
ints: BitSet8::from_range(0, 0),
floats: BitSet8::from_range(5, 7),
bools: BitSet8::from_range(3, 7),
refs: BitSet8::from_range(0, 0),
};
assert_eq!(vts.example().to_string(), "f32x2");
let vts = ValueTypeSet {
lanes: BitSet16::from_range(2, 8),
ints: BitSet8::from_range(0, 0),
floats: BitSet8::from_range(0, 0),
bools: BitSet8::from_range(3, 7),
refs: BitSet8::from_range(0, 0),
};
assert!(!vts.contains(B32X2));
assert!(vts.contains(B32X4));
assert_eq!(vts.example().to_string(), "b32x4");
let vts = ValueTypeSet {
lanes: BitSet16::from_range(0, 9),
ints: BitSet8::from_range(3, 7),
floats: BitSet8::from_range(0, 0),
bools: BitSet8::from_range(0, 0),
refs: BitSet8::from_range(0, 0),
};
assert!(vts.contains(I32));
assert!(vts.contains(I32X4));
assert!(!vts.contains(R32));
assert!(!vts.contains(R64));
}
}