register_allocator/src/loc_set.rs

   1 use crate::{
   2     error::{Error, Result},
   3     interned::{GlobalState, Intern, InternTarget, Interned},
   4     loc::{Loc, LocFields, LocKind, Ty},
   5 };
   6 use enum_map::{enum_map, EnumMap};
   7 use num_bigint::BigUint;
   8 use num_traits::Zero;
   9 use once_cell::race::OnceBox;
  10 use serde::{Deserialize, Serialize};
  11 use std::{
  12     borrow::Borrow,
  13     cell::Cell,
  14     collections::{
  15         btree_map::{self, Entry},
  16         BTreeMap,
  17     },
  18     fmt,
  19     hash::Hash,
  20     iter::FusedIterator,
  21     mem,
  22     num::NonZeroU32,
  23     ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Range, Sub, SubAssign},
  24 };
  25
  26 #[inline]
  27 fn zero_biguint<'a>() -> &'a BigUint {
  28     static ZERO: OnceBox<BigUint> = OnceBox::new();
  29     ZERO.get_or_init(
  30         #[cold]
  31         || BigUint::zero().into(),
  32     )
  33 }
  34
  35 #[derive(Deserialize)]
  36 struct LocSetSerialized {
  37     starts_map: BTreeMap<NonZeroU32, EnumMap<LocKind, BigUint>>,
  38 }
  39
  40 impl TryFrom<LocSetSerialized> for LocSet {
  41     type Error = Error;
  42
  43     fn try_from(value: LocSetSerialized) -> Result<Self, Self::Error> {
  44         Self::from_starts_map(value.starts_map)
  45     }
  46 }
  47
  48 #[derive(Clone, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
  49 #[serde(try_from = "LocSetSerialized")]
  50 pub struct LocSet {
  51     starts_map: BTreeMap<NonZeroU32, EnumMap<LocKind, BigUint>>,
  52 }
  53
  54 impl<'a> arbitrary::Arbitrary<'a> for LocSet {
  55     fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
  56         u.arbitrary_iter()?.collect()
  57     }
  58 }
  59
  60 /// computes same value as `a & !b`, but more efficiently
  61 fn and_not<A: Borrow<BigUint>, B>(a: A, b: B) -> BigUint
  62 where
  63     BigUint: for<'a> BitXor<A, Output = BigUint>,
  64     B: for<'a> BitAnd<&'a BigUint, Output = BigUint>,
  65 {
  66     // use logical equivalent that avoids needing to use BigInt
  67     (b & a.borrow()) ^ a
  68 }
  69
  70 impl From<Loc> for LocSet {
  71     fn from(value: Loc) -> Self {
  72         Self::from_iter([value])
  73     }
  74 }
  75
  76 impl LocSet {
  77     pub fn arbitrary_with_ty(
  78         ty: Ty,
  79         u: &mut arbitrary::Unstructured<'_>,
  80     ) -> arbitrary::Result<Self> {
  81         let kinds = ty.base_ty.loc_kinds();
  82         type Mask = u128;
  83         let kinds: Vec<_> = if kinds.len() > Mask::BITS as usize {
  84             let chosen_kinds = kinds
  85                 .iter()
  86                 .zip(u.arbitrary_iter::<bool>()?)
  87                 .filter(|(_, cond)| !matches!(cond, Ok(false)))
  88                 .map(|(&kind, cond)| {
  89                     cond?;
  90                     Ok(kind)
  91                 })
  92                 .collect::<arbitrary::Result<Vec<_>>>()?;
  93             if chosen_kinds.is_empty() {
  94                 vec![*u.choose(kinds)?]
  95             } else {
  96                 chosen_kinds
  97             }
  98         } else {
  99             let max_mask = Mask::wrapping_shl(1, kinds.len() as u32).wrapping_sub(1);
 100             let mask = u.int_in_range(1..=max_mask)?; // non-zero
 101             kinds
 102                 .iter()
 103                 .enumerate()
 104                 .filter_map(|(idx, &kind)| {
 105                     if mask & (1 << idx) != 0 {
 106                         Some(kind)
 107                     } else {
 108                         None
 109                     }
 110                 })
 111                 .collect()
 112         };
 113         let mut starts = EnumMap::<LocKind, BigUint>::default();
 114         let mut all_zero = true;
 115         for kind in kinds {
 116             let bit_count = Loc::max_start(kind, ty.reg_len)? + 1;
 117             let byte_count = (bit_count + u8::BITS - 1) / u8::BITS;
 118             let bytes = u.bytes(byte_count as usize)?;
 119             starts[kind] = BigUint::from_bytes_le(bytes);
 120             starts[kind] &= (BigUint::from(1u8) << bit_count) - 1u8;
 121             all_zero &= starts[kind].is_zero();
 122         }
 123         if all_zero {
 124             Ok(Loc::arbitrary_with_ty(ty, u)?.into())
 125         } else {
 126             Ok(Self::from_starts_map_iter_unchecked([(ty.reg_len, starts)]))
 127         }
 128     }
 129     pub fn starts(&self, reg_len: NonZeroU32, kind: LocKind) -> &BigUint {
 130         self.starts_map
 131             .get(&reg_len)
 132             .map(|v| &v[kind])
 133             .unwrap_or_else(zero_biguint)
 134     }
 135     pub fn stops(&self, reg_len: NonZeroU32, kind: LocKind) -> BigUint {
 136         self.starts(reg_len, kind) << reg_len.get()
 137     }
 138     pub fn starts_map(&self) -> &BTreeMap<NonZeroU32, EnumMap<LocKind, BigUint>> {
 139         &self.starts_map
 140     }
 141     pub const fn new() -> Self {
 142         Self {
 143             starts_map: BTreeMap::new(),
 144         }
 145     }
 146     /// filters out empty entries, but doesn't do any other checks
 147     fn from_starts_map_iter_unchecked(
 148         starts_map: impl IntoIterator<Item = (NonZeroU32, EnumMap<LocKind, BigUint>)>,
 149     ) -> Self {
 150         Self {
 151             starts_map: starts_map
 152                 .into_iter()
 153                 .filter(|(_, starts)| !starts.iter().all(|(_, starts)| starts.is_zero()))
 154                 .collect(),
 155         }
 156     }
 157     fn for_each_reg_len_filtering_out_empty_entries(
 158         &mut self,
 159         mut f: impl FnMut(NonZeroU32, &mut EnumMap<LocKind, BigUint>),
 160     ) {
 161         self.starts_map.retain(|&reg_len, starts| {
 162             f(reg_len, starts);
 163             !Self::is_entry_empty(starts)
 164         });
 165     }
 166     /// helper for binary operations that keeps Locs not present in rhs
 167     fn bin_op_keep_helper(
 168         &mut self,
 169         rhs: &Self,
 170         mut f: impl FnMut(NonZeroU32, &mut EnumMap<LocKind, BigUint>, &EnumMap<LocKind, BigUint>),
 171     ) {
 172         rhs.starts_map.iter().for_each(|(&reg_len, rhs_starts)| {
 173             match self.starts_map.entry(reg_len) {
 174                 Entry::Vacant(entry) => {
 175                     let mut lhs_starts = EnumMap::default();
 176                     f(reg_len, &mut lhs_starts, rhs_starts);
 177                     if !Self::is_entry_empty(&lhs_starts) {
 178                         entry.insert(lhs_starts);
 179                     }
 180                 }
 181                 Entry::Occupied(mut entry) => {
 182                     f(reg_len, entry.get_mut(), rhs_starts);
 183                     if Self::is_entry_empty(entry.get()) {
 184                         entry.remove();
 185                     }
 186                 }
 187             }
 188         });
 189     }
 190     fn is_entry_empty(starts: &EnumMap<LocKind, BigUint>) -> bool {
 191         starts.iter().all(|(_, starts)| starts.is_zero())
 192     }
 193     pub fn from_starts_map(
 194         mut starts_map: BTreeMap<NonZeroU32, EnumMap<LocKind, BigUint>>,
 195     ) -> Result<Self> {
 196         let mut error = Ok(());
 197         starts_map.retain(|&reg_len, starts| {
 198             if error.is_err() {
 199                 return false;
 200             }
 201             let mut any_locs = false;
 202             for (kind, starts) in starts {
 203                 if !starts.is_zero() {
 204                     any_locs = true;
 205                     error = (|| {
 206                         // bits() is one past max bit set, so use >= rather than >
 207                         if starts.bits() >= Loc::max_start(kind, reg_len)? as u64 {
 208                             return Err(Error::StartNotInValidRange);
 209                         }
 210                         Ok(())
 211                     })();
 212                     if error.is_err() {
 213                         return false;
 214                     }
 215                 }
 216             }
 217             any_locs
 218         });
 219         Ok(Self { starts_map })
 220     }
 221     pub fn clear(&mut self) {
 222         self.starts_map.clear();
 223     }
 224     pub fn contains_exact(&self, value: Loc) -> bool {
 225         self.starts(value.reg_len, value.kind).bit(value.start as _)
 226     }
 227     pub fn insert(&mut self, value: Loc) -> bool {
 228         let starts = match self.starts_map.entry(value.reg_len) {
 229             Entry::Occupied(entry) => entry.into_mut(),
 230             Entry::Vacant(entry) => {
 231                 entry.insert(Default::default())[value.kind].set_bit(value.start as u64, true);
 232                 return true;
 233             }
 234         };
 235         let starts = &mut starts[value.kind];
 236         let retval = !starts.bit(value.start as u64);
 237         starts.set_bit(value.start as u64, true);
 238         retval
 239     }
 240     pub fn remove(&mut self, value: Loc) -> bool {
 241         let Entry::Occupied(mut entry) = self.starts_map.entry(value.reg_len) else {
 242             return false;
 243         };
 244         let starts = entry.get_mut();
 245         if starts[value.kind].bit(value.start as u64) {
 246             starts[value.kind].set_bit(value.start as u64, false);
 247             if starts.values().all(BigUint::is_zero) {
 248                 entry.remove();
 249             }
 250             true
 251         } else {
 252             false
 253         }
 254     }
 255     pub fn is_empty(&self) -> bool {
 256         self.starts_map.is_empty()
 257     }
 258     pub fn iter(&self) -> Iter<'_> {
 259         Iter {
 260             internals: IterInternals::new(self.starts_map.iter()),
 261         }
 262     }
 263     pub fn len(&self) -> usize {
 264         let retval: u64 = self
 265             .starts_map
 266             .values()
 267             .map(|starts| starts.values().map(BigUint::count_ones).sum::<u64>())
 268             .sum();
 269         retval as usize
 270     }
 271     /// computes `self = &other - &self`
 272     pub fn sub_reverse_assign(&mut self, other: impl Borrow<Self>) {
 273         // TODO: make more efficient
 274         let other: &Self = other.borrow();
 275         *self = other - &*self;
 276     }
 277 }
 278
 279 #[derive(Clone, Debug)]
 280 struct IterInternalsRest<StartsMapValueIter, Starts>
 281 where
 282     StartsMapValueIter: Iterator<Item = (LocKind, Starts)>,
 283     Starts: Borrow<BigUint>,
 284 {
 285     reg_len: NonZeroU32,
 286     starts_map_value_iter: StartsMapValueIter,
 287     kind: LocKind,
 288     starts: Starts,
 289     start_range: Range<u32>,
 290 }
 291
 292 impl<StartsMapValueIter, Starts> IterInternalsRest<StartsMapValueIter, Starts>
 293 where
 294     StartsMapValueIter: Iterator<Item = (LocKind, Starts)>,
 295     Starts: Borrow<BigUint>,
 296 {
 297     fn new(reg_len: NonZeroU32, mut starts_map_value_iter: StartsMapValueIter) -> Option<Self> {
 298         loop {
 299             let (kind, starts) = starts_map_value_iter.next()?;
 300             let starts_ref: &BigUint = starts.borrow();
 301             let Some(start) = starts_ref.trailing_zeros() else {
 302                 continue;
 303             };
 304             let start = start.try_into().expect("checked by LocSet constructors");
 305             let end = starts_ref
 306                 .bits()
 307                 .try_into()
 308                 .expect("checked by LocSet constructors");
 309             return Some(Self {
 310                 reg_len,
 311                 starts_map_value_iter,
 312                 kind,
 313                 starts,
 314                 start_range: start..end,
 315             });
 316         }
 317     }
 318     fn next(this: &mut Option<Self>) -> Option<Loc> {
 319         while let Some(Self {
 320             reg_len,
 321             starts_map_value_iter: _,
 322             kind,
 323             ref starts,
 324             ref mut start_range,
 325         }) = *this
 326         {
 327             let Some(start) = start_range.next() else {
 328                 *this = Self::new(reg_len, this.take().expect("known to be Some").starts_map_value_iter);
 329                 continue;
 330             };
 331             if starts.borrow().bit(start as u64) {
 332                 return Some(
 333                     Loc::new(LocFields {
 334                         kind,
 335                         start,
 336                         reg_len,
 337                     })
 338                     .expect("known to be valid"),
 339                 );
 340             }
 341         }
 342         None
 343     }
 344 }
 345
 346 #[derive(Clone, Debug)]
 347 struct IterInternals<StartsMapIter, RegLen, StartsMapValue, StartsMapValueIter, Starts>
 348 where
 349     StartsMapIter: Iterator<Item = (RegLen, StartsMapValue)>,
 350     RegLen: Borrow<NonZeroU32>,
 351     StartsMapValue: IntoIterator<IntoIter = StartsMapValueIter>,
 352     StartsMapValueIter: Iterator<Item = (LocKind, Starts)>,
 353     Starts: Borrow<BigUint>,
 354 {
 355     starts_map_iter: StartsMapIter,
 356     rest: Option<IterInternalsRest<StartsMapValueIter, Starts>>,
 357 }
 358
 359 impl<StartsMapIter, RegLen, StartsMapValue, StartsMapValueIter, Starts>
 360     IterInternals<StartsMapIter, RegLen, StartsMapValue, StartsMapValueIter, Starts>
 361 where
 362     StartsMapIter: Iterator<Item = (RegLen, StartsMapValue)>,
 363     RegLen: Borrow<NonZeroU32>,
 364     StartsMapValue: IntoIterator<IntoIter = StartsMapValueIter>,
 365     StartsMapValueIter: Iterator<Item = (LocKind, Starts)>,
 366     Starts: Borrow<BigUint>,
 367 {
 368     fn new(starts_map_iter: StartsMapIter) -> Self {
 369         Self {
 370             starts_map_iter,
 371             rest: None,
 372         }
 373     }
 374     fn next(&mut self) -> Option<Loc> {
 375         loop {
 376             while self.rest.is_none() {
 377                 let (reg_len, starts_map_value) = self.starts_map_iter.next()?;
 378                 self.rest = IterInternalsRest::new(*reg_len.borrow(), starts_map_value.into_iter());
 379             }
 380             if let Some(loc) = IterInternalsRest::next(&mut self.rest) {
 381                 return Some(loc);
 382             }
 383         }
 384     }
 385 }
 386
 387 #[derive(Clone, Debug)]
 388 pub struct Iter<'a> {
 389     internals: IterInternals<
 390         btree_map::Iter<'a, NonZeroU32, EnumMap<LocKind, BigUint>>,
 391         &'a NonZeroU32,
 392         &'a EnumMap<LocKind, BigUint>,
 393         enum_map::Iter<'a, LocKind, BigUint>,
 394         &'a BigUint,
 395     >,
 396 }
 397
 398 impl Iterator for Iter<'_> {
 399     type Item = Loc;
 400
 401     fn next(&mut self) -> Option<Self::Item> {
 402         self.internals.next()
 403     }
 404 }
 405
 406 impl FusedIterator for Iter<'_> {}
 407
 408 pub struct IntoIter {
 409     internals: IterInternals<
 410         btree_map::IntoIter<NonZeroU32, EnumMap<LocKind, BigUint>>,
 411         NonZeroU32,
 412         EnumMap<LocKind, BigUint>,
 413         enum_map::IntoIter<LocKind, BigUint>,
 414         BigUint,
 415     >,
 416 }
 417
 418 impl Iterator for IntoIter {
 419     type Item = Loc;
 420
 421     fn next(&mut self) -> Option<Self::Item> {
 422         self.internals.next()
 423     }
 424 }
 425
 426 impl FusedIterator for IntoIter {}
 427
 428 impl IntoIterator for LocSet {
 429     type Item = Loc;
 430     type IntoIter = IntoIter;
 431
 432     fn into_iter(self) -> Self::IntoIter {
 433         IntoIter {
 434             internals: IterInternals::new(self.starts_map.into_iter()),
 435         }
 436     }
 437 }
 438
 439 impl<'a> IntoIterator for &'a LocSet {
 440     type Item = Loc;
 441     type IntoIter = Iter<'a>;
 442
 443     fn into_iter(self) -> Self::IntoIter {
 444         self.iter()
 445     }
 446 }
 447
 448 impl Extend<Loc> for LocSet {
 449     fn extend<T: IntoIterator<Item = Loc>>(&mut self, iter: T) {
 450         iter.into_iter().for_each(|item| {
 451             self.insert(item);
 452         });
 453     }
 454 }
 455
 456 impl FromIterator<Loc> for LocSet {
 457     fn from_iter<T: IntoIterator<Item = Loc>>(iter: T) -> Self {
 458         let mut retval = LocSet::new();
 459         retval.extend(iter);
 460         retval
 461     }
 462 }
 463
 464 struct HexBigUint<'a>(&'a BigUint);
 465
 466 impl fmt::Debug for HexBigUint<'_> {
 467     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 468         write!(f, "{:#x}", self.0)
 469     }
 470 }
 471
 472 struct LocSetStarts<'a>(&'a EnumMap<LocKind, BigUint>);
 473
 474 impl fmt::Debug for LocSetStarts<'_> {
 475     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 476         f.debug_map()
 477             .entries(self.0.iter().map(|(k, v)| (k, HexBigUint(v))))
 478             .finish()
 479     }
 480 }
 481
 482 struct LocSetStartsMap<'a>(&'a BTreeMap<NonZeroU32, EnumMap<LocKind, BigUint>>);
 483
 484 impl fmt::Debug for LocSetStartsMap<'_> {
 485     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 486         f.debug_map()
 487             .entries(self.0.iter().map(|(k, v)| (k, LocSetStarts(v))))
 488             .finish()
 489     }
 490 }
 491
 492 impl fmt::Debug for LocSet {
 493     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 494         f.debug_struct("LocSet")
 495             .field("starts_map", &LocSetStartsMap(&self.starts_map))
 496             .finish()
 497     }
 498 }
 499
 500 macro_rules! forward_bin_op {
 501     (
 502         $bin_op:ident::$bin_op_fn:ident(),
 503         $bin_assign_op:ident::$bin_assign_op_fn:ident(),
 504         $bin_assign_rev_op_fn:ident(),
 505     ) => {
 506         impl $bin_assign_op<LocSet> for LocSet {
 507             fn $bin_assign_op_fn(&mut self, rhs: LocSet) {
 508                 self.$bin_assign_op_fn(&rhs);
 509             }
 510         }
 511
 512         impl $bin_op<&'_ LocSet> for LocSet {
 513             type Output = LocSet;
 514
 515             fn $bin_op_fn(mut self, rhs: &'_ LocSet) -> Self::Output {
 516                 self.$bin_assign_op_fn(rhs);
 517                 self
 518             }
 519         }
 520
 521         impl $bin_op<LocSet> for LocSet {
 522             type Output = LocSet;
 523
 524             fn $bin_op_fn(mut self, rhs: LocSet) -> Self::Output {
 525                 self.$bin_assign_op_fn(rhs);
 526                 self
 527             }
 528         }
 529
 530         impl $bin_op<LocSet> for &'_ LocSet {
 531             type Output = LocSet;
 532
 533             fn $bin_op_fn(self, mut rhs: LocSet) -> Self::Output {
 534                 rhs.$bin_assign_rev_op_fn(self);
 535                 rhs
 536             }
 537         }
 538
 539         const _: fn() = {
 540             fn _check<T>()
 541             where
 542                 for<'a> T: $bin_op<T> + $bin_op<&'a T> + $bin_assign_op<T> + $bin_assign_op<&'a T>,
 543                 for<'a, 'b> &'a T: $bin_op<T> + $bin_op<&'b T>,
 544             {
 545             }
 546             _check::<LocSet>
 547         };
 548     };
 549 }
 550
 551 impl BitAnd<&'_ LocSet> for &'_ LocSet {
 552     type Output = LocSet;
 553
 554     fn bitand(self, rhs: &'_ LocSet) -> Self::Output {
 555         LocSet::from_starts_map_iter_unchecked(self.starts_map.iter().map(|(&reg_len, starts)| {
 556             (
 557                 reg_len,
 558                 enum_map! {kind => (&starts[kind]).bitand(rhs.starts(reg_len, kind))},
 559             )
 560         }))
 561     }
 562 }
 563
 564 impl BitAndAssign<&'_ LocSet> for LocSet {
 565     fn bitand_assign(&mut self, rhs: &'_ LocSet) {
 566         self.for_each_reg_len_filtering_out_empty_entries(|reg_len, starts| {
 567             for (kind, starts) in starts {
 568                 starts.bitand_assign(rhs.starts(reg_len, kind));
 569             }
 570         });
 571     }
 572 }
 573
 574 /// helper for binary operations that keeps Locs not present in rhs
 575 macro_rules! impl_bin_op_keep {
 576     (
 577         $bin_op:ident::$bin_op_fn:ident(),
 578         $bin_assign_op:ident::$bin_assign_op_fn:ident(),
 579     ) => {
 580         impl $bin_op<&'_ LocSet> for &'_ LocSet {
 581             type Output = LocSet;
 582
 583             fn $bin_op_fn(self, rhs: &'_ LocSet) -> Self::Output {
 584                 let mut retval: LocSet = self.clone();
 585                 retval.$bin_assign_op_fn(rhs);
 586                 retval
 587             }
 588         }
 589
 590         impl $bin_assign_op<&'_ LocSet> for LocSet {
 591             fn $bin_assign_op_fn(&mut self, rhs: &'_ LocSet) {
 592                 self.bin_op_keep_helper(rhs, |_reg_len, lhs_starts, rhs_starts| {
 593                     for (kind, rhs_starts) in rhs_starts {
 594                         lhs_starts[kind].$bin_assign_op_fn(rhs_starts);
 595                     }
 596                 });
 597             }
 598         }
 599     };
 600 }
 601
 602 forward_bin_op! {
 603     BitAnd::bitand(),
 604     BitAndAssign::bitand_assign(),
 605     bitand_assign(),
 606 }
 607
 608 impl_bin_op_keep! {
 609     BitOr::bitor(),
 610     BitOrAssign::bitor_assign(),
 611 }
 612
 613 forward_bin_op! {
 614     BitOr::bitor(),
 615     BitOrAssign::bitor_assign(),
 616     bitor_assign(),
 617 }
 618
 619 impl_bin_op_keep! {
 620     BitXor::bitxor(),
 621     BitXorAssign::bitxor_assign(),
 622 }
 623
 624 forward_bin_op! {
 625     BitXor::bitxor(),
 626     BitXorAssign::bitxor_assign(),
 627     bitxor_assign(),
 628 }
 629
 630 impl Sub<&'_ LocSet> for &'_ LocSet {
 631     type Output = LocSet;
 632
 633     fn sub(self, rhs: &'_ LocSet) -> Self::Output {
 634         LocSet::from_starts_map_iter_unchecked(self.starts_map.iter().map(|(&reg_len, starts)| {
 635             (
 636                 reg_len,
 637                 enum_map! {kind => and_not(&starts[kind], rhs.starts(reg_len, kind))},
 638             )
 639         }))
 640     }
 641 }
 642
 643 impl SubAssign<&'_ LocSet> for LocSet {
 644     fn sub_assign(&mut self, rhs: &'_ LocSet) {
 645         self.bin_op_keep_helper(rhs, |_reg_len, lhs_starts, rhs_starts| {
 646             for (kind, lhs_starts) in lhs_starts {
 647                 let rhs_starts = &rhs_starts[kind];
 648                 if rhs_starts.is_zero() {
 649                     continue;
 650                 }
 651                 *lhs_starts = and_not(mem::take(lhs_starts), rhs_starts);
 652             }
 653         });
 654     }
 655 }
 656
 657 forward_bin_op! {
 658     Sub::sub(),
 659     SubAssign::sub_assign(),
 660     sub_reverse_assign(),
 661 }
 662
 663 /// the largest number of Locs in `lhs` that a single Loc
 664 /// from `rhs` can conflict with
 665 #[derive(Clone)]
 666 pub struct LocSetMaxConflictsWith<Rhs> {
 667     lhs: Interned<LocSet>,
 668     rhs: Rhs,
 669     // result is not included in equality or hash
 670     result: Cell<Option<u32>>,
 671 }
 672
 673 impl<Rhs: Hash> Hash for LocSetMaxConflictsWith<Rhs> {
 674     fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
 675         self.lhs.hash(state);
 676         self.rhs.hash(state);
 677     }
 678 }
 679
 680 impl<Rhs: Eq> Eq for LocSetMaxConflictsWith<Rhs> {}
 681
 682 impl<Rhs: PartialEq> PartialEq for LocSetMaxConflictsWith<Rhs> {
 683     fn eq(&self, other: &Self) -> bool {
 684         self.lhs == other.lhs && self.rhs == other.rhs
 685     }
 686 }
 687
 688 pub trait LocSetMaxConflictsWithTrait: Clone {
 689     fn intern(
 690         v: LocSetMaxConflictsWith<Self>,
 691         global_state: &GlobalState,
 692     ) -> Interned<LocSetMaxConflictsWith<Self>>;
 693     fn compute_result(lhs: &Interned<LocSet>, rhs: &Self, global_state: &GlobalState) -> u32;
 694     #[cfg(feature = "fuzzing")]
 695     fn reference_compute_result(
 696         lhs: &Interned<LocSet>,
 697         rhs: &Self,
 698         global_state: &GlobalState,
 699     ) -> u32;
 700 }
 701
 702 impl LocSetMaxConflictsWithTrait for Loc {
 703     fn compute_result(lhs: &Interned<LocSet>, rhs: &Self, _global_state: &GlobalState) -> u32 {
 704         // now we do the equivalent of:
 705         // return lhs.iter().map(|loc| rhs.conflicts(loc) as u32).sum()
 706         let mut retval = 0;
 707         for (&lhs_reg_len, lhs_starts) in lhs.starts_map() {
 708             let lhs_starts = &lhs_starts[rhs.kind];
 709             if lhs_starts.is_zero() {
 710                 continue;
 711             }
 712             // now we do the equivalent of:
 713             // retval += sum(rhs.start < lhs_start + lhs_reg_len
 714             //               and lhs_start < rhs.start + rhs.reg_len
 715             //               for lhs_start in lhs_starts)
 716             let lhs_stops = lhs_starts << lhs_reg_len.get();
 717
 718             // find all the bit indexes `i` where `i < rhs.start + 1`
 719             let lt_rhs_start_plus_1 = (BigUint::from(1u32) << (rhs.start + 1)) - 1u32;
 720
 721             // find all the bit indexes `i` where
 722             // `i < rhs.start + rhs.reg_len + lhs_reg_len`
 723             let lt_rhs_start_plus_rhs_reg_len_plus_reg_len =
 724                 (BigUint::from(1u32) << (rhs.start + rhs.reg_len.get() + lhs_reg_len.get())) - 1u32;
 725             let lhs_stops_and_lt_rhs_start_plus_1 = &lhs_stops & lt_rhs_start_plus_1;
 726             let mut included = and_not(lhs_stops, lhs_stops_and_lt_rhs_start_plus_1);
 727             included &= lt_rhs_start_plus_rhs_reg_len_plus_reg_len;
 728             retval += included.count_ones() as u32;
 729         }
 730         retval
 731     }
 732
 733     #[cfg(feature = "fuzzing")]
 734     fn reference_compute_result(
 735         lhs: &Interned<LocSet>,
 736         rhs: &Self,
 737         global_state: &GlobalState,
 738     ) -> u32 {
 739         lhs.iter().map(|loc| rhs.conflicts(loc) as u32).sum::<u32>()
 740     }
 741
 742     fn intern(
 743         v: LocSetMaxConflictsWith<Self>,
 744         global_state: &GlobalState,
 745     ) -> Interned<LocSetMaxConflictsWith<Self>> {
 746         v.into_interned(global_state)
 747     }
 748 }
 749
 750 impl LocSetMaxConflictsWithTrait for Interned<LocSet> {
 751     fn compute_result(lhs: &Interned<LocSet>, rhs: &Self, global_state: &GlobalState) -> u32 {
 752         rhs.iter()
 753             .map(|loc| lhs.clone().max_conflicts_with(loc, global_state))
 754             .max()
 755             .unwrap_or(0)
 756     }
 757
 758     #[cfg(feature = "fuzzing")]
 759     fn reference_compute_result(
 760         lhs: &Interned<LocSet>,
 761         rhs: &Self,
 762         global_state: &GlobalState,
 763     ) -> u32 {
 764         rhs.iter()
 765             .map(|loc| lhs.clone().reference_max_conflicts_with(loc, global_state))
 766             .max()
 767             .unwrap_or(0)
 768     }
 769
 770     fn intern(
 771         v: LocSetMaxConflictsWith<Self>,
 772         global_state: &GlobalState,
 773     ) -> Interned<LocSetMaxConflictsWith<Self>> {
 774         v.into_interned(global_state)
 775     }
 776 }
 777
 778 impl<Rhs: LocSetMaxConflictsWithTrait> LocSetMaxConflictsWith<Rhs> {
 779     pub fn lhs(&self) -> &Interned<LocSet> {
 780         &self.lhs
 781     }
 782     pub fn rhs(&self) -> &Rhs {
 783         &self.rhs
 784     }
 785     pub fn result(&self, global_state: &GlobalState) -> u32 {
 786         match self.result.get() {
 787             Some(v) => v,
 788             None => {
 789                 let retval = Rhs::compute_result(&self.lhs, &self.rhs, global_state);
 790                 self.result.set(Some(retval));
 791                 retval
 792             }
 793         }
 794     }
 795     #[cfg(feature = "fuzzing")]
 796     pub fn reference_result(&self, global_state: &GlobalState) -> u32 {
 797         match self.result.get() {
 798             Some(v) => v,
 799             None => {
 800                 let retval = Rhs::reference_compute_result(&self.lhs, &self.rhs, global_state);
 801                 self.result.set(Some(retval));
 802                 retval
 803             }
 804         }
 805     }
 806 }
 807
 808 impl Interned<LocSet> {
 809     pub fn max_conflicts_with<Rhs>(self, rhs: Rhs, global_state: &GlobalState) -> u32
 810     where
 811         Rhs: LocSetMaxConflictsWithTrait,
 812         LocSetMaxConflictsWith<Rhs>: InternTarget,
 813     {
 814         LocSetMaxConflictsWithTrait::intern(
 815             LocSetMaxConflictsWith {
 816                 lhs: self,
 817                 rhs,
 818                 result: Cell::default(),
 819             },
 820             global_state,
 821         )
 822         .result(global_state)
 823     }
 824     #[cfg(feature = "fuzzing")]
 825     pub fn reference_max_conflicts_with<Rhs>(self, rhs: Rhs, global_state: &GlobalState) -> u32
 826     where
 827         Rhs: LocSetMaxConflictsWithTrait,
 828         LocSetMaxConflictsWith<Rhs>: InternTarget,
 829     {
 830         LocSetMaxConflictsWithTrait::intern(
 831             LocSetMaxConflictsWith {
 832                 lhs: self,
 833                 rhs,
 834                 result: Cell::default(),
 835             },
 836             global_state,
 837         )
 838         .reference_result(global_state)
 839     }
 840     pub fn conflicts_with<Rhs>(self, rhs: Rhs, global_state: &GlobalState) -> bool
 841     where
 842         Rhs: LocSetMaxConflictsWithTrait,
 843         LocSetMaxConflictsWith<Rhs>: InternTarget,
 844     {
 845         self.max_conflicts_with(rhs, global_state) != 0
 846     }
 847 }
 848
 849 #[cfg(test)]
 850 mod tests {
 851     use super::*;
 852
 853     #[test]
 854     fn test_and_not() {
 855         for a in 0..0x10u32 {
 856             for b in 0..0x10 {
 857                 assert_eq!(
 858                     and_not(&BigUint::from(a), BigUint::from(b)),
 859                     (a & !b).into()
 860                 );
 861             }
 862         }
 863     }
 864 }