]>
Commit | Line | Data |
---|---|---|
b7449926 | 1 | use rustc_data_structures::fx::FxHashSet; |
f9f354fc | 2 | use rustc_middle::mir::{Body, Local}; |
ba9703b0 | 3 | use rustc_middle::ty::{RegionVid, TyCtxt}; |
b7449926 XL |
4 | use std::rc::Rc; |
5 | ||
c295e0f8 XL |
6 | use rustc_mir_dataflow::impls::MaybeInitializedPlaces; |
7 | use rustc_mir_dataflow::move_paths::MoveData; | |
8 | use rustc_mir_dataflow::ResultsCursor; | |
60c5eb7d | 9 | |
c295e0f8 | 10 | use crate::{ |
60c5eb7d XL |
11 | constraints::OutlivesConstraintSet, |
12 | facts::{AllFacts, AllFactsExt}, | |
dfeec247 XL |
13 | location::LocationTable, |
14 | nll::ToRegionVid, | |
60c5eb7d XL |
15 | region_infer::values::RegionValueElements, |
16 | universal_regions::UniversalRegions, | |
60c5eb7d XL |
17 | }; |
18 | ||
b7449926 XL |
19 | use super::TypeChecker; |
20 | ||
b7449926 | 21 | mod local_use_map; |
416331ca | 22 | mod polonius; |
b7449926 XL |
23 | mod trace; |
24 | ||
25 | /// Combines liveness analysis with initialization analysis to | |
26 | /// determine which variables are live at which points, both due to | |
27 | /// ordinary uses and drops. Returns a set of (ty, location) pairs | |
28 | /// that indicate which types must be live at which point in the CFG. | |
29 | /// This vector is consumed by `constraint_generation`. | |
30 | /// | |
9fa01778 | 31 | /// N.B., this computation requires normalization; therefore, it must be |
b7449926 | 32 | /// performed before |
74b04a01 | 33 | pub(super) fn generate<'mir, 'tcx>( |
dc9dc135 | 34 | typeck: &mut TypeChecker<'_, 'tcx>, |
f9f354fc | 35 | body: &Body<'tcx>, |
b7449926 | 36 | elements: &Rc<RegionValueElements>, |
74b04a01 | 37 | flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, |
b7449926 | 38 | move_data: &MoveData<'tcx>, |
0bf4aa26 | 39 | location_table: &LocationTable, |
ee023bcb | 40 | use_polonius: bool, |
b7449926 XL |
41 | ) { |
42 | debug!("liveness::generate"); | |
532ac7d7 | 43 | |
e74abb32 XL |
44 | let free_regions = regions_that_outlive_free_regions( |
45 | typeck.infcx.num_region_vars(), | |
46 | &typeck.borrowck_context.universal_regions, | |
47 | &typeck.borrowck_context.constraints.outlives_constraints, | |
48 | ); | |
60c5eb7d | 49 | let live_locals = compute_live_locals(typeck.tcx(), &free_regions, &body); |
ee023bcb | 50 | let facts_enabled = use_polonius || AllFacts::enabled(typeck.tcx()); |
e74abb32 | 51 | |
e74abb32 XL |
52 | let polonius_drop_used = if facts_enabled { |
53 | let mut drop_used = Vec::new(); | |
dfeec247 | 54 | polonius::populate_access_facts(typeck, body, location_table, move_data, &mut drop_used); |
e74abb32 | 55 | Some(drop_used) |
532ac7d7 | 56 | } else { |
e74abb32 | 57 | None |
b7449926 | 58 | }; |
532ac7d7 | 59 | |
e74abb32 XL |
60 | if !live_locals.is_empty() || facts_enabled { |
61 | trace::trace( | |
62 | typeck, | |
63 | body, | |
64 | elements, | |
65 | flow_inits, | |
66 | move_data, | |
67 | live_locals, | |
68 | polonius_drop_used, | |
69 | ); | |
532ac7d7 XL |
70 | } |
71 | } | |
72 | ||
73 | // The purpose of `compute_live_locals` is to define the subset of `Local` | |
74 | // variables for which we need to do a liveness computation. We only need | |
75 | // to compute whether a variable `X` is live if that variable contains | |
76 | // some region `R` in its type where `R` is not known to outlive a free | |
77 | // region (i.e., where `R` may be valid for just a subset of the fn body). | |
a2a8927a | 78 | fn compute_live_locals<'tcx>( |
dc9dc135 | 79 | tcx: TyCtxt<'tcx>, |
532ac7d7 | 80 | free_regions: &FxHashSet<RegionVid>, |
dc9dc135 | 81 | body: &Body<'tcx>, |
532ac7d7 | 82 | ) -> Vec<Local> { |
dc9dc135 | 83 | let live_locals: Vec<Local> = body |
532ac7d7 XL |
84 | .local_decls |
85 | .iter_enumerated() | |
86 | .filter_map(|(local, local_decl)| { | |
87 | if tcx.all_free_regions_meet(&local_decl.ty, |r| { | |
88 | free_regions.contains(&r.to_region_vid()) | |
89 | }) { | |
90 | None | |
91 | } else { | |
92 | Some(local) | |
93 | } | |
94 | }) | |
95 | .collect(); | |
96 | ||
dc9dc135 | 97 | debug!("{} total variables", body.local_decls.len()); |
532ac7d7 XL |
98 | debug!("{} variables need liveness", live_locals.len()); |
99 | debug!("{} regions outlive free regions", free_regions.len()); | |
100 | ||
101 | live_locals | |
b7449926 XL |
102 | } |
103 | ||
9fa01778 | 104 | /// Computes all regions that are (currently) known to outlive free |
b7449926 XL |
105 | /// regions. For these regions, we do not need to compute |
106 | /// liveness, since the outlives constraints will ensure that they | |
107 | /// are live over the whole fn body anyhow. | |
a2a8927a | 108 | fn regions_that_outlive_free_regions<'tcx>( |
b7449926 XL |
109 | num_region_vars: usize, |
110 | universal_regions: &UniversalRegions<'tcx>, | |
17df50a5 | 111 | constraint_set: &OutlivesConstraintSet<'tcx>, |
b7449926 XL |
112 | ) -> FxHashSet<RegionVid> { |
113 | // Build a graph of the outlives constraints thus far. This is | |
114 | // a reverse graph, so for each constraint `R1: R2` we have an | |
115 | // edge `R2 -> R1`. Therefore, if we find all regions | |
116 | // reachable from each free region, we will have all the | |
117 | // regions that are forced to outlive some free region. | |
118 | let rev_constraint_graph = constraint_set.reverse_graph(num_region_vars); | |
119 | let fr_static = universal_regions.fr_static; | |
120 | let rev_region_graph = rev_constraint_graph.region_graph(constraint_set, fr_static); | |
121 | ||
122 | // Stack for the depth-first search. Start out with all the free regions. | |
123 | let mut stack: Vec<_> = universal_regions.universal_regions().collect(); | |
124 | ||
125 | // Set of all free regions, plus anything that outlives them. Initially | |
126 | // just contains the free regions. | |
127 | let mut outlives_free_region: FxHashSet<_> = stack.iter().cloned().collect(); | |
128 | ||
129 | // Do the DFS -- for each thing in the stack, find all things | |
130 | // that outlive it and add them to the set. If they are not, | |
131 | // push them onto the stack for later. | |
132 | while let Some(sub_region) = stack.pop() { | |
133 | stack.extend( | |
134 | rev_region_graph | |
135 | .outgoing_regions(sub_region) | |
136 | .filter(|&r| outlives_free_region.insert(r)), | |
137 | ); | |
138 | } | |
139 | ||
140 | // Return the final set of things we visited. | |
141 | outlives_free_region | |
142 | } |