1 // Copyright 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.
11 use rustc::middle::const_eval::ConstVal;
12 use rustc::middle::def_id::DefId;
13 use rustc::middle::region::CodeExtent;
14 use rustc::middle::subst::Substs;
15 use rustc::middle::ty::{AdtDef, ClosureSubsts, FnOutput, Region, Ty};
16 use rustc_back::slice;
17 use rustc_data_structures::fnv::FnvHashMap;
18 use rustc_front::hir::InlineAsm;
19 use syntax::ast::Name;
20 use syntax::codemap::Span;
21 use std::fmt::{Debug, Formatter, Error};
24 /// Lowered representation of a single function.
25 pub struct Mir<'tcx> {
26 /// List of basic blocks. References to basic block use a newtyped index type `BasicBlock`
27 /// that indexes into this vector.
28 pub basic_blocks: Vec<BasicBlockData<'tcx>>,
30 /// Return type of the function.
31 pub return_ty: FnOutput<'tcx>,
33 /// Variables: these are stack slots corresponding to user variables. They may be
34 /// assigned many times.
35 pub var_decls: Vec<VarDecl<'tcx>>,
37 /// Args: these are stack slots corresponding to the input arguments.
38 pub arg_decls: Vec<ArgDecl<'tcx>>,
40 /// Temp declarations: stack slots that for temporaries created by
41 /// the compiler. These are assigned once, but they are not SSA
42 /// values in that it is possible to borrow them and mutate them
43 /// through the resulting reference.
44 pub temp_decls: Vec<TempDecl<'tcx>>,
47 /// where execution begins
48 pub const START_BLOCK: BasicBlock = BasicBlock(0);
50 /// where execution ends, on normal return
51 pub const END_BLOCK: BasicBlock = BasicBlock(1);
53 /// where execution ends, on panic
54 pub const DIVERGE_BLOCK: BasicBlock = BasicBlock(2);
56 impl<'tcx> Mir<'tcx> {
57 pub fn all_basic_blocks(&self) -> Vec<BasicBlock> {
58 (0..self.basic_blocks.len())
59 .map(|i| BasicBlock::new(i))
63 pub fn basic_block_data(&self, bb: BasicBlock) -> &BasicBlockData<'tcx> {
64 &self.basic_blocks[bb.index()]
67 pub fn basic_block_data_mut(&mut self, bb: BasicBlock) -> &mut BasicBlockData<'tcx> {
68 &mut self.basic_blocks[bb.index()]
72 ///////////////////////////////////////////////////////////////////////////
73 // Mutability and borrow kinds
75 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
81 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
83 /// Data must be immutable and is aliasable.
86 /// Data must be immutable but not aliasable. This kind of borrow
87 /// cannot currently be expressed by the user and is used only in
88 /// implicit closure bindings. It is needed when you the closure
89 /// is borrowing or mutating a mutable referent, e.g.:
91 /// let x: &mut isize = ...;
92 /// let y = || *x += 5;
94 /// If we were to try to translate this closure into a more explicit
95 /// form, we'd encounter an error with the code as written:
97 /// struct Env { x: & &mut isize }
98 /// let x: &mut isize = ...;
99 /// let y = (&mut Env { &x }, fn_ptr); // Closure is pair of env and fn
100 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
102 /// This is then illegal because you cannot mutate a `&mut` found
103 /// in an aliasable location. To solve, you'd have to translate with
104 /// an `&mut` borrow:
106 /// struct Env { x: & &mut isize }
107 /// let x: &mut isize = ...;
108 /// let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
109 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
111 /// Now the assignment to `**env.x` is legal, but creating a
112 /// mutable pointer to `x` is not because `x` is not mutable. We
113 /// could fix this by declaring `x` as `let mut x`. This is ok in
114 /// user code, if awkward, but extra weird for closures, since the
115 /// borrow is hidden.
117 /// So we introduce a "unique imm" borrow -- the referent is
118 /// immutable, but not aliasable. This solves the problem. For
119 /// simplicity, we don't give users the way to express this
120 /// borrow, it's just used when translating closures.
123 /// Data is mutable and not aliasable.
127 ///////////////////////////////////////////////////////////////////////////
128 // Variables and temps
130 // A "variable" is a binding declared by the user as part of the fn
132 pub struct VarDecl<'tcx> {
133 pub mutability: Mutability,
138 // A "temp" is a temporary that we place on the stack. They are
139 // anonymous, always mutable, and have only a type.
140 pub struct TempDecl<'tcx> {
144 // A "arg" is one of the function's formal arguments. These are
145 // anonymous and distinct from the bindings that the user declares.
147 // For example, in this function:
150 // fn foo((x, y): (i32, u32)) { ... }
153 // there is only one argument, of type `(i32, u32)`, but two bindings
155 pub struct ArgDecl<'tcx> {
159 ///////////////////////////////////////////////////////////////////////////
162 /// A moment in the flow of execution. It corresponds to a point in
163 /// between two statements:
166 /// <--- if statement == 0
168 /// <--- if statement == 1
171 /// <--- if statement == n-1
173 /// <--- if statement == n
175 /// where the block has `n` statements.
176 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
177 pub struct ExecutionPoint {
178 pub block: BasicBlock,
182 /// A single-entry-multiple-exit region in the graph. We build one of
183 /// these for every node-id during MIR construction. By construction
184 /// we are assured that the entry dominates all points within, and
185 /// that, for every interior point X, it is postdominated by some exit.
186 pub struct GraphExtent {
187 pub entry: ExecutionPoint,
188 pub exit: GraphExtentExit,
191 pub enum GraphExtentExit {
192 /// `Statement(X)`: a very common special case covering a span
193 /// that is local to a single block. It starts at the entry point
194 /// and extends until the start of statement `X` (non-inclusive).
197 /// The more general case where the exits are a set of points.
198 Points(Vec<ExecutionPoint>),
201 ///////////////////////////////////////////////////////////////////////////
204 /// The index of a particular basic block. The index is into the `basic_blocks`
205 /// list of the `Mir`.
207 /// (We use a `u32` internally just to save memory.)
208 #[derive(Copy, Clone, PartialEq, Eq)]
209 pub struct BasicBlock(u32);
212 pub fn new(index: usize) -> BasicBlock {
213 assert!(index < (u32::MAX as usize));
214 BasicBlock(index as u32)
217 /// Extract the index.
218 pub fn index(self) -> usize {
223 impl Debug for BasicBlock {
224 fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
225 write!(fmt, "BB({})", self.0)
229 ///////////////////////////////////////////////////////////////////////////
230 // BasicBlock and Terminator
233 pub struct BasicBlockData<'tcx> {
234 pub statements: Vec<Statement<'tcx>>,
235 pub terminator: Terminator<'tcx>,
238 pub enum Terminator<'tcx> {
239 /// block should have one successor in the graph; we jump there
244 /// block should initiate unwinding; should be one successor
245 /// that does cleanup and branches to DIVERGE_BLOCK
250 /// jump to branch 0 if this lvalue evaluates to true
253 targets: [BasicBlock; 2],
256 /// lvalue evaluates to some enum; jump depending on the branch
259 adt_def: AdtDef<'tcx>,
260 targets: Vec<BasicBlock>,
263 /// operand evaluates to an integer; jump depending on its value
264 /// to one of the targets, and otherwise fallback to `otherwise`
266 /// discriminant value being tested
269 /// type of value being tested
272 /// Possible values. The locations to branch to in each case
273 /// are found in the corresponding indices from the `targets` vector.
274 values: Vec<ConstVal>,
276 /// Possible branch sites. The length of this vector should be
277 /// equal to the length of the `values` vector plus 1 -- the
278 /// extra item is the block to branch to if none of the values
280 targets: Vec<BasicBlock>,
283 /// Indicates that the last statement in the block panics, aborts,
284 /// etc. No successors. This terminator appears on exactly one
285 /// basic block which we create in advance. However, during
286 /// construction, we use this value as a sentinel for "terminator
287 /// not yet assigned", and assert at the end that only the
288 /// well-known diverging block actually diverges.
291 /// Indicates a normal return. The ReturnPointer lvalue should
292 /// have been filled in by now. This should only occur in the
296 /// block ends with a call; it should have two successors. The
297 /// first successor indicates normal return. The second indicates
300 data: CallData<'tcx>,
301 targets: [BasicBlock; 2],
305 impl<'tcx> Terminator<'tcx> {
306 pub fn successors(&self) -> &[BasicBlock] {
307 use self::Terminator::*;
309 Goto { target: ref b } => slice::ref_slice(b),
310 Panic { target: ref b } => slice::ref_slice(b),
311 If { cond: _, targets: ref b } => b,
312 Switch { targets: ref b, .. } => b,
313 SwitchInt { targets: ref b, .. } => b,
316 Call { data: _, targets: ref b } => b,
320 pub fn successors_mut(&mut self) -> &mut [BasicBlock] {
321 use self::Terminator::*;
323 Goto { target: ref mut b } => slice::mut_ref_slice(b),
324 Panic { target: ref mut b } => slice::mut_ref_slice(b),
325 If { cond: _, targets: ref mut b } => b,
326 Switch { targets: ref mut b, .. } => b,
327 SwitchInt { targets: ref mut b, .. } => b,
330 Call { data: _, targets: ref mut b } => b,
336 pub struct CallData<'tcx> {
337 /// where the return value is written to
338 pub destination: Lvalue<'tcx>,
340 /// the fn being called
341 pub func: Operand<'tcx>,
344 pub args: Vec<Operand<'tcx>>,
347 impl<'tcx> BasicBlockData<'tcx> {
348 pub fn new(terminator: Terminator<'tcx>) -> BasicBlockData<'tcx> {
351 terminator: terminator,
356 impl<'tcx> Debug for Terminator<'tcx> {
357 fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
358 use self::Terminator::*;
361 write!(fmt, "goto -> {:?}", target),
363 write!(fmt, "panic -> {:?}", target),
364 If { cond: ref lv, ref targets } =>
365 write!(fmt, "if({:?}) -> {:?}", lv, targets),
366 Switch { discr: ref lv, adt_def: _, ref targets } =>
367 write!(fmt, "switch({:?}) -> {:?}", lv, targets),
368 SwitchInt { discr: ref lv, switch_ty: _, ref values, ref targets } =>
369 write!(fmt, "switchInt({:?}, {:?}) -> {:?}", lv, values, targets),
371 write!(fmt, "diverge"),
373 write!(fmt, "return"),
374 Call { data: ref c, targets } => {
375 try!(write!(fmt, "{:?} = {:?}(", c.destination, c.func));
376 for (index, arg) in c.args.iter().enumerate() {
378 try!(write!(fmt, ", "));
380 try!(write!(fmt, "{:?}", arg));
382 write!(fmt, ") -> {:?}", targets)
389 ///////////////////////////////////////////////////////////////////////////
392 pub struct Statement<'tcx> {
394 pub kind: StatementKind<'tcx>,
398 pub enum StatementKind<'tcx> {
399 Assign(Lvalue<'tcx>, Rvalue<'tcx>),
400 Drop(DropKind, Lvalue<'tcx>),
403 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
405 Free, // free a partially constructed box, should go away eventually
409 impl<'tcx> Debug for Statement<'tcx> {
410 fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
411 use self::StatementKind::*;
413 Assign(ref lv, ref rv) => write!(fmt, "{:?} = {:?}", lv, rv),
414 Drop(DropKind::Free, ref lv) => write!(fmt, "free {:?}", lv),
415 Drop(DropKind::Deep, ref lv) => write!(fmt, "drop {:?}", lv),
419 ///////////////////////////////////////////////////////////////////////////
422 /// A path to a value; something that can be evaluated without
423 /// changing or disturbing program state.
424 #[derive(Clone, PartialEq)]
425 pub enum Lvalue<'tcx> {
426 /// local variable declared by the user
429 /// temporary introduced during lowering into MIR
432 /// formal parameter of the function; note that these are NOT the
433 /// bindings that the user declares, which are vars
436 /// static or static mut variable
439 /// the return pointer of the fn
442 /// projection out of an lvalue (access a field, deref a pointer, etc)
443 Projection(Box<LvalueProjection<'tcx>>),
446 /// The `Projection` data structure defines things of the form `B.x`
447 /// or `*B` or `B[index]`. Note that it is parameterized because it is
448 /// shared between `Constant` and `Lvalue`. See the aliases
449 /// `LvalueProjection` etc below.
450 #[derive(Clone, Debug, PartialEq)]
451 pub struct Projection<'tcx, B, V> {
453 pub elem: ProjectionElem<'tcx, V>,
456 #[derive(Clone, Debug, PartialEq)]
457 pub enum ProjectionElem<'tcx, V> {
462 // These indices are generated by slice patterns. Easiest to explain
466 // [X, _, .._, _, _] => { offset: 0, min_length: 4, from_end: false },
467 // [_, X, .._, _, _] => { offset: 1, min_length: 4, from_end: false },
468 // [_, _, .._, X, _] => { offset: 2, min_length: 4, from_end: true },
469 // [_, _, .._, _, X] => { offset: 1, min_length: 4, from_end: true },
472 offset: u32, // index or -index (in Python terms), depending on from_end
473 min_length: u32, // thing being indexed must be at least this long
474 from_end: bool, // counting backwards from end?
477 // "Downcast" to a variant of an ADT. Currently, we only introduce
478 // this for ADTs with more than one variant. It may be better to
479 // just introduce it always, or always for enums.
480 Downcast(AdtDef<'tcx>, usize),
483 /// Alias for projections as they appear in lvalues, where the base is an lvalue
484 /// and the index is an operand.
485 pub type LvalueProjection<'tcx> =
486 Projection<'tcx,Lvalue<'tcx>,Operand<'tcx>>;
488 /// Alias for projections as they appear in lvalues, where the base is an lvalue
489 /// and the index is an operand.
490 pub type LvalueElem<'tcx> =
491 ProjectionElem<'tcx,Operand<'tcx>>;
493 /// Index into the list of fields found in a `VariantDef`
494 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
495 pub struct Field(u32);
498 pub fn new(value: usize) -> Field {
499 assert!(value < (u32::MAX) as usize);
503 pub fn index(self) -> usize {
508 impl<'tcx> Lvalue<'tcx> {
509 pub fn field(self, f: Field) -> Lvalue<'tcx> {
510 self.elem(ProjectionElem::Field(f))
513 pub fn deref(self) -> Lvalue<'tcx> {
514 self.elem(ProjectionElem::Deref)
517 pub fn index(self, index: Operand<'tcx>) -> Lvalue<'tcx> {
518 self.elem(ProjectionElem::Index(index))
521 pub fn elem(self, elem: LvalueElem<'tcx>) -> Lvalue<'tcx> {
522 Lvalue::Projection(Box::new(LvalueProjection {
529 impl<'tcx> Debug for Lvalue<'tcx> {
530 fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
535 write!(fmt,"Var({:?})", id),
537 write!(fmt,"Arg({:?})", id),
539 write!(fmt,"Temp({:?})", id),
541 write!(fmt,"Static({:?})", id),
543 write!(fmt,"ReturnPointer"),
544 Projection(ref data) =>
546 ProjectionElem::Downcast(_, variant_index) =>
547 write!(fmt,"({:?} as {:?})", data.base, variant_index),
548 ProjectionElem::Deref =>
549 write!(fmt,"(*{:?})", data.base),
550 ProjectionElem::Field(field) =>
551 write!(fmt,"{:?}.{:?}", data.base, field.index()),
552 ProjectionElem::Index(ref index) =>
553 write!(fmt,"{:?}[{:?}]", data.base, index),
554 ProjectionElem::ConstantIndex { offset, min_length, from_end: false } =>
555 write!(fmt,"{:?}[{:?} of {:?}]", data.base, offset, min_length),
556 ProjectionElem::ConstantIndex { offset, min_length, from_end: true } =>
557 write!(fmt,"{:?}[-{:?} of {:?}]", data.base, offset, min_length),
563 ///////////////////////////////////////////////////////////////////////////
566 // These are values that can appear inside an rvalue (or an index
567 // lvalue). They are intentionally limited to prevent rvalues from
568 // being nested in one another.
570 #[derive(Clone, PartialEq)]
571 pub enum Operand<'tcx> {
572 Consume(Lvalue<'tcx>),
573 Constant(Constant<'tcx>),
576 impl<'tcx> Debug for Operand<'tcx> {
577 fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
578 use self::Operand::*;
580 Constant(ref a) => write!(fmt, "{:?}", a),
581 Consume(ref lv) => write!(fmt, "{:?}", lv),
586 ///////////////////////////////////////////////////////////////////////////
590 pub enum Rvalue<'tcx> {
591 // x (either a move or copy, depending on type of x)
595 Repeat(Operand<'tcx>, Constant<'tcx>),
598 Ref(Region, BorrowKind, Lvalue<'tcx>),
600 // length of a [X] or [X;n] value
603 Cast(CastKind, Operand<'tcx>, Ty<'tcx>),
605 BinaryOp(BinOp, Operand<'tcx>, Operand<'tcx>),
607 UnaryOp(UnOp, Operand<'tcx>),
609 // Creates an *uninitialized* Box
612 // Create an aggregate value, like a tuple or struct. This is
613 // only needed because we want to distinguish `dest = Foo { x:
614 // ..., y: ... }` from `dest.x = ...; dest.y = ...;` in the case
615 // that `Foo` has a destructor. These rvalues can be optimized
616 // away after type-checking and before lowering.
617 Aggregate(AggregateKind<'tcx>, Vec<Operand<'tcx>>),
619 // Generates a slice of the form `&input[from_start..L-from_end]`
620 // where `L` is the length of the slice. This is only created by
621 // slice pattern matching, so e.g. a pattern of the form `[x, y,
622 // .., z]` might create a slice with `from_start=2` and
630 InlineAsm(&'tcx InlineAsm),
633 #[derive(Clone, Debug, PartialEq, Eq)]
637 /// Convert unique, zero-sized type for a fn to fn()
640 /// Convert safe fn() to unsafe fn()
643 /// "Unsize" -- convert a thin-or-fat pointer to a fat pointer.
644 /// trans must figure out the details once full monomorphization
645 /// is known. For example, this could be used to cast from a
646 /// `&[i32;N]` to a `&[i32]`, or a `Box<T>` to a `Box<Trait>`
647 /// (presuming `T: Trait`).
651 #[derive(Clone, Debug, PartialEq, Eq)]
652 pub enum AggregateKind<'tcx> {
655 Adt(AdtDef<'tcx>, usize, &'tcx Substs<'tcx>),
656 Closure(DefId, &'tcx ClosureSubsts<'tcx>),
659 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
661 /// The `+` operator (addition)
663 /// The `-` operator (subtraction)
665 /// The `*` operator (multiplication)
667 /// The `/` operator (division)
669 /// The `%` operator (modulus)
671 /// The `^` operator (bitwise xor)
673 /// The `&` operator (bitwise and)
675 /// The `|` operator (bitwise or)
677 /// The `<<` operator (shift left)
679 /// The `>>` operator (shift right)
681 /// The `==` operator (equality)
683 /// The `<` operator (less than)
685 /// The `<=` operator (less than or equal to)
687 /// The `!=` operator (not equal to)
689 /// The `>=` operator (greater than or equal to)
691 /// The `>` operator (greater than)
695 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
697 /// The `!` operator for logical inversion
699 /// The `-` operator for negation
703 impl<'tcx> Debug for Rvalue<'tcx> {
704 fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
708 Use(ref lvalue) => write!(fmt, "{:?}", lvalue),
709 Repeat(ref a, ref b) => write!(fmt, "[{:?}; {:?}]", a, b),
710 Ref(ref a, bk, ref b) => write!(fmt, "&{:?} {:?} {:?}", a, bk, b),
711 Len(ref a) => write!(fmt, "LEN({:?})", a),
712 Cast(ref kind, ref lv, ref ty) => write!(fmt, "{:?} as {:?} ({:?}", lv, ty, kind),
713 BinaryOp(ref op, ref a, ref b) => write!(fmt, "{:?}({:?},{:?})", op, a, b),
714 UnaryOp(ref op, ref a) => write!(fmt, "{:?}({:?})", op, a),
715 Box(ref t) => write!(fmt, "Box {:?}", t),
716 Aggregate(ref kind, ref lvs) => write!(fmt, "Aggregate<{:?}>({:?})", kind, lvs),
717 InlineAsm(ref asm) => write!(fmt, "InlineAsm({:?})", asm),
718 Slice { ref input, from_start, from_end } =>
719 write!(fmt, "{:?}[{:?}..-{:?}]", input, from_start, from_end),
724 ///////////////////////////////////////////////////////////////////////////
727 // Two constants are equal if they are the same constant. Note that
728 // this does not necessarily mean that they are "==" in Rust -- in
729 // particular one must be wary of `NaN`!
731 #[derive(Clone, Debug, PartialEq)]
732 pub struct Constant<'tcx> {
735 pub literal: Literal<'tcx>,
738 #[derive(Clone, Debug, PartialEq)]
739 pub enum Literal<'tcx> {
742 substs: &'tcx Substs<'tcx>,