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::PointerField::*;
47 pub use self::Repr::*;
52 use llvm::{ValueRef, True, IntEQ, IntNE};
55 use middle::subst::Subst;
59 use trans::cleanup::CleanupMethods;
63 use trans::type_::Type;
65 use middle::ty::{mod, Ty};
69 use syntax::attr::IntType;
70 use util::ppaux::ty_to_string;
72 type Hint = attr::ReprAttr;
76 #[deriving(Eq, PartialEq, Show)]
78 /// C-like enums; basically an int.
79 CEnum(IntType, Disr, Disr), // discriminant range (signedness based on the IntType)
81 * Single-case variants, and structs/tuples/records.
83 * Structs with destructors need a dynamic destroyedness flag to
84 * avoid running the destructor too many times; this is included
85 * in the `Struct` if present.
87 Univariant(Struct<'tcx>, bool),
89 * General-case enums: for each case there is a struct, and they
90 * all start with a field for the discriminant.
92 * Types with destructors need a dynamic destroyedness flag to
93 * avoid running the destructor too many times; the last argument
94 * indicates whether such a flag is present.
96 General(IntType, Vec<Struct<'tcx>>, bool),
98 * Two cases distinguished by a nullable pointer: the case with discriminant
99 * `nndiscr` must have single field which is known to be nonnull due to its type.
100 * The other case is known to be zero sized. Hence we represent the enum
101 * as simply a nullable pointer: if not null it indicates the `nndiscr` variant,
102 * otherwise it indicates the other case.
107 nullfields: Vec<Ty<'tcx>>
110 * Two cases distinguished by a nullable pointer: the case with discriminant
111 * `nndiscr` is represented by the struct `nonnull`, where the `ptrfield`th
112 * field is known to be nonnull due to its type; if that field is null, then
113 * it represents the other case, which is inhabited by at most one value
114 * (and all other fields are undefined/unused).
116 * For example, `std::option::Option` instantiated at a safe pointer type
117 * is represented such that `None` is a null pointer and `Some` is the
120 StructWrappedNullablePointer {
121 nonnull: Struct<'tcx>,
123 ptrfield: PointerField,
124 nullfields: Vec<Ty<'tcx>>,
128 /// For structs, and struct-like parts of anything fancier.
129 #[deriving(Eq, PartialEq, Show)]
130 pub struct Struct<'tcx> {
131 // If the struct is DST, then the size and alignment do not take into
132 // account the unsized fields of the struct.
137 pub fields: Vec<Ty<'tcx>>
141 * Convenience for `represent_type`. There should probably be more or
142 * these, for places in trans where the `Ty` isn't directly
145 pub fn represent_node<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
146 node: ast::NodeId) -> Rc<Repr<'tcx>> {
147 represent_type(bcx.ccx(), node_id_type(bcx, node))
150 /// Decides how to represent a given type.
151 pub fn represent_type<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
152 t: Ty<'tcx>) -> Rc<Repr<'tcx>> {
153 debug!("Representing: {}", ty_to_string(cx.tcx(), t));
154 match cx.adt_reprs().borrow().get(&t) {
155 Some(repr) => return repr.clone(),
159 let repr = Rc::new(represent_type_uncached(cx, t));
160 debug!("Represented as: {}", repr)
161 cx.adt_reprs().borrow_mut().insert(t, repr.clone());
165 fn represent_type_uncached<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
166 t: Ty<'tcx>) -> Repr<'tcx> {
168 ty::ty_tup(ref elems) => {
169 Univariant(mk_struct(cx, elems.as_slice(), false, t), false)
171 ty::ty_struct(def_id, ref substs) => {
172 let fields = ty::lookup_struct_fields(cx.tcx(), def_id);
173 let mut ftys = fields.iter().map(|field| {
174 ty::lookup_field_type(cx.tcx(), def_id, field.id, substs)
175 }).collect::<Vec<_>>();
176 let packed = ty::lookup_packed(cx.tcx(), def_id);
177 let dtor = ty::ty_dtor(cx.tcx(), def_id).has_drop_flag();
178 if dtor { ftys.push(ty::mk_bool()); }
180 Univariant(mk_struct(cx, ftys.as_slice(), packed, t), dtor)
182 ty::ty_unboxed_closure(def_id, _, ref substs) => {
183 let upvars = ty::unboxed_closure_upvars(cx.tcx(), def_id, substs);
184 let upvar_types = upvars.iter().map(|u| u.ty).collect::<Vec<_>>();
185 Univariant(mk_struct(cx, upvar_types.as_slice(), false, t), false)
187 ty::ty_enum(def_id, ref substs) => {
188 let cases = get_cases(cx.tcx(), def_id, substs);
189 let hint = *ty::lookup_repr_hints(cx.tcx(), def_id).as_slice().get(0)
190 .unwrap_or(&attr::ReprAny);
192 let dtor = ty::ty_dtor(cx.tcx(), def_id).has_drop_flag();
194 if cases.len() == 0 {
195 // Uninhabitable; represent as unit
196 // (Typechecking will reject discriminant-sizing attrs.)
197 assert_eq!(hint, attr::ReprAny);
198 let ftys = if dtor { vec!(ty::mk_bool()) } else { vec!() };
199 return Univariant(mk_struct(cx, ftys.as_slice(), false, t),
203 if !dtor && cases.iter().all(|c| c.tys.len() == 0) {
204 // All bodies empty -> intlike
205 let discrs: Vec<u64> = cases.iter().map(|c| c.discr).collect();
206 let bounds = IntBounds {
207 ulo: *discrs.iter().min().unwrap(),
208 uhi: *discrs.iter().max().unwrap(),
209 slo: discrs.iter().map(|n| *n as i64).min().unwrap(),
210 shi: discrs.iter().map(|n| *n as i64).max().unwrap()
212 return mk_cenum(cx, hint, &bounds);
215 // Since there's at least one
216 // non-empty body, explicit discriminants should have
217 // been rejected by a checker before this point.
218 if !cases.iter().enumerate().all(|(i,c)| c.discr == (i as Disr)) {
219 cx.sess().bug(format!("non-C-like enum {} with specified \
221 ty::item_path_str(cx.tcx(),
222 def_id)).as_slice());
225 if cases.len() == 1 {
226 // Equivalent to a struct/tuple/newtype.
227 // (Typechecking will reject discriminant-sizing attrs.)
228 assert_eq!(hint, attr::ReprAny);
229 let mut ftys = cases[0].tys.clone();
230 if dtor { ftys.push(ty::mk_bool()); }
231 return Univariant(mk_struct(cx, ftys.as_slice(), false, t),
235 if !dtor && cases.len() == 2 && hint == attr::ReprAny {
236 // Nullable pointer optimization
239 if cases[1 - discr].is_zerolen(cx, t) {
240 let st = mk_struct(cx, cases[discr].tys.as_slice(),
242 match cases[discr].find_ptr(cx) {
243 Some(ThinPointer(_)) if st.fields.len() == 1 => {
244 return RawNullablePointer {
245 nndiscr: discr as Disr,
247 nullfields: cases[1 - discr].tys.clone()
251 return StructWrappedNullablePointer {
252 nndiscr: discr as Disr,
255 nullfields: cases[1 - discr].tys.clone()
266 assert!((cases.len() - 1) as i64 >= 0);
267 let bounds = IntBounds { ulo: 0, uhi: (cases.len() - 1) as u64,
268 slo: 0, shi: (cases.len() - 1) as i64 };
269 let ity = range_to_inttype(cx, hint, &bounds);
271 let fields : Vec<_> = cases.iter().map(|c| {
272 let mut ftys = vec!(ty_of_inttype(ity));
273 ftys.push_all(c.tys.as_slice());
274 if dtor { ftys.push(ty::mk_bool()); }
275 mk_struct(cx, ftys.as_slice(), false, t)
278 ensure_enum_fits_in_address_space(cx, ity, fields.as_slice(), t);
280 General(ity, fields, dtor)
282 _ => cx.sess().bug(format!("adt::represent_type called on non-ADT type: {}",
283 ty_to_string(cx.tcx(), t)).as_slice())
287 // this should probably all be in ty
294 #[deriving(Eq, PartialEq, Show)]
295 pub enum PointerField {
300 impl<'tcx> Case<'tcx> {
301 fn is_zerolen<'a>(&self, cx: &CrateContext<'a, 'tcx>, scapegoat: Ty<'tcx>) -> bool {
302 mk_struct(cx, self.tys.as_slice(), false, scapegoat).size == 0
305 fn find_ptr<'a>(&self, cx: &CrateContext<'a, 'tcx>) -> Option<PointerField> {
306 for (i, &ty) in self.tys.iter().enumerate() {
308 // &T/&mut T/Box<T> could either be a thin or fat pointer depending on T
309 ty::ty_rptr(_, ty::mt { ty, .. }) | ty::ty_uniq(ty) => match ty.sty {
310 // &[T] and &str are a pointer and length pair
311 ty::ty_vec(_, None) | ty::ty_str => return Some(FatPointer(i)),
313 // &Trait is a pair of pointers: the actual object and a vtable
314 ty::ty_trait(..) => return Some(FatPointer(i)),
316 ty::ty_struct(..) if !ty::type_is_sized(cx.tcx(), ty) => {
317 return Some(FatPointer(i))
320 // Any other &T is just a pointer
321 _ => return Some(ThinPointer(i))
324 // Functions are just pointers
325 ty::ty_bare_fn(..) => return Some(ThinPointer(i)),
327 // Closures are a pair of pointers: the code and environment
328 ty::ty_closure(..) => return Some(FatPointer(i)),
330 // Anything else is not a pointer
339 fn get_cases<'tcx>(tcx: &ty::ctxt<'tcx>,
341 substs: &subst::Substs<'tcx>)
343 ty::enum_variants(tcx, def_id).iter().map(|vi| {
344 let arg_tys = vi.args.iter().map(|&raw_ty| {
345 raw_ty.subst(tcx, substs)
347 Case { discr: vi.disr_val, tys: arg_tys }
351 fn mk_struct<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
352 tys: &[Ty<'tcx>], packed: bool,
355 let sized = tys.iter().all(|&ty| ty::type_is_sized(cx.tcx(), ty));
356 let lltys : Vec<Type> = if sized {
358 .map(|&ty| type_of::sizing_type_of(cx, ty)).collect()
360 tys.iter().filter(|&ty| ty::type_is_sized(cx.tcx(), *ty))
361 .map(|&ty| type_of::sizing_type_of(cx, ty)).collect()
364 ensure_struct_fits_in_address_space(cx, lltys.as_slice(), packed, scapegoat);
366 let llty_rec = Type::struct_(cx, lltys.as_slice(), packed);
368 size: machine::llsize_of_alloc(cx, llty_rec),
369 align: machine::llalign_of_min(cx, llty_rec),
372 fields: tys.to_vec(),
384 fn mk_cenum<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
385 hint: Hint, bounds: &IntBounds)
387 let it = range_to_inttype(cx, hint, bounds);
389 attr::SignedInt(_) => CEnum(it, bounds.slo as Disr, bounds.shi as Disr),
390 attr::UnsignedInt(_) => CEnum(it, bounds.ulo, bounds.uhi)
394 fn range_to_inttype(cx: &CrateContext, hint: Hint, bounds: &IntBounds) -> IntType {
395 debug!("range_to_inttype: {} {}", hint, bounds);
396 // Lists of sizes to try. u64 is always allowed as a fallback.
397 #[allow(non_upper_case_globals)]
398 static choose_shortest: &'static[IntType] = &[
399 attr::UnsignedInt(ast::TyU8), attr::SignedInt(ast::TyI8),
400 attr::UnsignedInt(ast::TyU16), attr::SignedInt(ast::TyI16),
401 attr::UnsignedInt(ast::TyU32), attr::SignedInt(ast::TyI32)];
402 #[allow(non_upper_case_globals)]
403 static at_least_32: &'static[IntType] = &[
404 attr::UnsignedInt(ast::TyU32), attr::SignedInt(ast::TyI32)];
408 attr::ReprInt(span, ity) => {
409 if !bounds_usable(cx, ity, bounds) {
410 cx.sess().span_bug(span, "representation hint insufficient for discriminant range")
414 attr::ReprExtern => {
415 attempts = match cx.sess().target.target.arch.as_slice() {
416 // WARNING: the ARM EABI has two variants; the one corresponding to `at_least_32`
417 // appears to be used on Linux and NetBSD, but some systems may use the variant
418 // corresponding to `choose_shortest`. However, we don't run on those yet...?
419 "arm" => at_least_32,
424 attempts = choose_shortest;
426 attr::ReprPacked => {
427 cx.tcx().sess.bug("range_to_inttype: found ReprPacked on an enum");
430 for &ity in attempts.iter() {
431 if bounds_usable(cx, ity, bounds) {
435 return attr::UnsignedInt(ast::TyU64);
438 pub fn ll_inttype(cx: &CrateContext, ity: IntType) -> Type {
440 attr::SignedInt(t) => Type::int_from_ty(cx, t),
441 attr::UnsignedInt(t) => Type::uint_from_ty(cx, t)
445 fn bounds_usable(cx: &CrateContext, ity: IntType, bounds: &IntBounds) -> bool {
446 debug!("bounds_usable: {} {}", ity, bounds);
448 attr::SignedInt(_) => {
449 let lllo = C_integral(ll_inttype(cx, ity), bounds.slo as u64, true);
450 let llhi = C_integral(ll_inttype(cx, ity), bounds.shi as u64, true);
451 bounds.slo == const_to_int(lllo) as i64 && bounds.shi == const_to_int(llhi) as i64
453 attr::UnsignedInt(_) => {
454 let lllo = C_integral(ll_inttype(cx, ity), bounds.ulo, false);
455 let llhi = C_integral(ll_inttype(cx, ity), bounds.uhi, false);
456 bounds.ulo == const_to_uint(lllo) as u64 && bounds.uhi == const_to_uint(llhi) as u64
461 // FIXME(#17596) Ty<'tcx> is incorrectly invariant w.r.t 'tcx.
462 pub fn ty_of_inttype<'tcx>(ity: IntType) -> Ty<'tcx> {
464 attr::SignedInt(t) => ty::mk_mach_int(t),
465 attr::UnsignedInt(t) => ty::mk_mach_uint(t)
469 // LLVM doesn't like types that don't fit in the address space
470 fn ensure_struct_fits_in_address_space<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
473 scapegoat: Ty<'tcx>) {
475 for &llty in fields.iter() {
476 // Invariant: offset < ccx.obj_size_bound() <= 1<<61
478 let type_align = machine::llalign_of_min(ccx, llty);
479 offset = roundup(offset, type_align);
481 // type_align is a power-of-2, so still offset < ccx.obj_size_bound()
482 // llsize_of_alloc(ccx, llty) is also less than ccx.obj_size_bound()
483 // so the sum is less than 1<<62 (and therefore can't overflow).
484 offset += machine::llsize_of_alloc(ccx, llty);
486 if offset >= ccx.obj_size_bound() {
487 ccx.report_overbig_object(scapegoat);
492 fn union_size_and_align(sts: &[Struct]) -> (machine::llsize, machine::llalign) {
493 let size = sts.iter().map(|st| st.size).max().unwrap();
494 let most_aligned = sts.iter().max_by(|st| st.align).unwrap();
495 (size, most_aligned.align)
498 fn ensure_enum_fits_in_address_space<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
501 scapegoat: Ty<'tcx>) {
502 let discr_size = machine::llsize_of_alloc(ccx, ll_inttype(ccx, discr));
503 let (field_size, field_align) = union_size_and_align(fields);
505 // field_align < 1<<32, discr_size <= 8, field_size < OBJ_SIZE_BOUND <= 1<<61
506 // so the sum is less than 1<<62 (and can't overflow).
507 let total_size = roundup(discr_size, field_align) + field_size;
509 if total_size >= ccx.obj_size_bound() {
510 ccx.report_overbig_object(scapegoat);
516 * LLVM-level types are a little complicated.
518 * C-like enums need to be actual ints, not wrapped in a struct,
519 * because that changes the ABI on some platforms (see issue #10308).
521 * For nominal types, in some cases, we need to use LLVM named structs
522 * and fill in the actual contents in a second pass to prevent
523 * unbounded recursion; see also the comments in `trans::type_of`.
525 pub fn type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, r: &Repr<'tcx>) -> Type {
526 generic_type_of(cx, r, None, false, false)
528 // Pass dst=true if the type you are passing is a DST. Yes, we could figure
529 // this out, but if you call this on an unsized type without realising it, you
530 // are going to get the wrong type (it will not include the unsized parts of it).
531 pub fn sizing_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
532 r: &Repr<'tcx>, dst: bool) -> Type {
533 generic_type_of(cx, r, None, true, dst)
535 pub fn incomplete_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
536 r: &Repr<'tcx>, name: &str) -> Type {
537 generic_type_of(cx, r, Some(name), false, false)
539 pub fn finish_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
540 r: &Repr<'tcx>, llty: &mut Type) {
542 CEnum(..) | General(..) | RawNullablePointer { .. } => { }
543 Univariant(ref st, _) | StructWrappedNullablePointer { nonnull: ref st, .. } =>
544 llty.set_struct_body(struct_llfields(cx, st, false, false).as_slice(),
549 fn generic_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
555 CEnum(ity, _, _) => ll_inttype(cx, ity),
556 RawNullablePointer { nnty, .. } => type_of::sizing_type_of(cx, nnty),
557 Univariant(ref st, _) | StructWrappedNullablePointer { nonnull: ref st, .. } => {
560 Type::struct_(cx, struct_llfields(cx, st, sizing, dst).as_slice(),
563 Some(name) => { assert_eq!(sizing, false); Type::named_struct(cx, name) }
566 General(ity, ref sts, _) => {
567 // We need a representation that has:
568 // * The alignment of the most-aligned field
569 // * The size of the largest variant (rounded up to that alignment)
570 // * No alignment padding anywhere any variant has actual data
571 // (currently matters only for enums small enough to be immediate)
572 // * The discriminant in an obvious place.
574 // So we start with the discriminant, pad it up to the alignment with
575 // more of its own type, then use alignment-sized ints to get the rest
578 // FIXME #10604: this breaks when vector types are present.
579 let (size, align) = union_size_and_align(sts.as_slice());
580 let align_s = align as u64;
581 let discr_ty = ll_inttype(cx, ity);
582 let discr_size = machine::llsize_of_alloc(cx, discr_ty);
583 let align_units = (size + align_s - 1) / align_s - 1;
584 let pad_ty = match align_s {
585 1 => Type::array(&Type::i8(cx), align_units),
586 2 => Type::array(&Type::i16(cx), align_units),
587 4 => Type::array(&Type::i32(cx), align_units),
588 8 if machine::llalign_of_min(cx, Type::i64(cx)) == 8 =>
589 Type::array(&Type::i64(cx), align_units),
590 a if a.count_ones() == 1 => Type::array(&Type::vector(&Type::i32(cx), a / 4),
592 _ => panic!("unsupported enum alignment: {}", align)
594 assert_eq!(machine::llalign_of_min(cx, pad_ty), align);
595 assert_eq!(align_s % discr_size, 0);
596 let fields = vec!(discr_ty,
597 Type::array(&discr_ty, align_s / discr_size - 1),
600 None => Type::struct_(cx, fields.as_slice(), false),
602 let mut llty = Type::named_struct(cx, name);
603 llty.set_struct_body(fields.as_slice(), false);
611 fn struct_llfields<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, st: &Struct<'tcx>,
612 sizing: bool, dst: bool) -> Vec<Type> {
614 st.fields.iter().filter(|&ty| !dst || ty::type_is_sized(cx.tcx(), *ty))
615 .map(|&ty| type_of::sizing_type_of(cx, ty)).collect()
617 st.fields.iter().map(|&ty| type_of::type_of(cx, ty)).collect()
622 * Obtain a representation of the discriminant sufficient to translate
623 * destructuring; this may or may not involve the actual discriminant.
625 * This should ideally be less tightly tied to `_match`.
627 pub fn trans_switch<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
628 r: &Repr<'tcx>, scrutinee: ValueRef)
629 -> (_match::BranchKind, Option<ValueRef>) {
631 CEnum(..) | General(..) |
632 RawNullablePointer { .. } | StructWrappedNullablePointer { .. } => {
633 (_match::Switch, Some(trans_get_discr(bcx, r, scrutinee, None)))
636 (_match::Single, None)
643 /// Obtain the actual discriminant of a value.
644 pub fn trans_get_discr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>,
645 scrutinee: ValueRef, cast_to: Option<Type>)
649 debug!("trans_get_discr r: {}", r);
651 CEnum(ity, min, max) => {
652 val = load_discr(bcx, ity, scrutinee, min, max);
653 signed = ity.is_signed();
655 General(ity, ref cases, _) => {
656 let ptr = GEPi(bcx, scrutinee, &[0, 0]);
657 val = load_discr(bcx, ity, ptr, 0, (cases.len() - 1) as Disr);
658 signed = ity.is_signed();
661 val = C_u8(bcx.ccx(), 0);
664 RawNullablePointer { nndiscr, nnty, .. } => {
665 let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
666 let llptrty = type_of::sizing_type_of(bcx.ccx(), nnty);
667 val = ICmp(bcx, cmp, Load(bcx, scrutinee), C_null(llptrty));
670 StructWrappedNullablePointer { nndiscr, ptrfield, .. } => {
671 val = struct_wrapped_nullable_bitdiscr(bcx, nndiscr, ptrfield, scrutinee);
677 Some(llty) => if signed { SExt(bcx, val, llty) } else { ZExt(bcx, val, llty) }
681 fn struct_wrapped_nullable_bitdiscr(bcx: Block, nndiscr: Disr, ptrfield: PointerField,
682 scrutinee: ValueRef) -> ValueRef {
683 let llptrptr = match ptrfield {
684 ThinPointer(field) => GEPi(bcx, scrutinee, &[0, field]),
685 FatPointer(field) => GEPi(bcx, scrutinee, &[0, field, abi::FAT_PTR_ADDR])
687 let llptr = Load(bcx, llptrptr);
688 let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
689 ICmp(bcx, cmp, llptr, C_null(val_ty(llptr)))
692 /// Helper for cases where the discriminant is simply loaded.
693 fn load_discr(bcx: Block, ity: IntType, ptr: ValueRef, min: Disr, max: Disr)
695 let llty = ll_inttype(bcx.ccx(), ity);
696 assert_eq!(val_ty(ptr), llty.ptr_to());
697 let bits = machine::llbitsize_of_real(bcx.ccx(), llty);
699 let bits = bits as uint;
700 let mask = (-1u64 >> (64 - bits)) as Disr;
701 if (max + 1) & mask == min & mask {
702 // i.e., if the range is everything. The lo==hi case would be
703 // rejected by the LLVM verifier (it would mean either an
704 // empty set, which is impossible, or the entire range of the
705 // type, which is pointless).
708 // llvm::ConstantRange can deal with ranges that wrap around,
709 // so an overflow on (max + 1) is fine.
710 LoadRangeAssert(bcx, ptr, min, (max+1), /* signed: */ True)
715 * Yield information about how to dispatch a case of the
716 * discriminant-like value returned by `trans_switch`.
718 * This should ideally be less tightly tied to `_match`.
720 pub fn trans_case<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr, discr: Disr)
721 -> _match::OptResult<'blk, 'tcx> {
723 CEnum(ity, _, _) => {
724 _match::SingleResult(Result::new(bcx, C_integral(ll_inttype(bcx.ccx(), ity),
725 discr as u64, true)))
727 General(ity, _, _) => {
728 _match::SingleResult(Result::new(bcx, C_integral(ll_inttype(bcx.ccx(), ity),
729 discr as u64, true)))
732 bcx.ccx().sess().bug("no cases for univariants or structs")
734 RawNullablePointer { .. } |
735 StructWrappedNullablePointer { .. } => {
736 assert!(discr == 0 || discr == 1);
737 _match::SingleResult(Result::new(bcx, C_bool(bcx.ccx(), discr != 0)))
743 * Set the discriminant for a new value of the given case of the given
746 pub fn trans_set_discr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>,
747 val: ValueRef, discr: Disr) {
749 CEnum(ity, min, max) => {
750 assert_discr_in_range(ity, min, max, discr);
751 Store(bcx, C_integral(ll_inttype(bcx.ccx(), ity), discr as u64, true),
754 General(ity, ref cases, dtor) => {
756 let ptr = trans_field_ptr(bcx, r, val, discr,
757 cases[discr as uint].fields.len() - 2);
758 Store(bcx, C_u8(bcx.ccx(), 1), ptr);
760 Store(bcx, C_integral(ll_inttype(bcx.ccx(), ity), discr as u64, true),
761 GEPi(bcx, val, &[0, 0]))
763 Univariant(ref st, dtor) => {
764 assert_eq!(discr, 0);
766 Store(bcx, C_u8(bcx.ccx(), 1),
767 GEPi(bcx, val, &[0, st.fields.len() - 1]));
770 RawNullablePointer { nndiscr, nnty, ..} => {
771 if discr != nndiscr {
772 let llptrty = type_of::sizing_type_of(bcx.ccx(), nnty);
773 Store(bcx, C_null(llptrty), val)
776 StructWrappedNullablePointer { ref nonnull, nndiscr, ptrfield, .. } => {
777 if discr != nndiscr {
778 let (llptrptr, llptrty) = match ptrfield {
779 ThinPointer(field) =>
780 (GEPi(bcx, val, &[0, field]),
781 type_of::type_of(bcx.ccx(), nonnull.fields[field])),
782 FatPointer(field) => {
783 let v = GEPi(bcx, val, &[0, field, abi::FAT_PTR_ADDR]);
784 (v, val_ty(v).element_type())
787 Store(bcx, C_null(llptrty), llptrptr)
793 fn assert_discr_in_range(ity: IntType, min: Disr, max: Disr, discr: Disr) {
795 attr::UnsignedInt(_) => assert!(min <= discr && discr <= max),
796 attr::SignedInt(_) => assert!(min as i64 <= discr as i64 && discr as i64 <= max as i64)
801 * The number of fields in a given case; for use when obtaining this
802 * information from the type or definition is less convenient.
804 pub fn num_args(r: &Repr, discr: Disr) -> uint {
807 Univariant(ref st, dtor) => {
808 assert_eq!(discr, 0);
809 st.fields.len() - (if dtor { 1 } else { 0 })
811 General(_, ref cases, dtor) => {
812 cases[discr as uint].fields.len() - 1 - (if dtor { 1 } else { 0 })
814 RawNullablePointer { nndiscr, ref nullfields, .. } => {
815 if discr == nndiscr { 1 } else { nullfields.len() }
817 StructWrappedNullablePointer { ref nonnull, nndiscr,
818 ref nullfields, .. } => {
819 if discr == nndiscr { nonnull.fields.len() } else { nullfields.len() }
824 /// Access a field, at a point when the value's case is known.
825 pub fn trans_field_ptr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>,
826 val: ValueRef, discr: Disr, ix: uint) -> ValueRef {
827 // Note: if this ever needs to generate conditionals (e.g., if we
828 // decide to do some kind of cdr-coding-like non-unique repr
829 // someday), it will need to return a possibly-new bcx as well.
832 bcx.ccx().sess().bug("element access in C-like enum")
834 Univariant(ref st, _dtor) => {
835 assert_eq!(discr, 0);
836 struct_field_ptr(bcx, st, val, ix, false)
838 General(_, ref cases, _) => {
839 struct_field_ptr(bcx, &cases[discr as uint], val, ix + 1, true)
841 RawNullablePointer { nndiscr, ref nullfields, .. } |
842 StructWrappedNullablePointer { nndiscr, ref nullfields, .. } if discr != nndiscr => {
843 // The unit-like case might have a nonzero number of unit-like fields.
844 // (e.d., Result of Either with (), as one side.)
845 let ty = type_of::type_of(bcx.ccx(), nullfields[ix]);
846 assert_eq!(machine::llsize_of_alloc(bcx.ccx(), ty), 0);
847 // The contents of memory at this pointer can't matter, but use
848 // the value that's "reasonable" in case of pointer comparison.
849 PointerCast(bcx, val, ty.ptr_to())
851 RawNullablePointer { nndiscr, nnty, .. } => {
853 assert_eq!(discr, nndiscr);
854 let ty = type_of::type_of(bcx.ccx(), nnty);
855 PointerCast(bcx, val, ty.ptr_to())
857 StructWrappedNullablePointer { ref nonnull, nndiscr, .. } => {
858 assert_eq!(discr, nndiscr);
859 struct_field_ptr(bcx, nonnull, val, ix, false)
864 pub fn struct_field_ptr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, st: &Struct<'tcx>, val: ValueRef,
865 ix: uint, needs_cast: bool) -> ValueRef {
866 let val = if needs_cast {
868 let fields = st.fields.iter().map(|&ty| type_of::type_of(ccx, ty)).collect::<Vec<_>>();
869 let real_ty = Type::struct_(ccx, fields.as_slice(), st.packed);
870 PointerCast(bcx, val, real_ty.ptr_to())
875 GEPi(bcx, val, &[0, ix])
878 pub fn fold_variants<'blk, 'tcx>(
879 bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>, value: ValueRef,
880 f: |Block<'blk, 'tcx>, &Struct<'tcx>, ValueRef| -> Block<'blk, 'tcx>)
881 -> Block<'blk, 'tcx> {
884 Univariant(ref st, _) => {
887 General(ity, ref cases, _) => {
889 let unr_cx = fcx.new_temp_block("enum-variant-iter-unr");
892 let discr_val = trans_get_discr(bcx, r, value, None);
893 let llswitch = Switch(bcx, discr_val, unr_cx.llbb, cases.len());
894 let bcx_next = fcx.new_temp_block("enum-variant-iter-next");
896 for (discr, case) in cases.iter().enumerate() {
897 let mut variant_cx = fcx.new_temp_block(
898 format!("enum-variant-iter-{}", discr.to_string()).as_slice()
900 let rhs_val = C_integral(ll_inttype(ccx, ity), discr as u64, true);
901 AddCase(llswitch, rhs_val, variant_cx.llbb);
903 let fields = case.fields.iter().map(|&ty|
904 type_of::type_of(bcx.ccx(), ty)).collect::<Vec<_>>();
905 let real_ty = Type::struct_(ccx, fields.as_slice(), case.packed);
906 let variant_value = PointerCast(variant_cx, value, real_ty.ptr_to());
908 variant_cx = f(variant_cx, case, variant_value);
909 Br(variant_cx, bcx_next.llbb);
918 /// Access the struct drop flag, if present.
919 pub fn trans_drop_flag_ptr<'blk, 'tcx>(mut bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>, val: ValueRef)
920 -> datum::DatumBlock<'blk, 'tcx, datum::Expr> {
921 let ptr_ty = ty::mk_imm_ptr(bcx.tcx(), ty::mk_bool());
923 Univariant(ref st, true) => {
924 let flag_ptr = GEPi(bcx, val, &[0, st.fields.len() - 1]);
925 datum::immediate_rvalue_bcx(bcx, flag_ptr, ptr_ty).to_expr_datumblock()
927 General(_, _, true) => {
929 let custom_cleanup_scope = fcx.push_custom_cleanup_scope();
930 let scratch = unpack_datum!(bcx, datum::lvalue_scratch_datum(
931 bcx, ty::mk_bool(), "drop_flag", false,
932 cleanup::CustomScope(custom_cleanup_scope), (), |_, bcx, _| bcx
934 bcx = fold_variants(bcx, r, val, |variant_cx, st, value| {
935 let ptr = struct_field_ptr(variant_cx, st, value, (st.fields.len() - 1), false);
936 datum::Datum::new(ptr, ptr_ty, datum::Rvalue::new(datum::ByRef))
937 .store_to(variant_cx, scratch.val)
939 let expr_datum = scratch.to_expr_datum();
940 fcx.pop_custom_cleanup_scope(custom_cleanup_scope);
941 datum::DatumBlock::new(bcx, expr_datum)
943 _ => bcx.ccx().sess().bug("tried to get drop flag of non-droppable type")
948 * Construct a constant value, suitable for initializing a
949 * GlobalVariable, given a case and constant values for its fields.
950 * Note that this may have a different LLVM type (and different
951 * alignment!) from the representation's `type_of`, so it needs a
952 * pointer cast before use.
954 * The LLVM type system does not directly support unions, and only
955 * pointers can be bitcast, so a constant (and, by extension, the
956 * GlobalVariable initialized by it) will have a type that can vary
957 * depending on which case of an enum it is.
959 * To understand the alignment situation, consider `enum E { V64(u64),
960 * V32(u32, u32) }` on Windows. The type has 8-byte alignment to
961 * accommodate the u64, but `V32(x, y)` would have LLVM type `{i32,
962 * i32, i32}`, which is 4-byte aligned.
964 * Currently the returned value has the same size as the type, but
965 * this could be changed in the future to avoid allocating unnecessary
966 * space after values of shorter-than-maximum cases.
968 pub fn trans_const<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, r: &Repr<'tcx>, discr: Disr,
969 vals: &[ValueRef]) -> ValueRef {
971 CEnum(ity, min, max) => {
972 assert_eq!(vals.len(), 0);
973 assert_discr_in_range(ity, min, max, discr);
974 C_integral(ll_inttype(ccx, ity), discr as u64, true)
976 General(ity, ref cases, _) => {
977 let case = &cases[discr as uint];
978 let max_sz = cases.iter().map(|x| x.size).max().unwrap();
979 let lldiscr = C_integral(ll_inttype(ccx, ity), discr as u64, true);
980 let mut f = vec![lldiscr];
982 let mut contents = build_const_struct(ccx, case, f.as_slice());
983 contents.push_all(&[padding(ccx, max_sz - case.size)]);
984 C_struct(ccx, contents.as_slice(), false)
986 Univariant(ref st, _dro) => {
988 let contents = build_const_struct(ccx, st, vals);
989 C_struct(ccx, contents.as_slice(), st.packed)
991 RawNullablePointer { nndiscr, nnty, .. } => {
992 if discr == nndiscr {
993 assert_eq!(vals.len(), 1);
996 C_null(type_of::sizing_type_of(ccx, nnty))
999 StructWrappedNullablePointer { ref nonnull, nndiscr, .. } => {
1000 if discr == nndiscr {
1001 C_struct(ccx, build_const_struct(ccx,
1006 let vals = nonnull.fields.iter().map(|&ty| {
1007 // Always use null even if it's not the `ptrfield`th
1008 // field; see #8506.
1009 C_null(type_of::sizing_type_of(ccx, ty))
1010 }).collect::<Vec<ValueRef>>();
1011 C_struct(ccx, build_const_struct(ccx,
1013 vals.as_slice()).as_slice(),
1021 * Compute struct field offsets relative to struct begin.
1023 fn compute_struct_field_offsets<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
1024 st: &Struct<'tcx>) -> Vec<u64> {
1025 let mut offsets = vec!();
1028 for &ty in st.fields.iter() {
1029 let llty = type_of::sizing_type_of(ccx, ty);
1031 let type_align = type_of::align_of(ccx, ty);
1032 offset = roundup(offset, type_align);
1034 offsets.push(offset);
1035 offset += machine::llsize_of_alloc(ccx, llty);
1037 assert_eq!(st.fields.len(), offsets.len());
1042 * Building structs is a little complicated, because we might need to
1043 * insert padding if a field's value is less aligned than its type.
1045 * Continuing the example from `trans_const`, a value of type `(u32,
1046 * E)` should have the `E` at offset 8, but if that field's
1047 * initializer is 4-byte aligned then simply translating the tuple as
1048 * a two-element struct will locate it at offset 4, and accesses to it
1049 * will read the wrong memory.
1051 fn build_const_struct<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
1052 st: &Struct<'tcx>, vals: &[ValueRef])
1054 assert_eq!(vals.len(), st.fields.len());
1056 let target_offsets = compute_struct_field_offsets(ccx, st);
1058 // offset of current value
1060 let mut cfields = Vec::new();
1061 for (&val, &target_offset) in vals.iter().zip(target_offsets.iter()) {
1063 let val_align = machine::llalign_of_min(ccx, val_ty(val));
1064 offset = roundup(offset, val_align);
1066 if offset != target_offset {
1067 cfields.push(padding(ccx, target_offset - offset));
1068 offset = target_offset;
1070 assert!(!is_undef(val));
1072 offset += machine::llsize_of_alloc(ccx, val_ty(val));
1075 assert!(st.sized && offset <= st.size);
1076 if offset != st.size {
1077 cfields.push(padding(ccx, st.size - offset));
1083 fn padding(ccx: &CrateContext, size: u64) -> ValueRef {
1084 C_undef(Type::array(&Type::i8(ccx), size))
1087 // FIXME this utility routine should be somewhere more general
1089 fn roundup(x: u64, a: u32) -> u64 { let a = a as u64; ((x + (a - 1)) / a) * a }
1091 /// Get the discriminant of a constant value. (Not currently used.)
1092 pub fn const_get_discrim(ccx: &CrateContext, r: &Repr, val: ValueRef)
1095 CEnum(ity, _, _) => {
1097 attr::SignedInt(..) => const_to_int(val) as Disr,
1098 attr::UnsignedInt(..) => const_to_uint(val) as Disr
1101 General(ity, _, _) => {
1103 attr::SignedInt(..) => const_to_int(const_get_elt(ccx, val, &[0])) as Disr,
1104 attr::UnsignedInt(..) => const_to_uint(const_get_elt(ccx, val, &[0])) as Disr
1107 Univariant(..) => 0,
1108 RawNullablePointer { nndiscr, .. } => {
1110 /* subtraction as uint is ok because nndiscr is either 0 or 1 */
1111 (1 - nndiscr) as Disr
1116 StructWrappedNullablePointer { nndiscr, ptrfield, .. } => {
1117 let (idx, sub_idx) = match ptrfield {
1118 ThinPointer(field) => (field, None),
1119 FatPointer(field) => (field, Some(abi::FAT_PTR_ADDR))
1121 if is_null(const_struct_field(ccx, val, idx, sub_idx)) {
1122 /* subtraction as uint is ok because nndiscr is either 0 or 1 */
1123 (1 - nndiscr) as Disr
1132 * Extract a field of a constant value, as appropriate for its
1135 * (Not to be confused with `common::const_get_elt`, which operates on
1136 * raw LLVM-level structs and arrays.)
1138 pub fn const_get_field(ccx: &CrateContext, r: &Repr, val: ValueRef,
1139 _discr: Disr, ix: uint) -> ValueRef {
1141 CEnum(..) => ccx.sess().bug("element access in C-like enum const"),
1142 Univariant(..) => const_struct_field(ccx, val, ix, None),
1143 General(..) => const_struct_field(ccx, val, ix + 1, None),
1144 RawNullablePointer { .. } => {
1148 StructWrappedNullablePointer{ .. } => const_struct_field(ccx, val, ix, None)
1152 /// Extract field of struct-like const, skipping our alignment padding.
1153 fn const_struct_field(ccx: &CrateContext, val: ValueRef, ix: uint, sub_idx: Option<uint>)
1155 // Get the ix-th non-undef element of the struct.
1156 let mut real_ix = 0; // actual position in the struct
1157 let mut ix = ix; // logical index relative to real_ix
1161 field = match sub_idx {
1162 Some(si) => const_get_elt(ccx, val, &[real_ix, si as u32]),
1163 None => const_get_elt(ccx, val, &[real_ix])
1165 if !is_undef(field) {
1168 real_ix = real_ix + 1;
1174 real_ix = real_ix + 1;