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.
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.
11 //! # Representation of Algebraic Data Types
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.)
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.
23 //! Having everything in one place will enable improvements to data
24 //! structure representation; possibilities include:
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
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.
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.
44 #![allow(unsigned_negation)]
46 pub use self::Repr::*;
51 use llvm::{ValueRef, True, IntEQ, IntNE};
52 use back::abi::FAT_PTR_ADDR;
54 use middle::ty::{self, Ty, ClosureTyper};
58 use syntax::attr::IntType;
62 use trans::cleanup::CleanupMethods;
65 use trans::debuginfo::DebugLoc;
67 use trans::monomorphize;
68 use trans::type_::Type;
70 use util::ppaux::ty_to_string;
72 type Hint = attr::ReprAttr;
75 #[derive(Eq, PartialEq, Debug)]
77 /// C-like enums; basically an int.
78 CEnum(IntType, Disr, Disr), // discriminant range (signedness based on the IntType)
79 /// Single-case variants, and structs/tuples/records.
81 /// Structs with destructors need a dynamic destroyedness flag to
82 /// avoid running the destructor too many times; this is included
83 /// in the `Struct` if present.
84 Univariant(Struct<'tcx>, bool),
85 /// General-case enums: for each case there is a struct, and they
86 /// all start with a field for the discriminant.
88 /// Types with destructors need a dynamic destroyedness flag to
89 /// avoid running the destructor too many times; the last argument
90 /// indicates whether such a flag is present.
91 General(IntType, Vec<Struct<'tcx>>, bool),
92 /// Two cases distinguished by a nullable pointer: the case with discriminant
93 /// `nndiscr` must have single field which is known to be nonnull due to its type.
94 /// The other case is known to be zero sized. Hence we represent the enum
95 /// as simply a nullable pointer: if not null it indicates the `nndiscr` variant,
96 /// otherwise it indicates the other case.
100 nullfields: Vec<Ty<'tcx>>
102 /// Two cases distinguished by a nullable pointer: the case with discriminant
103 /// `nndiscr` is represented by the struct `nonnull`, where the `discrfield`th
104 /// field is known to be nonnull due to its type; if that field is null, then
105 /// it represents the other case, which is inhabited by at most one value
106 /// (and all other fields are undefined/unused).
108 /// For example, `std::option::Option` instantiated at a safe pointer type
109 /// is represented such that `None` is a null pointer and `Some` is the
110 /// identity function.
111 StructWrappedNullablePointer {
112 nonnull: Struct<'tcx>,
114 discrfield: DiscrField,
115 nullfields: Vec<Ty<'tcx>>,
119 /// For structs, and struct-like parts of anything fancier.
120 #[derive(Eq, PartialEq, Debug)]
121 pub struct Struct<'tcx> {
122 // If the struct is DST, then the size and alignment do not take into
123 // account the unsized fields of the struct.
128 pub fields: Vec<Ty<'tcx>>
131 /// Convenience for `represent_type`. There should probably be more or
132 /// these, for places in trans where the `Ty` isn't directly
134 pub fn represent_node<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
135 node: ast::NodeId) -> Rc<Repr<'tcx>> {
136 represent_type(bcx.ccx(), node_id_type(bcx, node))
139 /// Decides how to represent a given type.
140 pub fn represent_type<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
141 t: Ty<'tcx>) -> Rc<Repr<'tcx>> {
142 debug!("Representing: {}", ty_to_string(cx.tcx(), t));
143 match cx.adt_reprs().borrow().get(&t) {
144 Some(repr) => return repr.clone(),
148 let repr = Rc::new(represent_type_uncached(cx, t));
149 debug!("Represented as: {:?}", repr);
150 cx.adt_reprs().borrow_mut().insert(t, repr.clone());
154 fn represent_type_uncached<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
155 t: Ty<'tcx>) -> Repr<'tcx> {
157 ty::ty_tup(ref elems) => {
158 Univariant(mk_struct(cx, &elems[..], false, t), false)
160 ty::ty_struct(def_id, substs) => {
161 let fields = ty::lookup_struct_fields(cx.tcx(), def_id);
162 let mut ftys = fields.iter().map(|field| {
163 let fty = ty::lookup_field_type(cx.tcx(), def_id, field.id, substs);
164 monomorphize::normalize_associated_type(cx.tcx(), &fty)
165 }).collect::<Vec<_>>();
166 let packed = ty::lookup_packed(cx.tcx(), def_id);
167 let dtor = ty::ty_dtor(cx.tcx(), def_id).has_drop_flag();
168 if dtor { ftys.push(cx.tcx().types.bool); }
170 Univariant(mk_struct(cx, &ftys[..], packed, t), dtor)
172 ty::ty_closure(def_id, _, substs) => {
173 let typer = NormalizingClosureTyper::new(cx.tcx());
174 let upvars = typer.closure_upvars(def_id, substs).unwrap();
175 let upvar_types = upvars.iter().map(|u| u.ty).collect::<Vec<_>>();
176 Univariant(mk_struct(cx, &upvar_types[..], false, t), false)
178 ty::ty_enum(def_id, substs) => {
179 let cases = get_cases(cx.tcx(), def_id, substs);
180 let hint = *ty::lookup_repr_hints(cx.tcx(), def_id)[].get(0)
181 .unwrap_or(&attr::ReprAny);
183 let dtor = ty::ty_dtor(cx.tcx(), def_id).has_drop_flag();
185 if cases.len() == 0 {
186 // Uninhabitable; represent as unit
187 // (Typechecking will reject discriminant-sizing attrs.)
188 assert_eq!(hint, attr::ReprAny);
189 let ftys = if dtor { vec!(cx.tcx().types.bool) } else { vec!() };
190 return Univariant(mk_struct(cx, &ftys[..], false, t),
194 if !dtor && cases.iter().all(|c| c.tys.len() == 0) {
195 // All bodies empty -> intlike
196 let discrs: Vec<u64> = cases.iter().map(|c| c.discr).collect();
197 let bounds = IntBounds {
198 ulo: *discrs.iter().min().unwrap(),
199 uhi: *discrs.iter().max().unwrap(),
200 slo: discrs.iter().map(|n| *n as i64).min().unwrap(),
201 shi: discrs.iter().map(|n| *n as i64).max().unwrap()
203 return mk_cenum(cx, hint, &bounds);
206 // Since there's at least one
207 // non-empty body, explicit discriminants should have
208 // been rejected by a checker before this point.
209 if !cases.iter().enumerate().all(|(i,c)| c.discr == (i as Disr)) {
210 cx.sess().bug(&format!("non-C-like enum {} with specified \
212 ty::item_path_str(cx.tcx(),
216 if cases.len() == 1 {
217 // Equivalent to a struct/tuple/newtype.
218 // (Typechecking will reject discriminant-sizing attrs.)
219 assert_eq!(hint, attr::ReprAny);
220 let mut ftys = cases[0].tys.clone();
221 if dtor { ftys.push(cx.tcx().types.bool); }
222 return Univariant(mk_struct(cx, &ftys[..], false, t),
226 if !dtor && cases.len() == 2 && hint == attr::ReprAny {
227 // Nullable pointer optimization
230 if cases[1 - discr].is_zerolen(cx, t) {
231 let st = mk_struct(cx, &cases[discr].tys[],
233 match cases[discr].find_ptr(cx) {
234 Some(ref df) if df.len() == 1 && st.fields.len() == 1 => {
235 return RawNullablePointer {
236 nndiscr: discr as Disr,
238 nullfields: cases[1 - discr].tys.clone()
241 Some(mut discrfield) => {
243 discrfield.reverse();
244 return StructWrappedNullablePointer {
245 nndiscr: discr as Disr,
247 discrfield: discrfield,
248 nullfields: cases[1 - discr].tys.clone()
259 assert!((cases.len() - 1) as i64 >= 0);
260 let bounds = IntBounds { ulo: 0, uhi: (cases.len() - 1) as u64,
261 slo: 0, shi: (cases.len() - 1) as i64 };
262 let min_ity = range_to_inttype(cx, hint, &bounds);
264 // Create the set of structs that represent each variant
265 // Use the minimum integer type we figured out above
266 let fields : Vec<_> = cases.iter().map(|c| {
267 let mut ftys = vec!(ty_of_inttype(cx.tcx(), min_ity));
268 ftys.push_all(&c.tys);
269 if dtor { ftys.push(cx.tcx().types.bool); }
270 mk_struct(cx, &ftys, false, t)
274 // Check to see if we should use a different type for the
275 // discriminant. If the overall alignment of the type is
276 // the same as the first field in each variant, we can safely use
277 // an alignment-sized type.
278 // We increase the size of the discriminant to avoid LLVM copying
279 // padding when it doesn't need to. This normally causes unaligned
280 // load/stores and excessive memcpy/memset operations. By using a
281 // bigger integer size, LLVM can be sure about it's contents and
282 // won't be so conservative.
283 // This check is needed to avoid increasing the size of types when
284 // the alignment of the first field is smaller than the overall
285 // alignment of the type.
286 let (_, align) = union_size_and_align(&fields);
287 let mut use_align = true;
289 // Get the first non-zero-sized field
290 let field = st.fields.iter().skip(1).filter(|ty| {
291 let t = type_of::sizing_type_of(cx, **ty);
292 machine::llsize_of_real(cx, t) != 0 ||
293 // This case is only relevant for zero-sized types with large alignment
294 machine::llalign_of_min(cx, t) != 1
297 if let Some(field) = field {
298 let field_align = type_of::align_of(cx, *field);
299 if field_align != align {
305 let ity = if use_align {
306 // Use the overall alignment
308 1 => attr::UnsignedInt(ast::TyU8),
309 2 => attr::UnsignedInt(ast::TyU16),
310 4 => attr::UnsignedInt(ast::TyU32),
311 8 if machine::llalign_of_min(cx, Type::i64(cx)) == 8 =>
312 attr::UnsignedInt(ast::TyU64),
313 _ => min_ity // use min_ity as a fallback
319 let fields : Vec<_> = cases.iter().map(|c| {
320 let mut ftys = vec!(ty_of_inttype(cx.tcx(), ity));
321 ftys.push_all(&c.tys[]);
322 if dtor { ftys.push(cx.tcx().types.bool); }
323 mk_struct(cx, &ftys[..], false, t)
326 ensure_enum_fits_in_address_space(cx, &fields[..], t);
328 General(ity, fields, dtor)
330 _ => cx.sess().bug(&format!("adt::represent_type called on non-ADT type: {}",
331 ty_to_string(cx.tcx(), t))[])
335 // this should probably all be in ty
341 /// This represents the (GEP) indices to follow to get to the discriminant field
342 pub type DiscrField = Vec<uint>;
344 fn find_discr_field_candidate<'tcx>(tcx: &ty::ctxt<'tcx>,
346 mut path: DiscrField) -> Option<DiscrField> {
348 // Fat &T/&mut T/Box<T> i.e. T is [T], str, or Trait
349 ty::ty_rptr(_, ty::mt { ty, .. }) | ty::ty_uniq(ty) if !type_is_sized(tcx, ty) => {
350 path.push(FAT_PTR_ADDR);
354 // Regular thin pointer: &T/&mut T/Box<T>
355 ty::ty_rptr(..) | ty::ty_uniq(..) => Some(path),
357 // Functions are just pointers
358 ty::ty_bare_fn(..) => Some(path),
360 // Is this the NonZero lang item wrapping a pointer or integer type?
361 ty::ty_struct(did, substs) if Some(did) == tcx.lang_items.non_zero() => {
362 let nonzero_fields = ty::lookup_struct_fields(tcx, did);
363 assert_eq!(nonzero_fields.len(), 1);
364 let nonzero_field = ty::lookup_field_type(tcx, did, nonzero_fields[0].id, substs);
365 match nonzero_field.sty {
366 ty::ty_ptr(..) | ty::ty_int(..) | ty::ty_uint(..) => {
374 // Perhaps one of the fields of this struct is non-zero
375 // let's recurse and find out
376 ty::ty_struct(def_id, substs) => {
377 let fields = ty::lookup_struct_fields(tcx, def_id);
378 for (j, field) in fields.iter().enumerate() {
379 let field_ty = ty::lookup_field_type(tcx, def_id, field.id, substs);
380 if let Some(mut fpath) = find_discr_field_candidate(tcx, field_ty, path.clone()) {
388 // Can we use one of the fields in this tuple?
389 ty::ty_tup(ref tys) => {
390 for (j, &ty) in tys.iter().enumerate() {
391 if let Some(mut fpath) = find_discr_field_candidate(tcx, ty, path.clone()) {
399 // Is this a fixed-size array of something non-zero
400 // with at least one element?
401 ty::ty_vec(ety, Some(d)) if d > 0 => {
402 if let Some(mut vpath) = find_discr_field_candidate(tcx, ety, path) {
410 // Anything else is not a pointer
415 impl<'tcx> Case<'tcx> {
416 fn is_zerolen<'a>(&self, cx: &CrateContext<'a, 'tcx>, scapegoat: Ty<'tcx>) -> bool {
417 mk_struct(cx, &self.tys[], false, scapegoat).size == 0
420 fn find_ptr<'a>(&self, cx: &CrateContext<'a, 'tcx>) -> Option<DiscrField> {
421 for (i, &ty) in self.tys.iter().enumerate() {
422 if let Some(mut path) = find_discr_field_candidate(cx.tcx(), ty, vec![]) {
431 fn get_cases<'tcx>(tcx: &ty::ctxt<'tcx>,
433 substs: &subst::Substs<'tcx>)
435 ty::enum_variants(tcx, def_id).iter().map(|vi| {
436 let arg_tys = vi.args.iter().map(|&raw_ty| {
437 monomorphize::apply_param_substs(tcx, substs, &raw_ty)
439 Case { discr: vi.disr_val, tys: arg_tys }
443 fn mk_struct<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
444 tys: &[Ty<'tcx>], packed: bool,
447 let sized = tys.iter().all(|&ty| type_is_sized(cx.tcx(), ty));
448 let lltys : Vec<Type> = if sized {
450 .map(|&ty| type_of::sizing_type_of(cx, ty)).collect()
452 tys.iter().filter(|&ty| type_is_sized(cx.tcx(), *ty))
453 .map(|&ty| type_of::sizing_type_of(cx, ty)).collect()
456 ensure_struct_fits_in_address_space(cx, &lltys[..], packed, scapegoat);
458 let llty_rec = Type::struct_(cx, &lltys[..], packed);
460 size: machine::llsize_of_alloc(cx, llty_rec),
461 align: machine::llalign_of_min(cx, llty_rec),
464 fields: tys.to_vec(),
476 fn mk_cenum<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
477 hint: Hint, bounds: &IntBounds)
479 let it = range_to_inttype(cx, hint, bounds);
481 attr::SignedInt(_) => CEnum(it, bounds.slo as Disr, bounds.shi as Disr),
482 attr::UnsignedInt(_) => CEnum(it, bounds.ulo, bounds.uhi)
486 fn range_to_inttype(cx: &CrateContext, hint: Hint, bounds: &IntBounds) -> IntType {
487 debug!("range_to_inttype: {:?} {:?}", hint, bounds);
488 // Lists of sizes to try. u64 is always allowed as a fallback.
489 #[allow(non_upper_case_globals)]
490 static choose_shortest: &'static[IntType] = &[
491 attr::UnsignedInt(ast::TyU8), attr::SignedInt(ast::TyI8),
492 attr::UnsignedInt(ast::TyU16), attr::SignedInt(ast::TyI16),
493 attr::UnsignedInt(ast::TyU32), attr::SignedInt(ast::TyI32)];
494 #[allow(non_upper_case_globals)]
495 static at_least_32: &'static[IntType] = &[
496 attr::UnsignedInt(ast::TyU32), attr::SignedInt(ast::TyI32)];
500 attr::ReprInt(span, ity) => {
501 if !bounds_usable(cx, ity, bounds) {
502 cx.sess().span_bug(span, "representation hint insufficient for discriminant range")
506 attr::ReprExtern => {
507 attempts = match &cx.sess().target.target.arch[] {
508 // WARNING: the ARM EABI has two variants; the one corresponding to `at_least_32`
509 // appears to be used on Linux and NetBSD, but some systems may use the variant
510 // corresponding to `choose_shortest`. However, we don't run on those yet...?
511 "arm" => at_least_32,
516 attempts = choose_shortest;
518 attr::ReprPacked => {
519 cx.tcx().sess.bug("range_to_inttype: found ReprPacked on an enum");
522 for &ity in attempts {
523 if bounds_usable(cx, ity, bounds) {
527 return attr::UnsignedInt(ast::TyU64);
530 pub fn ll_inttype(cx: &CrateContext, ity: IntType) -> Type {
532 attr::SignedInt(t) => Type::int_from_ty(cx, t),
533 attr::UnsignedInt(t) => Type::uint_from_ty(cx, t)
537 fn bounds_usable(cx: &CrateContext, ity: IntType, bounds: &IntBounds) -> bool {
538 debug!("bounds_usable: {:?} {:?}", ity, bounds);
540 attr::SignedInt(_) => {
541 let lllo = C_integral(ll_inttype(cx, ity), bounds.slo as u64, true);
542 let llhi = C_integral(ll_inttype(cx, ity), bounds.shi as u64, true);
543 bounds.slo == const_to_int(lllo) as i64 && bounds.shi == const_to_int(llhi) as i64
545 attr::UnsignedInt(_) => {
546 let lllo = C_integral(ll_inttype(cx, ity), bounds.ulo, false);
547 let llhi = C_integral(ll_inttype(cx, ity), bounds.uhi, false);
548 bounds.ulo == const_to_uint(lllo) as u64 && bounds.uhi == const_to_uint(llhi) as u64
553 pub fn ty_of_inttype<'tcx>(tcx: &ty::ctxt<'tcx>, ity: IntType) -> Ty<'tcx> {
555 attr::SignedInt(t) => ty::mk_mach_int(tcx, t),
556 attr::UnsignedInt(t) => ty::mk_mach_uint(tcx, t)
560 // LLVM doesn't like types that don't fit in the address space
561 fn ensure_struct_fits_in_address_space<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
564 scapegoat: Ty<'tcx>) {
566 for &llty in fields {
567 // Invariant: offset < ccx.obj_size_bound() <= 1<<61
569 let type_align = machine::llalign_of_min(ccx, llty);
570 offset = roundup(offset, type_align);
572 // type_align is a power-of-2, so still offset < ccx.obj_size_bound()
573 // llsize_of_alloc(ccx, llty) is also less than ccx.obj_size_bound()
574 // so the sum is less than 1<<62 (and therefore can't overflow).
575 offset += machine::llsize_of_alloc(ccx, llty);
577 if offset >= ccx.obj_size_bound() {
578 ccx.report_overbig_object(scapegoat);
583 fn union_size_and_align(sts: &[Struct]) -> (machine::llsize, machine::llalign) {
584 let size = sts.iter().map(|st| st.size).max().unwrap();
585 let align = sts.iter().map(|st| st.align).max().unwrap();
586 (roundup(size, align), align)
589 fn ensure_enum_fits_in_address_space<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
591 scapegoat: Ty<'tcx>) {
592 let (total_size, _) = union_size_and_align(fields);
594 if total_size >= ccx.obj_size_bound() {
595 ccx.report_overbig_object(scapegoat);
600 /// LLVM-level types are a little complicated.
602 /// C-like enums need to be actual ints, not wrapped in a struct,
603 /// because that changes the ABI on some platforms (see issue #10308).
605 /// For nominal types, in some cases, we need to use LLVM named structs
606 /// and fill in the actual contents in a second pass to prevent
607 /// unbounded recursion; see also the comments in `trans::type_of`.
608 pub fn type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, r: &Repr<'tcx>) -> Type {
609 generic_type_of(cx, r, None, false, false)
611 // Pass dst=true if the type you are passing is a DST. Yes, we could figure
612 // this out, but if you call this on an unsized type without realising it, you
613 // are going to get the wrong type (it will not include the unsized parts of it).
614 pub fn sizing_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
615 r: &Repr<'tcx>, dst: bool) -> Type {
616 generic_type_of(cx, r, None, true, dst)
618 pub fn incomplete_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
619 r: &Repr<'tcx>, name: &str) -> Type {
620 generic_type_of(cx, r, Some(name), false, false)
622 pub fn finish_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
623 r: &Repr<'tcx>, llty: &mut Type) {
625 CEnum(..) | General(..) | RawNullablePointer { .. } => { }
626 Univariant(ref st, _) | StructWrappedNullablePointer { nonnull: ref st, .. } =>
627 llty.set_struct_body(&struct_llfields(cx, st, false, false)[],
632 fn generic_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
638 CEnum(ity, _, _) => ll_inttype(cx, ity),
639 RawNullablePointer { nnty, .. } => type_of::sizing_type_of(cx, nnty),
640 Univariant(ref st, _) | StructWrappedNullablePointer { nonnull: ref st, .. } => {
643 Type::struct_(cx, &struct_llfields(cx, st, sizing, dst)[],
646 Some(name) => { assert_eq!(sizing, false); Type::named_struct(cx, name) }
649 General(ity, ref sts, _) => {
650 // We need a representation that has:
651 // * The alignment of the most-aligned field
652 // * The size of the largest variant (rounded up to that alignment)
653 // * No alignment padding anywhere any variant has actual data
654 // (currently matters only for enums small enough to be immediate)
655 // * The discriminant in an obvious place.
657 // So we start with the discriminant, pad it up to the alignment with
658 // more of its own type, then use alignment-sized ints to get the rest
661 // FIXME #10604: this breaks when vector types are present.
662 let (size, align) = union_size_and_align(&sts[..]);
663 let align_s = align as u64;
664 assert_eq!(size % align_s, 0);
665 let align_units = size / align_s - 1;
667 let discr_ty = ll_inttype(cx, ity);
668 let discr_size = machine::llsize_of_alloc(cx, discr_ty);
669 let fill_ty = match align_s {
670 1 => Type::array(&Type::i8(cx), align_units),
671 2 => Type::array(&Type::i16(cx), align_units),
672 4 => Type::array(&Type::i32(cx), align_units),
673 8 if machine::llalign_of_min(cx, Type::i64(cx)) == 8 =>
674 Type::array(&Type::i64(cx), align_units),
675 a if a.count_ones() == 1 => Type::array(&Type::vector(&Type::i32(cx), a / 4),
677 _ => panic!("unsupported enum alignment: {}", align)
679 assert_eq!(machine::llalign_of_min(cx, fill_ty), align);
680 assert_eq!(align_s % discr_size, 0);
681 let fields = [discr_ty,
682 Type::array(&discr_ty, align_s / discr_size - 1),
685 None => Type::struct_(cx, &fields[..], false),
687 let mut llty = Type::named_struct(cx, name);
688 llty.set_struct_body(&fields[..], false);
696 fn struct_llfields<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, st: &Struct<'tcx>,
697 sizing: bool, dst: bool) -> Vec<Type> {
699 st.fields.iter().filter(|&ty| !dst || type_is_sized(cx.tcx(), *ty))
700 .map(|&ty| type_of::sizing_type_of(cx, ty)).collect()
702 st.fields.iter().map(|&ty| type_of::type_of(cx, ty)).collect()
706 /// Obtain a representation of the discriminant sufficient to translate
707 /// destructuring; this may or may not involve the actual discriminant.
709 /// This should ideally be less tightly tied to `_match`.
710 pub fn trans_switch<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
711 r: &Repr<'tcx>, scrutinee: ValueRef)
712 -> (_match::BranchKind, Option<ValueRef>) {
714 CEnum(..) | General(..) |
715 RawNullablePointer { .. } | StructWrappedNullablePointer { .. } => {
716 (_match::Switch, Some(trans_get_discr(bcx, r, scrutinee, None)))
719 (_match::Single, None)
726 /// Obtain the actual discriminant of a value.
727 pub fn trans_get_discr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>,
728 scrutinee: ValueRef, cast_to: Option<Type>)
732 debug!("trans_get_discr r: {:?}", r);
734 CEnum(ity, min, max) => {
735 val = load_discr(bcx, ity, scrutinee, min, max);
736 signed = ity.is_signed();
738 General(ity, ref cases, _) => {
739 let ptr = GEPi(bcx, scrutinee, &[0, 0]);
740 val = load_discr(bcx, ity, ptr, 0, (cases.len() - 1) as Disr);
741 signed = ity.is_signed();
744 val = C_u8(bcx.ccx(), 0);
747 RawNullablePointer { nndiscr, nnty, .. } => {
748 let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
749 let llptrty = type_of::sizing_type_of(bcx.ccx(), nnty);
750 val = ICmp(bcx, cmp, Load(bcx, scrutinee), C_null(llptrty), DebugLoc::None);
753 StructWrappedNullablePointer { nndiscr, ref discrfield, .. } => {
754 val = struct_wrapped_nullable_bitdiscr(bcx, nndiscr, discrfield, scrutinee);
760 Some(llty) => if signed { SExt(bcx, val, llty) } else { ZExt(bcx, val, llty) }
764 fn struct_wrapped_nullable_bitdiscr(bcx: Block, nndiscr: Disr, discrfield: &DiscrField,
765 scrutinee: ValueRef) -> ValueRef {
766 let llptrptr = GEPi(bcx, scrutinee, &discrfield[..]);
767 let llptr = Load(bcx, llptrptr);
768 let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
769 ICmp(bcx, cmp, llptr, C_null(val_ty(llptr)), DebugLoc::None)
772 /// Helper for cases where the discriminant is simply loaded.
773 fn load_discr(bcx: Block, ity: IntType, ptr: ValueRef, min: Disr, max: Disr)
775 let llty = ll_inttype(bcx.ccx(), ity);
776 assert_eq!(val_ty(ptr), llty.ptr_to());
777 let bits = machine::llbitsize_of_real(bcx.ccx(), llty);
779 let bits = bits as uint;
780 let mask = (-1u64 >> (64 - bits)) as Disr;
781 if (max + 1) & mask == min & mask {
782 // i.e., if the range is everything. The lo==hi case would be
783 // rejected by the LLVM verifier (it would mean either an
784 // empty set, which is impossible, or the entire range of the
785 // type, which is pointless).
788 // llvm::ConstantRange can deal with ranges that wrap around,
789 // so an overflow on (max + 1) is fine.
790 LoadRangeAssert(bcx, ptr, min, (max+1), /* signed: */ True)
794 /// Yield information about how to dispatch a case of the
795 /// discriminant-like value returned by `trans_switch`.
797 /// This should ideally be less tightly tied to `_match`.
798 pub fn trans_case<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr, discr: Disr)
799 -> _match::OptResult<'blk, 'tcx> {
801 CEnum(ity, _, _) => {
802 _match::SingleResult(Result::new(bcx, C_integral(ll_inttype(bcx.ccx(), ity),
803 discr as u64, true)))
805 General(ity, _, _) => {
806 _match::SingleResult(Result::new(bcx, C_integral(ll_inttype(bcx.ccx(), ity),
807 discr as u64, true)))
810 bcx.ccx().sess().bug("no cases for univariants or structs")
812 RawNullablePointer { .. } |
813 StructWrappedNullablePointer { .. } => {
814 assert!(discr == 0 || discr == 1);
815 _match::SingleResult(Result::new(bcx, C_bool(bcx.ccx(), discr != 0)))
820 /// Set the discriminant for a new value of the given case of the given
822 pub fn trans_set_discr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>,
823 val: ValueRef, discr: Disr) {
825 CEnum(ity, min, max) => {
826 assert_discr_in_range(ity, min, max, discr);
827 Store(bcx, C_integral(ll_inttype(bcx.ccx(), ity), discr as u64, true),
830 General(ity, ref cases, dtor) => {
832 let ptr = trans_field_ptr(bcx, r, val, discr,
833 cases[discr as uint].fields.len() - 2);
834 Store(bcx, C_u8(bcx.ccx(), 1), ptr);
836 Store(bcx, C_integral(ll_inttype(bcx.ccx(), ity), discr as u64, true),
837 GEPi(bcx, val, &[0, 0]))
839 Univariant(ref st, dtor) => {
840 assert_eq!(discr, 0);
842 Store(bcx, C_u8(bcx.ccx(), 1),
843 GEPi(bcx, val, &[0, st.fields.len() - 1]));
846 RawNullablePointer { nndiscr, nnty, ..} => {
847 if discr != nndiscr {
848 let llptrty = type_of::sizing_type_of(bcx.ccx(), nnty);
849 Store(bcx, C_null(llptrty), val)
852 StructWrappedNullablePointer { nndiscr, ref discrfield, .. } => {
853 if discr != nndiscr {
854 let llptrptr = GEPi(bcx, val, &discrfield[..]);
855 let llptrty = val_ty(llptrptr).element_type();
856 Store(bcx, C_null(llptrty), llptrptr)
862 fn assert_discr_in_range(ity: IntType, min: Disr, max: Disr, discr: Disr) {
864 attr::UnsignedInt(_) => assert!(min <= discr && discr <= max),
865 attr::SignedInt(_) => assert!(min as i64 <= discr as i64 && discr as i64 <= max as i64)
869 /// The number of fields in a given case; for use when obtaining this
870 /// information from the type or definition is less convenient.
871 pub fn num_args(r: &Repr, discr: Disr) -> uint {
874 Univariant(ref st, dtor) => {
875 assert_eq!(discr, 0);
876 st.fields.len() - (if dtor { 1 } else { 0 })
878 General(_, ref cases, dtor) => {
879 cases[discr as uint].fields.len() - 1 - (if dtor { 1 } else { 0 })
881 RawNullablePointer { nndiscr, ref nullfields, .. } => {
882 if discr == nndiscr { 1 } else { nullfields.len() }
884 StructWrappedNullablePointer { ref nonnull, nndiscr,
885 ref nullfields, .. } => {
886 if discr == nndiscr { nonnull.fields.len() } else { nullfields.len() }
891 /// Access a field, at a point when the value's case is known.
892 pub fn trans_field_ptr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>,
893 val: ValueRef, discr: Disr, ix: uint) -> ValueRef {
894 // Note: if this ever needs to generate conditionals (e.g., if we
895 // decide to do some kind of cdr-coding-like non-unique repr
896 // someday), it will need to return a possibly-new bcx as well.
899 bcx.ccx().sess().bug("element access in C-like enum")
901 Univariant(ref st, _dtor) => {
902 assert_eq!(discr, 0);
903 struct_field_ptr(bcx, st, val, ix, false)
905 General(_, ref cases, _) => {
906 struct_field_ptr(bcx, &cases[discr as uint], val, ix + 1, true)
908 RawNullablePointer { nndiscr, ref nullfields, .. } |
909 StructWrappedNullablePointer { nndiscr, ref nullfields, .. } if discr != nndiscr => {
910 // The unit-like case might have a nonzero number of unit-like fields.
911 // (e.d., Result of Either with (), as one side.)
912 let ty = type_of::type_of(bcx.ccx(), nullfields[ix]);
913 assert_eq!(machine::llsize_of_alloc(bcx.ccx(), ty), 0);
914 // The contents of memory at this pointer can't matter, but use
915 // the value that's "reasonable" in case of pointer comparison.
916 PointerCast(bcx, val, ty.ptr_to())
918 RawNullablePointer { nndiscr, nnty, .. } => {
920 assert_eq!(discr, nndiscr);
921 let ty = type_of::type_of(bcx.ccx(), nnty);
922 PointerCast(bcx, val, ty.ptr_to())
924 StructWrappedNullablePointer { ref nonnull, nndiscr, .. } => {
925 assert_eq!(discr, nndiscr);
926 struct_field_ptr(bcx, nonnull, val, ix, false)
931 pub fn struct_field_ptr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, st: &Struct<'tcx>, val: ValueRef,
932 ix: uint, needs_cast: bool) -> ValueRef {
933 let val = if needs_cast {
935 let fields = st.fields.iter().map(|&ty| type_of::type_of(ccx, ty)).collect::<Vec<_>>();
936 let real_ty = Type::struct_(ccx, &fields[..], st.packed);
937 PointerCast(bcx, val, real_ty.ptr_to())
942 GEPi(bcx, val, &[0, ix])
945 pub fn fold_variants<'blk, 'tcx, F>(bcx: Block<'blk, 'tcx>,
949 -> Block<'blk, 'tcx> where
950 F: FnMut(Block<'blk, 'tcx>, &Struct<'tcx>, ValueRef) -> Block<'blk, 'tcx>,
954 Univariant(ref st, _) => {
957 General(ity, ref cases, _) => {
959 let unr_cx = fcx.new_temp_block("enum-variant-iter-unr");
962 let discr_val = trans_get_discr(bcx, r, value, None);
963 let llswitch = Switch(bcx, discr_val, unr_cx.llbb, cases.len());
964 let bcx_next = fcx.new_temp_block("enum-variant-iter-next");
966 for (discr, case) in cases.iter().enumerate() {
967 let mut variant_cx = fcx.new_temp_block(
968 &format!("enum-variant-iter-{}", &discr.to_string())[]
970 let rhs_val = C_integral(ll_inttype(ccx, ity), discr as u64, true);
971 AddCase(llswitch, rhs_val, variant_cx.llbb);
973 let fields = case.fields.iter().map(|&ty|
974 type_of::type_of(bcx.ccx(), ty)).collect::<Vec<_>>();
975 let real_ty = Type::struct_(ccx, &fields[..], case.packed);
976 let variant_value = PointerCast(variant_cx, value, real_ty.ptr_to());
978 variant_cx = f(variant_cx, case, variant_value);
979 Br(variant_cx, bcx_next.llbb, DebugLoc::None);
988 /// Access the struct drop flag, if present.
989 pub fn trans_drop_flag_ptr<'blk, 'tcx>(mut bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>, val: ValueRef)
990 -> datum::DatumBlock<'blk, 'tcx, datum::Expr>
993 let ptr_ty = ty::mk_imm_ptr(bcx.tcx(), tcx.types.bool);
995 Univariant(ref st, true) => {
996 let flag_ptr = GEPi(bcx, val, &[0, st.fields.len() - 1]);
997 datum::immediate_rvalue_bcx(bcx, flag_ptr, ptr_ty).to_expr_datumblock()
999 General(_, _, true) => {
1001 let custom_cleanup_scope = fcx.push_custom_cleanup_scope();
1002 let scratch = unpack_datum!(bcx, datum::lvalue_scratch_datum(
1003 bcx, tcx.types.bool, "drop_flag", false,
1004 cleanup::CustomScope(custom_cleanup_scope), (), |_, bcx, _| bcx
1006 bcx = fold_variants(bcx, r, val, |variant_cx, st, value| {
1007 let ptr = struct_field_ptr(variant_cx, st, value, (st.fields.len() - 1), false);
1008 datum::Datum::new(ptr, ptr_ty, datum::Rvalue::new(datum::ByRef))
1009 .store_to(variant_cx, scratch.val)
1011 let expr_datum = scratch.to_expr_datum();
1012 fcx.pop_custom_cleanup_scope(custom_cleanup_scope);
1013 datum::DatumBlock::new(bcx, expr_datum)
1015 _ => bcx.ccx().sess().bug("tried to get drop flag of non-droppable type")
1019 /// Construct a constant value, suitable for initializing a
1020 /// GlobalVariable, given a case and constant values for its fields.
1021 /// Note that this may have a different LLVM type (and different
1022 /// alignment!) from the representation's `type_of`, so it needs a
1023 /// pointer cast before use.
1025 /// The LLVM type system does not directly support unions, and only
1026 /// pointers can be bitcast, so a constant (and, by extension, the
1027 /// GlobalVariable initialized by it) will have a type that can vary
1028 /// depending on which case of an enum it is.
1030 /// To understand the alignment situation, consider `enum E { V64(u64),
1031 /// V32(u32, u32) }` on Windows. The type has 8-byte alignment to
1032 /// accommodate the u64, but `V32(x, y)` would have LLVM type `{i32,
1033 /// i32, i32}`, which is 4-byte aligned.
1035 /// Currently the returned value has the same size as the type, but
1036 /// this could be changed in the future to avoid allocating unnecessary
1037 /// space after values of shorter-than-maximum cases.
1038 pub fn trans_const<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, r: &Repr<'tcx>, discr: Disr,
1039 vals: &[ValueRef]) -> ValueRef {
1041 CEnum(ity, min, max) => {
1042 assert_eq!(vals.len(), 0);
1043 assert_discr_in_range(ity, min, max, discr);
1044 C_integral(ll_inttype(ccx, ity), discr as u64, true)
1046 General(ity, ref cases, _) => {
1047 let case = &cases[discr as uint];
1048 let (max_sz, _) = union_size_and_align(&cases[..]);
1049 let lldiscr = C_integral(ll_inttype(ccx, ity), discr as u64, true);
1050 let mut f = vec![lldiscr];
1052 let mut contents = build_const_struct(ccx, case, &f[..]);
1053 contents.push_all(&[padding(ccx, max_sz - case.size)]);
1054 C_struct(ccx, &contents[..], false)
1056 Univariant(ref st, _dro) => {
1057 assert!(discr == 0);
1058 let contents = build_const_struct(ccx, st, vals);
1059 C_struct(ccx, &contents[..], st.packed)
1061 RawNullablePointer { nndiscr, nnty, .. } => {
1062 if discr == nndiscr {
1063 assert_eq!(vals.len(), 1);
1066 C_null(type_of::sizing_type_of(ccx, nnty))
1069 StructWrappedNullablePointer { ref nonnull, nndiscr, .. } => {
1070 if discr == nndiscr {
1071 C_struct(ccx, &build_const_struct(ccx,
1076 let vals = nonnull.fields.iter().map(|&ty| {
1077 // Always use null even if it's not the `discrfield`th
1078 // field; see #8506.
1079 C_null(type_of::sizing_type_of(ccx, ty))
1080 }).collect::<Vec<ValueRef>>();
1081 C_struct(ccx, &build_const_struct(ccx,
1090 /// Compute struct field offsets relative to struct begin.
1091 fn compute_struct_field_offsets<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
1092 st: &Struct<'tcx>) -> Vec<u64> {
1093 let mut offsets = vec!();
1096 for &ty in &st.fields {
1097 let llty = type_of::sizing_type_of(ccx, ty);
1099 let type_align = type_of::align_of(ccx, ty);
1100 offset = roundup(offset, type_align);
1102 offsets.push(offset);
1103 offset += machine::llsize_of_alloc(ccx, llty);
1105 assert_eq!(st.fields.len(), offsets.len());
1109 /// Building structs is a little complicated, because we might need to
1110 /// insert padding if a field's value is less aligned than its type.
1112 /// Continuing the example from `trans_const`, a value of type `(u32,
1113 /// E)` should have the `E` at offset 8, but if that field's
1114 /// initializer is 4-byte aligned then simply translating the tuple as
1115 /// a two-element struct will locate it at offset 4, and accesses to it
1116 /// will read the wrong memory.
1117 fn build_const_struct<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
1118 st: &Struct<'tcx>, vals: &[ValueRef])
1120 assert_eq!(vals.len(), st.fields.len());
1122 let target_offsets = compute_struct_field_offsets(ccx, st);
1124 // offset of current value
1126 let mut cfields = Vec::new();
1127 for (&val, &target_offset) in vals.iter().zip(target_offsets.iter()) {
1129 let val_align = machine::llalign_of_min(ccx, val_ty(val));
1130 offset = roundup(offset, val_align);
1132 if offset != target_offset {
1133 cfields.push(padding(ccx, target_offset - offset));
1134 offset = target_offset;
1136 assert!(!is_undef(val));
1138 offset += machine::llsize_of_alloc(ccx, val_ty(val));
1141 assert!(st.sized && offset <= st.size);
1142 if offset != st.size {
1143 cfields.push(padding(ccx, st.size - offset));
1149 fn padding(ccx: &CrateContext, size: u64) -> ValueRef {
1150 C_undef(Type::array(&Type::i8(ccx), size))
1153 // FIXME this utility routine should be somewhere more general
1155 fn roundup(x: u64, a: u32) -> u64 { let a = a as u64; ((x + (a - 1)) / a) * a }
1157 /// Get the discriminant of a constant value.
1158 pub fn const_get_discrim(ccx: &CrateContext, r: &Repr, val: ValueRef) -> Disr {
1160 CEnum(ity, _, _) => {
1162 attr::SignedInt(..) => const_to_int(val) as Disr,
1163 attr::UnsignedInt(..) => const_to_uint(val) as Disr
1166 General(ity, _, _) => {
1168 attr::SignedInt(..) => const_to_int(const_get_elt(ccx, val, &[0])) as Disr,
1169 attr::UnsignedInt(..) => const_to_uint(const_get_elt(ccx, val, &[0])) as Disr
1172 Univariant(..) => 0,
1173 RawNullablePointer { .. } | StructWrappedNullablePointer { .. } => {
1174 ccx.sess().bug("const discrim access of non c-like enum")
1179 /// Extract a field of a constant value, as appropriate for its
1182 /// (Not to be confused with `common::const_get_elt`, which operates on
1183 /// raw LLVM-level structs and arrays.)
1184 pub fn const_get_field(ccx: &CrateContext, r: &Repr, val: ValueRef,
1185 _discr: Disr, ix: uint) -> ValueRef {
1187 CEnum(..) => ccx.sess().bug("element access in C-like enum const"),
1188 Univariant(..) => const_struct_field(ccx, val, ix),
1189 General(..) => const_struct_field(ccx, val, ix + 1),
1190 RawNullablePointer { .. } => {
1194 StructWrappedNullablePointer{ .. } => const_struct_field(ccx, val, ix)
1198 /// Extract field of struct-like const, skipping our alignment padding.
1199 fn const_struct_field(ccx: &CrateContext, val: ValueRef, ix: uint) -> ValueRef {
1200 // Get the ix-th non-undef element of the struct.
1201 let mut real_ix = 0; // actual position in the struct
1202 let mut ix = ix; // logical index relative to real_ix
1206 field = const_get_elt(ccx, val, &[real_ix]);
1207 if !is_undef(field) {
1210 real_ix = real_ix + 1;
1216 real_ix = real_ix + 1;