compiler/rustc_hir_analysis/src/check/generator_interior/drop_ranges/cfg_propagate.rs

   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 }