1 #![deny(rustc::untranslatable_diagnostic)]
2 #![deny(rustc::diagnostic_outside_of_impl)]
3 use rustc_data_structures::fx::FxIndexSet;
4 use rustc_index::bit_set::SparseBitMatrix;
5 use rustc_index::interval::IntervalSet;
6 use rustc_index::interval::SparseIntervalMatrix;
7 use rustc_index::vec::Idx;
8 use rustc_index::vec::IndexVec;
9 use rustc_middle::mir::{BasicBlock, Body, Location};
10 use rustc_middle::ty::{self, RegionVid};
14 /// Maps between a `Location` and a `PointIndex` (and vice versa).
15 pub(crate) struct RegionValueElements {
16 /// For each basic block, how many points are contained within?
17 statements_before_block: IndexVec<BasicBlock, usize>,
19 /// Map backward from each point to the basic block that it
21 basic_blocks: IndexVec<PointIndex, BasicBlock>,
26 impl RegionValueElements {
27 pub(crate) fn new(body: &Body<'_>) -> Self {
28 let mut num_points = 0;
29 let statements_before_block: IndexVec<BasicBlock, usize> = body
34 num_points += block_data.statements.len() + 1;
38 debug!("RegionValueElements: statements_before_block={:#?}", statements_before_block);
39 debug!("RegionValueElements: num_points={:#?}", num_points);
41 let mut basic_blocks = IndexVec::with_capacity(num_points);
42 for (bb, bb_data) in body.basic_blocks.iter_enumerated() {
43 basic_blocks.extend((0..=bb_data.statements.len()).map(|_| bb));
46 Self { statements_before_block, basic_blocks, num_points }
49 /// Total number of point indices
50 pub(crate) fn num_points(&self) -> usize {
54 /// Converts a `Location` into a `PointIndex`. O(1).
55 pub(crate) fn point_from_location(&self, location: Location) -> PointIndex {
56 let Location { block, statement_index } = location;
57 let start_index = self.statements_before_block[block];
58 PointIndex::new(start_index + statement_index)
61 /// Converts a `Location` into a `PointIndex`. O(1).
62 pub(crate) fn entry_point(&self, block: BasicBlock) -> PointIndex {
63 let start_index = self.statements_before_block[block];
64 PointIndex::new(start_index)
67 /// Return the PointIndex for the block start of this index.
68 pub(crate) fn to_block_start(&self, index: PointIndex) -> PointIndex {
69 PointIndex::new(self.statements_before_block[self.basic_blocks[index]])
72 /// Converts a `PointIndex` back to a location. O(1).
73 pub(crate) fn to_location(&self, index: PointIndex) -> Location {
74 assert!(index.index() < self.num_points);
75 let block = self.basic_blocks[index];
76 let start_index = self.statements_before_block[block];
77 let statement_index = index.index() - start_index;
78 Location { block, statement_index }
81 /// Sometimes we get point-indices back from bitsets that may be
82 /// out of range (because they round up to the nearest 2^N number
83 /// of bits). Use this function to filter such points out if you
85 pub(crate) fn point_in_range(&self, index: PointIndex) -> bool {
86 index.index() < self.num_points
90 rustc_index::newtype_index! {
91 /// A single integer representing a `Location` in the MIR control-flow
92 /// graph. Constructed efficiently from `RegionValueElements`.
93 #[debug_format = "PointIndex({})"]
94 pub struct PointIndex {}
97 rustc_index::newtype_index! {
98 /// A single integer representing a `ty::Placeholder`.
99 #[debug_format = "PlaceholderIndex({})"]
100 pub struct PlaceholderIndex {}
103 /// An individual element in a region value -- the value of a
104 /// particular region variable consists of a set of these elements.
105 #[derive(Debug, Clone)]
106 pub(crate) enum RegionElement {
107 /// A point in the control-flow graph.
110 /// A universally quantified region from the root universe (e.g.,
111 /// a lifetime parameter).
112 RootUniversalRegion(RegionVid),
114 /// A placeholder (e.g., instantiated from a `for<'a> fn(&'a u32)`
116 PlaceholderRegion(ty::PlaceholderRegion),
119 /// When we initially compute liveness, we use an interval matrix storing
120 /// liveness ranges for each region-vid.
121 pub(crate) struct LivenessValues<N: Idx> {
122 elements: Rc<RegionValueElements>,
123 points: SparseIntervalMatrix<N, PointIndex>,
126 impl<N: Idx> LivenessValues<N> {
127 /// Creates a new set of "region values" that tracks causal information.
128 /// Each of the regions in num_region_variables will be initialized with an
129 /// empty set of points and no causal information.
130 pub(crate) fn new(elements: Rc<RegionValueElements>) -> Self {
131 Self { points: SparseIntervalMatrix::new(elements.num_points), elements }
134 /// Iterate through each region that has a value in this set.
135 pub(crate) fn rows(&self) -> impl Iterator<Item = N> {
139 /// Adds the given element to the value for the given region. Returns whether
140 /// the element is newly added (i.e., was not already present).
141 pub(crate) fn add_element(&mut self, row: N, location: Location) -> bool {
142 debug!("LivenessValues::add(r={:?}, location={:?})", row, location);
143 let index = self.elements.point_from_location(location);
144 self.points.insert(row, index)
147 /// Adds all the elements in the given bit array into the given
148 /// region. Returns whether any of them are newly added.
149 pub(crate) fn add_elements(&mut self, row: N, locations: &IntervalSet<PointIndex>) -> bool {
150 debug!("LivenessValues::add_elements(row={:?}, locations={:?})", row, locations);
151 self.points.union_row(row, locations)
154 /// Adds all the control-flow points to the values for `r`.
155 pub(crate) fn add_all_points(&mut self, row: N) {
156 self.points.insert_all_into_row(row);
159 /// Returns `true` if the region `r` contains the given element.
160 pub(crate) fn contains(&self, row: N, location: Location) -> bool {
161 let index = self.elements.point_from_location(location);
162 self.points.row(row).map_or(false, |r| r.contains(index))
165 /// Returns an iterator of all the elements contained by the region `r`
166 pub(crate) fn get_elements(&self, row: N) -> impl Iterator<Item = Location> + '_ {
170 .flat_map(|set| set.iter())
171 .take_while(move |&p| self.elements.point_in_range(p))
172 .map(move |p| self.elements.to_location(p))
175 /// Returns a "pretty" string value of the region. Meant for debugging.
176 pub(crate) fn region_value_str(&self, r: N) -> String {
177 region_value_str(self.get_elements(r).map(RegionElement::Location))
181 /// Maps from `ty::PlaceholderRegion` values that are used in the rest of
182 /// rustc to the internal `PlaceholderIndex` values that are used in
185 pub(crate) struct PlaceholderIndices {
186 indices: FxIndexSet<ty::PlaceholderRegion>,
189 impl PlaceholderIndices {
190 pub(crate) fn insert(&mut self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
191 let (index, _) = self.indices.insert_full(placeholder);
195 pub(crate) fn lookup_index(&self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
196 self.indices.get_index_of(&placeholder).unwrap().into()
199 pub(crate) fn lookup_placeholder(
201 placeholder: PlaceholderIndex,
202 ) -> ty::PlaceholderRegion {
203 self.indices[placeholder.index()]
206 pub(crate) fn len(&self) -> usize {
211 /// Stores the full values for a set of regions (in contrast to
212 /// `LivenessValues`, which only stores those points in the where a
213 /// region is live). The full value for a region may contain points in
214 /// the CFG, but also free regions as well as bound universe
220 /// fn foo(x: &'a u32) -> &'a u32 {
221 /// let y: &'0 u32 = x; // let's call this `'0`
226 /// Here, the variable `'0` would contain the free region `'a`,
227 /// because (since it is returned) it must live for at least `'a`. But
228 /// it would also contain various points from within the function.
230 pub(crate) struct RegionValues<N: Idx> {
231 elements: Rc<RegionValueElements>,
232 placeholder_indices: Rc<PlaceholderIndices>,
233 points: SparseIntervalMatrix<N, PointIndex>,
234 free_regions: SparseBitMatrix<N, RegionVid>,
236 /// Placeholders represent bound regions -- so something like `'a`
237 /// in for<'a> fn(&'a u32)`.
238 placeholders: SparseBitMatrix<N, PlaceholderIndex>,
241 impl<N: Idx> RegionValues<N> {
242 /// Creates a new set of "region values" that tracks causal information.
243 /// Each of the regions in num_region_variables will be initialized with an
244 /// empty set of points and no causal information.
246 elements: &Rc<RegionValueElements>,
247 num_universal_regions: usize,
248 placeholder_indices: &Rc<PlaceholderIndices>,
250 let num_placeholders = placeholder_indices.len();
252 elements: elements.clone(),
253 points: SparseIntervalMatrix::new(elements.num_points),
254 placeholder_indices: placeholder_indices.clone(),
255 free_regions: SparseBitMatrix::new(num_universal_regions),
256 placeholders: SparseBitMatrix::new(num_placeholders),
260 /// Adds the given element to the value for the given region. Returns whether
261 /// the element is newly added (i.e., was not already present).
262 pub(crate) fn add_element(&mut self, r: N, elem: impl ToElementIndex) -> bool {
263 debug!("add(r={:?}, elem={:?})", r, elem);
264 elem.add_to_row(self, r)
267 /// Adds all the control-flow points to the values for `r`.
268 pub(crate) fn add_all_points(&mut self, r: N) {
269 self.points.insert_all_into_row(r);
272 /// Adds all elements in `r_from` to `r_to` (because e.g., `r_to:
274 pub(crate) fn add_region(&mut self, r_to: N, r_from: N) -> bool {
275 self.points.union_rows(r_from, r_to)
276 | self.free_regions.union_rows(r_from, r_to)
277 | self.placeholders.union_rows(r_from, r_to)
280 /// Returns `true` if the region `r` contains the given element.
281 pub(crate) fn contains(&self, r: N, elem: impl ToElementIndex) -> bool {
282 elem.contained_in_row(self, r)
285 /// `self[to] |= values[from]`, essentially: that is, take all the
286 /// elements for the region `from` from `values` and add them to
287 /// the region `to` in `self`.
288 pub(crate) fn merge_liveness<M: Idx>(&mut self, to: N, from: M, values: &LivenessValues<M>) {
289 if let Some(set) = values.points.row(from) {
290 self.points.union_row(to, set);
294 /// Returns `true` if `sup_region` contains all the CFG points that
295 /// `sub_region` contains. Ignores universal regions.
296 pub(crate) fn contains_points(&self, sup_region: N, sub_region: N) -> bool {
297 if let Some(sub_row) = self.points.row(sub_region) {
298 if let Some(sup_row) = self.points.row(sup_region) {
299 sup_row.superset(sub_row)
301 // sup row is empty, so sub row must be empty
305 // sub row is empty, always true
310 /// Returns the locations contained within a given region `r`.
311 pub(crate) fn locations_outlived_by<'a>(&'a self, r: N) -> impl Iterator<Item = Location> + 'a {
312 self.points.row(r).into_iter().flat_map(move |set| {
314 .take_while(move |&p| self.elements.point_in_range(p))
315 .map(move |p| self.elements.to_location(p))
319 /// Returns just the universal regions that are contained in a given region's value.
320 pub(crate) fn universal_regions_outlived_by<'a>(
323 ) -> impl Iterator<Item = RegionVid> + 'a {
324 self.free_regions.row(r).into_iter().flat_map(|set| set.iter())
327 /// Returns all the elements contained in a given region's value.
328 pub(crate) fn placeholders_contained_in<'a>(
331 ) -> impl Iterator<Item = ty::PlaceholderRegion> + 'a {
335 .flat_map(|set| set.iter())
336 .map(move |p| self.placeholder_indices.lookup_placeholder(p))
339 /// Returns all the elements contained in a given region's value.
340 pub(crate) fn elements_contained_in<'a>(
343 ) -> impl Iterator<Item = RegionElement> + 'a {
344 let points_iter = self.locations_outlived_by(r).map(RegionElement::Location);
346 let free_regions_iter =
347 self.universal_regions_outlived_by(r).map(RegionElement::RootUniversalRegion);
349 let placeholder_universes_iter =
350 self.placeholders_contained_in(r).map(RegionElement::PlaceholderRegion);
352 points_iter.chain(free_regions_iter).chain(placeholder_universes_iter)
355 /// Returns a "pretty" string value of the region. Meant for debugging.
356 pub(crate) fn region_value_str(&self, r: N) -> String {
357 region_value_str(self.elements_contained_in(r))
361 pub(crate) trait ToElementIndex: Debug + Copy {
362 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool;
364 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool;
367 impl ToElementIndex for Location {
368 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
369 let index = values.elements.point_from_location(self);
370 values.points.insert(row, index)
373 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
374 let index = values.elements.point_from_location(self);
375 values.points.contains(row, index)
379 impl ToElementIndex for RegionVid {
380 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
381 values.free_regions.insert(row, self)
384 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
385 values.free_regions.contains(row, self)
389 impl ToElementIndex for ty::PlaceholderRegion {
390 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
391 let index = values.placeholder_indices.lookup_index(self);
392 values.placeholders.insert(row, index)
395 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
396 let index = values.placeholder_indices.lookup_index(self);
397 values.placeholders.contains(row, index)
401 pub(crate) fn location_set_str(
402 elements: &RegionValueElements,
403 points: impl IntoIterator<Item = PointIndex>,
408 .take_while(|&p| elements.point_in_range(p))
409 .map(|p| elements.to_location(p))
410 .map(RegionElement::Location),
414 fn region_value_str(elements: impl IntoIterator<Item = RegionElement>) -> String {
415 let mut result = String::new();
418 // Set to Some(l1, l2) when we have observed all the locations
419 // from l1..=l2 (inclusive) but not yet printed them. This
420 // gets extended if we then see l3 where l3 is the successor
422 let mut open_location: Option<(Location, Location)> = None;
425 let mut push_sep = |s: &mut String| {
430 for element in elements {
432 RegionElement::Location(l) => {
433 if let Some((location1, location2)) = open_location {
434 if location2.block == l.block
435 && location2.statement_index == l.statement_index - 1
437 open_location = Some((location1, l));
441 push_sep(&mut result);
442 push_location_range(&mut result, location1, location2);
445 open_location = Some((l, l));
448 RegionElement::RootUniversalRegion(fr) => {
449 if let Some((location1, location2)) = open_location {
450 push_sep(&mut result);
451 push_location_range(&mut result, location1, location2);
452 open_location = None;
455 push_sep(&mut result);
456 result.push_str(&format!("{:?}", fr));
459 RegionElement::PlaceholderRegion(placeholder) => {
460 if let Some((location1, location2)) = open_location {
461 push_sep(&mut result);
462 push_location_range(&mut result, location1, location2);
463 open_location = None;
466 push_sep(&mut result);
467 result.push_str(&format!("{:?}", placeholder));
472 if let Some((location1, location2)) = open_location {
473 push_sep(&mut result);
474 push_location_range(&mut result, location1, location2);
481 fn push_location_range(str: &mut String, location1: Location, location2: Location) {
482 if location1 == location2 {
483 str.push_str(&format!("{:?}", location1));
485 assert_eq!(location1.block, location2.block);
486 str.push_str(&format!(
488 location1.block, location1.statement_index, location2.statement_index