Skip to content

Commit cfa3fe5

Browse files
borsbors
committed
Auto merge of #90637 - Mark-Simulacrum:liveness-btree, r=lqd
Store liveness in interval sets for region inference On the 100,000 line test case from #90445, this reduces memory usage from 35 GB to 444 MB at peak (based on DHAT results, though with regular malloc), and yields a 9.4x speedup, with wall time going from 14.5 seconds to 1.5s. Performance results show that for the majority of real-world code this has little to no impact, but it's expected to generally scale better for auto-generated functions and other cases which stress this area of the compiler, as results on #90445 illustrate. There may also be further room for improvement in future PRs making use of this data structures benefits over raw bitsets (which, at some level, are a less perfect fit for representing liveness, which is almost always composed of contiguous ranges, not point locations). Fixes #90445.
2 parents 984a6bf + 4abb328 commit cfa3fe5

File tree

7 files changed

+491
-17
lines changed

7 files changed

+491
-17
lines changed

‎Cargo.lock

+1
Original file line numberDiff line numberDiff line change
@@ -3976,6 +3976,7 @@ dependencies = [
39763976
"arrayvec",
39773977
"rustc_macros",
39783978
"rustc_serialize",
3979+
"smallvec",
39793980
]
39803981

39813982
[[package]]

‎compiler/rustc_borrowck/src/region_infer/values.rs

+11-9
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
use rustc_data_structures::fx::FxIndexSet;
2-
use rustc_index::bit_set::{HybridBitSet, SparseBitMatrix};
2+
use rustc_index::bit_set::SparseBitMatrix;
3+
use rustc_index::interval::IntervalSet;
4+
use rustc_index::interval::SparseIntervalMatrix;
35
use rustc_index::vec::Idx;
46
use rustc_index::vec::IndexVec;
57
use rustc_middle::mir::{BasicBlock, Body, Location};
@@ -110,19 +112,19 @@ crate enum RegionElement {
110112
PlaceholderRegion(ty::PlaceholderRegion),
111113
}
112114

113-
/// When we initially compute liveness, we use a bit matrix storing
114-
/// points for each region-vid.
115+
/// When we initially compute liveness, we use an interval matrix storing
116+
/// liveness ranges for each region-vid.
115117
crate struct LivenessValues<N: Idx> {
116118
elements: Rc<RegionValueElements>,
117-
points: SparseBitMatrix<N, PointIndex>,
119+
points: SparseIntervalMatrix<N, PointIndex>,
118120
}
119121

120122
impl<N: Idx> LivenessValues<N> {
121123
/// Creates a new set of "region values" that tracks causal information.
122124
/// Each of the regions in num_region_variables will be initialized with an
123125
/// empty set of points and no causal information.
124126
crate fn new(elements: Rc<RegionValueElements>) -> Self {
125-
Self { points: SparseBitMatrix::new(elements.num_points), elements }
127+
Self { points: SparseIntervalMatrix::new(elements.num_points), elements }
126128
}
127129

128130
/// Iterate through each region that has a value in this set.
@@ -140,7 +142,7 @@ impl<N: Idx> LivenessValues<N> {
140142

141143
/// Adds all the elements in the given bit array into the given
142144
/// region. Returns whether any of them are newly added.
143-
crate fn add_elements(&mut self, row: N, locations: &HybridBitSet<PointIndex>) -> bool {
145+
crate fn add_elements(&mut self, row: N, locations: &IntervalSet<PointIndex>) -> bool {
144146
debug!("LivenessValues::add_elements(row={:?}, locations={:?})", row, locations);
145147
self.points.union_row(row, locations)
146148
}
@@ -153,7 +155,7 @@ impl<N: Idx> LivenessValues<N> {
153155
/// Returns `true` if the region `r` contains the given element.
154156
crate fn contains(&self, row: N, location: Location) -> bool {
155157
let index = self.elements.point_from_location(location);
156-
self.points.contains(row, index)
158+
self.points.row(row).map_or(false, |r| r.contains(index))
157159
}
158160

159161
/// Returns an iterator of all the elements contained by the region `r`
@@ -221,7 +223,7 @@ impl PlaceholderIndices {
221223
crate struct RegionValues<N: Idx> {
222224
elements: Rc<RegionValueElements>,
223225
placeholder_indices: Rc<PlaceholderIndices>,
224-
points: SparseBitMatrix<N, PointIndex>,
226+
points: SparseIntervalMatrix<N, PointIndex>,
225227
free_regions: SparseBitMatrix<N, RegionVid>,
226228

227229
/// Placeholders represent bound regions -- so something like `'a`
@@ -241,7 +243,7 @@ impl<N: Idx> RegionValues<N> {
241243
let num_placeholders = placeholder_indices.len();
242244
Self {
243245
elements: elements.clone(),
244-
points: SparseBitMatrix::new(elements.num_points),
246+
points: SparseIntervalMatrix::new(elements.num_points),
245247
placeholder_indices: placeholder_indices.clone(),
246248
free_regions: SparseBitMatrix::new(num_universal_regions),
247249
placeholders: SparseBitMatrix::new(num_placeholders),

‎compiler/rustc_borrowck/src/type_check/liveness/trace.rs

+9-8
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
use rustc_data_structures::fx::{FxHashMap, FxHashSet};
22
use rustc_index::bit_set::HybridBitSet;
3+
use rustc_index::interval::IntervalSet;
34
use rustc_infer::infer::canonical::QueryRegionConstraints;
45
use rustc_middle::mir::{BasicBlock, Body, ConstraintCategory, Local, Location};
56
use rustc_middle::ty::{Ty, TypeFoldable};
@@ -105,12 +106,12 @@ struct LivenessResults<'me, 'typeck, 'flow, 'tcx> {
105106

106107
/// Points where the current variable is "use live" -- meaning
107108
/// that there is a future "full use" that may use its value.
108-
use_live_at: HybridBitSet<PointIndex>,
109+
use_live_at: IntervalSet<PointIndex>,
109110

110111
/// Points where the current variable is "drop live" -- meaning
111112
/// that there is no future "full use" that may use its value, but
112113
/// there is a future drop.
113-
drop_live_at: HybridBitSet<PointIndex>,
114+
drop_live_at: IntervalSet<PointIndex>,
114115

115116
/// Locations where drops may occur.
116117
drop_locations: Vec<Location>,
@@ -125,8 +126,8 @@ impl<'me, 'typeck, 'flow, 'tcx> LivenessResults<'me, 'typeck, 'flow, 'tcx> {
125126
LivenessResults {
126127
cx,
127128
defs: HybridBitSet::new_empty(num_points),
128-
use_live_at: HybridBitSet::new_empty(num_points),
129-
drop_live_at: HybridBitSet::new_empty(num_points),
129+
use_live_at: IntervalSet::new(num_points),
130+
drop_live_at: IntervalSet::new(num_points),
130131
drop_locations: vec![],
131132
stack: vec![],
132133
}
@@ -165,7 +166,7 @@ impl<'me, 'typeck, 'flow, 'tcx> LivenessResults<'me, 'typeck, 'flow, 'tcx> {
165166
drop_used: Vec<(Local, Location)>,
166167
live_locals: FxHashSet<Local>,
167168
) {
168-
let locations = HybridBitSet::new_empty(self.cx.elements.num_points());
169+
let locations = IntervalSet::new(self.cx.elements.num_points());
169170

170171
for (local, location) in drop_used {
171172
if !live_locals.contains(&local) {
@@ -456,7 +457,7 @@ impl<'tcx> LivenessContext<'_, '_, '_, 'tcx> {
456457
fn add_use_live_facts_for(
457458
&mut self,
458459
value: impl TypeFoldable<'tcx>,
459-
live_at: &HybridBitSet<PointIndex>,
460+
live_at: &IntervalSet<PointIndex>,
460461
) {
461462
debug!("add_use_live_facts_for(value={:?})", value);
462463

@@ -473,7 +474,7 @@ impl<'tcx> LivenessContext<'_, '_, '_, 'tcx> {
473474
dropped_local: Local,
474475
dropped_ty: Ty<'tcx>,
475476
drop_locations: &[Location],
476-
live_at: &HybridBitSet<PointIndex>,
477+
live_at: &IntervalSet<PointIndex>,
477478
) {
478479
debug!(
479480
"add_drop_live_constraint(\
@@ -521,7 +522,7 @@ impl<'tcx> LivenessContext<'_, '_, '_, 'tcx> {
521522
elements: &RegionValueElements,
522523
typeck: &mut TypeChecker<'_, 'tcx>,
523524
value: impl TypeFoldable<'tcx>,
524-
live_at: &HybridBitSet<PointIndex>,
525+
live_at: &IntervalSet<PointIndex>,
525526
) {
526527
debug!("make_all_regions_live(value={:?})", value);
527528
debug!(

‎compiler/rustc_index/Cargo.toml

+1
Original file line numberDiff line numberDiff line change
@@ -10,3 +10,4 @@ doctest = false
1010
arrayvec = { version = "0.7", default-features = false }
1111
rustc_serialize = { path = "../rustc_serialize" }
1212
rustc_macros = { path = "../rustc_macros" }
13+
smallvec = "1"

0 commit comments

Comments
 (0)