src/librustc_trans/adt.rs

   1 // Copyright 2013 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 //! # Representation of Algebraic Data Types
  12 //!
  13 //! This module determines how to represent enums, structs, and tuples
  14 //! based on their monomorphized types; it is responsible both for
  15 //! choosing a representation and translating basic operations on
  16 //! values of those types.  (Note: exporting the representations for
  17 //! debuggers is handled in debuginfo.rs, not here.)
  18 //!
  19 //! Note that the interface treats everything as a general case of an
  20 //! enum, so structs/tuples/etc. have one pseudo-variant with
  21 //! discriminant 0; i.e., as if they were a univariant enum.
  22 //!
  23 //! Having everything in one place will enable improvements to data
  24 //! structure representation; possibilities include:
  25 //!
  26 //! - User-specified alignment (e.g., cacheline-aligning parts of
  27 //!   concurrently accessed data structures); LLVM can't represent this
  28 //!   directly, so we'd have to insert padding fields in any structure
  29 //!   that might contain one and adjust GEP indices accordingly.  See
  30 //!   issue #4578.
  31 //!
  32 //! - Store nested enums' discriminants in the same word.  Rather, if
  33 //!   some variants start with enums, and those enums representations
  34 //!   have unused alignment padding between discriminant and body, the
  35 //!   outer enum's discriminant can be stored there and those variants
  36 //!   can start at offset 0.  Kind of fancy, and might need work to
  37 //!   make copies of the inner enum type cooperate, but it could help
  38 //!   with `Option` or `Result` wrapped around another enum.
  39 //!
  40 //! - Tagged pointers would be neat, but given that any type can be
  41 //!   used unboxed and any field can have pointers (including mutable)
  42 //!   taken to it, implementing them for Rust seems difficult.
  43
  44 use super::Disr;
  45
  46 use std;
  47
  48 use llvm::{ValueRef, True, IntEQ, IntNE};
  49 use rustc::ty::layout;
  50 use rustc::ty::{self, Ty, AdtKind};
  51 use common::*;
  52 use builder::Builder;
  53 use base;
  54 use machine;
  55 use monomorphize;
  56 use type_::Type;
  57 use type_of;
  58
  59 use mir::lvalue::Alignment;
  60
  61 /// Given an enum, struct, closure, or tuple, extracts fields.
  62 /// Treats closures as a struct with one variant.
  63 /// `empty_if_no_variants` is a switch to deal with empty enums.
  64 /// If true, `variant_index` is disregarded and an empty Vec returned in this case.
  65 pub fn compute_fields<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>,
  66                                 variant_index: usize,
  67                                 empty_if_no_variants: bool) -> Vec<Ty<'tcx>> {
  68     match t.sty {
  69         ty::TyAdt(ref def, _) if def.variants.len() == 0 && empty_if_no_variants => {
  70             Vec::default()
  71         },
  72         ty::TyAdt(ref def, ref substs) => {
  73             def.variants[variant_index].fields.iter().map(|f| {
  74                 monomorphize::field_ty(cx.tcx(), substs, f)
  75             }).collect::<Vec<_>>()
  76         },
  77         ty::TyTuple(fields, _) => fields.to_vec(),
  78         ty::TyClosure(def_id, substs) => {
  79             if variant_index > 0 { bug!("{} is a closure, which only has one variant", t);}
  80             substs.upvar_tys(def_id, cx.tcx()).collect()
  81         },
  82         _ => bug!("{} is not a type that can have fields.", t)
  83     }
  84 }
  85
  86 /// LLVM-level types are a little complicated.
  87 ///
  88 /// C-like enums need to be actual ints, not wrapped in a struct,
  89 /// because that changes the ABI on some platforms (see issue #10308).
  90 ///
  91 /// For nominal types, in some cases, we need to use LLVM named structs
  92 /// and fill in the actual contents in a second pass to prevent
  93 /// unbounded recursion; see also the comments in `trans::type_of`.
  94 pub fn type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) -> Type {
  95     generic_type_of(cx, t, None, false, false)
  96 }
  97
  98
  99 // Pass dst=true if the type you are passing is a DST. Yes, we could figure
 100 // this out, but if you call this on an unsized type without realising it, you
 101 // are going to get the wrong type (it will not include the unsized parts of it).
 102 pub fn sizing_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 103                                 t: Ty<'tcx>, dst: bool) -> Type {
 104     generic_type_of(cx, t, None, true, dst)
 105 }
 106
 107 pub fn incomplete_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 108                                     t: Ty<'tcx>, name: &str) -> Type {
 109     generic_type_of(cx, t, Some(name), false, false)
 110 }
 111
 112 pub fn finish_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 113                                 t: Ty<'tcx>, llty: &mut Type) {
 114     let l = cx.layout_of(t);
 115     debug!("finish_type_of: {} with layout {:#?}", t, l);
 116     match *l {
 117         layout::CEnum { .. } | layout::General { .. }
 118         | layout::UntaggedUnion { .. } | layout::RawNullablePointer { .. } => { }
 119         layout::Univariant { ..}
 120         | layout::StructWrappedNullablePointer { .. } => {
 121             let (nonnull_variant_index, nonnull_variant, packed) = match *l {
 122                 layout::Univariant { ref variant, .. } => (0, variant, variant.packed),
 123                 layout::StructWrappedNullablePointer { nndiscr, ref nonnull, .. } =>
 124                     (nndiscr, nonnull, nonnull.packed),
 125                 _ => unreachable!()
 126             };
 127             let fields = compute_fields(cx, t, nonnull_variant_index as usize, true);
 128             llty.set_struct_body(&struct_llfields(cx, &fields, nonnull_variant, false, false),
 129                                  packed)
 130         },
 131         _ => bug!("This function cannot handle {} with layout {:#?}", t, l)
 132     }
 133 }
 134
 135 fn generic_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 136                              t: Ty<'tcx>,
 137                              name: Option<&str>,
 138                              sizing: bool,
 139                              dst: bool) -> Type {
 140     let l = cx.layout_of(t);
 141     debug!("adt::generic_type_of t: {:?} name: {:?} sizing: {} dst: {}",
 142            t, name, sizing, dst);
 143     match *l {
 144         layout::CEnum { discr, .. } => Type::from_integer(cx, discr),
 145         layout::RawNullablePointer { nndiscr, .. } => {
 146             let (def, substs) = match t.sty {
 147                 ty::TyAdt(d, s) => (d, s),
 148                 _ => bug!("{} is not an ADT", t)
 149             };
 150             let nnty = monomorphize::field_ty(cx.tcx(), substs,
 151                 &def.variants[nndiscr as usize].fields[0]);
 152             type_of::sizing_type_of(cx, nnty)
 153         }
 154         layout::StructWrappedNullablePointer { nndiscr, ref nonnull, .. } => {
 155             let fields = compute_fields(cx, t, nndiscr as usize, false);
 156             match name {
 157                 None => {
 158                     Type::struct_(cx, &struct_llfields(cx, &fields, nonnull, sizing, dst),
 159                                   nonnull.packed)
 160                 }
 161                 Some(name) => {
 162                     assert_eq!(sizing, false);
 163                     Type::named_struct(cx, name)
 164                 }
 165             }
 166         }
 167         layout::Univariant { ref variant, .. } => {
 168             // Note that this case also handles empty enums.
 169             // Thus the true as the final parameter here.
 170             let fields = compute_fields(cx, t, 0, true);
 171             match name {
 172                 None => {
 173                     let fields = struct_llfields(cx, &fields, &variant, sizing, dst);
 174                     Type::struct_(cx, &fields, variant.packed)
 175                 }
 176                 Some(name) => {
 177                     // Hypothesis: named_struct's can never need a
 178                     // drop flag. (... needs validation.)
 179                     assert_eq!(sizing, false);
 180                     Type::named_struct(cx, name)
 181                 }
 182             }
 183         }
 184         layout::Vector { element, count } => {
 185             let elem_ty = Type::from_primitive(cx, element);
 186             Type::vector(&elem_ty, count)
 187         }
 188         layout::UntaggedUnion { ref variants, .. }=> {
 189             // Use alignment-sized ints to fill all the union storage.
 190             let size = variants.stride().bytes();
 191             let align = variants.align.abi();
 192             let fill = union_fill(cx, size, align);
 193             match name {
 194                 None => {
 195                     Type::struct_(cx, &[fill], variants.packed)
 196                 }
 197                 Some(name) => {
 198                     let mut llty = Type::named_struct(cx, name);
 199                     llty.set_struct_body(&[fill], variants.packed);
 200                     llty
 201                 }
 202             }
 203         }
 204         layout::General { discr, size, align, .. } => {
 205             // We need a representation that has:
 206             // * The alignment of the most-aligned field
 207             // * The size of the largest variant (rounded up to that alignment)
 208             // * No alignment padding anywhere any variant has actual data
 209             //   (currently matters only for enums small enough to be immediate)
 210             // * The discriminant in an obvious place.
 211             //
 212             // So we start with the discriminant, pad it up to the alignment with
 213             // more of its own type, then use alignment-sized ints to get the rest
 214             // of the size.
 215             let size = size.bytes();
 216             let align = align.abi();
 217             assert!(align <= std::u32::MAX as u64);
 218             let discr_ty = Type::from_integer(cx, discr);
 219             let discr_size = discr.size().bytes();
 220             let padded_discr_size = roundup(discr_size, align as u32);
 221             let variant_part_size = size-padded_discr_size;
 222             let variant_fill = union_fill(cx, variant_part_size, align);
 223
 224             assert_eq!(machine::llalign_of_min(cx, variant_fill), align as u32);
 225             assert_eq!(padded_discr_size % discr_size, 0); // Ensure discr_ty can fill pad evenly
 226             let fields: Vec<Type> =
 227                 [discr_ty,
 228                  Type::array(&discr_ty, (padded_discr_size - discr_size)/discr_size),
 229                  variant_fill].iter().cloned().collect();
 230             match name {
 231                 None => {
 232                     Type::struct_(cx, &fields[..], false)
 233                 }
 234                 Some(name) => {
 235                     let mut llty = Type::named_struct(cx, name);
 236                     llty.set_struct_body(&fields[..], false);
 237                     llty
 238                 }
 239             }
 240         }
 241         _ => bug!("Unsupported type {} represented as {:#?}", t, l)
 242     }
 243 }
 244
 245 fn union_fill(cx: &CrateContext, size: u64, align: u64) -> Type {
 246     assert_eq!(size%align, 0);
 247     assert_eq!(align.count_ones(), 1, "Alignment must be a power fof 2. Got {}", align);
 248     let align_units = size/align;
 249     let dl = &cx.tcx().data_layout;
 250     let layout_align = layout::Align::from_bytes(align, align).unwrap();
 251     if let Some(ity) = layout::Integer::for_abi_align(dl, layout_align) {
 252         Type::array(&Type::from_integer(cx, ity), align_units)
 253     } else {
 254         Type::array(&Type::vector(&Type::i32(cx), align/4),
 255                     align_units)
 256     }
 257 }
 258
 259
 260 fn struct_llfields<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, fields: &Vec<Ty<'tcx>>,
 261                              variant: &layout::Struct,
 262                              sizing: bool, dst: bool) -> Vec<Type> {
 263     let fields = variant.field_index_by_increasing_offset().map(|i| fields[i as usize]);
 264     if sizing {
 265         fields.filter(|ty| !dst || cx.shared().type_is_sized(*ty))
 266             .map(|ty| type_of::sizing_type_of(cx, ty)).collect()
 267     } else {
 268         fields.map(|ty| type_of::in_memory_type_of(cx, ty)).collect()
 269     }
 270 }
 271
 272 pub fn is_discr_signed<'tcx>(l: &layout::Layout) -> bool {
 273     match *l {
 274         layout::CEnum { signed, .. }=> signed,
 275         _ => false,
 276     }
 277 }
 278
 279 /// Obtain the actual discriminant of a value.
 280 pub fn trans_get_discr<'a, 'tcx>(
 281     bcx: &Builder<'a, 'tcx>,
 282     t: Ty<'tcx>,
 283     scrutinee: ValueRef,
 284     alignment: Alignment,
 285     cast_to: Option<Type>,
 286     range_assert: bool
 287 ) -> ValueRef {
 288     let (def, substs) = match t.sty {
 289         ty::TyAdt(ref def, substs) if def.adt_kind() == AdtKind::Enum => (def, substs),
 290         _ => bug!("{} is not an enum", t)
 291     };
 292
 293     debug!("trans_get_discr t: {:?}", t);
 294     let l = bcx.ccx.layout_of(t);
 295
 296     let val = match *l {
 297         layout::CEnum { discr, min, max, .. } => {
 298             load_discr(bcx, discr, scrutinee, alignment, min, max, range_assert)
 299         }
 300         layout::General { discr, .. } => {
 301             let ptr = bcx.struct_gep(scrutinee, 0);
 302             load_discr(bcx, discr, ptr, alignment,
 303                        0, def.variants.len() as u64 - 1,
 304                        range_assert)
 305         }
 306         layout::Univariant { .. } | layout::UntaggedUnion { .. } => C_u8(bcx.ccx, 0),
 307         layout::RawNullablePointer { nndiscr, .. } => {
 308             let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
 309             let llptrty = type_of::sizing_type_of(bcx.ccx,
 310                 monomorphize::field_ty(bcx.tcx(), substs,
 311                 &def.variants[nndiscr as usize].fields[0]));
 312             bcx.icmp(cmp, bcx.load(scrutinee, alignment.to_align()), C_null(llptrty))
 313         }
 314         layout::StructWrappedNullablePointer { nndiscr, ref discrfield, .. } => {
 315             struct_wrapped_nullable_bitdiscr(bcx, nndiscr, discrfield, scrutinee, alignment)
 316         },
 317         _ => bug!("{} is not an enum", t)
 318     };
 319     match cast_to {
 320         None => val,
 321         Some(llty) => if is_discr_signed(&l) { bcx.sext(val, llty) } else { bcx.zext(val, llty) }
 322     }
 323 }
 324
 325 fn struct_wrapped_nullable_bitdiscr(
 326     bcx: &Builder,
 327     nndiscr: u64,
 328     discrfield: &layout::FieldPath,
 329     scrutinee: ValueRef,
 330     alignment: Alignment,
 331 ) -> ValueRef {
 332     let llptrptr = bcx.gepi(scrutinee,
 333         &discrfield.iter().map(|f| *f as usize).collect::<Vec<_>>()[..]);
 334     let llptr = bcx.load(llptrptr, alignment.to_align());
 335     let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
 336     bcx.icmp(cmp, llptr, C_null(val_ty(llptr)))
 337 }
 338
 339 /// Helper for cases where the discriminant is simply loaded.
 340 fn load_discr(bcx: &Builder, ity: layout::Integer, ptr: ValueRef,
 341               alignment: Alignment, min: u64, max: u64,
 342               range_assert: bool)
 343     -> ValueRef {
 344     let llty = Type::from_integer(bcx.ccx, ity);
 345     assert_eq!(val_ty(ptr), llty.ptr_to());
 346     let bits = ity.size().bits();
 347     assert!(bits <= 64);
 348     let bits = bits as usize;
 349     let mask = !0u64 >> (64 - bits);
 350     // For a (max) discr of -1, max will be `-1 as usize`, which overflows.
 351     // However, that is fine here (it would still represent the full range),
 352     if max.wrapping_add(1) & mask == min & mask || !range_assert {
 353         // i.e., if the range is everything.  The lo==hi case would be
 354         // rejected by the LLVM verifier (it would mean either an
 355         // empty set, which is impossible, or the entire range of the
 356         // type, which is pointless).
 357         bcx.load(ptr, alignment.to_align())
 358     } else {
 359         // llvm::ConstantRange can deal with ranges that wrap around,
 360         // so an overflow on (max + 1) is fine.
 361         bcx.load_range_assert(ptr, min, max.wrapping_add(1), /* signed: */ True,
 362                               alignment.to_align())
 363     }
 364 }
 365
 366 /// Yield information about how to dispatch a case of the
 367 /// discriminant-like value returned by `trans_switch`.
 368 ///
 369 /// This should ideally be less tightly tied to `_match`.
 370 pub fn trans_case<'a, 'tcx>(bcx: &Builder<'a, 'tcx>, t: Ty<'tcx>, value: Disr) -> ValueRef {
 371     let l = bcx.ccx.layout_of(t);
 372     match *l {
 373         layout::CEnum { discr, .. }
 374         | layout::General { discr, .. }=> {
 375             C_integral(Type::from_integer(bcx.ccx, discr), value.0, true)
 376         }
 377         layout::RawNullablePointer { .. } |
 378         layout::StructWrappedNullablePointer { .. } => {
 379             assert!(value == Disr(0) || value == Disr(1));
 380             C_bool(bcx.ccx, value != Disr(0))
 381         }
 382         _ => {
 383             bug!("{} does not have a discriminant. Represented as {:#?}", t, l);
 384         }
 385     }
 386 }
 387
 388 /// Set the discriminant for a new value of the given case of the given
 389 /// representation.
 390 pub fn trans_set_discr<'a, 'tcx>(bcx: &Builder<'a, 'tcx>, t: Ty<'tcx>, val: ValueRef, to: Disr) {
 391     let l = bcx.ccx.layout_of(t);
 392     match *l {
 393         layout::CEnum{ discr, min, max, .. } => {
 394             assert_discr_in_range(Disr(min), Disr(max), to);
 395             bcx.store(C_integral(Type::from_integer(bcx.ccx, discr), to.0, true),
 396                   val, None);
 397         }
 398         layout::General{ discr, .. } => {
 399             bcx.store(C_integral(Type::from_integer(bcx.ccx, discr), to.0, true),
 400                   bcx.struct_gep(val, 0), None);
 401         }
 402         layout::Univariant { .. }
 403         | layout::UntaggedUnion { .. }
 404         | layout::Vector { .. } => {
 405             assert_eq!(to, Disr(0));
 406         }
 407         layout::RawNullablePointer { nndiscr, .. } => {
 408             let nnty = compute_fields(bcx.ccx, t, nndiscr as usize, false)[0];
 409             if to.0 != nndiscr {
 410                 let llptrty = type_of::sizing_type_of(bcx.ccx, nnty);
 411                 bcx.store(C_null(llptrty), val, None);
 412             }
 413         }
 414         layout::StructWrappedNullablePointer { nndiscr, ref discrfield, ref nonnull, .. } => {
 415             if to.0 != nndiscr {
 416                 if target_sets_discr_via_memset(bcx) {
 417                     // Issue #34427: As workaround for LLVM bug on
 418                     // ARM, use memset of 0 on whole struct rather
 419                     // than storing null to single target field.
 420                     let llptr = bcx.pointercast(val, Type::i8(bcx.ccx).ptr_to());
 421                     let fill_byte = C_u8(bcx.ccx, 0);
 422                     let size = C_uint(bcx.ccx, nonnull.stride().bytes());
 423                     let align = C_i32(bcx.ccx, nonnull.align.abi() as i32);
 424                     base::call_memset(bcx, llptr, fill_byte, size, align, false);
 425                 } else {
 426                     let path = discrfield.iter().map(|&i| i as usize).collect::<Vec<_>>();
 427                     let llptrptr = bcx.gepi(val, &path[..]);
 428                     let llptrty = val_ty(llptrptr).element_type();
 429                     bcx.store(C_null(llptrty), llptrptr, None);
 430                 }
 431             }
 432         }
 433         _ => bug!("Cannot handle {} represented as {:#?}", t, l)
 434     }
 435 }
 436
 437 fn target_sets_discr_via_memset<'a, 'tcx>(bcx: &Builder<'a, 'tcx>) -> bool {
 438     bcx.sess().target.target.arch == "arm" || bcx.sess().target.target.arch == "aarch64"
 439 }
 440
 441 pub fn assert_discr_in_range(min: Disr, max: Disr, discr: Disr) {
 442     if min <= max {
 443         assert!(min <= discr && discr <= max)
 444     } else {
 445         assert!(min <= discr || discr <= max)
 446     }
 447 }
 448
 449 // FIXME this utility routine should be somewhere more general
 450 #[inline]
 451 fn roundup(x: u64, a: u32) -> u64 { let a = a as u64; ((x + (a - 1)) / a) * a }
 452
 453 /// Extract a field of a constant value, as appropriate for its
 454 /// representation.
 455 ///
 456 /// (Not to be confused with `common::const_get_elt`, which operates on
 457 /// raw LLVM-level structs and arrays.)
 458 pub fn const_get_field<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>,
 459                        val: ValueRef, _discr: Disr,
 460                        ix: usize) -> ValueRef {
 461     let l = ccx.layout_of(t);
 462     match *l {
 463         layout::CEnum { .. } => bug!("element access in C-like enum const"),
 464         layout::Univariant { ref variant, .. } => {
 465             const_struct_field(val, variant.memory_index[ix] as usize)
 466         }
 467         layout::Vector { .. } => const_struct_field(val, ix),
 468         layout::UntaggedUnion { .. } => const_struct_field(val, 0),
 469         _ => bug!("{} does not have fields.", t)
 470     }
 471 }
 472
 473 /// Extract field of struct-like const, skipping our alignment padding.
 474 fn const_struct_field(val: ValueRef, ix: usize) -> ValueRef {
 475     // Get the ix-th non-undef element of the struct.
 476     let mut real_ix = 0; // actual position in the struct
 477     let mut ix = ix; // logical index relative to real_ix
 478     let mut field;
 479     loop {
 480         loop {
 481             field = const_get_elt(val, &[real_ix]);
 482             if !is_undef(field) {
 483                 break;
 484             }
 485             real_ix = real_ix + 1;
 486         }
 487         if ix == 0 {
 488             return field;
 489         }
 490         ix = ix - 1;
 491         real_ix = real_ix + 1;
 492     }
 493 }