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, LocalDefId}
;
17 use rustc
::middle
::region
;
19 use rustc
::mir
::visit
::{MutVisitor, TyContext}
;
20 use rustc
::ty
::{self, Ty, TyCtxt}
;
21 use rustc
::ty
::subst
::Substs
;
22 use rustc
::util
::nodemap
::NodeMap
;
23 use rustc_const_eval
::pattern
::{BindingMode, PatternKind}
;
24 use rustc_data_structures
::indexed_vec
::{IndexVec, Idx}
;
30 use syntax
::symbol
::keywords
;
32 use transform
::MirSource
;
35 /// Construct the MIR for a given def-id.
36 pub fn mir_build
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>, def_id
: DefId
) -> Mir
<'tcx
> {
37 let id
= tcx
.hir
.as_local_node_id(def_id
).unwrap();
38 let unsupported
= || {
39 span_bug
!(tcx
.hir
.span(id
), "can't build MIR for {:?}", def_id
);
42 // Figure out what primary body this item has.
43 let body_id
= match tcx
.hir
.get(id
) {
44 hir
::map
::NodeItem(item
) => {
46 hir
::ItemConst(_
, body
) |
47 hir
::ItemStatic(_
, _
, body
) |
48 hir
::ItemFn(.., body
) => body
,
52 hir
::map
::NodeTraitItem(item
) => {
54 hir
::TraitItemKind
::Const(_
, Some(body
)) |
55 hir
::TraitItemKind
::Method(_
,
56 hir
::TraitMethod
::Provided(body
)) => body
,
60 hir
::map
::NodeImplItem(item
) => {
62 hir
::ImplItemKind
::Const(_
, body
) |
63 hir
::ImplItemKind
::Method(_
, body
) => body
,
67 hir
::map
::NodeExpr(expr
) => {
68 // FIXME(eddyb) Closures should have separate
69 // function definition IDs and expression IDs.
70 // Type-checking should not let closures get
71 // this far in a constant position.
72 // Assume that everything other than closures
73 // is a constant "initializer" expression.
75 hir
::ExprClosure(_
, _
, body
, _
, _
) => body
,
76 _
=> hir
::BodyId { node_id: expr.id }
,
79 hir
::map
::NodeVariant(variant
) =>
80 return create_constructor_shim(tcx
, id
, &variant
.node
.data
),
81 hir
::map
::NodeStructCtor(ctor
) =>
82 return create_constructor_shim(tcx
, id
, ctor
),
86 tcx
.infer_ctxt().enter(|infcx
| {
87 let cx
= Cx
::new(&infcx
, id
);
88 let mut mir
= if cx
.tables().tainted_by_errors
{
89 build
::construct_error(cx
, body_id
)
90 } else if let hir
::BodyOwnerKind
::Fn
= cx
.body_owner_kind
{
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,
153 MirSource
::item(def_id
), &mir
, |_
, _
| Ok(()) );
159 /// A pass to lift all the types and substitutions in a Mir
160 /// to the global tcx. Sadly, we don't have a "folder" that
161 /// can change 'tcx so we have to transmute afterwards.
162 struct GlobalizeMir
<'a
, 'gcx
: 'a
> {
163 tcx
: TyCtxt
<'a
, 'gcx
, 'gcx
>,
167 impl<'a
, 'gcx
: 'tcx
, 'tcx
> MutVisitor
<'tcx
> for GlobalizeMir
<'a
, 'gcx
> {
168 fn visit_ty(&mut self, ty
: &mut Ty
<'tcx
>, _
: TyContext
) {
169 if let Some(lifted
) = self.tcx
.lift(ty
) {
173 "found type `{:?}` with inference types/regions in MIR",
178 fn visit_region(&mut self, region
: &mut ty
::Region
<'tcx
>, _
: Location
) {
179 if let Some(lifted
) = self.tcx
.lift(region
) {
183 "found region `{:?}` with inference types/regions in MIR",
188 fn visit_const(&mut self, constant
: &mut &'tcx ty
::Const
<'tcx
>, _
: Location
) {
189 if let Some(lifted
) = self.tcx
.lift(constant
) {
193 "found constant `{:?}` with inference types/regions in MIR",
198 fn visit_substs(&mut self, substs
: &mut &'tcx Substs
<'tcx
>, _
: Location
) {
199 if let Some(lifted
) = self.tcx
.lift(substs
) {
203 "found substs `{:?}` with inference types/regions in MIR",
209 fn create_constructor_shim
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
210 ctor_id
: ast
::NodeId
,
211 v
: &'tcx hir
::VariantData
)
214 let span
= tcx
.hir
.span(ctor_id
);
215 if let hir
::VariantData
::Tuple(ref fields
, ctor_id
) = *v
{
216 tcx
.infer_ctxt().enter(|infcx
| {
217 let mut mir
= 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,
231 MirSource
::item(tcx
.hir
.local_def_id(ctor_id
)),
232 &mir
, |_
, _
| Ok(()) );
237 span_bug
!(span
, "attempting to create MIR for non-tuple variant {:?}", v
);
241 ///////////////////////////////////////////////////////////////////////////
242 // BuildMir -- walks a crate, looking for fn items and methods to build MIR from
244 pub fn closure_self_ty
<'a
, 'gcx
, 'tcx
>(tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>,
245 closure_expr_id
: ast
::NodeId
,
246 body_id
: hir
::BodyId
)
248 let closure_expr_hir_id
= tcx
.hir
.node_to_hir_id(closure_expr_id
);
249 let closure_ty
= tcx
.body_tables(body_id
).node_id_to_type(closure_expr_hir_id
);
251 let closure_def_id
= tcx
.hir
.local_def_id(closure_expr_id
);
252 let region
= ty
::ReFree(ty
::FreeRegion
{
253 scope
: closure_def_id
,
254 bound_region
: ty
::BoundRegion
::BrEnv
,
256 let region
= tcx
.mk_region(region
);
258 match tcx
.closure_kind(closure_def_id
) {
259 ty
::ClosureKind
::Fn
=>
261 ty
::TypeAndMut
{ ty
: closure_ty
,
262 mutbl
: hir
::MutImmutable
}),
263 ty
::ClosureKind
::FnMut
=>
265 ty
::TypeAndMut
{ ty
: closure_ty
,
266 mutbl
: hir
::MutMutable
}),
267 ty
::ClosureKind
::FnOnce
=>
272 struct Builder
<'a
, 'gcx
: 'a
+'tcx
, 'tcx
: 'a
> {
273 hir
: Cx
<'a
, 'gcx
, 'tcx
>,
279 /// the current set of scopes, updated as we traverse;
280 /// see the `scope` module for more details
281 scopes
: Vec
<scope
::Scope
<'tcx
>>,
283 /// The current unsafe block in scope, even if it is hidden by
284 /// a PushUnsafeBlock
285 unpushed_unsafe
: Safety
,
287 /// The number of `push_unsafe_block` levels in scope
288 push_unsafe_count
: usize,
290 /// the current set of breakables; see the `scope` module for more
292 breakable_scopes
: Vec
<scope
::BreakableScope
<'tcx
>>,
294 /// the vector of all scopes that we have created thus far;
295 /// we track this for debuginfo later
296 visibility_scopes
: IndexVec
<VisibilityScope
, VisibilityScopeData
>,
297 visibility_scope_info
: IndexVec
<VisibilityScope
, VisibilityScopeInfo
>,
298 visibility_scope
: VisibilityScope
,
300 /// Maps node ids of variable bindings to the `Local`s created for them.
301 var_indices
: NodeMap
<Local
>,
302 local_decls
: IndexVec
<Local
, LocalDecl
<'tcx
>>,
303 unit_temp
: Option
<Lvalue
<'tcx
>>,
305 /// cached block with the RESUME terminator; this is created
306 /// when first set of cleanups are built.
307 cached_resume_block
: Option
<BasicBlock
>,
308 /// cached block with the RETURN terminator
309 cached_return_block
: Option
<BasicBlock
>,
310 /// cached block with the UNREACHABLE terminator
311 cached_unreachable_block
: Option
<BasicBlock
>,
315 basic_blocks
: IndexVec
<BasicBlock
, BasicBlockData
<'tcx
>>,
318 newtype_index
!(ScopeId
);
320 ///////////////////////////////////////////////////////////////////////////
321 /// The `BlockAnd` "monad" packages up the new basic block along with a
322 /// produced value (sometimes just unit, of course). The `unpack!`
323 /// macro (and methods below) makes working with `BlockAnd` much more
326 #[must_use] // if you don't use one of these results, you're leaving a dangling edge
327 struct BlockAnd
<T
>(BasicBlock
, T
);
329 trait BlockAndExtension
{
330 fn and
<T
>(self, v
: T
) -> BlockAnd
<T
>;
331 fn unit(self) -> BlockAnd
<()>;
334 impl BlockAndExtension
for BasicBlock
{
335 fn and
<T
>(self, v
: T
) -> BlockAnd
<T
> {
339 fn unit(self) -> BlockAnd
<()> {
344 /// Update a block pointer and return the value.
345 /// Use it like `let x = unpack!(block = self.foo(block, foo))`.
346 macro_rules
! unpack
{
347 ($x
:ident
= $c
:expr
) => {
349 let BlockAnd(b
, v
) = $c
;
357 let BlockAnd(b
, ()) = $c
;
363 ///////////////////////////////////////////////////////////////////////////
364 /// the main entry point for building MIR for a function
366 fn construct_fn
<'a
, 'gcx
, 'tcx
, A
>(hir
: Cx
<'a
, 'gcx
, 'tcx
>,
372 yield_ty
: Option
<Ty
<'gcx
>>,
373 body
: &'gcx hir
::Body
)
375 where A
: Iterator
<Item
=(Ty
<'gcx
>, Option
<&'gcx hir
::Pat
>)>
377 let arguments
: Vec
<_
> = arguments
.collect();
380 let span
= tcx
.hir
.span(fn_id
);
381 let mut builder
= Builder
::new(hir
.clone(),
387 let call_site_scope
= region
::Scope
::CallSite(body
.value
.hir_id
.local_id
);
388 let arg_scope
= region
::Scope
::Arguments(body
.value
.hir_id
.local_id
);
389 let mut block
= START_BLOCK
;
390 let source_info
= builder
.source_info(span
);
391 let call_site_s
= (call_site_scope
, source_info
);
392 unpack
!(block
= builder
.in_scope(call_site_s
, LintLevel
::Inherited
, block
, |builder
| {
393 let arg_scope_s
= (arg_scope
, source_info
);
394 unpack
!(block
= builder
.in_scope(arg_scope_s
, LintLevel
::Inherited
, block
, |builder
| {
395 builder
.args_and_body(block
, &arguments
, arg_scope
, &body
.value
)
397 // Attribute epilogue to function's closing brace
398 let fn_end
= span
.with_lo(span
.hi());
399 let source_info
= builder
.source_info(fn_end
);
400 let return_block
= builder
.return_block();
401 builder
.cfg
.terminate(block
, source_info
,
402 TerminatorKind
::Goto { target: return_block }
);
403 builder
.cfg
.terminate(return_block
, source_info
,
404 TerminatorKind
::Return
);
405 // Attribute any unreachable codepaths to the function's closing brace
406 if let Some(unreachable_block
) = builder
.cached_unreachable_block
{
407 builder
.cfg
.terminate(unreachable_block
, source_info
,
408 TerminatorKind
::Unreachable
);
412 assert_eq
!(block
, builder
.return_block());
414 let mut spread_arg
= None
;
415 if abi
== Abi
::RustCall
{
416 // RustCall pseudo-ABI untuples the last argument.
417 spread_arg
= Some(Local
::new(arguments
.len()));
420 // Gather the upvars of a closure, if any.
421 let upvar_decls
: Vec
<_
> = tcx
.with_freevars(fn_id
, |freevars
| {
422 freevars
.iter().map(|fv
| {
423 let var_id
= fv
.var_id();
424 let var_hir_id
= tcx
.hir
.node_to_hir_id(var_id
);
425 let closure_expr_id
= tcx
.hir
.local_def_id(fn_id
);
426 let capture
= hir
.tables().upvar_capture(ty
::UpvarId
{
428 closure_expr_id
: LocalDefId
::from_def_id(closure_expr_id
),
430 let by_ref
= match capture
{
431 ty
::UpvarCapture
::ByValue
=> false,
432 ty
::UpvarCapture
::ByRef(..) => true
434 let mut decl
= UpvarDecl
{
435 debug_name
: keywords
::Invalid
.name(),
438 if let Some(hir
::map
::NodeBinding(pat
)) = tcx
.hir
.find(var_id
) {
439 if let hir
::PatKind
::Binding(_
, _
, ref ident
, _
) = pat
.node
{
440 decl
.debug_name
= ident
.node
;
447 let mut mir
= builder
.finish(upvar_decls
, yield_ty
);
448 mir
.spread_arg
= spread_arg
;
452 fn construct_const
<'a
, 'gcx
, 'tcx
>(hir
: Cx
<'a
, 'gcx
, 'tcx
>,
453 body_id
: hir
::BodyId
)
456 let ast_expr
= &tcx
.hir
.body(body_id
).value
;
457 let ty
= hir
.tables().expr_ty_adjusted(ast_expr
);
458 let owner_id
= tcx
.hir
.body_owner(body_id
);
459 let span
= tcx
.hir
.span(owner_id
);
460 let mut builder
= Builder
::new(hir
.clone(), span
, 0, Safety
::Safe
, ty
);
462 let mut block
= START_BLOCK
;
463 let expr
= builder
.hir
.mirror(ast_expr
);
464 unpack
!(block
= builder
.into_expr(&Lvalue
::Local(RETURN_POINTER
), block
, expr
));
466 let source_info
= builder
.source_info(span
);
467 builder
.cfg
.terminate(block
, source_info
, TerminatorKind
::Return
);
469 // Constants can't `return` so a return block should not be created.
470 assert_eq
!(builder
.cached_return_block
, None
);
472 builder
.finish(vec
![], None
)
475 fn construct_error
<'a
, 'gcx
, 'tcx
>(hir
: Cx
<'a
, 'gcx
, 'tcx
>,
476 body_id
: hir
::BodyId
)
478 let owner_id
= hir
.tcx().hir
.body_owner(body_id
);
479 let span
= hir
.tcx().hir
.span(owner_id
);
480 let ty
= hir
.tcx().types
.err
;
481 let mut builder
= Builder
::new(hir
, span
, 0, Safety
::Safe
, ty
);
482 let source_info
= builder
.source_info(span
);
483 builder
.cfg
.terminate(START_BLOCK
, source_info
, TerminatorKind
::Unreachable
);
484 builder
.finish(vec
![], None
)
487 impl<'a
, 'gcx
, 'tcx
> Builder
<'a
, 'gcx
, 'tcx
> {
488 fn new(hir
: Cx
<'a
, 'gcx
, 'tcx
>,
493 -> Builder
<'a
, 'gcx
, 'tcx
> {
494 let lint_level
= LintLevel
::Explicit(hir
.root_lint_level
);
495 let mut builder
= Builder
{
497 cfg
: CFG { basic_blocks: IndexVec::new() }
,
501 visibility_scopes
: IndexVec
::new(),
502 visibility_scope
: ARGUMENT_VISIBILITY_SCOPE
,
503 visibility_scope_info
: IndexVec
::new(),
504 push_unsafe_count
: 0,
505 unpushed_unsafe
: safety
,
506 breakable_scopes
: vec
![],
507 local_decls
: IndexVec
::from_elem_n(LocalDecl
::new_return_pointer(return_ty
,
509 var_indices
: NodeMap(),
511 cached_resume_block
: None
,
512 cached_return_block
: None
,
513 cached_unreachable_block
: None
,
516 assert_eq
!(builder
.cfg
.start_new_block(), START_BLOCK
);
518 builder
.new_visibility_scope(span
, lint_level
, Some(safety
)),
519 ARGUMENT_VISIBILITY_SCOPE
);
520 builder
.visibility_scopes
[ARGUMENT_VISIBILITY_SCOPE
].parent_scope
= None
;
526 upvar_decls
: Vec
<UpvarDecl
>,
527 yield_ty
: Option
<Ty
<'tcx
>>)
529 for (index
, block
) in self.cfg
.basic_blocks
.iter().enumerate() {
530 if block
.terminator
.is_none() {
531 span_bug
!(self.fn_span
, "no terminator on block {:?}", index
);
535 Mir
::new(self.cfg
.basic_blocks
,
536 self.visibility_scopes
,
537 ClearOnDecode
::Set(self.visibility_scope_info
),
547 fn args_and_body(&mut self,
548 mut block
: BasicBlock
,
549 arguments
: &[(Ty
<'gcx
>, Option
<&'gcx hir
::Pat
>)],
550 argument_scope
: region
::Scope
,
551 ast_body
: &'gcx hir
::Expr
)
554 // Allocate locals for the function arguments
555 for &(ty
, pattern
) in arguments
.iter() {
556 // If this is a simple binding pattern, give the local a nice name for debuginfo.
558 if let Some(pat
) = pattern
{
559 if let hir
::PatKind
::Binding(_
, _
, ref ident
, _
) = pat
.node
{
560 name
= Some(ident
.node
);
564 self.local_decls
.push(LocalDecl
{
565 mutability
: Mutability
::Not
,
567 source_info
: SourceInfo
{
568 scope
: ARGUMENT_VISIBILITY_SCOPE
,
569 span
: pattern
.map_or(self.fn_span
, |pat
| pat
.span
)
571 lexical_scope
: ARGUMENT_VISIBILITY_SCOPE
,
574 is_user_variable
: false,
578 let mut scope
= None
;
579 // Bind the argument patterns
580 for (index
, &(ty
, pattern
)) in arguments
.iter().enumerate() {
581 // Function arguments always get the first Local indices after the return pointer
582 let local
= Local
::new(index
+ 1);
583 let lvalue
= Lvalue
::Local(local
);
585 if let Some(pattern
) = pattern
{
586 let pattern
= self.hir
.pattern_from_hir(pattern
);
588 match *pattern
.kind
{
589 // Don't introduce extra copies for simple bindings
590 PatternKind
::Binding { mutability, var, mode: BindingMode::ByValue, .. }
=> {
591 self.local_decls
[local
].mutability
= mutability
;
592 self.var_indices
.insert(var
, local
);
595 scope
= self.declare_bindings(scope
, ast_body
.span
,
596 LintLevel
::Inherited
, &pattern
);
597 unpack
!(block
= self.lvalue_into_pattern(block
, pattern
, &lvalue
));
602 // Make sure we drop (parts of) the argument even when not matched on.
603 self.schedule_drop(pattern
.as_ref().map_or(ast_body
.span
, |pat
| pat
.span
),
604 argument_scope
, &lvalue
, ty
);
608 // Enter the argument pattern bindings visibility scope, if it exists.
609 if let Some(visibility_scope
) = scope
{
610 self.visibility_scope
= visibility_scope
;
613 let body
= self.hir
.mirror(ast_body
);
614 self.into(&Lvalue
::Local(RETURN_POINTER
), block
, body
)
617 fn get_unit_temp(&mut self) -> Lvalue
<'tcx
> {
618 match self.unit_temp
{
619 Some(ref tmp
) => tmp
.clone(),
621 let ty
= self.hir
.unit_ty();
622 let fn_span
= self.fn_span
;
623 let tmp
= self.temp(ty
, fn_span
);
624 self.unit_temp
= Some(tmp
.clone());
630 fn return_block(&mut self) -> BasicBlock
{
631 match self.cached_return_block
{
634 let rb
= self.cfg
.start_new_block();
635 self.cached_return_block
= Some(rb
);
641 fn unreachable_block(&mut self) -> BasicBlock
{
642 match self.cached_unreachable_block
{
645 let ub
= self.cfg
.start_new_block();
646 self.cached_unreachable_block
= Some(ub
);
653 ///////////////////////////////////////////////////////////////////////////
654 // Builder methods are broken up into modules, depending on what kind
655 // of thing is being translated. Note that they use the `unpack` macro
656 // above extensively.