rustc_mir_dataflow/
points.rs

1use rustc_index::bit_set::DenseBitSet;
2use rustc_index::interval::SparseIntervalMatrix;
3use rustc_index::{Idx, IndexVec};
4use rustc_middle::mir::{self, BasicBlock, Body, Location};
5
6use crate::framework::{Analysis, Results, ResultsVisitor, visit_results};
7
8/// Maps between a `Location` and a `PointIndex` (and vice versa).
9pub struct DenseLocationMap {
10    /// For each basic block, how many points are contained within?
11    statements_before_block: IndexVec<BasicBlock, usize>,
12
13    /// Map backward from each point to the basic block that it
14    /// belongs to.
15    basic_blocks: IndexVec<PointIndex, BasicBlock>,
16
17    num_points: usize,
18}
19
20impl DenseLocationMap {
21    #[inline]
22    pub fn new(body: &Body<'_>) -> Self {
23        let mut num_points = 0;
24        let statements_before_block: IndexVec<BasicBlock, usize> = body
25            .basic_blocks
26            .iter()
27            .map(|block_data| {
28                let v = num_points;
29                num_points += block_data.statements.len() + 1;
30                v
31            })
32            .collect();
33
34        let mut basic_blocks = IndexVec::with_capacity(num_points);
35        for (bb, bb_data) in body.basic_blocks.iter_enumerated() {
36            basic_blocks.extend((0..=bb_data.statements.len()).map(|_| bb));
37        }
38
39        Self { statements_before_block, basic_blocks, num_points }
40    }
41
42    /// Total number of point indices
43    #[inline]
44    pub fn num_points(&self) -> usize {
45        self.num_points
46    }
47
48    /// Converts a `Location` into a `PointIndex`. O(1).
49    #[inline]
50    pub fn point_from_location(&self, location: Location) -> PointIndex {
51        let Location { block, statement_index } = location;
52        let start_index = self.statements_before_block[block];
53        PointIndex::new(start_index + statement_index)
54    }
55
56    /// Returns the `PointIndex` for the first statement in the given `BasicBlock`. O(1).
57    #[inline]
58    pub fn entry_point(&self, block: BasicBlock) -> PointIndex {
59        let start_index = self.statements_before_block[block];
60        PointIndex::new(start_index)
61    }
62
63    /// Return the PointIndex for the block start of this index.
64    #[inline]
65    pub fn to_block_start(&self, index: PointIndex) -> PointIndex {
66        PointIndex::new(self.statements_before_block[self.basic_blocks[index]])
67    }
68
69    /// Converts a `PointIndex` back to a location. O(1).
70    #[inline]
71    pub 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    #[inline]
84    pub fn point_in_range(&self, index: PointIndex) -> bool {
85        index.index() < self.num_points
86    }
87}
88
89rustc_index::newtype_index! {
90    /// A single integer representing a `Location` in the MIR control-flow
91    /// graph. Constructed efficiently from `DenseLocationMap`.
92    #[orderable]
93    #[debug_format = "PointIndex({})"]
94    pub struct PointIndex {}
95}
96
97/// Add points depending on the result of the given dataflow analysis.
98pub fn save_as_intervals<'tcx, N, A>(
99    elements: &DenseLocationMap,
100    body: &mir::Body<'tcx>,
101    mut analysis: A,
102    results: Results<A::Domain>,
103) -> SparseIntervalMatrix<N, PointIndex>
104where
105    N: Idx,
106    A: Analysis<'tcx, Domain = DenseBitSet<N>>,
107{
108    let values = SparseIntervalMatrix::new(elements.num_points());
109    let mut visitor = Visitor { elements, values };
110    visit_results(
111        body,
112        body.basic_blocks.reverse_postorder().iter().copied(),
113        &mut analysis,
114        &results,
115        &mut visitor,
116    );
117    visitor.values
118}
119
120struct Visitor<'a, N: Idx> {
121    elements: &'a DenseLocationMap,
122    values: SparseIntervalMatrix<N, PointIndex>,
123}
124
125impl<'tcx, A, N> ResultsVisitor<'tcx, A> for Visitor<'_, N>
126where
127    A: Analysis<'tcx, Domain = DenseBitSet<N>>,
128    N: Idx,
129{
130    fn visit_after_primary_statement_effect<'mir>(
131        &mut self,
132        _analysis: &mut A,
133        state: &A::Domain,
134        _statement: &'mir mir::Statement<'tcx>,
135        location: Location,
136    ) {
137        let point = self.elements.point_from_location(location);
138        // Use internal iterator manually as it is much more efficient.
139        state.iter().for_each(|node| {
140            self.values.insert(node, point);
141        });
142    }
143
144    fn visit_after_primary_terminator_effect<'mir>(
145        &mut self,
146        _analysis: &mut A,
147        state: &A::Domain,
148        _terminator: &'mir mir::Terminator<'tcx>,
149        location: Location,
150    ) {
151        let point = self.elements.point_from_location(location);
152        // Use internal iterator manually as it is much more efficient.
153        state.iter().for_each(|node| {
154            self.values.insert(node, point);
155        });
156    }
157}
rustc_mir_dataflow/points.rs

rustc_mir_dataflow/
points.rs
