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