From a5ea39553260aa3173fa136c483af00aa69314f7 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Wed, 15 Feb 2023 19:59:39 -0800 Subject: [PATCH] wip --- register_allocator/src/fuzzing.rs | 7 +-- register_allocator/src/live_range.rs | 1 + register_allocator/src/loc.rs | 42 ++++++++++++- register_allocator/src/state.rs | 88 +++++++++++++++++++++++++++- 4 files changed, 131 insertions(+), 7 deletions(-) diff --git a/register_allocator/src/fuzzing.rs b/register_allocator/src/fuzzing.rs index 25748ad..6ba5ace 100644 --- a/register_allocator/src/fuzzing.rs +++ b/register_allocator/src/fuzzing.rs @@ -1,11 +1,10 @@ #![cfg(feature = "fuzzing")] use crate::{ function::{ - Block, BlockTermInstKind, Constraint, CopyInstKind, Entries, EntriesMut, FnFields, Inst, - InstKind, InstStage, KindAndConstraint, Operand, OperandKind, OperandKindDefOnly, SSAVal, - SSAValDef, + Block, BlockTermInstKind, Constraint, CopyInstKind, FnFields, Inst, InstKind, InstStage, + KindAndConstraint, Operand, OperandKind, OperandKindDefOnly, SSAVal, SSAValDef, }, - index::{BlockIdx, InstIdx, InstRange, OperandIdx, RangeIter, SSAValIdx}, + index::{BlockIdx, Entries, EntriesMut, InstIdx, InstRange, OperandIdx, RangeIter, SSAValIdx}, interned::{GlobalState, Intern}, loc::Ty, loc_set::LocSet, diff --git a/register_allocator/src/live_range.rs b/register_allocator/src/live_range.rs index 239120f..9cf9a71 100644 --- a/register_allocator/src/live_range.rs +++ b/register_allocator/src/live_range.rs @@ -171,6 +171,7 @@ fn _check_prog_range_is_not_hashable() { pub struct LiveRange { pub range: ProgRange, pub ssa_val: SSAValIdx, + pub allocation: Option, } pub struct LiveRangeBundle { diff --git a/register_allocator/src/loc.rs b/register_allocator/src/loc.rs index 08e81fc..6798b44 100644 --- a/register_allocator/src/loc.rs +++ b/register_allocator/src/loc.rs @@ -2,7 +2,7 @@ use crate::error::{Error, Result}; use arbitrary::{size_hint, Arbitrary}; use enum_map::Enum; use serde::{Deserialize, Serialize}; -use std::num::NonZeroU32; +use std::{iter::FusedIterator, num::NonZeroU32}; #[derive( Serialize, @@ -181,6 +181,26 @@ impl Ty { } } +validated_fields! { + #[fields_ty = SubLocFields] + #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)] + pub struct SubLoc { + pub kind: LocKind, + pub start: u32, + } +} + +impl SubLoc { + pub const fn new(fields: SubLocFields) -> Result { + const_try!(Loc::new(LocFields { + reg_len: nzu32_lit!(1), + kind: fields.kind, + start: fields.start + })); + Ok(SubLoc(fields)) + } +} + validated_fields! { #[fields_ty = LocFields] #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)] @@ -230,9 +250,18 @@ impl LocFields { pub const fn stop(self) -> NonZeroU32 { const_unwrap_opt!(self.reg_len.checked_add(self.start), "overflow") } + pub const fn first_subloc(self) -> SubLocFields { + SubLocFields { + kind: self.kind, + start: self.start, + } + } } impl Loc { + pub const fn first_subloc(self) -> SubLoc { + SubLoc(self.get().first_subloc()) + } pub fn arbitrary_with_ty( ty: Ty, u: &mut arbitrary::Unstructured<'_>, @@ -358,6 +387,17 @@ impl Loc { reg_len: nzu32_lit!(1), }), ]; + pub fn sub_locs( + self, + ) -> impl Iterator + FusedIterator + ExactSizeIterator + DoubleEndedIterator + { + let LocFields { + reg_len: _, + kind, + start, + } = *self; + (start..self.stop().get()).map(move |start| SubLoc(SubLocFields { kind, start })) + } } #[cfg(test)] diff --git a/register_allocator/src/state.rs b/register_allocator/src/state.rs index 103233a..684f262 100644 --- a/register_allocator/src/state.rs +++ b/register_allocator/src/state.rs @@ -1,8 +1,92 @@ -use crate::{function::Function, interned::GlobalState, live_range::LiveRange}; +use crate::{ + function::Function, + index::LiveRangeIdx, + interned::GlobalState, + live_range::{LiveRange, ProgRange}, + loc::{Loc, SubLoc}, +}; +use hashbrown::HashMap; +use std::{collections::BTreeMap, rc::Rc}; #[derive(Debug)] pub struct AllocatorState<'a> { - global_state: &'a GlobalState, + global_state: &'a Rc, func: &'a Function, live_ranges: Vec, + allocations: HashMap>, +} + +impl<'a> AllocatorState<'a> { + pub fn new(global_state: &'a Rc, func: &'a Function) -> Self { + Self { + global_state, + func, + live_ranges: vec![], + allocations: HashMap::new(), + } + } + pub fn global_state(&self) -> &'a Rc { + self.global_state + } + pub fn func(&self) -> &'a Function { + self.func + } + pub fn live_ranges(&self) -> &[LiveRange] { + &self.live_ranges + } + pub fn allocations(&self, sub_loc: SubLoc) -> &BTreeMap { + const EMPTY: &'static BTreeMap = &BTreeMap::new(); + self.allocations.get(&sub_loc).unwrap_or(EMPTY) + } + pub fn remove_allocations_for(&mut self, live_range_idx: LiveRangeIdx) -> Option { + let live_range = &mut self.live_ranges[live_range_idx]; + let old_allocation = live_range.allocation.take(); + if let Some(old_allocation) = old_allocation { + for sub_loc in old_allocation.sub_locs() { + if let Some(allocations) = self.allocations.get_mut(&sub_loc) { + allocations.remove(&live_range.range); + } + } + } + old_allocation + } + pub fn add_allocations_for( + &mut self, + live_range_idx: LiveRangeIdx, + new_allocation: Option, + ) { + let live_range = &mut self.live_ranges[live_range_idx]; + assert!(live_range.allocation.is_none()); + live_range.allocation = new_allocation; + if let Some(new_allocation) = new_allocation { + for sub_loc in new_allocation.sub_locs() { + self.allocations + .entry(sub_loc) + .or_default() + .insert(live_range.range, live_range_idx); + } + } + } + pub fn replace_allocation( + &mut self, + live_range_idx: LiveRangeIdx, + new_allocation: Option, + ) -> Option { + let old_allocation = self.remove_allocations_for(live_range_idx); + self.add_allocations_for(live_range_idx, new_allocation); + old_allocation + } + pub fn add_live_range(&mut self, mut live_range: LiveRange) -> LiveRangeIdx { + let allocation = live_range.allocation.take(); + let live_range_idx = LiveRangeIdx::new(self.live_ranges.len()); + self.live_ranges.push(live_range); + self.add_allocations_for(live_range_idx, allocation); + live_range_idx + } + pub fn set_live_range(&mut self, live_range_idx: LiveRangeIdx, mut new_live_range: LiveRange) { + let allocation = new_live_range.allocation.take(); + self.remove_allocations_for(live_range_idx); + self.live_ranges[live_range_idx] = new_live_range; + self.add_allocations_for(live_range_idx, allocation); + } } -- 2.30.2