1 // Copyright 2012-2014 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 use rustc::middle::region::CodeExtent;
13 use rustc::middle::ty::{FnOutput, Ty};
14 use rustc::mir::repr::*;
15 use rustc_data_structures::fnv::FnvHashMap;
17 use std::ops::{Index, IndexMut};
19 use syntax::codemap::Span;
21 pub struct Builder<'a, 'tcx: 'a> {
27 // the current set of scopes, updated as we traverse;
28 // see the `scope` module for more details
29 scopes: Vec<scope::Scope<'tcx>>,
31 // for each scope, a span of blocks that defines it;
32 // we track these for use in region and borrow checking,
33 // but these are liable to get out of date once optimization
34 // begins. They are also hopefully temporary, and will be
35 // no longer needed when we adopt graph-based regions.
36 scope_auxiliary: ScopeAuxiliaryVec,
38 // the current set of loops; see the `scope` module for more
40 loop_scopes: Vec<scope::LoopScope>,
42 // the vector of all scopes that we have created thus far;
43 // we track this for debuginfo later
44 scope_datas: Vec<ScopeData>,
46 var_decls: Vec<VarDecl<'tcx>>,
47 var_indices: FnvHashMap<ast::NodeId, u32>,
48 temp_decls: Vec<TempDecl<'tcx>>,
49 unit_temp: Option<Lvalue<'tcx>>,
53 basic_blocks: Vec<BasicBlockData<'tcx>>,
56 /// For each scope, we track the extent (from the HIR) and a
57 /// single-entry-multiple-exit subgraph that contains all the
58 /// statements/terminators within it.
60 /// This information is separated out from the main `ScopeData`
61 /// because it is short-lived. First, the extent contains node-ids,
62 /// so it cannot be saved and re-loaded. Second, any optimization will mess up
63 /// the dominator/postdominator information.
65 /// The intention is basically to use this information to do
66 /// regionck/borrowck and then throw it away once we are done.
67 pub struct ScopeAuxiliary {
68 /// extent of this scope from the MIR.
69 pub extent: CodeExtent,
71 /// "entry point": dominator of all nodes in the scope
74 /// "exit points": mutual postdominators of all nodes in the scope
75 pub postdoms: Vec<Location>,
78 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
80 /// the location is within this block
81 pub block: BasicBlock,
83 /// the location is the start of the this statement; or, if `statement_index`
84 /// == num-statements, then the start of the terminator.
85 pub statement_index: usize,
88 pub struct ScopeAuxiliaryVec {
89 pub vec: Vec<ScopeAuxiliary>
92 impl Index<ScopeId> for ScopeAuxiliaryVec {
93 type Output = ScopeAuxiliary;
96 fn index(&self, index: ScopeId) -> &ScopeAuxiliary {
97 &self.vec[index.index()]
101 impl IndexMut<ScopeId> for ScopeAuxiliaryVec {
103 fn index_mut(&mut self, index: ScopeId) -> &mut ScopeAuxiliary {
104 &mut self.vec[index.index()]
108 ///////////////////////////////////////////////////////////////////////////
109 /// The `BlockAnd` "monad" packages up the new basic block along with a
110 /// produced value (sometimes just unit, of course). The `unpack!`
111 /// macro (and methods below) makes working with `BlockAnd` much more
114 #[must_use] // if you don't use one of these results, you're leaving a dangling edge
115 pub struct BlockAnd<T>(BasicBlock, T);
117 trait BlockAndExtension {
118 fn and<T>(self, v: T) -> BlockAnd<T>;
119 fn unit(self) -> BlockAnd<()>;
122 impl BlockAndExtension for BasicBlock {
123 fn and<T>(self, v: T) -> BlockAnd<T> {
127 fn unit(self) -> BlockAnd<()> {
132 /// Update a block pointer and return the value.
133 /// Use it like `let x = unpack!(block = self.foo(block, foo))`.
134 macro_rules! unpack {
135 ($x:ident = $c:expr) => {
137 let BlockAnd(b, v) = $c;
145 let BlockAnd(b, ()) = $c;
151 ///////////////////////////////////////////////////////////////////////////
152 /// the main entry point for building MIR for a function
154 pub fn construct<'a,'tcx>(hir: Cx<'a,'tcx>,
156 implicit_arguments: Vec<Ty<'tcx>>,
157 explicit_arguments: Vec<(Ty<'tcx>, &'tcx hir::Pat)>,
158 argument_extent: CodeExtent,
159 return_ty: FnOutput<'tcx>,
160 ast_block: &'tcx hir::Block)
161 -> (Mir<'tcx>, ScopeAuxiliaryVec) {
162 let cfg = CFG { basic_blocks: vec![] };
164 let mut builder = Builder {
170 scope_auxiliary: ScopeAuxiliaryVec { vec: vec![] },
174 var_indices: FnvHashMap(),
178 assert_eq!(builder.cfg.start_new_block(), START_BLOCK);
179 assert_eq!(builder.cfg.start_new_block(), END_BLOCK);
181 let mut block = START_BLOCK;
182 let (arg_decls, arg_scope_id) =
183 unpack!(block = builder.args_and_body(block,
189 builder.cfg.terminate(block, arg_scope_id, span,
190 TerminatorKind::Goto { target: END_BLOCK });
191 builder.cfg.terminate(END_BLOCK, arg_scope_id, span,
192 TerminatorKind::Return);
195 builder.cfg.basic_blocks
198 .all(|(index, block)| {
199 if block.terminator.is_none() {
200 panic!("no terminator on block {:?} in {:?}",
201 index, argument_extent)
208 basic_blocks: builder.cfg.basic_blocks,
209 scopes: builder.scope_datas,
210 var_decls: builder.var_decls,
211 arg_decls: arg_decls,
212 temp_decls: builder.temp_decls,
213 return_ty: return_ty,
216 builder.scope_auxiliary,
220 impl<'a,'tcx> Builder<'a,'tcx> {
221 fn args_and_body(&mut self,
222 mut block: BasicBlock,
223 implicit_arguments: Vec<Ty<'tcx>>,
224 explicit_arguments: Vec<(Ty<'tcx>, &'tcx hir::Pat)>,
225 argument_extent: CodeExtent,
226 ast_block: &'tcx hir::Block)
227 -> BlockAnd<(Vec<ArgDecl<'tcx>>, ScopeId)>
229 self.in_scope(argument_extent, block, |this, argument_scope_id| {
230 // to start, translate the argument patterns and collect the argument types.
231 let implicits = implicit_arguments.into_iter().map(|ty| (ty, None));
232 let explicits = explicit_arguments.into_iter().map(|(ty, pat)| (ty, Some(pat)));
237 .map(|(index, (ty, pattern))| {
238 let lvalue = Lvalue::Arg(index as u32);
239 if let Some(pattern) = pattern {
240 let pattern = this.hir.irrefutable_pat(pattern);
241 unpack!(block = this.lvalue_into_pattern(block,
246 // Make sure we drop (parts of) the argument even when not matched on.
247 this.schedule_drop(pattern.as_ref().map_or(ast_block.span, |pat| pat.span),
248 argument_extent, &lvalue, ty);
249 ArgDecl { ty: ty, spread: false }
253 // start the first basic block and translate the body
254 unpack!(block = this.ast_block(&Lvalue::ReturnPointer, block, ast_block));
256 block.and((arg_decls, argument_scope_id))
260 fn get_unit_temp(&mut self) -> Lvalue<'tcx> {
261 match self.unit_temp {
262 Some(ref tmp) => tmp.clone(),
264 let ty = self.hir.unit_ty();
265 let tmp = self.temp(ty);
266 self.unit_temp = Some(tmp.clone());
273 ///////////////////////////////////////////////////////////////////////////
274 // Builder methods are broken up into modules, depending on what kind
275 // of thing is being translated. Note that they use the `unpack` macro
276 // above extensively.