Rollup merge of #95120 - smoelius:backward-switch-int, r=ecstatic-morse

Implement `apply_switch_int_edge_effects` for backward analyses

See #94576 for some discussion.

r? `@ecstatic-morse`

2 files changed, 95 insertions, 0 deletions

diff --git a/compiler/rustc_middle/src/mir/mod.rs b/compiler/rustc_middle/src/mir/mod.rs
index ea71cff1616..eec6eed311b 100644
--- a/compiler/rustc_middle/src/mir/mod.rs
+++ b/compiler/rustc_middle/src/mir/mod.rs
@@ -45,6 +45,7 @@ use std::{iter, mem, option};
 use self::graph_cyclic_cache::GraphIsCyclicCache;
 use self::predecessors::{PredecessorCache, Predecessors};
 pub use self::query::*;
+use self::switch_sources::{SwitchSourceCache, SwitchSources};
 
 pub mod coverage;
 mod generic_graph;
@@ -58,6 +59,7 @@ mod predecessors;
 pub mod pretty;
 mod query;
 pub mod spanview;
+mod switch_sources;
 pub mod tcx;
 pub mod terminator;
 pub use terminator::*;
@@ -296,6 +298,7 @@ pub struct Body<'tcx> {
     pub is_polymorphic: bool,
 
     predecessor_cache: PredecessorCache,
+    switch_source_cache: SwitchSourceCache,
     is_cyclic: GraphIsCyclicCache,
 
     pub tainted_by_errors: Option<ErrorGuaranteed>,
@@ -344,6 +347,7 @@ impl<'tcx> Body<'tcx> {
             required_consts: Vec::new(),
             is_polymorphic: false,
             predecessor_cache: PredecessorCache::new(),
+            switch_source_cache: SwitchSourceCache::new(),
             is_cyclic: GraphIsCyclicCache::new(),
             tainted_by_errors,
         };
@@ -372,6 +376,7 @@ impl<'tcx> Body<'tcx> {
             var_debug_info: Vec::new(),
             is_polymorphic: false,
             predecessor_cache: PredecessorCache::new(),
+            switch_source_cache: SwitchSourceCache::new(),
             is_cyclic: GraphIsCyclicCache::new(),
             tainted_by_errors: None,
         };
@@ -392,6 +397,7 @@ impl<'tcx> Body<'tcx> {
         // FIXME: Use a finer-grained API for this, so only transformations that alter terminators
         // invalidate the caches.
         self.predecessor_cache.invalidate();
+        self.switch_source_cache.invalidate();
         self.is_cyclic.invalidate();
         &mut self.basic_blocks
     }
@@ -401,6 +407,7 @@ impl<'tcx> Body<'tcx> {
         &mut self,
     ) -> (&mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, &mut LocalDecls<'tcx>) {
         self.predecessor_cache.invalidate();
+        self.switch_source_cache.invalidate();
         self.is_cyclic.invalidate();
         (&mut self.basic_blocks, &mut self.local_decls)
     }
@@ -414,6 +421,7 @@ impl<'tcx> Body<'tcx> {
         &mut Vec<VarDebugInfo<'tcx>>,
     ) {
         self.predecessor_cache.invalidate();
+        self.switch_source_cache.invalidate();
         self.is_cyclic.invalidate();
         (&mut self.basic_blocks, &mut self.local_decls, &mut self.var_debug_info)
     }
@@ -542,6 +550,11 @@ impl<'tcx> Body<'tcx> {
     }
 
     #[inline]
+    pub fn switch_sources(&self) -> &SwitchSources {
+        self.switch_source_cache.compute(&self.basic_blocks)
+    }
+
+    #[inline]
     pub fn dominators(&self) -> Dominators<BasicBlock> {
         dominators(self)
     }
diff --git a/compiler/rustc_middle/src/mir/switch_sources.rs b/compiler/rustc_middle/src/mir/switch_sources.rs
new file mode 100644
index 00000000000..7f62b4d0dba
--- /dev/null
+++ b/compiler/rustc_middle/src/mir/switch_sources.rs
@@ -0,0 +1,82 @@
+//! Lazily compute the inverse of each `SwitchInt`'s switch targets. Modeled after
+//! `Predecessors`/`PredecessorCache`.
+
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
+use rustc_data_structures::sync::OnceCell;
+use rustc_index::vec::IndexVec;
+use rustc_serialize as serialize;
+use smallvec::SmallVec;
+
+use crate::mir::{BasicBlock, BasicBlockData, Terminator, TerminatorKind};
+
+pub type SwitchSources = IndexVec<BasicBlock, IndexVec<BasicBlock, SmallVec<[Option<u128>; 1]>>>;
+
+#[derive(Clone, Debug)]
+pub(super) struct SwitchSourceCache {
+    cache: OnceCell<SwitchSources>,
+}
+
+impl SwitchSourceCache {
+    #[inline]
+    pub(super) fn new() -> Self {
+        SwitchSourceCache { cache: OnceCell::new() }
+    }
+
+    /// Invalidates the switch source cache.
+    #[inline]
+    pub(super) fn invalidate(&mut self) {
+        self.cache = OnceCell::new();
+    }
+
+    /// Returns the switch sources for this MIR.
+    #[inline]
+    pub(super) fn compute(
+        &self,
+        basic_blocks: &IndexVec<BasicBlock, BasicBlockData<'_>>,
+    ) -> &SwitchSources {
+        self.cache.get_or_init(|| {
+            let mut switch_sources = IndexVec::from_elem(
+                IndexVec::from_elem(SmallVec::new(), basic_blocks),
+                basic_blocks,
+            );
+            for (bb, data) in basic_blocks.iter_enumerated() {
+                if let Some(Terminator {
+                    kind: TerminatorKind::SwitchInt { targets, .. }, ..
+                }) = &data.terminator
+                {
+                    for (value, target) in targets.iter() {
+                        switch_sources[target][bb].push(Some(value));
+                    }
+                    switch_sources[targets.otherwise()][bb].push(None);
+                }
+            }
+
+            switch_sources
+        })
+    }
+}
+
+impl<S: serialize::Encoder> serialize::Encodable<S> for SwitchSourceCache {
+    #[inline]
+    fn encode(&self, s: &mut S) -> Result<(), S::Error> {
+        s.emit_unit()
+    }
+}
+
+impl<D: serialize::Decoder> serialize::Decodable<D> for SwitchSourceCache {
+    #[inline]
+    fn decode(_: &mut D) -> Self {
+        Self::new()
+    }
+}
+
+impl<CTX> HashStable<CTX> for SwitchSourceCache {
+    #[inline]
+    fn hash_stable(&self, _: &mut CTX, _: &mut StableHasher) {
+        // do nothing
+    }
+}
+
+TrivialTypeFoldableAndLiftImpls! {
+    SwitchSourceCache,
+}