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