]>
Commit | Line | Data |
---|---|---|
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 | 11 | use hair::cx::Cx; |
54a0048b SL |
12 | use rustc::middle::region::{CodeExtent, CodeExtentData}; |
13 | use rustc::ty::{FnOutput, Ty}; | |
92a42be0 | 14 | use rustc::mir::repr::*; |
e9174d1e | 15 | use rustc_data_structures::fnv::FnvHashMap; |
54a0048b SL |
16 | use rustc::hir; |
17 | use std::ops::{Index, IndexMut}; | |
b039eaaf SL |
18 | use syntax::ast; |
19 | use syntax::codemap::Span; | |
b039eaaf | 20 | |
9cc50fc6 | 21 | pub 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 |
56 | struct 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. | |
71 | pub 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)] | |
83 | pub 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 | ||
92 | pub struct ScopeAuxiliaryVec { | |
93 | pub vec: Vec<ScopeAuxiliary> | |
94 | } | |
95 | ||
96 | impl 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 | ||
105 | impl 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 | 119 | pub struct BlockAnd<T>(BasicBlock, T); |
e9174d1e | 120 | |
92a42be0 SL |
121 | trait BlockAndExtension { |
122 | fn and<T>(self, v: T) -> BlockAnd<T>; | |
123 | fn unit(self) -> BlockAnd<()>; | |
124 | } | |
125 | ||
126 | impl 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))`. | |
138 | macro_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 | 158 | pub 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 | 241 | impl<'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 | ||
300 | mod block; | |
301 | mod cfg; | |
302 | mod expr; | |
303 | mod into; | |
304 | mod matches; | |
305 | mod misc; | |
306 | mod scope; |