src/librustc_mir/build/mod.rs

   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
  11 use hair::cx::Cx;
  12 use rustc::middle::region::CodeExtent;
  13 use rustc::middle::ty::{FnOutput, Ty};
  14 use rustc::mir::repr::*;
  15 use rustc_data_structures::fnv::FnvHashMap;
  16 use rustc_front::hir;
  17
  18 use syntax::ast;
  19 use syntax::codemap::Span;
  20
  21 pub struct Builder<'a, 'tcx: 'a> {
  22     hir: Cx<'a, 'tcx>,
  23     cfg: CFG<'tcx>,
  24
  25     // the current set of scopes, updated as we traverse;
  26     // see the `scope` module for more details
  27     scopes: Vec<scope::Scope<'tcx>>,
  28
  29     // for each scope, a span of blocks that defines it;
  30     // we track these for use in region and borrow checking,
  31     // but these are liable to get out of date once optimization
  32     // begins. They are also hopefully temporary, and will be
  33     // no longer needed when we adopt graph-based regions.
  34     scope_auxiliary: Vec<ScopeAuxiliary>,
  35
  36     // the current set of loops; see the `scope` module for more
  37     // details
  38     loop_scopes: Vec<scope::LoopScope>,
  39
  40     // the vector of all scopes that we have created thus far;
  41     // we track this for debuginfo later
  42     scope_data_vec: ScopeDataVec,
  43
  44     var_decls: Vec<VarDecl<'tcx>>,
  45     var_indices: FnvHashMap<ast::NodeId, u32>,
  46     temp_decls: Vec<TempDecl<'tcx>>,
  47     unit_temp: Option<Lvalue<'tcx>>,
  48 }
  49
  50 struct CFG<'tcx> {
  51     basic_blocks: Vec<BasicBlockData<'tcx>>,
  52 }
  53
  54 /// For each scope, we track the extent (from the HIR) and a
  55 /// single-entry-multiple-exit subgraph that contains all the
  56 /// statements/terminators within it.
  57 ///
  58 /// This information is separated out from the main `ScopeData`
  59 /// because it is short-lived. First, the extent contains node-ids,
  60 /// so it cannot be saved and re-loaded. Second, any optimization will mess up
  61 /// the dominator/postdominator information.
  62 ///
  63 /// The intention is basically to use this information to do
  64 /// regionck/borrowck and then throw it away once we are done.
  65 pub struct ScopeAuxiliary {
  66     /// extent of this scope from the MIR.
  67     pub extent: CodeExtent,
  68
  69     /// "entry point": dominator of all nodes in the scope
  70     pub dom: Location,
  71
  72     /// "exit points": mutual postdominators of all nodes in the scope
  73     pub postdoms: Vec<Location>,
  74 }
  75
  76 pub struct Location {
  77     /// the location is within this block
  78     pub block: BasicBlock,
  79
  80     /// the location is the start of the this statement; or, if `statement_index`
  81     /// == num-statements, then the start of the terminator.
  82     pub statement_index: usize,
  83 }
  84
  85 pub struct MirPlusPlus<'tcx> {
  86     pub mir: Mir<'tcx>,
  87     pub scope_auxiliary: Vec<ScopeAuxiliary>,
  88 }
  89
  90 ///////////////////////////////////////////////////////////////////////////
  91 /// The `BlockAnd` "monad" packages up the new basic block along with a
  92 /// produced value (sometimes just unit, of course). The `unpack!`
  93 /// macro (and methods below) makes working with `BlockAnd` much more
  94 /// convenient.
  95
  96 #[must_use] // if you don't use one of these results, you're leaving a dangling edge
  97 pub struct BlockAnd<T>(BasicBlock, T);
  98
  99 trait BlockAndExtension {
 100     fn and<T>(self, v: T) -> BlockAnd<T>;
 101     fn unit(self) -> BlockAnd<()>;
 102 }
 103
 104 impl BlockAndExtension for BasicBlock {
 105     fn and<T>(self, v: T) -> BlockAnd<T> {
 106         BlockAnd(self, v)
 107     }
 108
 109     fn unit(self) -> BlockAnd<()> {
 110         BlockAnd(self, ())
 111     }
 112 }
 113
 114 /// Update a block pointer and return the value.
 115 /// Use it like `let x = unpack!(block = self.foo(block, foo))`.
 116 macro_rules! unpack {
 117     ($x:ident = $c:expr) => {
 118         {
 119             let BlockAnd(b, v) = $c;
 120             $x = b;
 121             v
 122         }
 123     };
 124
 125     ($c:expr) => {
 126         {
 127             let BlockAnd(b, ()) = $c;
 128             b
 129         }
 130     };
 131 }
 132
 133 ///////////////////////////////////////////////////////////////////////////
 134 /// the main entry point for building MIR for a function
 135
 136 pub fn construct<'a,'tcx>(hir: Cx<'a,'tcx>,
 137                           span: Span,
 138                           implicit_arguments: Vec<Ty<'tcx>>,
 139                           explicit_arguments: Vec<(Ty<'tcx>, &'tcx hir::Pat)>,
 140                           argument_extent: CodeExtent,
 141                           return_ty: FnOutput<'tcx>,
 142                           ast_block: &'tcx hir::Block)
 143                           -> MirPlusPlus<'tcx> {
 144     let cfg = CFG { basic_blocks: vec![] };
 145
 146     let mut builder = Builder {
 147         hir: hir,
 148         cfg: cfg,
 149         scopes: vec![],
 150         scope_data_vec: ScopeDataVec::new(),
 151         scope_auxiliary: vec![],
 152         loop_scopes: vec![],
 153         temp_decls: vec![],
 154         var_decls: vec![],
 155         var_indices: FnvHashMap(),
 156         unit_temp: None,
 157     };
 158
 159     assert_eq!(builder.cfg.start_new_block(), START_BLOCK);
 160     assert_eq!(builder.cfg.start_new_block(), END_BLOCK);
 161
 162     let mut block = START_BLOCK;
 163     let arg_decls = unpack!(block = builder.args_and_body(block,
 164                                                           implicit_arguments,
 165                                                           explicit_arguments,
 166                                                           argument_extent,
 167                                                           ast_block));
 168
 169     builder.cfg.terminate(block, TerminatorKind::Goto { target: END_BLOCK });
 170     builder.cfg.terminate(END_BLOCK, TerminatorKind::Return);
 171
 172     MirPlusPlus {
 173         mir: Mir {
 174             basic_blocks: builder.cfg.basic_blocks,
 175             scopes: builder.scope_data_vec,
 176             var_decls: builder.var_decls,
 177             arg_decls: arg_decls,
 178             temp_decls: builder.temp_decls,
 179             return_ty: return_ty,
 180             span: span
 181         },
 182         scope_auxiliary: builder.scope_auxiliary,
 183     }
 184 }
 185
 186 impl<'a,'tcx> Builder<'a,'tcx> {
 187     fn args_and_body(&mut self,
 188                      mut block: BasicBlock,
 189                      implicit_arguments: Vec<Ty<'tcx>>,
 190                      explicit_arguments: Vec<(Ty<'tcx>, &'tcx hir::Pat)>,
 191                      argument_extent: CodeExtent,
 192                      ast_block: &'tcx hir::Block)
 193                      -> BlockAnd<Vec<ArgDecl<'tcx>>>
 194     {
 195         self.in_scope(argument_extent, block, |this, argument_scope_id| {
 196             // to start, translate the argument patterns and collect the argument types.
 197             let implicits = implicit_arguments.into_iter().map(|ty| (ty, None));
 198             let explicits = explicit_arguments.into_iter().map(|(ty, pat)| (ty, Some(pat)));
 199             let arg_decls =
 200                 implicits
 201                 .chain(explicits)
 202                 .enumerate()
 203                 .map(|(index, (ty, pattern))| {
 204                     let lvalue = Lvalue::Arg(index as u32);
 205                     if let Some(pattern) = pattern {
 206                         let pattern = this.hir.irrefutable_pat(pattern);
 207                         unpack!(block = this.lvalue_into_pattern(block,
 208                                                                  argument_scope_id,
 209                                                                  pattern,
 210                                                                  &lvalue));
 211                     }
 212                     // Make sure we drop (parts of) the argument even when not matched on.
 213                     this.schedule_drop(pattern.as_ref().map_or(ast_block.span, |pat| pat.span),
 214                                        argument_extent, &lvalue, ty);
 215                     ArgDecl { ty: ty, spread: false }
 216                 })
 217                 .collect();
 218
 219             // start the first basic block and translate the body
 220             unpack!(block = this.ast_block(&Lvalue::ReturnPointer, block, ast_block));
 221
 222             block.and(arg_decls)
 223         })
 224     }
 225
 226     fn get_unit_temp(&mut self) -> Lvalue<'tcx> {
 227         match self.unit_temp {
 228             Some(ref tmp) => tmp.clone(),
 229             None => {
 230                 let ty = self.hir.unit_ty();
 231                 let tmp = self.temp(ty);
 232                 self.unit_temp = Some(tmp.clone());
 233                 tmp
 234             }
 235         }
 236     }
 237 }
 238
 239 ///////////////////////////////////////////////////////////////////////////
 240 // Builder methods are broken up into modules, depending on what kind
 241 // of thing is being translated. Note that they use the `unpack` macro
 242 // above extensively.
 243
 244 mod block;
 245 mod cfg;
 246 mod expr;
 247 mod into;
 248 mod matches;
 249 mod misc;
 250 mod scope;