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>>,
117 /// The cached block for the cleanups-on-diverge path. This block
118 /// contains a block that will just do a RESUME to an appropriate
119 /// place. This block does not execute any of the drops or free:
120 /// each of those has their own cached-blocks, which will branch
122 cached_block: Option<BasicBlock>
125 struct DropData<'tcx> {
128 // NB: per-drop “cache” is necessary for the build_scope_drops function below.
130 /// The cached block for the cleanups-on-diverge path. This block contains code to run the
131 /// current drop and all the preceding drops (i.e. those having lower index in Drop’s
132 /// Scope drop array)
133 cached_block: Option<BasicBlock>
136 struct FreeData<'tcx> {
139 /// Lvalue containing the allocated box.
142 /// type of item for which the box was allocated for (i.e. the T in Box<T>).
145 /// The cached block containing code to run the free. The block will also execute all the drops
147 cached_block: Option<BasicBlock>
150 #[derive(Clone, Debug)]
151 pub struct LoopScope {
152 /// Extent of the loop
153 pub extent: CodeExtent,
154 /// Where the body of the loop begins
155 pub continue_block: BasicBlock,
156 /// Block to branch into when the loop terminates (either by being `break`-en out from, or by
157 /// having its condition to become false)
158 pub break_block: BasicBlock, // where to go on a `break
159 /// Indicates the reachability of the break_block for this loop
160 pub might_break: bool
163 impl<'tcx> Scope<'tcx> {
164 /// Invalidate all the cached blocks in the scope.
166 /// Should always be run for all inner scopes when a drop is pushed into some scope enclosing a
167 /// larger extent of code.
168 fn invalidate_cache(&mut self) {
169 self.cached_block = None;
170 for dropdata in &mut self.drops {
171 dropdata.cached_block = None;
173 if let Some(ref mut freedata) = self.free {
174 freedata.cached_block = None;
178 /// Returns the cached block for this scope.
180 /// Precondition: the caches must be fully filled (i.e. diverge_cleanup is called) in order for
181 /// this method to work correctly.
182 fn cached_block(&self) -> Option<BasicBlock> {
183 if let Some(data) = self.drops.last() {
184 Some(data.cached_block.expect("drop cache is not filled"))
185 } else if let Some(ref data) = self.free {
186 Some(data.cached_block.expect("free cache is not filled"))
193 impl<'a,'tcx> Builder<'a,'tcx> {
194 // Adding and removing scopes
195 // ==========================
196 /// Start a loop scope, which tracks where `continue` and `break`
197 /// should branch to. See module comment for more details.
199 /// Returns the might_break attribute of the LoopScope used.
200 pub fn in_loop_scope<F>(&mut self,
201 loop_block: BasicBlock,
202 break_block: BasicBlock,
205 where F: FnOnce(&mut Builder<'a, 'tcx>)
207 let extent = self.extent_of_innermost_scope();
208 let loop_scope = LoopScope {
209 extent: extent.clone(),
210 continue_block: loop_block,
211 break_block: break_block,
214 self.loop_scopes.push(loop_scope);
216 let loop_scope = self.loop_scopes.pop().unwrap();
217 assert!(loop_scope.extent == extent);
218 loop_scope.might_break
221 /// Convenience wrapper that pushes a scope and then executes `f`
222 /// to build its contents, popping the scope afterwards.
223 pub fn in_scope<F, R>(&mut self, extent: CodeExtent, mut block: BasicBlock, f: F) -> BlockAnd<R>
224 where F: FnOnce(&mut Builder<'a, 'tcx>, ScopeId) -> BlockAnd<R>
226 debug!("in_scope(extent={:?}, block={:?})", extent, block);
227 let id = self.push_scope(extent, block);
228 let rv = unpack!(block = f(self, id));
229 unpack!(block = self.pop_scope(extent, block));
230 debug!("in_scope: exiting extent={:?} block={:?}", extent, block);
234 /// Push a scope onto the stack. You can then build code in this
235 /// scope and call `pop_scope` afterwards. Note that these two
236 /// calls must be paired; using `in_scope` as a convenience
237 /// wrapper maybe preferable.
238 pub fn push_scope(&mut self, extent: CodeExtent, entry: BasicBlock) -> ScopeId {
239 debug!("push_scope({:?})", extent);
240 let parent_id = self.scopes.last().map(|s| s.id);
241 let id = ScopeId::new(self.scope_data_vec.vec.len());
242 self.scope_data_vec.vec.push(ScopeData {
243 parent_scope: parent_id,
245 self.scopes.push(Scope {
252 self.scope_auxiliary.push(ScopeAuxiliary {
254 dom: self.cfg.current_location(entry),
260 /// Pops a scope, which should have extent `extent`, adding any
261 /// drops onto the end of `block` that are needed. This must
262 /// match 1-to-1 with `push_scope`.
263 pub fn pop_scope(&mut self,
265 mut block: BasicBlock)
267 debug!("pop_scope({:?}, {:?})", extent, block);
268 // We need to have `cached_block`s available for all the drops, so we call diverge_cleanup
269 // to make sure all the `cached_block`s are filled in.
270 self.diverge_cleanup();
271 let scope = self.scopes.pop().unwrap();
272 assert_eq!(scope.extent, extent);
273 unpack!(block = build_scope_drops(&mut self.cfg, &scope, &self.scopes, block));
274 self.scope_auxiliary[scope.id.index()]
276 .push(self.cfg.current_location(block));
281 /// Branch out of `block` to `target`, exiting all scopes up to
282 /// and including `extent`. This will insert whatever drops are
283 /// needed, as well as tracking this exit for the SEME region. See
284 /// module comment for details.
285 pub fn exit_scope(&mut self,
288 mut block: BasicBlock,
289 target: BasicBlock) {
290 debug!("exit_scope(extent={:?}, block={:?}, target={:?})", extent, block, target);
291 let scope_count = 1 + self.scopes.iter().rev().position(|scope| scope.extent == extent)
293 self.hir.span_bug(span, &format!("extent {:?} does not enclose", extent))
296 let tmp = self.get_unit_temp();
297 for (idx, ref scope) in self.scopes.iter().enumerate().rev().take(scope_count) {
298 unpack!(block = build_scope_drops(&mut self.cfg,
302 if let Some(ref free_data) = scope.free {
303 let next = self.cfg.start_new_block();
304 let free = build_free(self.hir.tcx(), &tmp, free_data, next);
305 self.cfg.terminate(block, scope.id, span, free);
308 self.scope_auxiliary[scope.id.index()]
310 .push(self.cfg.current_location(block));
313 let scope_id = self.innermost_scope_id();
314 self.cfg.terminate(block,
317 TerminatorKind::Goto { target: target });
322 /// Finds the loop scope for a given label. This is used for
323 /// resolving `break` and `continue`.
324 pub fn find_loop_scope(&mut self,
326 label: Option<CodeExtent>)
328 let Builder { ref mut loop_scopes, ref mut hir, .. } = *self;
331 // no label? return the innermost loop scope
332 loop_scopes.iter_mut().rev().next()
335 // otherwise, find the loop-scope with the correct id
336 loop_scopes.iter_mut()
338 .filter(|loop_scope| loop_scope.extent == label)
341 }.unwrap_or_else(|| hir.span_bug(span, "no enclosing loop scope found?"))
344 pub fn innermost_scope_id(&self) -> ScopeId {
345 self.scopes.last().map(|scope| scope.id).unwrap()
348 pub fn extent_of_innermost_scope(&self) -> CodeExtent {
349 self.scopes.last().map(|scope| scope.extent).unwrap()
352 pub fn extent_of_outermost_scope(&self) -> CodeExtent {
353 self.scopes.first().map(|scope| scope.extent).unwrap()
358 /// Indicates that `lvalue` should be dropped on exit from
360 pub fn schedule_drop(&mut self,
363 lvalue: &Lvalue<'tcx>,
364 lvalue_ty: Ty<'tcx>) {
365 if !self.hir.needs_drop(lvalue_ty) {
368 for scope in self.scopes.iter_mut().rev() {
369 if scope.extent == extent {
370 // No need to invalidate any caches here. The just-scheduled drop will branch into
371 // the drop that comes before it in the vector.
372 scope.drops.push(DropData {
374 value: lvalue.clone(),
379 // We must invalidate all the cached_blocks leading up to the scope we’re
380 // looking for, because all of the blocks in the chain will become incorrect.
381 scope.invalidate_cache()
384 self.hir.span_bug(span,
385 &format!("extent {:?} not in scope to drop {:?}", extent, lvalue));
388 /// Schedule dropping of a not-yet-fully-initialised box.
390 /// This cleanup will only be translated into unwind branch.
391 /// The extent should be for the `EXPR` inside `box EXPR`.
392 /// There may only be one “free” scheduled in any given scope.
393 pub fn schedule_box_free(&mut self,
396 value: &Lvalue<'tcx>,
398 for scope in self.scopes.iter_mut().rev() {
399 if scope.extent == extent {
400 assert!(scope.free.is_none(), "scope already has a scheduled free!");
401 // We also must invalidate the caches in the scope for which the free is scheduled
402 // because the drops must branch into the free we schedule here.
403 scope.invalidate_cache();
404 scope.free = Some(FreeData {
406 value: value.clone(),
412 // We must invalidate all the cached_blocks leading up to the scope we’re looking
413 // for, because otherwise some/most of the blocks in the chain will become
415 scope.invalidate_cache();
418 self.hir.span_bug(span,
419 &format!("extent {:?} not in scope to free {:?}", extent, value));
424 /// Creates a path that performs all required cleanup for unwinding.
426 /// This path terminates in Resume. Returns the start of the path.
427 /// See module comment for more details. None indicates there’s no
428 /// cleanup to do at this point.
429 pub fn diverge_cleanup(&mut self) -> Option<BasicBlock> {
430 if self.scopes.is_empty() {
433 let unit_temp = self.get_unit_temp();
434 let Builder { ref mut hir, ref mut cfg, ref mut scopes, .. } = *self;
436 // Given an array of scopes, we generate these from the outermost scope to the innermost
437 // one. Thus for array [S0, S1, S2] with corresponding cleanup blocks [B0, B1, B2], we will
438 // generate B0 <- B1 <- B2 in left-to-right order. Control flow of the generated blocks
439 // always ends up at a block with the Resume terminator.
440 if scopes.iter().any(|scope| !scope.drops.is_empty() || scope.free.is_some()) {
441 Some(build_diverge_scope(hir.tcx(), self.fn_span, cfg, &unit_temp, scopes))
447 /// Utility function for *non*-scope code to build their own drops
448 pub fn build_drop(&mut self,
453 let scope_id = self.innermost_scope_id();
454 let next_target = self.cfg.start_new_block();
455 let diverge_target = self.diverge_cleanup();
456 self.cfg.terminate(block,
459 TerminatorKind::Drop {
462 unwind: diverge_target,
470 // FIXME: should be moved into their own module
471 pub fn panic_bounds_check(&mut self,
473 index: Operand<'tcx>,
476 // fn(&(filename: &'static str, line: u32), index: usize, length: usize) -> !
477 let region = ty::ReStatic; // FIXME(mir-borrowck): use a better region?
478 let func = self.lang_function(lang_items::PanicBoundsCheckFnLangItem);
479 let args = self.hir.tcx().replace_late_bound_regions(&func.ty.fn_args(), |_| region).0;
481 let ref_ty = args[0];
482 let tup_ty = if let ty::TyRef(_, tyandmut) = ref_ty.sty {
485 self.hir.span_bug(span, &format!("unexpected panic_bound_check type: {:?}", func.ty));
488 let (tuple, tuple_ref) = (self.temp(tup_ty), self.temp(ref_ty));
489 let (file, line) = self.span_to_fileline_args(span);
490 let elems = vec![Operand::Constant(file), Operand::Constant(line)];
491 let scope_id = self.innermost_scope_id();
492 // FIXME: We should have this as a constant, rather than a stack variable (to not pollute
493 // icache with cold branch code), however to achieve that we either have to rely on rvalue
494 // promotion or have some way, in MIR, to create constants.
495 self.cfg.push_assign(block, scope_id, span, &tuple, // tuple = (file_arg, line_arg);
496 Rvalue::Aggregate(AggregateKind::Tuple, elems));
497 // FIXME: is this region really correct here?
498 self.cfg.push_assign(block, scope_id, span, &tuple_ref, // tuple_ref = &tuple;
499 Rvalue::Ref(region, BorrowKind::Shared, tuple));
500 let cleanup = self.diverge_cleanup();
501 self.cfg.terminate(block, scope_id, span, TerminatorKind::Call {
502 func: Operand::Constant(func),
503 args: vec![Operand::Consume(tuple_ref), index, len],
509 /// Create diverge cleanup and branch to it from `block`.
510 pub fn panic(&mut self, block: BasicBlock, msg: &'static str, span: Span) {
511 // fn(&(msg: &'static str filename: &'static str, line: u32)) -> !
512 let region = ty::ReStatic; // FIXME(mir-borrowck): use a better region?
513 let func = self.lang_function(lang_items::PanicFnLangItem);
514 let args = self.hir.tcx().replace_late_bound_regions(&func.ty.fn_args(), |_| region).0;
516 let ref_ty = args[0];
517 let tup_ty = if let ty::TyRef(_, tyandmut) = ref_ty.sty {
520 self.hir.span_bug(span, &format!("unexpected panic type: {:?}", func.ty));
523 let (tuple, tuple_ref) = (self.temp(tup_ty), self.temp(ref_ty));
524 let (file, line) = self.span_to_fileline_args(span);
525 let message = Constant {
527 ty: self.hir.tcx().mk_static_str(),
528 literal: self.hir.str_literal(intern_and_get_ident(msg))
530 let elems = vec![Operand::Constant(message),
531 Operand::Constant(file),
532 Operand::Constant(line)];
533 let scope_id = self.innermost_scope_id();
534 // FIXME: We should have this as a constant, rather than a stack variable (to not pollute
535 // icache with cold branch code), however to achieve that we either have to rely on rvalue
536 // promotion or have some way, in MIR, to create constants.
537 self.cfg.push_assign(block, scope_id, span, &tuple, // [1]
538 Rvalue::Aggregate(AggregateKind::Tuple, elems));
539 // [1] tuple = (message_arg, file_arg, line_arg);
540 // FIXME: is this region really correct here?
541 self.cfg.push_assign(block, scope_id, span, &tuple_ref, // tuple_ref = &tuple;
542 Rvalue::Ref(region, BorrowKind::Shared, tuple));
543 let cleanup = self.diverge_cleanup();
544 self.cfg.terminate(block, scope_id, span, TerminatorKind::Call {
545 func: Operand::Constant(func),
546 args: vec![Operand::Consume(tuple_ref)],
552 fn lang_function(&mut self, lang_item: lang_items::LangItem) -> Constant<'tcx> {
553 let funcdid = match self.hir.tcx().lang_items.require(lang_item) {
556 self.hir.tcx().sess.fatal(&m)
561 ty: self.hir.tcx().lookup_item_type(funcdid).ty,
562 literal: Literal::Item {
564 substs: self.hir.tcx().mk_substs(Substs::empty())
569 fn span_to_fileline_args(&mut self, span: Span) -> (Constant<'tcx>, Constant<'tcx>) {
570 let span_lines = self.hir.tcx().sess.codemap().lookup_char_pos(span.lo);
573 ty: self.hir.tcx().mk_static_str(),
574 literal: self.hir.str_literal(intern_and_get_ident(&span_lines.file.name))
577 ty: self.hir.tcx().types.u32,
578 literal: Literal::Value {
579 value: ConstVal::Integral(ConstInt::U32(span_lines.line as u32)),
586 /// Builds drops for pop_scope and exit_scope.
587 fn build_scope_drops<'tcx>(cfg: &mut CFG<'tcx>,
589 earlier_scopes: &[Scope<'tcx>],
590 mut block: BasicBlock)
592 let mut iter = scope.drops.iter().rev().peekable();
593 while let Some(drop_data) = iter.next() {
594 // Try to find the next block with its cached block for us to diverge into in case the
596 let on_diverge = iter.peek().iter().flat_map(|dd| dd.cached_block.into_iter()).next();
597 // If there’s no `cached_block`s within current scope, we must look for one in the
599 let on_diverge = on_diverge.or_else(||{
600 earlier_scopes.iter().rev().flat_map(|s| s.cached_block()).next()
602 let next = cfg.start_new_block();
603 cfg.terminate(block, scope.id, drop_data.span, TerminatorKind::Drop {
604 value: drop_data.value.clone(),
613 fn build_diverge_scope<'tcx>(tcx: &TyCtxt<'tcx>,
616 unit_temp: &Lvalue<'tcx>,
617 scopes: &mut [Scope<'tcx>])
620 assert!(scopes.len() >= 1);
622 // Build up the drops in **reverse** order. The end result will
625 // [drops[n]] -...-> [drops[0]] -> [Free] -> [scopes[..n-1]]
627 // +------------------------------------+
628 // code for scopes[n]
630 // The code in this function reads from right to left. At each
631 // point, we check for cached blocks representing the
632 // remainder. If everything is cached, we'll just walk right to
633 // left reading the cached results but never created anything.
635 // To start, translate scopes[1..].
636 let (scope, earlier_scopes) = scopes.split_last_mut().unwrap();
637 let mut target = if let Some(cached_block) = scope.cached_block {
639 } else if earlier_scopes.is_empty() {
640 // Diverging from the root scope creates a RESUME terminator.
641 // FIXME what span to use here?
642 let resumeblk = cfg.start_new_cleanup_block();
643 cfg.terminate(resumeblk, scope.id, fn_span, TerminatorKind::Resume);
646 // Diverging from any other scope chains up to the previous scope.
647 build_diverge_scope(tcx, fn_span, cfg, unit_temp, earlier_scopes)
649 scope.cached_block = Some(target);
651 // Next, build up any free.
652 if let Some(ref mut free_data) = scope.free {
653 target = if let Some(cached_block) = free_data.cached_block {
656 let into = cfg.start_new_cleanup_block();
660 build_free(tcx, unit_temp, free_data, target));
661 free_data.cached_block = Some(into);
666 // Next, build up the drops. Here we iterate the vector in
667 // *forward* order, so that we generate drops[0] first (right to
668 // left in diagram above).
669 for drop_data in &mut scope.drops {
670 target = if let Some(cached_block) = drop_data.cached_block {
673 let block = cfg.start_new_cleanup_block();
677 TerminatorKind::Drop {
678 value: drop_data.value.clone(),
682 drop_data.cached_block = Some(block);
690 fn build_free<'tcx>(tcx: &TyCtxt<'tcx>,
691 unit_temp: &Lvalue<'tcx>,
692 data: &FreeData<'tcx>,
694 -> TerminatorKind<'tcx> {
695 let free_func = tcx.lang_items.require(lang_items::BoxFreeFnLangItem)
696 .unwrap_or_else(|e| tcx.sess.fatal(&e));
697 let substs = tcx.mk_substs(Substs::new(
698 VecPerParamSpace::new(vec![], vec![], vec![data.item_ty]),
699 VecPerParamSpace::new(vec![], vec![], vec![])
701 TerminatorKind::Call {
702 func: Operand::Constant(Constant {
704 ty: tcx.lookup_item_type(free_func).ty.subst(tcx, substs),
705 literal: Literal::Item {
710 args: vec![Operand::Consume(data.value.clone())],
711 destination: Some((unit_temp.clone(), target)),