compiler/rustc_borrowck/src/region_infer/values.rs

   1 use rustc_data_structures::fx::FxIndexSet;
   2 use rustc_index::bit_set::SparseBitMatrix;
   3 use rustc_index::interval::IntervalSet;
   4 use rustc_index::interval::SparseIntervalMatrix;
   5 use rustc_index::vec::Idx;
   6 use rustc_index::vec::IndexVec;
   7 use rustc_middle::mir::{BasicBlock, Body, Location};
   8 use rustc_middle::ty::{self, RegionVid};
   9 use std::fmt::Debug;
  10 use std::rc::Rc;
  11
  12 /// Maps between a `Location` and a `PointIndex` (and vice versa).
  13 pub(crate) struct RegionValueElements {
  14     /// For each basic block, how many points are contained within?
  15     statements_before_block: IndexVec<BasicBlock, usize>,
  16
  17     /// Map backward from each point to the basic block that it
  18     /// belongs to.
  19     basic_blocks: IndexVec<PointIndex, BasicBlock>,
  20
  21     num_points: usize,
  22 }
  23
  24 impl RegionValueElements {
  25     pub(crate) fn new(body: &Body<'_>) -> Self {
  26         let mut num_points = 0;
  27         let statements_before_block: IndexVec<BasicBlock, usize> = body
  28             .basic_blocks
  29             .iter()
  30             .map(|block_data| {
  31                 let v = num_points;
  32                 num_points += block_data.statements.len() + 1;
  33                 v
  34             })
  35             .collect();
  36         debug!("RegionValueElements: statements_before_block={:#?}", statements_before_block);
  37         debug!("RegionValueElements: num_points={:#?}", num_points);
  38
  39         let mut basic_blocks = IndexVec::with_capacity(num_points);
  40         for (bb, bb_data) in body.basic_blocks.iter_enumerated() {
  41             basic_blocks.extend((0..=bb_data.statements.len()).map(|_| bb));
  42         }
  43
  44         Self { statements_before_block, basic_blocks, num_points }
  45     }
  46
  47     /// Total number of point indices
  48     pub(crate) fn num_points(&self) -> usize {
  49         self.num_points
  50     }
  51
  52     /// Converts a `Location` into a `PointIndex`. O(1).
  53     pub(crate) fn point_from_location(&self, location: Location) -> PointIndex {
  54         let Location { block, statement_index } = location;
  55         let start_index = self.statements_before_block[block];
  56         PointIndex::new(start_index + statement_index)
  57     }
  58
  59     /// Converts a `Location` into a `PointIndex`. O(1).
  60     pub(crate) fn entry_point(&self, block: BasicBlock) -> PointIndex {
  61         let start_index = self.statements_before_block[block];
  62         PointIndex::new(start_index)
  63     }
  64
  65     /// Return the PointIndex for the block start of this index.
  66     pub(crate) fn to_block_start(&self, index: PointIndex) -> PointIndex {
  67         PointIndex::new(self.statements_before_block[self.basic_blocks[index]])
  68     }
  69
  70     /// Converts a `PointIndex` back to a location. O(1).
  71     pub(crate) fn to_location(&self, index: PointIndex) -> Location {
  72         assert!(index.index() < self.num_points);
  73         let block = self.basic_blocks[index];
  74         let start_index = self.statements_before_block[block];
  75         let statement_index = index.index() - start_index;
  76         Location { block, statement_index }
  77     }
  78
  79     /// Sometimes we get point-indices back from bitsets that may be
  80     /// out of range (because they round up to the nearest 2^N number
  81     /// of bits). Use this function to filter such points out if you
  82     /// like.
  83     pub(crate) fn point_in_range(&self, index: PointIndex) -> bool {
  84         index.index() < self.num_points
  85     }
  86 }
  87
  88 rustc_index::newtype_index! {
  89     /// A single integer representing a `Location` in the MIR control-flow
  90     /// graph. Constructed efficiently from `RegionValueElements`.
  91     pub struct PointIndex { DEBUG_FORMAT = "PointIndex({})" }
  92 }
  93
  94 rustc_index::newtype_index! {
  95     /// A single integer representing a `ty::Placeholder`.
  96     pub struct PlaceholderIndex { DEBUG_FORMAT = "PlaceholderIndex({})" }
  97 }
  98
  99 /// An individual element in a region value -- the value of a
 100 /// particular region variable consists of a set of these elements.
 101 #[derive(Debug, Clone)]
 102 pub(crate) enum RegionElement {
 103     /// A point in the control-flow graph.
 104     Location(Location),
 105
 106     /// A universally quantified region from the root universe (e.g.,
 107     /// a lifetime parameter).
 108     RootUniversalRegion(RegionVid),
 109
 110     /// A placeholder (e.g., instantiated from a `for<'a> fn(&'a u32)`
 111     /// type).
 112     PlaceholderRegion(ty::PlaceholderRegion),
 113 }
 114
 115 /// When we initially compute liveness, we use an interval matrix storing
 116 /// liveness ranges for each region-vid.
 117 pub(crate) struct LivenessValues<N: Idx> {
 118     elements: Rc<RegionValueElements>,
 119     points: SparseIntervalMatrix<N, PointIndex>,
 120 }
 121
 122 impl<N: Idx> LivenessValues<N> {
 123     /// Creates a new set of "region values" that tracks causal information.
 124     /// Each of the regions in num_region_variables will be initialized with an
 125     /// empty set of points and no causal information.
 126     pub(crate) fn new(elements: Rc<RegionValueElements>) -> Self {
 127         Self { points: SparseIntervalMatrix::new(elements.num_points), elements }
 128     }
 129
 130     /// Iterate through each region that has a value in this set.
 131     pub(crate) fn rows(&self) -> impl Iterator<Item = N> {
 132         self.points.rows()
 133     }
 134
 135     /// Adds the given element to the value for the given region. Returns whether
 136     /// the element is newly added (i.e., was not already present).
 137     pub(crate) fn add_element(&mut self, row: N, location: Location) -> bool {
 138         debug!("LivenessValues::add(r={:?}, location={:?})", row, location);
 139         let index = self.elements.point_from_location(location);
 140         self.points.insert(row, index)
 141     }
 142
 143     /// Adds all the elements in the given bit array into the given
 144     /// region. Returns whether any of them are newly added.
 145     pub(crate) fn add_elements(&mut self, row: N, locations: &IntervalSet<PointIndex>) -> bool {
 146         debug!("LivenessValues::add_elements(row={:?}, locations={:?})", row, locations);
 147         self.points.union_row(row, locations)
 148     }
 149
 150     /// Adds all the control-flow points to the values for `r`.
 151     pub(crate) fn add_all_points(&mut self, row: N) {
 152         self.points.insert_all_into_row(row);
 153     }
 154
 155     /// Returns `true` if the region `r` contains the given element.
 156     pub(crate) fn contains(&self, row: N, location: Location) -> bool {
 157         let index = self.elements.point_from_location(location);
 158         self.points.row(row).map_or(false, |r| r.contains(index))
 159     }
 160
 161     /// Returns an iterator of all the elements contained by the region `r`
 162     pub(crate) fn get_elements(&self, row: N) -> impl Iterator<Item = Location> + '_ {
 163         self.points
 164             .row(row)
 165             .into_iter()
 166             .flat_map(|set| set.iter())
 167             .take_while(move |&p| self.elements.point_in_range(p))
 168             .map(move |p| self.elements.to_location(p))
 169     }
 170
 171     /// Returns a "pretty" string value of the region. Meant for debugging.
 172     pub(crate) fn region_value_str(&self, r: N) -> String {
 173         region_value_str(self.get_elements(r).map(RegionElement::Location))
 174     }
 175 }
 176
 177 /// Maps from `ty::PlaceholderRegion` values that are used in the rest of
 178 /// rustc to the internal `PlaceholderIndex` values that are used in
 179 /// NLL.
 180 #[derive(Default)]
 181 pub(crate) struct PlaceholderIndices {
 182     indices: FxIndexSet<ty::PlaceholderRegion>,
 183 }
 184
 185 impl PlaceholderIndices {
 186     pub(crate) fn insert(&mut self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
 187         let (index, _) = self.indices.insert_full(placeholder);
 188         index.into()
 189     }
 190
 191     pub(crate) fn lookup_index(&self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
 192         self.indices.get_index_of(&placeholder).unwrap().into()
 193     }
 194
 195     pub(crate) fn lookup_placeholder(
 196         &self,
 197         placeholder: PlaceholderIndex,
 198     ) -> ty::PlaceholderRegion {
 199         self.indices[placeholder.index()]
 200     }
 201
 202     pub(crate) fn len(&self) -> usize {
 203         self.indices.len()
 204     }
 205 }
 206
 207 /// Stores the full values for a set of regions (in contrast to
 208 /// `LivenessValues`, which only stores those points in the where a
 209 /// region is live). The full value for a region may contain points in
 210 /// the CFG, but also free regions as well as bound universe
 211 /// placeholders.
 212 ///
 213 /// Example:
 214 ///
 215 /// ```text
 216 /// fn foo(x: &'a u32) -> &'a u32 {
 217 ///    let y: &'0 u32 = x; // let's call this `'0`
 218 ///    y
 219 /// }
 220 /// ```
 221 ///
 222 /// Here, the variable `'0` would contain the free region `'a`,
 223 /// because (since it is returned) it must live for at least `'a`. But
 224 /// it would also contain various points from within the function.
 225 #[derive(Clone)]
 226 pub(crate) struct RegionValues<N: Idx> {
 227     elements: Rc<RegionValueElements>,
 228     placeholder_indices: Rc<PlaceholderIndices>,
 229     points: SparseIntervalMatrix<N, PointIndex>,
 230     free_regions: SparseBitMatrix<N, RegionVid>,
 231
 232     /// Placeholders represent bound regions -- so something like `'a`
 233     /// in for<'a> fn(&'a u32)`.
 234     placeholders: SparseBitMatrix<N, PlaceholderIndex>,
 235 }
 236
 237 impl<N: Idx> RegionValues<N> {
 238     /// Creates a new set of "region values" that tracks causal information.
 239     /// Each of the regions in num_region_variables will be initialized with an
 240     /// empty set of points and no causal information.
 241     pub(crate) fn new(
 242         elements: &Rc<RegionValueElements>,
 243         num_universal_regions: usize,
 244         placeholder_indices: &Rc<PlaceholderIndices>,
 245     ) -> Self {
 246         let num_placeholders = placeholder_indices.len();
 247         Self {
 248             elements: elements.clone(),
 249             points: SparseIntervalMatrix::new(elements.num_points),
 250             placeholder_indices: placeholder_indices.clone(),
 251             free_regions: SparseBitMatrix::new(num_universal_regions),
 252             placeholders: SparseBitMatrix::new(num_placeholders),
 253         }
 254     }
 255
 256     /// Adds the given element to the value for the given region. Returns whether
 257     /// the element is newly added (i.e., was not already present).
 258     pub(crate) fn add_element(&mut self, r: N, elem: impl ToElementIndex) -> bool {
 259         debug!("add(r={:?}, elem={:?})", r, elem);
 260         elem.add_to_row(self, r)
 261     }
 262
 263     /// Adds all the control-flow points to the values for `r`.
 264     pub(crate) fn add_all_points(&mut self, r: N) {
 265         self.points.insert_all_into_row(r);
 266     }
 267
 268     /// Adds all elements in `r_from` to `r_to` (because e.g., `r_to:
 269     /// r_from`).
 270     pub(crate) fn add_region(&mut self, r_to: N, r_from: N) -> bool {
 271         self.points.union_rows(r_from, r_to)
 272             | self.free_regions.union_rows(r_from, r_to)
 273             | self.placeholders.union_rows(r_from, r_to)
 274     }
 275
 276     /// Returns `true` if the region `r` contains the given element.
 277     pub(crate) fn contains(&self, r: N, elem: impl ToElementIndex) -> bool {
 278         elem.contained_in_row(self, r)
 279     }
 280
 281     /// `self[to] |= values[from]`, essentially: that is, take all the
 282     /// elements for the region `from` from `values` and add them to
 283     /// the region `to` in `self`.
 284     pub(crate) fn merge_liveness<M: Idx>(&mut self, to: N, from: M, values: &LivenessValues<M>) {
 285         if let Some(set) = values.points.row(from) {
 286             self.points.union_row(to, set);
 287         }
 288     }
 289
 290     /// Returns `true` if `sup_region` contains all the CFG points that
 291     /// `sub_region` contains. Ignores universal regions.
 292     pub(crate) fn contains_points(&self, sup_region: N, sub_region: N) -> bool {
 293         if let Some(sub_row) = self.points.row(sub_region) {
 294             if let Some(sup_row) = self.points.row(sup_region) {
 295                 sup_row.superset(sub_row)
 296             } else {
 297                 // sup row is empty, so sub row must be empty
 298                 sub_row.is_empty()
 299             }
 300         } else {
 301             // sub row is empty, always true
 302             true
 303         }
 304     }
 305
 306     /// Returns the locations contained within a given region `r`.
 307     pub(crate) fn locations_outlived_by<'a>(&'a self, r: N) -> impl Iterator<Item = Location> + 'a {
 308         self.points.row(r).into_iter().flat_map(move |set| {
 309             set.iter()
 310                 .take_while(move |&p| self.elements.point_in_range(p))
 311                 .map(move |p| self.elements.to_location(p))
 312         })
 313     }
 314
 315     /// Returns just the universal regions that are contained in a given region's value.
 316     pub(crate) fn universal_regions_outlived_by<'a>(
 317         &'a self,
 318         r: N,
 319     ) -> impl Iterator<Item = RegionVid> + 'a {
 320         self.free_regions.row(r).into_iter().flat_map(|set| set.iter())
 321     }
 322
 323     /// Returns all the elements contained in a given region's value.
 324     pub(crate) fn placeholders_contained_in<'a>(
 325         &'a self,
 326         r: N,
 327     ) -> impl Iterator<Item = ty::PlaceholderRegion> + 'a {
 328         self.placeholders
 329             .row(r)
 330             .into_iter()
 331             .flat_map(|set| set.iter())
 332             .map(move |p| self.placeholder_indices.lookup_placeholder(p))
 333     }
 334
 335     /// Returns all the elements contained in a given region's value.
 336     pub(crate) fn elements_contained_in<'a>(
 337         &'a self,
 338         r: N,
 339     ) -> impl Iterator<Item = RegionElement> + 'a {
 340         let points_iter = self.locations_outlived_by(r).map(RegionElement::Location);
 341
 342         let free_regions_iter =
 343             self.universal_regions_outlived_by(r).map(RegionElement::RootUniversalRegion);
 344
 345         let placeholder_universes_iter =
 346             self.placeholders_contained_in(r).map(RegionElement::PlaceholderRegion);
 347
 348         points_iter.chain(free_regions_iter).chain(placeholder_universes_iter)
 349     }
 350
 351     /// Returns a "pretty" string value of the region. Meant for debugging.
 352     pub(crate) fn region_value_str(&self, r: N) -> String {
 353         region_value_str(self.elements_contained_in(r))
 354     }
 355 }
 356
 357 pub(crate) trait ToElementIndex: Debug + Copy {
 358     fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool;
 359
 360     fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool;
 361 }
 362
 363 impl ToElementIndex for Location {
 364     fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
 365         let index = values.elements.point_from_location(self);
 366         values.points.insert(row, index)
 367     }
 368
 369     fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
 370         let index = values.elements.point_from_location(self);
 371         values.points.contains(row, index)
 372     }
 373 }
 374
 375 impl ToElementIndex for RegionVid {
 376     fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
 377         values.free_regions.insert(row, self)
 378     }
 379
 380     fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
 381         values.free_regions.contains(row, self)
 382     }
 383 }
 384
 385 impl ToElementIndex for ty::PlaceholderRegion {
 386     fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
 387         let index = values.placeholder_indices.lookup_index(self);
 388         values.placeholders.insert(row, index)
 389     }
 390
 391     fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
 392         let index = values.placeholder_indices.lookup_index(self);
 393         values.placeholders.contains(row, index)
 394     }
 395 }
 396
 397 pub(crate) fn location_set_str(
 398     elements: &RegionValueElements,
 399     points: impl IntoIterator<Item = PointIndex>,
 400 ) -> String {
 401     region_value_str(
 402         points
 403             .into_iter()
 404             .take_while(|&p| elements.point_in_range(p))
 405             .map(|p| elements.to_location(p))
 406             .map(RegionElement::Location),
 407     )
 408 }
 409
 410 fn region_value_str(elements: impl IntoIterator<Item = RegionElement>) -> String {
 411     let mut result = String::new();
 412     result.push('{');
 413
 414     // Set to Some(l1, l2) when we have observed all the locations
 415     // from l1..=l2 (inclusive) but not yet printed them. This
 416     // gets extended if we then see l3 where l3 is the successor
 417     // to l2.
 418     let mut open_location: Option<(Location, Location)> = None;
 419
 420     let mut sep = "";
 421     let mut push_sep = |s: &mut String| {
 422         s.push_str(sep);
 423         sep = ", ";
 424     };
 425
 426     for element in elements {
 427         match element {
 428             RegionElement::Location(l) => {
 429                 if let Some((location1, location2)) = open_location {
 430                     if location2.block == l.block
 431                         && location2.statement_index == l.statement_index - 1
 432                     {
 433                         open_location = Some((location1, l));
 434                         continue;
 435                     }
 436
 437                     push_sep(&mut result);
 438                     push_location_range(&mut result, location1, location2);
 439                 }
 440
 441                 open_location = Some((l, l));
 442             }
 443
 444             RegionElement::RootUniversalRegion(fr) => {
 445                 if let Some((location1, location2)) = open_location {
 446                     push_sep(&mut result);
 447                     push_location_range(&mut result, location1, location2);
 448                     open_location = None;
 449                 }
 450
 451                 push_sep(&mut result);
 452                 result.push_str(&format!("{:?}", fr));
 453             }
 454
 455             RegionElement::PlaceholderRegion(placeholder) => {
 456                 if let Some((location1, location2)) = open_location {
 457                     push_sep(&mut result);
 458                     push_location_range(&mut result, location1, location2);
 459                     open_location = None;
 460                 }
 461
 462                 push_sep(&mut result);
 463                 result.push_str(&format!("{:?}", placeholder));
 464             }
 465         }
 466     }
 467
 468     if let Some((location1, location2)) = open_location {
 469         push_sep(&mut result);
 470         push_location_range(&mut result, location1, location2);
 471     }
 472
 473     result.push('}');
 474
 475     return result;
 476
 477     fn push_location_range(str: &mut String, location1: Location, location2: Location) {
 478         if location1 == location2 {
 479             str.push_str(&format!("{:?}", location1));
 480         } else {
 481             assert_eq!(location1.block, location2.block);
 482             str.push_str(&format!(
 483                 "{:?}[{}..={}]",
 484                 location1.block, location1.statement_index, location2.statement_index
 485             ));
 486         }
 487     }
 488 }