| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Use a valid name for graphviz graphs
Hiridification has broken graphviz output because `HirId` has a more complex display implemetation than `NodeId`. Since the id was just used to generate a distinct identifier, we just pull out the various constituent indexed.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
MIR borrowck doesn't accept the example of iterating and updating a mutable reference
Fixes #46589.
r? @pnkfelix or @nikomatsakis
|
|
This avoids all sorts of confusing issues with using both `dest_place`
and `self` in the `propagate_call_return` function in the
`BitDenotation` implementation for `Borrows`.
|
|
|
|
As suggested in the feedback for #55244.
When I replaced the macro with a function, rustc started complaining
that there were two unused functions so I also removed those.
|
|
|
|
`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.
|
|
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`.
|
|
|
|
|
|
|
|
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
|
|
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.
|
|
|
|
`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%.
|
|
|
|
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
|
|
|
|
|
|
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)`.
|
|
|
|
|
|
|
|
Remove some unnecessary IdxSet methods
This replaces `IdxSet:: reset_to_empty` with `IdxSet:: clear`, and `IdxSet::elems`/`IdxSet::each_bit` with `IdxSet::iter`. Based on some [comments on #rustc](https://botbot.me/mozilla/rustc/2018-01-23/?msg=96063396).
r? @pnkfelix
|
|
|
|
|
|
|
|
Sometimes a simple goto misses the cleanup/unwind edges. Specifically, in the
case of infinite loops such as those introduced by a loop statement without any
other out edges. Analogous to TerminatorKind::FalseEdges; this new terminator
kind is used when we want borrowck to consider an unwind path, but real control
flow should never actually take it.
|
|
Generator bugfixes
r? @nikomatsakis
|
|
Fixes #47736
|
|
|
|
NLL fixes
First, introduce pre-statement effects to dataflow to fix #46875. Edge dataflow effects might make that redundant, but I'm not sure of the best way to integrate them with liveness etc., and if this is a hack, this is one of the cleanest hacks I've seen.
And I want a small fix to avoid the torrent of bug reports.
Second, fix linking of projections to fix #46974
r? @pnkfelix
|
|
|
|
The Abort Terminatorkind will cause an llvm.trap function call to be
emitted.
Signed-off-by: David Henningsson <diwic@ubuntu.com>
|
|
High-level picture: The old `Borrows` analysis is now called
`Reservations` (implemented as a newtype wrapper around `Borrows`);
this continues to compute whether a `Rvalue::Ref` can reach a
statement without an intervening `EndRegion`. In addition, we also
track what `Place` each such `Rvalue::Ref` was immediately assigned
to in a given borrow (yay for MIR-structural properties!).
The new `ActiveBorrows` analysis then tracks the initial use of any of
those assigned `Places` for a given borrow. I.e. a borrow becomes
"active" immediately after it starts being "used" in some way. (This
is conservative in the sense that we will treat a copy `x = y;` as a
use of `y`; in principle one might further delay activation in such
cases.)
The new `ActiveBorrows` analysis needs to take the `Reservations`
results as an initial input, because the reservation state influences
the gen/kill sets for `ActiveBorrows`. In particular, a use of `a`
activates a borrow `a = &b` if and only if there exists a path (in the
control flow graph) from the borrow to that use. So we need to know if
the borrow reaches a given use to know if it really gets a gen-bit or
not.
* Incorporating the output from one dataflow analysis into the input
of another required more changes to the infrastructure than I had
expected, and even after those changes, the resulting code is still
a bit subtle.
* In particular, Since we need to know the intrablock reservation
state, we need to dynamically update a bitvector for the
reservations as we are also trying to compute the gen/kills
bitvector for the active borrows.
* The way I ended up deciding to do this (after also toying with at
least two other designs) is to put both the reservation state and
the active borrow state into a single bitvector. That is why we now
have separate (but related) `BorrowIndex` and
`ReserveOrActivateIndex`: each borrow index maps to a pair of
neighboring reservation and activation indexes.
As noted above, these changes are solely adding the active borrows
dataflow analysis (and updating the existing code to cope with the
switch from `Borrows` to `Reservations`). The code to process the
bitvector in the borrow checker currently just skips over all of the
active borrow bits.
But atop this commit, one *can* observe the analysis results by
looking at the graphviz output, e.g. via
```rust
#[rustc_mir(borrowck_graphviz_preflow="pre_two_phase.dot",
borrowck_graphviz_postflow="post_two_phase.dot")]
```
Includes doc for `FindPlaceUses`, as well as `Reservations` and
`ActiveBorrows` structs, which are wrappers are the `Borrows` struct
that dictate which flow analysis should be performed.
|
|
intrablock state.
(Still musing about whether it could make sense to revise the design
here to make these constraints on usage explicit.)
|
|
This is meant to ease development of multi-stage dataflow analyses
where the output from one analysis is used to initialize the state
for the next; in such a context, you cannot start with `bottom_value`
for all the bits.
|
|
Made `do_dataflow` and related API `pub(crate)`.
|
|
If the gen/kill bits are set there, the effects of `start_block_effects`
will not be seen when using `FlowAtLocation` etc. to go over the MIR.
EverInitializedLvals is the only pass that got this wrong, but this
fixes the footgun for everyone.
|
