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 pub struct PointIndex { DEBUG_FORMAT = "PointIndex({})" }
96 rustc_index::newtype_index! {
97 /// A single integer representing a `ty::Placeholder`.
98 pub struct PlaceholderIndex { DEBUG_FORMAT = "PlaceholderIndex({})" }
101 /// An individual element in a region value -- the value of a
102 /// particular region variable consists of a set of these elements.
103 #[derive(Debug, Clone)]
104 pub(crate) enum RegionElement {
105 /// A point in the control-flow graph.
108 /// A universally quantified region from the root universe (e.g.,
109 /// a lifetime parameter).
110 RootUniversalRegion(RegionVid),
112 /// A placeholder (e.g., instantiated from a `for<'a> fn(&'a u32)`
114 PlaceholderRegion(ty::PlaceholderRegion),
117 /// When we initially compute liveness, we use an interval matrix storing
118 /// liveness ranges for each region-vid.
119 pub(crate) struct LivenessValues<N: Idx> {
120 elements: Rc<RegionValueElements>,
121 points: SparseIntervalMatrix<N, PointIndex>,
124 impl<N: Idx> LivenessValues<N> {
125 /// Creates a new set of "region values" that tracks causal information.
126 /// Each of the regions in num_region_variables will be initialized with an
127 /// empty set of points and no causal information.
128 pub(crate) fn new(elements: Rc<RegionValueElements>) -> Self {
129 Self { points: SparseIntervalMatrix::new(elements.num_points), elements }
132 /// Iterate through each region that has a value in this set.
133 pub(crate) fn rows(&self) -> impl Iterator<Item = N> {
137 /// Adds the given element to the value for the given region. Returns whether
138 /// the element is newly added (i.e., was not already present).
139 pub(crate) fn add_element(&mut self, row: N, location: Location) -> bool {
140 debug!("LivenessValues::add(r={:?}, location={:?})", row, location);
141 let index = self.elements.point_from_location(location);
142 self.points.insert(row, index)
145 /// Adds all the elements in the given bit array into the given
146 /// region. Returns whether any of them are newly added.
147 pub(crate) fn add_elements(&mut self, row: N, locations: &IntervalSet<PointIndex>) -> bool {
148 debug!("LivenessValues::add_elements(row={:?}, locations={:?})", row, locations);
149 self.points.union_row(row, locations)
152 /// Adds all the control-flow points to the values for `r`.
153 pub(crate) fn add_all_points(&mut self, row: N) {
154 self.points.insert_all_into_row(row);
157 /// Returns `true` if the region `r` contains the given element.
158 pub(crate) fn contains(&self, row: N, location: Location) -> bool {
159 let index = self.elements.point_from_location(location);
160 self.points.row(row).map_or(false, |r| r.contains(index))
163 /// Returns an iterator of all the elements contained by the region `r`
164 pub(crate) fn get_elements(&self, row: N) -> impl Iterator<Item = Location> + '_ {
168 .flat_map(|set| set.iter())
169 .take_while(move |&p| self.elements.point_in_range(p))
170 .map(move |p| self.elements.to_location(p))
173 /// Returns a "pretty" string value of the region. Meant for debugging.
174 pub(crate) fn region_value_str(&self, r: N) -> String {
175 region_value_str(self.get_elements(r).map(RegionElement::Location))
179 /// Maps from `ty::PlaceholderRegion` values that are used in the rest of
180 /// rustc to the internal `PlaceholderIndex` values that are used in
183 pub(crate) struct PlaceholderIndices {
184 indices: FxIndexSet<ty::PlaceholderRegion>,
187 impl PlaceholderIndices {
188 pub(crate) fn insert(&mut self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
189 let (index, _) = self.indices.insert_full(placeholder);
193 pub(crate) fn lookup_index(&self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
194 self.indices.get_index_of(&placeholder).unwrap().into()
197 pub(crate) fn lookup_placeholder(
199 placeholder: PlaceholderIndex,
200 ) -> ty::PlaceholderRegion {
201 self.indices[placeholder.index()]
204 pub(crate) fn len(&self) -> usize {
209 /// Stores the full values for a set of regions (in contrast to
210 /// `LivenessValues`, which only stores those points in the where a
211 /// region is live). The full value for a region may contain points in
212 /// the CFG, but also free regions as well as bound universe
218 /// fn foo(x: &'a u32) -> &'a u32 {
219 /// let y: &'0 u32 = x; // let's call this `'0`
224 /// Here, the variable `'0` would contain the free region `'a`,
225 /// because (since it is returned) it must live for at least `'a`. But
226 /// it would also contain various points from within the function.
228 pub(crate) struct RegionValues<N: Idx> {
229 elements: Rc<RegionValueElements>,
230 placeholder_indices: Rc<PlaceholderIndices>,
231 points: SparseIntervalMatrix<N, PointIndex>,
232 free_regions: SparseBitMatrix<N, RegionVid>,
234 /// Placeholders represent bound regions -- so something like `'a`
235 /// in for<'a> fn(&'a u32)`.
236 placeholders: SparseBitMatrix<N, PlaceholderIndex>,
239 impl<N: Idx> RegionValues<N> {
240 /// Creates a new set of "region values" that tracks causal information.
241 /// Each of the regions in num_region_variables will be initialized with an
242 /// empty set of points and no causal information.
244 elements: &Rc<RegionValueElements>,
245 num_universal_regions: usize,
246 placeholder_indices: &Rc<PlaceholderIndices>,
248 let num_placeholders = placeholder_indices.len();
250 elements: elements.clone(),
251 points: SparseIntervalMatrix::new(elements.num_points),
252 placeholder_indices: placeholder_indices.clone(),
253 free_regions: SparseBitMatrix::new(num_universal_regions),
254 placeholders: SparseBitMatrix::new(num_placeholders),
258 /// Adds the given element to the value for the given region. Returns whether
259 /// the element is newly added (i.e., was not already present).
260 pub(crate) fn add_element(&mut self, r: N, elem: impl ToElementIndex) -> bool {
261 debug!("add(r={:?}, elem={:?})", r, elem);
262 elem.add_to_row(self, r)
265 /// Adds all the control-flow points to the values for `r`.
266 pub(crate) fn add_all_points(&mut self, r: N) {
267 self.points.insert_all_into_row(r);
270 /// Adds all elements in `r_from` to `r_to` (because e.g., `r_to:
272 pub(crate) fn add_region(&mut self, r_to: N, r_from: N) -> bool {
273 self.points.union_rows(r_from, r_to)
274 | self.free_regions.union_rows(r_from, r_to)
275 | self.placeholders.union_rows(r_from, r_to)
278 /// Returns `true` if the region `r` contains the given element.
279 pub(crate) fn contains(&self, r: N, elem: impl ToElementIndex) -> bool {
280 elem.contained_in_row(self, r)
283 /// `self[to] |= values[from]`, essentially: that is, take all the
284 /// elements for the region `from` from `values` and add them to
285 /// the region `to` in `self`.
286 pub(crate) fn merge_liveness<M: Idx>(&mut self, to: N, from: M, values: &LivenessValues<M>) {
287 if let Some(set) = values.points.row(from) {
288 self.points.union_row(to, set);
292 /// Returns `true` if `sup_region` contains all the CFG points that
293 /// `sub_region` contains. Ignores universal regions.
294 pub(crate) fn contains_points(&self, sup_region: N, sub_region: N) -> bool {
295 if let Some(sub_row) = self.points.row(sub_region) {
296 if let Some(sup_row) = self.points.row(sup_region) {
297 sup_row.superset(sub_row)
299 // sup row is empty, so sub row must be empty
303 // sub row is empty, always true
308 /// Returns the locations contained within a given region `r`.
309 pub(crate) fn locations_outlived_by<'a>(&'a self, r: N) -> impl Iterator<Item = Location> + 'a {
310 self.points.row(r).into_iter().flat_map(move |set| {
312 .take_while(move |&p| self.elements.point_in_range(p))
313 .map(move |p| self.elements.to_location(p))
317 /// Returns just the universal regions that are contained in a given region's value.
318 pub(crate) fn universal_regions_outlived_by<'a>(
321 ) -> impl Iterator<Item = RegionVid> + 'a {
322 self.free_regions.row(r).into_iter().flat_map(|set| set.iter())
325 /// Returns all the elements contained in a given region's value.
326 pub(crate) fn placeholders_contained_in<'a>(
329 ) -> impl Iterator<Item = ty::PlaceholderRegion> + 'a {
333 .flat_map(|set| set.iter())
334 .map(move |p| self.placeholder_indices.lookup_placeholder(p))
337 /// Returns all the elements contained in a given region's value.
338 pub(crate) fn elements_contained_in<'a>(
341 ) -> impl Iterator<Item = RegionElement> + 'a {
342 let points_iter = self.locations_outlived_by(r).map(RegionElement::Location);
344 let free_regions_iter =
345 self.universal_regions_outlived_by(r).map(RegionElement::RootUniversalRegion);
347 let placeholder_universes_iter =
348 self.placeholders_contained_in(r).map(RegionElement::PlaceholderRegion);
350 points_iter.chain(free_regions_iter).chain(placeholder_universes_iter)
353 /// Returns a "pretty" string value of the region. Meant for debugging.
354 pub(crate) fn region_value_str(&self, r: N) -> String {
355 region_value_str(self.elements_contained_in(r))
359 pub(crate) trait ToElementIndex: Debug + Copy {
360 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool;
362 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool;
365 impl ToElementIndex for Location {
366 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
367 let index = values.elements.point_from_location(self);
368 values.points.insert(row, index)
371 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
372 let index = values.elements.point_from_location(self);
373 values.points.contains(row, index)
377 impl ToElementIndex for RegionVid {
378 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
379 values.free_regions.insert(row, self)
382 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
383 values.free_regions.contains(row, self)
387 impl ToElementIndex for ty::PlaceholderRegion {
388 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
389 let index = values.placeholder_indices.lookup_index(self);
390 values.placeholders.insert(row, index)
393 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
394 let index = values.placeholder_indices.lookup_index(self);
395 values.placeholders.contains(row, index)
399 pub(crate) fn location_set_str(
400 elements: &RegionValueElements,
401 points: impl IntoIterator<Item = PointIndex>,
406 .take_while(|&p| elements.point_in_range(p))
407 .map(|p| elements.to_location(p))
408 .map(RegionElement::Location),
412 fn region_value_str(elements: impl IntoIterator<Item = RegionElement>) -> String {
413 let mut result = String::new();
416 // Set to Some(l1, l2) when we have observed all the locations
417 // from l1..=l2 (inclusive) but not yet printed them. This
418 // gets extended if we then see l3 where l3 is the successor
420 let mut open_location: Option<(Location, Location)> = None;
423 let mut push_sep = |s: &mut String| {
428 for element in elements {
430 RegionElement::Location(l) => {
431 if let Some((location1, location2)) = open_location {
432 if location2.block == l.block
433 && location2.statement_index == l.statement_index - 1
435 open_location = Some((location1, l));
439 push_sep(&mut result);
440 push_location_range(&mut result, location1, location2);
443 open_location = Some((l, l));
446 RegionElement::RootUniversalRegion(fr) => {
447 if let Some((location1, location2)) = open_location {
448 push_sep(&mut result);
449 push_location_range(&mut result, location1, location2);
450 open_location = None;
453 push_sep(&mut result);
454 result.push_str(&format!("{:?}", fr));
457 RegionElement::PlaceholderRegion(placeholder) => {
458 if let Some((location1, location2)) = open_location {
459 push_sep(&mut result);
460 push_location_range(&mut result, location1, location2);
461 open_location = None;
464 push_sep(&mut result);
465 result.push_str(&format!("{:?}", placeholder));
470 if let Some((location1, location2)) = open_location {
471 push_sep(&mut result);
472 push_location_range(&mut result, location1, location2);
479 fn push_location_range(str: &mut String, location1: Location, location2: Location) {
480 if location1 == location2 {
481 str.push_str(&format!("{:?}", location1));
483 assert_eq!(location1.block, location2.block);
484 str.push_str(&format!(
486 location1.block, location1.statement_index, location2.statement_index