]>
Commit | Line | Data |
---|---|---|
5099ac24 FG |
1 | //! Drop range analysis finds the portions of the tree where a value is guaranteed to be dropped |
2 | //! (i.e. moved, uninitialized, etc.). This is used to exclude the types of those values from the | |
3 | //! generator type. See `InteriorVisitor::record` for where the results of this analysis are used. | |
4 | //! | |
5 | //! There are three phases to this analysis: | |
6 | //! 1. Use `ExprUseVisitor` to identify the interesting values that are consumed and borrowed. | |
7 | //! 2. Use `DropRangeVisitor` to find where the interesting values are dropped or reinitialized, | |
8 | //! and also build a control flow graph. | |
9 | //! 3. Use `DropRanges::propagate_to_fixpoint` to flow the dropped/reinitialized information through | |
10 | //! the CFG and find the exact points where we know a value is definitely dropped. | |
11 | //! | |
12 | //! The end result is a data structure that maps the post-order index of each node in the HIR tree | |
13 | //! to a set of values that are known to be dropped at that location. | |
14 | ||
15 | use self::cfg_build::build_control_flow_graph; | |
16 | use self::record_consumed_borrow::find_consumed_and_borrowed; | |
17 | use crate::check::FnCtxt; | |
18 | use hir::def_id::DefId; | |
19 | use hir::{Body, HirId, HirIdMap, Node}; | |
064997fb | 20 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
5099ac24 FG |
21 | use rustc_hir as hir; |
22 | use rustc_index::bit_set::BitSet; | |
23 | use rustc_index::vec::IndexVec; | |
24 | use rustc_middle::hir::map::Map; | |
25 | use rustc_middle::hir::place::{PlaceBase, PlaceWithHirId}; | |
26 | use rustc_middle::ty; | |
27 | use std::collections::BTreeMap; | |
28 | use std::fmt::Debug; | |
29 | ||
30 | mod cfg_build; | |
31 | mod cfg_propagate; | |
32 | mod cfg_visualize; | |
33 | mod record_consumed_borrow; | |
34 | ||
35 | pub fn compute_drop_ranges<'a, 'tcx>( | |
36 | fcx: &'a FnCtxt<'a, 'tcx>, | |
37 | def_id: DefId, | |
38 | body: &'tcx Body<'tcx>, | |
39 | ) -> DropRanges { | |
064997fb | 40 | if fcx.sess().opts.unstable_opts.drop_tracking { |
5099ac24 FG |
41 | let consumed_borrowed_places = find_consumed_and_borrowed(fcx, def_id, body); |
42 | ||
923072b8 | 43 | let typeck_results = &fcx.typeck_results.borrow(); |
5099ac24 | 44 | let num_exprs = fcx.tcx.region_scope_tree(def_id).body_expr_count(body.id()).unwrap_or(0); |
5e7ed085 | 45 | let (mut drop_ranges, borrowed_temporaries) = build_control_flow_graph( |
5099ac24 FG |
46 | fcx.tcx.hir(), |
47 | fcx.tcx, | |
923072b8 | 48 | typeck_results, |
5099ac24 FG |
49 | consumed_borrowed_places, |
50 | body, | |
51 | num_exprs, | |
52 | ); | |
53 | ||
54 | drop_ranges.propagate_to_fixpoint(); | |
55 | ||
5e7ed085 FG |
56 | debug!("borrowed_temporaries = {borrowed_temporaries:?}"); |
57 | DropRanges { | |
58 | tracked_value_map: drop_ranges.tracked_value_map, | |
59 | nodes: drop_ranges.nodes, | |
60 | borrowed_temporaries: Some(borrowed_temporaries), | |
61 | } | |
5099ac24 FG |
62 | } else { |
63 | // If drop range tracking is not enabled, skip all the analysis and produce an | |
64 | // empty set of DropRanges. | |
5e7ed085 FG |
65 | DropRanges { |
66 | tracked_value_map: FxHashMap::default(), | |
67 | nodes: IndexVec::new(), | |
68 | borrowed_temporaries: None, | |
69 | } | |
5099ac24 FG |
70 | } |
71 | } | |
72 | ||
73 | /// Applies `f` to consumable node in the HIR subtree pointed to by `place`. | |
74 | /// | |
75 | /// This includes the place itself, and if the place is a reference to a local | |
76 | /// variable then `f` is also called on the HIR node for that variable as well. | |
77 | /// | |
78 | /// For example, if `place` points to `foo()`, then `f` is called once for the | |
79 | /// result of `foo`. On the other hand, if `place` points to `x` then `f` will | |
80 | /// be called both on the `ExprKind::Path` node that represents the expression | |
81 | /// as well as the HirId of the local `x` itself. | |
82 | fn for_each_consumable<'tcx>(hir: Map<'tcx>, place: TrackedValue, mut f: impl FnMut(TrackedValue)) { | |
83 | f(place); | |
84 | let node = hir.find(place.hir_id()); | |
85 | if let Some(Node::Expr(expr)) = node { | |
86 | match expr.kind { | |
87 | hir::ExprKind::Path(hir::QPath::Resolved( | |
88 | _, | |
89 | hir::Path { res: hir::def::Res::Local(hir_id), .. }, | |
90 | )) => { | |
91 | f(TrackedValue::Variable(*hir_id)); | |
92 | } | |
93 | _ => (), | |
94 | } | |
95 | } | |
96 | } | |
97 | ||
98 | rustc_index::newtype_index! { | |
99 | pub struct PostOrderId { | |
100 | DEBUG_FORMAT = "id({})", | |
101 | } | |
102 | } | |
103 | ||
104 | rustc_index::newtype_index! { | |
105 | pub struct TrackedValueIndex { | |
106 | DEBUG_FORMAT = "hidx({})", | |
107 | } | |
108 | } | |
109 | ||
110 | /// Identifies a value whose drop state we need to track. | |
064997fb | 111 | #[derive(PartialEq, Eq, Hash, Clone, Copy)] |
5099ac24 FG |
112 | enum TrackedValue { |
113 | /// Represents a named variable, such as a let binding, parameter, or upvar. | |
114 | /// | |
115 | /// The HirId points to the variable's definition site. | |
116 | Variable(HirId), | |
117 | /// A value produced as a result of an expression. | |
118 | /// | |
119 | /// The HirId points to the expression that returns this value. | |
120 | Temporary(HirId), | |
121 | } | |
122 | ||
064997fb FG |
123 | impl Debug for TrackedValue { |
124 | fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { | |
125 | ty::tls::with_opt(|opt_tcx| { | |
126 | if let Some(tcx) = opt_tcx { | |
127 | write!(f, "{}", tcx.hir().node_to_string(self.hir_id())) | |
128 | } else { | |
129 | match self { | |
130 | Self::Variable(hir_id) => write!(f, "Variable({:?})", hir_id), | |
131 | Self::Temporary(hir_id) => write!(f, "Temporary({:?})", hir_id), | |
132 | } | |
133 | } | |
134 | }) | |
135 | } | |
136 | } | |
137 | ||
5099ac24 FG |
138 | impl TrackedValue { |
139 | fn hir_id(&self) -> HirId { | |
140 | match self { | |
141 | TrackedValue::Variable(hir_id) | TrackedValue::Temporary(hir_id) => *hir_id, | |
142 | } | |
143 | } | |
144 | ||
145 | fn from_place_with_projections_allowed(place_with_id: &PlaceWithHirId<'_>) -> Self { | |
146 | match place_with_id.place.base { | |
147 | PlaceBase::Rvalue | PlaceBase::StaticItem => { | |
148 | TrackedValue::Temporary(place_with_id.hir_id) | |
149 | } | |
150 | PlaceBase::Local(hir_id) | |
151 | | PlaceBase::Upvar(ty::UpvarId { var_path: ty::UpvarPath { hir_id }, .. }) => { | |
152 | TrackedValue::Variable(hir_id) | |
153 | } | |
154 | } | |
155 | } | |
156 | } | |
157 | ||
158 | /// Represents a reason why we might not be able to convert a HirId or Place | |
159 | /// into a tracked value. | |
160 | #[derive(Debug)] | |
161 | enum TrackedValueConversionError { | |
162 | /// Place projects are not currently supported. | |
163 | /// | |
164 | /// The reasoning around these is kind of subtle, so we choose to be more | |
064997fb | 165 | /// conservative around these for now. There is no reason in theory we |
5099ac24 FG |
166 | /// cannot support these, we just have not implemented it yet. |
167 | PlaceProjectionsNotSupported, | |
168 | } | |
169 | ||
170 | impl TryFrom<&PlaceWithHirId<'_>> for TrackedValue { | |
171 | type Error = TrackedValueConversionError; | |
172 | ||
173 | fn try_from(place_with_id: &PlaceWithHirId<'_>) -> Result<Self, Self::Error> { | |
174 | if !place_with_id.place.projections.is_empty() { | |
175 | debug!( | |
176 | "TrackedValue from PlaceWithHirId: {:?} has projections, which are not supported.", | |
177 | place_with_id | |
178 | ); | |
179 | return Err(TrackedValueConversionError::PlaceProjectionsNotSupported); | |
180 | } | |
181 | ||
182 | Ok(TrackedValue::from_place_with_projections_allowed(place_with_id)) | |
183 | } | |
184 | } | |
185 | ||
186 | pub struct DropRanges { | |
187 | tracked_value_map: FxHashMap<TrackedValue, TrackedValueIndex>, | |
188 | nodes: IndexVec<PostOrderId, NodeInfo>, | |
5e7ed085 | 189 | borrowed_temporaries: Option<FxHashSet<HirId>>, |
5099ac24 FG |
190 | } |
191 | ||
192 | impl DropRanges { | |
193 | pub fn is_dropped_at(&self, hir_id: HirId, location: usize) -> bool { | |
194 | self.tracked_value_map | |
195 | .get(&TrackedValue::Temporary(hir_id)) | |
196 | .or(self.tracked_value_map.get(&TrackedValue::Variable(hir_id))) | |
197 | .cloned() | |
198 | .map_or(false, |tracked_value_id| { | |
199 | self.expect_node(location.into()).drop_state.contains(tracked_value_id) | |
200 | }) | |
201 | } | |
202 | ||
5e7ed085 FG |
203 | pub fn is_borrowed_temporary(&self, expr: &hir::Expr<'_>) -> bool { |
204 | if let Some(b) = &self.borrowed_temporaries { b.contains(&expr.hir_id) } else { true } | |
205 | } | |
206 | ||
5099ac24 FG |
207 | /// Returns a reference to the NodeInfo for a node, panicking if it does not exist |
208 | fn expect_node(&self, id: PostOrderId) -> &NodeInfo { | |
209 | &self.nodes[id] | |
210 | } | |
211 | } | |
212 | ||
213 | /// Tracks information needed to compute drop ranges. | |
214 | struct DropRangesBuilder { | |
215 | /// The core of DropRangesBuilder is a set of nodes, which each represent | |
216 | /// one expression. We primarily refer to them by their index in a | |
217 | /// post-order traversal of the HIR tree, since this is what | |
218 | /// generator_interior uses to talk about yield positions. | |
219 | /// | |
220 | /// This IndexVec keeps the relevant details for each node. See the | |
221 | /// NodeInfo struct for more details, but this information includes things | |
222 | /// such as the set of control-flow successors, which variables are dropped | |
223 | /// or reinitialized, and whether each variable has been inferred to be | |
5e7ed085 | 224 | /// known-dropped or potentially reinitialized at each point. |
5099ac24 FG |
225 | nodes: IndexVec<PostOrderId, NodeInfo>, |
226 | /// We refer to values whose drop state we are tracking by the HirId of | |
227 | /// where they are defined. Within a NodeInfo, however, we store the | |
228 | /// drop-state in a bit vector indexed by a HirIdIndex | |
229 | /// (see NodeInfo::drop_state). The hir_id_map field stores the mapping | |
230 | /// from HirIds to the HirIdIndex that is used to represent that value in | |
231 | /// bitvector. | |
232 | tracked_value_map: FxHashMap<TrackedValue, TrackedValueIndex>, | |
233 | ||
234 | /// When building the control flow graph, we don't always know the | |
235 | /// post-order index of the target node at the point we encounter it. | |
236 | /// For example, this happens with break and continue. In those cases, | |
237 | /// we store a pair of the PostOrderId of the source and the HirId | |
238 | /// of the target. Once we have gathered all of these edges, we make a | |
239 | /// pass over the set of deferred edges (see process_deferred_edges in | |
240 | /// cfg_build.rs), look up the PostOrderId for the target (since now the | |
241 | /// post-order index for all nodes is known), and add missing control flow | |
242 | /// edges. | |
243 | deferred_edges: Vec<(PostOrderId, HirId)>, | |
244 | /// This maps HirIds of expressions to their post-order index. It is | |
245 | /// used in process_deferred_edges to correctly add back-edges. | |
246 | post_order_map: HirIdMap<PostOrderId>, | |
247 | } | |
248 | ||
249 | impl Debug for DropRangesBuilder { | |
250 | fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { | |
251 | f.debug_struct("DropRanges") | |
252 | .field("hir_id_map", &self.tracked_value_map) | |
253 | .field("post_order_maps", &self.post_order_map) | |
254 | .field("nodes", &self.nodes.iter_enumerated().collect::<BTreeMap<_, _>>()) | |
255 | .finish() | |
256 | } | |
257 | } | |
258 | ||
259 | /// DropRanges keeps track of what values are definitely dropped at each point in the code. | |
260 | /// | |
261 | /// Values of interest are defined by the hir_id of their place. Locations in code are identified | |
262 | /// by their index in the post-order traversal. At its core, DropRanges maps | |
263 | /// (hir_id, post_order_id) -> bool, where a true value indicates that the value is definitely | |
264 | /// dropped at the point of the node identified by post_order_id. | |
265 | impl DropRangesBuilder { | |
266 | /// Returns the number of values (hir_ids) that are tracked | |
267 | fn num_values(&self) -> usize { | |
268 | self.tracked_value_map.len() | |
269 | } | |
270 | ||
271 | fn node_mut(&mut self, id: PostOrderId) -> &mut NodeInfo { | |
272 | let size = self.num_values(); | |
273 | self.nodes.ensure_contains_elem(id, || NodeInfo::new(size)); | |
274 | &mut self.nodes[id] | |
275 | } | |
276 | ||
277 | fn add_control_edge(&mut self, from: PostOrderId, to: PostOrderId) { | |
278 | trace!("adding control edge from {:?} to {:?}", from, to); | |
279 | self.node_mut(from).successors.push(to); | |
280 | } | |
281 | } | |
282 | ||
283 | #[derive(Debug)] | |
284 | struct NodeInfo { | |
285 | /// IDs of nodes that can follow this one in the control flow | |
286 | /// | |
287 | /// If the vec is empty, then control proceeds to the next node. | |
288 | successors: Vec<PostOrderId>, | |
289 | ||
290 | /// List of hir_ids that are dropped by this node. | |
291 | drops: Vec<TrackedValueIndex>, | |
292 | ||
293 | /// List of hir_ids that are reinitialized by this node. | |
294 | reinits: Vec<TrackedValueIndex>, | |
295 | ||
296 | /// Set of values that are definitely dropped at this point. | |
297 | drop_state: BitSet<TrackedValueIndex>, | |
298 | } | |
299 | ||
300 | impl NodeInfo { | |
301 | fn new(num_values: usize) -> Self { | |
302 | Self { | |
303 | successors: vec![], | |
304 | drops: vec![], | |
305 | reinits: vec![], | |
306 | drop_state: BitSet::new_filled(num_values), | |
307 | } | |
308 | } | |
309 | } |