1 use rustc_index::vec::{Idx, IndexVec};
2 use rustc_middle::mir::{BasicBlock, Body, Location};
3 
4 /// Maps between a MIR Location, which identifies a particular
5 /// statement within a basic block, to a "rich location", which
6 /// identifies at a finer granularity. In particular, we distinguish
7 /// the *start* of a statement and the *mid-point*. The mid-point is
8 /// the point *just* before the statement takes effect; in particular,
9 /// for an assignment `A = B`, it is the point where B is about to be
10 /// written into A. This mid-point is a kind of hack to work around
11 /// our inability to track the position information at sufficient
12 /// granularity through outlives relations; however, the rich location
13 /// table serves another purpose: it compresses locations from
14 /// multiple words into a single u32.
15 pub struct LocationTable {
16     num_points: usize,
17     statements_before_block: IndexVec<BasicBlock, usize>,
18 }
19 
20 rustc_index::newtype_index! {
21     pub struct LocationIndex {
22         DEBUG_FORMAT = "LocationIndex({})"
23     }
24 }
25 
26 #[derive(Copy, Clone, Debug)]
27 pub enum RichLocation {
28     Start(Location),
29     Mid(Location),
30 }
31 
32 impl LocationTable {
new(body: &Body<'_>) -> Self33     crate fn new(body: &Body<'_>) -> Self {
34         let mut num_points = 0;
35         let statements_before_block = body
36             .basic_blocks()
37             .iter()
38             .map(|block_data| {
39                 let v = num_points;
40                 num_points += (block_data.statements.len() + 1) * 2;
41                 v
42             })
43             .collect();
44 
45         debug!("LocationTable(statements_before_block={:#?})", statements_before_block);
46         debug!("LocationTable: num_points={:#?}", num_points);
47 
48         Self { num_points, statements_before_block }
49     }
50 
all_points(&self) -> impl Iterator<Item = LocationIndex>51     pub fn all_points(&self) -> impl Iterator<Item = LocationIndex> {
52         (0..self.num_points).map(LocationIndex::new)
53     }
54 
start_index(&self, location: Location) -> LocationIndex55     pub fn start_index(&self, location: Location) -> LocationIndex {
56         let Location { block, statement_index } = location;
57         let start_index = self.statements_before_block[block];
58         LocationIndex::new(start_index + statement_index * 2)
59     }
60 
mid_index(&self, location: Location) -> LocationIndex61     pub fn mid_index(&self, location: Location) -> LocationIndex {
62         let Location { block, statement_index } = location;
63         let start_index = self.statements_before_block[block];
64         LocationIndex::new(start_index + statement_index * 2 + 1)
65     }
66 
to_location(&self, index: LocationIndex) -> RichLocation67     pub fn to_location(&self, index: LocationIndex) -> RichLocation {
68         let point_index = index.index();
69 
70         // Find the basic block. We have a vector with the
71         // starting index of the statement in each block. Imagine
72         // we have statement #22, and we have a vector like:
73         //
74         // [0, 10, 20]
75         //
76         // In that case, this represents point_index 2 of
77         // basic block BB2. We know this because BB0 accounts for
78         // 0..10, BB1 accounts for 11..20, and BB2 accounts for
79         // 20...
80         //
81         // To compute this, we could do a binary search, but
82         // because I am lazy we instead iterate through to find
83         // the last point where the "first index" (0, 10, or 20)
84         // was less than the statement index (22). In our case, this will
85         // be (BB2, 20).
86         let (block, &first_index) = self
87             .statements_before_block
88             .iter_enumerated()
89             .filter(|(_, first_index)| **first_index <= point_index)
90             .last()
91             .unwrap();
92 
93         let statement_index = (point_index - first_index) / 2;
94         if index.is_start() {
95             RichLocation::Start(Location { block, statement_index })
96         } else {
97             RichLocation::Mid(Location { block, statement_index })
98         }
99     }
100 }
101 
102 impl LocationIndex {
is_start(&self) -> bool103     fn is_start(&self) -> bool {
104         // even indices are start points; odd indices are mid points
105         (self.index() % 2) == 0
106     }
107 }
108