1 use super::{DropRangesBuilder, PostOrderId};
2 use rustc_index::{bit_set::BitSet, vec::IndexVec};
3 use std::collections::BTreeMap;
5 impl DropRangesBuilder {
6 pub fn propagate_to_fixpoint(&mut self) {
7 trace!("before fixpoint: {:#?}", self);
8 let preds = self.compute_predecessors();
10 trace!("predecessors: {:#?}", preds.iter_enumerated().collect::<BTreeMap<_, _>>());
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());
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.
24 // We handle the start node specially, since it doesn't have any predecessors,
25 // but we need to start somewhere.
27 0 => !changed_nodes.contains(id),
28 _ => !preds[id].iter().any(|pred| changed_nodes.contains(*pred)),
30 trace!("short-circuiting because none of {:?} have changed", preds[id]);
31 unchanged_mask.remove(id);
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();
43 for pred in &preds[id] {
44 new_state.intersect(&self.nodes[*pred].drop_state);
47 for drop in &self.nodes[id].drops {
48 new_state.insert(*drop);
51 for reinit in &self.nodes[id].reinits {
52 new_state.remove(*reinit);
55 if self.nodes[id].drop_state.intersect(&new_state) {
56 changed_nodes.insert(id);
59 unchanged_mask.remove(id);
63 changed_nodes.intersect(&unchanged_mask);
68 trace!("drop_state changed, re-running propagation");
71 trace!("after fixpoint: {:#?}", self);
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.
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);
85 for succ in &node.successors {
86 preds[*succ].push(id);