src/librustc/mir/cache.rs

   1 use crate::ich::StableHashingContext;
   2 use crate::mir::{BasicBlock, BasicBlockData, Body, LocalDecls, Location, Successors};
   3 use rustc_data_structures::graph::dominators::{dominators, Dominators};
   4 use rustc_data_structures::graph::{self, GraphPredecessors, GraphSuccessors};
   5 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
   6 use rustc_index::vec::IndexVec;
   7 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
   8 use std::iter;
   9 use std::ops::{Deref, DerefMut, Index, IndexMut};
  10 use std::vec::IntoIter;
  11
  12 #[derive(Clone, Debug)]
  13 pub struct Cache {
  14     predecessors: Option<IndexVec<BasicBlock, Vec<BasicBlock>>>,
  15 }
  16
  17 impl rustc_serialize::Encodable for Cache {
  18     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
  19         Encodable::encode(&(), s)
  20     }
  21 }
  22
  23 impl rustc_serialize::Decodable for Cache {
  24     fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> {
  25         Decodable::decode(d).map(|_v: ()| Self::new())
  26     }
  27 }
  28
  29 impl<'a> HashStable<StableHashingContext<'a>> for Cache {
  30     fn hash_stable(&self, _: &mut StableHashingContext<'a>, _: &mut StableHasher) {
  31         // Do nothing.
  32     }
  33 }
  34
  35 impl Cache {
  36     pub fn new() -> Self {
  37         Self { predecessors: None }
  38     }
  39
  40     pub fn invalidate_predecessors(&mut self) {
  41         // FIXME: consider being more fine-grained
  42         self.predecessors = None;
  43     }
  44
  45     pub fn ensure_predecessors(&mut self, body: &Body<'_>) {
  46         if self.predecessors.is_none() {
  47             let mut result = IndexVec::from_elem(vec![], body.basic_blocks());
  48             for (bb, data) in body.basic_blocks().iter_enumerated() {
  49                 if let Some(ref term) = data.terminator {
  50                     for &tgt in term.successors() {
  51                         result[tgt].push(bb);
  52                     }
  53                 }
  54             }
  55
  56             self.predecessors = Some(result)
  57         }
  58     }
  59
  60     /// This will recompute the predecessors cache if it is not available
  61     fn predecessors(&mut self, body: &Body<'_>) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
  62         self.ensure_predecessors(body);
  63         self.predecessors.as_ref().unwrap()
  64     }
  65
  66     fn unwrap_predecessors_for(&self, bb: BasicBlock) -> &[BasicBlock] {
  67         &self.predecessors.as_ref().unwrap()[bb]
  68     }
  69
  70     fn unwrap_predecessor_locations<'a>(
  71         &'a self,
  72         loc: Location,
  73         body: &'a Body<'a>,
  74     ) -> impl Iterator<Item = Location> + 'a {
  75         let if_zero_locations = if loc.statement_index == 0 {
  76             let predecessor_blocks = self.unwrap_predecessors_for(loc.block);
  77             let num_predecessor_blocks = predecessor_blocks.len();
  78             Some(
  79                 (0..num_predecessor_blocks)
  80                     .map(move |i| predecessor_blocks[i])
  81                     .map(move |bb| body.terminator_loc(bb)),
  82             )
  83         } else {
  84             None
  85         };
  86
  87         let if_not_zero_locations = if loc.statement_index == 0 {
  88             None
  89         } else {
  90             Some(Location { block: loc.block, statement_index: loc.statement_index - 1 })
  91         };
  92
  93         if_zero_locations.into_iter().flatten().chain(if_not_zero_locations)
  94     }
  95
  96     pub fn basic_blocks_mut<'a, 'tcx>(
  97         &mut self,
  98         body: &'a mut Body<'tcx>,
  99     ) -> &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 100         debug!("bbm: Clearing predecessors cache for body at: {:?}", body.span.data());
 101         self.invalidate_predecessors();
 102         &mut body.basic_blocks
 103     }
 104
 105     pub fn basic_blocks_and_local_decls_mut<'a, 'tcx>(
 106         &mut self,
 107         body: &'a mut Body<'tcx>,
 108     ) -> (&'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, &'a mut LocalDecls<'tcx>) {
 109         debug!("bbaldm: Clearing predecessors cache for body at: {:?}", body.span.data());
 110         self.invalidate_predecessors();
 111         (&mut body.basic_blocks, &mut body.local_decls)
 112     }
 113 }
 114
 115 #[derive(Clone, Debug, HashStable, RustcEncodable, RustcDecodable, TypeFoldable)]
 116 pub struct BodyAndCache<'tcx> {
 117     body: Body<'tcx>,
 118     cache: Cache,
 119 }
 120
 121 impl BodyAndCache<'tcx> {
 122     pub fn new(body: Body<'tcx>) -> Self {
 123         Self { body, cache: Cache::new() }
 124     }
 125 }
 126
 127 #[macro_export]
 128 macro_rules! read_only {
 129     ($body:expr) => {{
 130         $body.ensure_predecessors();
 131         $body.unwrap_read_only()
 132     }};
 133 }
 134
 135 impl BodyAndCache<'tcx> {
 136     pub fn ensure_predecessors(&mut self) {
 137         self.cache.ensure_predecessors(&self.body);
 138     }
 139
 140     pub fn predecessors(&mut self) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
 141         self.cache.predecessors(&self.body)
 142     }
 143
 144     pub fn unwrap_read_only(&self) -> ReadOnlyBodyAndCache<'_, 'tcx> {
 145         ReadOnlyBodyAndCache::new(&self.body, &self.cache)
 146     }
 147
 148     pub fn basic_blocks_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 149         self.cache.basic_blocks_mut(&mut self.body)
 150     }
 151
 152     pub fn basic_blocks_and_local_decls_mut(
 153         &mut self,
 154     ) -> (&mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, &mut LocalDecls<'tcx>) {
 155         self.cache.basic_blocks_and_local_decls_mut(&mut self.body)
 156     }
 157 }
 158
 159 impl<'tcx> Index<BasicBlock> for BodyAndCache<'tcx> {
 160     type Output = BasicBlockData<'tcx>;
 161
 162     fn index(&self, index: BasicBlock) -> &BasicBlockData<'tcx> {
 163         &self.body[index]
 164     }
 165 }
 166
 167 impl<'tcx> IndexMut<BasicBlock> for BodyAndCache<'tcx> {
 168     fn index_mut(&mut self, index: BasicBlock) -> &mut Self::Output {
 169         &mut self.basic_blocks_mut()[index]
 170     }
 171 }
 172
 173 impl<'tcx> Deref for BodyAndCache<'tcx> {
 174     type Target = Body<'tcx>;
 175
 176     fn deref(&self) -> &Self::Target {
 177         &self.body
 178     }
 179 }
 180
 181 impl<'tcx> DerefMut for BodyAndCache<'tcx> {
 182     fn deref_mut(&mut self) -> &mut Self::Target {
 183         &mut self.body
 184     }
 185 }
 186
 187 #[derive(Copy, Clone, Debug)]
 188 pub struct ReadOnlyBodyAndCache<'a, 'tcx> {
 189     body: &'a Body<'tcx>,
 190     cache: &'a Cache,
 191 }
 192
 193 impl ReadOnlyBodyAndCache<'a, 'tcx> {
 194     fn new(body: &'a Body<'tcx>, cache: &'a Cache) -> Self {
 195         assert!(
 196             cache.predecessors.is_some(),
 197             "Cannot construct ReadOnlyBodyAndCache without computed predecessors"
 198         );
 199         Self { body, cache }
 200     }
 201
 202     pub fn predecessors(&self) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
 203         self.cache.predecessors.as_ref().unwrap()
 204     }
 205
 206     pub fn predecessors_for(&self, bb: BasicBlock) -> &[BasicBlock] {
 207         self.cache.unwrap_predecessors_for(bb)
 208     }
 209
 210     pub fn predecessor_locations(&self, loc: Location) -> impl Iterator<Item = Location> + '_ {
 211         self.cache.unwrap_predecessor_locations(loc, self.body)
 212     }
 213
 214     pub fn basic_blocks(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 215         &self.body.basic_blocks
 216     }
 217
 218     pub fn dominators(&self) -> Dominators<BasicBlock> {
 219         dominators(self)
 220     }
 221 }
 222
 223 impl graph::DirectedGraph for ReadOnlyBodyAndCache<'a, 'tcx> {
 224     type Node = BasicBlock;
 225 }
 226
 227 impl graph::GraphPredecessors<'graph> for ReadOnlyBodyAndCache<'a, 'tcx> {
 228     type Item = BasicBlock;
 229     type Iter = IntoIter<BasicBlock>;
 230 }
 231
 232 impl graph::WithPredecessors for ReadOnlyBodyAndCache<'a, 'tcx> {
 233     fn predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter {
 234         self.cache.unwrap_predecessors_for(node).to_vec().into_iter()
 235     }
 236 }
 237
 238 impl graph::WithNumNodes for ReadOnlyBodyAndCache<'a, 'tcx> {
 239     fn num_nodes(&self) -> usize {
 240         self.body.num_nodes()
 241     }
 242 }
 243
 244 impl graph::WithStartNode for ReadOnlyBodyAndCache<'a, 'tcx> {
 245     fn start_node(&self) -> Self::Node {
 246         self.body.start_node()
 247     }
 248 }
 249
 250 impl graph::WithSuccessors for ReadOnlyBodyAndCache<'a, 'tcx> {
 251     fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter {
 252         self.body.successors(node)
 253     }
 254 }
 255
 256 impl<'a, 'b, 'tcx> graph::GraphSuccessors<'b> for ReadOnlyBodyAndCache<'a, 'tcx> {
 257     type Item = BasicBlock;
 258     type Iter = iter::Cloned<Successors<'b>>;
 259 }
 260
 261 impl Deref for ReadOnlyBodyAndCache<'a, 'tcx> {
 262     type Target = &'a Body<'tcx>;
 263
 264     fn deref(&self) -> &Self::Target {
 265         &self.body
 266     }
 267 }
 268
 269 CloneTypeFoldableAndLiftImpls! {
 270     Cache,
 271 }