Merging upstream version 1.67.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 158 insertions, 53 deletions

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
             }
         }
     }