src/librustc_trans/mir/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 libc::c_uint;
  12 use llvm::{self, ValueRef};
  13 use rustc::ty;
  14 use rustc::mir::repr as mir;
  15 use rustc::mir::tcx::LvalueTy;
  16 use base;
  17 use common::{self, Block, BlockAndBuilder, FunctionContext};
  18
  19 use std::ops::Deref;
  20 use std::rc::Rc;
  21
  22 use basic_block::BasicBlock;
  23
  24 use rustc_data_structures::bitvec::BitVector;
  25
  26 use self::lvalue::{LvalueRef, get_dataptr, get_meta};
  27 use rustc_mir::traversal;
  28
  29 use self::operand::OperandRef;
  30
  31 #[derive(Clone)]
  32 pub enum CachedMir<'mir, 'tcx: 'mir> {
  33     Ref(&'mir mir::Mir<'tcx>),
  34     Owned(Rc<mir::Mir<'tcx>>)
  35 }
  36
  37 impl<'mir, 'tcx: 'mir> Deref for CachedMir<'mir, 'tcx> {
  38     type Target = mir::Mir<'tcx>;
  39     fn deref(&self) -> &mir::Mir<'tcx> {
  40         match *self {
  41             CachedMir::Ref(r) => r,
  42             CachedMir::Owned(ref rc) => rc
  43         }
  44     }
  45 }
  46
  47 // FIXME DebugLoc is always None right now
  48
  49 /// Master context for translating MIR.
  50 pub struct MirContext<'bcx, 'tcx:'bcx> {
  51     mir: CachedMir<'bcx, 'tcx>,
  52
  53     /// Function context
  54     fcx: &'bcx common::FunctionContext<'bcx, 'tcx>,
  55
  56     /// When unwinding is initiated, we have to store this personality
  57     /// value somewhere so that we can load it and re-use it in the
  58     /// resume instruction. The personality is (afaik) some kind of
  59     /// value used for C++ unwinding, which must filter by type: we
  60     /// don't really care about it very much. Anyway, this value
  61     /// contains an alloca into which the personality is stored and
  62     /// then later loaded when generating the DIVERGE_BLOCK.
  63     llpersonalityslot: Option<ValueRef>,
  64
  65     /// A `Block` for each MIR `BasicBlock`
  66     blocks: Vec<Block<'bcx, 'tcx>>,
  67
  68     /// Cached unreachable block
  69     unreachable_block: Option<Block<'bcx, 'tcx>>,
  70
  71     /// An LLVM alloca for each MIR `VarDecl`
  72     vars: Vec<LvalueRef<'tcx>>,
  73
  74     /// The location where each MIR `TempDecl` is stored. This is
  75     /// usually an `LvalueRef` representing an alloca, but not always:
  76     /// sometimes we can skip the alloca and just store the value
  77     /// directly using an `OperandRef`, which makes for tighter LLVM
  78     /// IR. The conditions for using an `OperandRef` are as follows:
  79     ///
  80     /// - the type of the temporary must be judged "immediate" by `type_is_immediate`
  81     /// - the operand must never be referenced indirectly
  82     ///     - we should not take its address using the `&` operator
  83     ///     - nor should it appear in an lvalue path like `tmp.a`
  84     /// - the operand must be defined by an rvalue that can generate immediate
  85     ///   values
  86     ///
  87     /// Avoiding allocs can also be important for certain intrinsics,
  88     /// notably `expect`.
  89     temps: Vec<TempRef<'tcx>>,
  90
  91     /// The arguments to the function; as args are lvalues, these are
  92     /// always indirect, though we try to avoid creating an alloca
  93     /// when we can (and just reuse the pointer the caller provided).
  94     args: Vec<LvalueRef<'tcx>>,
  95 }
  96
  97 enum TempRef<'tcx> {
  98     Lvalue(LvalueRef<'tcx>),
  99     Operand(Option<OperandRef<'tcx>>),
 100 }
 101
 102 ///////////////////////////////////////////////////////////////////////////
 103
 104 pub fn trans_mir<'blk, 'tcx: 'blk>(fcx: &'blk FunctionContext<'blk, 'tcx>) {
 105     let bcx = fcx.init(false, None).build();
 106     let mir = bcx.mir();
 107
 108     let mir_blocks = mir.all_basic_blocks();
 109
 110     // Analyze the temps to determine which must be lvalues
 111     // FIXME
 112     let lvalue_temps = bcx.with_block(|bcx| {
 113       analyze::lvalue_temps(bcx, &mir)
 114     });
 115
 116     // Allocate variable and temp allocas
 117     let vars = mir.var_decls.iter()
 118                             .map(|decl| (bcx.monomorphize(&decl.ty), decl.name))
 119                             .map(|(mty, name)| LvalueRef::alloca(&bcx, mty, &name.as_str()))
 120                             .collect();
 121     let temps = mir.temp_decls.iter()
 122                               .map(|decl| bcx.monomorphize(&decl.ty))
 123                               .enumerate()
 124                               .map(|(i, mty)| if lvalue_temps.contains(i) {
 125                                   TempRef::Lvalue(LvalueRef::alloca(&bcx,
 126                                                                     mty,
 127                                                                     &format!("temp{:?}", i)))
 128                               } else {
 129                                   // If this is an immediate temp, we do not create an
 130                                   // alloca in advance. Instead we wait until we see the
 131                                   // definition and update the operand there.
 132                                   TempRef::Operand(None)
 133                               })
 134                               .collect();
 135     let args = arg_value_refs(&bcx, &mir);
 136
 137     // Allocate a `Block` for every basic block
 138     let block_bcxs: Vec<Block<'blk,'tcx>> =
 139         mir_blocks.iter()
 140                   .map(|&bb|{
 141                       if bb == mir::START_BLOCK {
 142                           fcx.new_block("start", None)
 143                       } else if bb == mir::END_BLOCK {
 144                           fcx.new_block("end", None)
 145                       } else {
 146                           fcx.new_block(&format!("{:?}", bb), None)
 147                       }
 148                   })
 149                   .collect();
 150
 151     // Branch to the START block
 152     let start_bcx = block_bcxs[mir::START_BLOCK.index()];
 153     bcx.br(start_bcx.llbb);
 154
 155     let mut mircx = MirContext {
 156         mir: mir.clone(),
 157         fcx: fcx,
 158         llpersonalityslot: None,
 159         blocks: block_bcxs,
 160         unreachable_block: None,
 161         vars: vars,
 162         temps: temps,
 163         args: args,
 164     };
 165
 166     let mut visited = BitVector::new(mir_blocks.len());
 167
 168     let rpo = traversal::reverse_postorder(&mir);
 169     // Translate the body of each block using reverse postorder
 170     for (bb, _) in rpo {
 171         visited.insert(bb.index());
 172         mircx.trans_block(bb);
 173     }
 174
 175     // Remove blocks that haven't been visited, or have no
 176     // predecessors.
 177     for &bb in &mir_blocks {
 178         let block = mircx.blocks[bb.index()];
 179         let block = BasicBlock(block.llbb);
 180         // Unreachable block
 181         if !visited.contains(bb.index()) {
 182             block.delete();
 183         } else if block.pred_iter().count() == 0 {
 184             block.delete();
 185         }
 186     }
 187
 188     fcx.cleanup();
 189 }
 190
 191 /// Produce, for each argument, a `ValueRef` pointing at the
 192 /// argument's value. As arguments are lvalues, these are always
 193 /// indirect.
 194 fn arg_value_refs<'bcx, 'tcx>(bcx: &BlockAndBuilder<'bcx, 'tcx>,
 195                               mir: &mir::Mir<'tcx>)
 196                               -> Vec<LvalueRef<'tcx>> {
 197     let fcx = bcx.fcx();
 198     let tcx = bcx.tcx();
 199     let mut idx = 0;
 200     let mut llarg_idx = fcx.fn_ty.ret.is_indirect() as usize;
 201     mir.arg_decls.iter().enumerate().map(|(arg_index, arg_decl)| {
 202         let arg_ty = bcx.monomorphize(&arg_decl.ty);
 203         if arg_decl.spread {
 204             // This argument (e.g. the last argument in the "rust-call" ABI)
 205             // is a tuple that was spread at the ABI level and now we have
 206             // to reconstruct it into a tuple local variable, from multiple
 207             // individual LLVM function arguments.
 208
 209             let tupled_arg_tys = match arg_ty.sty {
 210                 ty::TyTuple(ref tys) => tys,
 211                 _ => bug!("spread argument isn't a tuple?!")
 212             };
 213
 214             let lltemp = bcx.with_block(|bcx| {
 215                 base::alloc_ty(bcx, arg_ty, &format!("arg{}", arg_index))
 216             });
 217             for (i, &tupled_arg_ty) in tupled_arg_tys.iter().enumerate() {
 218                 let dst = bcx.struct_gep(lltemp, i);
 219                 let arg = &fcx.fn_ty.args[idx];
 220                     idx += 1;
 221                 if common::type_is_fat_ptr(tcx, tupled_arg_ty) {
 222                         // We pass fat pointers as two words, but inside the tuple
 223                         // they are the two sub-fields of a single aggregate field.
 224                     let meta = &fcx.fn_ty.args[idx];
 225                     idx += 1;
 226                     arg.store_fn_arg(bcx, &mut llarg_idx, get_dataptr(bcx, dst));
 227                     meta.store_fn_arg(bcx, &mut llarg_idx, get_meta(bcx, dst));
 228                 } else {
 229                     arg.store_fn_arg(bcx, &mut llarg_idx, dst);
 230                 }
 231             }
 232             return LvalueRef::new_sized(lltemp, LvalueTy::from_ty(arg_ty));
 233         }
 234
 235         let arg = &fcx.fn_ty.args[idx];
 236         idx += 1;
 237         let llval = if arg.is_indirect() {
 238             // Don't copy an indirect argument to an alloca, the caller
 239             // already put it in a temporary alloca and gave it up, unless
 240             // we emit extra-debug-info, which requires local allocas :(.
 241             // FIXME: lifetimes, debug info
 242             let llarg = llvm::get_param(fcx.llfn, llarg_idx as c_uint);
 243             llarg_idx += 1;
 244             llarg
 245         } else {
 246             let lltemp = bcx.with_block(|bcx| {
 247                 base::alloc_ty(bcx, arg_ty, &format!("arg{}", arg_index))
 248             });
 249             if common::type_is_fat_ptr(tcx, arg_ty) {
 250                 // we pass fat pointers as two words, but we want to
 251                 // represent them internally as a pointer to two words,
 252                 // so make an alloca to store them in.
 253                 let meta = &fcx.fn_ty.args[idx];
 254                 idx += 1;
 255                 arg.store_fn_arg(bcx, &mut llarg_idx, get_dataptr(bcx, lltemp));
 256                 meta.store_fn_arg(bcx, &mut llarg_idx, get_meta(bcx, lltemp));
 257             } else  {
 258                 // otherwise, arg is passed by value, so make a
 259                 // temporary and store it there
 260                 arg.store_fn_arg(bcx, &mut llarg_idx, lltemp);
 261             }
 262             lltemp
 263         };
 264         LvalueRef::new_sized(llval, LvalueTy::from_ty(arg_ty))
 265     }).collect()
 266 }
 267
 268 mod analyze;
 269 mod block;
 270 mod constant;
 271 mod drop;
 272 mod lvalue;
 273 mod operand;
 274 mod rvalue;
 275 mod statement;