rustc_mir_dataflow/
points.rs

Help
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 results: Results<'tcx, A>,
102) -> SparseIntervalMatrix<N, PointIndex>
103where
104    N: Idx,
105    A: Analysis<'tcx, Domain = DenseBitSet<N>>,
106{
107    let values = SparseIntervalMatrix::new(elements.num_points());
108    let mut visitor = Visitor { elements, values };
109    visit_results(
110        body,
111        body.basic_blocks.reverse_postorder().iter().copied(),
112        &mut results,
113        &mut visitor,
114    );
115    visitor.values
116}
117
118struct Visitor<'a, N: Idx> {
119    elements: &'a DenseLocationMap,
120    values: SparseIntervalMatrix<N, PointIndex>,
121}
122
123impl<'mir, 'tcx, A, N> ResultsVisitor<'mir, 'tcx, A> for Visitor<'_, N>
124where
125    A: Analysis<'tcx, Domain = DenseBitSet<N>>,
126    N: Idx,
127{
128    fn visit_after_primary_statement_effect(
129        &mut self,
130        _results: &mut Results<'tcx, A>,
131        state: &A::Domain,
132        _statement: &'mir mir::Statement<'tcx>,
133        location: Location,
134    ) {
135        let point = self.elements.point_from_location(location);
136        // Use internal iterator manually as it is much more efficient.
137        state.iter().for_each(|node| {
138            self.values.insert(node, point);
139        });
140    }
141
142    fn visit_after_primary_terminator_effect(
143        &mut self,
144        _results: &mut Results<'tcx, A>,
145        state: &A::Domain,
146        _terminator: &'mir mir::Terminator<'tcx>,
147        location: Location,
148    ) {
149        let point = self.elements.point_from_location(location);
150        // Use internal iterator manually as it is much more efficient.
151        state.iter().for_each(|node| {
152            self.values.insert(node, point);
153        });
154    }
155}
rustc_mir_dataflow/points.rs

rustc_mir_dataflow/
points.rs
