From 2456495a260827217d3c612d6c577c2f165c61eb Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Sun, 30 May 2021 10:25:41 -0700 Subject: Stop generating `alloca`s+`memcmp` for simple array equality --- compiler/rustc_codegen_llvm/src/context.rs | 5 +++++ compiler/rustc_codegen_llvm/src/intrinsic.rs | 26 ++++++++++++++++++++++++++ compiler/rustc_mir/src/interpret/intrinsics.rs | 18 ++++++++++++++++++ compiler/rustc_span/src/symbol.rs | 1 + compiler/rustc_typeck/src/check/intrinsic.rs | 8 ++++++++ 5 files changed, 58 insertions(+) (limited to 'compiler') diff --git a/compiler/rustc_codegen_llvm/src/context.rs b/compiler/rustc_codegen_llvm/src/context.rs index f662887abf8..d1aecd32e2f 100644 --- a/compiler/rustc_codegen_llvm/src/context.rs +++ b/compiler/rustc_codegen_llvm/src/context.rs @@ -500,6 +500,7 @@ impl CodegenCx<'b, 'tcx> { let t_i32 = self.type_i32(); let t_i64 = self.type_i64(); let t_i128 = self.type_i128(); + let t_isize = self.type_isize(); let t_f32 = self.type_f32(); let t_f64 = self.type_f64(); @@ -712,6 +713,10 @@ impl CodegenCx<'b, 'tcx> { ifn!("llvm.assume", fn(i1) -> void); ifn!("llvm.prefetch", fn(i8p, t_i32, t_i32, t_i32) -> void); + // This isn't an "LLVM intrinsic", but LLVM's optimization passes + // recognize it like one and we assume it exists in `core::slice::cmp` + ifn!("memcmp", fn(i8p, i8p, t_isize) -> t_i32); + // variadic intrinsics ifn!("llvm.va_start", fn(i8p) -> void); ifn!("llvm.va_end", fn(i8p) -> void); diff --git a/compiler/rustc_codegen_llvm/src/intrinsic.rs b/compiler/rustc_codegen_llvm/src/intrinsic.rs index 1fb201eda6b..615295e96e1 100644 --- a/compiler/rustc_codegen_llvm/src/intrinsic.rs +++ b/compiler/rustc_codegen_llvm/src/intrinsic.rs @@ -296,6 +296,32 @@ impl IntrinsicCallMethods<'tcx> for Builder<'a, 'll, 'tcx> { } } + sym::raw_eq => { + let tp_ty = substs.type_at(0); + let (size, align) = self.size_and_align_of(tp_ty); + let a = args[0].immediate(); + let b = args[1].immediate(); + if size.bytes() == 0 { + self.const_bool(true) + } else if size > self.data_layout().pointer_size * 4 { + let i8p_ty = self.type_i8p(); + let a_ptr = self.bitcast(a, i8p_ty); + let b_ptr = self.bitcast(b, i8p_ty); + let n = self.const_usize(size.bytes()); + let llfn = self.get_intrinsic("memcmp"); + let cmp = self.call(llfn, &[a_ptr, b_ptr, n], None); + self.icmp(IntPredicate::IntEQ, cmp, self.const_i32(0)) + } else { + let integer_ty = self.type_ix(size.bits()); + let ptr_ty = self.type_ptr_to(integer_ty); + let a_ptr = self.bitcast(a, ptr_ty); + let a_val = self.load(a_ptr, align); + let b_ptr = self.bitcast(b, ptr_ty); + let b_val = self.load(b_ptr, align); + self.icmp(IntPredicate::IntEQ, a_val, b_val) + } + } + _ if name_str.starts_with("simd_") => { match generic_simd_intrinsic(self, name, callee_ty, args, ret_ty, llret_ty, span) { Ok(llval) => llval, diff --git a/compiler/rustc_mir/src/interpret/intrinsics.rs b/compiler/rustc_mir/src/interpret/intrinsics.rs index 4e4166dad50..5dd679b8912 100644 --- a/compiler/rustc_mir/src/interpret/intrinsics.rs +++ b/compiler/rustc_mir/src/interpret/intrinsics.rs @@ -472,6 +472,10 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> { throw_ub_format!("`assume` intrinsic called with `false`"); } } + sym::raw_eq => { + let result = self.raw_eq_intrinsic(&args[0], &args[1])?; + self.write_scalar(result, dest)?; + } _ => return Ok(false), } @@ -559,4 +563,18 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> { self.memory.copy(src, align, dst, align, size, nonoverlapping) } + + pub(crate) fn raw_eq_intrinsic( + &mut self, + lhs: &OpTy<'tcx, >::PointerTag>, + rhs: &OpTy<'tcx, >::PointerTag>, + ) -> InterpResult<'tcx, Scalar> { + let layout = self.layout_of(lhs.layout.ty.builtin_deref(true).unwrap().ty)?; + + let lhs = self.read_scalar(lhs)?.check_init()?; + let rhs = self.read_scalar(rhs)?.check_init()?; + let lhs_bytes = self.memory.read_bytes(lhs, layout.size)?; + let rhs_bytes = self.memory.read_bytes(rhs, layout.size)?; + Ok(Scalar::Int((lhs_bytes == rhs_bytes).into())) + } } diff --git a/compiler/rustc_span/src/symbol.rs b/compiler/rustc_span/src/symbol.rs index edb97d70517..3ab32fe418d 100644 --- a/compiler/rustc_span/src/symbol.rs +++ b/compiler/rustc_span/src/symbol.rs @@ -933,6 +933,7 @@ symbols! { quote, range_inclusive_new, raw_dylib, + raw_eq, raw_identifiers, raw_ref_op, re_rebalance_coherence, diff --git a/compiler/rustc_typeck/src/check/intrinsic.rs b/compiler/rustc_typeck/src/check/intrinsic.rs index 882d5d54b7c..18ccaf79d32 100644 --- a/compiler/rustc_typeck/src/check/intrinsic.rs +++ b/compiler/rustc_typeck/src/check/intrinsic.rs @@ -380,6 +380,14 @@ pub fn check_intrinsic_type(tcx: TyCtxt<'_>, it: &hir::ForeignItem<'_>) { sym::nontemporal_store => (1, vec![tcx.mk_mut_ptr(param(0)), param(0)], tcx.mk_unit()), + sym::raw_eq => { + let param_count = if intrinsic_name == sym::raw_eq { 2 } else { 1 }; + let br = ty::BoundRegion { var: ty::BoundVar::from_u32(0), kind: ty::BrAnon(0) }; + let param_ty = + tcx.mk_imm_ref(tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)), param(0)); + (1, vec![param_ty; param_count], tcx.types.bool) + } + other => { tcx.sess.emit_err(UnrecognizedIntrinsicFunction { span: it.span, name: other }); return; -- cgit 1.4.1-3-g733a5 From b63b2f1e426016b24a9e552faf17f20f421f5034 Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Sun, 30 May 2021 11:31:56 -0700 Subject: PR feedback - Add `:Sized` assertion in interpreter impl - Use `Scalar::from_bool` instead of `ScalarInt: From` - Remove unneeded comparison in intrinsic typeck - Make this UB to call with undef, not just return undef in that case --- compiler/rustc_mir/src/interpret/intrinsics.rs | 3 ++- compiler/rustc_typeck/src/check/intrinsic.rs | 3 +-- library/core/src/intrinsics.rs | 8 ++++++-- 3 files changed, 9 insertions(+), 5 deletions(-) (limited to 'compiler') diff --git a/compiler/rustc_mir/src/interpret/intrinsics.rs b/compiler/rustc_mir/src/interpret/intrinsics.rs index 5dd679b8912..ad9cf3e7d2f 100644 --- a/compiler/rustc_mir/src/interpret/intrinsics.rs +++ b/compiler/rustc_mir/src/interpret/intrinsics.rs @@ -570,11 +570,12 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> { rhs: &OpTy<'tcx, >::PointerTag>, ) -> InterpResult<'tcx, Scalar> { let layout = self.layout_of(lhs.layout.ty.builtin_deref(true).unwrap().ty)?; + assert!(!layout.is_unsized()); let lhs = self.read_scalar(lhs)?.check_init()?; let rhs = self.read_scalar(rhs)?.check_init()?; let lhs_bytes = self.memory.read_bytes(lhs, layout.size)?; let rhs_bytes = self.memory.read_bytes(rhs, layout.size)?; - Ok(Scalar::Int((lhs_bytes == rhs_bytes).into())) + Ok(Scalar::from_bool(lhs_bytes == rhs_bytes)) } } diff --git a/compiler/rustc_typeck/src/check/intrinsic.rs b/compiler/rustc_typeck/src/check/intrinsic.rs index 18ccaf79d32..6661df21ed9 100644 --- a/compiler/rustc_typeck/src/check/intrinsic.rs +++ b/compiler/rustc_typeck/src/check/intrinsic.rs @@ -381,11 +381,10 @@ pub fn check_intrinsic_type(tcx: TyCtxt<'_>, it: &hir::ForeignItem<'_>) { sym::nontemporal_store => (1, vec![tcx.mk_mut_ptr(param(0)), param(0)], tcx.mk_unit()), sym::raw_eq => { - let param_count = if intrinsic_name == sym::raw_eq { 2 } else { 1 }; let br = ty::BoundRegion { var: ty::BoundVar::from_u32(0), kind: ty::BrAnon(0) }; let param_ty = tcx.mk_imm_ref(tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)), param(0)); - (1, vec![param_ty; param_count], tcx.types.bool) + (1, vec![param_ty; 2], tcx.types.bool) } other => { diff --git a/library/core/src/intrinsics.rs b/library/core/src/intrinsics.rs index 7d2c278aa05..238f00e41b3 100644 --- a/library/core/src/intrinsics.rs +++ b/library/core/src/intrinsics.rs @@ -1924,8 +1924,12 @@ extern "rust-intrinsic" { /// /// # Safety /// - /// This doesn't take into account padding, so if `T` has padding - /// the result will be `undef`, which cannot be exposed to safe code. + /// It's UB to call this if any of the *bytes* in `*a` or `*b` are uninitialized. + /// Note that this is a stricter criterion than just the *values* being + /// fully-initialized: if `T` has padding, it's UB to call this intrinsic. + /// + /// (The implementation is allowed to branch on the results of comparisons, + /// which is UB if any of their inputs are `undef`.) #[cfg(not(bootstrap))] #[rustc_const_unstable(feature = "const_intrinsic_raw_eq", issue = "none")] pub fn raw_eq(a: &T, b: &T) -> bool; -- cgit 1.4.1-3-g733a5 From 12163534a94b24a8a754fffe6e601904c2c6f31f Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Sun, 30 May 2021 18:04:07 -0700 Subject: Implement the raw_eq intrinsic in codegen_cranelift --- .../rustc_codegen_cranelift/src/intrinsics/mod.rs | 39 ++++++++++++++++++++++ .../rustc_codegen_cranelift/src/value_and_place.rs | 6 ++++ 2 files changed, 45 insertions(+) (limited to 'compiler') diff --git a/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs b/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs index 52896fc7127..3e658cb1211 100644 --- a/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs +++ b/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs @@ -1115,6 +1115,45 @@ pub(crate) fn codegen_intrinsic_call<'tcx>( ); ret.write_cvalue(fx, CValue::by_val(res, ret.layout())); }; + + raw_eq, (v lhs_ref, v rhs_ref) { + fn type_by_size(size: Size) -> Option { + Some(match size.bits() { + 8 => types::I8, + 16 => types::I16, + 32 => types::I32, + 64 => types::I64, + 128 => types::I128, + _ => return None, + }) + } + + let size = fx.layout_of(T).layout.size; + let is_eq_value = + if size == Size::ZERO { + // No bytes means they're trivially equal + fx.bcx.ins().bconst(types::B1, true) + } else if let Some(clty) = type_by_size(size) { + // Can't use `trusted` for these loads; they could be unaligned. + let mut flags = MemFlags::new(); + flags.set_notrap(); + let lhs_val = fx.bcx.ins().load(clty, flags, lhs_ref, 0); + let rhs_val = fx.bcx.ins().load(clty, flags, rhs_ref, 0); + fx.bcx.ins().icmp(IntCC::Equal, lhs_val, rhs_val) + } else { + // Just call `memcmp` (like slices do in core) when the + // size is too large or it's not a power-of-two. + let ptr_ty = pointer_ty(fx.tcx); + let signed_bytes = i64::try_from(size.bytes()).unwrap(); + let bytes_val = fx.bcx.ins().iconst(ptr_ty, signed_bytes); + let params = vec![AbiParam::new(ptr_ty); 3]; + let returns = vec![AbiParam::new(types::I32)]; + let args = &[lhs_ref, rhs_ref, bytes_val]; + let cmp = fx.lib_call("memcmp", params, returns, args)[0]; + fx.bcx.ins().icmp_imm(IntCC::Equal, cmp, 0) + }; + ret.write_cvalue(fx, CValue::by_val(is_eq_value, ret.layout())); + }; } if let Some((_, dest)) = destination { diff --git a/compiler/rustc_codegen_cranelift/src/value_and_place.rs b/compiler/rustc_codegen_cranelift/src/value_and_place.rs index 171f39805f8..b6f5f5707fb 100644 --- a/compiler/rustc_codegen_cranelift/src/value_and_place.rs +++ b/compiler/rustc_codegen_cranelift/src/value_and_place.rs @@ -437,6 +437,12 @@ impl<'tcx> CPlace<'tcx> { | (types::F32, types::I32) | (types::I64, types::F64) | (types::F64, types::I64) => fx.bcx.ins().bitcast(dst_ty, data), + + // Widen an abstract SSA boolean to something that can be stored in memory + (types::B1, types::I8 | types::I16 | types::I32 | types::I64 | types::I128) => { + fx.bcx.ins().bint(dst_ty, data) + } + _ if src_ty.is_vector() && dst_ty.is_vector() => { fx.bcx.ins().raw_bitcast(dst_ty, data) } -- cgit 1.4.1-3-g733a5 From 3d2869c6ff6ca7bd28383db6831f68b2d0349b0a Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Mon, 31 May 2021 10:26:08 -0700 Subject: PR Feedback: Don't put SSA-only types in `CValue`s --- compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs | 8 +++++--- compiler/rustc_codegen_cranelift/src/value_and_place.rs | 10 ++++------ 2 files changed, 9 insertions(+), 9 deletions(-) (limited to 'compiler') diff --git a/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs b/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs index 3e658cb1211..31f7e0d4e37 100644 --- a/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs +++ b/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs @@ -1132,14 +1132,15 @@ pub(crate) fn codegen_intrinsic_call<'tcx>( let is_eq_value = if size == Size::ZERO { // No bytes means they're trivially equal - fx.bcx.ins().bconst(types::B1, true) + fx.bcx.ins().iconst(types::I8, 1) } else if let Some(clty) = type_by_size(size) { // Can't use `trusted` for these loads; they could be unaligned. let mut flags = MemFlags::new(); flags.set_notrap(); let lhs_val = fx.bcx.ins().load(clty, flags, lhs_ref, 0); let rhs_val = fx.bcx.ins().load(clty, flags, rhs_ref, 0); - fx.bcx.ins().icmp(IntCC::Equal, lhs_val, rhs_val) + let eq = fx.bcx.ins().icmp(IntCC::Equal, lhs_val, rhs_val); + fx.bcx.ins().bint(types::I8, eq) } else { // Just call `memcmp` (like slices do in core) when the // size is too large or it's not a power-of-two. @@ -1150,7 +1151,8 @@ pub(crate) fn codegen_intrinsic_call<'tcx>( let returns = vec![AbiParam::new(types::I32)]; let args = &[lhs_ref, rhs_ref, bytes_val]; let cmp = fx.lib_call("memcmp", params, returns, args)[0]; - fx.bcx.ins().icmp_imm(IntCC::Equal, cmp, 0) + let eq = fx.bcx.ins().icmp_imm(IntCC::Equal, cmp, 0); + fx.bcx.ins().bint(types::I8, eq) }; ret.write_cvalue(fx, CValue::by_val(is_eq_value, ret.layout())); }; diff --git a/compiler/rustc_codegen_cranelift/src/value_and_place.rs b/compiler/rustc_codegen_cranelift/src/value_and_place.rs index b6f5f5707fb..ae8ccc626b4 100644 --- a/compiler/rustc_codegen_cranelift/src/value_and_place.rs +++ b/compiler/rustc_codegen_cranelift/src/value_and_place.rs @@ -437,12 +437,6 @@ impl<'tcx> CPlace<'tcx> { | (types::F32, types::I32) | (types::I64, types::F64) | (types::F64, types::I64) => fx.bcx.ins().bitcast(dst_ty, data), - - // Widen an abstract SSA boolean to something that can be stored in memory - (types::B1, types::I8 | types::I16 | types::I32 | types::I64 | types::I128) => { - fx.bcx.ins().bint(dst_ty, data) - } - _ if src_ty.is_vector() && dst_ty.is_vector() => { fx.bcx.ins().raw_bitcast(dst_ty, data) } @@ -459,6 +453,10 @@ impl<'tcx> CPlace<'tcx> { ptr.store(fx, data, MemFlags::trusted()); ptr.load(fx, dst_ty, MemFlags::trusted()) } + + // `CValue`s should never contain SSA-only types, so if you ended + // up here having seen an error like `B1 -> I8`, then before + // calling `write_cvalue` you need to add a `bint` instruction. _ => unreachable!("write_cvalue_transmute: {:?} -> {:?}", src_ty, dst_ty), }; //fx.bcx.set_val_label(data, cranelift_codegen::ir::ValueLabel::new(var.index())); -- cgit 1.4.1-3-g733a5 From 6444f24a29d1b9868e5dba647daf8209499757f6 Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Tue, 1 Jun 2021 06:19:49 -0700 Subject: Use cranelift's `Type::int` instead of doing the match myself --- compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs | 9 +-------- 1 file changed, 1 insertion(+), 8 deletions(-) (limited to 'compiler') diff --git a/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs b/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs index 31f7e0d4e37..3979886e10c 100644 --- a/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs +++ b/compiler/rustc_codegen_cranelift/src/intrinsics/mod.rs @@ -1118,14 +1118,7 @@ pub(crate) fn codegen_intrinsic_call<'tcx>( raw_eq, (v lhs_ref, v rhs_ref) { fn type_by_size(size: Size) -> Option { - Some(match size.bits() { - 8 => types::I8, - 16 => types::I16, - 32 => types::I32, - 64 => types::I64, - 128 => types::I128, - _ => return None, - }) + Type::int(size.bits().try_into().ok()?) } let size = fx.layout_of(T).layout.size; -- cgit 1.4.1-3-g733a5 From 07fb5ee78f4f251637c5c4414982a8c6e32e186d Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Wed, 2 Jun 2021 23:35:30 -0700 Subject: Adjust the threshold to look at the ABI, not just the size --- compiler/rustc_codegen_llvm/src/intrinsic.rs | 36 ++++++++++++++++++---------- src/test/codegen/array-equality.rs | 12 ++++++++++ 2 files changed, 36 insertions(+), 12 deletions(-) (limited to 'compiler') diff --git a/compiler/rustc_codegen_llvm/src/intrinsic.rs b/compiler/rustc_codegen_llvm/src/intrinsic.rs index 615295e96e1..9a968659e2f 100644 --- a/compiler/rustc_codegen_llvm/src/intrinsic.rs +++ b/compiler/rustc_codegen_llvm/src/intrinsic.rs @@ -297,28 +297,40 @@ impl IntrinsicCallMethods<'tcx> for Builder<'a, 'll, 'tcx> { } sym::raw_eq => { + use abi::Abi::*; let tp_ty = substs.type_at(0); - let (size, align) = self.size_and_align_of(tp_ty); + let layout = self.layout_of(tp_ty).layout; + let use_integer_compare = match layout.abi { + Scalar(_) | ScalarPair(_, _) => true, + Uninhabited | Vector { .. } => false, + Aggregate { .. } => { + // For rusty ABIs, small aggregates are actually passed + // as `RegKind::Integer` (see `FnAbi::adjust_for_abi`), + // so we re-use that same threshold here. + layout.size <= self.data_layout().pointer_size * 2 + } + }; + let a = args[0].immediate(); let b = args[1].immediate(); - if size.bytes() == 0 { + if layout.size.bytes() == 0 { self.const_bool(true) - } else if size > self.data_layout().pointer_size * 4 { + } else if use_integer_compare { + let integer_ty = self.type_ix(layout.size.bits()); + let ptr_ty = self.type_ptr_to(integer_ty); + let a_ptr = self.bitcast(a, ptr_ty); + let a_val = self.load(a_ptr, layout.align.abi); + let b_ptr = self.bitcast(b, ptr_ty); + let b_val = self.load(b_ptr, layout.align.abi); + self.icmp(IntPredicate::IntEQ, a_val, b_val) + } else { let i8p_ty = self.type_i8p(); let a_ptr = self.bitcast(a, i8p_ty); let b_ptr = self.bitcast(b, i8p_ty); - let n = self.const_usize(size.bytes()); + let n = self.const_usize(layout.size.bytes()); let llfn = self.get_intrinsic("memcmp"); let cmp = self.call(llfn, &[a_ptr, b_ptr, n], None); self.icmp(IntPredicate::IntEQ, cmp, self.const_i32(0)) - } else { - let integer_ty = self.type_ix(size.bits()); - let ptr_ty = self.type_ptr_to(integer_ty); - let a_ptr = self.bitcast(a, ptr_ty); - let a_val = self.load(a_ptr, align); - let b_ptr = self.bitcast(b, ptr_ty); - let b_val = self.load(b_ptr, align); - self.icmp(IntPredicate::IntEQ, a_val, b_val) } } diff --git a/src/test/codegen/array-equality.rs b/src/test/codegen/array-equality.rs index aa56e32e26c..4b60fa4b0bf 100644 --- a/src/test/codegen/array-equality.rs +++ b/src/test/codegen/array-equality.rs @@ -23,6 +23,18 @@ pub fn array_eq_ref(a: &[u16; 6], b: &[u16; 6]) -> bool { a == b } +// CHECK-LABEL: @array_eq_value_still_passed_by_pointer +#[no_mangle] +pub fn array_eq_value_still_passed_by_pointer(a: [u16; 9], b: [u16; 9]) -> bool { + // CHECK-NEXT: start: + // CHECK-NEXT: bitcast + // CHECK-NEXT: bitcast + // CHECK-NEXT: %[[CMP:.+]] = tail call i32 @{{bcmp|memcmp}}(i8* nonnull dereferenceable(18) %{{.+}}, i8* nonnull dereferenceable(18) %{{.+}}, i64 18) + // CHECK-NEXT: %[[EQ:.+]] = icmp eq i32 %[[CMP]], 0 + // CHECK-NEXT: ret i1 %[[EQ]] + a == b +} + // CHECK-LABEL: @array_eq_long #[no_mangle] pub fn array_eq_long(a: &[u16; 1234], b: &[u16; 1234]) -> bool { -- cgit 1.4.1-3-g733a5