| use rustc_hir as hir; |
| use rustc_index::bit_set::BitSet; |
| use rustc_index::vec::{Idx, IndexVec}; |
| use rustc_middle::mir::{GeneratorLayout, GeneratorSavedLocal}; |
| use rustc_middle::ty::layout::{ |
| IntegerExt, LayoutCx, LayoutError, LayoutOf, TyAndLayout, MAX_SIMD_LANES, |
| }; |
| use rustc_middle::ty::{ |
| self, subst::SubstsRef, EarlyBinder, ReprOptions, Ty, TyCtxt, TypeVisitable, |
| }; |
| use rustc_session::{DataTypeKind, FieldInfo, SizeKind, VariantInfo}; |
| use rustc_span::symbol::Symbol; |
| use rustc_span::DUMMY_SP; |
| use rustc_target::abi::*; |
| |
| use std::cmp::{self, Ordering}; |
| use std::iter; |
| use std::num::NonZeroUsize; |
| use std::ops::Bound; |
| |
| use rand::{seq::SliceRandom, SeedableRng}; |
| use rand_xoshiro::Xoshiro128StarStar; |
| |
| use crate::layout_sanity_check::sanity_check_layout; |
| |
| pub fn provide(providers: &mut ty::query::Providers) { |
| *providers = ty::query::Providers { layout_of, ..*providers }; |
| } |
| |
| #[instrument(skip(tcx, query), level = "debug")] |
| fn layout_of<'tcx>( |
| tcx: TyCtxt<'tcx>, |
| query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>, |
| ) -> Result<TyAndLayout<'tcx>, LayoutError<'tcx>> { |
| let (param_env, ty) = query.into_parts(); |
| debug!(?ty); |
| |
| let param_env = param_env.with_reveal_all_normalized(tcx); |
| let unnormalized_ty = ty; |
| |
| // FIXME: We might want to have two different versions of `layout_of`: |
| // One that can be called after typecheck has completed and can use |
| // `normalize_erasing_regions` here and another one that can be called |
| // before typecheck has completed and uses `try_normalize_erasing_regions`. |
| let ty = match tcx.try_normalize_erasing_regions(param_env, ty) { |
| Ok(t) => t, |
| Err(normalization_error) => { |
| return Err(LayoutError::NormalizationFailure(ty, normalization_error)); |
| } |
| }; |
| |
| if ty != unnormalized_ty { |
| // Ensure this layout is also cached for the normalized type. |
| return tcx.layout_of(param_env.and(ty)); |
| } |
| |
| let cx = LayoutCx { tcx, param_env }; |
| |
| let layout = layout_of_uncached(&cx, ty)?; |
| let layout = TyAndLayout { ty, layout }; |
| |
| record_layout_for_printing(&cx, layout); |
| |
| sanity_check_layout(&cx, &layout); |
| |
| Ok(layout) |
| } |
| |
| #[derive(Copy, Clone, Debug)] |
| enum StructKind { |
| /// A tuple, closure, or univariant which cannot be coerced to unsized. |
| AlwaysSized, |
| /// A univariant, the last field of which may be coerced to unsized. |
| MaybeUnsized, |
| /// A univariant, but with a prefix of an arbitrary size & alignment (e.g., enum tag). |
| Prefixed(Size, Align), |
| } |
| |
| // Invert a bijective mapping, i.e. `invert(map)[y] = x` if `map[x] = y`. |
| // This is used to go between `memory_index` (source field order to memory order) |
| // and `inverse_memory_index` (memory order to source field order). |
| // See also `FieldsShape::Arbitrary::memory_index` for more details. |
| // FIXME(eddyb) build a better abstraction for permutations, if possible. |
| fn invert_mapping(map: &[u32]) -> Vec<u32> { |
| let mut inverse = vec![0; map.len()]; |
| for i in 0..map.len() { |
| inverse[map[i] as usize] = i as u32; |
| } |
| inverse |
| } |
| |
| fn scalar_pair<'tcx>(cx: &LayoutCx<'tcx, TyCtxt<'tcx>>, a: Scalar, b: Scalar) -> LayoutS<'tcx> { |
| let dl = cx.data_layout(); |
| let b_align = b.align(dl); |
| let align = a.align(dl).max(b_align).max(dl.aggregate_align); |
| let b_offset = a.size(dl).align_to(b_align.abi); |
| let size = (b_offset + b.size(dl)).align_to(align.abi); |
| |
| // HACK(nox): We iter on `b` and then `a` because `max_by_key` |
| // returns the last maximum. |
| let largest_niche = Niche::from_scalar(dl, b_offset, b) |
| .into_iter() |
| .chain(Niche::from_scalar(dl, Size::ZERO, a)) |
| .max_by_key(|niche| niche.available(dl)); |
| |
| LayoutS { |
| variants: Variants::Single { index: VariantIdx::new(0) }, |
| fields: FieldsShape::Arbitrary { |
| offsets: vec![Size::ZERO, b_offset], |
| memory_index: vec![0, 1], |
| }, |
| abi: Abi::ScalarPair(a, b), |
| largest_niche, |
| align, |
| size, |
| } |
| } |
| |
| fn univariant_uninterned<'tcx>( |
| cx: &LayoutCx<'tcx, TyCtxt<'tcx>>, |
| ty: Ty<'tcx>, |
| fields: &[TyAndLayout<'_>], |
| repr: &ReprOptions, |
| kind: StructKind, |
| ) -> Result<LayoutS<'tcx>, LayoutError<'tcx>> { |
| let dl = cx.data_layout(); |
| let pack = repr.pack; |
| if pack.is_some() && repr.align.is_some() { |
| cx.tcx.sess.delay_span_bug(DUMMY_SP, "struct cannot be packed and aligned"); |
| return Err(LayoutError::Unknown(ty)); |
| } |
| |
| let mut align = if pack.is_some() { dl.i8_align } else { dl.aggregate_align }; |
| |
| let mut inverse_memory_index: Vec<u32> = (0..fields.len() as u32).collect(); |
| |
| let optimize = !repr.inhibit_struct_field_reordering_opt(); |
| if optimize { |
| let end = if let StructKind::MaybeUnsized = kind { fields.len() - 1 } else { fields.len() }; |
| let optimizing = &mut inverse_memory_index[..end]; |
| let field_align = |f: &TyAndLayout<'_>| { |
| if let Some(pack) = pack { f.align.abi.min(pack) } else { f.align.abi } |
| }; |
| |
| // If `-Z randomize-layout` was enabled for the type definition we can shuffle |
| // the field ordering to try and catch some code making assumptions about layouts |
| // we don't guarantee |
| if repr.can_randomize_type_layout() { |
| // `ReprOptions.layout_seed` is a deterministic seed that we can use to |
| // randomize field ordering with |
| let mut rng = Xoshiro128StarStar::seed_from_u64(repr.field_shuffle_seed); |
| |
| // Shuffle the ordering of the fields |
| optimizing.shuffle(&mut rng); |
| |
| // Otherwise we just leave things alone and actually optimize the type's fields |
| } else { |
| match kind { |
| StructKind::AlwaysSized | StructKind::MaybeUnsized => { |
| optimizing.sort_by_key(|&x| { |
| // Place ZSTs first to avoid "interesting offsets", |
| // especially with only one or two non-ZST fields. |
| let f = &fields[x as usize]; |
| (!f.is_zst(), cmp::Reverse(field_align(f))) |
| }); |
| } |
| |
| StructKind::Prefixed(..) => { |
| // Sort in ascending alignment so that the layout stays optimal |
| // regardless of the prefix |
| optimizing.sort_by_key(|&x| field_align(&fields[x as usize])); |
| } |
| } |
| |
| // FIXME(Kixiron): We can always shuffle fields within a given alignment class |
| // regardless of the status of `-Z randomize-layout` |
| } |
| } |
| |
| // inverse_memory_index holds field indices by increasing memory offset. |
| // That is, if field 5 has offset 0, the first element of inverse_memory_index is 5. |
| // We now write field offsets to the corresponding offset slot; |
| // field 5 with offset 0 puts 0 in offsets[5]. |
| // At the bottom of this function, we invert `inverse_memory_index` to |
| // produce `memory_index` (see `invert_mapping`). |
| |
| let mut sized = true; |
| let mut offsets = vec![Size::ZERO; fields.len()]; |
| let mut offset = Size::ZERO; |
| let mut largest_niche = None; |
| let mut largest_niche_available = 0; |
| |
| if let StructKind::Prefixed(prefix_size, prefix_align) = kind { |
| let prefix_align = |
| if let Some(pack) = pack { prefix_align.min(pack) } else { prefix_align }; |
| align = align.max(AbiAndPrefAlign::new(prefix_align)); |
| offset = prefix_size.align_to(prefix_align); |
| } |
| |
| for &i in &inverse_memory_index { |
| let field = fields[i as usize]; |
| if !sized { |
| cx.tcx.sess.delay_span_bug( |
| DUMMY_SP, |
| &format!( |
| "univariant: field #{} of `{}` comes after unsized field", |
| offsets.len(), |
| ty |
| ), |
| ); |
| } |
| |
| if field.is_unsized() { |
| sized = false; |
| } |
| |
| // Invariant: offset < dl.obj_size_bound() <= 1<<61 |
| let field_align = if let Some(pack) = pack { |
| field.align.min(AbiAndPrefAlign::new(pack)) |
| } else { |
| field.align |
| }; |
| offset = offset.align_to(field_align.abi); |
| align = align.max(field_align); |
| |
| debug!("univariant offset: {:?} field: {:#?}", offset, field); |
| offsets[i as usize] = offset; |
| |
| if let Some(mut niche) = field.largest_niche { |
| let available = niche.available(dl); |
| if available > largest_niche_available { |
| largest_niche_available = available; |
| niche.offset += offset; |
| largest_niche = Some(niche); |
| } |
| } |
| |
| offset = offset.checked_add(field.size, dl).ok_or(LayoutError::SizeOverflow(ty))?; |
| } |
| |
| if let Some(repr_align) = repr.align { |
| align = align.max(AbiAndPrefAlign::new(repr_align)); |
| } |
| |
| debug!("univariant min_size: {:?}", offset); |
| let min_size = offset; |
| |
| // As stated above, inverse_memory_index holds field indices by increasing offset. |
| // This makes it an already-sorted view of the offsets vec. |
| // To invert it, consider: |
| // If field 5 has offset 0, offsets[0] is 5, and memory_index[5] should be 0. |
| // Field 5 would be the first element, so memory_index is i: |
| // Note: if we didn't optimize, it's already right. |
| |
| let memory_index = |
| if optimize { invert_mapping(&inverse_memory_index) } else { inverse_memory_index }; |
| |
| let size = min_size.align_to(align.abi); |
| let mut abi = Abi::Aggregate { sized }; |
| |
| // Unpack newtype ABIs and find scalar pairs. |
| if sized && size.bytes() > 0 { |
| // All other fields must be ZSTs. |
| let mut non_zst_fields = fields.iter().enumerate().filter(|&(_, f)| !f.is_zst()); |
| |
| match (non_zst_fields.next(), non_zst_fields.next(), non_zst_fields.next()) { |
| // We have exactly one non-ZST field. |
| (Some((i, field)), None, None) => { |
| // Field fills the struct and it has a scalar or scalar pair ABI. |
| if offsets[i].bytes() == 0 && align.abi == field.align.abi && size == field.size { |
| match field.abi { |
| // For plain scalars, or vectors of them, we can't unpack |
| // newtypes for `#[repr(C)]`, as that affects C ABIs. |
| Abi::Scalar(_) | Abi::Vector { .. } if optimize => { |
| abi = field.abi; |
| } |
| // But scalar pairs are Rust-specific and get |
| // treated as aggregates by C ABIs anyway. |
| Abi::ScalarPair(..) => { |
| abi = field.abi; |
| } |
| _ => {} |
| } |
| } |
| } |
| |
| // Two non-ZST fields, and they're both scalars. |
| (Some((i, a)), Some((j, b)), None) => { |
| match (a.abi, b.abi) { |
| (Abi::Scalar(a), Abi::Scalar(b)) => { |
| // Order by the memory placement, not source order. |
| let ((i, a), (j, b)) = if offsets[i] < offsets[j] { |
| ((i, a), (j, b)) |
| } else { |
| ((j, b), (i, a)) |
| }; |
| let pair = scalar_pair(cx, a, b); |
| let pair_offsets = match pair.fields { |
| FieldsShape::Arbitrary { ref offsets, ref memory_index } => { |
| assert_eq!(memory_index, &[0, 1]); |
| offsets |
| } |
| _ => bug!(), |
| }; |
| if offsets[i] == pair_offsets[0] |
| && offsets[j] == pair_offsets[1] |
| && align == pair.align |
| && size == pair.size |
| { |
| // We can use `ScalarPair` only when it matches our |
| // already computed layout (including `#[repr(C)]`). |
| abi = pair.abi; |
| } |
| } |
| _ => {} |
| } |
| } |
| |
| _ => {} |
| } |
| } |
| |
| if fields.iter().any(|f| f.abi.is_uninhabited()) { |
| abi = Abi::Uninhabited; |
| } |
| |
| Ok(LayoutS { |
| variants: Variants::Single { index: VariantIdx::new(0) }, |
| fields: FieldsShape::Arbitrary { offsets, memory_index }, |
| abi, |
| largest_niche, |
| align, |
| size, |
| }) |
| } |
| |
| fn layout_of_uncached<'tcx>( |
| cx: &LayoutCx<'tcx, TyCtxt<'tcx>>, |
| ty: Ty<'tcx>, |
| ) -> Result<Layout<'tcx>, LayoutError<'tcx>> { |
| let tcx = cx.tcx; |
| let param_env = cx.param_env; |
| let dl = cx.data_layout(); |
| let scalar_unit = |value: Primitive| { |
| let size = value.size(dl); |
| assert!(size.bits() <= 128); |
| Scalar::Initialized { value, valid_range: WrappingRange::full(size) } |
| }; |
| let scalar = |value: Primitive| tcx.intern_layout(LayoutS::scalar(cx, scalar_unit(value))); |
| |
| let univariant = |fields: &[TyAndLayout<'_>], repr: &ReprOptions, kind| { |
| Ok(tcx.intern_layout(univariant_uninterned(cx, ty, fields, repr, kind)?)) |
| }; |
| debug_assert!(!ty.has_non_region_infer()); |
| |
| Ok(match *ty.kind() { |
| // Basic scalars. |
| ty::Bool => tcx.intern_layout(LayoutS::scalar( |
| cx, |
| Scalar::Initialized { |
| value: Int(I8, false), |
| valid_range: WrappingRange { start: 0, end: 1 }, |
| }, |
| )), |
| ty::Char => tcx.intern_layout(LayoutS::scalar( |
| cx, |
| Scalar::Initialized { |
| value: Int(I32, false), |
| valid_range: WrappingRange { start: 0, end: 0x10FFFF }, |
| }, |
| )), |
| ty::Int(ity) => scalar(Int(Integer::from_int_ty(dl, ity), true)), |
| ty::Uint(ity) => scalar(Int(Integer::from_uint_ty(dl, ity), false)), |
| ty::Float(fty) => scalar(match fty { |
| ty::FloatTy::F32 => F32, |
| ty::FloatTy::F64 => F64, |
| }), |
| ty::FnPtr(_) => { |
| let mut ptr = scalar_unit(Pointer); |
| ptr.valid_range_mut().start = 1; |
| tcx.intern_layout(LayoutS::scalar(cx, ptr)) |
| } |
| |
| // The never type. |
| ty::Never => tcx.intern_layout(LayoutS { |
| variants: Variants::Single { index: VariantIdx::new(0) }, |
| fields: FieldsShape::Primitive, |
| abi: Abi::Uninhabited, |
| largest_niche: None, |
| align: dl.i8_align, |
| size: Size::ZERO, |
| }), |
| |
| // Potentially-wide pointers. |
| ty::Ref(_, pointee, _) | ty::RawPtr(ty::TypeAndMut { ty: pointee, .. }) => { |
| let mut data_ptr = scalar_unit(Pointer); |
| if !ty.is_unsafe_ptr() { |
| data_ptr.valid_range_mut().start = 1; |
| } |
| |
| let pointee = tcx.normalize_erasing_regions(param_env, pointee); |
| if pointee.is_sized(tcx, param_env) { |
| return Ok(tcx.intern_layout(LayoutS::scalar(cx, data_ptr))); |
| } |
| |
| let unsized_part = tcx.struct_tail_erasing_lifetimes(pointee, param_env); |
| let metadata = match unsized_part.kind() { |
| ty::Foreign(..) => { |
| return Ok(tcx.intern_layout(LayoutS::scalar(cx, data_ptr))); |
| } |
| ty::Slice(_) | ty::Str => scalar_unit(Int(dl.ptr_sized_integer(), false)), |
| ty::Dynamic(..) => { |
| let mut vtable = scalar_unit(Pointer); |
| vtable.valid_range_mut().start = 1; |
| vtable |
| } |
| _ => return Err(LayoutError::Unknown(unsized_part)), |
| }; |
| |
| // Effectively a (ptr, meta) tuple. |
| tcx.intern_layout(scalar_pair(cx, data_ptr, metadata)) |
| } |
| |
| ty::Dynamic(_, _, ty::DynStar) => { |
| let mut data = scalar_unit(Int(dl.ptr_sized_integer(), false)); |
| data.valid_range_mut().start = 0; |
| let mut vtable = scalar_unit(Pointer); |
| vtable.valid_range_mut().start = 1; |
| tcx.intern_layout(scalar_pair(cx, data, vtable)) |
| } |
| |
| // Arrays and slices. |
| ty::Array(element, mut count) => { |
| if count.has_projections() { |
| count = tcx.normalize_erasing_regions(param_env, count); |
| if count.has_projections() { |
| return Err(LayoutError::Unknown(ty)); |
| } |
| } |
| |
| let count = count.try_eval_usize(tcx, param_env).ok_or(LayoutError::Unknown(ty))?; |
| let element = cx.layout_of(element)?; |
| let size = element.size.checked_mul(count, dl).ok_or(LayoutError::SizeOverflow(ty))?; |
| |
| let abi = if count != 0 && tcx.conservative_is_privately_uninhabited(param_env.and(ty)) |
| { |
| Abi::Uninhabited |
| } else { |
| Abi::Aggregate { sized: true } |
| }; |
| |
| let largest_niche = if count != 0 { element.largest_niche } else { None }; |
| |
| tcx.intern_layout(LayoutS { |
| variants: Variants::Single { index: VariantIdx::new(0) }, |
| fields: FieldsShape::Array { stride: element.size, count }, |
| abi, |
| largest_niche, |
| align: element.align, |
| size, |
| }) |
| } |
| ty::Slice(element) => { |
| let element = cx.layout_of(element)?; |
| tcx.intern_layout(LayoutS { |
| variants: Variants::Single { index: VariantIdx::new(0) }, |
| fields: FieldsShape::Array { stride: element.size, count: 0 }, |
| abi: Abi::Aggregate { sized: false }, |
| largest_niche: None, |
| align: element.align, |
| size: Size::ZERO, |
| }) |
| } |
| ty::Str => tcx.intern_layout(LayoutS { |
| variants: Variants::Single { index: VariantIdx::new(0) }, |
| fields: FieldsShape::Array { stride: Size::from_bytes(1), count: 0 }, |
| abi: Abi::Aggregate { sized: false }, |
| largest_niche: None, |
| align: dl.i8_align, |
| size: Size::ZERO, |
| }), |
| |
| // Odd unit types. |
| ty::FnDef(..) => univariant(&[], &ReprOptions::default(), StructKind::AlwaysSized)?, |
| ty::Dynamic(_, _, ty::Dyn) | ty::Foreign(..) => { |
| let mut unit = univariant_uninterned( |
| cx, |
| ty, |
| &[], |
| &ReprOptions::default(), |
| StructKind::AlwaysSized, |
| )?; |
| match unit.abi { |
| Abi::Aggregate { ref mut sized } => *sized = false, |
| _ => bug!(), |
| } |
| tcx.intern_layout(unit) |
| } |
| |
| ty::Generator(def_id, substs, _) => generator_layout(cx, ty, def_id, substs)?, |
| |
| ty::Closure(_, ref substs) => { |
| let tys = substs.as_closure().upvar_tys(); |
| univariant( |
| &tys.map(|ty| cx.layout_of(ty)).collect::<Result<Vec<_>, _>>()?, |
| &ReprOptions::default(), |
| StructKind::AlwaysSized, |
| )? |
| } |
| |
| ty::Tuple(tys) => { |
| let kind = |
| if tys.len() == 0 { StructKind::AlwaysSized } else { StructKind::MaybeUnsized }; |
| |
| univariant( |
| &tys.iter().map(|k| cx.layout_of(k)).collect::<Result<Vec<_>, _>>()?, |
| &ReprOptions::default(), |
| kind, |
| )? |
| } |
| |
| // SIMD vector types. |
| ty::Adt(def, substs) if def.repr().simd() => { |
| if !def.is_struct() { |
| // Should have yielded E0517 by now. |
| tcx.sess.delay_span_bug( |
| DUMMY_SP, |
| "#[repr(simd)] was applied to an ADT that is not a struct", |
| ); |
| return Err(LayoutError::Unknown(ty)); |
| } |
| |
| // Supported SIMD vectors are homogeneous ADTs with at least one field: |
| // |
| // * #[repr(simd)] struct S(T, T, T, T); |
| // * #[repr(simd)] struct S { x: T, y: T, z: T, w: T } |
| // * #[repr(simd)] struct S([T; 4]) |
| // |
| // where T is a primitive scalar (integer/float/pointer). |
| |
| // SIMD vectors with zero fields are not supported. |
| // (should be caught by typeck) |
| if def.non_enum_variant().fields.is_empty() { |
| tcx.sess.fatal(&format!("monomorphising SIMD type `{}` of zero length", ty)); |
| } |
| |
| // Type of the first ADT field: |
| let f0_ty = def.non_enum_variant().fields[0].ty(tcx, substs); |
| |
| // Heterogeneous SIMD vectors are not supported: |
| // (should be caught by typeck) |
| for fi in &def.non_enum_variant().fields { |
| if fi.ty(tcx, substs) != f0_ty { |
| tcx.sess.fatal(&format!("monomorphising heterogeneous SIMD type `{}`", ty)); |
| } |
| } |
| |
| // The element type and number of elements of the SIMD vector |
| // are obtained from: |
| // |
| // * the element type and length of the single array field, if |
| // the first field is of array type, or |
| // |
| // * the homogeneous field type and the number of fields. |
| let (e_ty, e_len, is_array) = if let ty::Array(e_ty, _) = f0_ty.kind() { |
| // First ADT field is an array: |
| |
| // SIMD vectors with multiple array fields are not supported: |
| // (should be caught by typeck) |
| if def.non_enum_variant().fields.len() != 1 { |
| tcx.sess.fatal(&format!( |
| "monomorphising SIMD type `{}` with more than one array field", |
| ty |
| )); |
| } |
| |
| // Extract the number of elements from the layout of the array field: |
| let FieldsShape::Array { count, .. } = cx.layout_of(f0_ty)?.layout.fields() else { |
| return Err(LayoutError::Unknown(ty)); |
| }; |
| |
| (*e_ty, *count, true) |
| } else { |
| // First ADT field is not an array: |
| (f0_ty, def.non_enum_variant().fields.len() as _, false) |
| }; |
| |
| // SIMD vectors of zero length are not supported. |
| // Additionally, lengths are capped at 2^16 as a fixed maximum backends must |
| // support. |
| // |
| // Can't be caught in typeck if the array length is generic. |
| if e_len == 0 { |
| tcx.sess.fatal(&format!("monomorphising SIMD type `{}` of zero length", ty)); |
| } else if e_len > MAX_SIMD_LANES { |
| tcx.sess.fatal(&format!( |
| "monomorphising SIMD type `{}` of length greater than {}", |
| ty, MAX_SIMD_LANES, |
| )); |
| } |
| |
| // Compute the ABI of the element type: |
| let e_ly = cx.layout_of(e_ty)?; |
| let Abi::Scalar(e_abi) = e_ly.abi else { |
| // This error isn't caught in typeck, e.g., if |
| // the element type of the vector is generic. |
| tcx.sess.fatal(&format!( |
| "monomorphising SIMD type `{}` with a non-primitive-scalar \ |
| (integer/float/pointer) element type `{}`", |
| ty, e_ty |
| )) |
| }; |
| |
| // Compute the size and alignment of the vector: |
| let size = e_ly.size.checked_mul(e_len, dl).ok_or(LayoutError::SizeOverflow(ty))?; |
| let align = dl.vector_align(size); |
| let size = size.align_to(align.abi); |
| |
| // Compute the placement of the vector fields: |
| let fields = if is_array { |
| FieldsShape::Arbitrary { offsets: vec![Size::ZERO], memory_index: vec![0] } |
| } else { |
| FieldsShape::Array { stride: e_ly.size, count: e_len } |
| }; |
| |
| tcx.intern_layout(LayoutS { |
| variants: Variants::Single { index: VariantIdx::new(0) }, |
| fields, |
| abi: Abi::Vector { element: e_abi, count: e_len }, |
| largest_niche: e_ly.largest_niche, |
| size, |
| align, |
| }) |
| } |
| |
| // ADTs. |
| ty::Adt(def, substs) => { |
| // Cache the field layouts. |
| let variants = def |
| .variants() |
| .iter() |
| .map(|v| { |
| v.fields |
| .iter() |
| .map(|field| cx.layout_of(field.ty(tcx, substs))) |
| .collect::<Result<Vec<_>, _>>() |
| }) |
| .collect::<Result<IndexVec<VariantIdx, _>, _>>()?; |
| |
| if def.is_union() { |
| if def.repr().pack.is_some() && def.repr().align.is_some() { |
| cx.tcx.sess.delay_span_bug( |
| tcx.def_span(def.did()), |
| "union cannot be packed and aligned", |
| ); |
| return Err(LayoutError::Unknown(ty)); |
| } |
| |
| let mut align = |
| if def.repr().pack.is_some() { dl.i8_align } else { dl.aggregate_align }; |
| |
| if let Some(repr_align) = def.repr().align { |
| align = align.max(AbiAndPrefAlign::new(repr_align)); |
| } |
| |
| let optimize = !def.repr().inhibit_union_abi_opt(); |
| let mut size = Size::ZERO; |
| let mut abi = Abi::Aggregate { sized: true }; |
| let index = VariantIdx::new(0); |
| for field in &variants[index] { |
| assert!(!field.is_unsized()); |
| align = align.max(field.align); |
| |
| // If all non-ZST fields have the same ABI, forward this ABI |
| if optimize && !field.is_zst() { |
| // Discard valid range information and allow undef |
| let field_abi = match field.abi { |
| Abi::Scalar(x) => Abi::Scalar(x.to_union()), |
| Abi::ScalarPair(x, y) => Abi::ScalarPair(x.to_union(), y.to_union()), |
| Abi::Vector { element: x, count } => { |
| Abi::Vector { element: x.to_union(), count } |
| } |
| Abi::Uninhabited | Abi::Aggregate { .. } => { |
| Abi::Aggregate { sized: true } |
| } |
| }; |
| |
| if size == Size::ZERO { |
| // first non ZST: initialize 'abi' |
| abi = field_abi; |
| } else if abi != field_abi { |
| // different fields have different ABI: reset to Aggregate |
| abi = Abi::Aggregate { sized: true }; |
| } |
| } |
| |
| size = cmp::max(size, field.size); |
| } |
| |
| if let Some(pack) = def.repr().pack { |
| align = align.min(AbiAndPrefAlign::new(pack)); |
| } |
| |
| return Ok(tcx.intern_layout(LayoutS { |
| variants: Variants::Single { index }, |
| fields: FieldsShape::Union( |
| NonZeroUsize::new(variants[index].len()).ok_or(LayoutError::Unknown(ty))?, |
| ), |
| abi, |
| largest_niche: None, |
| align, |
| size: size.align_to(align.abi), |
| })); |
| } |
| |
| // A variant is absent if it's uninhabited and only has ZST fields. |
| // Present uninhabited variants only require space for their fields, |
| // but *not* an encoding of the discriminant (e.g., a tag value). |
| // See issue #49298 for more details on the need to leave space |
| // for non-ZST uninhabited data (mostly partial initialization). |
| let absent = |fields: &[TyAndLayout<'_>]| { |
| let uninhabited = fields.iter().any(|f| f.abi.is_uninhabited()); |
| let is_zst = fields.iter().all(|f| f.is_zst()); |
| uninhabited && is_zst |
| }; |
| let (present_first, present_second) = { |
| let mut present_variants = variants |
| .iter_enumerated() |
| .filter_map(|(i, v)| if absent(v) { None } else { Some(i) }); |
| (present_variants.next(), present_variants.next()) |
| }; |
| let present_first = match present_first { |
| Some(present_first) => present_first, |
| // Uninhabited because it has no variants, or only absent ones. |
| None if def.is_enum() => { |
| return Ok(tcx.layout_of(param_env.and(tcx.types.never))?.layout); |
| } |
| // If it's a struct, still compute a layout so that we can still compute the |
| // field offsets. |
| None => VariantIdx::new(0), |
| }; |
| |
| let is_struct = !def.is_enum() || |
| // Only one variant is present. |
| (present_second.is_none() && |
| // Representation optimizations are allowed. |
| !def.repr().inhibit_enum_layout_opt()); |
| if is_struct { |
| // Struct, or univariant enum equivalent to a struct. |
| // (Typechecking will reject discriminant-sizing attrs.) |
| |
| let v = present_first; |
| let kind = if def.is_enum() || variants[v].is_empty() { |
| StructKind::AlwaysSized |
| } else { |
| let param_env = tcx.param_env(def.did()); |
| let last_field = def.variant(v).fields.last().unwrap(); |
| let always_sized = tcx.type_of(last_field.did).is_sized(tcx, param_env); |
| if !always_sized { StructKind::MaybeUnsized } else { StructKind::AlwaysSized } |
| }; |
| |
| let mut st = univariant_uninterned(cx, ty, &variants[v], &def.repr(), kind)?; |
| st.variants = Variants::Single { index: v }; |
| |
| if def.is_unsafe_cell() { |
| let hide_niches = |scalar: &mut _| match scalar { |
| Scalar::Initialized { value, valid_range } => { |
| *valid_range = WrappingRange::full(value.size(dl)) |
| } |
| // Already doesn't have any niches |
| Scalar::Union { .. } => {} |
| }; |
| match &mut st.abi { |
| Abi::Uninhabited => {} |
| Abi::Scalar(scalar) => hide_niches(scalar), |
| Abi::ScalarPair(a, b) => { |
| hide_niches(a); |
| hide_niches(b); |
| } |
| Abi::Vector { element, count: _ } => hide_niches(element), |
| Abi::Aggregate { sized: _ } => {} |
| } |
| st.largest_niche = None; |
| return Ok(tcx.intern_layout(st)); |
| } |
| |
| let (start, end) = cx.tcx.layout_scalar_valid_range(def.did()); |
| match st.abi { |
| Abi::Scalar(ref mut scalar) | Abi::ScalarPair(ref mut scalar, _) => { |
| // the asserts ensure that we are not using the |
| // `#[rustc_layout_scalar_valid_range(n)]` |
| // attribute to widen the range of anything as that would probably |
| // result in UB somewhere |
| // FIXME(eddyb) the asserts are probably not needed, |
| // as larger validity ranges would result in missed |
| // optimizations, *not* wrongly assuming the inner |
| // value is valid. e.g. unions enlarge validity ranges, |
| // because the values may be uninitialized. |
| if let Bound::Included(start) = start { |
| // FIXME(eddyb) this might be incorrect - it doesn't |
| // account for wrap-around (end < start) ranges. |
| let valid_range = scalar.valid_range_mut(); |
| assert!(valid_range.start <= start); |
| valid_range.start = start; |
| } |
| if let Bound::Included(end) = end { |
| // FIXME(eddyb) this might be incorrect - it doesn't |
| // account for wrap-around (end < start) ranges. |
| let valid_range = scalar.valid_range_mut(); |
| assert!(valid_range.end >= end); |
| valid_range.end = end; |
| } |
| |
| // Update `largest_niche` if we have introduced a larger niche. |
| let niche = Niche::from_scalar(dl, Size::ZERO, *scalar); |
| if let Some(niche) = niche { |
| match st.largest_niche { |
| Some(largest_niche) => { |
| // Replace the existing niche even if they're equal, |
| // because this one is at a lower offset. |
| if largest_niche.available(dl) <= niche.available(dl) { |
| st.largest_niche = Some(niche); |
| } |
| } |
| None => st.largest_niche = Some(niche), |
| } |
| } |
| } |
| _ => assert!( |
| start == Bound::Unbounded && end == Bound::Unbounded, |
| "nonscalar layout for layout_scalar_valid_range type {:?}: {:#?}", |
| def, |
| st, |
| ), |
| } |
| |
| return Ok(tcx.intern_layout(st)); |
| } |
| |
| // At this point, we have handled all unions and |
| // structs. (We have also handled univariant enums |
| // that allow representation optimization.) |
| assert!(def.is_enum()); |
| |
| // Until we've decided whether to use the tagged or |
| // niche filling LayoutS, we don't want to intern the |
| // variant layouts, so we can't store them in the |
| // overall LayoutS. Store the overall LayoutS |
| // and the variant LayoutSs here until then. |
| struct TmpLayout<'tcx> { |
| layout: LayoutS<'tcx>, |
| variants: IndexVec<VariantIdx, LayoutS<'tcx>>, |
| } |
| |
| let calculate_niche_filling_layout = |
| || -> Result<Option<TmpLayout<'tcx>>, LayoutError<'tcx>> { |
| // The current code for niche-filling relies on variant indices |
| // instead of actual discriminants, so enums with |
| // explicit discriminants (RFC #2363) would misbehave. |
| if def.repr().inhibit_enum_layout_opt() |
| || def |
| .variants() |
| .iter_enumerated() |
| .any(|(i, v)| v.discr != ty::VariantDiscr::Relative(i.as_u32())) |
| { |
| return Ok(None); |
| } |
| |
| if variants.len() < 2 { |
| return Ok(None); |
| } |
| |
| let mut align = dl.aggregate_align; |
| let mut variant_layouts = variants |
| .iter_enumerated() |
| .map(|(j, v)| { |
| let mut st = univariant_uninterned( |
| cx, |
| ty, |
| v, |
| &def.repr(), |
| StructKind::AlwaysSized, |
| )?; |
| st.variants = Variants::Single { index: j }; |
| |
| align = align.max(st.align); |
| |
| Ok(st) |
| }) |
| .collect::<Result<IndexVec<VariantIdx, _>, _>>()?; |
| |
| let largest_variant_index = match variant_layouts |
| .iter_enumerated() |
| .max_by_key(|(_i, layout)| layout.size.bytes()) |
| .map(|(i, _layout)| i) |
| { |
| None => return Ok(None), |
| Some(i) => i, |
| }; |
| |
| let all_indices = VariantIdx::new(0)..=VariantIdx::new(variants.len() - 1); |
| let needs_disc = |index: VariantIdx| { |
| index != largest_variant_index && !absent(&variants[index]) |
| }; |
| let niche_variants = all_indices.clone().find(|v| needs_disc(*v)).unwrap() |
| ..=all_indices.rev().find(|v| needs_disc(*v)).unwrap(); |
| |
| let count = niche_variants.size_hint().1.unwrap() as u128; |
| |
| // Find the field with the largest niche |
| let (field_index, niche, (niche_start, niche_scalar)) = match variants |
| [largest_variant_index] |
| .iter() |
| .enumerate() |
| .filter_map(|(j, field)| Some((j, field.largest_niche?))) |
| .max_by_key(|(_, niche)| niche.available(dl)) |
| .and_then(|(j, niche)| Some((j, niche, niche.reserve(cx, count)?))) |
| { |
| None => return Ok(None), |
| Some(x) => x, |
| }; |
| |
| let niche_offset = niche.offset |
| + variant_layouts[largest_variant_index].fields.offset(field_index); |
| let niche_size = niche.value.size(dl); |
| let size = variant_layouts[largest_variant_index].size.align_to(align.abi); |
| |
| let all_variants_fit = |
| variant_layouts.iter_enumerated_mut().all(|(i, layout)| { |
| if i == largest_variant_index { |
| return true; |
| } |
| |
| layout.largest_niche = None; |
| |
| if layout.size <= niche_offset { |
| // This variant will fit before the niche. |
| return true; |
| } |
| |
| // Determine if it'll fit after the niche. |
| let this_align = layout.align.abi; |
| let this_offset = (niche_offset + niche_size).align_to(this_align); |
| |
| if this_offset + layout.size > size { |
| return false; |
| } |
| |
| // It'll fit, but we need to make some adjustments. |
| match layout.fields { |
| FieldsShape::Arbitrary { ref mut offsets, .. } => { |
| for (j, offset) in offsets.iter_mut().enumerate() { |
| if !variants[i][j].is_zst() { |
| *offset += this_offset; |
| } |
| } |
| } |
| _ => { |
| panic!("Layout of fields should be Arbitrary for variants") |
| } |
| } |
| |
| // It can't be a Scalar or ScalarPair because the offset isn't 0. |
| if !layout.abi.is_uninhabited() { |
| layout.abi = Abi::Aggregate { sized: true }; |
| } |
| layout.size += this_offset; |
| |
| true |
| }); |
| |
| if !all_variants_fit { |
| return Ok(None); |
| } |
| |
| let largest_niche = Niche::from_scalar(dl, niche_offset, niche_scalar); |
| |
| let others_zst = variant_layouts |
| .iter_enumerated() |
| .all(|(i, layout)| i == largest_variant_index || layout.size == Size::ZERO); |
| let same_size = size == variant_layouts[largest_variant_index].size; |
| let same_align = align == variant_layouts[largest_variant_index].align; |
| |
| let abi = if variant_layouts.iter().all(|v| v.abi.is_uninhabited()) { |
| Abi::Uninhabited |
| } else if same_size && same_align && others_zst { |
| match variant_layouts[largest_variant_index].abi { |
| // When the total alignment and size match, we can use the |
| // same ABI as the scalar variant with the reserved niche. |
| Abi::Scalar(_) => Abi::Scalar(niche_scalar), |
| Abi::ScalarPair(first, second) => { |
| // Only the niche is guaranteed to be initialised, |
| // so use union layouts for the other primitive. |
| if niche_offset == Size::ZERO { |
| Abi::ScalarPair(niche_scalar, second.to_union()) |
| } else { |
| Abi::ScalarPair(first.to_union(), niche_scalar) |
| } |
| } |
| _ => Abi::Aggregate { sized: true }, |
| } |
| } else { |
| Abi::Aggregate { sized: true } |
| }; |
| |
| let layout = LayoutS { |
| variants: Variants::Multiple { |
| tag: niche_scalar, |
| tag_encoding: TagEncoding::Niche { |
| untagged_variant: largest_variant_index, |
| niche_variants, |
| niche_start, |
| }, |
| tag_field: 0, |
| variants: IndexVec::new(), |
| }, |
| fields: FieldsShape::Arbitrary { |
| offsets: vec![niche_offset], |
| memory_index: vec![0], |
| }, |
| abi, |
| largest_niche, |
| size, |
| align, |
| }; |
| |
| Ok(Some(TmpLayout { layout, variants: variant_layouts })) |
| }; |
| |
| let niche_filling_layout = calculate_niche_filling_layout()?; |
| |
| let (mut min, mut max) = (i128::MAX, i128::MIN); |
| let discr_type = def.repr().discr_type(); |
| let bits = Integer::from_attr(cx, discr_type).size().bits(); |
| for (i, discr) in def.discriminants(tcx) { |
| if variants[i].iter().any(|f| f.abi.is_uninhabited()) { |
| continue; |
| } |
| let mut x = discr.val as i128; |
| if discr_type.is_signed() { |
| // sign extend the raw representation to be an i128 |
| x = (x << (128 - bits)) >> (128 - bits); |
| } |
| if x < min { |
| min = x; |
| } |
| if x > max { |
| max = x; |
| } |
| } |
| // We might have no inhabited variants, so pretend there's at least one. |
| if (min, max) == (i128::MAX, i128::MIN) { |
| min = 0; |
| max = 0; |
| } |
| assert!(min <= max, "discriminant range is {}...{}", min, max); |
| let (min_ity, signed) = Integer::repr_discr(tcx, ty, &def.repr(), min, max); |
| |
| let mut align = dl.aggregate_align; |
| let mut size = Size::ZERO; |
| |
| // We're interested in the smallest alignment, so start large. |
| let mut start_align = Align::from_bytes(256).unwrap(); |
| assert_eq!(Integer::for_align(dl, start_align), None); |
| |
| // repr(C) on an enum tells us to make a (tag, union) layout, |
| // so we need to grow the prefix alignment to be at least |
| // the alignment of the union. (This value is used both for |
| // determining the alignment of the overall enum, and the |
| // determining the alignment of the payload after the tag.) |
| let mut prefix_align = min_ity.align(dl).abi; |
| if def.repr().c() { |
| for fields in &variants { |
| for field in fields { |
| prefix_align = prefix_align.max(field.align.abi); |
| } |
| } |
| } |
| |
| // Create the set of structs that represent each variant. |
| let mut layout_variants = variants |
| .iter_enumerated() |
| .map(|(i, field_layouts)| { |
| let mut st = univariant_uninterned( |
| cx, |
| ty, |
| &field_layouts, |
| &def.repr(), |
| StructKind::Prefixed(min_ity.size(), prefix_align), |
| )?; |
| st.variants = Variants::Single { index: i }; |
| // Find the first field we can't move later |
| // to make room for a larger discriminant. |
| for field in st.fields.index_by_increasing_offset().map(|j| field_layouts[j]) { |
| if !field.is_zst() || field.align.abi.bytes() != 1 { |
| start_align = start_align.min(field.align.abi); |
| break; |
| } |
| } |
| size = cmp::max(size, st.size); |
| align = align.max(st.align); |
| Ok(st) |
| }) |
| .collect::<Result<IndexVec<VariantIdx, _>, _>>()?; |
| |
| // Align the maximum variant size to the largest alignment. |
| size = size.align_to(align.abi); |
| |
| if size.bytes() >= dl.obj_size_bound() { |
| return Err(LayoutError::SizeOverflow(ty)); |
| } |
| |
| let typeck_ity = Integer::from_attr(dl, def.repr().discr_type()); |
| if typeck_ity < min_ity { |
| // It is a bug if Layout decided on a greater discriminant size than typeck for |
| // some reason at this point (based on values discriminant can take on). Mostly |
| // because this discriminant will be loaded, and then stored into variable of |
| // type calculated by typeck. Consider such case (a bug): typeck decided on |
| // byte-sized discriminant, but layout thinks we need a 16-bit to store all |
| // discriminant values. That would be a bug, because then, in codegen, in order |
| // to store this 16-bit discriminant into 8-bit sized temporary some of the |
| // space necessary to represent would have to be discarded (or layout is wrong |
| // on thinking it needs 16 bits) |
| bug!( |
| "layout decided on a larger discriminant type ({:?}) than typeck ({:?})", |
| min_ity, |
| typeck_ity |
| ); |
| // However, it is fine to make discr type however large (as an optimisation) |
| // after this point – we’ll just truncate the value we load in codegen. |
| } |
| |
| // Check to see if we should use a different type for the |
| // discriminant. We can safely use a type with the same size |
| // as the alignment of the first field of each variant. |
| // We increase the size of the discriminant to avoid LLVM copying |
| // padding when it doesn't need to. This normally causes unaligned |
| // load/stores and excessive memcpy/memset operations. By using a |
| // bigger integer size, LLVM can be sure about its contents and |
| // won't be so conservative. |
| |
| // Use the initial field alignment |
| let mut ity = if def.repr().c() || def.repr().int.is_some() { |
| min_ity |
| } else { |
| Integer::for_align(dl, start_align).unwrap_or(min_ity) |
| }; |
| |
| // If the alignment is not larger than the chosen discriminant size, |
| // don't use the alignment as the final size. |
| if ity <= min_ity { |
| ity = min_ity; |
| } else { |
| // Patch up the variants' first few fields. |
| let old_ity_size = min_ity.size(); |
| let new_ity_size = ity.size(); |
| for variant in &mut layout_variants { |
| match variant.fields { |
| FieldsShape::Arbitrary { ref mut offsets, .. } => { |
| for i in offsets { |
| if *i <= old_ity_size { |
| assert_eq!(*i, old_ity_size); |
| *i = new_ity_size; |
| } |
| } |
| // We might be making the struct larger. |
| if variant.size <= old_ity_size { |
| variant.size = new_ity_size; |
| } |
| } |
| _ => bug!(), |
| } |
| } |
| } |
| |
| let tag_mask = ity.size().unsigned_int_max(); |
| let tag = Scalar::Initialized { |
| value: Int(ity, signed), |
| valid_range: WrappingRange { |
| start: (min as u128 & tag_mask), |
| end: (max as u128 & tag_mask), |
| }, |
| }; |
| let mut abi = Abi::Aggregate { sized: true }; |
| |
| if layout_variants.iter().all(|v| v.abi.is_uninhabited()) { |
| abi = Abi::Uninhabited; |
| } else if tag.size(dl) == size { |
| // Make sure we only use scalar layout when the enum is entirely its |
| // own tag (i.e. it has no padding nor any non-ZST variant fields). |
| abi = Abi::Scalar(tag); |
| } else { |
| // Try to use a ScalarPair for all tagged enums. |
| let mut common_prim = None; |
| let mut common_prim_initialized_in_all_variants = true; |
| for (field_layouts, layout_variant) in iter::zip(&variants, &layout_variants) { |
| let FieldsShape::Arbitrary { ref offsets, .. } = layout_variant.fields else { |
| bug!(); |
| }; |
| let mut fields = iter::zip(field_layouts, offsets).filter(|p| !p.0.is_zst()); |
| let (field, offset) = match (fields.next(), fields.next()) { |
| (None, None) => { |
| common_prim_initialized_in_all_variants = false; |
| continue; |
| } |
| (Some(pair), None) => pair, |
| _ => { |
| common_prim = None; |
| break; |
| } |
| }; |
| let prim = match field.abi { |
| Abi::Scalar(scalar) => { |
| common_prim_initialized_in_all_variants &= |
| matches!(scalar, Scalar::Initialized { .. }); |
| scalar.primitive() |
| } |
| _ => { |
| common_prim = None; |
| break; |
| } |
| }; |
| if let Some(pair) = common_prim { |
| // This is pretty conservative. We could go fancier |
| // by conflating things like i32 and u32, or even |
| // realising that (u8, u8) could just cohabit with |
| // u16 or even u32. |
| if pair != (prim, offset) { |
| common_prim = None; |
| break; |
| } |
| } else { |
| common_prim = Some((prim, offset)); |
| } |
| } |
| if let Some((prim, offset)) = common_prim { |
| let prim_scalar = if common_prim_initialized_in_all_variants { |
| scalar_unit(prim) |
| } else { |
| // Common prim might be uninit. |
| Scalar::Union { value: prim } |
| }; |
| let pair = scalar_pair(cx, tag, prim_scalar); |
| let pair_offsets = match pair.fields { |
| FieldsShape::Arbitrary { ref offsets, ref memory_index } => { |
| assert_eq!(memory_index, &[0, 1]); |
| offsets |
| } |
| _ => bug!(), |
| }; |
| if pair_offsets[0] == Size::ZERO |
| && pair_offsets[1] == *offset |
| && align == pair.align |
| && size == pair.size |
| { |
| // We can use `ScalarPair` only when it matches our |
| // already computed layout (including `#[repr(C)]`). |
| abi = pair.abi; |
| } |
| } |
| } |
| |
| // If we pick a "clever" (by-value) ABI, we might have to adjust the ABI of the |
| // variants to ensure they are consistent. This is because a downcast is |
| // semantically a NOP, and thus should not affect layout. |
| if matches!(abi, Abi::Scalar(..) | Abi::ScalarPair(..)) { |
| for variant in &mut layout_variants { |
| // We only do this for variants with fields; the others are not accessed anyway. |
| // Also do not overwrite any already existing "clever" ABIs. |
| if variant.fields.count() > 0 && matches!(variant.abi, Abi::Aggregate { .. }) { |
| variant.abi = abi; |
| // Also need to bump up the size and alignment, so that the entire value fits in here. |
| variant.size = cmp::max(variant.size, size); |
| variant.align.abi = cmp::max(variant.align.abi, align.abi); |
| } |
| } |
| } |
| |
| let largest_niche = Niche::from_scalar(dl, Size::ZERO, tag); |
| |
| let tagged_layout = LayoutS { |
| variants: Variants::Multiple { |
| tag, |
| tag_encoding: TagEncoding::Direct, |
| tag_field: 0, |
| variants: IndexVec::new(), |
| }, |
| fields: FieldsShape::Arbitrary { offsets: vec![Size::ZERO], memory_index: vec![0] }, |
| largest_niche, |
| abi, |
| align, |
| size, |
| }; |
| |
| let tagged_layout = TmpLayout { layout: tagged_layout, variants: layout_variants }; |
| |
| let mut best_layout = match (tagged_layout, niche_filling_layout) { |
| (tl, Some(nl)) => { |
| // Pick the smaller layout; otherwise, |
| // pick the layout with the larger niche; otherwise, |
| // pick tagged as it has simpler codegen. |
| use Ordering::*; |
| let niche_size = |tmp_l: &TmpLayout<'_>| { |
| tmp_l.layout.largest_niche.map_or(0, |n| n.available(dl)) |
| }; |
| match ( |
| tl.layout.size.cmp(&nl.layout.size), |
| niche_size(&tl).cmp(&niche_size(&nl)), |
| ) { |
| (Greater, _) => nl, |
| (Equal, Less) => nl, |
| _ => tl, |
| } |
| } |
| (tl, None) => tl, |
| }; |
| |
| // Now we can intern the variant layouts and store them in the enum layout. |
| best_layout.layout.variants = match best_layout.layout.variants { |
| Variants::Multiple { tag, tag_encoding, tag_field, .. } => Variants::Multiple { |
| tag, |
| tag_encoding, |
| tag_field, |
| variants: best_layout |
| .variants |
| .into_iter() |
| .map(|layout| tcx.intern_layout(layout)) |
| .collect(), |
| }, |
| _ => bug!(), |
| }; |
| |
| tcx.intern_layout(best_layout.layout) |
| } |
| |
| // Types with no meaningful known layout. |
| ty::Projection(_) | ty::Opaque(..) => { |
| // NOTE(eddyb) `layout_of` query should've normalized these away, |
| // if that was possible, so there's no reason to try again here. |
| return Err(LayoutError::Unknown(ty)); |
| } |
| |
| ty::Placeholder(..) | ty::GeneratorWitness(..) | ty::Infer(_) => { |
| bug!("Layout::compute: unexpected type `{}`", ty) |
| } |
| |
| ty::Bound(..) | ty::Param(_) | ty::Error(_) => { |
| return Err(LayoutError::Unknown(ty)); |
| } |
| }) |
| } |
| |
| /// Overlap eligibility and variant assignment for each GeneratorSavedLocal. |
| #[derive(Clone, Debug, PartialEq)] |
| enum SavedLocalEligibility { |
| Unassigned, |
| Assigned(VariantIdx), |
| // FIXME: Use newtype_index so we aren't wasting bytes |
| Ineligible(Option<u32>), |
| } |
| |
| // When laying out generators, we divide our saved local fields into two |
| // categories: overlap-eligible and overlap-ineligible. |
| // |
| // Those fields which are ineligible for overlap go in a "prefix" at the |
| // beginning of the layout, and always have space reserved for them. |
| // |
| // Overlap-eligible fields are only assigned to one variant, so we lay |
| // those fields out for each variant and put them right after the |
| // prefix. |
| // |
| // Finally, in the layout details, we point to the fields from the |
| // variants they are assigned to. It is possible for some fields to be |
| // included in multiple variants. No field ever "moves around" in the |
| // layout; its offset is always the same. |
| // |
| // Also included in the layout are the upvars and the discriminant. |
| // These are included as fields on the "outer" layout; they are not part |
| // of any variant. |
| |
| /// Compute the eligibility and assignment of each local. |
| fn generator_saved_local_eligibility<'tcx>( |
| info: &GeneratorLayout<'tcx>, |
| ) -> (BitSet<GeneratorSavedLocal>, IndexVec<GeneratorSavedLocal, SavedLocalEligibility>) { |
| use SavedLocalEligibility::*; |
| |
| let mut assignments: IndexVec<GeneratorSavedLocal, SavedLocalEligibility> = |
| IndexVec::from_elem_n(Unassigned, info.field_tys.len()); |
| |
| // The saved locals not eligible for overlap. These will get |
| // "promoted" to the prefix of our generator. |
| let mut ineligible_locals = BitSet::new_empty(info.field_tys.len()); |
| |
| // Figure out which of our saved locals are fields in only |
| // one variant. The rest are deemed ineligible for overlap. |
| for (variant_index, fields) in info.variant_fields.iter_enumerated() { |
| for local in fields { |
| match assignments[*local] { |
| Unassigned => { |
| assignments[*local] = Assigned(variant_index); |
| } |
| Assigned(idx) => { |
| // We've already seen this local at another suspension |
| // point, so it is no longer a candidate. |
| trace!( |
| "removing local {:?} in >1 variant ({:?}, {:?})", |
| local, |
| variant_index, |
| idx |
| ); |
| ineligible_locals.insert(*local); |
| assignments[*local] = Ineligible(None); |
| } |
| Ineligible(_) => {} |
| } |
| } |
| } |
| |
| // Next, check every pair of eligible locals to see if they |
| // conflict. |
| for local_a in info.storage_conflicts.rows() { |
| let conflicts_a = info.storage_conflicts.count(local_a); |
| if ineligible_locals.contains(local_a) { |
| continue; |
| } |
| |
| for local_b in info.storage_conflicts.iter(local_a) { |
| // local_a and local_b are storage live at the same time, therefore they |
| // cannot overlap in the generator layout. The only way to guarantee |
| // this is if they are in the same variant, or one is ineligible |
| // (which means it is stored in every variant). |
| if ineligible_locals.contains(local_b) || assignments[local_a] == assignments[local_b] { |
| continue; |
| } |
| |
| // If they conflict, we will choose one to make ineligible. |
| // This is not always optimal; it's just a greedy heuristic that |
| // seems to produce good results most of the time. |
| let conflicts_b = info.storage_conflicts.count(local_b); |
| let (remove, other) = |
| if conflicts_a > conflicts_b { (local_a, local_b) } else { (local_b, local_a) }; |
| ineligible_locals.insert(remove); |
| assignments[remove] = Ineligible(None); |
| trace!("removing local {:?} due to conflict with {:?}", remove, other); |
| } |
| } |
| |
| // Count the number of variants in use. If only one of them, then it is |
| // impossible to overlap any locals in our layout. In this case it's |
| // always better to make the remaining locals ineligible, so we can |
| // lay them out with the other locals in the prefix and eliminate |
| // unnecessary padding bytes. |
| { |
| let mut used_variants = BitSet::new_empty(info.variant_fields.len()); |
| for assignment in &assignments { |
| if let Assigned(idx) = assignment { |
| used_variants.insert(*idx); |
| } |
| } |
| if used_variants.count() < 2 { |
| for assignment in assignments.iter_mut() { |
| *assignment = Ineligible(None); |
| } |
| ineligible_locals.insert_all(); |
| } |
| } |
| |
| // Write down the order of our locals that will be promoted to the prefix. |
| { |
| for (idx, local) in ineligible_locals.iter().enumerate() { |
| assignments[local] = Ineligible(Some(idx as u32)); |
| } |
| } |
| debug!("generator saved local assignments: {:?}", assignments); |
| |
| (ineligible_locals, assignments) |
| } |
| |
| /// Compute the full generator layout. |
| fn generator_layout<'tcx>( |
| cx: &LayoutCx<'tcx, TyCtxt<'tcx>>, |
| ty: Ty<'tcx>, |
| def_id: hir::def_id::DefId, |
| substs: SubstsRef<'tcx>, |
| ) -> Result<Layout<'tcx>, LayoutError<'tcx>> { |
| use SavedLocalEligibility::*; |
| let tcx = cx.tcx; |
| let subst_field = |ty: Ty<'tcx>| EarlyBinder(ty).subst(tcx, substs); |
| |
| let Some(info) = tcx.generator_layout(def_id) else { |
| return Err(LayoutError::Unknown(ty)); |
| }; |
| let (ineligible_locals, assignments) = generator_saved_local_eligibility(&info); |
| |
| // Build a prefix layout, including "promoting" all ineligible |
| // locals as part of the prefix. We compute the layout of all of |
| // these fields at once to get optimal packing. |
| let tag_index = substs.as_generator().prefix_tys().count(); |
| |
| // `info.variant_fields` already accounts for the reserved variants, so no need to add them. |
| let max_discr = (info.variant_fields.len() - 1) as u128; |
| let discr_int = Integer::fit_unsigned(max_discr); |
| let discr_int_ty = discr_int.to_ty(tcx, false); |
| let tag = Scalar::Initialized { |
| value: Primitive::Int(discr_int, false), |
| valid_range: WrappingRange { start: 0, end: max_discr }, |
| }; |
| let tag_layout = cx.tcx.intern_layout(LayoutS::scalar(cx, tag)); |
| let tag_layout = TyAndLayout { ty: discr_int_ty, layout: tag_layout }; |
| |
| let promoted_layouts = ineligible_locals |
| .iter() |
| .map(|local| subst_field(info.field_tys[local])) |
| .map(|ty| tcx.mk_maybe_uninit(ty)) |
| .map(|ty| cx.layout_of(ty)); |
| let prefix_layouts = substs |
| .as_generator() |
| .prefix_tys() |
| .map(|ty| cx.layout_of(ty)) |
| .chain(iter::once(Ok(tag_layout))) |
| .chain(promoted_layouts) |
| .collect::<Result<Vec<_>, _>>()?; |
| let prefix = univariant_uninterned( |
| cx, |
| ty, |
| &prefix_layouts, |
| &ReprOptions::default(), |
| StructKind::AlwaysSized, |
| )?; |
| |
| let (prefix_size, prefix_align) = (prefix.size, prefix.align); |
| |
| // Split the prefix layout into the "outer" fields (upvars and |
| // discriminant) and the "promoted" fields. Promoted fields will |
| // get included in each variant that requested them in |
| // GeneratorLayout. |
| debug!("prefix = {:#?}", prefix); |
| let (outer_fields, promoted_offsets, promoted_memory_index) = match prefix.fields { |
| FieldsShape::Arbitrary { mut offsets, memory_index } => { |
| let mut inverse_memory_index = invert_mapping(&memory_index); |
| |
| // "a" (`0..b_start`) and "b" (`b_start..`) correspond to |
| // "outer" and "promoted" fields respectively. |
| let b_start = (tag_index + 1) as u32; |
| let offsets_b = offsets.split_off(b_start as usize); |
| let offsets_a = offsets; |
| |
| // Disentangle the "a" and "b" components of `inverse_memory_index` |
| // by preserving the order but keeping only one disjoint "half" each. |
| // FIXME(eddyb) build a better abstraction for permutations, if possible. |
| let inverse_memory_index_b: Vec<_> = |
| inverse_memory_index.iter().filter_map(|&i| i.checked_sub(b_start)).collect(); |
| inverse_memory_index.retain(|&i| i < b_start); |
| let inverse_memory_index_a = inverse_memory_index; |
| |
| // Since `inverse_memory_index_{a,b}` each only refer to their |
| // respective fields, they can be safely inverted |
| let memory_index_a = invert_mapping(&inverse_memory_index_a); |
| let memory_index_b = invert_mapping(&inverse_memory_index_b); |
| |
| let outer_fields = |
| FieldsShape::Arbitrary { offsets: offsets_a, memory_index: memory_index_a }; |
| (outer_fields, offsets_b, memory_index_b) |
| } |
| _ => bug!(), |
| }; |
| |
| let mut size = prefix.size; |
| let mut align = prefix.align; |
| let variants = info |
| .variant_fields |
| .iter_enumerated() |
| .map(|(index, variant_fields)| { |
| // Only include overlap-eligible fields when we compute our variant layout. |
| let variant_only_tys = variant_fields |
| .iter() |
| .filter(|local| match assignments[**local] { |
| Unassigned => bug!(), |
| Assigned(v) if v == index => true, |
| Assigned(_) => bug!("assignment does not match variant"), |
| Ineligible(_) => false, |
| }) |
| .map(|local| subst_field(info.field_tys[*local])); |
| |
| let mut variant = univariant_uninterned( |
| cx, |
| ty, |
| &variant_only_tys.map(|ty| cx.layout_of(ty)).collect::<Result<Vec<_>, _>>()?, |
| &ReprOptions::default(), |
| StructKind::Prefixed(prefix_size, prefix_align.abi), |
| )?; |
| variant.variants = Variants::Single { index }; |
| |
| let FieldsShape::Arbitrary { offsets, memory_index } = variant.fields else { |
| bug!(); |
| }; |
| |
| // Now, stitch the promoted and variant-only fields back together in |
| // the order they are mentioned by our GeneratorLayout. |
| // Because we only use some subset (that can differ between variants) |
| // of the promoted fields, we can't just pick those elements of the |
| // `promoted_memory_index` (as we'd end up with gaps). |
| // So instead, we build an "inverse memory_index", as if all of the |
| // promoted fields were being used, but leave the elements not in the |
| // subset as `INVALID_FIELD_IDX`, which we can filter out later to |
| // obtain a valid (bijective) mapping. |
| const INVALID_FIELD_IDX: u32 = !0; |
| let mut combined_inverse_memory_index = |
| vec![INVALID_FIELD_IDX; promoted_memory_index.len() + memory_index.len()]; |
| let mut offsets_and_memory_index = iter::zip(offsets, memory_index); |
| let combined_offsets = variant_fields |
| .iter() |
| .enumerate() |
| .map(|(i, local)| { |
| let (offset, memory_index) = match assignments[*local] { |
| Unassigned => bug!(), |
| Assigned(_) => { |
| let (offset, memory_index) = offsets_and_memory_index.next().unwrap(); |
| (offset, promoted_memory_index.len() as u32 + memory_index) |
| } |
| Ineligible(field_idx) => { |
| let field_idx = field_idx.unwrap() as usize; |
| (promoted_offsets[field_idx], promoted_memory_index[field_idx]) |
| } |
| }; |
| combined_inverse_memory_index[memory_index as usize] = i as u32; |
| offset |
| }) |
| .collect(); |
| |
| // Remove the unused slots and invert the mapping to obtain the |
| // combined `memory_index` (also see previous comment). |
| combined_inverse_memory_index.retain(|&i| i != INVALID_FIELD_IDX); |
| let combined_memory_index = invert_mapping(&combined_inverse_memory_index); |
| |
| variant.fields = FieldsShape::Arbitrary { |
| offsets: combined_offsets, |
| memory_index: combined_memory_index, |
| }; |
| |
| size = size.max(variant.size); |
| align = align.max(variant.align); |
| Ok(tcx.intern_layout(variant)) |
| }) |
| .collect::<Result<IndexVec<VariantIdx, _>, _>>()?; |
| |
| size = size.align_to(align.abi); |
| |
| let abi = if prefix.abi.is_uninhabited() || variants.iter().all(|v| v.abi().is_uninhabited()) { |
| Abi::Uninhabited |
| } else { |
| Abi::Aggregate { sized: true } |
| }; |
| |
| let layout = tcx.intern_layout(LayoutS { |
| variants: Variants::Multiple { |
| tag, |
| tag_encoding: TagEncoding::Direct, |
| tag_field: tag_index, |
| variants, |
| }, |
| fields: outer_fields, |
| abi, |
| largest_niche: prefix.largest_niche, |
| size, |
| align, |
| }); |
| debug!("generator layout ({:?}): {:#?}", ty, layout); |
| Ok(layout) |
| } |
| |
| /// This is invoked by the `layout_of` query to record the final |
| /// layout of each type. |
| #[inline(always)] |
| fn record_layout_for_printing<'tcx>(cx: &LayoutCx<'tcx, TyCtxt<'tcx>>, layout: TyAndLayout<'tcx>) { |
| // If we are running with `-Zprint-type-sizes`, maybe record layouts |
| // for dumping later. |
| if cx.tcx.sess.opts.unstable_opts.print_type_sizes { |
| record_layout_for_printing_outlined(cx, layout) |
| } |
| } |
| |
| fn record_layout_for_printing_outlined<'tcx>( |
| cx: &LayoutCx<'tcx, TyCtxt<'tcx>>, |
| layout: TyAndLayout<'tcx>, |
| ) { |
| // Ignore layouts that are done with non-empty environments or |
| // non-monomorphic layouts, as the user only wants to see the stuff |
| // resulting from the final codegen session. |
| if layout.ty.has_non_region_param() || !cx.param_env.caller_bounds().is_empty() { |
| return; |
| } |
| |
| // (delay format until we actually need it) |
| let record = |kind, packed, opt_discr_size, variants| { |
| let type_desc = format!("{:?}", layout.ty); |
| cx.tcx.sess.code_stats.record_type_size( |
| kind, |
| type_desc, |
| layout.align.abi, |
| layout.size, |
| packed, |
| opt_discr_size, |
| variants, |
| ); |
| }; |
| |
| let adt_def = match *layout.ty.kind() { |
| ty::Adt(ref adt_def, _) => { |
| debug!("print-type-size t: `{:?}` process adt", layout.ty); |
| adt_def |
| } |
| |
| ty::Closure(..) => { |
| debug!("print-type-size t: `{:?}` record closure", layout.ty); |
| record(DataTypeKind::Closure, false, None, vec![]); |
| return; |
| } |
| |
| _ => { |
| debug!("print-type-size t: `{:?}` skip non-nominal", layout.ty); |
| return; |
| } |
| }; |
| |
| let adt_kind = adt_def.adt_kind(); |
| let adt_packed = adt_def.repr().pack.is_some(); |
| |
| let build_variant_info = |n: Option<Symbol>, flds: &[Symbol], layout: TyAndLayout<'tcx>| { |
| let mut min_size = Size::ZERO; |
| let field_info: Vec<_> = flds |
| .iter() |
| .enumerate() |
| .map(|(i, &name)| { |
| let field_layout = layout.field(cx, i); |
| let offset = layout.fields.offset(i); |
| let field_end = offset + field_layout.size; |
| if min_size < field_end { |
| min_size = field_end; |
| } |
| FieldInfo { |
| name, |
| offset: offset.bytes(), |
| size: field_layout.size.bytes(), |
| align: field_layout.align.abi.bytes(), |
| } |
| }) |
| .collect(); |
| |
| VariantInfo { |
| name: n, |
| kind: if layout.is_unsized() { SizeKind::Min } else { SizeKind::Exact }, |
| align: layout.align.abi.bytes(), |
| size: if min_size.bytes() == 0 { layout.size.bytes() } else { min_size.bytes() }, |
| fields: field_info, |
| } |
| }; |
| |
| match layout.variants { |
| Variants::Single { index } => { |
| if !adt_def.variants().is_empty() && layout.fields != FieldsShape::Primitive { |
| debug!("print-type-size `{:#?}` variant {}", layout, adt_def.variant(index).name); |
| let variant_def = &adt_def.variant(index); |
| let fields: Vec<_> = variant_def.fields.iter().map(|f| f.name).collect(); |
| record( |
| adt_kind.into(), |
| adt_packed, |
| None, |
| vec![build_variant_info(Some(variant_def.name), &fields, layout)], |
| ); |
| } else { |
| // (This case arises for *empty* enums; so give it |
| // zero variants.) |
| record(adt_kind.into(), adt_packed, None, vec![]); |
| } |
| } |
| |
| Variants::Multiple { tag, ref tag_encoding, .. } => { |
| debug!( |
| "print-type-size `{:#?}` adt general variants def {}", |
| layout.ty, |
| adt_def.variants().len() |
| ); |
| let variant_infos: Vec<_> = adt_def |
| .variants() |
| .iter_enumerated() |
| .map(|(i, variant_def)| { |
| let fields: Vec<_> = variant_def.fields.iter().map(|f| f.name).collect(); |
| build_variant_info(Some(variant_def.name), &fields, layout.for_variant(cx, i)) |
| }) |
| .collect(); |
| record( |
| adt_kind.into(), |
| adt_packed, |
| match tag_encoding { |
| TagEncoding::Direct => Some(tag.size(cx)), |
| _ => None, |
| }, |
| variant_infos, |
| ); |
| } |
| } |
| } |
