]>
Commit | Line | Data |
---|---|---|
0bf4aa26 | 1 | use borrow_check::location::LocationTable; |
b7449926 XL |
2 | use borrow_check::nll::region_infer::values::RegionValueElements; |
3 | use borrow_check::nll::constraints::ConstraintSet; | |
4 | use borrow_check::nll::NllLivenessMap; | |
5 | use borrow_check::nll::universal_regions::UniversalRegions; | |
6 | use dataflow::move_paths::MoveData; | |
7 | use dataflow::MaybeInitializedPlaces; | |
8 | use dataflow::FlowAtLocation; | |
9 | use rustc::mir::Mir; | |
10 | use rustc::ty::RegionVid; | |
11 | use rustc_data_structures::fx::FxHashSet; | |
12 | use std::rc::Rc; | |
13 | ||
14 | use super::TypeChecker; | |
15 | ||
16 | crate mod liveness_map; | |
17 | mod local_use_map; | |
18 | mod trace; | |
19 | ||
20 | /// Combines liveness analysis with initialization analysis to | |
21 | /// determine which variables are live at which points, both due to | |
22 | /// ordinary uses and drops. Returns a set of (ty, location) pairs | |
23 | /// that indicate which types must be live at which point in the CFG. | |
24 | /// This vector is consumed by `constraint_generation`. | |
25 | /// | |
26 | /// NB. This computation requires normalization; therefore, it must be | |
27 | /// performed before | |
28 | pub(super) fn generate<'gcx, 'tcx>( | |
29 | typeck: &mut TypeChecker<'_, 'gcx, 'tcx>, | |
30 | mir: &Mir<'tcx>, | |
31 | elements: &Rc<RegionValueElements>, | |
0731742a | 32 | flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'gcx, 'tcx>>, |
b7449926 | 33 | move_data: &MoveData<'tcx>, |
0bf4aa26 | 34 | location_table: &LocationTable, |
b7449926 XL |
35 | ) { |
36 | debug!("liveness::generate"); | |
37 | let free_regions = { | |
38 | let borrowck_context = typeck.borrowck_context.as_ref().unwrap(); | |
39 | regions_that_outlive_free_regions( | |
40 | typeck.infcx.num_region_vars(), | |
41 | &borrowck_context.universal_regions, | |
42 | &borrowck_context.constraints.outlives_constraints, | |
43 | ) | |
44 | }; | |
45 | let liveness_map = NllLivenessMap::compute(typeck.tcx(), &free_regions, mir); | |
0bf4aa26 | 46 | trace::trace(typeck, mir, elements, flow_inits, move_data, &liveness_map, location_table); |
b7449926 XL |
47 | } |
48 | ||
49 | /// Compute all regions that are (currently) known to outlive free | |
50 | /// regions. For these regions, we do not need to compute | |
51 | /// liveness, since the outlives constraints will ensure that they | |
52 | /// are live over the whole fn body anyhow. | |
53 | fn regions_that_outlive_free_regions( | |
54 | num_region_vars: usize, | |
55 | universal_regions: &UniversalRegions<'tcx>, | |
56 | constraint_set: &ConstraintSet, | |
57 | ) -> FxHashSet<RegionVid> { | |
58 | // Build a graph of the outlives constraints thus far. This is | |
59 | // a reverse graph, so for each constraint `R1: R2` we have an | |
60 | // edge `R2 -> R1`. Therefore, if we find all regions | |
61 | // reachable from each free region, we will have all the | |
62 | // regions that are forced to outlive some free region. | |
63 | let rev_constraint_graph = constraint_set.reverse_graph(num_region_vars); | |
64 | let fr_static = universal_regions.fr_static; | |
65 | let rev_region_graph = rev_constraint_graph.region_graph(constraint_set, fr_static); | |
66 | ||
67 | // Stack for the depth-first search. Start out with all the free regions. | |
68 | let mut stack: Vec<_> = universal_regions.universal_regions().collect(); | |
69 | ||
70 | // Set of all free regions, plus anything that outlives them. Initially | |
71 | // just contains the free regions. | |
72 | let mut outlives_free_region: FxHashSet<_> = stack.iter().cloned().collect(); | |
73 | ||
74 | // Do the DFS -- for each thing in the stack, find all things | |
75 | // that outlive it and add them to the set. If they are not, | |
76 | // push them onto the stack for later. | |
77 | while let Some(sub_region) = stack.pop() { | |
78 | stack.extend( | |
79 | rev_region_graph | |
80 | .outgoing_regions(sub_region) | |
81 | .filter(|&r| outlives_free_region.insert(r)), | |
82 | ); | |
83 | } | |
84 | ||
85 | // Return the final set of things we visited. | |
86 | outlives_free_region | |
87 | } |