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};
9 use std::ops::{Deref, DerefMut, Index, IndexMut};
10 use std::vec::IntoIter;
12 #[derive(Clone, Debug)]
14 predecessors: Option<IndexVec<BasicBlock, Vec<BasicBlock>>>,
17 impl rustc_serialize::Encodable for Cache {
18 fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
19 Encodable::encode(&(), s)
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())
29 impl<'a> HashStable<StableHashingContext<'a>> for Cache {
30 fn hash_stable(&self, _: &mut StableHashingContext<'a>, _: &mut StableHasher) {
36 pub fn new() -> Self {
37 Self { predecessors: None }
40 pub fn invalidate_predecessors(&mut self) {
41 // FIXME: consider being more fine-grained
42 self.predecessors = None;
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() {
56 self.predecessors = Some(result)
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()
66 fn unwrap_predecessors_for(&self, bb: BasicBlock) -> &[BasicBlock] {
67 &self.predecessors.as_ref().unwrap()[bb]
70 fn unwrap_predecessor_locations<'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();
79 (0..num_predecessor_blocks)
80 .map(move |i| predecessor_blocks[i])
81 .map(move |bb| body.terminator_loc(bb)),
87 let if_not_zero_locations = if loc.statement_index == 0 {
90 Some(Location { block: loc.block, statement_index: loc.statement_index - 1 })
93 if_zero_locations.into_iter().flatten().chain(if_not_zero_locations)
96 pub fn basic_blocks_mut<'a, 'tcx>(
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
105 pub fn basic_blocks_and_local_decls_mut<'a, 'tcx>(
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)
115 #[derive(Clone, Debug, HashStable, RustcEncodable, RustcDecodable, TypeFoldable)]
116 pub struct BodyAndCache<'tcx> {
121 impl BodyAndCache<'tcx> {
122 pub fn new(body: Body<'tcx>) -> Self {
123 Self { body, cache: Cache::new() }
128 macro_rules! read_only {
130 $body.ensure_predecessors();
131 $body.unwrap_read_only()
135 impl BodyAndCache<'tcx> {
136 pub fn ensure_predecessors(&mut self) {
137 self.cache.ensure_predecessors(&self.body);
140 pub fn predecessors(&mut self) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
141 self.cache.predecessors(&self.body)
144 pub fn unwrap_read_only(&self) -> ReadOnlyBodyAndCache<'_, 'tcx> {
145 ReadOnlyBodyAndCache::new(&self.body, &self.cache)
148 pub fn basic_blocks_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
149 self.cache.basic_blocks_mut(&mut self.body)
152 pub fn basic_blocks_and_local_decls_mut(
154 ) -> (&mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, &mut LocalDecls<'tcx>) {
155 self.cache.basic_blocks_and_local_decls_mut(&mut self.body)
159 impl<'tcx> Index<BasicBlock> for BodyAndCache<'tcx> {
160 type Output = BasicBlockData<'tcx>;
162 fn index(&self, index: BasicBlock) -> &BasicBlockData<'tcx> {
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]
173 impl<'tcx> Deref for BodyAndCache<'tcx> {
174 type Target = Body<'tcx>;
176 fn deref(&self) -> &Self::Target {
181 impl<'tcx> DerefMut for BodyAndCache<'tcx> {
182 fn deref_mut(&mut self) -> &mut Self::Target {
187 #[derive(Copy, Clone, Debug)]
188 pub struct ReadOnlyBodyAndCache<'a, 'tcx> {
189 body: &'a Body<'tcx>,
193 impl ReadOnlyBodyAndCache<'a, 'tcx> {
194 fn new(body: &'a Body<'tcx>, cache: &'a Cache) -> Self {
196 cache.predecessors.is_some(),
197 "Cannot construct ReadOnlyBodyAndCache without computed predecessors"
202 pub fn predecessors(&self) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
203 self.cache.predecessors.as_ref().unwrap()
206 pub fn predecessors_for(&self, bb: BasicBlock) -> &[BasicBlock] {
207 self.cache.unwrap_predecessors_for(bb)
210 pub fn predecessor_locations(&self, loc: Location) -> impl Iterator<Item = Location> + '_ {
211 self.cache.unwrap_predecessor_locations(loc, self.body)
214 pub fn basic_blocks(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
215 &self.body.basic_blocks
218 pub fn dominators(&self) -> Dominators<BasicBlock> {
223 impl graph::DirectedGraph for ReadOnlyBodyAndCache<'a, 'tcx> {
224 type Node = BasicBlock;
227 impl graph::GraphPredecessors<'graph> for ReadOnlyBodyAndCache<'a, 'tcx> {
228 type Item = BasicBlock;
229 type Iter = IntoIter<BasicBlock>;
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()
238 impl graph::WithNumNodes for ReadOnlyBodyAndCache<'a, 'tcx> {
239 fn num_nodes(&self) -> usize {
240 self.body.num_nodes()
244 impl graph::WithStartNode for ReadOnlyBodyAndCache<'a, 'tcx> {
245 fn start_node(&self) -> Self::Node {
246 self.body.start_node()
250 impl graph::WithSuccessors for ReadOnlyBodyAndCache<'a, 'tcx> {
251 fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter {
252 self.body.successors(node)
256 impl<'a, 'b, 'tcx> graph::GraphSuccessors<'b> for ReadOnlyBodyAndCache<'a, 'tcx> {
257 type Item = BasicBlock;
258 type Iter = iter::Cloned<Successors<'b>>;
261 impl Deref for ReadOnlyBodyAndCache<'a, 'tcx> {
262 type Target = &'a Body<'tcx>;
264 fn deref(&self) -> &Self::Target {
269 CloneTypeFoldableAndLiftImpls! {