Skip to content

Commit 20b8c98

Browse files
ZalatharZalathar
committed
Avoid the would-change check for bitset chunks that are unique
1 parent b49ecc9 commit 20b8c98

3 files changed

Lines changed: 122 additions & 41 deletions

File tree

‎compiler/rustc_index/src/bit_set.rs‎

Lines changed: 72 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -743,6 +743,39 @@ impl<T: Idx> ChunkedBitSet<T> {
743743
bit_relations_inherent_impls! {}
744744
}
745745

746+
/// Behaves like [`Rc::make_mut`], except that if an inner clone would be
747+
/// required but `would_change` returns false, then no inner clone occurs and
748+
/// None is returned instead.
749+
///
750+
/// This function assumes that `would_change` is cheaper than an inner clone,
751+
/// but expensive enough to be worth avoiding if an inner clone isn't required.
752+
///
753+
/// In other words, this function returns:
754+
/// - Some (without cloning) if [`Rc::get_mut`] succeeds
755+
/// - None (without cloning) if `would_change` returns false
756+
/// - Some (after cloning) otherwise
757+
fn make_chunk_words_mut_for_change<'a>(
758+
self_words: &'a mut Rc<[Word; CHUNK_WORDS]>,
759+
would_change: impl Fn(&[Word; CHUNK_WORDS]) -> bool,
760+
) -> Option<&'a mut [Word; CHUNK_WORDS]> {
761+
// If the Rc is already unique, we can skip the would-change check entirely.
762+
if let Some(words) = Rc::get_mut(self_words) {
763+
// Round-trip through a raw pointer to work around a well-known limitation of the
764+
// non-Polonius borrow checker <https://github.com/rust-lang/rust/issues/54663>.
765+
// SAFETY: Equivalent to `Some(words)`, which is sound but only accepted by Polonius;
766+
// see `tests/ui/nll/polonius/nll-problem-case-3-issue-54663.rs`.
767+
return Some(unsafe { &mut *(words as *mut _) });
768+
};
769+
770+
// At this point we would need to clone the chunk if we wanted to return `&mut`,
771+
// so first check if the intended operation would actually modify the words.
772+
if !would_change(self_words) {
773+
return None;
774+
}
775+
776+
Some(Rc::make_mut(self_words))
777+
}
778+
746779
impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> {
747780
fn union(&mut self, other: &ChunkedBitSet<T>) -> bool {
748781
assert_eq!(self.domain_size, other.domain_size);
@@ -780,33 +813,28 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> {
780813
// performance win. Also, we only need to operate on the
781814
// in-use words, hence the slicing.
782815
let num_words = num_words(chunk_domain_size as usize);
783-
784-
// If both sides are the same, nothing will change. This
785-
// case is very common and it's a pretty fast check, so
786-
// it's a performance win to do it.
787-
if self_chunk_words[0..num_words] == other_chunk_words[0..num_words] {
788-
continue;
789-
}
790-
791-
// Do a more precise "will anything change?" test. Also a
792-
// performance win.
793816
let op = |a, b| a | b;
794-
if !bitwise_changes(
795-
&self_chunk_words[0..num_words],
796-
&other_chunk_words[0..num_words],
797-
op,
798-
) {
817+
818+
// Try to get a mutable reference to our words, but only if doing so is
819+
// cheap, or if we're definitely going to modify the words.
820+
let Some(self_chunk_words) =
821+
make_chunk_words_mut_for_change(self_chunk_words, |self_chunk_words| {
822+
let lhs = &self_chunk_words[0..num_words];
823+
let rhs = &other_chunk_words[0..num_words];
824+
// If both sides are the same, nothing will change. That case is very
825+
// common, so it's a performance win to do an extremely fast equality
826+
// check before the full would-change check.
827+
(lhs != rhs) && bitwise_changes(lhs, rhs, op)
828+
})
829+
else {
799830
continue;
800-
}
831+
};
801832

802-
// If we reach here, `self_chunk_words` is definitely changing.
803-
let self_chunk_words = Rc::make_mut(self_chunk_words);
804-
let has_changed = bitwise(
833+
bitwise(
805834
&mut self_chunk_words[0..num_words],
806835
&other_chunk_words[0..num_words],
807836
op,
808837
);
809-
debug_assert!(has_changed);
810838
*self_chunk_count = count_ones(&self_chunk_words[0..num_words]) as ChunkSize;
811839
if *self_chunk_count == chunk_domain_size {
812840
*self_chunk = Ones;
@@ -868,21 +896,24 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> {
868896
// See `ChunkedBitSet::union` for details on what is happening here.
869897
let num_words = num_words(chunk_domain_size as usize);
870898
let op = |a: Word, b: Word| a & !b;
871-
if !bitwise_changes(
872-
&self_chunk_words[0..num_words],
873-
&other_chunk_words[0..num_words],
874-
op,
875-
) {
899+
900+
let Some(self_chunk_words) =
901+
make_chunk_words_mut_for_change(self_chunk_words, |self_chunk_words| {
902+
bitwise_changes(
903+
&self_chunk_words[0..num_words],
904+
&other_chunk_words[0..num_words],
905+
op,
906+
)
907+
})
908+
else {
876909
continue;
877-
}
910+
};
878911

879-
let self_chunk_words = Rc::make_mut(self_chunk_words);
880-
let has_changed = bitwise(
912+
bitwise(
881913
&mut self_chunk_words[0..num_words],
882914
&other_chunk_words[0..num_words],
883915
op,
884916
);
885-
debug_assert!(has_changed);
886917
*self_chunk_count = count_ones(&self_chunk_words[0..num_words]) as ChunkSize;
887918
if *self_chunk_count == 0 {
888919
*self_chunk = Zeros;
@@ -926,21 +957,24 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> {
926957
// See `ChunkedBitSet::union` for details on what is happening here.
927958
let num_words = num_words(chunk_domain_size as usize);
928959
let op = |a, b| a & b;
929-
if !bitwise_changes(
930-
&self_chunk_words[0..num_words],
931-
&other_chunk_words[0..num_words],
932-
op,
933-
) {
960+
961+
let Some(self_chunk_words) =
962+
make_chunk_words_mut_for_change(self_chunk_words, |self_chunk_words| {
963+
bitwise_changes(
964+
&self_chunk_words[0..num_words],
965+
&other_chunk_words[0..num_words],
966+
op,
967+
)
968+
})
969+
else {
934970
continue;
935-
}
971+
};
936972

937-
let self_chunk_words = Rc::make_mut(self_chunk_words);
938-
let has_changed = bitwise(
973+
bitwise(
939974
&mut self_chunk_words[0..num_words],
940975
&other_chunk_words[0..num_words],
941976
op,
942977
);
943-
debug_assert!(has_changed);
944978
*self_chunk_count = count_ones(&self_chunk_words[0..num_words]) as ChunkSize;
945979
if *self_chunk_count == 0 {
946980
*self_chunk = Zeros;

‎tests/ui/nll/polonius/nll-problem-case-3-issue-54663.nll.stderr‎

Lines changed: 32 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
error[E0499]: cannot borrow `*x` as mutable more than once at a time
2-
--> $DIR/nll-problem-case-3-issue-54663.rs:20:9
2+
--> $DIR/nll-problem-case-3-issue-54663.rs:22:9
33
|
44
LL | fn foo(x: &mut u8) -> Option<&u8> {
55
| - let's call the lifetime of this reference `'1`
@@ -11,6 +11,35 @@ LL | }
1111
LL | bar(x)
1212
| ^ second mutable borrow occurs here
1313

14-
error: aborting due to 1 previous error
14+
error[E0502]: cannot borrow `*self_words` as immutable because it is also borrowed as mutable
15+
--> $DIR/nll-problem-case-3-issue-54663.rs:38:22
16+
|
17+
LL | fn make_chunk_words_mut_for_change<'a>(
18+
| -- lifetime `'a` defined here
19+
...
20+
LL | if let Some(words) = Rc::get_mut(self_words) {
21+
| ---------- mutable borrow occurs here
22+
LL | return Some(words);
23+
| ----------- returning this value requires that `*self_words` is borrowed for `'a`
24+
...
25+
LL | if !would_change(self_words) {
26+
| ^^^^^^^^^^ immutable borrow occurs here
27+
28+
error[E0499]: cannot borrow `*self_words` as mutable more than once at a time
29+
--> $DIR/nll-problem-case-3-issue-54663.rs:42:23
30+
|
31+
LL | fn make_chunk_words_mut_for_change<'a>(
32+
| -- lifetime `'a` defined here
33+
...
34+
LL | if let Some(words) = Rc::get_mut(self_words) {
35+
| ---------- first mutable borrow occurs here
36+
LL | return Some(words);
37+
| ----------- returning this value requires that `*self_words` is borrowed for `'a`
38+
...
39+
LL | Some(Rc::make_mut(self_words))
40+
| ^^^^^^^^^^ second mutable borrow occurs here
41+
42+
error: aborting due to 3 previous errors
1543

16-
For more information about this error, try `rustc --explain E0499`.
44+
Some errors have detailed explanations: E0499, E0502.
45+
For more information about an error, try `rustc --explain E0499`.

‎tests/ui/nll/polonius/nll-problem-case-3-issue-54663.rs‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,8 @@
1313
//@ [legacy] check-pass
1414
//@ [legacy] compile-flags: -Z polonius=legacy
1515

16+
use std::rc::Rc;
17+
1618
fn foo(x: &mut u8) -> Option<&u8> {
1719
if let Some(y) = bar(x) {
1820
return Some(y);
@@ -23,3 +25,19 @@ fn foo(x: &mut u8) -> Option<&u8> {
2325
fn bar(x: &mut u8) -> Option<&u8> {
2426
Some(x)
2527
}
28+
29+
// Adapted from the compiler's `make_chunk_words_mut_for_change` in `bit_set.rs`.
30+
fn make_chunk_words_mut_for_change<'a>(
31+
self_words: &'a mut Rc<[u64; 32]>,
32+
would_change: impl Fn(&[u64; 32]) -> bool,
33+
) -> Option<&'a mut [u64; 32]> {
34+
if let Some(words) = Rc::get_mut(self_words) {
35+
return Some(words);
36+
};
37+
38+
if !would_change(self_words) {
39+
return None;
40+
}
41+
42+
Some(Rc::make_mut(self_words))
43+
}

0 commit comments

Comments
 (0)