]>
Commit | Line | Data |
---|---|---|
83c7162d XL |
1 | // Copyright 2017 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | use rustc::mir::{BasicBlock, Location, Mir}; | |
12 | use rustc_data_structures::indexed_vec::{Idx, IndexVec}; | |
13 | ||
14 | /// Maps between a MIR Location, which identifies the a particular | |
15 | /// statement within a basic block, to a "rich location", which | |
16 | /// identifies at a finer granularity. In particular, we distinguish | |
17 | /// the *start* of a statement and the *mid-point*. The mid-point is | |
18 | /// the point *just* before the statement takes effect; in particular, | |
19 | /// for an assignment `A = B`, it is the point where B is about to be | |
20 | /// written into A. This mid-point is a kind of hack to work around | |
21 | /// our inability to track the position information at sufficient | |
22 | /// granularity through outlives relations; however, the rich location | |
23 | /// table serves another purpose: it compresses locations from | |
24 | /// multiple words into a single u32. | |
25 | crate struct LocationTable { | |
26 | num_points: usize, | |
27 | statements_before_block: IndexVec<BasicBlock, usize>, | |
28 | } | |
29 | ||
30 | newtype_index!(LocationIndex { DEBUG_FORMAT = "LocationIndex({})" }); | |
31 | ||
32 | #[derive(Copy, Clone, Debug)] | |
33 | crate enum RichLocation { | |
34 | Start(Location), | |
35 | Mid(Location), | |
36 | } | |
37 | ||
38 | impl LocationTable { | |
39 | crate fn new(mir: &Mir<'_>) -> Self { | |
40 | let mut num_points = 0; | |
41 | let statements_before_block = mir.basic_blocks() | |
42 | .iter() | |
43 | .map(|block_data| { | |
44 | let v = num_points; | |
45 | num_points += (block_data.statements.len() + 1) * 2; | |
46 | v | |
47 | }) | |
48 | .collect(); | |
49 | ||
50 | debug!( | |
51 | "LocationTable(statements_before_block={:#?})", | |
52 | statements_before_block | |
53 | ); | |
54 | debug!("LocationTable: num_points={:#?}", num_points); | |
55 | ||
56 | Self { | |
57 | num_points, | |
58 | statements_before_block, | |
59 | } | |
60 | } | |
61 | ||
62 | crate fn all_points(&self) -> impl Iterator<Item = LocationIndex> { | |
63 | (0..self.num_points).map(LocationIndex::new) | |
64 | } | |
65 | ||
66 | crate fn start_index(&self, location: Location) -> LocationIndex { | |
67 | let Location { | |
68 | block, | |
69 | statement_index, | |
70 | } = location; | |
71 | let start_index = self.statements_before_block[block]; | |
72 | LocationIndex::new(start_index + statement_index * 2) | |
73 | } | |
74 | ||
75 | crate fn mid_index(&self, location: Location) -> LocationIndex { | |
76 | let Location { | |
77 | block, | |
78 | statement_index, | |
79 | } = location; | |
80 | let start_index = self.statements_before_block[block]; | |
81 | LocationIndex::new(start_index + statement_index * 2 + 1) | |
82 | } | |
83 | ||
84 | crate fn to_location(&self, index: LocationIndex) -> RichLocation { | |
85 | let point_index = index.index(); | |
86 | ||
87 | // Find the basic block. We have a vector with the | |
88 | // starting index of the statement in each block. Imagine | |
89 | // we have statement #22, and we have a vector like: | |
90 | // | |
91 | // [0, 10, 20] | |
92 | // | |
93 | // In that case, this represents point_index 2 of | |
94 | // basic block BB2. We know this because BB0 accounts for | |
95 | // 0..10, BB1 accounts for 11..20, and BB2 accounts for | |
96 | // 20... | |
97 | // | |
98 | // To compute this, we could do a binary search, but | |
99 | // because I am lazy we instead iterate through to find | |
100 | // the last point where the "first index" (0, 10, or 20) | |
101 | // was less than the statement index (22). In our case, this will | |
102 | // be (BB2, 20). | |
103 | let (block, &first_index) = self.statements_before_block | |
104 | .iter_enumerated() | |
105 | .filter(|(_, first_index)| **first_index <= point_index) | |
106 | .last() | |
107 | .unwrap(); | |
108 | ||
109 | let statement_index = (point_index - first_index) / 2; | |
110 | if index.is_start() { | |
111 | RichLocation::Start(Location { block, statement_index }) | |
112 | } else { | |
113 | RichLocation::Mid(Location { block, statement_index }) | |
114 | } | |
115 | } | |
116 | } | |
117 | ||
118 | impl LocationIndex { | |
119 | fn is_start(&self) -> bool { | |
120 | // even indices are start points; odd indices are mid points | |
121 | (self.index() % 2) == 0 | |
122 | } | |
123 | } |