src/librustc_trans/trans/tvec.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 #![allow(non_camel_case_types)]
  12
  13 use back::abi;
  14 use llvm;
  15 use llvm::{ValueRef};
  16 use trans::base::*;
  17 use trans::base;
  18 use trans::build::*;
  19 use trans::cleanup;
  20 use trans::cleanup::CleanupMethods;
  21 use trans::common::*;
  22 use trans::datum::*;
  23 use trans::expr::{Dest, Ignore, SaveIn};
  24 use trans::expr;
  25 use trans::glue;
  26 use trans::machine;
  27 use trans::machine::{nonzero_llsize_of, llsize_of_alloc};
  28 use trans::type_::Type;
  29 use trans::type_of;
  30 use middle::ty::{mod, Ty};
  31 use util::ppaux::ty_to_string;
  32
  33 use syntax::ast;
  34 use syntax::parse::token::InternedString;
  35
  36 fn get_len(bcx: Block, vptr: ValueRef) -> ValueRef {
  37     let _icx = push_ctxt("tvec::get_lenl");
  38     Load(bcx, expr::get_len(bcx, vptr))
  39 }
  40
  41 fn get_dataptr(bcx: Block, vptr: ValueRef) -> ValueRef {
  42     let _icx = push_ctxt("tvec::get_dataptr");
  43     Load(bcx, expr::get_dataptr(bcx, vptr))
  44 }
  45
  46 pub fn pointer_add_byte(bcx: Block, ptr: ValueRef, bytes: ValueRef) -> ValueRef {
  47     let _icx = push_ctxt("tvec::pointer_add_byte");
  48     let old_ty = val_ty(ptr);
  49     let bptr = PointerCast(bcx, ptr, Type::i8p(bcx.ccx()));
  50     return PointerCast(bcx, InBoundsGEP(bcx, bptr, &[bytes]), old_ty);
  51 }
  52
  53 pub fn make_drop_glue_unboxed<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
  54                                           vptr: ValueRef,
  55                                           unit_ty: Ty<'tcx>,
  56                                           should_deallocate: bool)
  57                                           -> Block<'blk, 'tcx> {
  58     let not_null = IsNotNull(bcx, vptr);
  59     with_cond(bcx, not_null, |bcx| {
  60         let ccx = bcx.ccx();
  61         let tcx = bcx.tcx();
  62         let _icx = push_ctxt("tvec::make_drop_glue_unboxed");
  63
  64         let dataptr = get_dataptr(bcx, vptr);
  65         let bcx = if type_needs_drop(tcx, unit_ty) {
  66             let len = get_len(bcx, vptr);
  67             iter_vec_raw(bcx, dataptr, unit_ty, len, |bb, vv, tt| glue::drop_ty(bb, vv, tt, None))
  68         } else {
  69             bcx
  70         };
  71
  72         if should_deallocate {
  73             let llty = type_of::type_of(ccx, unit_ty);
  74             let unit_size = llsize_of_alloc(ccx, llty);
  75             if unit_size != 0 {
  76                 let len = get_len(bcx, vptr);
  77                 let not_empty = ICmp(bcx, llvm::IntNE, len, C_uint(ccx, 0u));
  78                 with_cond(bcx, not_empty, |bcx| {
  79                     let llalign = C_uint(ccx, machine::llalign_of_min(ccx, llty));
  80                     let size = Mul(bcx, C_uint(ccx, unit_size), len);
  81                     glue::trans_exchange_free_dyn(bcx, dataptr, size, llalign)
  82                 })
  83             } else {
  84                 bcx
  85             }
  86         } else {
  87             bcx
  88         }
  89     })
  90 }
  91
  92 #[deriving(Copy)]
  93 pub struct VecTypes<'tcx> {
  94     pub unit_ty: Ty<'tcx>,
  95     pub llunit_ty: Type,
  96     pub llunit_size: ValueRef,
  97     pub llunit_alloc_size: u64
  98 }
  99
 100 impl<'tcx> VecTypes<'tcx> {
 101     pub fn to_string<'a>(&self, ccx: &CrateContext<'a, 'tcx>) -> String {
 102         format!("VecTypes {{unit_ty={}, llunit_ty={}, \
 103                  llunit_size={}, llunit_alloc_size={}}}",
 104                 ty_to_string(ccx.tcx(), self.unit_ty),
 105                 ccx.tn().type_to_string(self.llunit_ty),
 106                 ccx.tn().val_to_string(self.llunit_size),
 107                 self.llunit_alloc_size)
 108     }
 109 }
 110
 111 pub fn trans_fixed_vstore<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 112                                       expr: &ast::Expr,
 113                                       dest: expr::Dest)
 114                                       -> Block<'blk, 'tcx> {
 115     //!
 116     //
 117     // [...] allocates a fixed-size array and moves it around "by value".
 118     // In this case, it means that the caller has already given us a location
 119     // to store the array of the suitable size, so all we have to do is
 120     // generate the content.
 121
 122     debug!("trans_fixed_vstore(expr={}, dest={})",
 123            bcx.expr_to_string(expr), dest.to_string(bcx.ccx()));
 124
 125     let vt = vec_types_from_expr(bcx, expr);
 126
 127     return match dest {
 128         Ignore => write_content(bcx, &vt, expr, expr, dest),
 129         SaveIn(lldest) => {
 130             // lldest will have type *[T x N], but we want the type *T,
 131             // so use GEP to convert:
 132             let lldest = GEPi(bcx, lldest, &[0, 0]);
 133             write_content(bcx, &vt, expr, expr, SaveIn(lldest))
 134         }
 135     };
 136 }
 137
 138 /// &[...] allocates memory on the stack and writes the values into it, returning the vector (the
 139 /// caller must make the reference).  "..." is similar except that the memory can be statically
 140 /// allocated and we return a reference (strings are always by-ref).
 141 pub fn trans_slice_vec<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 142                                    slice_expr: &ast::Expr,
 143                                    content_expr: &ast::Expr)
 144                                    -> DatumBlock<'blk, 'tcx, Expr> {
 145     let fcx = bcx.fcx;
 146     let ccx = fcx.ccx;
 147     let mut bcx = bcx;
 148
 149     debug!("trans_slice_vec(slice_expr={})",
 150            bcx.expr_to_string(slice_expr));
 151
 152     let vec_ty = node_id_type(bcx, slice_expr.id);
 153
 154     // Handle the "..." case (returns a slice since strings are always unsized):
 155     if let ast::ExprLit(ref lit) = content_expr.node {
 156         if let ast::LitStr(ref s, _) = lit.node {
 157             let scratch = rvalue_scratch_datum(bcx, vec_ty, "");
 158             bcx = trans_lit_str(bcx,
 159                                 content_expr,
 160                                 s.clone(),
 161                                 SaveIn(scratch.val));
 162             return DatumBlock::new(bcx, scratch.to_expr_datum());
 163         }
 164     }
 165
 166     // Handle the &[...] case:
 167     let vt = vec_types_from_expr(bcx, content_expr);
 168     let count = elements_required(bcx, content_expr);
 169     debug!("    vt={}, count={}", vt.to_string(ccx), count);
 170     let llcount = C_uint(ccx, count);
 171
 172     let fixed_ty = ty::mk_vec(bcx.tcx(),
 173                               vt.unit_ty,
 174                               Some(count));
 175     let llfixed_ty = type_of::type_of(bcx.ccx(), fixed_ty).ptr_to();
 176
 177     let llfixed = if count == 0 {
 178         // Just create a zero-sized alloca to preserve
 179         // the non-null invariant of the inner slice ptr
 180         let llfixed = base::arrayalloca(bcx, vt.llunit_ty, llcount);
 181         BitCast(bcx, llfixed, llfixed_ty)
 182     } else {
 183         // Make a fixed-length backing array and allocate it on the stack.
 184         let llfixed = base::arrayalloca(bcx, vt.llunit_ty, llcount);
 185
 186         // Arrange for the backing array to be cleaned up.
 187         let llfixed_casted = BitCast(bcx, llfixed, llfixed_ty);
 188         let cleanup_scope = cleanup::temporary_scope(bcx.tcx(), content_expr.id);
 189         fcx.schedule_lifetime_end(cleanup_scope, llfixed_casted);
 190         fcx.schedule_drop_mem(cleanup_scope, llfixed_casted, fixed_ty);
 191
 192         // Generate the content into the backing array.
 193         bcx = write_content(bcx, &vt, slice_expr,
 194                             content_expr, SaveIn(llfixed));
 195
 196         llfixed_casted
 197     };
 198
 199     immediate_rvalue_bcx(bcx, llfixed, vec_ty).to_expr_datumblock()
 200 }
 201
 202 /// Literal strings translate to slices into static memory.  This is different from
 203 /// trans_slice_vstore() above because it doesn't need to copy the content anywhere.
 204 pub fn trans_lit_str<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 205                                  lit_expr: &ast::Expr,
 206                                  str_lit: InternedString,
 207                                  dest: Dest)
 208                                  -> Block<'blk, 'tcx> {
 209     debug!("trans_lit_str(lit_expr={}, dest={})",
 210            bcx.expr_to_string(lit_expr),
 211            dest.to_string(bcx.ccx()));
 212
 213     match dest {
 214         Ignore => bcx,
 215         SaveIn(lldest) => {
 216             unsafe {
 217                 let bytes = str_lit.get().len();
 218                 let llbytes = C_uint(bcx.ccx(), bytes);
 219                 let llcstr = C_cstr(bcx.ccx(), str_lit, false);
 220                 let llcstr = llvm::LLVMConstPointerCast(llcstr, Type::i8p(bcx.ccx()).to_ref());
 221                 Store(bcx, llcstr, GEPi(bcx, lldest, &[0u, abi::FAT_PTR_ADDR]));
 222                 Store(bcx, llbytes, GEPi(bcx, lldest, &[0u, abi::FAT_PTR_EXTRA]));
 223                 bcx
 224             }
 225         }
 226     }
 227 }
 228
 229 pub fn write_content<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 230                                  vt: &VecTypes<'tcx>,
 231                                  vstore_expr: &ast::Expr,
 232                                  content_expr: &ast::Expr,
 233                                  dest: Dest)
 234                                  -> Block<'blk, 'tcx> {
 235     let _icx = push_ctxt("tvec::write_content");
 236     let fcx = bcx.fcx;
 237     let mut bcx = bcx;
 238
 239     debug!("write_content(vt={}, dest={}, vstore_expr={})",
 240            vt.to_string(bcx.ccx()),
 241            dest.to_string(bcx.ccx()),
 242            bcx.expr_to_string(vstore_expr));
 243
 244     match content_expr.node {
 245         ast::ExprLit(ref lit) => {
 246             match lit.node {
 247                 ast::LitStr(ref s, _) => {
 248                     match dest {
 249                         Ignore => return bcx,
 250                         SaveIn(lldest) => {
 251                             let bytes = s.get().len();
 252                             let llbytes = C_uint(bcx.ccx(), bytes);
 253                             let llcstr = C_cstr(bcx.ccx(), (*s).clone(), false);
 254                             base::call_memcpy(bcx,
 255                                               lldest,
 256                                               llcstr,
 257                                               llbytes,
 258                                               1);
 259                             return bcx;
 260                         }
 261                     }
 262                 }
 263                 _ => {
 264                     bcx.tcx().sess.span_bug(content_expr.span,
 265                                             "unexpected evec content");
 266                 }
 267             }
 268         }
 269         ast::ExprVec(ref elements) => {
 270             match dest {
 271                 Ignore => {
 272                     for element in elements.iter() {
 273                         bcx = expr::trans_into(bcx, &**element, Ignore);
 274                     }
 275                 }
 276
 277                 SaveIn(lldest) => {
 278                     let temp_scope = fcx.push_custom_cleanup_scope();
 279                     for (i, element) in elements.iter().enumerate() {
 280                         let lleltptr = GEPi(bcx, lldest, &[i]);
 281                         debug!("writing index {} with lleltptr={}",
 282                                i, bcx.val_to_string(lleltptr));
 283                         bcx = expr::trans_into(bcx, &**element,
 284                                                SaveIn(lleltptr));
 285                         let scope = cleanup::CustomScope(temp_scope);
 286                         fcx.schedule_lifetime_end(scope, lleltptr);
 287                         fcx.schedule_drop_mem(scope, lleltptr, vt.unit_ty);
 288                     }
 289                     fcx.pop_custom_cleanup_scope(temp_scope);
 290                 }
 291             }
 292             return bcx;
 293         }
 294         ast::ExprRepeat(ref element, ref count_expr) => {
 295             match dest {
 296                 Ignore => {
 297                     return expr::trans_into(bcx, &**element, Ignore);
 298                 }
 299                 SaveIn(lldest) => {
 300                     match ty::eval_repeat_count(bcx.tcx(), &**count_expr) {
 301                         0 => bcx,
 302                         1 => expr::trans_into(bcx, &**element, SaveIn(lldest)),
 303                         count => {
 304                             let elem = unpack_datum!(bcx, expr::trans(bcx, &**element));
 305                             let bcx = iter_vec_loop(bcx, lldest, vt,
 306                                                     C_uint(bcx.ccx(), count),
 307                                                     |set_bcx, lleltptr, _| {
 308                                                         elem.shallow_copy(set_bcx, lleltptr)
 309                                                     });
 310
 311                             elem.add_clean_if_rvalue(bcx, element.id);
 312                             bcx
 313                         }
 314                     }
 315                 }
 316             }
 317         }
 318         _ => {
 319             bcx.tcx().sess.span_bug(content_expr.span,
 320                                     "unexpected vec content");
 321         }
 322     }
 323 }
 324
 325 pub fn vec_types_from_expr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 326                                        vec_expr: &ast::Expr)
 327                                        -> VecTypes<'tcx> {
 328     let vec_ty = node_id_type(bcx, vec_expr.id);
 329     vec_types(bcx, ty::sequence_element_type(bcx.tcx(), vec_ty))
 330 }
 331
 332 pub fn vec_types<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 333                              unit_ty: Ty<'tcx>)
 334                              -> VecTypes<'tcx> {
 335     let ccx = bcx.ccx();
 336     let llunit_ty = type_of::type_of(ccx, unit_ty);
 337     let llunit_size = nonzero_llsize_of(ccx, llunit_ty);
 338     let llunit_alloc_size = llsize_of_alloc(ccx, llunit_ty);
 339
 340     VecTypes {
 341         unit_ty: unit_ty,
 342         llunit_ty: llunit_ty,
 343         llunit_size: llunit_size,
 344         llunit_alloc_size: llunit_alloc_size
 345     }
 346 }
 347
 348 pub fn elements_required(bcx: Block, content_expr: &ast::Expr) -> uint {
 349     //! Figure out the number of elements we need to store this content
 350
 351     match content_expr.node {
 352         ast::ExprLit(ref lit) => {
 353             match lit.node {
 354                 ast::LitStr(ref s, _) => s.get().len(),
 355                 _ => {
 356                     bcx.tcx().sess.span_bug(content_expr.span,
 357                                             "unexpected evec content")
 358                 }
 359             }
 360         },
 361         ast::ExprVec(ref es) => es.len(),
 362         ast::ExprRepeat(_, ref count_expr) => {
 363             ty::eval_repeat_count(bcx.tcx(), &**count_expr)
 364         }
 365         _ => bcx.tcx().sess.span_bug(content_expr.span,
 366                                      "unexpected vec content")
 367     }
 368 }
 369
 370 /// Converts a fixed-length vector into the slice pair. The vector should be stored in `llval`
 371 /// which should be by ref.
 372 pub fn get_fixed_base_and_len(bcx: Block,
 373                               llval: ValueRef,
 374                               vec_length: uint)
 375                               -> (ValueRef, ValueRef) {
 376     let ccx = bcx.ccx();
 377
 378     let base = expr::get_dataptr(bcx, llval);
 379     let len = C_uint(ccx, vec_length);
 380     (base, len)
 381 }
 382
 383 fn get_slice_base_and_len(bcx: Block,
 384                           llval: ValueRef)
 385                           -> (ValueRef, ValueRef) {
 386     let base = Load(bcx, GEPi(bcx, llval, &[0u, abi::FAT_PTR_ADDR]));
 387     let len = Load(bcx, GEPi(bcx, llval, &[0u, abi::FAT_PTR_EXTRA]));
 388     (base, len)
 389 }
 390
 391 /// Converts a vector into the slice pair.  The vector should be stored in `llval` which should be
 392 /// by-reference.  If you have a datum, you would probably prefer to call
 393 /// `Datum::get_base_and_len()` which will handle any conversions for you.
 394 pub fn get_base_and_len(bcx: Block,
 395                         llval: ValueRef,
 396                         vec_ty: Ty)
 397                         -> (ValueRef, ValueRef) {
 398     let ccx = bcx.ccx();
 399
 400     match vec_ty.sty {
 401         ty::ty_vec(_, Some(n)) => get_fixed_base_and_len(bcx, llval, n),
 402         ty::ty_open(ty) => match ty.sty {
 403             ty::ty_vec(_, None) | ty::ty_str => get_slice_base_and_len(bcx, llval),
 404             _ => ccx.sess().bug("unexpected type in get_base_and_len")
 405         },
 406
 407         // Only used for pattern matching.
 408         ty::ty_uniq(ty) | ty::ty_rptr(_, ty::mt{ty, ..}) => match ty.sty {
 409             ty::ty_vec(_, None) | ty::ty_str => get_slice_base_and_len(bcx, llval),
 410             ty::ty_vec(_, Some(n)) => {
 411                 let base = GEPi(bcx, Load(bcx, llval), &[0u, 0u]);
 412                 (base, C_uint(ccx, n))
 413             }
 414             _ => ccx.sess().bug("unexpected type in get_base_and_len"),
 415         },
 416         _ => ccx.sess().bug("unexpected type in get_base_and_len"),
 417     }
 418 }
 419
 420 pub type iter_vec_block<'a, 'blk, 'tcx> =
 421     |Block<'blk, 'tcx>, ValueRef, Ty<'tcx>|: 'a -> Block<'blk, 'tcx>;
 422
 423 pub fn iter_vec_loop<'a, 'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 424                                      data_ptr: ValueRef,
 425                                      vt: &VecTypes<'tcx>,
 426                                      count: ValueRef,
 427                                      f: iter_vec_block<'a, 'blk, 'tcx>)
 428                                      -> Block<'blk, 'tcx> {
 429     let _icx = push_ctxt("tvec::iter_vec_loop");
 430     let fcx = bcx.fcx;
 431
 432     let next_bcx = fcx.new_temp_block("expr_repeat: while next");
 433     let loop_bcx = fcx.new_temp_block("expr_repeat");
 434     let cond_bcx = fcx.new_temp_block("expr_repeat: loop cond");
 435     let body_bcx = fcx.new_temp_block("expr_repeat: body: set");
 436     let inc_bcx = fcx.new_temp_block("expr_repeat: body: inc");
 437     Br(bcx, loop_bcx.llbb);
 438
 439     let loop_counter = {
 440         // i = 0
 441         let i = alloca(loop_bcx, bcx.ccx().int_type(), "__i");
 442         Store(loop_bcx, C_uint(bcx.ccx(), 0u), i);
 443
 444         Br(loop_bcx, cond_bcx.llbb);
 445         i
 446     };
 447
 448     { // i < count
 449         let lhs = Load(cond_bcx, loop_counter);
 450         let rhs = count;
 451         let cond_val = ICmp(cond_bcx, llvm::IntULT, lhs, rhs);
 452
 453         CondBr(cond_bcx, cond_val, body_bcx.llbb, next_bcx.llbb);
 454     }
 455
 456     { // loop body
 457         let i = Load(body_bcx, loop_counter);
 458         let lleltptr = if vt.llunit_alloc_size == 0 {
 459             data_ptr
 460         } else {
 461             InBoundsGEP(body_bcx, data_ptr, &[i])
 462         };
 463         let body_bcx = f(body_bcx, lleltptr, vt.unit_ty);
 464
 465         Br(body_bcx, inc_bcx.llbb);
 466     }
 467
 468     { // i += 1
 469         let i = Load(inc_bcx, loop_counter);
 470         let plusone = Add(inc_bcx, i, C_uint(bcx.ccx(), 1u));
 471         Store(inc_bcx, plusone, loop_counter);
 472
 473         Br(inc_bcx, cond_bcx.llbb);
 474     }
 475
 476     next_bcx
 477 }
 478
 479 pub fn iter_vec_raw<'a, 'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 480                                     data_ptr: ValueRef,
 481                                     unit_ty: Ty<'tcx>,
 482                                     len: ValueRef,
 483                                     f: iter_vec_block<'a, 'blk, 'tcx>)
 484                                     -> Block<'blk, 'tcx> {
 485     let _icx = push_ctxt("tvec::iter_vec_raw");
 486     let fcx = bcx.fcx;
 487
 488     let vt = vec_types(bcx, unit_ty);
 489     let fill = Mul(bcx, len, vt.llunit_size);
 490
 491     if vt.llunit_alloc_size == 0 {
 492         // Special-case vectors with elements of size 0  so they don't go out of bounds (#9890)
 493         iter_vec_loop(bcx, data_ptr, &vt, fill, f)
 494     } else {
 495         // Calculate the last pointer address we want to handle.
 496         // FIXME (#3729): Optimize this when the size of the unit type is
 497         // statically known to not use pointer casts, which tend to confuse
 498         // LLVM.
 499         let data_end_ptr = pointer_add_byte(bcx, data_ptr, fill);
 500
 501         // Now perform the iteration.
 502         let header_bcx = fcx.new_temp_block("iter_vec_loop_header");
 503         Br(bcx, header_bcx.llbb);
 504         let data_ptr =
 505             Phi(header_bcx, val_ty(data_ptr), &[data_ptr], &[bcx.llbb]);
 506         let not_yet_at_end =
 507             ICmp(header_bcx, llvm::IntULT, data_ptr, data_end_ptr);
 508         let body_bcx = fcx.new_temp_block("iter_vec_loop_body");
 509         let next_bcx = fcx.new_temp_block("iter_vec_next");
 510         CondBr(header_bcx, not_yet_at_end, body_bcx.llbb, next_bcx.llbb);
 511         let body_bcx = f(body_bcx, data_ptr, vt.unit_ty);
 512         AddIncomingToPhi(data_ptr, InBoundsGEP(body_bcx, data_ptr,
 513                                                &[C_int(bcx.ccx(), 1i)]),
 514                          body_bcx.llbb);
 515         Br(body_bcx, header_bcx.llbb);
 516         next_bcx
 517     }
 518 }