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