From 5363f350887b1e5b5dd21a86f88c8af9d7fea6da Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:18:25 +0200 Subject: Merging upstream version 1.67.1+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_codegen_ssa/src/mir/place.rs | 211 +++++++++++++++++++++------- 1 file changed, 158 insertions(+), 53 deletions(-) (limited to 'compiler/rustc_codegen_ssa/src/mir/place.rs') diff --git a/compiler/rustc_codegen_ssa/src/mir/place.rs b/compiler/rustc_codegen_ssa/src/mir/place.rs index 9c18df564..fbe30154a 100644 --- a/compiler/rustc_codegen_ssa/src/mir/place.rs +++ b/compiler/rustc_codegen_ssa/src/mir/place.rs @@ -29,7 +29,7 @@ pub struct PlaceRef<'tcx, V> { impl<'a, 'tcx, V: CodegenObject> PlaceRef<'tcx, V> { pub fn new_sized(llval: V, layout: TyAndLayout<'tcx>) -> PlaceRef<'tcx, V> { - assert!(!layout.is_unsized()); + assert!(layout.is_sized()); PlaceRef { llval, llextra: None, layout, align: layout.align.abi } } @@ -38,7 +38,7 @@ impl<'a, 'tcx, V: CodegenObject> PlaceRef<'tcx, V> { layout: TyAndLayout<'tcx>, align: Align, ) -> PlaceRef<'tcx, V> { - assert!(!layout.is_unsized()); + assert!(layout.is_sized()); PlaceRef { llval, llextra: None, layout, align } } @@ -48,7 +48,7 @@ impl<'a, 'tcx, V: CodegenObject> PlaceRef<'tcx, V> { bx: &mut Bx, layout: TyAndLayout<'tcx>, ) -> Self { - assert!(!layout.is_unsized(), "tried to statically allocate unsized place"); + assert!(layout.is_sized(), "tried to statically allocate unsized place"); let tmp = bx.alloca(bx.cx().backend_type(layout), layout.align.abi); Self::new_sized(tmp, layout) } @@ -145,7 +145,7 @@ impl<'a, 'tcx, V: CodegenObject> PlaceRef<'tcx, V> { ); return simple(); } - _ if !field.is_unsized() => return simple(), + _ if field.is_sized() => return simple(), ty::Slice(..) | ty::Str | ty::Foreign(..) => return simple(), ty::Adt(def, _) => { if def.repr().packed() { @@ -209,7 +209,9 @@ impl<'a, 'tcx, V: CodegenObject> PlaceRef<'tcx, V> { bx: &mut Bx, cast_to: Ty<'tcx>, ) -> V { - let cast_to = bx.cx().immediate_backend_type(bx.cx().layout_of(cast_to)); + let cast_to_layout = bx.cx().layout_of(cast_to); + let cast_to_size = cast_to_layout.layout.size(); + let cast_to = bx.cx().immediate_backend_type(cast_to_layout); if self.layout.abi.is_uninhabited() { return bx.cx().const_undef(cast_to); } @@ -229,7 +231,8 @@ impl<'a, 'tcx, V: CodegenObject> PlaceRef<'tcx, V> { // Read the tag/niche-encoded discriminant from memory. let tag = self.project_field(bx, tag_field); - let tag = bx.load_operand(tag); + let tag_op = bx.load_operand(tag); + let tag_imm = tag_op.immediate(); // Decode the discriminant (specifically if it's niche-encoded). match *tag_encoding { @@ -242,68 +245,170 @@ impl<'a, 'tcx, V: CodegenObject> PlaceRef<'tcx, V> { Int(_, signed) => !tag_scalar.is_bool() && signed, _ => false, }; - bx.intcast(tag.immediate(), cast_to, signed) + bx.intcast(tag_imm, cast_to, signed) } TagEncoding::Niche { untagged_variant, ref niche_variants, niche_start } => { - // Rebase from niche values to discriminants, and check - // whether the result is in range for the niche variants. - let niche_llty = bx.cx().immediate_backend_type(tag.layout); - let tag = tag.immediate(); - - // We first compute the "relative discriminant" (wrt `niche_variants`), - // that is, if `n = niche_variants.end() - niche_variants.start()`, - // we remap `niche_start..=niche_start + n` (which may wrap around) - // to (non-wrap-around) `0..=n`, to be able to check whether the - // discriminant corresponds to a niche variant with one comparison. - // We also can't go directly to the (variant index) discriminant - // and check that it is in the range `niche_variants`, because - // that might not fit in the same type, on top of needing an extra - // comparison (see also the comment on `let niche_discr`). - let relative_discr = if niche_start == 0 { - // Avoid subtracting `0`, which wouldn't work for pointers. - // FIXME(eddyb) check the actual primitive type here. - tag + // Cast to an integer so we don't have to treat a pointer as a + // special case. + let (tag, tag_llty) = if tag_scalar.primitive().is_ptr() { + let t = bx.type_isize(); + let tag = bx.ptrtoint(tag_imm, t); + (tag, t) } else { - bx.sub(tag, bx.cx().const_uint_big(niche_llty, niche_start)) + (tag_imm, bx.cx().immediate_backend_type(tag_op.layout)) }; + + let tag_size = tag_scalar.size(bx.cx()); + let max_unsigned = tag_size.unsigned_int_max(); + let max_signed = tag_size.signed_int_max() as u128; + let min_signed = max_signed + 1; let relative_max = niche_variants.end().as_u32() - niche_variants.start().as_u32(); - let is_niche = if relative_max == 0 { - // Avoid calling `const_uint`, which wouldn't work for pointers. - // Also use canonical == 0 instead of non-canonical u<= 0. - // FIXME(eddyb) check the actual primitive type here. - bx.icmp(IntPredicate::IntEQ, relative_discr, bx.cx().const_null(niche_llty)) + let niche_end = niche_start.wrapping_add(relative_max as u128) & max_unsigned; + let range = tag_scalar.valid_range(bx.cx()); + + let sle = |lhs: u128, rhs: u128| -> bool { + // Signed and unsigned comparisons give the same results, + // except that in signed comparisons an integer with the + // sign bit set is less than one with the sign bit clear. + // Toggle the sign bit to do a signed comparison. + (lhs ^ min_signed) <= (rhs ^ min_signed) + }; + + // We have a subrange `niche_start..=niche_end` inside `range`. + // If the value of the tag is inside this subrange, it's a + // "niche value", an increment of the discriminant. Otherwise it + // indicates the untagged variant. + // A general algorithm to extract the discriminant from the tag + // is: + // relative_tag = tag - niche_start + // is_niche = relative_tag <= (ule) relative_max + // discr = if is_niche { + // cast(relative_tag) + niche_variants.start() + // } else { + // untagged_variant + // } + // However, we will likely be able to emit simpler code. + + // Find the least and greatest values in `range`, considered + // both as signed and unsigned. + let (low_unsigned, high_unsigned) = if range.start <= range.end { + (range.start, range.end) } else { - let relative_max = bx.cx().const_uint(niche_llty, relative_max as u64); - bx.icmp(IntPredicate::IntULE, relative_discr, relative_max) + (0, max_unsigned) + }; + let (low_signed, high_signed) = if sle(range.start, range.end) { + (range.start, range.end) + } else { + (min_signed, max_signed) }; - // NOTE(eddyb) this addition needs to be performed on the final - // type, in case the niche itself can't represent all variant - // indices (e.g. `u8` niche with more than `256` variants, - // but enough uninhabited variants so that the remaining variants - // fit in the niche). - // In other words, `niche_variants.end - niche_variants.start` - // is representable in the niche, but `niche_variants.end` - // might not be, in extreme cases. - let niche_discr = { - let relative_discr = if relative_max == 0 { - // HACK(eddyb) since we have only one niche, we know which - // one it is, and we can avoid having a dynamic value here. - bx.cx().const_uint(cast_to, 0) + let niches_ule = niche_start <= niche_end; + let niches_sle = sle(niche_start, niche_end); + let cast_smaller = cast_to_size <= tag_size; + + // In the algorithm above, we can change + // cast(relative_tag) + niche_variants.start() + // into + // cast(tag + (niche_variants.start() - niche_start)) + // if either the casted type is no larger than the original + // type, or if the niche values are contiguous (in either the + // signed or unsigned sense). + let can_incr = cast_smaller || niches_ule || niches_sle; + + let data_for_boundary_niche = || -> Option<(IntPredicate, u128)> { + if !can_incr { + None + } else if niche_start == low_unsigned { + Some((IntPredicate::IntULE, niche_end)) + } else if niche_end == high_unsigned { + Some((IntPredicate::IntUGE, niche_start)) + } else if niche_start == low_signed { + Some((IntPredicate::IntSLE, niche_end)) + } else if niche_end == high_signed { + Some((IntPredicate::IntSGE, niche_start)) } else { - bx.intcast(relative_discr, cast_to, false) + None + } + }; + + let (is_niche, tagged_discr, delta) = if relative_max == 0 { + // Best case scenario: only one tagged variant. This will + // likely become just a comparison and a jump. + // The algorithm is: + // is_niche = tag == niche_start + // discr = if is_niche { + // niche_start + // } else { + // untagged_variant + // } + let niche_start = bx.cx().const_uint_big(tag_llty, niche_start); + let is_niche = bx.icmp(IntPredicate::IntEQ, tag, niche_start); + let tagged_discr = + bx.cx().const_uint(cast_to, niche_variants.start().as_u32() as u64); + (is_niche, tagged_discr, 0) + } else if let Some((predicate, constant)) = data_for_boundary_niche() { + // The niche values are either the lowest or the highest in + // `range`. We can avoid the first subtraction in the + // algorithm. + // The algorithm is now this: + // is_niche = tag <= niche_end + // discr = if is_niche { + // cast(tag + (niche_variants.start() - niche_start)) + // } else { + // untagged_variant + // } + // (the first line may instead be tag >= niche_start, + // and may be a signed or unsigned comparison) + // The arithmetic must be done before the cast, so we can + // have the correct wrapping behavior. See issue #104519 for + // the consequences of getting this wrong. + let is_niche = + bx.icmp(predicate, tag, bx.cx().const_uint_big(tag_llty, constant)); + let delta = (niche_variants.start().as_u32() as u128).wrapping_sub(niche_start); + let incr_tag = if delta == 0 { + tag + } else { + bx.add(tag, bx.cx().const_uint_big(tag_llty, delta)) }; - bx.add( + + let cast_tag = if cast_smaller { + bx.intcast(incr_tag, cast_to, false) + } else if niches_ule { + bx.zext(incr_tag, cast_to) + } else { + bx.sext(incr_tag, cast_to) + }; + + (is_niche, cast_tag, 0) + } else { + // The special cases don't apply, so we'll have to go with + // the general algorithm. + let relative_discr = bx.sub(tag, bx.cx().const_uint_big(tag_llty, niche_start)); + let cast_tag = bx.intcast(relative_discr, cast_to, false); + let is_niche = bx.icmp( + IntPredicate::IntULE, relative_discr, - bx.cx().const_uint(cast_to, niche_variants.start().as_u32() as u64), - ) + bx.cx().const_uint(tag_llty, relative_max as u64), + ); + (is_niche, cast_tag, niche_variants.start().as_u32() as u128) + }; + + let tagged_discr = if delta == 0 { + tagged_discr + } else { + bx.add(tagged_discr, bx.cx().const_uint_big(cast_to, delta)) }; - bx.select( + let discr = bx.select( is_niche, - niche_discr, + tagged_discr, bx.cx().const_uint(cast_to, untagged_variant.as_u32() as u64), - ) + ); + + // In principle we could insert assumes on the possible range of `discr`, but + // currently in LLVM this seems to be a pessimization. + + discr } } } -- cgit v1.2.3