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