| Age | Commit message (Collapse) | Author | Lines |
|---|
|
`BitwiseOperator` is an unnecessarily low-level thing. This commit
replaces it with `BitSetOperator`, which works on `BitSet`s instead of
words. Within `bit_set.rs`, the commit eliminates `Intersect`, `Union`,
and `Subtract` by instead passing a function to `bitwise()`.
|
|
Currently we have two files implementing bitsets (and 2D bit matrices).
This commit combines them into one, taking the best features from each.
This involves renaming a lot of things. The high level changes are as
follows.
- bitvec.rs --> bit_set.rs
- indexed_set.rs --> (removed)
- BitArray + IdxSet --> BitSet (merged, see below)
- BitVector --> GrowableBitSet
- {,Sparse,Hybrid}IdxSet --> {,Sparse,Hybrid}BitSet
- BitMatrix --> BitMatrix
- SparseBitMatrix --> SparseBitMatrix
The changes within the bitset types themselves are as follows.
```
OLD OLD NEW
BitArray<C> IdxSet<T> BitSet<T>
-------- ------ ------
grow - grow
new - (remove)
new_empty new_empty new_empty
new_filled new_filled new_filled
- to_hybrid to_hybrid
clear clear clear
set_up_to set_up_to set_up_to
clear_above - clear_above
count - count
contains(T) contains(&T) contains(T)
contains_all - superset
is_empty - is_empty
insert(T) add(&T) insert(T)
insert_all - insert_all()
remove(T) remove(&T) remove(T)
words words words
words_mut words_mut words_mut
- overwrite overwrite
merge union union
- subtract subtract
- intersect intersect
iter iter iter
```
In general, when choosing names I went with:
- names that are more obvious (e.g. `BitSet` over `IdxSet`).
- names that are more like the Rust libraries (e.g. `T` over `C`,
`insert` over `add`);
- names that are more set-like (e.g. `union` over `merge`, `superset`
over `contains_all`, `domain_size` over `num_bits`).
Also, using `T` for index arguments seems more sensible than `&T` --
even though the latter is standard in Rust collection types -- because
indices are always copyable. It also results in fewer `&` and `*`
sigils in practice.
|
|
|
|
|
|
Remove bitslice.rs
As the comment in `bitslice.rs` says:
> FIXME: merge with `bitvec`
|
|
Because they're just thin wrappers around `BitIter` and `slice::Iter`.
|
|
This requires the following changes.
- It moves parts of bitslice.rs into bitvec.rs: `bitwise()`,
`BitwiseOperator`, `bits_to_string()`.
- It changes `IdxSet` to just be a wrapper around `BitArray`.
- It changes `BitArray` and `BitVec` to use `usize` words instead of
`u128` words. (`BitSlice` and `IdxSet` already use `usize`.) Local
profiling showed `usize` was better.
- It moves some operations from `IdxSet` into `BitArray`:
`new_filled()`, `clear()`, `set_up_to()`, `trim_to()` (renamed
`clear_above()`), `words()` and `words_mut()`, `encode()` and
`decode(). The `IdxSet` operations now just call the `BitArray`
operations.
- It replaces `BitArray`'s iterator implementation with `IdxSet`'s,
because the latter is more concise. It also removes the buggy
`size_hint` function from `BitArray`'s iterator, which counted the
number of *words* rather than the number of *bits*. `IdxSet`'s
iterator is now just a thin wrapper around `BitArray`'s iterator.
- It moves some unit tests from `indexed_set.rs` to `bitvec.rs`.
|
|
Make it have the semantics of subtype.
|
|
Skip a shared borrow of a immutable local variables
issue #53643
r? @nikomatsakis
|
|
use `NonZeroU32` in `newtype_index!`macro, change syntax
Various improvements to the `newtype_index!` macro:
- Use `NonZeroU32` so that `Option<T>` is cheap
- More ergonomic helper method, no need to import `Idx` trait all the time
- Improve syntax to use `struct` keyword so that ripgrep works to find type def'n
Fixes https://github.com/rust-lang/rust/issues/50337
I'm curious to see if this passes tests =)
|
|
Rewrite `precompute_borrows_out_of_scope` for fewer hash table lookups.
It now does one hash table lookup per basic block, instead of one per
statement. This is worthwhile because this function is hot for NLL
builds of `ucd`.
I haven't measured the effect of this yet because I'm having trouble doing optimized builds of rustc that are suitable for profiling (#53916). I will do an online perf run instead.
r? @nikomatsakis
|
|
|
|
Rollup of 17 pull requests
Successful merges:
- #53299 (Updated core/macros.rs to note it works in a no_std environment.)
- #53376 (Cross reference io::copy and fs::copy in docs.)
- #53455 (Individual docs for {from,to}_*_bytes)
- #53550 (librustc_lint: In recursion warning, change 'recurring' to 'recursing')
- #53860 (Migrate (some) of run-pass/ to ui)
- #53874 (Implement Unpin for Box, Rc, and Arc)
- #53895 (tidy: Cleanups and clippy warning fixes)
- #53946 (Clarify `ManuallyDrop` docs)
- #53948 (Minimized clippy test from when NLL disabled two-phase borrows)
- #53959 (Add .git extension to submodule paths missing it)
- #53966 (A few cleanups and minor improvements to mir/dataflow)
- #53967 (propagate build.python into cmake)
- #53979 (Remove `#[repr(transparent)]` from atomics)
- #53991 (Add unchecked_shl/shr check for intrinsics to fix miri's test suit)
- #53992 (migrate run-pass/borrowck to ui/run-pass)
- #53994 (migrate run-pass/*/ to ui/run-pass)
- #54023 (update clippy submodule)
|
|
Add help message for missing IndexMut impl with NLL
Fixes #53228.
r? @nikomatsakis
|
|
issue #53643
|
|
|
|
It now does one hash table lookup per basic block, instead of one per
statement. This is worthwhile because this function is hot for NLL
builds of `ucd`.
|
|
|
|
|
|
|
|
|
|
They let `union()`, `union_sparse()` and `union_hybrid()` be merged.
Likewise for subtract()`, `subtract_sparse()` and `subtract_hybrid()`.
|
|
Merge `IdxSet` and `IdxSetBuf`
Because it simplifies things.
@r? nikomatsakis
|
|
Ty{Adt|Array|Slice|RawPtr|Ref|FnDef|FnPtr|Dynamic|Closure|Generator|GeneratorWitness|Never|Tuple|Projection|Anon|Infer|Error}
|
|
Now that the `Buf` vs. non-`Buf` distinction has been removed, it makes
sense to drop the `Buf` suffix and use the shorter names everywhere.
|
|
This makes it more like `AllSets::{gen,kill}_set`, removes the need for
a bunch of bitset range computations, and removes the need for `Bits`.
It's marginally less efficient, because we have to allocate one bitset
per basic block instead of one large shared bitset, but the difference
is negligible in practice.
|
|
|
|
|
|
Speed up NLL with HybridIdxSetBuf.
It's a sparse-when-small but dense-when-large index set that is very
efficient for sets that (a) have few elements, (b) have large
universe_size values, and (c) are cleared frequently. Which makes it
perfect for the `gen_set` and `kill_set` sets used by the new borrow
checker.
This patch reduces `tuple-stress`'s NLL-check time by 40%, and up to 12%
for several other benchmarks. And it halves the max-rss for `keccak`,
and has smaller wins for `inflate` and `clap-rs`.
|
|
`HybridIdxSetBuf` is a sparse-when-small but dense-when-large index set
that is very efficient for sets that (a) have few elements, (b) have
large `universe_size` values, and (c) are cleared frequently. Which
makes it perfect for the `gen_set` and `kill_set` sets used by the new
borrow checker.
This patch reduces the execution time of the five slowest NLL benchmarks
by 55%, 21%, 16%, 10% and 9%. It also reduces the max-rss of three
benchmarks by 53%, 33%, and 9%.
|
|
|
|
|
|
live across a yield terminator
|
|
Promoteds are statics and statics have a place, not just a value
r? @eddyb
This makes everything around promoteds a little simpler
|
|
Simplify 2 functions in rustc_mir/dataflow
- `graphviz::outgoing`: the `enumerate` only provides indices; use a range instead
- `DataflowState::interpret_set`: change a push loop to an iterator and remove the `each_bit` helper function
|
|
|
|
|
|
|
|
|
|
|
|
`BitSlice` fixes
`propagate_bits_into_entry_set_for` and `BitSlice::bitwise` are hot for some benchmarks under NLL. I tried and failed to speed them up. (Increasing the size of `bit_slice::Word` from `usize` to `u128` caused a slowdown, even though decreasing the size of `bitvec::Word` from `u128` to `u64` also caused a slowdown. Weird.)
Anyway, along the way I fixed up several problems in and around the `BitSlice` code.
r? @nikomatsakis
|
|
The strategy is this:
- we compute SCCs once all outlives constraints are known
- we allocate a set of values **per region** for storing liveness
- we allocate a set of values **per SCC** for storing the final values
- when we add a liveness constraint to the region R, we also add it
to the final value of the SCC to which R belongs
- then we can apply the constraints by just walking the DAG for the
SCCs and union'ing the children (which have their liveness
constraints within)
There are a few intermediate refactorings that I really ought to have
broken out into their own commits:
- reverse the constraint graph so that `R1: R2` means `R1 -> R2` and
not `R2 -> R1`. This fits better with the SCC computation and new
style of inference (`->` now means "take value from" and not "push
value into")
- this does affect some of the UI tests, since they traverse the
graph, but mostly the artificial ones and they don't necessarily
seem worse
- put some things (constraint set, etc) into `Rc`. This lets us root
them to permit mutation and iteration. It also guarantees they don't
change, which is critical to the correctness of the algorithm.
- Generalize various helpers that previously operated only on points
to work on any sort of region element.
|
|
Currently `Word` is `usize`, and there are various places in the code
that assume this.
This patch mostly just changes `usize` occurrences to `Word`. Most of
the changes were found as compile errors when I changed `Word` to a type
other than `usize`, but there was one non-obvious case in
librustc_mir/dataflow/mod.rs that caused bounds check failures before I
fixed it.
|
|
It has a single callsite, and duplicates some code from that callsite.
The code is more concise and clearer this way.
|
|
Visit the mir basic blocks in reverse-postfix order
cc #51167
r? @nikomatsakis
|
|
|
|
|
|
Avoid needless allocations in `liveness_of_locals`.
We don't need to replace the heap-allocated bitset, we can just
overwrite its contents.
This speeds up most NLL benchmarks, the best by 1.5%.
r? @nikomatsakis
|
|
The current situation is something of a mess.
- `IdxSetBuf` derefs to `IdxSet`.
- `IdxSetBuf` implements `Clone`, and therefore has a provided `clone_from`
method, which does allocation and so is expensive.
- `IdxSet` has a `clone_from` method that is non-allocating and therefore
cheap, but this method is not from the `Clone` trait.
As a result, if you have an `IdxSetBuf` called `b`, if you call
`b.clone_from(b2)` you'll get the expensive `IdxSetBuf` method, but if you call
`(*b).clone_from(b2)` you'll get the cheap `IdxSetBuf` method.
`liveness_of_locals()` does the former, presumably unintentionally, and
therefore does lots of unnecessary allocations.
Having a `clone_from` method that isn't from the `Clone` trait is a bad idea in
general, so this patch renames it as `overwrite`. This avoids the unnecessary
allocations in `liveness_of_locals()`, speeding up most NLL benchmarks, the
best by 1.5%. It also means that calls of the form `(*b).clone_from(b2)` can be
rewritten as `b.overwrite(b2)`.
|
|
|
