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, CodeExtentData};
  13 use rustc::ty::{FnOutput, Ty};
  14 use rustc::mir::repr::*;
  15 use rustc_data_structures::fnv::FnvHashMap;
  16 use rustc::hir;
  17 use std::ops::{Index, IndexMut};
  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     fn_span: Span,
  26
  27     // the current set of scopes, updated as we traverse;
  28     // see the `scope` module for more details
  29     scopes: Vec<scope::Scope<'tcx>>,
  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
  40     loop_scopes: Vec<scope::LoopScope>,
  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
  46     var_decls: Vec<VarDecl<'tcx>>,
  47     var_indices: FnvHashMap<ast::NodeId, u32>,
  48     temp_decls: Vec<TempDecl<'tcx>>,
  49     unit_temp: Option<Lvalue<'tcx>>,
  50
  51     // cached block with a RESUME terminator; we create this at the
  52     // first panic
  53     cached_resume_block: Option<BasicBlock>,
  54 }
  55
  56 struct CFG<'tcx> {
  57     basic_blocks: Vec<BasicBlockData<'tcx>>,
  58 }
  59
  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
 112 ///////////////////////////////////////////////////////////////////////////
 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.
 117
 118 #[must_use] // if you don't use one of these results, you're leaving a dangling edge
 119 pub struct BlockAnd<T>(BasicBlock, T);
 120
 121 trait BlockAndExtension {
 122     fn and<T>(self, v: T) -> BlockAnd<T>;
 123     fn unit(self) -> BlockAnd<()>;
 124 }
 125
 126 impl BlockAndExtension for BasicBlock {
 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 ///////////////////////////////////////////////////////////////////////////
 156 /// the main entry point for building MIR for a function
 157
 158 pub fn construct<'a,'tcx>(hir: Cx<'a,'tcx>,
 159                           span: Span,
 160                           fn_id: ast::NodeId,
 161                           body_id: ast::NodeId,
 162                           implicit_arguments: Vec<Ty<'tcx>>,
 163                           explicit_arguments: Vec<(Ty<'tcx>, &'tcx hir::Pat)>,
 164                           return_ty: FnOutput<'tcx>,
 165                           ast_block: &'tcx hir::Block)
 166                           -> (Mir<'tcx>, ScopeAuxiliaryVec) {
 167     let tcx = hir.tcx();
 168     let cfg = CFG { basic_blocks: vec![] };
 169
 170     let mut builder = Builder {
 171         hir: hir,
 172         cfg: cfg,
 173         fn_span: span,
 174         scopes: vec![],
 175         scope_datas: vec![],
 176         scope_auxiliary: ScopeAuxiliaryVec { vec: vec![] },
 177         loop_scopes: vec![],
 178         temp_decls: vec![],
 179         var_decls: vec![],
 180         var_indices: FnvHashMap(),
 181         unit_temp: None,
 182         cached_resume_block: None,
 183     };
 184
 185     assert_eq!(builder.cfg.start_new_block(), START_BLOCK);
 186     assert_eq!(builder.cfg.start_new_block(), END_BLOCK);
 187
 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     )
 239 }
 240
 241 impl<'a,'tcx> Builder<'a,'tcx> {
 242     fn args_and_body(&mut self,
 243                      mut block: BasicBlock,
 244                      implicit_arguments: Vec<Ty<'tcx>>,
 245                      explicit_arguments: Vec<(Ty<'tcx>, &'tcx hir::Pat)>,
 246                      argument_scope_id: ScopeId,
 247                      ast_block: &'tcx hir::Block)
 248                      -> BlockAnd<Vec<ArgDecl<'tcx>>>
 249     {
 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)));
 253             let arg_decls =
 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)
 280     }
 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     }
 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;