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:
108 /// 1. We require a `free` to only be scheduled in the scope of
109 /// `EXPR` in `box EXPR`;
110 /// 2. It only makes sense to have it translated into the diverge-path.
112 /// This kind of drop will be run *after* all the regular drops
113 /// scheduled onto this scope, because drops may have dependencies
114 /// on the allocated memory.
116 /// This is expected to go away once `box EXPR` becomes a sugar
117 /// for placement protocol and gets desugared in some earlier
119 free: Option<FreeData<'tcx>>,
121 /// The cached block for the cleanups-on-diverge path. This block
122 /// contains a block that will just do a RESUME to an appropriate
123 /// place. This block does not execute any of the drops or free:
124 /// each of those has their own cached-blocks, which will branch
126 cached_block: Option<BasicBlock>
129 struct DropData<'tcx> {
130 /// span where drop obligation was incurred (typically where lvalue was declared)
136 /// The cached block for the cleanups-on-diverge path. This block
137 /// contains code to run the current drop and all the preceding
138 /// drops (i.e. those having lower index in Drop’s Scope drop
140 cached_block: Option<BasicBlock>
143 struct FreeData<'tcx> {
144 /// span where free obligation was incurred
147 /// Lvalue containing the allocated box.
150 /// type of item for which the box was allocated for (i.e. the T in Box<T>).
153 /// The cached block containing code to run the free. The block will also execute all the drops
155 cached_block: Option<BasicBlock>
158 #[derive(Clone, Debug)]
159 pub struct LoopScope {
160 /// Extent of the loop
161 pub extent: CodeExtent,
162 /// Where the body of the loop begins
163 pub continue_block: BasicBlock,
164 /// Block to branch into when the loop terminates (either by being `break`-en out from, or by
165 /// having its condition to become false)
166 pub break_block: BasicBlock, // where to go on a `break
167 /// Indicates the reachability of the break_block for this loop
168 pub might_break: bool
171 impl<'tcx> Scope<'tcx> {
172 /// Invalidate all the cached blocks in the scope.
174 /// Should always be run for all inner scopes when a drop is pushed into some scope enclosing a
175 /// larger extent of code.
176 fn invalidate_cache(&mut self) {
177 self.cached_block = None;
178 for dropdata in &mut self.drops {
179 dropdata.cached_block = None;
181 if let Some(ref mut freedata) = self.free {
182 freedata.cached_block = None;
186 /// Returns the cached block for this scope.
188 /// Precondition: the caches must be fully filled (i.e. diverge_cleanup is called) in order for
189 /// this method to work correctly.
190 fn cached_block(&self) -> Option<BasicBlock> {
191 if let Some(data) = self.drops.last() {
192 Some(data.cached_block.expect("drop cache is not filled"))
193 } else if let Some(ref data) = self.free {
194 Some(data.cached_block.expect("free cache is not filled"))
201 impl<'a,'tcx> Builder<'a,'tcx> {
202 // Adding and removing scopes
203 // ==========================
204 /// Start a loop scope, which tracks where `continue` and `break`
205 /// should branch to. See module comment for more details.
207 /// Returns the might_break attribute of the LoopScope used.
208 pub fn in_loop_scope<F>(&mut self,
209 loop_block: BasicBlock,
210 break_block: BasicBlock,
213 where F: FnOnce(&mut Builder<'a, 'tcx>)
215 let extent = self.extent_of_innermost_scope();
216 let loop_scope = LoopScope {
217 extent: extent.clone(),
218 continue_block: loop_block,
219 break_block: break_block,
222 self.loop_scopes.push(loop_scope);
224 let loop_scope = self.loop_scopes.pop().unwrap();
225 assert!(loop_scope.extent == extent);
226 loop_scope.might_break
229 /// Convenience wrapper that pushes a scope and then executes `f`
230 /// to build its contents, popping the scope afterwards.
231 pub fn in_scope<F, R>(&mut self, extent: CodeExtent, mut block: BasicBlock, f: F) -> BlockAnd<R>
232 where F: FnOnce(&mut Builder<'a, 'tcx>, ScopeId) -> BlockAnd<R>
234 debug!("in_scope(extent={:?}, block={:?})", extent, block);
235 let id = self.push_scope(extent, block);
236 let rv = unpack!(block = f(self, id));
237 unpack!(block = self.pop_scope(extent, block));
238 debug!("in_scope: exiting extent={:?} block={:?}", extent, block);
242 /// Push a scope onto the stack. You can then build code in this
243 /// scope and call `pop_scope` afterwards. Note that these two
244 /// calls must be paired; using `in_scope` as a convenience
245 /// wrapper maybe preferable.
246 pub fn push_scope(&mut self, extent: CodeExtent, entry: BasicBlock) -> ScopeId {
247 debug!("push_scope({:?})", extent);
248 let parent_id = self.scopes.last().map(|s| s.id);
249 let id = ScopeId::new(self.scope_data_vec.vec.len());
250 self.scope_data_vec.vec.push(ScopeData {
251 parent_scope: parent_id,
253 self.scopes.push(Scope {
260 self.scope_auxiliary.push(ScopeAuxiliary {
262 dom: self.cfg.current_location(entry),
268 /// Pops a scope, which should have extent `extent`, adding any
269 /// drops onto the end of `block` that are needed. This must
270 /// match 1-to-1 with `push_scope`.
271 pub fn pop_scope(&mut self,
273 mut block: BasicBlock)
275 debug!("pop_scope({:?}, {:?})", extent, block);
276 // We need to have `cached_block`s available for all the drops, so we call diverge_cleanup
277 // to make sure all the `cached_block`s are filled in.
278 self.diverge_cleanup();
279 let scope = self.scopes.pop().unwrap();
280 assert_eq!(scope.extent, extent);
281 unpack!(block = build_scope_drops(&mut self.cfg, &scope, &self.scopes, block));
282 self.scope_auxiliary[scope.id.index()]
284 .push(self.cfg.current_location(block));
289 /// Branch out of `block` to `target`, exiting all scopes up to
290 /// and including `extent`. This will insert whatever drops are
291 /// needed, as well as tracking this exit for the SEME region. See
292 /// module comment for details.
293 pub fn exit_scope(&mut self,
296 mut block: BasicBlock,
297 target: BasicBlock) {
298 debug!("exit_scope(extent={:?}, block={:?}, target={:?})", extent, block, target);
299 let scope_count = 1 + self.scopes.iter().rev().position(|scope| scope.extent == extent)
301 self.hir.span_bug(span, &format!("extent {:?} does not enclose", extent))
304 let tmp = self.get_unit_temp();
305 for (idx, ref scope) in self.scopes.iter().enumerate().rev().take(scope_count) {
306 unpack!(block = build_scope_drops(&mut self.cfg,
310 if let Some(ref free_data) = scope.free {
311 let next = self.cfg.start_new_block();
312 let free = build_free(self.hir.tcx(), &tmp, free_data, next);
313 self.cfg.terminate(block, scope.id, span, free);
316 self.scope_auxiliary[scope.id.index()]
318 .push(self.cfg.current_location(block));
321 let scope_id = self.innermost_scope_id();
322 self.cfg.terminate(block,
325 TerminatorKind::Goto { target: target });
330 /// Finds the loop scope for a given label. This is used for
331 /// resolving `break` and `continue`.
332 pub fn find_loop_scope(&mut self,
334 label: Option<CodeExtent>)
336 let Builder { ref mut loop_scopes, ref mut hir, .. } = *self;
339 // no label? return the innermost loop scope
340 loop_scopes.iter_mut().rev().next()
343 // otherwise, find the loop-scope with the correct id
344 loop_scopes.iter_mut()
346 .filter(|loop_scope| loop_scope.extent == label)
349 }.unwrap_or_else(|| hir.span_bug(span, "no enclosing loop scope found?"))
352 pub fn innermost_scope_id(&self) -> ScopeId {
353 self.scopes.last().map(|scope| scope.id).unwrap()
356 pub fn extent_of_innermost_scope(&self) -> CodeExtent {
357 self.scopes.last().map(|scope| scope.extent).unwrap()
360 pub fn extent_of_outermost_scope(&self) -> CodeExtent {
361 self.scopes.first().map(|scope| scope.extent).unwrap()
366 /// Indicates that `lvalue` should be dropped on exit from
368 pub fn schedule_drop(&mut self,
371 lvalue: &Lvalue<'tcx>,
372 lvalue_ty: Ty<'tcx>) {
373 if !self.hir.needs_drop(lvalue_ty) {
376 for scope in self.scopes.iter_mut().rev() {
377 if scope.extent == extent {
378 // No need to invalidate any caches here. The just-scheduled drop will branch into
379 // the drop that comes before it in the vector.
380 scope.drops.push(DropData {
382 value: lvalue.clone(),
387 // We must invalidate all the cached_blocks leading up to the scope we’re
388 // looking for, because all of the blocks in the chain will become incorrect.
389 scope.invalidate_cache()
392 self.hir.span_bug(span,
393 &format!("extent {:?} not in scope to drop {:?}", extent, lvalue));
396 /// Schedule dropping of a not-yet-fully-initialised box.
398 /// This cleanup will only be translated into unwind branch.
399 /// The extent should be for the `EXPR` inside `box EXPR`.
400 /// There may only be one “free” scheduled in any given scope.
401 pub fn schedule_box_free(&mut self,
404 value: &Lvalue<'tcx>,
406 for scope in self.scopes.iter_mut().rev() {
407 if scope.extent == extent {
408 assert!(scope.free.is_none(), "scope already has a scheduled free!");
409 // We also must invalidate the caches in the scope for which the free is scheduled
410 // because the drops must branch into the free we schedule here.
411 scope.invalidate_cache();
412 scope.free = Some(FreeData {
414 value: value.clone(),
420 // We must invalidate all the cached_blocks leading up to the scope we’re looking
421 // for, because otherwise some/most of the blocks in the chain will become
423 scope.invalidate_cache();
426 self.hir.span_bug(span,
427 &format!("extent {:?} not in scope to free {:?}", extent, value));
432 /// Creates a path that performs all required cleanup for unwinding.
434 /// This path terminates in Resume. Returns the start of the path.
435 /// See module comment for more details. None indicates there’s no
436 /// cleanup to do at this point.
437 pub fn diverge_cleanup(&mut self) -> Option<BasicBlock> {
438 if self.scopes.is_empty() {
441 let unit_temp = self.get_unit_temp();
442 let Builder { ref mut hir, ref mut cfg, ref mut scopes, .. } = *self;
444 // Given an array of scopes, we generate these from the outermost scope to the innermost
445 // one. Thus for array [S0, S1, S2] with corresponding cleanup blocks [B0, B1, B2], we will
446 // generate B0 <- B1 <- B2 in left-to-right order. Control flow of the generated blocks
447 // always ends up at a block with the Resume terminator.
448 if scopes.iter().any(|scope| !scope.drops.is_empty() || scope.free.is_some()) {
449 Some(build_diverge_scope(hir.tcx(), self.fn_span, cfg, &unit_temp, scopes))
455 /// Utility function for *non*-scope code to build their own drops
456 pub fn build_drop(&mut self,
461 let scope_id = self.innermost_scope_id();
462 let next_target = self.cfg.start_new_block();
463 let diverge_target = self.diverge_cleanup();
464 self.cfg.terminate(block,
467 TerminatorKind::Drop {
470 unwind: diverge_target,
478 // FIXME: should be moved into their own module
479 pub fn panic_bounds_check(&mut self,
481 index: Operand<'tcx>,
484 // fn(&(filename: &'static str, line: u32), index: usize, length: usize) -> !
485 let region = ty::ReStatic; // FIXME(mir-borrowck): use a better region?
486 let func = self.lang_function(lang_items::PanicBoundsCheckFnLangItem);
487 let args = self.hir.tcx().replace_late_bound_regions(&func.ty.fn_args(), |_| region).0;
489 let ref_ty = args[0];
490 let tup_ty = if let ty::TyRef(_, tyandmut) = ref_ty.sty {
493 self.hir.span_bug(span, &format!("unexpected panic_bound_check type: {:?}", func.ty));
496 let (tuple, tuple_ref) = (self.temp(tup_ty), self.temp(ref_ty));
497 let (file, line) = self.span_to_fileline_args(span);
498 let elems = vec![Operand::Constant(file), Operand::Constant(line)];
499 let scope_id = self.innermost_scope_id();
500 // FIXME: We should have this as a constant, rather than a stack variable (to not pollute
501 // icache with cold branch code), however to achieve that we either have to rely on rvalue
502 // promotion or have some way, in MIR, to create constants.
503 self.cfg.push_assign(block, scope_id, span, &tuple, // tuple = (file_arg, line_arg);
504 Rvalue::Aggregate(AggregateKind::Tuple, elems));
505 // FIXME: is this region really correct here?
506 self.cfg.push_assign(block, scope_id, span, &tuple_ref, // tuple_ref = &tuple;
507 Rvalue::Ref(region, BorrowKind::Shared, tuple));
508 let cleanup = self.diverge_cleanup();
509 self.cfg.terminate(block, scope_id, span, TerminatorKind::Call {
510 func: Operand::Constant(func),
511 args: vec![Operand::Consume(tuple_ref), index, len],
517 /// Create diverge cleanup and branch to it from `block`.
518 pub fn panic(&mut self, block: BasicBlock, msg: &'static str, span: Span) {
519 // fn(&(msg: &'static str filename: &'static str, line: u32)) -> !
520 let region = ty::ReStatic; // FIXME(mir-borrowck): use a better region?
521 let func = self.lang_function(lang_items::PanicFnLangItem);
522 let args = self.hir.tcx().replace_late_bound_regions(&func.ty.fn_args(), |_| region).0;
524 let ref_ty = args[0];
525 let tup_ty = if let ty::TyRef(_, tyandmut) = ref_ty.sty {
528 self.hir.span_bug(span, &format!("unexpected panic type: {:?}", func.ty));
531 let (tuple, tuple_ref) = (self.temp(tup_ty), self.temp(ref_ty));
532 let (file, line) = self.span_to_fileline_args(span);
533 let message = Constant {
535 ty: self.hir.tcx().mk_static_str(),
536 literal: self.hir.str_literal(intern_and_get_ident(msg))
538 let elems = vec![Operand::Constant(message),
539 Operand::Constant(file),
540 Operand::Constant(line)];
541 let scope_id = self.innermost_scope_id();
542 // FIXME: We should have this as a constant, rather than a stack variable (to not pollute
543 // icache with cold branch code), however to achieve that we either have to rely on rvalue
544 // promotion or have some way, in MIR, to create constants.
545 self.cfg.push_assign(block, scope_id, span, &tuple, // [1]
546 Rvalue::Aggregate(AggregateKind::Tuple, elems));
547 // [1] tuple = (message_arg, file_arg, line_arg);
548 // FIXME: is this region really correct here?
549 self.cfg.push_assign(block, scope_id, span, &tuple_ref, // tuple_ref = &tuple;
550 Rvalue::Ref(region, BorrowKind::Shared, tuple));
551 let cleanup = self.diverge_cleanup();
552 self.cfg.terminate(block, scope_id, span, TerminatorKind::Call {
553 func: Operand::Constant(func),
554 args: vec![Operand::Consume(tuple_ref)],
560 fn lang_function(&mut self, lang_item: lang_items::LangItem) -> Constant<'tcx> {
561 let funcdid = match self.hir.tcx().lang_items.require(lang_item) {
564 self.hir.tcx().sess.fatal(&m)
569 ty: self.hir.tcx().lookup_item_type(funcdid).ty,
570 literal: Literal::Item {
572 substs: self.hir.tcx().mk_substs(Substs::empty())
577 fn span_to_fileline_args(&mut self, span: Span) -> (Constant<'tcx>, Constant<'tcx>) {
578 let span_lines = self.hir.tcx().sess.codemap().lookup_char_pos(span.lo);
581 ty: self.hir.tcx().mk_static_str(),
582 literal: self.hir.str_literal(intern_and_get_ident(&span_lines.file.name))
585 ty: self.hir.tcx().types.u32,
586 literal: Literal::Value {
587 value: ConstVal::Integral(ConstInt::U32(span_lines.line as u32)),
594 /// Builds drops for pop_scope and exit_scope.
595 fn build_scope_drops<'tcx>(cfg: &mut CFG<'tcx>,
597 earlier_scopes: &[Scope<'tcx>],
598 mut block: BasicBlock)
600 let mut iter = scope.drops.iter().rev().peekable();
601 while let Some(drop_data) = iter.next() {
602 // Try to find the next block with its cached block for us to diverge into in case the
604 let on_diverge = iter.peek().iter().flat_map(|dd| dd.cached_block.into_iter()).next();
605 // If there’s no `cached_block`s within current scope, we must look for one in the
607 let on_diverge = on_diverge.or_else(||{
608 earlier_scopes.iter().rev().flat_map(|s| s.cached_block()).next()
610 let next = cfg.start_new_block();
611 cfg.terminate(block, scope.id, drop_data.span, TerminatorKind::Drop {
612 value: drop_data.value.clone(),
621 fn build_diverge_scope<'tcx>(tcx: &TyCtxt<'tcx>,
624 unit_temp: &Lvalue<'tcx>,
625 scopes: &mut [Scope<'tcx>])
628 assert!(scopes.len() >= 1);
630 // Build up the drops in **reverse** order. The end result will
633 // [drops[n]] -...-> [drops[0]] -> [Free] -> [scopes[..n-1]]
635 // +------------------------------------+
636 // code for scopes[n]
638 // The code in this function reads from right to left. At each
639 // point, we check for cached blocks representing the
640 // remainder. If everything is cached, we'll just walk right to
641 // left reading the cached results but never created anything.
643 // To start, translate scopes[1..].
644 let (scope, earlier_scopes) = scopes.split_last_mut().unwrap();
645 let mut target = if let Some(cached_block) = scope.cached_block {
647 } else if earlier_scopes.is_empty() {
648 // Diverging from the root scope creates a RESUME terminator.
649 // FIXME what span to use here?
650 let resumeblk = cfg.start_new_cleanup_block();
651 cfg.terminate(resumeblk, scope.id, fn_span, TerminatorKind::Resume);
654 // Diverging from any other scope chains up to the previous scope.
655 build_diverge_scope(tcx, fn_span, cfg, unit_temp, earlier_scopes)
657 scope.cached_block = Some(target);
659 // Next, build up any free.
660 if let Some(ref mut free_data) = scope.free {
661 target = if let Some(cached_block) = free_data.cached_block {
664 let into = cfg.start_new_cleanup_block();
668 build_free(tcx, unit_temp, free_data, target));
669 free_data.cached_block = Some(into);
674 // Next, build up the drops. Here we iterate the vector in
675 // *forward* order, so that we generate drops[0] first (right to
676 // left in diagram above).
677 for drop_data in &mut scope.drops {
678 target = if let Some(cached_block) = drop_data.cached_block {
681 let block = cfg.start_new_cleanup_block();
685 TerminatorKind::Drop {
686 value: drop_data.value.clone(),
690 drop_data.cached_block = Some(block);
698 fn build_free<'tcx>(tcx: &TyCtxt<'tcx>,
699 unit_temp: &Lvalue<'tcx>,
700 data: &FreeData<'tcx>,
702 -> TerminatorKind<'tcx> {
703 let free_func = tcx.lang_items.require(lang_items::BoxFreeFnLangItem)
704 .unwrap_or_else(|e| tcx.sess.fatal(&e));
705 let substs = tcx.mk_substs(Substs::new(
706 VecPerParamSpace::new(vec![], vec![], vec![data.item_ty]),
707 VecPerParamSpace::new(vec![], vec![], vec![])
709 TerminatorKind::Call {
710 func: Operand::Constant(Constant {
712 ty: tcx.lookup_item_type(free_func).ty.subst(tcx, substs),
713 literal: Literal::Item {
718 args: vec![Operand::Consume(data.value.clone())],
719 destination: Some((unit_temp.clone(), target)),