]> git.proxmox.com Git - rustc.git/blame - src/librustc_mir/build/mod.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc_mir / build / mod.rs
CommitLineData
e9174d1e
SL
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.
4//
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.
10
92a42be0 11use hair::cx::Cx;
54a0048b
SL
12use rustc::middle::region::{CodeExtent, CodeExtentData};
13use rustc::ty::{FnOutput, Ty};
92a42be0 14use rustc::mir::repr::*;
e9174d1e 15use rustc_data_structures::fnv::FnvHashMap;
54a0048b
SL
16use rustc::hir;
17use std::ops::{Index, IndexMut};
b039eaaf
SL
18use syntax::ast;
19use syntax::codemap::Span;
b039eaaf 20
9cc50fc6 21pub struct Builder<'a, 'tcx: 'a> {
b039eaaf 22 hir: Cx<'a, 'tcx>,
b039eaaf 23 cfg: CFG<'tcx>,
54a0048b
SL
24
25 fn_span: Span,
26
27 // the current set of scopes, updated as we traverse;
28 // see the `scope` module for more details
b039eaaf 29 scopes: Vec<scope::Scope<'tcx>>,
54a0048b
SL
30
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,
37
38 // the current set of loops; see the `scope` module for more
39 // details
b039eaaf 40 loop_scopes: Vec<scope::LoopScope>,
54a0048b
SL
41
42 // the vector of all scopes that we have created thus far;
43 // we track this for debuginfo later
44 scope_datas: Vec<ScopeData>,
45
b039eaaf
SL
46 var_decls: Vec<VarDecl<'tcx>>,
47 var_indices: FnvHashMap<ast::NodeId, u32>,
48 temp_decls: Vec<TempDecl<'tcx>>,
7453a54e 49 unit_temp: Option<Lvalue<'tcx>>,
54a0048b
SL
50
51 // cached block with a RESUME terminator; we create this at the
52 // first panic
53 cached_resume_block: Option<BasicBlock>,
e9174d1e
SL
54}
55
b039eaaf
SL
56struct CFG<'tcx> {
57 basic_blocks: Vec<BasicBlockData<'tcx>>,
e9174d1e
SL
58}
59
54a0048b
SL
60/// For each scope, we track the extent (from the HIR) and a
61/// single-entry-multiple-exit subgraph that contains all the
62/// statements/terminators within it.
63///
64/// This information is separated out from the main `ScopeData`
65/// because it is short-lived. First, the extent contains node-ids,
66/// so it cannot be saved and re-loaded. Second, any optimization will mess up
67/// the dominator/postdominator information.
68///
69/// The intention is basically to use this information to do
70/// regionck/borrowck and then throw it away once we are done.
71pub struct ScopeAuxiliary {
72 /// extent of this scope from the MIR.
73 pub extent: CodeExtent,
74
75 /// "entry point": dominator of all nodes in the scope
76 pub dom: Location,
77
78 /// "exit points": mutual postdominators of all nodes in the scope
79 pub postdoms: Vec<Location>,
80}
81
82#[derive(Copy, Clone, PartialEq, Eq, Hash)]
83pub struct Location {
84 /// the location is within this block
85 pub block: BasicBlock,
86
87 /// the location is the start of the this statement; or, if `statement_index`
88 /// == num-statements, then the start of the terminator.
89 pub statement_index: usize,
90}
91
92pub struct ScopeAuxiliaryVec {
93 pub vec: Vec<ScopeAuxiliary>
94}
95
96impl Index<ScopeId> for ScopeAuxiliaryVec {
97 type Output = ScopeAuxiliary;
98
99 #[inline]
100 fn index(&self, index: ScopeId) -> &ScopeAuxiliary {
101 &self.vec[index.index()]
102 }
103}
104
105impl IndexMut<ScopeId> for ScopeAuxiliaryVec {
106 #[inline]
107 fn index_mut(&mut self, index: ScopeId) -> &mut ScopeAuxiliary {
108 &mut self.vec[index.index()]
109 }
110}
111
e9174d1e 112///////////////////////////////////////////////////////////////////////////
7453a54e
SL
113/// The `BlockAnd` "monad" packages up the new basic block along with a
114/// produced value (sometimes just unit, of course). The `unpack!`
115/// macro (and methods below) makes working with `BlockAnd` much more
116/// convenient.
e9174d1e
SL
117
118#[must_use] // if you don't use one of these results, you're leaving a dangling edge
9cc50fc6 119pub struct BlockAnd<T>(BasicBlock, T);
e9174d1e 120
92a42be0
SL
121trait BlockAndExtension {
122 fn and<T>(self, v: T) -> BlockAnd<T>;
123 fn unit(self) -> BlockAnd<()>;
124}
125
126impl BlockAndExtension for BasicBlock {
e9174d1e
SL
127 fn and<T>(self, v: T) -> BlockAnd<T> {
128 BlockAnd(self, v)
129 }
130
131 fn unit(self) -> BlockAnd<()> {
132 BlockAnd(self, ())
133 }
134}
135
136/// Update a block pointer and return the value.
137/// Use it like `let x = unpack!(block = self.foo(block, foo))`.
138macro_rules! unpack {
139 ($x:ident = $c:expr) => {
140 {
141 let BlockAnd(b, v) = $c;
142 $x = b;
143 v
144 }
145 };
146
147 ($c:expr) => {
148 {
149 let BlockAnd(b, ()) = $c;
150 b
151 }
152 };
153}
154
155///////////////////////////////////////////////////////////////////////////
7453a54e 156/// the main entry point for building MIR for a function
e9174d1e 157
9cc50fc6 158pub fn construct<'a,'tcx>(hir: Cx<'a,'tcx>,
7453a54e 159 span: Span,
54a0048b
SL
160 fn_id: ast::NodeId,
161 body_id: ast::NodeId,
92a42be0
SL
162 implicit_arguments: Vec<Ty<'tcx>>,
163 explicit_arguments: Vec<(Ty<'tcx>, &'tcx hir::Pat)>,
92a42be0
SL
164 return_ty: FnOutput<'tcx>,
165 ast_block: &'tcx hir::Block)
54a0048b
SL
166 -> (Mir<'tcx>, ScopeAuxiliaryVec) {
167 let tcx = hir.tcx();
e9174d1e
SL
168 let cfg = CFG { basic_blocks: vec![] };
169
e9174d1e
SL
170 let mut builder = Builder {
171 hir: hir,
172 cfg: cfg,
54a0048b 173 fn_span: span,
e9174d1e 174 scopes: vec![],
54a0048b
SL
175 scope_datas: vec![],
176 scope_auxiliary: ScopeAuxiliaryVec { vec: vec![] },
e9174d1e 177 loop_scopes: vec![],
9cc50fc6 178 temp_decls: vec![],
e9174d1e
SL
179 var_decls: vec![],
180 var_indices: FnvHashMap(),
7453a54e 181 unit_temp: None,
54a0048b 182 cached_resume_block: None,
e9174d1e
SL
183 };
184
185 assert_eq!(builder.cfg.start_new_block(), START_BLOCK);
186 assert_eq!(builder.cfg.start_new_block(), END_BLOCK);
e9174d1e 187
54a0048b
SL
188
189 let mut arg_decls = None; // assigned to `Some` in closures below
190 let call_site_extent =
191 tcx.region_maps.lookup_code_extent(
192 CodeExtentData::CallSiteScope { fn_id: fn_id, body_id: body_id });
193 let _ = builder.in_scope(call_site_extent, START_BLOCK, |builder, call_site_scope_id| {
194 let mut block = START_BLOCK;
195 let arg_extent =
196 tcx.region_maps.lookup_code_extent(
197 CodeExtentData::ParameterScope { fn_id: fn_id, body_id: body_id });
198 unpack!(block = builder.in_scope(arg_extent, block, |builder, arg_scope_id| {
199 arg_decls = Some(unpack!(block = builder.args_and_body(block,
200 implicit_arguments,
201 explicit_arguments,
202 arg_scope_id,
203 ast_block)));
204 block.unit()
205 }));
206
207 builder.cfg.terminate(block, call_site_scope_id, span,
208 TerminatorKind::Goto { target: END_BLOCK });
209 builder.cfg.terminate(END_BLOCK, call_site_scope_id, span,
210 TerminatorKind::Return);
211
212 END_BLOCK.unit()
213 });
214
215 assert!(
216 builder.cfg.basic_blocks
217 .iter()
218 .enumerate()
219 .all(|(index, block)| {
220 if block.terminator.is_none() {
221 bug!("no terminator on block {:?} in fn {:?}",
222 index, fn_id)
223 }
224 true
225 }));
226
227 (
228 Mir {
229 basic_blocks: builder.cfg.basic_blocks,
230 scopes: builder.scope_datas,
231 var_decls: builder.var_decls,
232 arg_decls: arg_decls.take().expect("args never built?"),
233 temp_decls: builder.temp_decls,
234 return_ty: return_ty,
235 span: span
236 },
237 builder.scope_auxiliary,
238 )
e9174d1e
SL
239}
240
b039eaaf 241impl<'a,'tcx> Builder<'a,'tcx> {
e9174d1e
SL
242 fn args_and_body(&mut self,
243 mut block: BasicBlock,
b039eaaf 244 implicit_arguments: Vec<Ty<'tcx>>,
92a42be0 245 explicit_arguments: Vec<(Ty<'tcx>, &'tcx hir::Pat)>,
54a0048b 246 argument_scope_id: ScopeId,
b039eaaf
SL
247 ast_block: &'tcx hir::Block)
248 -> BlockAnd<Vec<ArgDecl<'tcx>>>
e9174d1e 249 {
54a0048b
SL
250 // to start, translate the argument patterns and collect the argument types.
251 let implicits = implicit_arguments.into_iter().map(|ty| (ty, None));
252 let explicits = explicit_arguments.into_iter().map(|(ty, pat)| (ty, Some(pat)));
9cc50fc6 253 let arg_decls =
54a0048b
SL
254 implicits
255 .chain(explicits)
256 .enumerate()
257 .map(|(index, (ty, pattern))| {
258 let lvalue = Lvalue::Arg(index as u32);
259 if let Some(pattern) = pattern {
260 let pattern = self.hir.irrefutable_pat(pattern);
261 unpack!(block = self.lvalue_into_pattern(block,
262 argument_scope_id,
263 pattern,
264 &lvalue));
265 }
266
267 // Make sure we drop (parts of) the argument even when not matched on.
268 let argument_extent = self.scope_auxiliary[argument_scope_id].extent;
269 self.schedule_drop(pattern.as_ref().map_or(ast_block.span, |pat| pat.span),
270 argument_extent, &lvalue, ty);
271
272 ArgDecl { ty: ty, spread: false }
273 })
274 .collect();
275
276 // start the first basic block and translate the body
277 unpack!(block = self.ast_block(&Lvalue::ReturnPointer, block, ast_block));
278
279 block.and(arg_decls)
e9174d1e 280 }
7453a54e
SL
281
282 fn get_unit_temp(&mut self) -> Lvalue<'tcx> {
283 match self.unit_temp {
284 Some(ref tmp) => tmp.clone(),
285 None => {
286 let ty = self.hir.unit_ty();
287 let tmp = self.temp(ty);
288 self.unit_temp = Some(tmp.clone());
289 tmp
290 }
291 }
292 }
e9174d1e
SL
293}
294
295///////////////////////////////////////////////////////////////////////////
296// Builder methods are broken up into modules, depending on what kind
297// of thing is being translated. Note that they use the `unpack` macro
298// above extensively.
299
300mod block;
301mod cfg;
302mod expr;
303mod into;
304mod matches;
305mod misc;
306mod scope;