1 use rustc_data_structures::fx::FxHashMap;
2 use rustc_index::bit_set::{HybridBitSet, SparseBitMatrix};
3 use rustc_index::vec::Idx;
4 use rustc_index::vec::IndexVec;
5 use rustc_middle::mir::{BasicBlock, Body, Location, ReadOnlyBodyAndCache};
6 use rustc_middle::ty::{self, RegionVid};
10 /// Maps between a `Location` and a `PointIndex` (and vice versa).
11 crate struct RegionValueElements {
12 /// For each basic block, how many points are contained within?
13 statements_before_block: IndexVec<BasicBlock, usize>,
15 /// Map backward from each point to the basic block that it
17 basic_blocks: IndexVec<PointIndex, BasicBlock>,
22 impl RegionValueElements {
23 crate fn new(body: &Body<'_>) -> Self {
24 let mut num_points = 0;
25 let statements_before_block: IndexVec<BasicBlock, usize> = body
30 num_points += block_data.statements.len() + 1;
34 debug!("RegionValueElements: statements_before_block={:#?}", statements_before_block);
35 debug!("RegionValueElements: num_points={:#?}", num_points);
37 let mut basic_blocks = IndexVec::with_capacity(num_points);
38 for (bb, bb_data) in body.basic_blocks().iter_enumerated() {
39 basic_blocks.extend((0..=bb_data.statements.len()).map(|_| bb));
42 Self { statements_before_block, basic_blocks, num_points }
45 /// Total number of point indices
46 crate fn num_points(&self) -> usize {
50 /// Converts a `Location` into a `PointIndex`. O(1).
51 crate fn point_from_location(&self, location: Location) -> PointIndex {
52 let Location { block, statement_index } = location;
53 let start_index = self.statements_before_block[block];
54 PointIndex::new(start_index + statement_index)
57 /// Converts a `Location` into a `PointIndex`. O(1).
58 crate fn entry_point(&self, block: BasicBlock) -> PointIndex {
59 let start_index = self.statements_before_block[block];
60 PointIndex::new(start_index)
63 /// Converts a `PointIndex` back to a location. O(1).
64 crate fn to_location(&self, index: PointIndex) -> Location {
65 assert!(index.index() < self.num_points);
66 let block = self.basic_blocks[index];
67 let start_index = self.statements_before_block[block];
68 let statement_index = index.index() - start_index;
69 Location { block, statement_index }
72 /// Sometimes we get point-indices back from bitsets that may be
73 /// out of range (because they round up to the nearest 2^N number
74 /// of bits). Use this function to filter such points out if you
76 crate fn point_in_range(&self, index: PointIndex) -> bool {
77 index.index() < self.num_points
80 /// Pushes all predecessors of `index` onto `stack`.
81 crate fn push_predecessors(
83 body: ReadOnlyBodyAndCache<'_, '_>,
85 stack: &mut Vec<PointIndex>,
87 let Location { block, statement_index } = self.to_location(index);
88 if statement_index == 0 {
89 // If this is a basic block head, then the predecessors are
90 // the terminators of other basic blocks
92 body.predecessors_for(block)
94 .map(|&pred_bb| body.terminator_loc(pred_bb))
95 .map(|pred_loc| self.point_from_location(pred_loc)),
98 // Otherwise, the pred is just the previous statement
99 stack.push(PointIndex::new(index.index() - 1));
104 rustc_index::newtype_index! {
105 /// A single integer representing a `Location` in the MIR control-flow
106 /// graph. Constructed efficiently from `RegionValueElements`.
107 pub struct PointIndex { DEBUG_FORMAT = "PointIndex({})" }
110 rustc_index::newtype_index! {
111 /// A single integer representing a `ty::Placeholder`.
112 pub struct PlaceholderIndex { DEBUG_FORMAT = "PlaceholderIndex({})" }
115 /// An individual element in a region value -- the value of a
116 /// particular region variable consists of a set of these elements.
117 #[derive(Debug, Clone)]
118 crate enum RegionElement {
119 /// A point in the control-flow graph.
122 /// A universally quantified region from the root universe (e.g.,
123 /// a lifetime parameter).
124 RootUniversalRegion(RegionVid),
126 /// A placeholder (e.g., instantiated from a `for<'a> fn(&'a u32)`
128 PlaceholderRegion(ty::PlaceholderRegion),
131 /// When we initially compute liveness, we use a bit matrix storing
132 /// points for each region-vid.
133 crate struct LivenessValues<N: Idx> {
134 elements: Rc<RegionValueElements>,
135 points: SparseBitMatrix<N, PointIndex>,
138 impl<N: Idx> LivenessValues<N> {
139 /// Creates a new set of "region values" that tracks causal information.
140 /// Each of the regions in num_region_variables will be initialized with an
141 /// empty set of points and no causal information.
142 crate fn new(elements: Rc<RegionValueElements>) -> Self {
143 Self { points: SparseBitMatrix::new(elements.num_points), elements }
146 /// Iterate through each region that has a value in this set.
147 crate fn rows(&self) -> impl Iterator<Item = N> {
151 /// Adds the given element to the value for the given region. Returns whether
152 /// the element is newly added (i.e., was not already present).
153 crate fn add_element(&mut self, row: N, location: Location) -> bool {
154 debug!("LivenessValues::add(r={:?}, location={:?})", row, location);
155 let index = self.elements.point_from_location(location);
156 self.points.insert(row, index)
159 /// Adds all the elements in the given bit array into the given
160 /// region. Returns whether any of them are newly added.
161 crate fn add_elements(&mut self, row: N, locations: &HybridBitSet<PointIndex>) -> bool {
162 debug!("LivenessValues::add_elements(row={:?}, locations={:?})", row, locations);
163 self.points.union_into_row(row, locations)
166 /// Adds all the control-flow points to the values for `r`.
167 crate fn add_all_points(&mut self, row: N) {
168 self.points.insert_all_into_row(row);
171 /// Returns `true` if the region `r` contains the given element.
172 crate fn contains(&self, row: N, location: Location) -> bool {
173 let index = self.elements.point_from_location(location);
174 self.points.contains(row, index)
177 /// Returns a "pretty" string value of the region. Meant for debugging.
178 crate fn region_value_str(&self, r: N) -> String {
183 .flat_map(|set| set.iter())
184 .take_while(|&p| self.elements.point_in_range(p))
185 .map(|p| self.elements.to_location(p))
186 .map(RegionElement::Location),
191 /// Maps from `ty::PlaceholderRegion` values that are used in the rest of
192 /// rustc to the internal `PlaceholderIndex` values that are used in
195 crate struct PlaceholderIndices {
196 to_index: FxHashMap<ty::PlaceholderRegion, PlaceholderIndex>,
197 from_index: IndexVec<PlaceholderIndex, ty::PlaceholderRegion>,
200 impl PlaceholderIndices {
201 crate fn insert(&mut self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
202 let PlaceholderIndices { to_index, from_index } = self;
203 *to_index.entry(placeholder).or_insert_with(|| from_index.push(placeholder))
206 crate fn lookup_index(&self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
207 self.to_index[&placeholder]
210 crate fn lookup_placeholder(&self, placeholder: PlaceholderIndex) -> ty::PlaceholderRegion {
211 self.from_index[placeholder]
214 crate fn len(&self) -> usize {
215 self.from_index.len()
219 /// Stores the full values for a set of regions (in contrast to
220 /// `LivenessValues`, which only stores those points in the where a
221 /// region is live). The full value for a region may contain points in
222 /// the CFG, but also free regions as well as bound universe
228 /// fn foo(x: &'a u32) -> &'a u32 {
229 /// let y: &'0 u32 = x; // let's call this `'0`
234 /// Here, the variable `'0` would contain the free region `'a`,
235 /// because (since it is returned) it must live for at least `'a`. But
236 /// it would also contain various points from within the function.
238 crate struct RegionValues<N: Idx> {
239 elements: Rc<RegionValueElements>,
240 placeholder_indices: Rc<PlaceholderIndices>,
241 points: SparseBitMatrix<N, PointIndex>,
242 free_regions: SparseBitMatrix<N, RegionVid>,
244 /// Placeholders represent bound regions -- so something like `'a`
245 /// in for<'a> fn(&'a u32)`.
246 placeholders: SparseBitMatrix<N, PlaceholderIndex>,
249 impl<N: Idx> RegionValues<N> {
250 /// Creates a new set of "region values" that tracks causal information.
251 /// Each of the regions in num_region_variables will be initialized with an
252 /// empty set of points and no causal information.
254 elements: &Rc<RegionValueElements>,
255 num_universal_regions: usize,
256 placeholder_indices: &Rc<PlaceholderIndices>,
258 let num_placeholders = placeholder_indices.len();
260 elements: elements.clone(),
261 points: SparseBitMatrix::new(elements.num_points),
262 placeholder_indices: placeholder_indices.clone(),
263 free_regions: SparseBitMatrix::new(num_universal_regions),
264 placeholders: SparseBitMatrix::new(num_placeholders),
268 /// Adds the given element to the value for the given region. Returns whether
269 /// the element is newly added (i.e., was not already present).
270 crate fn add_element(&mut self, r: N, elem: impl ToElementIndex) -> bool {
271 debug!("add(r={:?}, elem={:?})", r, elem);
272 elem.add_to_row(self, r)
275 /// Adds all the control-flow points to the values for `r`.
276 crate fn add_all_points(&mut self, r: N) {
277 self.points.insert_all_into_row(r);
280 /// Adds all elements in `r_from` to `r_to` (because e.g., `r_to:
282 crate fn add_region(&mut self, r_to: N, r_from: N) -> bool {
283 self.points.union_rows(r_from, r_to)
284 | self.free_regions.union_rows(r_from, r_to)
285 | self.placeholders.union_rows(r_from, r_to)
288 /// Returns `true` if the region `r` contains the given element.
289 crate fn contains(&self, r: N, elem: impl ToElementIndex) -> bool {
290 elem.contained_in_row(self, r)
293 /// `self[to] |= values[from]`, essentially: that is, take all the
294 /// elements for the region `from` from `values` and add them to
295 /// the region `to` in `self`.
296 crate fn merge_liveness<M: Idx>(&mut self, to: N, from: M, values: &LivenessValues<M>) {
297 if let Some(set) = values.points.row(from) {
298 self.points.union_into_row(to, set);
302 /// Returns `true` if `sup_region` contains all the CFG points that
303 /// `sub_region` contains. Ignores universal regions.
304 crate fn contains_points(&self, sup_region: N, sub_region: N) -> bool {
305 if let Some(sub_row) = self.points.row(sub_region) {
306 if let Some(sup_row) = self.points.row(sup_region) {
307 sup_row.superset(sub_row)
309 // sup row is empty, so sub row must be empty
313 // sub row is empty, always true
318 /// Returns the locations contained within a given region `r`.
319 crate fn locations_outlived_by<'a>(&'a self, r: N) -> impl Iterator<Item = Location> + 'a {
320 self.points.row(r).into_iter().flat_map(move |set| {
322 .take_while(move |&p| self.elements.point_in_range(p))
323 .map(move |p| self.elements.to_location(p))
327 /// Returns just the universal regions that are contained in a given region's value.
328 crate fn universal_regions_outlived_by<'a>(
331 ) -> impl Iterator<Item = RegionVid> + 'a {
332 self.free_regions.row(r).into_iter().flat_map(|set| set.iter())
335 /// Returns all the elements contained in a given region's value.
336 crate fn placeholders_contained_in<'a>(
339 ) -> impl Iterator<Item = ty::PlaceholderRegion> + 'a {
343 .flat_map(|set| set.iter())
344 .map(move |p| self.placeholder_indices.lookup_placeholder(p))
347 /// Returns all the elements contained in a given region's value.
348 crate fn elements_contained_in<'a>(&'a self, r: N) -> impl Iterator<Item = RegionElement> + 'a {
349 let points_iter = self.locations_outlived_by(r).map(RegionElement::Location);
351 let free_regions_iter =
352 self.universal_regions_outlived_by(r).map(RegionElement::RootUniversalRegion);
354 let placeholder_universes_iter =
355 self.placeholders_contained_in(r).map(RegionElement::PlaceholderRegion);
357 points_iter.chain(free_regions_iter).chain(placeholder_universes_iter)
360 /// Returns a "pretty" string value of the region. Meant for debugging.
361 crate fn region_value_str(&self, r: N) -> String {
362 region_value_str(self.elements_contained_in(r))
366 crate trait ToElementIndex: Debug + Copy {
367 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool;
369 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool;
372 impl ToElementIndex for Location {
373 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
374 let index = values.elements.point_from_location(self);
375 values.points.insert(row, index)
378 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
379 let index = values.elements.point_from_location(self);
380 values.points.contains(row, index)
384 impl ToElementIndex for RegionVid {
385 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
386 values.free_regions.insert(row, self)
389 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
390 values.free_regions.contains(row, self)
394 impl ToElementIndex for ty::PlaceholderRegion {
395 fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
396 let index = values.placeholder_indices.lookup_index(self);
397 values.placeholders.insert(row, index)
400 fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
401 let index = values.placeholder_indices.lookup_index(self);
402 values.placeholders.contains(row, index)
406 crate fn location_set_str(
407 elements: &RegionValueElements,
408 points: impl IntoIterator<Item = PointIndex>,
413 .take_while(|&p| elements.point_in_range(p))
414 .map(|p| elements.to_location(p))
415 .map(RegionElement::Location),
419 fn region_value_str(elements: impl IntoIterator<Item = RegionElement>) -> String {
420 let mut result = String::new();
421 result.push_str("{");
423 // Set to Some(l1, l2) when we have observed all the locations
424 // from l1..=l2 (inclusive) but not yet printed them. This
425 // gets extended if we then see l3 where l3 is the successor
427 let mut open_location: Option<(Location, Location)> = None;
430 let mut push_sep = |s: &mut String| {
435 for element in elements {
437 RegionElement::Location(l) => {
438 if let Some((location1, location2)) = open_location {
439 if location2.block == l.block
440 && location2.statement_index == l.statement_index - 1
442 open_location = Some((location1, l));
446 push_sep(&mut result);
447 push_location_range(&mut result, location1, location2);
450 open_location = Some((l, l));
453 RegionElement::RootUniversalRegion(fr) => {
454 if let Some((location1, location2)) = open_location {
455 push_sep(&mut result);
456 push_location_range(&mut result, location1, location2);
457 open_location = None;
460 push_sep(&mut result);
461 result.push_str(&format!("{:?}", fr));
464 RegionElement::PlaceholderRegion(placeholder) => {
465 if let Some((location1, location2)) = open_location {
466 push_sep(&mut result);
467 push_location_range(&mut result, location1, location2);
468 open_location = None;
471 push_sep(&mut result);
472 result.push_str(&format!("{:?}", placeholder));
477 if let Some((location1, location2)) = open_location {
478 push_sep(&mut result);
479 push_location_range(&mut result, location1, location2);
482 result.push_str("}");
486 fn push_location_range(str: &mut String, location1: Location, location2: Location) {
487 if location1 == location2 {
488 str.push_str(&format!("{:?}", location1));
490 assert_eq!(location1.block, location2.block);
491 str.push_str(&format!(
493 location1.block, location1.statement_index, location2.statement_index