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.
16 use rustc
::hir
::def_id
::DefId
;
17 use rustc
::middle
::region
;
19 use rustc
::mir
::transform
::MirSource
;
20 use rustc
::mir
::visit
::{MutVisitor, Lookup}
;
21 use rustc
::ty
::{self, Ty, TyCtxt}
;
22 use rustc
::ty
::subst
::Substs
;
23 use rustc
::util
::nodemap
::NodeMap
;
24 use rustc_data_structures
::indexed_vec
::{IndexVec, Idx}
;
30 use syntax
::symbol
::keywords
;
34 /// Construct the MIR for a given def-id.
35 pub fn mir_build
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>, def_id
: DefId
) -> Mir
<'tcx
> {
36 let id
= tcx
.hir
.as_local_node_id(def_id
).unwrap();
37 let unsupported
= || {
38 span_bug
!(tcx
.hir
.span(id
), "can't build MIR for {:?}", def_id
);
41 // Figure out what primary body this item has.
42 let body_id
= match tcx
.hir
.get(id
) {
43 hir
::map
::NodeItem(item
) => {
45 hir
::ItemConst(_
, body
) |
46 hir
::ItemStatic(_
, _
, body
) |
47 hir
::ItemFn(.., body
) => body
,
51 hir
::map
::NodeTraitItem(item
) => {
53 hir
::TraitItemKind
::Const(_
, Some(body
)) |
54 hir
::TraitItemKind
::Method(_
,
55 hir
::TraitMethod
::Provided(body
)) => body
,
59 hir
::map
::NodeImplItem(item
) => {
61 hir
::ImplItemKind
::Const(_
, body
) |
62 hir
::ImplItemKind
::Method(_
, body
) => body
,
66 hir
::map
::NodeExpr(expr
) => {
67 // FIXME(eddyb) Closures should have separate
68 // function definition IDs and expression IDs.
69 // Type-checking should not let closures get
70 // this far in a constant position.
71 // Assume that everything other than closures
72 // is a constant "initializer" expression.
74 hir
::ExprClosure(_
, _
, body
, _
, _
) => body
,
75 _
=> hir
::BodyId { node_id: expr.id }
,
78 hir
::map
::NodeVariant(variant
) =>
79 return create_constructor_shim(tcx
, id
, &variant
.node
.data
),
80 hir
::map
::NodeStructCtor(ctor
) =>
81 return create_constructor_shim(tcx
, id
, ctor
),
85 let src
= MirSource
::from_node(tcx
, id
);
86 tcx
.infer_ctxt().enter(|infcx
| {
87 let cx
= Cx
::new(&infcx
, src
);
88 let mut mir
= if cx
.tables().tainted_by_errors
{
89 build
::construct_error(cx
, body_id
)
90 } else if let MirSource
::Fn(id
) = src
{
91 // fetch the fully liberated fn signature (that is, all bound
92 // types/lifetimes replaced)
93 let fn_hir_id
= tcx
.hir
.node_to_hir_id(id
);
94 let fn_sig
= cx
.tables().liberated_fn_sigs()[fn_hir_id
].clone();
96 let ty
= tcx
.type_of(tcx
.hir
.local_def_id(id
));
97 let mut abi
= fn_sig
.abi
;
98 let implicit_argument
= match ty
.sty
{
99 ty
::TyClosure(..) => {
100 // HACK(eddyb) Avoid having RustCall on closures,
101 // as it adds unnecessary (and wrong) auto-tupling.
103 Some((closure_self_ty(tcx
, id
, body_id
), None
))
105 ty
::TyGenerator(..) => {
106 let gen_ty
= tcx
.body_tables(body_id
).node_id_to_type(fn_hir_id
);
112 // FIXME: safety in closures
113 let safety
= match fn_sig
.unsafety
{
114 hir
::Unsafety
::Normal
=> Safety
::Safe
,
115 hir
::Unsafety
::Unsafe
=> Safety
::FnUnsafe
,
118 let body
= tcx
.hir
.body(body_id
);
119 let explicit_arguments
=
123 .map(|(index
, arg
)| {
124 (fn_sig
.inputs()[index
], Some(&*arg
.pat
))
127 let arguments
= implicit_argument
.into_iter().chain(explicit_arguments
);
129 let (yield_ty
, return_ty
) = if body
.is_generator
{
130 let gen_sig
= cx
.tables().generator_sigs()[fn_hir_id
].clone().unwrap();
131 (Some(gen_sig
.yield_ty
), gen_sig
.return_ty
)
133 (None
, fn_sig
.output())
136 build
::construct_fn(cx
, id
, arguments
, safety
, abi
,
137 return_ty
, yield_ty
, body
)
139 build
::construct_const(cx
, body_id
)
142 // Convert the Mir to global types.
143 let mut globalizer
= GlobalizeMir
{
147 globalizer
.visit_mir(&mut mir
);
149 mem
::transmute
::<Mir
, Mir
<'tcx
>>(mir
)
152 mir_util
::dump_mir(tcx
, None
, "mir_map", &0, src
, &mir
);
158 /// A pass to lift all the types and substitutions in a Mir
159 /// to the global tcx. Sadly, we don't have a "folder" that
160 /// can change 'tcx so we have to transmute afterwards.
161 struct GlobalizeMir
<'a
, 'gcx
: 'a
> {
162 tcx
: TyCtxt
<'a
, 'gcx
, 'gcx
>,
166 impl<'a
, 'gcx
: 'tcx
, 'tcx
> MutVisitor
<'tcx
> for GlobalizeMir
<'a
, 'gcx
> {
167 fn visit_ty(&mut self, ty
: &mut Ty
<'tcx
>, _
: Lookup
) {
168 if let Some(lifted
) = self.tcx
.lift(ty
) {
172 "found type `{:?}` with inference types/regions in MIR",
177 fn visit_region(&mut self, region
: &mut ty
::Region
<'tcx
>, _
: Location
) {
178 if let Some(lifted
) = self.tcx
.lift(region
) {
182 "found region `{:?}` with inference types/regions in MIR",
187 fn visit_const(&mut self, constant
: &mut &'tcx ty
::Const
<'tcx
>, _
: Location
) {
188 if let Some(lifted
) = self.tcx
.lift(constant
) {
192 "found constant `{:?}` with inference types/regions in MIR",
197 fn visit_substs(&mut self, substs
: &mut &'tcx Substs
<'tcx
>, _
: Location
) {
198 if let Some(lifted
) = self.tcx
.lift(substs
) {
202 "found substs `{:?}` with inference types/regions in MIR",
208 fn create_constructor_shim
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
209 ctor_id
: ast
::NodeId
,
210 v
: &'tcx hir
::VariantData
)
213 let span
= tcx
.hir
.span(ctor_id
);
214 if let hir
::VariantData
::Tuple(ref fields
, ctor_id
) = *v
{
215 tcx
.infer_ctxt().enter(|infcx
| {
217 shim
::build_adt_ctor(&infcx
, ctor_id
, fields
, span
);
219 // Convert the Mir to global types.
220 let tcx
= infcx
.tcx
.global_tcx();
221 let mut globalizer
= GlobalizeMir
{
225 globalizer
.visit_mir(&mut mir
);
227 mem
::transmute
::<Mir
, Mir
<'tcx
>>(mir
)
230 mir_util
::dump_mir(tcx
, None
, "mir_map", &0, src
, &mir
);
235 span_bug
!(span
, "attempting to create MIR for non-tuple variant {:?}", v
);
239 ///////////////////////////////////////////////////////////////////////////
240 // BuildMir -- walks a crate, looking for fn items and methods to build MIR from
242 pub fn closure_self_ty
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
243 closure_expr_id
: ast
::NodeId
,
244 body_id
: hir
::BodyId
)
246 let closure_expr_hir_id
= tcx
.hir
.node_to_hir_id(closure_expr_id
);
247 let closure_ty
= tcx
.body_tables(body_id
).node_id_to_type(closure_expr_hir_id
);
249 let closure_def_id
= tcx
.hir
.local_def_id(closure_expr_id
);
250 let region
= ty
::ReFree(ty
::FreeRegion
{
251 scope
: closure_def_id
,
252 bound_region
: ty
::BoundRegion
::BrEnv
,
254 let region
= tcx
.mk_region(region
);
256 match tcx
.closure_kind(closure_def_id
) {
257 ty
::ClosureKind
::Fn
=>
259 ty
::TypeAndMut
{ ty
: closure_ty
,
260 mutbl
: hir
::MutImmutable
}),
261 ty
::ClosureKind
::FnMut
=>
263 ty
::TypeAndMut
{ ty
: closure_ty
,
264 mutbl
: hir
::MutMutable
}),
265 ty
::ClosureKind
::FnOnce
=>
270 struct Builder
<'a
, 'gcx
: 'a
+'tcx
, 'tcx
: 'a
> {
271 hir
: Cx
<'a
, 'gcx
, 'tcx
>,
277 /// the current set of scopes, updated as we traverse;
278 /// see the `scope` module for more details
279 scopes
: Vec
<scope
::Scope
<'tcx
>>,
281 /// The current unsafe block in scope, even if it is hidden by
282 /// a PushUnsafeBlock
283 unpushed_unsafe
: Safety
,
285 /// The number of `push_unsafe_block` levels in scope
286 push_unsafe_count
: usize,
288 /// the current set of breakables; see the `scope` module for more
290 breakable_scopes
: Vec
<scope
::BreakableScope
<'tcx
>>,
292 /// the vector of all scopes that we have created thus far;
293 /// we track this for debuginfo later
294 visibility_scopes
: IndexVec
<VisibilityScope
, VisibilityScopeData
>,
295 visibility_scope_info
: IndexVec
<VisibilityScope
, VisibilityScopeInfo
>,
296 visibility_scope
: VisibilityScope
,
298 /// Maps node ids of variable bindings to the `Local`s created for them.
299 var_indices
: NodeMap
<Local
>,
300 local_decls
: IndexVec
<Local
, LocalDecl
<'tcx
>>,
301 unit_temp
: Option
<Lvalue
<'tcx
>>,
303 /// cached block with the RESUME terminator; this is created
304 /// when first set of cleanups are built.
305 cached_resume_block
: Option
<BasicBlock
>,
306 /// cached block with the RETURN terminator
307 cached_return_block
: Option
<BasicBlock
>,
311 basic_blocks
: IndexVec
<BasicBlock
, BasicBlockData
<'tcx
>>,
314 newtype_index
!(ScopeId
);
316 ///////////////////////////////////////////////////////////////////////////
317 /// The `BlockAnd` "monad" packages up the new basic block along with a
318 /// produced value (sometimes just unit, of course). The `unpack!`
319 /// macro (and methods below) makes working with `BlockAnd` much more
322 #[must_use] // if you don't use one of these results, you're leaving a dangling edge
323 struct BlockAnd
<T
>(BasicBlock
, T
);
325 trait BlockAndExtension
{
326 fn and
<T
>(self, v
: T
) -> BlockAnd
<T
>;
327 fn unit(self) -> BlockAnd
<()>;
330 impl BlockAndExtension
for BasicBlock
{
331 fn and
<T
>(self, v
: T
) -> BlockAnd
<T
> {
335 fn unit(self) -> BlockAnd
<()> {
340 /// Update a block pointer and return the value.
341 /// Use it like `let x = unpack!(block = self.foo(block, foo))`.
342 macro_rules
! unpack
{
343 ($x
:ident
= $c
:expr
) => {
345 let BlockAnd(b
, v
) = $c
;
353 let BlockAnd(b
, ()) = $c
;
359 ///////////////////////////////////////////////////////////////////////////
360 /// the main entry point for building MIR for a function
362 fn construct_fn
<'a
, 'gcx
, 'tcx
, A
>(hir
: Cx
<'a
, 'gcx
, 'tcx
>,
368 yield_ty
: Option
<Ty
<'gcx
>>,
369 body
: &'gcx hir
::Body
)
371 where A
: Iterator
<Item
=(Ty
<'gcx
>, Option
<&'gcx hir
::Pat
>)>
373 let arguments
: Vec
<_
> = arguments
.collect();
376 let span
= tcx
.hir
.span(fn_id
);
377 let mut builder
= Builder
::new(hir
.clone(),
383 let call_site_scope
= region
::Scope
::CallSite(body
.value
.hir_id
.local_id
);
384 let arg_scope
= region
::Scope
::Arguments(body
.value
.hir_id
.local_id
);
385 let mut block
= START_BLOCK
;
386 let source_info
= builder
.source_info(span
);
387 let call_site_s
= (call_site_scope
, source_info
);
388 unpack
!(block
= builder
.in_scope(call_site_s
, LintLevel
::Inherited
, block
, |builder
| {
389 let arg_scope_s
= (arg_scope
, source_info
);
390 unpack
!(block
= builder
.in_scope(arg_scope_s
, LintLevel
::Inherited
, block
, |builder
| {
391 builder
.args_and_body(block
, &arguments
, arg_scope
, &body
.value
)
393 // Attribute epilogue to function's closing brace
394 let fn_end
= span
.with_lo(span
.hi());
395 let source_info
= builder
.source_info(fn_end
);
396 let return_block
= builder
.return_block();
397 builder
.cfg
.terminate(block
, source_info
,
398 TerminatorKind
::Goto { target: return_block }
);
399 builder
.cfg
.terminate(return_block
, source_info
,
400 TerminatorKind
::Return
);
403 assert_eq
!(block
, builder
.return_block());
405 let mut spread_arg
= None
;
406 if abi
== Abi
::RustCall
{
407 // RustCall pseudo-ABI untuples the last argument.
408 spread_arg
= Some(Local
::new(arguments
.len()));
411 // Gather the upvars of a closure, if any.
412 let upvar_decls
: Vec
<_
> = tcx
.with_freevars(fn_id
, |freevars
| {
413 freevars
.iter().map(|fv
| {
414 let var_id
= fv
.var_id();
415 let var_hir_id
= tcx
.hir
.node_to_hir_id(var_id
);
416 let closure_expr_id
= tcx
.hir
.local_def_id(fn_id
).index
;
417 let capture
= hir
.tables().upvar_capture(ty
::UpvarId
{
421 let by_ref
= match capture
{
422 ty
::UpvarCapture
::ByValue
=> false,
423 ty
::UpvarCapture
::ByRef(..) => true
425 let mut decl
= UpvarDecl
{
426 debug_name
: keywords
::Invalid
.name(),
429 if let Some(hir
::map
::NodeBinding(pat
)) = tcx
.hir
.find(var_id
) {
430 if let hir
::PatKind
::Binding(_
, _
, ref ident
, _
) = pat
.node
{
431 decl
.debug_name
= ident
.node
;
438 let mut mir
= builder
.finish(upvar_decls
, return_ty
, yield_ty
);
439 mir
.spread_arg
= spread_arg
;
443 fn construct_const
<'a
, 'gcx
, 'tcx
>(hir
: Cx
<'a
, 'gcx
, 'tcx
>,
444 body_id
: hir
::BodyId
)
447 let ast_expr
= &tcx
.hir
.body(body_id
).value
;
448 let ty
= hir
.tables().expr_ty_adjusted(ast_expr
);
449 let owner_id
= tcx
.hir
.body_owner(body_id
);
450 let span
= tcx
.hir
.span(owner_id
);
451 let mut builder
= Builder
::new(hir
.clone(), span
, 0, Safety
::Safe
, ty
);
453 let mut block
= START_BLOCK
;
454 let expr
= builder
.hir
.mirror(ast_expr
);
455 unpack
!(block
= builder
.into_expr(&Lvalue
::Local(RETURN_POINTER
), block
, expr
));
457 let source_info
= builder
.source_info(span
);
458 builder
.cfg
.terminate(block
, source_info
, TerminatorKind
::Return
);
460 // Constants can't `return` so a return block should not be created.
461 assert_eq
!(builder
.cached_return_block
, None
);
463 builder
.finish(vec
![], ty
, None
)
466 fn construct_error
<'a
, 'gcx
, 'tcx
>(hir
: Cx
<'a
, 'gcx
, 'tcx
>,
467 body_id
: hir
::BodyId
)
469 let owner_id
= hir
.tcx().hir
.body_owner(body_id
);
470 let span
= hir
.tcx().hir
.span(owner_id
);
471 let ty
= hir
.tcx().types
.err
;
472 let mut builder
= Builder
::new(hir
, span
, 0, Safety
::Safe
, ty
);
473 let source_info
= builder
.source_info(span
);
474 builder
.cfg
.terminate(START_BLOCK
, source_info
, TerminatorKind
::Unreachable
);
475 builder
.finish(vec
![], ty
, None
)
478 impl<'a
, 'gcx
, 'tcx
> Builder
<'a
, 'gcx
, 'tcx
> {
479 fn new(hir
: Cx
<'a
, 'gcx
, 'tcx
>,
484 -> Builder
<'a
, 'gcx
, 'tcx
> {
485 let lint_level
= LintLevel
::Explicit(hir
.root_lint_level
);
486 let mut builder
= Builder
{
488 cfg
: CFG { basic_blocks: IndexVec::new() }
,
492 visibility_scopes
: IndexVec
::new(),
493 visibility_scope
: ARGUMENT_VISIBILITY_SCOPE
,
494 visibility_scope_info
: IndexVec
::new(),
495 push_unsafe_count
: 0,
496 unpushed_unsafe
: safety
,
497 breakable_scopes
: vec
![],
498 local_decls
: IndexVec
::from_elem_n(LocalDecl
::new_return_pointer(return_ty
,
500 var_indices
: NodeMap(),
502 cached_resume_block
: None
,
503 cached_return_block
: None
506 assert_eq
!(builder
.cfg
.start_new_block(), START_BLOCK
);
508 builder
.new_visibility_scope(span
, lint_level
, Some(safety
)),
509 ARGUMENT_VISIBILITY_SCOPE
);
510 builder
.visibility_scopes
[ARGUMENT_VISIBILITY_SCOPE
].parent_scope
= None
;
516 upvar_decls
: Vec
<UpvarDecl
>,
518 yield_ty
: Option
<Ty
<'tcx
>>)
520 for (index
, block
) in self.cfg
.basic_blocks
.iter().enumerate() {
521 if block
.terminator
.is_none() {
522 span_bug
!(self.fn_span
, "no terminator on block {:?}", index
);
526 Mir
::new(self.cfg
.basic_blocks
,
527 self.visibility_scopes
,
528 ClearOnDecode
::Set(self.visibility_scope_info
),
539 fn args_and_body(&mut self,
540 mut block
: BasicBlock
,
541 arguments
: &[(Ty
<'gcx
>, Option
<&'gcx hir
::Pat
>)],
542 argument_scope
: region
::Scope
,
543 ast_body
: &'gcx hir
::Expr
)
546 // Allocate locals for the function arguments
547 for &(ty
, pattern
) in arguments
.iter() {
548 // If this is a simple binding pattern, give the local a nice name for debuginfo.
550 if let Some(pat
) = pattern
{
551 if let hir
::PatKind
::Binding(_
, _
, ref ident
, _
) = pat
.node
{
552 name
= Some(ident
.node
);
556 self.local_decls
.push(LocalDecl
{
557 mutability
: Mutability
::Not
,
559 source_info
: SourceInfo
{
560 scope
: ARGUMENT_VISIBILITY_SCOPE
,
561 span
: pattern
.map_or(self.fn_span
, |pat
| pat
.span
)
563 lexical_scope
: ARGUMENT_VISIBILITY_SCOPE
,
566 is_user_variable
: false,
570 let mut scope
= None
;
571 // Bind the argument patterns
572 for (index
, &(ty
, pattern
)) in arguments
.iter().enumerate() {
573 // Function arguments always get the first Local indices after the return pointer
574 let lvalue
= Lvalue
::Local(Local
::new(index
+ 1));
576 if let Some(pattern
) = pattern
{
577 let pattern
= self.hir
.pattern_from_hir(pattern
);
578 scope
= self.declare_bindings(scope
, ast_body
.span
,
579 LintLevel
::Inherited
, &pattern
);
580 unpack
!(block
= self.lvalue_into_pattern(block
, pattern
, &lvalue
));
583 // Make sure we drop (parts of) the argument even when not matched on.
584 self.schedule_drop(pattern
.as_ref().map_or(ast_body
.span
, |pat
| pat
.span
),
585 argument_scope
, &lvalue
, ty
);
589 // Enter the argument pattern bindings visibility scope, if it exists.
590 if let Some(visibility_scope
) = scope
{
591 self.visibility_scope
= visibility_scope
;
594 let body
= self.hir
.mirror(ast_body
);
595 self.into(&Lvalue
::Local(RETURN_POINTER
), block
, body
)
598 fn get_unit_temp(&mut self) -> Lvalue
<'tcx
> {
599 match self.unit_temp
{
600 Some(ref tmp
) => tmp
.clone(),
602 let ty
= self.hir
.unit_ty();
603 let fn_span
= self.fn_span
;
604 let tmp
= self.temp(ty
, fn_span
);
605 self.unit_temp
= Some(tmp
.clone());
611 fn return_block(&mut self) -> BasicBlock
{
612 match self.cached_return_block
{
615 let rb
= self.cfg
.start_new_block();
616 self.cached_return_block
= Some(rb
);
623 ///////////////////////////////////////////////////////////////////////////
624 // Builder methods are broken up into modules, depending on what kind
625 // of thing is being translated. Note that they use the `unpack` macro
626 // above extensively.