From 6de83870c8d83b61259cb6ddc339d3a02381965f Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Thu, 2 Feb 2023 23:01:05 -0800 Subject: [PATCH] wrap rest of IR indexes --- register_allocator/src/error.rs | 488 ++++++++++++++++++++++++-- register_allocator/src/function.rs | 529 +++++++++++++++++++++++------ register_allocator/src/fuzzing.rs | 119 +++---- register_allocator/src/index.rs | 106 +++++- 4 files changed, 1019 insertions(+), 223 deletions(-) diff --git a/register_allocator/src/error.rs b/register_allocator/src/error.rs index d504213..30fe203 100644 --- a/register_allocator/src/error.rs +++ b/register_allocator/src/error.rs @@ -1,11 +1,444 @@ use crate::{ - index::{BlockIdx, DisplayOptionIdx, InstIdx, SSAValIdx}, + index::{BlockIdx, BlockParamIdx, DisplayOptionIdx, IndexTy, InstIdx, OperandIdx, SSAValIdx}, loc::{BaseTy, Ty}, }; +use std::fmt; use thiserror::Error; +#[derive(Debug, Error)] +#[error("SSA value index {idx} out of range")] +pub struct SSAValIdxOutOfRange { + pub idx: SSAValIdx, +} + +impl SSAValIdxOutOfRange { + pub fn with_inst_and_operand( + self, + inst: InstIdx, + operand: OperandIdx, + ) -> WithContext< + Option, + InstIdx, + AlwaysNone, + OperandIdx, + AlwaysNone, + SSAValIdxOutOfRange, + > { + WithContext { + block: None, + inst, + succ: AlwaysNone, + operand, + param: AlwaysNone, + out_of_range_error: self, + } + } + pub fn with_block_inst_and_operand( + self, + block: BlockIdx, + inst: InstIdx, + operand: OperandIdx, + ) -> WithContext< + Option, + InstIdx, + AlwaysNone, + OperandIdx, + AlwaysNone, + SSAValIdxOutOfRange, + > { + WithContext { + block: Some(block), + inst, + succ: AlwaysNone, + operand, + param: AlwaysNone, + out_of_range_error: self, + } + } + pub fn with_inst_succ_and_param( + self, + inst: InstIdx, + succ: BlockIdx, + param: BlockParamIdx, + ) -> WithContext< + Option, + InstIdx, + BlockIdx, + AlwaysNone, + BlockParamIdx, + SSAValIdxOutOfRange, + > { + WithContext { + block: None, + inst, + succ, + operand: AlwaysNone, + param, + out_of_range_error: self, + } + } + pub fn with_block_inst_succ_and_param( + self, + block: BlockIdx, + inst: InstIdx, + succ: BlockIdx, + param: BlockParamIdx, + ) -> WithContext< + Option, + InstIdx, + BlockIdx, + AlwaysNone, + BlockParamIdx, + SSAValIdxOutOfRange, + > { + WithContext { + block: Some(block), + inst, + succ, + operand: AlwaysNone, + param, + out_of_range_error: self, + } + } + pub fn with_block_and_param( + self, + block: BlockIdx, + param: BlockParamIdx, + ) -> WithContext + { + WithContext { + block, + inst: AlwaysNone, + succ: AlwaysNone, + operand: AlwaysNone, + param, + out_of_range_error: self, + } + } +} + +#[derive(Debug, Error)] +#[error("instruction index {idx} out of range")] +pub struct InstIdxOutOfRange { + pub idx: InstIdx, +} + +impl InstIdxOutOfRange { + pub fn with_block( + self, + block: BlockIdx, + ) -> WithContext + { + WithContext { + block, + inst: AlwaysNone, + succ: AlwaysNone, + operand: AlwaysNone, + param: AlwaysNone, + out_of_range_error: self, + } + } +} + +#[derive(Debug, Error)] +#[error("block index {idx} out of range")] +pub struct BlockIdxOutOfRange { + pub idx: BlockIdx, +} + +#[derive(Debug, Error)] +#[error("block parameter index {idx} is out of range")] +pub struct BlockParamIdxOutOfRange { + pub idx: BlockParamIdx, +} + +impl BlockParamIdxOutOfRange { + pub fn with_block( + self, + block: BlockIdx, + ) -> WithContext< + BlockIdx, + AlwaysNone, + AlwaysNone, + AlwaysNone, + AlwaysNone, + BlockParamIdxOutOfRange, + > { + WithContext { + block, + inst: AlwaysNone, + succ: AlwaysNone, + operand: AlwaysNone, + param: AlwaysNone, + out_of_range_error: self, + } + } + pub fn with_block_inst_and_succ( + self, + block: BlockIdx, + inst: InstIdx, + succ: BlockIdx, + ) -> WithContext< + Option, + InstIdx, + BlockIdx, + AlwaysNone, + AlwaysNone, + BlockParamIdxOutOfRange, + > { + WithContext { + block: Some(block), + inst, + succ, + operand: AlwaysNone, + param: AlwaysNone, + out_of_range_error: self, + } + } + pub fn with_inst_and_succ( + self, + inst: InstIdx, + succ: BlockIdx, + ) -> WithContext< + Option, + InstIdx, + BlockIdx, + AlwaysNone, + AlwaysNone, + BlockParamIdxOutOfRange, + > { + WithContext { + block: None, + inst, + succ, + operand: AlwaysNone, + param: AlwaysNone, + out_of_range_error: self, + } + } +} + +#[derive(Debug, Error)] +#[error("operand index {idx} is out of range")] +pub struct OperandIdxOutOfRange { + pub idx: OperandIdx, +} + +impl OperandIdxOutOfRange { + pub fn with_block_and_inst( + self, + block: BlockIdx, + inst: InstIdx, + ) -> WithContext< + Option, + InstIdx, + AlwaysNone, + AlwaysNone, + AlwaysNone, + OperandIdxOutOfRange, + > { + WithContext { + block: Some(block), + inst, + succ: AlwaysNone, + operand: AlwaysNone, + param: AlwaysNone, + out_of_range_error: self, + } + } + pub fn with_inst( + self, + inst: InstIdx, + ) -> WithContext< + Option, + InstIdx, + AlwaysNone, + AlwaysNone, + AlwaysNone, + OperandIdxOutOfRange, + > { + WithContext { + block: None, + inst, + succ: AlwaysNone, + operand: AlwaysNone, + param: AlwaysNone, + out_of_range_error: self, + } + } +} + +#[derive(Default, Clone, Copy, Debug)] +pub struct AlwaysNone; + +pub trait ToContextValue: fmt::Debug + Copy { + fn to_context_value(self) -> Option; +} + +impl ToContextValue for AlwaysNone { + fn to_context_value(self) -> Option { + None + } +} + +impl ToContextValue for T { + fn to_context_value(self) -> Option { + Some(self) + } +} + +impl ToContextValue for Option { + fn to_context_value(self) -> Option { + self + } +} + +#[derive(Debug, Error)] +pub struct WithContext +where + Block: ToContextValue, + Inst: ToContextValue, + Succ: ToContextValue, + Operand: ToContextValue, + BlockParam: ToContextValue, +{ + pub block: Block, + pub inst: Inst, + pub succ: Succ, + pub operand: Operand, + pub param: BlockParam, + #[source] + pub out_of_range_error: E, +} + +impl fmt::Display + for WithContext +where + Block: ToContextValue, + Inst: ToContextValue, + Succ: ToContextValue, + Operand: ToContextValue, + BlockParam: ToContextValue, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let Self { + block, + inst, + succ, + operand, + param, + out_of_range_error: _, + } = self; + let block = block.to_context_value(); + let inst = inst.to_context_value(); + let succ = succ.to_context_value(); + let operand = operand.to_context_value(); + let param = param.to_context_value(); + macro_rules! write_if { + ($field:ident, $f:ident, $($rest:tt)+) => { + if let Some($field) = $field { + write!($f, $($rest)+)?; + } + }; + } + if block.is_some() || inst.is_some() { + write!(f, " in ")?; + } + write_if!(block, f, "{block}"); + if block.is_some() && inst.is_some() { + write!(f, ":")?; + } + write_if!(inst, f, "{inst}"); + write_if!(succ, f, " in successor {succ}"); + write_if!(operand, f, " in {operand}"); + write_if!(param, f, " in block parameter {param}"); + Ok(()) + } +} + #[derive(Debug, Error)] pub enum Error { + #[error(transparent)] + SSAValIdxOutOfRangeWithBlockInstAndOperand( + #[from] + WithContext< + Option, + InstIdx, + AlwaysNone, + OperandIdx, + AlwaysNone, + SSAValIdxOutOfRange, + >, + ), + #[error(transparent)] + SSAValIdxOutOfRangeWithBlockInstSuccAndParam( + #[from] + WithContext< + Option, + InstIdx, + BlockIdx, + AlwaysNone, + BlockParamIdx, + SSAValIdxOutOfRange, + >, + ), + #[error(transparent)] + SSAValIdxOutOfRangeWithBlockAndParam( + #[from] + WithContext< + BlockIdx, + AlwaysNone, + AlwaysNone, + AlwaysNone, + BlockParamIdx, + SSAValIdxOutOfRange, + >, + ), + #[error(transparent)] + InstIdxOutOfRangeWithBlock( + #[from] + WithContext, + ), + #[error(transparent)] + InstIdxOutOfRange(#[from] InstIdxOutOfRange), + #[error(transparent)] + BlockIdxOutOfRange(#[from] BlockIdxOutOfRange), + #[error(transparent)] + BlockParamIdxOutOfRangeWithBlock( + #[from] + WithContext< + BlockIdx, + AlwaysNone, + AlwaysNone, + AlwaysNone, + AlwaysNone, + BlockParamIdxOutOfRange, + >, + ), + #[error(transparent)] + BlockParamIdxOutOfRangeWithBlockInstAndSucc( + #[from] + WithContext< + Option, + InstIdx, + BlockIdx, + AlwaysNone, + AlwaysNone, + BlockParamIdxOutOfRange, + >, + ), + #[error(transparent)] + OperandIdxOutOfRangeWithBlockAndInst( + #[from] + WithContext< + Option, + InstIdx, + AlwaysNone, + AlwaysNone, + AlwaysNone, + OperandIdxOutOfRange, + >, + ), #[error("can't create a vector of an only-scalar type: {base_ty:?}")] TriedToCreateVectorOfOnlyScalarType { base_ty: BaseTy }, #[error("reg_len out of range")] @@ -49,16 +482,11 @@ pub enum Error { TermInstOnlyAllowedAtBlockEnd { inst_idx: InstIdx }, #[error("instruction not in a block: {inst}")] InstHasNoBlock { inst: InstIdx }, - #[error("operand index {operand_idx} out of range for {inst}")] - OperandIndexOutOfRange { inst: InstIdx, operand_idx: usize }, #[error("duplicate copy destination operand: operand index {operand_idx} for {inst}")] - DupCopyDestOperand { inst: InstIdx, operand_idx: usize }, - #[error("SSA value index {idx} out of range")] - SSAValIdxOutOfRange { idx: SSAValIdx }, - #[error("instruction index {idx} out of range")] - InstIdxOutOfRange { idx: InstIdx }, - #[error("block index {idx} out of range")] - BlockIdxOutOfRange { idx: BlockIdx }, + DupCopyDestOperand { + inst: InstIdx, + operand_idx: OperandIdx, + }, #[error("copy instruction's source type doesn't match source operands")] CopySrcTyMismatch { inst: InstIdx }, #[error("copy instruction's destination type doesn't match destination operands")] @@ -70,7 +498,7 @@ pub enum Error { MissingOperandUse { ssa_val_idx: SSAValIdx, inst: InstIdx, - operand_idx: usize, + operand_idx: OperandIdx, }, #[error( "operand index {operand_idx} for {inst} has kind `Def` but isn't \ @@ -79,7 +507,7 @@ pub enum Error { OperandDefIsNotSSAValDef { ssa_val_idx: SSAValIdx, inst: InstIdx, - operand_idx: usize, + operand_idx: OperandIdx, }, #[error( "SSA value {ssa_val_idx}'s definition isn't the corresponding \ @@ -88,7 +516,7 @@ pub enum Error { SSAValDefIsNotOperandsSSAVal { ssa_val_idx: SSAValIdx, inst: InstIdx, - operand_idx: usize, + operand_idx: OperandIdx, }, #[error( "SSA value {ssa_val_idx}'s type can't be used with the constraint on \ @@ -97,13 +525,16 @@ pub enum Error { ConstraintTyMismatch { ssa_val_idx: SSAValIdx, inst: InstIdx, - operand_idx: usize, + operand_idx: OperandIdx, }, #[error( "fixed location constraint on operand index {operand_idx} for \ {inst} conflicts with clobbers" )] - FixedLocConflictsWithClobbers { inst: InstIdx, operand_idx: usize }, + FixedLocConflictsWithClobbers { + inst: InstIdx, + operand_idx: OperandIdx, + }, #[error("operand kind must be def")] OperandKindMustBeDef, #[error( @@ -112,7 +543,7 @@ pub enum Error { )] ReuseTargetOperandMustBeUse { inst: InstIdx, - reuse_target_operand_idx: usize, + reuse_target_operand_idx: OperandIdx, }, #[error( "source block {src_block} missing from branch {branch_inst}'s \ @@ -131,7 +562,7 @@ pub enum Error { ssa_val_idx: SSAValIdx, inst: InstIdx, succ: BlockIdx, - param_idx: usize, + param_idx: BlockParamIdx, }, #[error( "the number of parameters ({branch_param_count}) for branch {inst}'s \ @@ -152,7 +583,7 @@ pub enum Error { BranchSuccParamTyMismatch { inst: InstIdx, succ: BlockIdx, - param_idx: usize, + param_idx: BlockParamIdx, block_param_ty: Ty, branch_param_ty: Ty, }, @@ -163,7 +594,7 @@ pub enum Error { MismatchedBlockParamDef { ssa_val_idx: SSAValIdx, block: BlockIdx, - param_idx: usize, + param_idx: BlockParamIdx, }, #[error( "predecessor {src_block} of target block {tgt_block} is missing from \ @@ -174,8 +605,6 @@ pub enum Error { branch_inst: InstIdx, tgt_block: BlockIdx, }, - #[error("block parameter index {param_idx} is out of range for block {block}")] - BlockParamIdxOutOfRange { block: BlockIdx, param_idx: usize }, #[error( "SSA value {ssa_val_idx}'s use isn't the corresponding \ operand's SSA Value: operand index {operand_idx} for {inst}" @@ -183,7 +612,7 @@ pub enum Error { SSAValUseIsNotOperandsSSAVal { ssa_val_idx: SSAValIdx, inst: InstIdx, - operand_idx: usize, + operand_idx: OperandIdx, }, #[error( "SSA value {ssa_val_idx} is use as a branch instruction {inst}'s \ @@ -200,15 +629,6 @@ pub enum Error { branch_inst: InstIdx, tgt_block: BlockIdx, }, - #[error( - "branch instruction {branch_inst}'s block parameter index {param_idx} \ - is out of range for target block {tgt_block}" - )] - BranchTargetParamIdxOutOfRange { - branch_inst: InstIdx, - tgt_block: BlockIdx, - param_idx: usize, - }, #[error( "SSA value {ssa_val_idx}'s use isn't the corresponding \ branch {branch_inst}'s target block parameter's SSA Value for \ @@ -218,7 +638,7 @@ pub enum Error { ssa_val_idx: SSAValIdx, branch_inst: InstIdx, tgt_block: BlockIdx, - param_idx: usize, + param_idx: BlockParamIdx, }, #[error( "block {block_idx} has incorrect immediate dominator: expected \ @@ -248,8 +668,8 @@ pub enum Error { )] ReuseOperandTyMismatch { inst: InstIdx, - tgt_operand_idx: usize, - src_operand_idx: usize, + tgt_operand_idx: OperandIdx, + src_operand_idx: OperandIdx, src_ty: Ty, tgt_ty: Ty, }, diff --git a/register_allocator/src/function.rs b/register_allocator/src/function.rs index cff8039..02419e5 100644 --- a/register_allocator/src/function.rs +++ b/register_allocator/src/function.rs @@ -1,6 +1,11 @@ use crate::{ - error::{Error, Result}, - index::{BlockIdx, InstIdx, InstRange, SSAValIdx}, + error::{ + BlockIdxOutOfRange, BlockParamIdxOutOfRange, Error, InstIdxOutOfRange, + OperandIdxOutOfRange, Result, SSAValIdxOutOfRange, + }, + index::{ + BlockIdx, BlockParamIdx, IndexTy, InstIdx, InstRange, OperandIdx, RangeIter, SSAValIdx, + }, interned::{GlobalState, Intern, Interned}, loc::{BaseTy, Loc, Ty}, loc_set::LocSet, @@ -18,34 +23,53 @@ use serde::{Deserialize, Serialize}; use smallvec::SmallVec; use std::{ collections::{btree_map, BTreeMap, BTreeSet}, + iter::FusedIterator, mem, ops::{Index, IndexMut}, }; #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash, Serialize, Deserialize)] pub enum SSAValDef { - BlockParam { block: BlockIdx, param_idx: usize }, - Operand { inst: InstIdx, operand_idx: usize }, + BlockParam { + block: BlockIdx, + param_idx: BlockParamIdx, + }, + Operand { + inst: InstIdx, + operand_idx: OperandIdx, + }, +} + +impl SSAValDef { + pub const fn invalid() -> Self { + SSAValDef::BlockParam { + block: BlockIdx::ENTRY_BLOCK, + param_idx: BlockParamIdx::new(!0), + } + } } #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize)] pub struct BranchSuccParamUse { pub branch_inst: InstIdx, pub succ: BlockIdx, - pub param_idx: usize, + pub param_idx: BlockParamIdx, } #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize)] pub struct OperandUse { pub inst: InstIdx, - pub operand_idx: usize, + pub operand_idx: OperandIdx, } #[derive(Clone, PartialEq, Eq, Debug, Hash, Serialize, Deserialize)] pub struct SSAVal { pub ty: Ty, + #[serde(skip, default = "SSAValDef::invalid")] pub def: SSAValDef, + #[serde(skip)] pub operand_uses: BTreeSet, + #[serde(skip)] pub branch_succ_param_uses: BTreeSet, } @@ -333,7 +357,7 @@ impl From for OperandKind { pub enum KindAndConstraint { Reuse { kind: OperandKindDefOnly, - reuse_operand_idx: usize, + reuse_operand_idx: OperandIdx, }, Constraint { kind: OperandKind, @@ -409,9 +433,9 @@ impl Operand { } fn validate( self, - _block: BlockIdx, + block: BlockIdx, inst: InstIdx, - operand_idx: usize, + operand_idx: OperandIdx, func: &FnFields, global_state: &GlobalState, ) -> Result<()> { @@ -420,7 +444,10 @@ impl Operand { kind_and_constraint, stage: _, } = self; - let ssa_val = func.try_get_ssa_val(ssa_val_idx)?; + let ssa_val = func + .ssa_vals + .try_index(ssa_val_idx) + .map_err(|e| e.with_block_inst_and_operand(block, inst, operand_idx))?; match kind_and_constraint.kind() { OperandKind::Use => { if !ssa_val @@ -451,7 +478,10 @@ impl Operand { } = self.kind_and_constraint { let reuse_src = func.try_get_operand(inst, reuse_operand_idx)?; - let reuse_src_ssa_val = func.try_get_ssa_val(reuse_src.ssa_val)?; + let reuse_src_ssa_val = func + .ssa_vals + .try_index(reuse_src.ssa_val) + .map_err(|e| e.with_block_inst_and_operand(block, inst, reuse_operand_idx))?; if ssa_val.ty != reuse_src_ssa_val.ty { return Err(Error::ReuseOperandTyMismatch { inst, @@ -472,7 +502,8 @@ impl Operand { })?; if let Some(fixed_loc) = constraint.fixed_loc() { if func - .try_get_inst(inst)? + .insts + .try_index(inst)? .clobbers .clone() .conflicts_with(fixed_loc, global_state) @@ -487,17 +518,24 @@ impl Operand { /// copy concatenates all `srcs` together and de-concatenates the result into all `dests`. #[derive(Clone, PartialEq, Eq, Debug, Hash, Serialize, Deserialize)] pub struct CopyInstKind { - pub src_operand_idxs: Vec, - pub dest_operand_idxs: Vec, + pub src_operand_idxs: Vec, + pub dest_operand_idxs: Vec, pub copy_ty: Ty, } impl CopyInstKind { - fn calc_copy_ty(operand_idxs: &[usize], inst: InstIdx, func: &FnFields) -> Result> { + fn calc_copy_ty( + operand_idxs: &[OperandIdx], + inst: InstIdx, + func: &FnFields, + ) -> Result> { let mut retval: Option = None; for &operand_idx in operand_idxs { let operand = func.try_get_operand(inst, operand_idx)?; - let ssa_val = func.try_get_ssa_val(operand.ssa_val)?; + let ssa_val = func + .ssa_vals + .try_index(operand.ssa_val) + .map_err(|e| e.with_inst_and_operand(inst, operand_idx))?; retval = Some(match retval { Some(retval) => retval.try_concat(ssa_val.ty)?, None => ssa_val.ty, @@ -593,8 +631,8 @@ impl Inst { Error::TermInstOnlyAllowedAtBlockEnd { inst_idx: inst } }); } - for (idx, operand) in operands.iter().enumerate() { - operand.validate(block, inst, idx, func, global_state)?; + for (operand_idx, operand) in operands.entries() { + operand.validate(block, inst, operand_idx, func, global_state)?; } match kind { InstKind::Normal => {} @@ -606,12 +644,14 @@ impl Inst { let mut seen_dest_operands = SmallVec::<[bool; 16]>::new(); seen_dest_operands.resize(operands.len(), false); for &dest_operand_idx in dest_operand_idxs { - let seen_dest_operand = seen_dest_operands.get_mut(dest_operand_idx).ok_or( - Error::OperandIndexOutOfRange { - inst, - operand_idx: dest_operand_idx, - }, - )?; + let seen_dest_operand = seen_dest_operands + .get_mut(dest_operand_idx.get()) + .ok_or_else(|| { + OperandIdxOutOfRange { + idx: dest_operand_idx, + } + .with_inst(inst) + })?; if mem::replace(seen_dest_operand, true) { return Err(Error::DupCopyDestOperand { inst, @@ -628,7 +668,7 @@ impl Inst { } InstKind::BlockTerm(BlockTermInstKind { succs_and_params }) => { for (&succ_idx, params) in succs_and_params { - let succ = func.try_get_block(succ_idx)?; + let succ = func.blocks.try_index(succ_idx)?; if !succ.preds.contains(&block) { return Err(Error::SrcBlockMissingFromBranchTgtBlocksPreds { src_block: block, @@ -644,11 +684,17 @@ impl Inst { branch_param_count: params.len(), }); } - for (param_idx, (&branch_ssa_val_idx, &block_ssa_val_idx)) in - params.iter().zip(&succ.params).enumerate() + for ((param_idx, &branch_ssa_val_idx), &block_ssa_val_idx) in + params.entries().zip(&succ.params) { - let branch_ssa_val = func.try_get_ssa_val(branch_ssa_val_idx)?; - let block_ssa_val = func.try_get_ssa_val(block_ssa_val_idx)?; + let branch_ssa_val = func + .ssa_vals + .try_index(branch_ssa_val_idx) + .map_err(|e| e.with_inst_succ_and_param(inst, succ_idx, param_idx))?; + let block_ssa_val = func + .ssa_vals + .try_index(block_ssa_val_idx) + .map_err(|e| e.with_block_and_param(succ_idx, param_idx))?; if !branch_ssa_val .branch_succ_param_uses .contains(&BranchSuccParamUse { @@ -679,10 +725,10 @@ impl Inst { } Ok(()) } - pub fn try_get_operand(&self, inst: InstIdx, operand_idx: usize) -> Result<&Operand> { + pub fn try_get_operand(&self, inst: InstIdx, operand_idx: OperandIdx) -> Result<&Operand> { self.operands - .get(operand_idx) - .ok_or(Error::OperandIndexOutOfRange { inst, operand_idx }) + .try_index(operand_idx) + .map_err(|e| e.with_inst(inst).into()) } } @@ -732,8 +778,11 @@ impl Block { for inst in *insts { func.insts[inst].validate(block, inst, func, global_state)?; } - for (param_idx, &ssa_val_idx) in params.iter().enumerate() { - let ssa_val = func.try_get_ssa_val(ssa_val_idx)?; + for (param_idx, &ssa_val_idx) in params.entries() { + let ssa_val = func + .ssa_vals + .try_index(ssa_val_idx) + .map_err(|e| e.with_block_and_param(block, param_idx))?; let def = SSAValDef::BlockParam { block, param_idx }; if ssa_val.def != def { return Err(Error::MismatchedBlockParamDef { @@ -784,6 +833,7 @@ impl Function { } pub fn new_with_global_state(mut fields: FnFields, global_state: &GlobalState) -> Result { fields.fill_start_inst_to_block_map(); + fields.fill_ssa_defs_uses()?; let FnFields { ssa_vals, insts: _, @@ -793,12 +843,11 @@ impl Function { blocks .get(BlockIdx::ENTRY_BLOCK.get()) .ok_or(Error::MissingEntryBlock)?; - for (idx, block) in blocks.iter().enumerate() { - block.validate(BlockIdx::new(idx), &fields, global_state)?; + for (block_idx, block) in blocks.entries() { + block.validate(block_idx, &fields, global_state)?; } let dominators = dominators::simple_fast(&fields, BlockIdx::ENTRY_BLOCK); - for (idx, block) in blocks.iter().enumerate() { - let block_idx = BlockIdx::new(idx); + for (block_idx, block) in blocks.entries() { let expected = dominators.immediate_dominator(block_idx); if block.immediate_dominator != expected { return Err(Error::IncorrectImmediateDominator { @@ -808,8 +857,8 @@ impl Function { }); } } - for (idx, ssa_val) in ssa_vals.iter().enumerate() { - ssa_val.validate(SSAValIdx::new(idx), &fields)?; + for (ssa_val_idx, ssa_val) in ssa_vals.entries() { + ssa_val.validate(ssa_val_idx, &fields)?; } Ok(Self(fields)) } @@ -827,46 +876,94 @@ impl Function { impl FnFields { pub fn fill_start_inst_to_block_map(&mut self) { self.start_inst_to_block_map.clear(); - for (idx, block) in self.blocks.iter().enumerate() { - let block_idx = BlockIdx::new(idx); + for (block_idx, block) in self.blocks.entries() { if block_idx != BlockIdx::ENTRY_BLOCK { self.start_inst_to_block_map .insert(block.insts.start, block_idx); } } } - pub fn try_get_ssa_val(&self, idx: SSAValIdx) -> Result<&SSAVal> { - self.ssa_vals - .get(idx.get()) - .ok_or(Error::SSAValIdxOutOfRange { idx }) - } - pub fn try_get_inst(&self, idx: InstIdx) -> Result<&Inst> { - self.insts - .get(idx.get()) - .ok_or(Error::InstIdxOutOfRange { idx }) - } - pub fn try_get_inst_mut(&mut self, idx: InstIdx) -> Result<&mut Inst> { - self.insts - .get_mut(idx.get()) - .ok_or(Error::InstIdxOutOfRange { idx }) - } - pub fn try_get_operand(&self, inst: InstIdx, operand_idx: usize) -> Result<&Operand> { - self.try_get_inst(inst)?.try_get_operand(inst, operand_idx) + pub fn fill_ssa_defs_uses(&mut self) -> Result<()> { + for ssa_val in &mut self.ssa_vals { + ssa_val.branch_succ_param_uses.clear(); + ssa_val.operand_uses.clear(); + ssa_val.def = SSAValDef::invalid(); + } + for (block_idx, block) in self.blocks.entries() { + for (param_idx, ¶m) in block.params.entries() { + self.ssa_vals + .try_index_mut(param) + .map_err(|e| e.with_block_and_param(block_idx, param_idx))? + .def = SSAValDef::BlockParam { + block: block_idx, + param_idx, + }; + } + } + for (inst_idx, inst) in self.insts.entries() { + for (operand_idx, operand) in inst.operands.entries() { + let ssa_val = self + .ssa_vals + .try_index_mut(operand.ssa_val) + .map_err(|e| e.with_inst_and_operand(inst_idx, operand_idx))?; + match operand.kind_and_constraint.kind() { + OperandKind::Use => { + ssa_val.operand_uses.insert(OperandUse { + inst: inst_idx, + operand_idx, + }); + } + OperandKind::Def => { + ssa_val.def = SSAValDef::Operand { + inst: inst_idx, + operand_idx, + }; + } + } + } + match &inst.kind { + InstKind::Normal | InstKind::Copy(_) => {} + InstKind::BlockTerm(BlockTermInstKind { succs_and_params }) => { + for (&succ, params) in succs_and_params { + for (param_idx, ¶m) in params.entries() { + let ssa_val = self.ssa_vals.try_index_mut(param).map_err(|e| { + e.with_inst_succ_and_param(inst_idx, succ, param_idx) + })?; + ssa_val.branch_succ_param_uses.insert(BranchSuccParamUse { + branch_inst: inst_idx, + succ, + param_idx, + }); + } + } + } + } + } + Ok(()) } - pub fn try_get_block(&self, idx: BlockIdx) -> Result<&Block> { - self.blocks - .get(idx.get()) - .ok_or(Error::BlockIdxOutOfRange { idx }) + pub fn try_get_operand(&self, inst: InstIdx, operand_idx: OperandIdx) -> Result<&Operand> { + Ok(self + .insts + .try_index(inst)? + .operands + .try_index(operand_idx) + .map_err(|e| e.with_inst(inst))?) } - pub fn try_get_block_param(&self, block: BlockIdx, param_idx: usize) -> Result { - self.try_get_block(block)? + pub fn try_get_block_param( + &self, + block: BlockIdx, + param_idx: BlockParamIdx, + ) -> Result { + Ok(*self + .blocks + .try_index(block)? .params - .get(param_idx) - .copied() - .ok_or(Error::BlockParamIdxOutOfRange { block, param_idx }) + .try_index(param_idx) + .map_err(|e| e.with_block(block))?) } pub fn try_get_block_term_inst_idx(&self, block: BlockIdx) -> Result { - self.try_get_block(block)? + self.blocks + .try_index(block)? .insts .last() .ok_or(Error::BlockIsEmpty { block }) @@ -877,7 +974,8 @@ impl FnFields { ) -> Result<(InstIdx, &BlockTermInstKind)> { let term_idx = self.try_get_block_term_inst_idx(block)?; let term_kind = self - .try_get_inst(term_idx)? + .insts + .try_index(term_idx)? .kind .block_term() .ok_or(Error::BlocksLastInstMustBeTerm { term_idx })?; @@ -889,7 +987,8 @@ impl FnFields { ) -> Result<(InstIdx, &mut BlockTermInstKind)> { let term_idx = self.try_get_block_term_inst_idx(block)?; let term_kind = self - .try_get_inst_mut(term_idx)? + .insts + .try_index_mut(term_idx)? .kind .block_term_mut() .ok_or(Error::BlocksLastInstMustBeTerm { term_idx })?; @@ -900,7 +999,7 @@ impl FnFields { branch_inst: InstIdx, succ: BlockIdx, ) -> Result<&[SSAValIdx]> { - let inst = self.try_get_inst(branch_inst)?; + let inst = self.insts.try_index(branch_inst)?; let BlockTermInstKind { succs_and_params } = inst .kind .block_term() @@ -916,16 +1015,12 @@ impl FnFields { &self, branch_inst: InstIdx, succ: BlockIdx, - param_idx: usize, + param_idx: BlockParamIdx, ) -> Result { Ok(*self .try_get_branch_target_params(branch_inst, succ)? - .get(param_idx) - .ok_or(Error::BranchTargetParamIdxOutOfRange { - branch_inst, - tgt_block: succ, - param_idx, - })?) + .try_index(param_idx) + .map_err(|e: BlockParamIdxOutOfRange| e.with_inst_and_succ(branch_inst, succ))?) } pub fn inst_to_block(&self, inst: InstIdx) -> BlockIdx { self.start_inst_to_block_map @@ -936,46 +1031,268 @@ impl FnFields { } } -impl Index for Vec { - type Output = SSAVal; +pub trait Entries<'a, I>: Index +where + I: IndexTy, + Self::Output: 'a, +{ + type Iter: Iterator + + DoubleEndedIterator + + ExactSizeIterator + + FusedIterator; + fn entries(&'a self) -> Self::Iter; + fn keys(&'a self) -> RangeIter; +} - fn index(&self, index: SSAValIdx) -> &Self::Output { - &self[index.get()] - } +pub trait EntriesMut<'a, I>: Entries<'a, I> + IndexMut +where + I: IndexTy, + Self::Output: 'a, +{ + type IterMut: Iterator + + DoubleEndedIterator + + ExactSizeIterator + + FusedIterator; + fn entries_mut(&'a mut self) -> Self::IterMut; } -impl IndexMut for Vec { - fn index_mut(&mut self, index: SSAValIdx) -> &mut Self::Output { - &mut self[index.get()] - } +pub trait TryIndex: for<'a> Entries<'a, I> +where + I: IndexTy, +{ + type Error; + fn try_index(&self, idx: I) -> Result<&Self::Output, Self::Error>; } -impl Index for Vec { - type Output = Inst; +pub trait TryIndexMut: TryIndex + for<'a> EntriesMut<'a, I> +where + I: IndexTy, +{ + fn try_index_mut(&mut self, idx: I) -> Result<&mut Self::Output, Self::Error>; +} - fn index(&self, index: InstIdx) -> &Self::Output { - &self[index.get()] - } +macro_rules! impl_index { + ( + #[error = $Error:ident, iter = $Iter:ident, iter_mut = $IterMut:ident] + impl Index<$I:ty> for Vec<$T:ty> {} + ) => { + #[derive(Clone, Debug)] + pub struct $Iter<'a> { + iter: std::iter::Enumerate>, + } + + impl<'a> Iterator for $Iter<'a> { + type Item = ($I, &'a $T); + + fn next(&mut self) -> Option { + self.iter.next().map(|(i, v)| (<$I>::new(i), v)) + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + fn fold(self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter + .fold(init, move |a, (i, v)| f(a, (<$I>::new(i), v))) + } + } + + impl DoubleEndedIterator for $Iter<'_> { + fn next_back(&mut self) -> Option { + self.iter.next_back().map(|(i, v)| (<$I>::new(i), v)) + } + + fn rfold(self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter + .rfold(init, move |a, (i, v)| f(a, (<$I>::new(i), v))) + } + } + + impl ExactSizeIterator for $Iter<'_> { + fn len(&self) -> usize { + self.iter.len() + } + } + + impl FusedIterator for $Iter<'_> {} + + #[derive(Debug)] + pub struct $IterMut<'a> { + iter: std::iter::Enumerate>, + } + + impl<'a> Iterator for $IterMut<'a> { + type Item = ($I, &'a mut $T); + + fn next(&mut self) -> Option { + self.iter.next().map(|(i, v)| (<$I>::new(i), v)) + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + fn fold(self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter + .fold(init, move |a, (i, v)| f(a, (<$I>::new(i), v))) + } + } + + impl DoubleEndedIterator for $IterMut<'_> { + fn next_back(&mut self) -> Option { + self.iter.next_back().map(|(i, v)| (<$I>::new(i), v)) + } + + fn rfold(self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.iter + .rfold(init, move |a, (i, v)| f(a, (<$I>::new(i), v))) + } + } + + impl ExactSizeIterator for $IterMut<'_> { + fn len(&self) -> usize { + self.iter.len() + } + } + + impl FusedIterator for $IterMut<'_> {} + + impl Index<$I> for Vec<$T> { + type Output = $T; + + fn index(&self, index: $I) -> &Self::Output { + &self[index.get()] + } + } + + impl IndexMut<$I> for Vec<$T> { + fn index_mut(&mut self, index: $I) -> &mut Self::Output { + &mut self[index.get()] + } + } + + impl<'a> Entries<'a, $I> for Vec<$T> { + type Iter = $Iter<'a>; + fn entries(&'a self) -> Self::Iter { + $Iter { + iter: (**self).iter().enumerate(), + } + } + fn keys(&'a self) -> RangeIter<$I> { + RangeIter::from_usize_range(0..self.len()) + } + } + + impl<'a> EntriesMut<'a, $I> for Vec<$T> { + type IterMut = $IterMut<'a>; + fn entries_mut(&'a mut self) -> Self::IterMut { + $IterMut { + iter: (**self).iter_mut().enumerate(), + } + } + } + + impl TryIndex<$I> for Vec<$T> { + type Error = $Error; + + fn try_index(&self, idx: $I) -> Result<&Self::Output, Self::Error> { + self.get(idx.get()).ok_or($Error { idx }) + } + } + + impl TryIndexMut<$I> for Vec<$T> { + fn try_index_mut(&mut self, idx: $I) -> Result<&mut Self::Output, Self::Error> { + self.get_mut(idx.get()).ok_or($Error { idx }) + } + } + + impl Index<$I> for [$T] { + type Output = $T; + + fn index(&self, index: $I) -> &Self::Output { + &self[index.get()] + } + } + + impl IndexMut<$I> for [$T] { + fn index_mut(&mut self, index: $I) -> &mut Self::Output { + &mut self[index.get()] + } + } + + impl<'a> Entries<'a, $I> for [$T] { + type Iter = $Iter<'a>; + fn entries(&'a self) -> Self::Iter { + $Iter { + iter: self.iter().enumerate(), + } + } + fn keys(&'a self) -> RangeIter<$I> { + RangeIter::from_usize_range(0..self.len()) + } + } + + impl<'a> EntriesMut<'a, $I> for [$T] { + type IterMut = $IterMut<'a>; + fn entries_mut(&'a mut self) -> Self::IterMut { + $IterMut { + iter: self.iter_mut().enumerate(), + } + } + } + + impl TryIndex<$I> for [$T] { + type Error = $Error; + + fn try_index(&self, idx: $I) -> Result<&Self::Output, Self::Error> { + self.get(idx.get()).ok_or($Error { idx }) + } + } + + impl TryIndexMut<$I> for [$T] { + fn try_index_mut(&mut self, idx: $I) -> Result<&mut Self::Output, Self::Error> { + self.get_mut(idx.get()).ok_or($Error { idx }) + } + } + }; } -impl IndexMut for Vec { - fn index_mut(&mut self, index: InstIdx) -> &mut Self::Output { - &mut self[index.get()] - } +impl_index! { + #[error = SSAValIdxOutOfRange, iter = SSAValEntriesIter, iter_mut = SSAValEntriesIterMut] + impl Index for Vec {} } -impl Index for Vec { - type Output = Block; +impl_index! { + #[error = BlockParamIdxOutOfRange, iter = BlockParamEntriesIter, iter_mut = BlockParamEntriesIterMut] + impl Index for Vec {} +} - fn index(&self, index: BlockIdx) -> &Self::Output { - &self[index.get()] - } +impl_index! { + #[error = OperandIdxOutOfRange, iter = OperandEntriesIter, iter_mut = OperandEntriesIterMut] + impl Index for Vec {} } -impl IndexMut for Vec { - fn index_mut(&mut self, index: BlockIdx) -> &mut Self::Output { - &mut self[index.get()] - } +impl_index! { + #[error = InstIdxOutOfRange, iter = InstEntriesIter, iter_mut = InstEntriesIterMut] + impl Index for Vec {} +} + +impl_index! { + #[error = BlockIdxOutOfRange, iter = BlockEntriesIter, iter_mut = BlockEntriesIterMut] + impl Index for Vec {} } impl GraphBase for FnFields { diff --git a/register_allocator/src/fuzzing.rs b/register_allocator/src/fuzzing.rs index 235ed73..25748ad 100644 --- a/register_allocator/src/fuzzing.rs +++ b/register_allocator/src/fuzzing.rs @@ -1,11 +1,11 @@ #![cfg(feature = "fuzzing")] use crate::{ function::{ - Block, BlockTermInstKind, BranchSuccParamUse, Constraint, CopyInstKind, FnFields, Inst, - InstKind, InstStage, KindAndConstraint, Operand, OperandKind, OperandKindDefOnly, - OperandUse, SSAVal, SSAValDef, + Block, BlockTermInstKind, Constraint, CopyInstKind, Entries, EntriesMut, FnFields, Inst, + InstKind, InstStage, KindAndConstraint, Operand, OperandKind, OperandKindDefOnly, SSAVal, + SSAValDef, }, - index::{BlockIdx, InstIdx, InstRange, SSAValIdx}, + index::{BlockIdx, InstIdx, InstRange, OperandIdx, RangeIter, SSAValIdx}, interned::{GlobalState, Intern}, loc::Ty, loc_set::LocSet, @@ -78,11 +78,11 @@ impl FnBuilder<'_, '_, '_> { let idom = self.func.blocks[block_idx].immediate_dominator; self.available_ssa_vals_at_end(idom) } - fn new_ssa_val(ssa_vals: &mut Vec, ty: Ty, def: SSAValDef) -> SSAValIdx { + fn new_ssa_val(ssa_vals: &mut Vec, ty: Ty) -> SSAValIdx { let retval = SSAValIdx::new(ssa_vals.len()); ssa_vals.push(SSAVal { ty, - def, + def: SSAValDef::invalid(), operand_uses: Default::default(), branch_succ_param_uses: Default::default(), }); @@ -117,7 +117,7 @@ impl FnBuilder<'_, '_, '_> { } let mut possible_src_operand_idxs = vec![]; let mut possible_dest_operand_idxs = vec![]; - for (operand_idx, operand) in operands.iter().enumerate() { + for (operand_idx, operand) in operands.entries() { match operand.kind_and_constraint.kind() { OperandKind::Use => possible_src_operand_idxs.push(operand_idx), OperandKind::Def => possible_dest_operand_idxs.push(operand_idx), @@ -129,7 +129,7 @@ impl FnBuilder<'_, '_, '_> { // 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::, Error>>()?; + .collect::, Error>>()?; // dest can't have duplicates, so shuffle let len = possible_dest_operand_idxs.len(); for i in 0..len { @@ -184,20 +184,12 @@ impl FnBuilder<'_, '_, '_> { } fn run(&mut self) -> Result<(), Error> { let block_count = self.u.int_in_range(1..=10u16)?; - for block_idx in 0..block_count as usize { - let block_idx = BlockIdx::new(block_idx); + for block_idx in RangeIter::::from_usize_range(0..block_count as usize) { let mut params = Vec::new(); if block_idx != BlockIdx::ENTRY_BLOCK { - for param_idx in 0..self.u.int_in_range(0..=10)? { + for _param_idx in 0..self.u.int_in_range(0..=10)? { let ty = self.u.arbitrary()?; - params.push(Self::new_ssa_val( - &mut self.func.ssa_vals, - ty, - SSAValDef::BlockParam { - block: block_idx, - param_idx, - }, - )); + params.push(Self::new_ssa_val(&mut self.func.ssa_vals, ty)); } } let end = InstIdx::new(self.func.insts.len()); @@ -216,11 +208,7 @@ impl FnBuilder<'_, '_, '_> { let kind = self.u.arbitrary()?; let ssa_val = if let OperandKind::Def = kind { let ty = self.u.arbitrary()?; - let def = SSAValDef::Operand { - inst: InstIdx::new(self.func.insts.len()), - operand_idx: operands.len(), - }; - Self::new_ssa_val(&mut self.func.ssa_vals, ty, def) + Self::new_ssa_val(&mut self.func.ssa_vals, ty) } else { SSAValIdx::new(!0) }; @@ -254,8 +242,7 @@ impl FnBuilder<'_, '_, '_> { self.new_inst_in_last_block(inst_kind, operands, clobbers); } } - for block_idx in 0..self.func.blocks.len() { - let block_idx = BlockIdx::new(block_idx); + for block_idx in self.func.blocks.keys() { let term_idx = self .func .try_get_block_term_inst_idx(block_idx) @@ -271,8 +258,7 @@ impl FnBuilder<'_, '_, '_> { self.func.blocks[succ].preds.insert(block_idx); } } - for block_idx in 0..self.func.blocks.len() { - let block_idx = BlockIdx::new(block_idx); + for block_idx in self.func.blocks.keys() { let term_idx = self .func .try_get_block_term_inst_idx(block_idx) @@ -304,19 +290,17 @@ impl FnBuilder<'_, '_, '_> { }); } let dominators = dominators::simple_fast(&self.func, BlockIdx::ENTRY_BLOCK); - for block_idx in 0..self.func.blocks.len() { - let block_idx = BlockIdx::new(block_idx); + for block_idx in self.func.blocks.keys() { self.func.blocks[block_idx].immediate_dominator = dominators.immediate_dominator(block_idx); } // must have filled dominators first since available_ssa_vals_before_start() needs them - for block_idx in 0..self.func.blocks.len() { - let block_idx = BlockIdx::new(block_idx); + for block_idx in self.func.blocks.keys() { let mut available_ssa_vals = self.available_ssa_vals_before_start(block_idx); available_ssa_vals.extend(&self.func.ssa_vals, &self.func.blocks[block_idx].params); for inst_idx in self.func.blocks[block_idx].insts { let inst = &mut self.func.insts[inst_idx]; - for (operand_idx, operand) in inst.operands.iter_mut().enumerate() { + for (_operand_idx, operand) in inst.operands.entries_mut() { if operand.kind_and_constraint.kind() != OperandKind::Use { continue; } @@ -330,22 +314,12 @@ impl FnBuilder<'_, '_, '_> { ssa_val: Self::new_ssa_val( &mut self.func.ssa_vals, self.u.arbitrary()?, - SSAValDef::Operand { - inst: inst_idx, - operand_idx, - }, ), stage: self.u.arbitrary()?, }; } else { operand.ssa_val = *self.u.choose(&available_ssa_vals.all)?; } - self.func.ssa_vals[operand.ssa_val] - .operand_uses - .insert(OperandUse { - inst: inst_idx, - operand_idx, - }); } available_ssa_vals.extend( &self.func.ssa_vals, @@ -360,27 +334,15 @@ impl FnBuilder<'_, '_, '_> { InstKind::BlockTerm(block_term_inst_kind) => { for (&succ_idx, params) in &mut block_term_inst_kind.succs_and_params { let succ = &self.func.blocks[succ_idx]; - for (param_idx, &succ_param) in succ.params.iter().enumerate() { + for (_param_idx, &succ_param) in succ.params.entries() { let succ_param_ty = self.func.ssa_vals[succ_param].ty; let choices = available_ssa_vals.per_ty(succ_param_ty); let ssa_val_idx; if choices.is_empty() { // no available ssa vals with correct type, fix that by appending def operand with that type - ssa_val_idx = Self::new_ssa_val( - &mut self.func.ssa_vals, - succ_param_ty, - SSAValDef::Operand { - inst: inst_idx, - operand_idx: inst.operands.len(), - }, - ); + ssa_val_idx = + Self::new_ssa_val(&mut self.func.ssa_vals, succ_param_ty); available_ssa_vals.extend(&self.func.ssa_vals, [ssa_val_idx]); - self.func.ssa_vals[ssa_val_idx].operand_uses.insert( - OperandUse { - inst: inst_idx, - operand_idx: inst.operands.len(), - }, - ); inst.operands.push(Operand { kind_and_constraint: KindAndConstraint::Constraint { kind: OperandKind::Def, @@ -393,23 +355,15 @@ impl FnBuilder<'_, '_, '_> { ssa_val_idx = *self.u.choose(choices)? }; params.push(ssa_val_idx); - self.func.ssa_vals[ssa_val_idx] - .branch_succ_param_uses - .insert(BranchSuccParamUse { - branch_inst: inst_idx, - succ: succ_idx, - param_idx, - }); } } } } } } - for (inst_idx, inst) in self.func.insts.iter_mut().enumerate() { - let inst_idx = InstIdx::new(inst_idx); - let mut reusable_operand_idxs: HashMap> = HashMap::new(); - for (operand_idx, operand) in inst.operands.iter().enumerate() { + for (inst_idx, inst) in self.func.insts.entries_mut() { + let mut reusable_operand_idxs: HashMap> = HashMap::new(); + for (operand_idx, operand) in inst.operands.entries() { if operand.kind_and_constraint.kind() == OperandKind::Use { reusable_operand_idxs .entry(self.func.ssa_vals[operand.ssa_val].ty) @@ -418,21 +372,24 @@ impl FnBuilder<'_, '_, '_> { } } let mut used_locs = EnumMap::::default(); - for operand_idx in 0..inst.operands.len() { + for operand_idx in inst.operands.keys() { 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 reusable_operand_idxs = reusable_operand_idxs + .get(&operand_ty) + .map(Deref::deref) + .unwrap_or_default(); + if !reusable_operand_idxs.is_empty() { + let reuse_operand_idx = *self.u.choose(reusable_operand_idxs)?; + if reuse_operand_idx != operand_idx { + inst.operands[operand_idx].kind_and_constraint = + KindAndConstraint::Reuse { + kind: OperandKindDefOnly, + reuse_operand_idx, + }; + continue; + } } } let operand = &mut inst.operands[operand_idx]; diff --git a/register_allocator/src/index.rs b/register_allocator/src/index.rs index 3c99fb6..a235f4f 100644 --- a/register_allocator/src/index.rs +++ b/register_allocator/src/index.rs @@ -1,11 +1,90 @@ -use serde::{Deserialize, Serialize}; -use std::{fmt, iter::FusedIterator, ops::Range}; +use serde::{de::DeserializeOwned, Deserialize, Serialize}; +use std::{fmt, hash::Hash, iter::FusedIterator, ops::Range}; pub trait DisplayOptionIdx { type Type: fmt::Display; fn display_option_idx(self) -> Self::Type; } +pub trait IndexTy: Copy + fmt::Debug + Ord + Hash + Serialize + DeserializeOwned { + fn new(value: usize) -> Self; + fn get(self) -> usize; + fn next(self) -> Self { + Self::new(self.get() + 1) + } + fn prev(self) -> Self { + Self::new(self.get() - 1) + } +} + +#[derive(Debug, Clone)] +pub struct RangeIter(pub Range); + +impl RangeIter { + pub fn as_usize_range(&self) -> Range { + self.0.start.get()..self.0.end.get() + } + pub fn from_usize_range(range: Range) -> Self { + Self(T::new(range.start)..T::new(range.end)) + } + pub fn with_self_as_usize_range) -> R>(&mut self, f: F) -> R { + let mut range = self.as_usize_range(); + let retval = f(&mut range); + *self = Self::from_usize_range(range); + retval + } +} + +impl Iterator for RangeIter { + type Item = T; + + fn next(&mut self) -> Option { + self.with_self_as_usize_range(|r| r.next().map(T::new)) + } + + fn size_hint(&self) -> (usize, Option) { + self.as_usize_range().size_hint() + } + + fn nth(&mut self, n: usize) -> Option { + self.with_self_as_usize_range(|r| r.nth(n).map(T::new)) + } + + fn fold(self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.as_usize_range() + .fold(init, move |a, v| f(a, T::new(v))) + } +} + +impl FusedIterator for RangeIter {} + +impl ExactSizeIterator for RangeIter { + fn len(&self) -> usize { + self.as_usize_range().len() + } +} + +impl DoubleEndedIterator for RangeIter { + fn next_back(&mut self) -> Option { + self.with_self_as_usize_range(|r| r.next_back().map(T::new)) + } + + fn nth_back(&mut self, n: usize) -> Option { + self.with_self_as_usize_range(|r| r.nth_back(n).map(T::new)) + } + + fn rfold(self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + self.as_usize_range() + .rfold(init, move |a, v| f(a, T::new(v))) + } +} + macro_rules! define_index { ($name:ident) => { #[derive( @@ -16,6 +95,15 @@ macro_rules! define_index { value: usize, } + impl IndexTy for $name { + fn new(value: usize) -> Self { + Self { value } + } + fn get(self) -> usize { + self.value + } + } + impl $name { pub const fn new(value: usize) -> Self { Self { value } @@ -67,6 +155,8 @@ macro_rules! define_index { define_index!(SSAValIdx); define_index!(InstIdx); define_index!(BlockIdx); +define_index!(BlockParamIdx); +define_index!(OperandIdx); impl fmt::Display for SSAValIdx { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { @@ -86,6 +176,18 @@ impl fmt::Display for BlockIdx { } } +impl fmt::Display for BlockParamIdx { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "bparam{}", self.get()) + } +} + +impl fmt::Display for OperandIdx { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "operand{}", self.get()) + } +} + impl BlockIdx { pub const ENTRY_BLOCK: BlockIdx = BlockIdx::new(0); } -- 2.30.2