1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
12 Managing the scope stack. The scopes are tied to lexical scopes, so as
13 we descend the HAIR, we push a scope on the stack, translate ite
14 contents, and then pop it off. Every scope is named by a
19 When pushing a new scope, we record the current point in the graph (a
20 basic block); this marks the entry to the scope. We then generate more
21 stuff in the control-flow graph. Whenever the scope is exited, either
22 via a `break` or `return` or just by fallthrough, that marks an exit
23 from the scope. Each lexical scope thus corresponds to a single-entry,
24 multiple-exit (SEME) region in the control-flow graph.
26 For now, we keep a mapping from each `CodeExtent` to its
27 corresponding SEME region for later reference (see caveat in next
28 paragraph). This is because region scopes are tied to
29 them. Eventually, when we shift to non-lexical lifetimes, three should
30 be no need to remember this mapping.
32 There is one additional wrinkle, actually, that I wanted to hide from
33 you but duty compels me to mention. In the course of translating
34 matches, it sometimes happen that certain code (namely guards) gets
35 executed multiple times. This means that the scope lexical scope may
36 in fact correspond to multiple, disjoint SEME regions. So in fact our
37 mapping is from one scope to a vector of SEME regions.
41 The primary purpose for scopes is to insert drops: while translating
42 the contents, we also accumulate lvalues that need to be dropped upon
43 exit from each scope. This is done by calling `schedule_drop`. Once a
44 drop is scheduled, whenever we branch out we will insert drops of all
45 those lvalues onto the outgoing edge. Note that we don't know the full
46 set of scheduled drops up front, and so whenever we exit from the
47 scope we only drop the values scheduled thus far. For example, consider
48 the scope S corresponding to this loop:
58 When processing the `let x`, we will add one drop to the scope for
59 `x`. The break will then insert a drop for `x`. When we process `let
60 y`, we will add another drop (in fact, to a subscope, but let's ignore
61 that for now); any later drops would also drop `y`.
65 There are numerous "normal" ways to early exit a scope: `break`,
66 `continue`, `return` (panics are handled separately). Whenever an
67 early exit occurs, the method `exit_scope` is called. It is given the
68 current point in execution where the early exit occurs, as well as the
69 scope you want to branch to (note that all early exits from to some
70 other enclosing scope). `exit_scope` will record thid exit point and
73 Panics are handled in a similar fashion, except that a panic always
74 returns out to the `DIVERGE_BLOCK`. To trigger a panic, simply call
75 `panic(p)` with the current point `p`. Or else you can call
76 `diverge_cleanup`, which will produce a block that you can branch to
77 which does the appropriate cleanup and then diverges. `panic(p)`
78 simply calls `diverge_cleanup()` and adds an edge from `p` to the
83 In addition to the normal scope stack, we track a loop scope stack
84 that contains only loops. It tracks where a `break` and `continue`
89 use build::{BlockAnd, BlockAndExtension, Builder, CFG, ScopeAuxiliary};
90 use rustc::middle::region::CodeExtent;
91 use rustc::middle::lang_items;
92 use rustc::middle::subst::{Substs, Subst, VecPerParamSpace};
93 use rustc::middle::ty::{self, Ty, TyCtxt};
94 use rustc::mir::repr::*;
95 use syntax::codemap::{Span, DUMMY_SP};
96 use syntax::parse::token::intern_and_get_ident;
97 use rustc::middle::const_eval::ConstVal;
98 use rustc_const_eval::ConstInt;
100 pub struct Scope<'tcx> {
101 // the scope-id within the scope_data_vec
104 drops: Vec<DropData<'tcx>>,
106 // A scope may only have one associated free, because:
107 // 1. We require a `free` to only be scheduled in the scope of `EXPR` in `box EXPR`;
108 // 2. It only makes sense to have it translated into the diverge-path.
110 // This kind of drop will be run *after* all the regular drops scheduled onto this scope,
111 // because drops may have dependencies on the allocated memory.
113 // This is expected to go away once `box EXPR` becomes a sugar for placement protocol and gets
114 // desugared in some earlier stage.
115 free: Option<FreeData<'tcx>>,
118 struct DropData<'tcx> {
120 // NB: per-drop “cache” is necessary for the build_scope_drops function below.
121 /// The cached block for the cleanups-on-diverge path. This block contains code to run the
122 /// current drop and all the preceding drops (i.e. those having lower index in Drop’s
123 /// Scope drop array)
124 cached_block: Option<BasicBlock>
127 struct FreeData<'tcx> {
129 /// Lvalue containing the allocated box.
131 /// type of item for which the box was allocated for (i.e. the T in Box<T>).
133 /// The cached block containing code to run the free. The block will also execute all the drops
135 cached_block: Option<BasicBlock>
138 #[derive(Clone, Debug)]
139 pub struct LoopScope {
140 /// Extent of the loop
141 pub extent: CodeExtent,
142 /// Where the body of the loop begins
143 pub continue_block: BasicBlock,
144 /// Block to branch into when the loop terminates (either by being `break`-en out from, or by
145 /// having its condition to become false)
146 pub break_block: BasicBlock, // where to go on a `break
147 /// Indicates the reachability of the break_block for this loop
148 pub might_break: bool
151 impl<'tcx> Scope<'tcx> {
152 /// Invalidate all the cached blocks in the scope.
154 /// Should always be run for all inner scopes when a drop is pushed into some scope enclosing a
155 /// larger extent of code.
156 fn invalidate_cache(&mut self) {
157 for dropdata in &mut self.drops {
158 dropdata.cached_block = None;
160 if let Some(ref mut freedata) = self.free {
161 freedata.cached_block = None;
165 /// Returns the cached block for this scope.
167 /// Precondition: the caches must be fully filled (i.e. diverge_cleanup is called) in order for
168 /// this method to work correctly.
169 fn cached_block(&self) -> Option<BasicBlock> {
170 if let Some(data) = self.drops.last() {
171 Some(data.cached_block.expect("drop cache is not filled"))
172 } else if let Some(ref data) = self.free {
173 Some(data.cached_block.expect("free cache is not filled"))
180 impl<'a,'tcx> Builder<'a,'tcx> {
181 // Adding and removing scopes
182 // ==========================
183 /// Start a loop scope, which tracks where `continue` and `break`
184 /// should branch to. See module comment for more details.
186 /// Returns the might_break attribute of the LoopScope used.
187 pub fn in_loop_scope<F>(&mut self,
188 loop_block: BasicBlock,
189 break_block: BasicBlock,
192 where F: FnOnce(&mut Builder<'a, 'tcx>)
194 let extent = self.extent_of_innermost_scope();
195 let loop_scope = LoopScope {
196 extent: extent.clone(),
197 continue_block: loop_block,
198 break_block: break_block,
201 self.loop_scopes.push(loop_scope);
203 let loop_scope = self.loop_scopes.pop().unwrap();
204 assert!(loop_scope.extent == extent);
205 loop_scope.might_break
208 /// Convenience wrapper that pushes a scope and then executes `f`
209 /// to build its contents, popping the scope afterwards.
210 pub fn in_scope<F, R>(&mut self, extent: CodeExtent, mut block: BasicBlock, f: F) -> BlockAnd<R>
211 where F: FnOnce(&mut Builder<'a, 'tcx>, ScopeId) -> BlockAnd<R>
213 debug!("in_scope(extent={:?}, block={:?})", extent, block);
214 let id = self.push_scope(extent, block);
215 let rv = unpack!(block = f(self, id));
216 unpack!(block = self.pop_scope(extent, block));
217 debug!("in_scope: exiting extent={:?} block={:?}", extent, block);
221 /// Push a scope onto the stack. You can then build code in this
222 /// scope and call `pop_scope` afterwards. Note that these two
223 /// calls must be paired; using `in_scope` as a convenience
224 /// wrapper maybe preferable.
225 pub fn push_scope(&mut self, extent: CodeExtent, entry: BasicBlock) -> ScopeId {
226 debug!("push_scope({:?})", extent);
227 let parent_id = self.scopes.last().map(|s| s.id);
228 let id = ScopeId::new(self.scope_data_vec.vec.len());
229 self.scope_data_vec.vec.push(ScopeData {
230 parent_scope: parent_id,
232 self.scopes.push(Scope {
238 self.scope_auxiliary.push(ScopeAuxiliary {
240 dom: self.cfg.current_location(entry),
246 /// Pops a scope, which should have extent `extent`, adding any
247 /// drops onto the end of `block` that are needed. This must
248 /// match 1-to-1 with `push_scope`.
249 pub fn pop_scope(&mut self,
251 mut block: BasicBlock)
253 debug!("pop_scope({:?}, {:?})", extent, block);
254 // We need to have `cached_block`s available for all the drops, so we call diverge_cleanup
255 // to make sure all the `cached_block`s are filled in.
256 self.diverge_cleanup();
257 let scope = self.scopes.pop().unwrap();
258 assert_eq!(scope.extent, extent);
259 unpack!(block = build_scope_drops(&mut self.cfg, &scope, &self.scopes, block));
260 self.scope_auxiliary[scope.id.index()]
262 .push(self.cfg.current_location(block));
267 /// Branch out of `block` to `target`, exiting all scopes up to
268 /// and including `extent`. This will insert whatever drops are
269 /// needed, as well as tracking this exit for the SEME region. See
270 /// module comment for details.
271 pub fn exit_scope(&mut self,
274 mut block: BasicBlock,
275 target: BasicBlock) {
276 debug!("exit_scope(extent={:?}, block={:?}, target={:?})", extent, block, target);
277 let scope_count = 1 + self.scopes.iter().rev().position(|scope| scope.extent == extent)
279 self.hir.span_bug(span, &format!("extent {:?} does not enclose", extent))
282 let tmp = self.get_unit_temp();
283 for (idx, ref scope) in self.scopes.iter().enumerate().rev().take(scope_count) {
284 unpack!(block = build_scope_drops(&mut self.cfg,
288 if let Some(ref free_data) = scope.free {
289 let next = self.cfg.start_new_block();
290 let free = build_free(self.hir.tcx(), tmp.clone(), free_data, next);
291 self.cfg.terminate(block, free);
294 self.scope_auxiliary[scope.id.index()]
296 .push(self.cfg.current_location(block));
298 self.cfg.terminate(block, Terminator::Goto { target: target });
303 /// Finds the loop scope for a given label. This is used for
304 /// resolving `break` and `continue`.
305 pub fn find_loop_scope(&mut self,
307 label: Option<CodeExtent>)
309 let Builder { ref mut loop_scopes, ref mut hir, .. } = *self;
312 // no label? return the innermost loop scope
313 loop_scopes.iter_mut().rev().next()
316 // otherwise, find the loop-scope with the correct id
317 loop_scopes.iter_mut()
319 .filter(|loop_scope| loop_scope.extent == label)
322 }.unwrap_or_else(|| hir.span_bug(span, "no enclosing loop scope found?"))
325 pub fn innermost_scope_id(&self) -> ScopeId {
326 self.scopes.last().map(|scope| scope.id).unwrap()
329 pub fn extent_of_innermost_scope(&self) -> CodeExtent {
330 self.scopes.last().map(|scope| scope.extent).unwrap()
333 pub fn extent_of_outermost_scope(&self) -> CodeExtent {
334 self.scopes.first().map(|scope| scope.extent).unwrap()
339 /// Indicates that `lvalue` should be dropped on exit from
341 pub fn schedule_drop(&mut self,
344 lvalue: &Lvalue<'tcx>,
345 lvalue_ty: Ty<'tcx>) {
346 if !self.hir.needs_drop(lvalue_ty) {
349 for scope in self.scopes.iter_mut().rev() {
350 if scope.extent == extent {
351 // No need to invalidate any caches here. The just-scheduled drop will branch into
352 // the drop that comes before it in the vector.
353 scope.drops.push(DropData {
354 value: lvalue.clone(),
359 // We must invalidate all the cached_blocks leading up to the scope we’re
360 // looking for, because all of the blocks in the chain will become incorrect.
361 scope.invalidate_cache()
364 self.hir.span_bug(span,
365 &format!("extent {:?} not in scope to drop {:?}", extent, lvalue));
368 /// Schedule dropping of a not-yet-fully-initialised box.
370 /// This cleanup will only be translated into unwind branch.
371 /// The extent should be for the `EXPR` inside `box EXPR`.
372 /// There may only be one “free” scheduled in any given scope.
373 pub fn schedule_box_free(&mut self,
376 value: &Lvalue<'tcx>,
378 for scope in self.scopes.iter_mut().rev() {
379 if scope.extent == extent {
380 assert!(scope.free.is_none(), "scope already has a scheduled free!");
381 // We also must invalidate the caches in the scope for which the free is scheduled
382 // because the drops must branch into the free we schedule here.
383 scope.invalidate_cache();
384 scope.free = Some(FreeData {
386 value: value.clone(),
392 // We must invalidate all the cached_blocks leading up to the scope we’re looking
393 // for, because otherwise some/most of the blocks in the chain will become
395 scope.invalidate_cache();
398 self.hir.span_bug(span,
399 &format!("extent {:?} not in scope to free {:?}", extent, value));
404 /// Creates a path that performs all required cleanup for unwinding.
406 /// This path terminates in Resume. Returns the start of the path.
407 /// See module comment for more details. None indicates there’s no
408 /// cleanup to do at this point.
409 pub fn diverge_cleanup(&mut self) -> Option<BasicBlock> {
410 if self.scopes.is_empty() {
413 let unit_temp = self.get_unit_temp();
414 let Builder { ref mut hir, ref mut cfg, ref mut scopes, .. } = *self;
415 let mut next_block = None;
417 // Given an array of scopes, we generate these from the outermost scope to the innermost
418 // one. Thus for array [S0, S1, S2] with corresponding cleanup blocks [B0, B1, B2], we will
419 // generate B0 <- B1 <- B2 in left-to-right order. Control flow of the generated blocks
420 // always ends up at a block with the Resume terminator.
421 for scope in scopes.iter_mut().filter(|s| !s.drops.is_empty() || s.free.is_some()) {
422 next_block = Some(build_diverge_scope(hir.tcx(),
428 scopes.iter().rev().flat_map(|x| x.cached_block()).next()
431 /// Utility function for *non*-scope code to build their own drops
432 pub fn build_drop(&mut self, block: BasicBlock, value: Lvalue<'tcx>) -> BlockAnd<()> {
433 let next_target = self.cfg.start_new_block();
434 let diverge_target = self.diverge_cleanup();
435 self.cfg.terminate(block, Terminator::Drop {
438 unwind: diverge_target,
446 // FIXME: should be moved into their own module
447 pub fn panic_bounds_check(&mut self,
449 index: Operand<'tcx>,
452 // fn(&(filename: &'static str, line: u32), index: usize, length: usize) -> !
453 let region = ty::ReStatic; // FIXME(mir-borrowck): use a better region?
454 let func = self.lang_function(lang_items::PanicBoundsCheckFnLangItem);
455 let args = self.hir.tcx().replace_late_bound_regions(&func.ty.fn_args(), |_| region).0;
457 let ref_ty = args[0];
458 let tup_ty = if let ty::TyRef(_, tyandmut) = ref_ty.sty {
461 self.hir.span_bug(span, &format!("unexpected panic_bound_check type: {:?}", func.ty));
464 let (tuple, tuple_ref) = (self.temp(tup_ty), self.temp(ref_ty));
465 let (file, line) = self.span_to_fileline_args(span);
466 let elems = vec![Operand::Constant(file), Operand::Constant(line)];
467 let scope_id = self.innermost_scope_id();
468 // FIXME: We should have this as a constant, rather than a stack variable (to not pollute
469 // icache with cold branch code), however to achieve that we either have to rely on rvalue
470 // promotion or have some way, in MIR, to create constants.
471 self.cfg.push_assign(block, scope_id, span, &tuple, // tuple = (file_arg, line_arg);
472 Rvalue::Aggregate(AggregateKind::Tuple, elems));
473 // FIXME: is this region really correct here?
474 self.cfg.push_assign(block, scope_id, span, &tuple_ref, // tuple_ref = &tuple;
475 Rvalue::Ref(region, BorrowKind::Shared, tuple));
476 let cleanup = self.diverge_cleanup();
477 self.cfg.terminate(block, Terminator::Call {
478 func: Operand::Constant(func),
479 args: vec![Operand::Consume(tuple_ref), index, len],
485 /// Create diverge cleanup and branch to it from `block`.
486 pub fn panic(&mut self, block: BasicBlock, msg: &'static str, span: Span) {
487 // fn(&(msg: &'static str filename: &'static str, line: u32)) -> !
488 let region = ty::ReStatic; // FIXME(mir-borrowck): use a better region?
489 let func = self.lang_function(lang_items::PanicFnLangItem);
490 let args = self.hir.tcx().replace_late_bound_regions(&func.ty.fn_args(), |_| region).0;
492 let ref_ty = args[0];
493 let tup_ty = if let ty::TyRef(_, tyandmut) = ref_ty.sty {
496 self.hir.span_bug(span, &format!("unexpected panic type: {:?}", func.ty));
499 let (tuple, tuple_ref) = (self.temp(tup_ty), self.temp(ref_ty));
500 let (file, line) = self.span_to_fileline_args(span);
501 let message = Constant {
503 ty: self.hir.tcx().mk_static_str(),
504 literal: self.hir.str_literal(intern_and_get_ident(msg))
506 let elems = vec![Operand::Constant(message),
507 Operand::Constant(file),
508 Operand::Constant(line)];
509 let scope_id = self.innermost_scope_id();
510 // FIXME: We should have this as a constant, rather than a stack variable (to not pollute
511 // icache with cold branch code), however to achieve that we either have to rely on rvalue
512 // promotion or have some way, in MIR, to create constants.
513 self.cfg.push_assign(block, scope_id, span, &tuple, // tuple = (message_arg, file_arg, line_arg);
514 Rvalue::Aggregate(AggregateKind::Tuple, elems));
515 // FIXME: is this region really correct here?
516 self.cfg.push_assign(block, scope_id, span, &tuple_ref, // tuple_ref = &tuple;
517 Rvalue::Ref(region, BorrowKind::Shared, tuple));
518 let cleanup = self.diverge_cleanup();
519 self.cfg.terminate(block, Terminator::Call {
520 func: Operand::Constant(func),
521 args: vec![Operand::Consume(tuple_ref)],
527 fn lang_function(&mut self, lang_item: lang_items::LangItem) -> Constant<'tcx> {
528 let funcdid = match self.hir.tcx().lang_items.require(lang_item) {
531 self.hir.tcx().sess.fatal(&m)
536 ty: self.hir.tcx().lookup_item_type(funcdid).ty,
537 literal: Literal::Item {
539 substs: self.hir.tcx().mk_substs(Substs::empty())
544 fn span_to_fileline_args(&mut self, span: Span) -> (Constant<'tcx>, Constant<'tcx>) {
545 let span_lines = self.hir.tcx().sess.codemap().lookup_char_pos(span.lo);
548 ty: self.hir.tcx().mk_static_str(),
549 literal: self.hir.str_literal(intern_and_get_ident(&span_lines.file.name))
552 ty: self.hir.tcx().types.u32,
553 literal: Literal::Value {
554 value: ConstVal::Integral(ConstInt::U32(span_lines.line as u32)),
561 /// Builds drops for pop_scope and exit_scope.
562 fn build_scope_drops<'tcx>(cfg: &mut CFG<'tcx>,
564 earlier_scopes: &[Scope<'tcx>],
565 mut block: BasicBlock)
567 let mut iter = scope.drops.iter().rev().peekable();
568 while let Some(drop_data) = iter.next() {
569 // Try to find the next block with its cached block for us to diverge into in case the
571 let on_diverge = iter.peek().iter().flat_map(|dd| dd.cached_block.into_iter()).next();
572 // If there’s no `cached_block`s within current scope, we must look for one in the
574 let on_diverge = on_diverge.or_else(||{
575 earlier_scopes.iter().rev().flat_map(|s| s.cached_block()).next()
577 let next = cfg.start_new_block();
578 cfg.terminate(block, Terminator::Drop {
579 value: drop_data.value.clone(),
588 fn build_diverge_scope<'tcx>(tcx: &TyCtxt<'tcx>,
590 unit_temp: Lvalue<'tcx>,
591 scope: &mut Scope<'tcx>,
592 target: Option<BasicBlock>)
594 debug_assert!(!scope.drops.is_empty() || scope.free.is_some());
596 // First, we build the drops, iterating the drops array in reverse. We do that so that as soon
597 // as we find a `cached_block`, we know that we’re finished and don’t need to do anything else.
598 let mut previous = None;
599 let mut last_drop_block = None;
600 for drop_data in scope.drops.iter_mut().rev() {
601 if let Some(cached_block) = drop_data.cached_block {
602 if let Some((previous_block, previous_value)) = previous {
603 cfg.terminate(previous_block, Terminator::Drop {
604 value: previous_value,
605 target: cached_block,
608 return last_drop_block.unwrap();
613 let block = cfg.start_new_cleanup_block();
614 drop_data.cached_block = Some(block);
615 if let Some((previous_block, previous_value)) = previous {
616 cfg.terminate(previous_block, Terminator::Drop {
617 value: previous_value,
622 last_drop_block = Some(block);
624 previous = Some((block, drop_data.value.clone()));
628 // Prepare the end target for this chain.
629 let mut target = target.unwrap_or_else(||{
630 let b = cfg.start_new_cleanup_block();
631 cfg.terminate(b, Terminator::Resume);
635 // Then, build the free branching into the prepared target.
636 if let Some(ref mut free_data) = scope.free {
637 target = if let Some(cached_block) = free_data.cached_block {
640 let into = cfg.start_new_cleanup_block();
641 cfg.terminate(into, build_free(tcx, unit_temp, free_data, target));
642 free_data.cached_block = Some(into);
647 if let Some((previous_block, previous_value)) = previous {
648 // Finally, branch into that just-built `target` from the `previous_block`.
649 cfg.terminate(previous_block, Terminator::Drop {
650 value: previous_value,
654 last_drop_block.unwrap()
656 // If `previous.is_none()`, there were no drops in this scope – we return the
662 fn build_free<'tcx>(tcx: &TyCtxt<'tcx>,
663 unit_temp: Lvalue<'tcx>,
664 data: &FreeData<'tcx>,
665 target: BasicBlock) -> Terminator<'tcx> {
666 let free_func = tcx.lang_items.require(lang_items::BoxFreeFnLangItem)
667 .unwrap_or_else(|e| tcx.sess.fatal(&e));
668 let substs = tcx.mk_substs(Substs::new(
669 VecPerParamSpace::new(vec![], vec![], vec![data.item_ty]),
670 VecPerParamSpace::new(vec![], vec![], vec![])
673 func: Operand::Constant(Constant {
675 ty: tcx.lookup_item_type(free_func).ty.subst(tcx, substs),
676 literal: Literal::Item {
681 args: vec![Operand::Consume(data.value.clone())],
682 destination: Some((unit_temp, target)),