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 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
  52 struct CFG<'tcx> {
  53     basic_blocks: Vec<BasicBlockData<'tcx>>,
  54 }
  55
  56 /// For each scope, we track the extent (from the HIR) and a
  57 /// single-entry-multiple-exit subgraph that contains all the
  58 /// statements/terminators within it.
  59 ///
  60 /// This information is separated out from the main `ScopeData`
  61 /// because it is short-lived. First, the extent contains node-ids,
  62 /// so it cannot be saved and re-loaded. Second, any optimization will mess up
  63 /// the dominator/postdominator information.
  64 ///
  65 /// The intention is basically to use this information to do
  66 /// regionck/borrowck and then throw it away once we are done.
  67 pub struct ScopeAuxiliary {
  68     /// extent of this scope from the MIR.
  69     pub extent: CodeExtent,
  70
  71     /// "entry point": dominator of all nodes in the scope
  72     pub dom: Location,
  73
  74     /// "exit points": mutual postdominators of all nodes in the scope
  75     pub postdoms: Vec<Location>,
  76 }
  77
  78 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
  79 pub struct Location {
  80     /// the location is within this block
  81     pub block: BasicBlock,
  82
  83     /// the location is the start of the this statement; or, if `statement_index`
  84     /// == num-statements, then the start of the terminator.
  85     pub statement_index: usize,
  86 }
  87
  88 pub struct ScopeAuxiliaryVec {
  89     pub vec: Vec<ScopeAuxiliary>
  90 }
  91
  92 impl Index<ScopeId> for ScopeAuxiliaryVec {
  93     type Output = ScopeAuxiliary;
  94
  95     #[inline]
  96     fn index(&self, index: ScopeId) -> &ScopeAuxiliary {
  97         &self.vec[index.index()]
  98     }
  99 }
 100
 101 impl IndexMut<ScopeId> for ScopeAuxiliaryVec {
 102     #[inline]
 103     fn index_mut(&mut self, index: ScopeId) -> &mut ScopeAuxiliary {
 104         &mut self.vec[index.index()]
 105     }
 106 }
 107
 108 ///////////////////////////////////////////////////////////////////////////
 109 /// The `BlockAnd` "monad" packages up the new basic block along with a
 110 /// produced value (sometimes just unit, of course). The `unpack!`
 111 /// macro (and methods below) makes working with `BlockAnd` much more
 112 /// convenient.
 113
 114 #[must_use] // if you don't use one of these results, you're leaving a dangling edge
 115 pub struct BlockAnd<T>(BasicBlock, T);
 116
 117 trait BlockAndExtension {
 118     fn and<T>(self, v: T) -> BlockAnd<T>;
 119     fn unit(self) -> BlockAnd<()>;
 120 }
 121
 122 impl BlockAndExtension for BasicBlock {
 123     fn and<T>(self, v: T) -> BlockAnd<T> {
 124         BlockAnd(self, v)
 125     }
 126
 127     fn unit(self) -> BlockAnd<()> {
 128         BlockAnd(self, ())
 129     }
 130 }
 131
 132 /// Update a block pointer and return the value.
 133 /// Use it like `let x = unpack!(block = self.foo(block, foo))`.
 134 macro_rules! unpack {
 135     ($x:ident = $c:expr) => {
 136         {
 137             let BlockAnd(b, v) = $c;
 138             $x = b;
 139             v
 140         }
 141     };
 142
 143     ($c:expr) => {
 144         {
 145             let BlockAnd(b, ()) = $c;
 146             b
 147         }
 148     };
 149 }
 150
 151 ///////////////////////////////////////////////////////////////////////////
 152 /// the main entry point for building MIR for a function
 153
 154 pub fn construct<'a,'tcx>(hir: Cx<'a,'tcx>,
 155                           span: Span,
 156                           implicit_arguments: Vec<Ty<'tcx>>,
 157                           explicit_arguments: Vec<(Ty<'tcx>, &'tcx hir::Pat)>,
 158                           argument_extent: CodeExtent,
 159                           return_ty: FnOutput<'tcx>,
 160                           ast_block: &'tcx hir::Block)
 161                           -> (Mir<'tcx>, ScopeAuxiliaryVec) {
 162     let cfg = CFG { basic_blocks: vec![] };
 163
 164     let mut builder = Builder {
 165         hir: hir,
 166         cfg: cfg,
 167         fn_span: span,
 168         scopes: vec![],
 169         scope_datas: vec![],
 170         scope_auxiliary: ScopeAuxiliaryVec { vec: vec![] },
 171         loop_scopes: vec![],
 172         temp_decls: vec![],
 173         var_decls: vec![],
 174         var_indices: FnvHashMap(),
 175         unit_temp: None,
 176     };
 177
 178     assert_eq!(builder.cfg.start_new_block(), START_BLOCK);
 179     assert_eq!(builder.cfg.start_new_block(), END_BLOCK);
 180
 181     let mut block = START_BLOCK;
 182     let (arg_decls, arg_scope_id) =
 183         unpack!(block = builder.args_and_body(block,
 184                                               implicit_arguments,
 185                                               explicit_arguments,
 186                                               argument_extent,
 187                                               ast_block));
 188
 189     builder.cfg.terminate(block, arg_scope_id, span,
 190                           TerminatorKind::Goto { target: END_BLOCK });
 191     builder.cfg.terminate(END_BLOCK, arg_scope_id, span,
 192                           TerminatorKind::Return);
 193
 194     assert!(
 195         builder.cfg.basic_blocks
 196                    .iter()
 197                    .enumerate()
 198                    .all(|(index, block)| {
 199                        if block.terminator.is_none() {
 200                            panic!("no terminator on block {:?} in {:?}",
 201                                index, argument_extent)
 202                        }
 203                        true
 204                    }));
 205
 206     (
 207         Mir {
 208             basic_blocks: builder.cfg.basic_blocks,
 209             scopes: builder.scope_datas,
 210             var_decls: builder.var_decls,
 211             arg_decls: arg_decls,
 212             temp_decls: builder.temp_decls,
 213             return_ty: return_ty,
 214             span: span
 215         },
 216         builder.scope_auxiliary,
 217     )
 218 }
 219
 220 impl<'a,'tcx> Builder<'a,'tcx> {
 221     fn args_and_body(&mut self,
 222                      mut block: BasicBlock,
 223                      implicit_arguments: Vec<Ty<'tcx>>,
 224                      explicit_arguments: Vec<(Ty<'tcx>, &'tcx hir::Pat)>,
 225                      argument_extent: CodeExtent,
 226                      ast_block: &'tcx hir::Block)
 227                      -> BlockAnd<(Vec<ArgDecl<'tcx>>, ScopeId)>
 228     {
 229         self.in_scope(argument_extent, block, |this, argument_scope_id| {
 230             // to start, translate the argument patterns and collect the argument types.
 231             let implicits = implicit_arguments.into_iter().map(|ty| (ty, None));
 232             let explicits = explicit_arguments.into_iter().map(|(ty, pat)| (ty, Some(pat)));
 233             let arg_decls =
 234                 implicits
 235                 .chain(explicits)
 236                 .enumerate()
 237                 .map(|(index, (ty, pattern))| {
 238                     let lvalue = Lvalue::Arg(index as u32);
 239                     if let Some(pattern) = pattern {
 240                         let pattern = this.hir.irrefutable_pat(pattern);
 241                         unpack!(block = this.lvalue_into_pattern(block,
 242                                                                  argument_scope_id,
 243                                                                  pattern,
 244                                                                  &lvalue));
 245                     }
 246                     // Make sure we drop (parts of) the argument even when not matched on.
 247                     this.schedule_drop(pattern.as_ref().map_or(ast_block.span, |pat| pat.span),
 248                                        argument_extent, &lvalue, ty);
 249                     ArgDecl { ty: ty, spread: false }
 250                 })
 251                 .collect();
 252
 253             // start the first basic block and translate the body
 254             unpack!(block = this.ast_block(&Lvalue::ReturnPointer, block, ast_block));
 255
 256             block.and((arg_decls, argument_scope_id))
 257         })
 258     }
 259
 260     fn get_unit_temp(&mut self) -> Lvalue<'tcx> {
 261         match self.unit_temp {
 262             Some(ref tmp) => tmp.clone(),
 263             None => {
 264                 let ty = self.hir.unit_ty();
 265                 let tmp = self.temp(ty);
 266                 self.unit_temp = Some(tmp.clone());
 267                 tmp
 268             }
 269         }
 270     }
 271 }
 272
 273 ///////////////////////////////////////////////////////////////////////////
 274 // Builder methods are broken up into modules, depending on what kind
 275 // of thing is being translated. Note that they use the `unpack` macro
 276 // above extensively.
 277
 278 mod block;
 279 mod cfg;
 280 mod expr;
 281 mod into;
 282 mod matches;
 283 mod misc;
 284 mod scope;