error::{Error, Result},
index::{BlockIdx, InstIdx, InstRange, SSAValIdx},
interned::{GlobalState, Intern, Interned},
- loc::{BaseTy, Loc, Ty},
+ loc::{BaseTy, Loc, LocFields, LocKind, Ty},
loc_set::LocSet,
};
use arbitrary::Arbitrary;
use core::fmt;
+use enum_map::Enum;
use hashbrown::HashSet;
use petgraph::{
algo::dominators,
}
#[derive(
- Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize, Arbitrary,
+ Copy,
+ Clone,
+ PartialEq,
+ Eq,
+ PartialOrd,
+ Ord,
+ Debug,
+ Hash,
+ Serialize,
+ Deserialize,
+ Arbitrary,
+ Enum,
)]
#[repr(u8)]
pub enum InstStage {
}
#[derive(
- Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize, Arbitrary,
+ Copy,
+ Clone,
+ PartialEq,
+ Eq,
+ PartialOrd,
+ Ord,
+ Debug,
+ Hash,
+ Serialize,
+ Deserialize,
+ Arbitrary,
+ Enum,
)]
#[repr(u8)]
pub enum OperandKind {
Def = 1,
}
-#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize)]
+#[derive(
+ Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize, Arbitrary,
+)]
pub enum Constraint {
/// any register or stack location
Any,
pub fn is_any(&self) -> bool {
matches!(self, Self::Any)
}
+ pub fn fixed_loc(&self) -> Option<Loc> {
+ match *self {
+ Constraint::Any
+ | Constraint::BaseGpr
+ | Constraint::SVExtra2VGpr
+ | Constraint::SVExtra2SGpr
+ | Constraint::SVExtra3Gpr
+ | Constraint::Stack => None,
+ Constraint::FixedLoc(v) => Some(v),
+ }
+ }
+ pub fn non_fixed_choices_for_ty(ty: Ty) -> &'static [Constraint] {
+ match (ty.base_ty, ty.reg_len.get()) {
+ (BaseTy::Bits64, 1) => &[
+ Constraint::Any,
+ Constraint::BaseGpr,
+ Constraint::SVExtra2SGpr,
+ Constraint::SVExtra2VGpr,
+ Constraint::SVExtra3Gpr,
+ Constraint::Stack,
+ ],
+ (BaseTy::Bits64, _) => &[
+ Constraint::Any,
+ Constraint::SVExtra2VGpr,
+ Constraint::SVExtra3Gpr,
+ Constraint::Stack,
+ ],
+ (BaseTy::Ca, _) | (BaseTy::VlMaxvl, _) => &[Constraint::Any, Constraint::Stack],
+ }
+ }
+ pub fn arbitrary_with_ty(
+ ty: Ty,
+ u: &mut arbitrary::Unstructured<'_>,
+ ) -> arbitrary::Result<Self> {
+ let non_fixed_choices = Self::non_fixed_choices_for_ty(ty);
+ if let Some(&retval) = non_fixed_choices.get(u.choose_index(non_fixed_choices.len() + 1)?) {
+ Ok(retval)
+ } else {
+ Ok(Constraint::FixedLoc(Loc::arbitrary_with_ty(ty, u)?))
+ }
+ }
+ pub fn check_for_ty_mismatch(&self, ty: Ty) -> Result<(), ()> {
+ match self {
+ Constraint::Any | Constraint::Stack => {}
+ Constraint::BaseGpr | Constraint::SVExtra2SGpr => {
+ if ty != Ty::scalar(BaseTy::Bits64) {
+ return Err(());
+ }
+ }
+ Constraint::SVExtra2VGpr | Constraint::SVExtra3Gpr => {
+ if ty.base_ty != BaseTy::Bits64 {
+ return Err(());
+ }
+ }
+ Constraint::FixedLoc(loc) => {
+ if ty != loc.ty() {
+ return Err(());
+ }
+ }
+ }
+ Ok(())
+ }
}
impl Default for Constraint {
}
}
let constraint = self.try_constraint(inst, func)?;
- match constraint {
- Constraint::Any | Constraint::Stack => {}
- Constraint::BaseGpr | Constraint::SVExtra2SGpr => {
- if ssa_val.ty != Ty::scalar(BaseTy::Bits64) {
- return Err(Error::ConstraintTyMismatch {
- ssa_val_idx,
- inst,
- operand_idx,
- });
- }
- }
- Constraint::SVExtra2VGpr | Constraint::SVExtra3Gpr => {
- if ssa_val.ty.base_ty != BaseTy::Bits64 {
- return Err(Error::ConstraintTyMismatch {
- ssa_val_idx,
- inst,
- operand_idx,
- });
- }
- }
- Constraint::FixedLoc(loc) => {
- if func
- .try_get_inst(inst)?
- .clobbers
- .clone()
- .conflicts_with(loc, global_state)
- {
- return Err(Error::FixedLocConflictsWithClobbers { inst, operand_idx });
- }
- if ssa_val.ty != loc.ty() {
- return Err(Error::ConstraintTyMismatch {
- ssa_val_idx,
- inst,
- operand_idx,
- });
- }
+ constraint
+ .check_for_ty_mismatch(ssa_val.ty)
+ .map_err(|()| Error::ConstraintTyMismatch {
+ ssa_val_idx,
+ inst,
+ operand_idx,
+ })?;
+ if let Some(fixed_loc) = constraint.fixed_loc() {
+ if func
+ .try_get_inst(inst)?
+ .clobbers
+ .clone()
+ .conflicts_with(fixed_loc, global_state)
+ {
+ return Err(Error::FixedLocConflictsWithClobbers { inst, operand_idx });
}
}
Ok(())
for &pred in preds {
let (term_inst, BlockTermInstKind { succs_and_params }) =
func.try_get_block_term_inst_and_kind(pred)?;
- if !succs_and_params.contains_key(&pred) {
+ if !succs_and_params.contains_key(&block) {
return Err(Error::PredMissingFromPredsTermBranchsTargets {
src_block: pred,
branch_inst: term_inst,
impl GraphProp for FnFields {
type EdgeType = Directed;
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use crate::loc::TyFields;
+ use std::num::NonZeroU32;
+
+ #[test]
+ fn test_constraint_non_fixed_choices_for_ty() {
+ macro_rules! seen {
+ (
+ enum ConstraintWithoutFixedLoc {
+ $($field:ident,)*
+ }
+ ) => {
+ #[derive(Default)]
+ #[allow(non_snake_case)]
+ struct Seen {
+ $($field: bool,)*
+ }
+
+ impl Seen {
+ fn add(&mut self, constraint: &Constraint) {
+ match constraint {
+ Constraint::FixedLoc(_) => {}
+ $(Constraint::$field => self.$field = true,)*
+ }
+ }
+ fn check(self) {
+ $(assert!(self.$field, "never seen field: {}", stringify!($field));)*
+ }
+ }
+ };
+ }
+ seen! {
+ enum ConstraintWithoutFixedLoc {
+ Any,
+ BaseGpr,
+ SVExtra2VGpr,
+ SVExtra2SGpr,
+ SVExtra3Gpr,
+ Stack,
+ }
+ }
+ let mut seen = Seen::default();
+ for base_ty in 0..BaseTy::LENGTH {
+ let base_ty = BaseTy::from_usize(base_ty);
+ for reg_len in [1, 2, 100] {
+ let reg_len = NonZeroU32::new(reg_len).unwrap();
+ let ty = Ty::new_or_scalar(TyFields { base_ty, reg_len });
+ let non_fixed_choices = Constraint::non_fixed_choices_for_ty(ty);
+ assert_eq!(non_fixed_choices.first(), Some(&Constraint::Any));
+ assert_eq!(non_fixed_choices.last(), Some(&Constraint::Stack));
+ for constraint in non_fixed_choices {
+ assert_eq!(constraint.fixed_loc(), None);
+ seen.add(constraint);
+ if constraint.check_for_ty_mismatch(ty).is_err() {
+ panic!("constraint ty mismatch: constraint={constraint:?} ty={ty:?}");
+ }
+ }
+ }
+ }
+ seen.check();
+ }
+}
use crate::{
function::{
Block, BlockTermInstKind, BranchSuccParamUse, Constraint, CopyInstKind, FnFields, Inst,
- InstKind, KindAndConstraint, Operand, OperandKind, OperandUse, SSAVal, SSAValDef,
+ InstKind, InstStage, KindAndConstraint, Operand, OperandKind, OperandKindDefOnly,
+ OperandUse, SSAVal, SSAValDef,
},
index::{BlockIdx, InstIdx, InstRange, SSAValIdx},
interned::{GlobalState, Intern},
loc_set::LocSet,
};
use arbitrary::{Arbitrary, Error, Unstructured};
+use enum_map::EnumMap;
use hashbrown::HashMap;
use petgraph::algo::dominators;
use std::{borrow::Borrow, collections::BTreeMap, ops::Deref};
u: &mut Unstructured<'_>,
// takes ref to Vec since Index<SSAValIdx> is only implemented for Vec
ssa_vals: &Vec<SSAVal>,
+ _inst_idx: InstIdx, // for debugging
operands: &[Operand],
) -> Result<Option<CopyInstKind>, Error> {
if operands.is_empty() {
if possible_src_operand_idxs.is_empty() || possible_dest_operand_idxs.is_empty() {
return Ok(None);
}
- let mut src_operand_idxs = vec![];
- for _ in 0..u.int_in_range(1..=3)? {
- // src can have duplicates, don't remove chosen items
- src_operand_idxs.push(*u.choose(&possible_src_operand_idxs)?);
+ // src can have duplicates, so pick randomly
+ let possible_src_operand_idxs = (0..u.int_in_range(1..=3)?)
+ .map(|_| u.choose(&possible_src_operand_idxs).copied())
+ .collect::<Result<Vec<usize>, Error>>()?;
+ // dest can't have duplicates, so shuffle
+ let len = possible_dest_operand_idxs.len();
+ for i in 0..len {
+ possible_dest_operand_idxs.swap(i, u.choose_index(len)?);
}
- for src_operand_idxs_len in (1..=src_operand_idxs.len()).rev() {
- let mut operand_types = src_operand_idxs[..src_operand_idxs_len]
- .iter()
- .map(|&idx| ssa_vals[operands[idx].ssa_val].ty);
- let copy_ty = operand_types.next_back().unwrap();
- let copy_ty = operand_types
- .filter(|v| v.base_ty == copy_ty.base_ty)
- .try_fold(copy_ty, Ty::try_concat);
- let Ok(copy_ty) = copy_ty else {
- continue;
+ possible_dest_operand_idxs.truncate(u.int_in_range(1..=3)?);
+ let mut copy_ty: Option<Ty> = None;
+ let mut src_operand_idxs = vec![];
+ let mut dest_operand_idxs = vec![];
+ for src_operand_idx in possible_src_operand_idxs {
+ let operand_type = ssa_vals[operands[src_operand_idx].ssa_val].ty;
+ let proposed_copy_ty = match copy_ty.map(|ty| ty.try_concat(operand_type)) {
+ None => operand_type,
+ Some(Ok(ty)) => ty,
+ Some(Err(_)) => continue,
};
- let mut possible_dest_operand_idxs = possible_dest_operand_idxs.clone();
- let mut dest_operand_idxs = vec![];
+ let mut proposed_dest_operand_idxs = vec![];
let mut dest_copy_ty: Option<Ty> = None;
- for _ in 0..u.int_in_range(1..=3)? {
- if possible_dest_operand_idxs.is_empty() {
- break;
- }
- // dest can't have duplicates, so remove items that were chosen
- let chosen_index = u.choose_index(possible_src_operand_idxs.len())?;
- let dest_operand_idx = possible_dest_operand_idxs.swap_remove(chosen_index);
+ for &dest_operand_idx in &possible_dest_operand_idxs {
let dest_operand_ty = ssa_vals[operands[dest_operand_idx].ssa_val].ty;
- if dest_operand_ty.base_ty != copy_ty.base_ty
- || dest_operand_ty.reg_len > copy_ty.reg_len
+ if dest_operand_ty.base_ty != proposed_copy_ty.base_ty
+ || dest_operand_ty.reg_len > proposed_copy_ty.reg_len
{
continue;
}
} else {
dest_operand_ty
};
- if next_dest_copy_ty.reg_len > copy_ty.reg_len {
+ if next_dest_copy_ty.reg_len > proposed_copy_ty.reg_len {
continue;
}
dest_copy_ty = Some(next_dest_copy_ty);
- dest_operand_idxs.push(dest_operand_idx);
+ proposed_dest_operand_idxs.push(dest_operand_idx);
}
- if dest_copy_ty != Some(copy_ty) || dest_operand_idxs.is_empty() {
+ if dest_copy_ty != Some(proposed_copy_ty) || proposed_dest_operand_idxs.is_empty() {
continue;
}
- return Ok(Some(CopyInstKind {
- src_operand_idxs,
- dest_operand_idxs,
- copy_ty,
- }));
+ copy_ty = Some(proposed_copy_ty);
+ src_operand_idxs.push(src_operand_idx);
+ dest_operand_idxs = proposed_dest_operand_idxs;
}
- Ok(None)
+ Ok(copy_ty.map(|copy_ty| CopyInstKind {
+ src_operand_idxs,
+ dest_operand_idxs,
+ copy_ty,
+ }))
}
fn run(&mut self) -> Result<(), Error> {
let block_count = self.u.int_in_range(1..=10u16)?;
operands.push(Operand {
ssa_val,
kind_and_constraint: KindAndConstraint::Constraint {
- kind: self.u.arbitrary()?,
+ kind,
constraint: Constraint::Any,
},
stage: self.u.arbitrary()?,
}
let inst_kind = if is_term {
let mut succs_and_params = BTreeMap::default();
- let succ_range = BlockIdx::ENTRY_BLOCK.get() as u16..=(block_count - 1);
+ let succ_range = (BlockIdx::ENTRY_BLOCK.get() as u16 + 1)..=(block_count - 1);
if !succ_range.is_empty() {
for i in 0..self.u.int_in_range(0..=3usize)? {
if i > succ_range.len() {
}
}
}
- for inst in &mut self.func.insts {
+ for (inst_idx, inst) in self.func.insts.iter_mut().enumerate() {
+ let inst_idx = InstIdx::new(inst_idx);
let mut reusable_operand_idxs: HashMap<Ty, Vec<usize>> = HashMap::new();
for (operand_idx, operand) in inst.operands.iter().enumerate() {
if operand.kind_and_constraint.kind() == OperandKind::Use {
.push(operand_idx);
}
}
- for operand in &mut inst.operands {
- let KindAndConstraint::Constraint { kind, constraint } = &mut operand.kind_and_constraint else {
+ let mut used_locs = EnumMap::<InstStage, LocSet>::default();
+ for operand_idx in 0..inst.operands.len() {
+ let operand = &inst.operands[operand_idx];
+ let operand_ty = self.func.ssa_vals[operand.ssa_val].ty;
+ if operand.kind_and_constraint.kind() == OperandKind::Def && self.u.arbitrary()? {
+ let reuse_operand_idx = self.u.choose_index(inst.operands.len())?;
+ let reuse_operand = &inst.operands[reuse_operand_idx];
+ if reuse_operand_idx != operand_idx
+ && reuse_operand.kind_and_constraint.kind() == OperandKind::Use
+ && self.func.ssa_vals[reuse_operand.ssa_val].ty == operand_ty
+ {
+ inst.operands[operand_idx].kind_and_constraint = KindAndConstraint::Reuse {
+ kind: OperandKindDefOnly,
+ reuse_operand_idx,
+ };
+ continue;
+ }
+ }
+ let operand = &mut inst.operands[operand_idx];
+ let KindAndConstraint::Constraint {
+ kind,
+ ref mut constraint,..
+ } = operand.kind_and_constraint else {
unreachable!();
};
- // FIXME: change some defs to reuses
- // FIXME: fill in constraint type
- // match kind {
- // OperandKind::Def
- // }
+ *constraint = Constraint::arbitrary_with_ty(operand_ty, self.u)?;
+ if let Some(fixed_loc) = constraint.fixed_loc() {
+ // is the operand probably live for both stages
+ let probably_live_for_both_stages = match (kind, operand.stage) {
+ (OperandKind::Use, InstStage::Late) => true, // also probably live for early stage
+ (OperandKind::Def, InstStage::Early) => true, // also probably live for late stage
+ _ => false,
+ };
+ let mut conflicts = inst
+ .clobbers
+ .clone()
+ .conflicts_with(fixed_loc, self.global_state);
+ if probably_live_for_both_stages {
+ for used_locs in used_locs.values() {
+ conflicts = conflicts
+ || used_locs
+ .to_interned(self.global_state)
+ .conflicts_with(fixed_loc, self.global_state);
+ }
+ } else {
+ conflicts = conflicts
+ || used_locs[operand.stage]
+ .to_interned(self.global_state)
+ .conflicts_with(fixed_loc, self.global_state);
+ }
+ if conflicts {
+ // conflicting constraint, so switch to a safe default instead
+ *constraint = Constraint::Any;
+ } else if probably_live_for_both_stages {
+ for used_locs in used_locs.values_mut() {
+ used_locs.insert(fixed_loc);
+ }
+ } else {
+ used_locs[operand.stage].insert(fixed_loc);
+ }
+ }
}
match inst.kind {
InstKind::Normal => {
if self.u.arbitrary()? {
- if let Some(copy_inst_kind) =
- Self::make_copy_inst_kind(self.u, &self.func.ssa_vals, &inst.operands)?
- {
+ if let Some(copy_inst_kind) = Self::make_copy_inst_kind(
+ self.u,
+ &self.func.ssa_vals,
+ inst_idx,
+ &inst.operands,
+ )? {
inst.kind = InstKind::Copy(copy_inst_kind);
}
}
projects / bigint-presentation-code.git / commitdiff