]>
Commit | Line | Data |
---|---|---|
5099ac24 FG |
1 | use super::{DropRangesBuilder, PostOrderId}; |
2 | use rustc_index::{bit_set::BitSet, vec::IndexVec}; | |
3 | use std::collections::BTreeMap; | |
4 | ||
5 | impl DropRangesBuilder { | |
6 | pub fn propagate_to_fixpoint(&mut self) { | |
7 | trace!("before fixpoint: {:#?}", self); | |
8 | let preds = self.compute_predecessors(); | |
9 | ||
10 | trace!("predecessors: {:#?}", preds.iter_enumerated().collect::<BTreeMap<_, _>>()); | |
11 | ||
12 | let mut new_state = BitSet::new_empty(self.num_values()); | |
13 | let mut changed_nodes = BitSet::new_empty(self.nodes.len()); | |
14 | let mut unchanged_mask = BitSet::new_filled(self.nodes.len()); | |
15 | changed_nodes.insert(0u32.into()); | |
16 | ||
17 | let mut propagate = || { | |
18 | let mut changed = false; | |
19 | unchanged_mask.insert_all(); | |
20 | for id in self.nodes.indices() { | |
21 | trace!("processing {:?}, changed_nodes: {:?}", id, changed_nodes); | |
22 | // Check if any predecessor has changed, and if not then short-circuit. | |
23 | // | |
24 | // We handle the start node specially, since it doesn't have any predecessors, | |
25 | // but we need to start somewhere. | |
26 | if match id.index() { | |
27 | 0 => !changed_nodes.contains(id), | |
28 | _ => !preds[id].iter().any(|pred| changed_nodes.contains(*pred)), | |
29 | } { | |
30 | trace!("short-circuiting because none of {:?} have changed", preds[id]); | |
31 | unchanged_mask.remove(id); | |
32 | continue; | |
33 | } | |
34 | ||
35 | if id.index() == 0 { | |
36 | new_state.clear(); | |
37 | } else { | |
38 | // If we are not the start node and we have no predecessors, treat | |
39 | // everything as dropped because there's no way to get here anyway. | |
40 | new_state.insert_all(); | |
41 | }; | |
42 | ||
43 | for pred in &preds[id] { | |
44 | new_state.intersect(&self.nodes[*pred].drop_state); | |
45 | } | |
46 | ||
47 | for drop in &self.nodes[id].drops { | |
48 | new_state.insert(*drop); | |
49 | } | |
50 | ||
51 | for reinit in &self.nodes[id].reinits { | |
52 | new_state.remove(*reinit); | |
53 | } | |
54 | ||
55 | if self.nodes[id].drop_state.intersect(&new_state) { | |
56 | changed_nodes.insert(id); | |
57 | changed = true; | |
58 | } else { | |
59 | unchanged_mask.remove(id); | |
60 | } | |
61 | } | |
62 | ||
63 | changed_nodes.intersect(&unchanged_mask); | |
64 | changed | |
65 | }; | |
66 | ||
67 | while propagate() { | |
68 | trace!("drop_state changed, re-running propagation"); | |
69 | } | |
70 | ||
71 | trace!("after fixpoint: {:#?}", self); | |
72 | } | |
73 | ||
74 | fn compute_predecessors(&self) -> IndexVec<PostOrderId, Vec<PostOrderId>> { | |
75 | let mut preds = IndexVec::from_fn_n(|_| vec![], self.nodes.len()); | |
76 | for (id, node) in self.nodes.iter_enumerated() { | |
77 | // If the node has no explicit successors, we assume that control | |
78 | // will from this node into the next one. | |
79 | // | |
80 | // If there are successors listed, then we assume that all | |
81 | // possible successors are given and we do not include the default. | |
82 | if node.successors.len() == 0 && id.index() != self.nodes.len() - 1 { | |
83 | preds[id + 1].push(id); | |
84 | } else { | |
85 | for succ in &node.successors { | |
86 | preds[*succ].push(id); | |
87 | } | |
88 | } | |
89 | } | |
90 | preds | |
91 | } | |
92 | } |