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 std;
  45
  46 use llvm::{ValueRef, True, IntEQ, IntNE};
  47 use rustc::ty::{self, Ty};
  48 use rustc::ty::layout::{self, LayoutTyper};
  49 use common::*;
  50 use builder::Builder;
  51 use base;
  52 use machine;
  53 use monomorphize;
  54 use type_::Type;
  55 use type_of;
  56
  57 use mir::lvalue::Alignment;
  58
  59 /// Given an enum, struct, closure, or tuple, extracts fields.
  60 /// Treats closures as a struct with one variant.
  61 /// `empty_if_no_variants` is a switch to deal with empty enums.
  62 /// If true, `variant_index` is disregarded and an empty Vec returned in this case.
  63 pub fn compute_fields<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>,
  64                                 variant_index: usize,
  65                                 empty_if_no_variants: bool) -> Vec<Ty<'tcx>> {
  66     match t.sty {
  67         ty::TyAdt(ref def, _) if def.variants.len() == 0 && empty_if_no_variants => {
  68             Vec::default()
  69         },
  70         ty::TyAdt(ref def, ref substs) => {
  71             def.variants[variant_index].fields.iter().map(|f| {
  72                 monomorphize::field_ty(cx.tcx(), substs, f)
  73             }).collect::<Vec<_>>()
  74         },
  75         ty::TyTuple(fields, _) => fields.to_vec(),
  76         ty::TyClosure(def_id, substs) => {
  77             if variant_index > 0 { bug!("{} is a closure, which only has one variant", t);}
  78             substs.upvar_tys(def_id, cx.tcx()).collect()
  79         },
  80         _ => bug!("{} is not a type that can have fields.", t)
  81     }
  82 }
  83
  84 /// LLVM-level types are a little complicated.
  85 ///
  86 /// C-like enums need to be actual ints, not wrapped in a struct,
  87 /// because that changes the ABI on some platforms (see issue #10308).
  88 ///
  89 /// For nominal types, in some cases, we need to use LLVM named structs
  90 /// and fill in the actual contents in a second pass to prevent
  91 /// unbounded recursion; see also the comments in `trans::type_of`.
  92 pub fn type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) -> Type {
  93     generic_type_of(cx, t, None, false, false)
  94 }
  95
  96 pub fn incomplete_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
  97                                     t: Ty<'tcx>, name: &str) -> Type {
  98     generic_type_of(cx, t, Some(name), false, false)
  99 }
 100
 101 pub fn finish_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 102                                 t: Ty<'tcx>, llty: &mut Type) {
 103     let l = cx.layout_of(t);
 104     debug!("finish_type_of: {} with layout {:#?}", t, l);
 105     match *l {
 106         layout::CEnum { .. } | layout::General { .. }
 107         | layout::UntaggedUnion { .. } | layout::RawNullablePointer { .. } => { }
 108         layout::Univariant { ..}
 109         | layout::StructWrappedNullablePointer { .. } => {
 110             let (nonnull_variant_index, nonnull_variant, packed) = match *l {
 111                 layout::Univariant { ref variant, .. } => (0, variant, variant.packed),
 112                 layout::StructWrappedNullablePointer { nndiscr, ref nonnull, .. } =>
 113                     (nndiscr, nonnull, nonnull.packed),
 114                 _ => unreachable!()
 115             };
 116             let fields = compute_fields(cx, t, nonnull_variant_index as usize, true);
 117             llty.set_struct_body(&struct_llfields(cx, &fields, nonnull_variant, false, false),
 118                                  packed)
 119         },
 120         _ => bug!("This function cannot handle {} with layout {:#?}", t, l)
 121     }
 122 }
 123
 124 fn generic_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 125                              t: Ty<'tcx>,
 126                              name: Option<&str>,
 127                              sizing: bool,
 128                              dst: bool) -> Type {
 129     let l = cx.layout_of(t);
 130     debug!("adt::generic_type_of t: {:?} name: {:?} sizing: {} dst: {}",
 131            t, name, sizing, dst);
 132     match *l {
 133         layout::CEnum { discr, .. } => Type::from_integer(cx, discr),
 134         layout::RawNullablePointer { nndiscr, .. } => {
 135             let (def, substs) = match t.sty {
 136                 ty::TyAdt(d, s) => (d, s),
 137                 _ => bug!("{} is not an ADT", t)
 138             };
 139             let nnty = monomorphize::field_ty(cx.tcx(), substs,
 140                 &def.variants[nndiscr as usize].fields[0]);
 141             if let layout::Scalar { value: layout::Pointer, .. } = *cx.layout_of(nnty) {
 142                 Type::i8p(cx)
 143             } else {
 144                 type_of::type_of(cx, nnty)
 145             }
 146         }
 147         layout::StructWrappedNullablePointer { nndiscr, ref nonnull, .. } => {
 148             let fields = compute_fields(cx, t, nndiscr as usize, false);
 149             match name {
 150                 None => {
 151                     Type::struct_(cx, &struct_llfields(cx, &fields, nonnull, sizing, dst),
 152                                   nonnull.packed)
 153                 }
 154                 Some(name) => {
 155                     assert_eq!(sizing, false);
 156                     Type::named_struct(cx, name)
 157                 }
 158             }
 159         }
 160         layout::Univariant { ref variant, .. } => {
 161             // Note that this case also handles empty enums.
 162             // Thus the true as the final parameter here.
 163             let fields = compute_fields(cx, t, 0, true);
 164             match name {
 165                 None => {
 166                     let fields = struct_llfields(cx, &fields, &variant, sizing, dst);
 167                     Type::struct_(cx, &fields, variant.packed)
 168                 }
 169                 Some(name) => {
 170                     // Hypothesis: named_struct's can never need a
 171                     // drop flag. (... needs validation.)
 172                     assert_eq!(sizing, false);
 173                     Type::named_struct(cx, name)
 174                 }
 175             }
 176         }
 177         layout::UntaggedUnion { ref variants, .. }=> {
 178             // Use alignment-sized ints to fill all the union storage.
 179             let size = variants.stride().bytes();
 180             let align = variants.align.abi();
 181             let fill = union_fill(cx, size, align);
 182             match name {
 183                 None => {
 184                     Type::struct_(cx, &[fill], variants.packed)
 185                 }
 186                 Some(name) => {
 187                     let mut llty = Type::named_struct(cx, name);
 188                     llty.set_struct_body(&[fill], variants.packed);
 189                     llty
 190                 }
 191             }
 192         }
 193         layout::General { discr, size, align, .. } => {
 194             // We need a representation that has:
 195             // * The alignment of the most-aligned field
 196             // * The size of the largest variant (rounded up to that alignment)
 197             // * No alignment padding anywhere any variant has actual data
 198             //   (currently matters only for enums small enough to be immediate)
 199             // * The discriminant in an obvious place.
 200             //
 201             // So we start with the discriminant, pad it up to the alignment with
 202             // more of its own type, then use alignment-sized ints to get the rest
 203             // of the size.
 204             let size = size.bytes();
 205             let align = align.abi();
 206             assert!(align <= std::u32::MAX as u64);
 207             let discr_ty = Type::from_integer(cx, discr);
 208             let discr_size = discr.size().bytes();
 209             let padded_discr_size = roundup(discr_size, align as u32);
 210             let variant_part_size = size-padded_discr_size;
 211             let variant_fill = union_fill(cx, variant_part_size, align);
 212
 213             assert_eq!(machine::llalign_of_min(cx, variant_fill), align as u32);
 214             assert_eq!(padded_discr_size % discr_size, 0); // Ensure discr_ty can fill pad evenly
 215             let fields: Vec<Type> =
 216                 [discr_ty,
 217                  Type::array(&discr_ty, (padded_discr_size - discr_size)/discr_size),
 218                  variant_fill].iter().cloned().collect();
 219             match name {
 220                 None => {
 221                     Type::struct_(cx, &fields, false)
 222                 }
 223                 Some(name) => {
 224                     let mut llty = Type::named_struct(cx, name);
 225                     llty.set_struct_body(&fields, false);
 226                     llty
 227                 }
 228             }
 229         }
 230         _ => bug!("Unsupported type {} represented as {:#?}", t, l)
 231     }
 232 }
 233
 234 fn union_fill(cx: &CrateContext, size: u64, align: u64) -> Type {
 235     assert_eq!(size%align, 0);
 236     assert_eq!(align.count_ones(), 1, "Alignment must be a power fof 2. Got {}", align);
 237     let align_units = size/align;
 238     let layout_align = layout::Align::from_bytes(align, align).unwrap();
 239     if let Some(ity) = layout::Integer::for_abi_align(cx, layout_align) {
 240         Type::array(&Type::from_integer(cx, ity), align_units)
 241     } else {
 242         Type::array(&Type::vector(&Type::i32(cx), align/4),
 243                     align_units)
 244     }
 245 }
 246
 247
 248 fn struct_llfields<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, fields: &Vec<Ty<'tcx>>,
 249                              variant: &layout::Struct,
 250                              sizing: bool, _dst: bool) -> Vec<Type> {
 251     let fields = variant.field_index_by_increasing_offset().map(|i| fields[i as usize]);
 252     if sizing {
 253         bug!()
 254     } else {
 255         fields.map(|ty| type_of::in_memory_type_of(cx, ty)).collect()
 256     }
 257 }
 258
 259 pub fn is_discr_signed<'tcx>(l: &layout::Layout) -> bool {
 260     match *l {
 261         layout::CEnum { signed, .. }=> signed,
 262         _ => false,
 263     }
 264 }
 265
 266 /// Obtain the actual discriminant of a value.
 267 pub fn trans_get_discr<'a, 'tcx>(
 268     bcx: &Builder<'a, 'tcx>,
 269     t: Ty<'tcx>,
 270     scrutinee: ValueRef,
 271     alignment: Alignment,
 272     cast_to: Option<Type>,
 273     range_assert: bool
 274 ) -> ValueRef {
 275     debug!("trans_get_discr t: {:?}", t);
 276     let l = bcx.ccx.layout_of(t);
 277
 278     let val = match *l {
 279         layout::CEnum { discr, min, max, .. } => {
 280             load_discr(bcx, discr, scrutinee, alignment, min, max, range_assert)
 281         }
 282         layout::General { discr, ref variants, .. } => {
 283             let ptr = bcx.struct_gep(scrutinee, 0);
 284             load_discr(bcx, discr, ptr, alignment,
 285                        0, variants.len() as u64 - 1,
 286                        range_assert)
 287         }
 288         layout::Univariant { .. } | layout::UntaggedUnion { .. } => C_u8(bcx.ccx, 0),
 289         layout::RawNullablePointer { nndiscr, .. } => {
 290             let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
 291             let discr = bcx.load(scrutinee, alignment.to_align());
 292             bcx.icmp(cmp, discr, C_null(val_ty(discr)))
 293         }
 294         layout::StructWrappedNullablePointer { nndiscr, ref discrfield, .. } => {
 295             struct_wrapped_nullable_bitdiscr(bcx, nndiscr, discrfield, scrutinee, alignment)
 296         },
 297         _ => bug!("{} is not an enum", t)
 298     };
 299     match cast_to {
 300         None => val,
 301         Some(llty) => bcx.intcast(val, llty, is_discr_signed(&l))
 302     }
 303 }
 304
 305 fn struct_wrapped_nullable_bitdiscr(
 306     bcx: &Builder,
 307     nndiscr: u64,
 308     discrfield: &layout::FieldPath,
 309     scrutinee: ValueRef,
 310     alignment: Alignment,
 311 ) -> ValueRef {
 312     let llptrptr = bcx.gepi(scrutinee,
 313         &discrfield.iter().map(|f| *f as usize).collect::<Vec<_>>());
 314     let llptr = bcx.load(llptrptr, alignment.to_align());
 315     let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
 316     bcx.icmp(cmp, llptr, C_null(val_ty(llptr)))
 317 }
 318
 319 /// Helper for cases where the discriminant is simply loaded.
 320 fn load_discr(bcx: &Builder, ity: layout::Integer, ptr: ValueRef,
 321               alignment: Alignment, min: u64, max: u64,
 322               range_assert: bool)
 323     -> ValueRef {
 324     let llty = Type::from_integer(bcx.ccx, ity);
 325     assert_eq!(val_ty(ptr), llty.ptr_to());
 326     let bits = ity.size().bits();
 327     assert!(bits <= 64);
 328     let bits = bits as usize;
 329     let mask = !0u64 >> (64 - bits);
 330     // For a (max) discr of -1, max will be `-1 as usize`, which overflows.
 331     // However, that is fine here (it would still represent the full range),
 332     if max.wrapping_add(1) & mask == min & mask || !range_assert {
 333         // i.e., if the range is everything.  The lo==hi case would be
 334         // rejected by the LLVM verifier (it would mean either an
 335         // empty set, which is impossible, or the entire range of the
 336         // type, which is pointless).
 337         bcx.load(ptr, alignment.to_align())
 338     } else {
 339         // llvm::ConstantRange can deal with ranges that wrap around,
 340         // so an overflow on (max + 1) is fine.
 341         bcx.load_range_assert(ptr, min, max.wrapping_add(1), /* signed: */ True,
 342                               alignment.to_align())
 343     }
 344 }
 345
 346 /// Set the discriminant for a new value of the given case of the given
 347 /// representation.
 348 pub fn trans_set_discr<'a, 'tcx>(bcx: &Builder<'a, 'tcx>, t: Ty<'tcx>, val: ValueRef, to: u64) {
 349     let l = bcx.ccx.layout_of(t);
 350     match *l {
 351         layout::CEnum{ discr, min, max, .. } => {
 352             assert_discr_in_range(min, max, to);
 353             bcx.store(C_integral(Type::from_integer(bcx.ccx, discr), to, true),
 354                   val, None);
 355         }
 356         layout::General{ discr, .. } => {
 357             bcx.store(C_integral(Type::from_integer(bcx.ccx, discr), to, true),
 358                   bcx.struct_gep(val, 0), None);
 359         }
 360         layout::Univariant { .. }
 361         | layout::UntaggedUnion { .. }
 362         | layout::Vector { .. } => {
 363             assert_eq!(to, 0);
 364         }
 365         layout::RawNullablePointer { nndiscr, .. } => {
 366             if to != nndiscr {
 367                 let llptrty = val_ty(val).element_type();
 368                 bcx.store(C_null(llptrty), val, None);
 369             }
 370         }
 371         layout::StructWrappedNullablePointer { nndiscr, ref discrfield, ref nonnull, .. } => {
 372             if to != nndiscr {
 373                 if target_sets_discr_via_memset(bcx) {
 374                     // Issue #34427: As workaround for LLVM bug on
 375                     // ARM, use memset of 0 on whole struct rather
 376                     // than storing null to single target field.
 377                     let llptr = bcx.pointercast(val, Type::i8(bcx.ccx).ptr_to());
 378                     let fill_byte = C_u8(bcx.ccx, 0);
 379                     let size = C_uint(bcx.ccx, nonnull.stride().bytes());
 380                     let align = C_i32(bcx.ccx, nonnull.align.abi() as i32);
 381                     base::call_memset(bcx, llptr, fill_byte, size, align, false);
 382                 } else {
 383                     let path = discrfield.iter().map(|&i| i as usize).collect::<Vec<_>>();
 384                     let llptrptr = bcx.gepi(val, &path);
 385                     let llptrty = val_ty(llptrptr).element_type();
 386                     bcx.store(C_null(llptrty), llptrptr, None);
 387                 }
 388             }
 389         }
 390         _ => bug!("Cannot handle {} represented as {:#?}", t, l)
 391     }
 392 }
 393
 394 fn target_sets_discr_via_memset<'a, 'tcx>(bcx: &Builder<'a, 'tcx>) -> bool {
 395     bcx.sess().target.target.arch == "arm" || bcx.sess().target.target.arch == "aarch64"
 396 }
 397
 398 pub fn assert_discr_in_range<D: PartialOrd>(min: D, max: D, discr: D) {
 399     if min <= max {
 400         assert!(min <= discr && discr <= max)
 401     } else {
 402         assert!(min <= discr || discr <= max)
 403     }
 404 }
 405
 406 // FIXME this utility routine should be somewhere more general
 407 #[inline]
 408 fn roundup(x: u64, a: u32) -> u64 { let a = a as u64; ((x + (a - 1)) / a) * a }
 409
 410 /// Extract a field of a constant value, as appropriate for its
 411 /// representation.
 412 ///
 413 /// (Not to be confused with `common::const_get_elt`, which operates on
 414 /// raw LLVM-level structs and arrays.)
 415 pub fn const_get_field<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>,
 416                        val: ValueRef,
 417                        ix: usize) -> ValueRef {
 418     let l = ccx.layout_of(t);
 419     match *l {
 420         layout::CEnum { .. } => bug!("element access in C-like enum const"),
 421         layout::Univariant { ref variant, .. } => {
 422             const_struct_field(val, variant.memory_index[ix] as usize)
 423         }
 424         layout::Vector { .. } => const_struct_field(val, ix),
 425         layout::UntaggedUnion { .. } => const_struct_field(val, 0),
 426         _ => bug!("{} does not have fields.", t)
 427     }
 428 }
 429
 430 /// Extract field of struct-like const, skipping our alignment padding.
 431 fn const_struct_field(val: ValueRef, ix: usize) -> ValueRef {
 432     // Get the ix-th non-undef element of the struct.
 433     let mut real_ix = 0; // actual position in the struct
 434     let mut ix = ix; // logical index relative to real_ix
 435     let mut field;
 436     loop {
 437         loop {
 438             field = const_get_elt(val, &[real_ix]);
 439             if !is_undef(field) {
 440                 break;
 441             }
 442             real_ix = real_ix + 1;
 443         }
 444         if ix == 0 {
 445             return field;
 446         }
 447         ix = ix - 1;
 448         real_ix = real_ix + 1;
 449     }
 450 }