4 use gccjit::{ComparisonOp, Function, RValue, ToRValue, Type, UnaryOp, FunctionType};
5 use rustc_codegen_ssa::MemFlags;
6 use rustc_codegen_ssa::base::wants_msvc_seh;
7 use rustc_codegen_ssa::common::IntPredicate;
8 use rustc_codegen_ssa::mir::operand::{OperandRef, OperandValue};
9 use rustc_codegen_ssa::mir::place::PlaceRef;
10 use rustc_codegen_ssa::traits::{ArgAbiMethods, BaseTypeMethods, BuilderMethods, ConstMethods, IntrinsicCallMethods};
11 use rustc_middle::bug;
12 use rustc_middle::ty::{self, Instance, Ty};
13 use rustc_middle::ty::layout::LayoutOf;
14 use rustc_span::{Span, Symbol, symbol::kw, sym};
15 use rustc_target::abi::HasDataLayout;
16 use rustc_target::abi::call::{ArgAbi, FnAbi, PassMode};
17 use rustc_target::spec::PanicStrategy;
19 use crate::abi::GccType;
20 use crate::builder::Builder;
21 use crate::common::{SignType, TypeReflection};
22 use crate::context::CodegenCx;
23 use crate::errors::InvalidMonomorphizationBasicInteger;
24 use crate::type_of::LayoutGccExt;
25 use crate::intrinsic::simd::generic_simd_intrinsic;
27 fn get_simple_intrinsic<'gcc, 'tcx>(cx: &CodegenCx<'gcc, 'tcx>, name: Symbol) -> Option<Function<'gcc>> {
28 let gcc_name = match name {
29 sym::sqrtf32 => "sqrtf",
30 sym::sqrtf64 => "sqrt",
31 sym::powif32 => "__builtin_powif",
32 sym::powif64 => "__builtin_powi",
33 sym::sinf32 => "sinf",
35 sym::cosf32 => "cosf",
37 sym::powf32 => "powf",
39 sym::expf32 => "expf",
41 sym::exp2f32 => "exp2f",
42 sym::exp2f64 => "exp2",
43 sym::logf32 => "logf",
45 sym::log10f32 => "log10f",
46 sym::log10f64 => "log10",
47 sym::log2f32 => "log2f",
48 sym::log2f64 => "log2",
49 sym::fmaf32 => "fmaf",
51 sym::fabsf32 => "fabsf",
52 sym::fabsf64 => "fabs",
53 sym::minnumf32 => "fminf",
54 sym::minnumf64 => "fmin",
55 sym::maxnumf32 => "fmaxf",
56 sym::maxnumf64 => "fmax",
57 sym::copysignf32 => "copysignf",
58 sym::copysignf64 => "copysign",
59 sym::floorf32 => "floorf",
60 sym::floorf64 => "floor",
61 sym::ceilf32 => "ceilf",
62 sym::ceilf64 => "ceil",
63 sym::truncf32 => "truncf",
64 sym::truncf64 => "trunc",
65 sym::rintf32 => "rintf",
66 sym::rintf64 => "rint",
67 sym::nearbyintf32 => "nearbyintf",
68 sym::nearbyintf64 => "nearbyint",
69 sym::roundf32 => "roundf",
70 sym::roundf64 => "round",
71 sym::abort => "abort",
74 Some(cx.context.get_builtin_function(&gcc_name))
77 impl<'a, 'gcc, 'tcx> IntrinsicCallMethods<'tcx> for Builder<'a, 'gcc, 'tcx> {
78 fn codegen_intrinsic_call(&mut self, instance: Instance<'tcx>, fn_abi: &FnAbi<'tcx, Ty<'tcx>>, args: &[OperandRef<'tcx, RValue<'gcc>>], llresult: RValue<'gcc>, span: Span) {
80 let callee_ty = instance.ty(tcx, ty::ParamEnv::reveal_all());
82 let (def_id, substs) = match *callee_ty.kind() {
83 ty::FnDef(def_id, substs) => (def_id, substs),
84 _ => bug!("expected fn item type, found {}", callee_ty),
87 let sig = callee_ty.fn_sig(tcx);
88 let sig = tcx.normalize_erasing_late_bound_regions(ty::ParamEnv::reveal_all(), sig);
89 let arg_tys = sig.inputs();
90 let ret_ty = sig.output();
91 let name = tcx.item_name(def_id);
92 let name_str = name.as_str();
94 let llret_ty = self.layout_of(ret_ty).gcc_type(self, true);
95 let result = PlaceRef::new_sized(llresult, fn_abi.ret.layout);
97 let simple = get_simple_intrinsic(self, name);
100 _ if simple.is_some() => {
101 // FIXME(antoyo): remove this cast when the API supports function.
102 let func = unsafe { std::mem::transmute(simple.expect("simple")) };
103 self.call(self.type_void(), None, func, &args.iter().map(|arg| arg.immediate()).collect::<Vec<_>>(), None)
106 self.expect(args[0].immediate(), true)
109 self.expect(args[0].immediate(), false)
131 sym::volatile_load | sym::unaligned_volatile_load => {
132 let tp_ty = substs.type_at(0);
133 let mut ptr = args[0].immediate();
134 if let PassMode::Cast(ty, _) = &fn_abi.ret.mode {
135 ptr = self.pointercast(ptr, self.type_ptr_to(ty.gcc_type(self)));
137 let load = self.volatile_load(ptr.get_type(), ptr);
138 // TODO(antoyo): set alignment.
139 self.to_immediate(load, self.layout_of(tp_ty))
141 sym::volatile_store => {
142 let dst = args[0].deref(self.cx());
143 args[1].val.volatile_store(self, dst);
146 sym::unaligned_volatile_store => {
147 let dst = args[0].deref(self.cx());
148 args[1].val.unaligned_volatile_store(self, dst);
151 sym::prefetch_read_data
152 | sym::prefetch_write_data
153 | sym::prefetch_read_instruction
154 | sym::prefetch_write_instruction => {
166 | sym::saturating_add
167 | sym::saturating_sub => {
169 match int_type_width_signed(ty, self) {
170 Some((width, signed)) => match name {
171 sym::ctlz | sym::cttz => {
172 let func = self.current_func.borrow().expect("func");
173 let then_block = func.new_block("then");
174 let else_block = func.new_block("else");
175 let after_block = func.new_block("after");
177 let arg = args[0].immediate();
178 let result = func.new_local(None, arg.get_type(), "zeros");
179 let zero = self.cx.gcc_zero(arg.get_type());
180 let cond = self.gcc_icmp(IntPredicate::IntEQ, arg, zero);
181 self.llbb().end_with_conditional(None, cond, then_block, else_block);
183 let zero_result = self.cx.gcc_uint(arg.get_type(), width);
184 then_block.add_assignment(None, result, zero_result);
185 then_block.end_with_jump(None, after_block);
187 // NOTE: since jumps were added in a place
188 // count_leading_zeroes() does not expect, the current block
189 // in the state need to be updated.
190 self.switch_to_block(else_block);
194 sym::ctlz => self.count_leading_zeroes(width, arg),
195 sym::cttz => self.count_trailing_zeroes(width, arg),
198 self.llbb().add_assignment(None, result, zeros);
199 self.llbb().end_with_jump(None, after_block);
201 // NOTE: since jumps were added in a place rustc does not
202 // expect, the current block in the state need to be updated.
203 self.switch_to_block(after_block);
207 sym::ctlz_nonzero => {
208 self.count_leading_zeroes(width, args[0].immediate())
210 sym::cttz_nonzero => {
211 self.count_trailing_zeroes(width, args[0].immediate())
213 sym::ctpop => self.pop_count(args[0].immediate()),
216 args[0].immediate() // byte swap a u8/i8 is just a no-op
219 self.gcc_bswap(args[0].immediate(), width)
222 sym::bitreverse => self.bit_reverse(width, args[0].immediate()),
223 sym::rotate_left | sym::rotate_right => {
224 // TODO(antoyo): implement using algorithm from:
225 // https://blog.regehr.org/archives/1063
226 // for other platforms.
227 let is_left = name == sym::rotate_left;
228 let val = args[0].immediate();
229 let raw_shift = args[1].immediate();
231 self.rotate_left(val, raw_shift, width)
234 self.rotate_right(val, raw_shift, width)
237 sym::saturating_add => {
238 self.saturating_add(args[0].immediate(), args[1].immediate(), signed, width)
240 sym::saturating_sub => {
241 self.saturating_sub(args[0].immediate(), args[1].immediate(), signed, width)
246 tcx.sess.emit_err(InvalidMonomorphizationBasicInteger { span, name, ty });
253 use rustc_target::abi::Abi::*;
254 let tp_ty = substs.type_at(0);
255 let layout = self.layout_of(tp_ty).layout;
256 let _use_integer_compare = match layout.abi() {
257 Scalar(_) | ScalarPair(_, _) => true,
258 Uninhabited | Vector { .. } => false,
259 Aggregate { .. } => {
260 // For rusty ABIs, small aggregates are actually passed
261 // as `RegKind::Integer` (see `FnAbi::adjust_for_abi`),
262 // so we re-use that same threshold here.
263 layout.size() <= self.data_layout().pointer_size * 2
267 let a = args[0].immediate();
268 let b = args[1].immediate();
269 if layout.size().bytes() == 0 {
270 self.const_bool(true)
272 /*else if use_integer_compare {
273 let integer_ty = self.type_ix(layout.size.bits()); // FIXME(antoyo): LLVM creates an integer of 96 bits for [i32; 3], but gcc doesn't support this, so it creates an integer of 128 bits.
274 let ptr_ty = self.type_ptr_to(integer_ty);
275 let a_ptr = self.bitcast(a, ptr_ty);
276 let a_val = self.load(integer_ty, a_ptr, layout.align.abi);
277 let b_ptr = self.bitcast(b, ptr_ty);
278 let b_val = self.load(integer_ty, b_ptr, layout.align.abi);
279 self.icmp(IntPredicate::IntEQ, a_val, b_val)
282 let void_ptr_type = self.context.new_type::<*const ()>();
283 let a_ptr = self.bitcast(a, void_ptr_type);
284 let b_ptr = self.bitcast(b, void_ptr_type);
285 let n = self.context.new_cast(None, self.const_usize(layout.size().bytes()), self.sizet_type);
286 let builtin = self.context.get_builtin_function("memcmp");
287 let cmp = self.context.new_call(None, builtin, &[a_ptr, b_ptr, n]);
288 self.icmp(IntPredicate::IntEQ, cmp, self.const_i32(0))
293 args[0].val.store(self, result);
295 let block = self.llbb();
296 let extended_asm = block.add_extended_asm(None, "");
297 extended_asm.add_input_operand(None, "r", result.llval);
298 extended_asm.add_clobber("memory");
299 extended_asm.set_volatile_flag(true);
301 // We have copied the value to `result` already.
306 let usize_type = self.context.new_type::<usize>();
307 let void_ptr_type = self.context.new_type::<*const ()>();
309 let ptr = args[0].immediate();
310 let mask = args[1].immediate();
312 let addr = self.bitcast(ptr, usize_type);
313 let masked = self.and(addr, mask);
314 self.bitcast(masked, void_ptr_type)
317 _ if name_str.starts_with("simd_") => {
318 match generic_simd_intrinsic(self, name, callee_ty, args, ret_ty, llret_ty, span) {
324 _ => bug!("unknown intrinsic '{}'", name),
327 if !fn_abi.ret.is_ignore() {
328 if let PassMode::Cast(ty, _) = &fn_abi.ret.mode {
329 let ptr_llty = self.type_ptr_to(ty.gcc_type(self));
330 let ptr = self.pointercast(result.llval, ptr_llty);
331 self.store(llval, ptr, result.align);
334 OperandRef::from_immediate_or_packed_pair(self, llval, result.layout)
336 .store(self, result);
341 fn abort(&mut self) {
342 let func = self.context.get_builtin_function("abort");
343 let func: RValue<'gcc> = unsafe { std::mem::transmute(func) };
344 self.call(self.type_void(), None, func, &[], None);
347 fn assume(&mut self, value: Self::Value) {
348 // TODO(antoyo): switch to assume when it exists.
349 // Or use something like this:
350 // #define __assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
351 self.expect(value, true);
354 fn expect(&mut self, cond: Self::Value, _expected: bool) -> Self::Value {
359 fn type_test(&mut self, _pointer: Self::Value, _typeid: Self::Value) -> Self::Value {
361 self.context.new_rvalue_from_int(self.int_type, 0)
364 fn type_checked_load(
366 _llvtable: Self::Value,
367 _vtable_byte_offset: u64,
368 _typeid: Self::Value,
371 self.context.new_rvalue_from_int(self.int_type, 0)
374 fn va_start(&mut self, _va_list: RValue<'gcc>) -> RValue<'gcc> {
378 fn va_end(&mut self, _va_list: RValue<'gcc>) -> RValue<'gcc> {
383 impl<'a, 'gcc, 'tcx> ArgAbiMethods<'tcx> for Builder<'a, 'gcc, 'tcx> {
384 fn store_fn_arg(&mut self, arg_abi: &ArgAbi<'tcx, Ty<'tcx>>, idx: &mut usize, dst: PlaceRef<'tcx, Self::Value>) {
385 arg_abi.store_fn_arg(self, idx, dst)
388 fn store_arg(&mut self, arg_abi: &ArgAbi<'tcx, Ty<'tcx>>, val: RValue<'gcc>, dst: PlaceRef<'tcx, RValue<'gcc>>) {
389 arg_abi.store(self, val, dst)
392 fn arg_memory_ty(&self, arg_abi: &ArgAbi<'tcx, Ty<'tcx>>) -> Type<'gcc> {
393 arg_abi.memory_ty(self)
397 pub trait ArgAbiExt<'gcc, 'tcx> {
398 fn memory_ty(&self, cx: &CodegenCx<'gcc, 'tcx>) -> Type<'gcc>;
399 fn store(&self, bx: &mut Builder<'_, 'gcc, 'tcx>, val: RValue<'gcc>, dst: PlaceRef<'tcx, RValue<'gcc>>);
400 fn store_fn_arg(&self, bx: &mut Builder<'_, 'gcc, 'tcx>, idx: &mut usize, dst: PlaceRef<'tcx, RValue<'gcc>>);
403 impl<'gcc, 'tcx> ArgAbiExt<'gcc, 'tcx> for ArgAbi<'tcx, Ty<'tcx>> {
404 /// Gets the LLVM type for a place of the original Rust type of
405 /// this argument/return, i.e., the result of `type_of::type_of`.
406 fn memory_ty(&self, cx: &CodegenCx<'gcc, 'tcx>) -> Type<'gcc> {
407 self.layout.gcc_type(cx, true)
410 /// Stores a direct/indirect value described by this ArgAbi into a
411 /// place for the original Rust type of this argument/return.
412 /// Can be used for both storing formal arguments into Rust variables
413 /// or results of call/invoke instructions into their destinations.
414 fn store(&self, bx: &mut Builder<'_, 'gcc, 'tcx>, val: RValue<'gcc>, dst: PlaceRef<'tcx, RValue<'gcc>>) {
415 if self.is_ignore() {
418 if self.is_sized_indirect() {
419 OperandValue::Ref(val, None, self.layout.align.abi).store(bx, dst)
421 else if self.is_unsized_indirect() {
422 bug!("unsized `ArgAbi` must be handled through `store_fn_arg`");
424 else if let PassMode::Cast(ref cast, _) = self.mode {
425 // FIXME(eddyb): Figure out when the simpler Store is safe, clang
426 // uses it for i16 -> {i8, i8}, but not for i24 -> {i8, i8, i8}.
427 let can_store_through_cast_ptr = false;
428 if can_store_through_cast_ptr {
429 let cast_ptr_llty = bx.type_ptr_to(cast.gcc_type(bx));
430 let cast_dst = bx.pointercast(dst.llval, cast_ptr_llty);
431 bx.store(val, cast_dst, self.layout.align.abi);
434 // The actual return type is a struct, but the ABI
435 // adaptation code has cast it into some scalar type. The
436 // code that follows is the only reliable way I have
437 // found to do a transform like i64 -> {i32,i32}.
438 // Basically we dump the data onto the stack then memcpy it.
440 // Other approaches I tried:
441 // - Casting rust ret pointer to the foreign type and using Store
442 // is (a) unsafe if size of foreign type > size of rust type and
443 // (b) runs afoul of strict aliasing rules, yielding invalid
444 // assembly under -O (specifically, the store gets removed).
445 // - Truncating foreign type to correct integral type and then
446 // bitcasting to the struct type yields invalid cast errors.
448 // We instead thus allocate some scratch space...
449 let scratch_size = cast.size(bx);
450 let scratch_align = cast.align(bx);
451 let llscratch = bx.alloca(cast.gcc_type(bx), scratch_align);
452 bx.lifetime_start(llscratch, scratch_size);
454 // ... where we first store the value...
455 bx.store(val, llscratch, scratch_align);
457 // ... and then memcpy it to the intended destination.
460 self.layout.align.abi,
463 bx.const_usize(self.layout.size.bytes()),
467 bx.lifetime_end(llscratch, scratch_size);
471 OperandValue::Immediate(val).store(bx, dst);
475 fn store_fn_arg<'a>(&self, bx: &mut Builder<'a, 'gcc, 'tcx>, idx: &mut usize, dst: PlaceRef<'tcx, RValue<'gcc>>) {
477 let val = bx.current_func().get_param(*idx as i32);
482 PassMode::Ignore => {},
483 PassMode::Pair(..) => {
484 OperandValue::Pair(next(), next()).store(bx, dst);
486 PassMode::Indirect { extra_attrs: Some(_), .. } => {
487 OperandValue::Ref(next(), Some(next()), self.layout.align.abi).store(bx, dst);
489 PassMode::Direct(_) | PassMode::Indirect { extra_attrs: None, .. } | PassMode::Cast(..) => {
490 let next_arg = next();
491 self.store(bx, next_arg, dst);
497 fn int_type_width_signed<'gcc, 'tcx>(ty: Ty<'tcx>, cx: &CodegenCx<'gcc, 'tcx>) -> Option<(u64, bool)> {
501 rustc_middle::ty::IntTy::Isize => u64::from(cx.tcx.sess.target.pointer_width),
502 rustc_middle::ty::IntTy::I8 => 8,
503 rustc_middle::ty::IntTy::I16 => 16,
504 rustc_middle::ty::IntTy::I32 => 32,
505 rustc_middle::ty::IntTy::I64 => 64,
506 rustc_middle::ty::IntTy::I128 => 128,
510 ty::Uint(t) => Some((
512 rustc_middle::ty::UintTy::Usize => u64::from(cx.tcx.sess.target.pointer_width),
513 rustc_middle::ty::UintTy::U8 => 8,
514 rustc_middle::ty::UintTy::U16 => 16,
515 rustc_middle::ty::UintTy::U32 => 32,
516 rustc_middle::ty::UintTy::U64 => 64,
517 rustc_middle::ty::UintTy::U128 => 128,
525 impl<'a, 'gcc, 'tcx> Builder<'a, 'gcc, 'tcx> {
526 fn bit_reverse(&mut self, width: u64, value: RValue<'gcc>) -> RValue<'gcc> {
527 let result_type = value.get_type();
528 let typ = result_type.to_unsigned(self.cx);
531 if result_type.is_signed(self.cx) {
532 self.gcc_int_cast(value, typ)
538 let context = &self.cx.context;
543 let left = self.and(value, context.new_rvalue_from_int(typ, 0xF0));
544 let left = self.lshr(left, context.new_rvalue_from_int(typ, 4));
545 let right = self.and(value, context.new_rvalue_from_int(typ, 0x0F));
546 let right = self.shl(right, context.new_rvalue_from_int(typ, 4));
547 let step1 = self.or(left, right);
550 let left = self.and(step1, context.new_rvalue_from_int(typ, 0xCC));
551 let left = self.lshr(left, context.new_rvalue_from_int(typ, 2));
552 let right = self.and(step1, context.new_rvalue_from_int(typ, 0x33));
553 let right = self.shl(right, context.new_rvalue_from_int(typ, 2));
554 let step2 = self.or(left, right);
557 let left = self.and(step2, context.new_rvalue_from_int(typ, 0xAA));
558 let left = self.lshr(left, context.new_rvalue_from_int(typ, 1));
559 let right = self.and(step2, context.new_rvalue_from_int(typ, 0x55));
560 let right = self.shl(right, context.new_rvalue_from_int(typ, 1));
561 let step3 = self.or(left, right);
567 let left = self.and(value, context.new_rvalue_from_int(typ, 0x5555));
568 let left = self.shl(left, context.new_rvalue_from_int(typ, 1));
569 let right = self.and(value, context.new_rvalue_from_int(typ, 0xAAAA));
570 let right = self.lshr(right, context.new_rvalue_from_int(typ, 1));
571 let step1 = self.or(left, right);
574 let left = self.and(step1, context.new_rvalue_from_int(typ, 0x3333));
575 let left = self.shl(left, context.new_rvalue_from_int(typ, 2));
576 let right = self.and(step1, context.new_rvalue_from_int(typ, 0xCCCC));
577 let right = self.lshr(right, context.new_rvalue_from_int(typ, 2));
578 let step2 = self.or(left, right);
581 let left = self.and(step2, context.new_rvalue_from_int(typ, 0x0F0F));
582 let left = self.shl(left, context.new_rvalue_from_int(typ, 4));
583 let right = self.and(step2, context.new_rvalue_from_int(typ, 0xF0F0));
584 let right = self.lshr(right, context.new_rvalue_from_int(typ, 4));
585 let step3 = self.or(left, right);
588 let left = self.and(step3, context.new_rvalue_from_int(typ, 0x00FF));
589 let left = self.shl(left, context.new_rvalue_from_int(typ, 8));
590 let right = self.and(step3, context.new_rvalue_from_int(typ, 0xFF00));
591 let right = self.lshr(right, context.new_rvalue_from_int(typ, 8));
592 let step4 = self.or(left, right);
597 // TODO(antoyo): Refactor with other implementations.
599 let left = self.and(value, context.new_rvalue_from_long(typ, 0x55555555));
600 let left = self.shl(left, context.new_rvalue_from_long(typ, 1));
601 let right = self.and(value, context.new_rvalue_from_long(typ, 0xAAAAAAAA));
602 let right = self.lshr(right, context.new_rvalue_from_long(typ, 1));
603 let step1 = self.or(left, right);
606 let left = self.and(step1, context.new_rvalue_from_long(typ, 0x33333333));
607 let left = self.shl(left, context.new_rvalue_from_long(typ, 2));
608 let right = self.and(step1, context.new_rvalue_from_long(typ, 0xCCCCCCCC));
609 let right = self.lshr(right, context.new_rvalue_from_long(typ, 2));
610 let step2 = self.or(left, right);
613 let left = self.and(step2, context.new_rvalue_from_long(typ, 0x0F0F0F0F));
614 let left = self.shl(left, context.new_rvalue_from_long(typ, 4));
615 let right = self.and(step2, context.new_rvalue_from_long(typ, 0xF0F0F0F0));
616 let right = self.lshr(right, context.new_rvalue_from_long(typ, 4));
617 let step3 = self.or(left, right);
620 let left = self.and(step3, context.new_rvalue_from_long(typ, 0x00FF00FF));
621 let left = self.shl(left, context.new_rvalue_from_long(typ, 8));
622 let right = self.and(step3, context.new_rvalue_from_long(typ, 0xFF00FF00));
623 let right = self.lshr(right, context.new_rvalue_from_long(typ, 8));
624 let step4 = self.or(left, right);
627 let left = self.and(step4, context.new_rvalue_from_long(typ, 0x0000FFFF));
628 let left = self.shl(left, context.new_rvalue_from_long(typ, 16));
629 let right = self.and(step4, context.new_rvalue_from_long(typ, 0xFFFF0000));
630 let right = self.lshr(right, context.new_rvalue_from_long(typ, 16));
631 let step5 = self.or(left, right);
637 let left = self.shl(value, context.new_rvalue_from_long(typ, 32));
638 let right = self.lshr(value, context.new_rvalue_from_long(typ, 32));
639 let step1 = self.or(left, right);
642 let left = self.and(step1, context.new_rvalue_from_long(typ, 0x0001FFFF0001FFFF));
643 let left = self.shl(left, context.new_rvalue_from_long(typ, 15));
644 let right = self.and(step1, context.new_rvalue_from_long(typ, 0xFFFE0000FFFE0000u64 as i64)); // TODO(antoyo): transmute the number instead?
645 let right = self.lshr(right, context.new_rvalue_from_long(typ, 17));
646 let step2 = self.or(left, right);
649 let left = self.lshr(step2, context.new_rvalue_from_long(typ, 10));
650 let left = self.xor(step2, left);
651 let temp = self.and(left, context.new_rvalue_from_long(typ, 0x003F801F003F801F));
653 let left = self.shl(temp, context.new_rvalue_from_long(typ, 10));
654 let left = self.or(temp, left);
655 let step3 = self.xor(left, step2);
658 let left = self.lshr(step3, context.new_rvalue_from_long(typ, 4));
659 let left = self.xor(step3, left);
660 let temp = self.and(left, context.new_rvalue_from_long(typ, 0x0E0384210E038421));
662 let left = self.shl(temp, context.new_rvalue_from_long(typ, 4));
663 let left = self.or(temp, left);
664 let step4 = self.xor(left, step3);
667 let left = self.lshr(step4, context.new_rvalue_from_long(typ, 2));
668 let left = self.xor(step4, left);
669 let temp = self.and(left, context.new_rvalue_from_long(typ, 0x2248884222488842));
671 let left = self.shl(temp, context.new_rvalue_from_long(typ, 2));
672 let left = self.or(temp, left);
673 let step5 = self.xor(left, step4);
678 // TODO(antoyo): find a more efficient implementation?
679 let sixty_four = self.gcc_int(typ, 64);
680 let right_shift = self.gcc_lshr(value, sixty_four);
681 let high = self.gcc_int_cast(right_shift, self.u64_type);
682 let low = self.gcc_int_cast(value, self.u64_type);
684 let reversed_high = self.bit_reverse(64, high);
685 let reversed_low = self.bit_reverse(64, low);
687 let new_low = self.gcc_int_cast(reversed_high, typ);
688 let new_high = self.shl(self.gcc_int_cast(reversed_low, typ), sixty_four);
690 self.gcc_or(new_low, new_high)
693 panic!("cannot bit reverse with width = {}", width);
697 self.gcc_int_cast(result, result_type)
700 fn count_leading_zeroes(&mut self, width: u64, arg: RValue<'gcc>) -> RValue<'gcc> {
701 // TODO(antoyo): use width?
702 let arg_type = arg.get_type();
703 let count_leading_zeroes =
704 // TODO(antoyo): write a new function Type::is_compatible_with(&Type) and use it here
705 // instead of using is_uint().
706 if arg_type.is_uint(&self.cx) {
709 else if arg_type.is_ulong(&self.cx) {
712 else if arg_type.is_ulonglong(&self.cx) {
715 else if width == 128 {
716 // Algorithm from: https://stackoverflow.com/a/28433850/389119
717 let array_type = self.context.new_array_type(None, arg_type, 3);
718 let result = self.current_func()
719 .new_local(None, array_type, "count_loading_zeroes_results");
721 let sixty_four = self.const_uint(arg_type, 64);
722 let shift = self.lshr(arg, sixty_four);
723 let high = self.gcc_int_cast(shift, self.u64_type);
724 let low = self.gcc_int_cast(arg, self.u64_type);
726 let zero = self.context.new_rvalue_zero(self.usize_type);
727 let one = self.context.new_rvalue_one(self.usize_type);
728 let two = self.context.new_rvalue_from_long(self.usize_type, 2);
730 let clzll = self.context.get_builtin_function("__builtin_clzll");
732 let first_elem = self.context.new_array_access(None, result, zero);
733 let first_value = self.gcc_int_cast(self.context.new_call(None, clzll, &[high]), arg_type);
735 .add_assignment(None, first_elem, first_value);
737 let second_elem = self.context.new_array_access(None, result, one);
738 let cast = self.gcc_int_cast(self.context.new_call(None, clzll, &[low]), arg_type);
739 let second_value = self.add(cast, sixty_four);
741 .add_assignment(None, second_elem, second_value);
743 let third_elem = self.context.new_array_access(None, result, two);
744 let third_value = self.const_uint(arg_type, 128);
746 .add_assignment(None, third_elem, third_value);
748 let not_high = self.context.new_unary_op(None, UnaryOp::LogicalNegate, self.u64_type, high);
749 let not_low = self.context.new_unary_op(None, UnaryOp::LogicalNegate, self.u64_type, low);
750 let not_low_and_not_high = not_low & not_high;
751 let index = not_high + not_low_and_not_high;
752 // NOTE: the following cast is necessary to avoid a GIMPLE verification failure in
754 // TODO(antoyo): do the correct verification in libgccjit to avoid an error at the
755 // compilation stage.
756 let index = self.context.new_cast(None, index, self.i32_type);
758 let res = self.context.new_array_access(None, result, index);
760 return self.gcc_int_cast(res.to_rvalue(), arg_type);
763 let count_leading_zeroes = self.context.get_builtin_function("__builtin_clzll");
764 let arg = self.context.new_cast(None, arg, self.ulonglong_type);
765 let diff = self.ulonglong_type.get_size() as i64 - arg_type.get_size() as i64;
766 let diff = self.context.new_rvalue_from_long(self.int_type, diff * 8);
767 let res = self.context.new_call(None, count_leading_zeroes, &[arg]) - diff;
768 return self.context.new_cast(None, res, arg_type);
770 let count_leading_zeroes = self.context.get_builtin_function(count_leading_zeroes);
771 let res = self.context.new_call(None, count_leading_zeroes, &[arg]);
772 self.context.new_cast(None, res, arg_type)
775 fn count_trailing_zeroes(&mut self, _width: u64, arg: RValue<'gcc>) -> RValue<'gcc> {
776 let result_type = arg.get_type();
778 if result_type.is_signed(self.cx) {
779 let new_type = result_type.to_unsigned(self.cx);
780 self.gcc_int_cast(arg, new_type)
785 let arg_type = arg.get_type();
786 let (count_trailing_zeroes, expected_type) =
787 // TODO(antoyo): write a new function Type::is_compatible_with(&Type) and use it here
788 // instead of using is_uint().
789 if arg_type.is_uchar(&self.cx) || arg_type.is_ushort(&self.cx) || arg_type.is_uint(&self.cx) {
790 // NOTE: we don't need to & 0xFF for uchar because the result is undefined on zero.
791 ("__builtin_ctz", self.cx.uint_type)
793 else if arg_type.is_ulong(&self.cx) {
794 ("__builtin_ctzl", self.cx.ulong_type)
796 else if arg_type.is_ulonglong(&self.cx) {
797 ("__builtin_ctzll", self.cx.ulonglong_type)
799 else if arg_type.is_u128(&self.cx) {
800 // Adapted from the algorithm to count leading zeroes from: https://stackoverflow.com/a/28433850/389119
801 let array_type = self.context.new_array_type(None, arg_type, 3);
802 let result = self.current_func()
803 .new_local(None, array_type, "count_loading_zeroes_results");
805 let sixty_four = self.gcc_int(arg_type, 64);
806 let shift = self.gcc_lshr(arg, sixty_four);
807 let high = self.gcc_int_cast(shift, self.u64_type);
808 let low = self.gcc_int_cast(arg, self.u64_type);
810 let zero = self.context.new_rvalue_zero(self.usize_type);
811 let one = self.context.new_rvalue_one(self.usize_type);
812 let two = self.context.new_rvalue_from_long(self.usize_type, 2);
814 let ctzll = self.context.get_builtin_function("__builtin_ctzll");
816 let first_elem = self.context.new_array_access(None, result, zero);
817 let first_value = self.gcc_int_cast(self.context.new_call(None, ctzll, &[low]), arg_type);
819 .add_assignment(None, first_elem, first_value);
821 let second_elem = self.context.new_array_access(None, result, one);
822 let second_value = self.gcc_add(self.gcc_int_cast(self.context.new_call(None, ctzll, &[high]), arg_type), sixty_four);
824 .add_assignment(None, second_elem, second_value);
826 let third_elem = self.context.new_array_access(None, result, two);
827 let third_value = self.gcc_int(arg_type, 128);
829 .add_assignment(None, third_elem, third_value);
831 let not_low = self.context.new_unary_op(None, UnaryOp::LogicalNegate, self.u64_type, low);
832 let not_high = self.context.new_unary_op(None, UnaryOp::LogicalNegate, self.u64_type, high);
833 let not_low_and_not_high = not_low & not_high;
834 let index = not_low + not_low_and_not_high;
835 // NOTE: the following cast is necessary to avoid a GIMPLE verification failure in
837 // TODO(antoyo): do the correct verification in libgccjit to avoid an error at the
838 // compilation stage.
839 let index = self.context.new_cast(None, index, self.i32_type);
841 let res = self.context.new_array_access(None, result, index);
843 return self.gcc_int_cast(res.to_rvalue(), result_type);
846 let count_trailing_zeroes = self.context.get_builtin_function("__builtin_ctzll");
847 let arg_size = arg_type.get_size();
848 let casted_arg = self.context.new_cast(None, arg, self.ulonglong_type);
849 let byte_diff = self.ulonglong_type.get_size() as i64 - arg_size as i64;
850 let diff = self.context.new_rvalue_from_long(self.int_type, byte_diff * 8);
851 let mask = self.context.new_rvalue_from_long(arg_type, -1); // To get the value with all bits set.
852 let masked = mask & self.context.new_unary_op(None, UnaryOp::BitwiseNegate, arg_type, arg);
853 let cond = self.context.new_comparison(None, ComparisonOp::Equals, masked, mask);
854 let diff = diff * self.context.new_cast(None, cond, self.int_type);
855 let res = self.context.new_call(None, count_trailing_zeroes, &[casted_arg]) - diff;
856 return self.context.new_cast(None, res, result_type);
858 let count_trailing_zeroes = self.context.get_builtin_function(count_trailing_zeroes);
860 if arg_type != expected_type {
861 self.context.new_cast(None, arg, expected_type)
866 let res = self.context.new_call(None, count_trailing_zeroes, &[arg]);
867 self.context.new_cast(None, res, result_type)
870 fn pop_count(&mut self, value: RValue<'gcc>) -> RValue<'gcc> {
871 // TODO(antoyo): use the optimized version with fewer operations.
872 let result_type = value.get_type();
873 let value_type = result_type.to_unsigned(self.cx);
876 if result_type.is_signed(self.cx) {
877 self.gcc_int_cast(value, value_type)
883 if value_type.is_u128(&self.cx) {
884 // TODO(antoyo): implement in the normal algorithm below to have a more efficient
885 // implementation (that does not require a call to __popcountdi2).
886 let popcount = self.context.get_builtin_function("__builtin_popcountll");
887 let sixty_four = self.gcc_int(value_type, 64);
888 let right_shift = self.gcc_lshr(value, sixty_four);
889 let high = self.gcc_int_cast(right_shift, self.cx.ulonglong_type);
890 let high = self.context.new_call(None, popcount, &[high]);
891 let low = self.gcc_int_cast(value, self.cx.ulonglong_type);
892 let low = self.context.new_call(None, popcount, &[low]);
893 let res = high + low;
894 return self.gcc_int_cast(res, result_type);
898 let mask = self.context.new_rvalue_from_long(value_type, 0x5555555555555555);
899 let left = value & mask;
900 let shifted = value >> self.context.new_rvalue_from_int(value_type, 1);
901 let right = shifted & mask;
902 let value = left + right;
905 let mask = self.context.new_rvalue_from_long(value_type, 0x3333333333333333);
906 let left = value & mask;
907 let shifted = value >> self.context.new_rvalue_from_int(value_type, 2);
908 let right = shifted & mask;
909 let value = left + right;
912 let mask = self.context.new_rvalue_from_long(value_type, 0x0F0F0F0F0F0F0F0F);
913 let left = value & mask;
914 let shifted = value >> self.context.new_rvalue_from_int(value_type, 4);
915 let right = shifted & mask;
916 let value = left + right;
918 if value_type.is_u8(&self.cx) {
919 return self.context.new_cast(None, value, result_type);
923 let mask = self.context.new_rvalue_from_long(value_type, 0x00FF00FF00FF00FF);
924 let left = value & mask;
925 let shifted = value >> self.context.new_rvalue_from_int(value_type, 8);
926 let right = shifted & mask;
927 let value = left + right;
929 if value_type.is_u16(&self.cx) {
930 return self.context.new_cast(None, value, result_type);
934 let mask = self.context.new_rvalue_from_long(value_type, 0x0000FFFF0000FFFF);
935 let left = value & mask;
936 let shifted = value >> self.context.new_rvalue_from_int(value_type, 16);
937 let right = shifted & mask;
938 let value = left + right;
940 if value_type.is_u32(&self.cx) {
941 return self.context.new_cast(None, value, result_type);
945 let mask = self.context.new_rvalue_from_long(value_type, 0x00000000FFFFFFFF);
946 let left = value & mask;
947 let shifted = value >> self.context.new_rvalue_from_int(value_type, 32);
948 let right = shifted & mask;
949 let value = left + right;
951 self.context.new_cast(None, value, result_type)
954 // Algorithm from: https://blog.regehr.org/archives/1063
955 fn rotate_left(&mut self, value: RValue<'gcc>, shift: RValue<'gcc>, width: u64) -> RValue<'gcc> {
956 let max = self.const_uint(shift.get_type(), width);
957 let shift = self.urem(shift, max);
958 let lhs = self.shl(value, shift);
959 let result_neg = self.neg(shift);
963 self.const_uint(shift.get_type(), width - 1),
965 let rhs = self.lshr(value, result_and);
969 // Algorithm from: https://blog.regehr.org/archives/1063
970 fn rotate_right(&mut self, value: RValue<'gcc>, shift: RValue<'gcc>, width: u64) -> RValue<'gcc> {
971 let max = self.const_uint(shift.get_type(), width);
972 let shift = self.urem(shift, max);
973 let lhs = self.lshr(value, shift);
974 let result_neg = self.neg(shift);
978 self.const_uint(shift.get_type(), width - 1),
980 let rhs = self.shl(value, result_and);
984 fn saturating_add(&mut self, lhs: RValue<'gcc>, rhs: RValue<'gcc>, signed: bool, width: u64) -> RValue<'gcc> {
985 let result_type = lhs.get_type();
987 // Based on algorithm from: https://stackoverflow.com/a/56531252/389119
988 let func = self.current_func.borrow().expect("func");
989 let res = func.new_local(None, result_type, "saturating_sum");
990 let supports_native_type = self.is_native_int_type(result_type);
992 if supports_native_type {
995 8 => "__builtin_add_overflow",
996 16 => "__builtin_add_overflow",
997 32 => "__builtin_sadd_overflow",
998 64 => "__builtin_saddll_overflow",
999 128 => "__builtin_add_overflow",
1000 _ => unreachable!(),
1002 let overflow_func = self.context.get_builtin_function(func_name);
1003 self.overflow_call(overflow_func, &[lhs, rhs, res.get_address(None)], None)
1008 128 => "__rust_i128_addo",
1009 _ => unreachable!(),
1011 let param_a = self.context.new_parameter(None, result_type, "a");
1012 let param_b = self.context.new_parameter(None, result_type, "b");
1013 let result_field = self.context.new_field(None, result_type, "result");
1014 let overflow_field = self.context.new_field(None, self.bool_type, "overflow");
1015 let return_type = self.context.new_struct_type(None, "result_overflow", &[result_field, overflow_field]);
1016 let func = self.context.new_function(None, FunctionType::Extern, return_type.as_type(), &[param_a, param_b], func_name, false);
1017 let result = self.context.new_call(None, func, &[lhs, rhs]);
1018 let overflow = result.access_field(None, overflow_field);
1019 let int_result = result.access_field(None, result_field);
1020 self.llbb().add_assignment(None, res, int_result);
1024 let then_block = func.new_block("then");
1025 let after_block = func.new_block("after");
1027 // Return `result_type`'s maximum or minimum value on overflow
1028 // NOTE: convert the type to unsigned to have an unsigned shift.
1029 let unsigned_type = result_type.to_unsigned(&self.cx);
1030 let shifted = self.gcc_lshr(self.gcc_int_cast(lhs, unsigned_type), self.gcc_int(unsigned_type, width as i64 - 1));
1031 let uint_max = self.gcc_not(self.gcc_int(unsigned_type, 0));
1032 let int_max = self.gcc_lshr(uint_max, self.gcc_int(unsigned_type, 1));
1033 then_block.add_assignment(None, res, self.gcc_int_cast(self.gcc_add(shifted, int_max), result_type));
1034 then_block.end_with_jump(None, after_block);
1036 self.llbb().end_with_conditional(None, overflow, then_block, after_block);
1038 // NOTE: since jumps were added in a place rustc does not
1039 // expect, the current block in the state need to be updated.
1040 self.switch_to_block(after_block);
1045 // Algorithm from: http://locklessinc.com/articles/sat_arithmetic/
1046 let res = self.gcc_add(lhs, rhs);
1047 let cond = self.gcc_icmp(IntPredicate::IntULT, res, lhs);
1048 let value = self.gcc_neg(self.gcc_int_cast(cond, result_type));
1049 self.gcc_or(res, value)
1053 // Algorithm from: https://locklessinc.com/articles/sat_arithmetic/
1054 fn saturating_sub(&mut self, lhs: RValue<'gcc>, rhs: RValue<'gcc>, signed: bool, width: u64) -> RValue<'gcc> {
1055 let result_type = lhs.get_type();
1057 // Based on algorithm from: https://stackoverflow.com/a/56531252/389119
1058 let func = self.current_func.borrow().expect("func");
1059 let res = func.new_local(None, result_type, "saturating_diff");
1060 let supports_native_type = self.is_native_int_type(result_type);
1062 if supports_native_type {
1065 8 => "__builtin_sub_overflow",
1066 16 => "__builtin_sub_overflow",
1067 32 => "__builtin_ssub_overflow",
1068 64 => "__builtin_ssubll_overflow",
1069 128 => "__builtin_sub_overflow",
1070 _ => unreachable!(),
1072 let overflow_func = self.context.get_builtin_function(func_name);
1073 self.overflow_call(overflow_func, &[lhs, rhs, res.get_address(None)], None)
1078 128 => "__rust_i128_subo",
1079 _ => unreachable!(),
1081 let param_a = self.context.new_parameter(None, result_type, "a");
1082 let param_b = self.context.new_parameter(None, result_type, "b");
1083 let result_field = self.context.new_field(None, result_type, "result");
1084 let overflow_field = self.context.new_field(None, self.bool_type, "overflow");
1085 let return_type = self.context.new_struct_type(None, "result_overflow", &[result_field, overflow_field]);
1086 let func = self.context.new_function(None, FunctionType::Extern, return_type.as_type(), &[param_a, param_b], func_name, false);
1087 let result = self.context.new_call(None, func, &[lhs, rhs]);
1088 let overflow = result.access_field(None, overflow_field);
1089 let int_result = result.access_field(None, result_field);
1090 self.llbb().add_assignment(None, res, int_result);
1094 let then_block = func.new_block("then");
1095 let after_block = func.new_block("after");
1097 // Return `result_type`'s maximum or minimum value on overflow
1098 // NOTE: convert the type to unsigned to have an unsigned shift.
1099 let unsigned_type = result_type.to_unsigned(&self.cx);
1100 let shifted = self.gcc_lshr(self.gcc_int_cast(lhs, unsigned_type), self.gcc_int(unsigned_type, width as i64 - 1));
1101 let uint_max = self.gcc_not(self.gcc_int(unsigned_type, 0));
1102 let int_max = self.gcc_lshr(uint_max, self.gcc_int(unsigned_type, 1));
1103 then_block.add_assignment(None, res, self.gcc_int_cast(self.gcc_add(shifted, int_max), result_type));
1104 then_block.end_with_jump(None, after_block);
1106 self.llbb().end_with_conditional(None, overflow, then_block, after_block);
1108 // NOTE: since jumps were added in a place rustc does not
1109 // expect, the current block in the state need to be updated.
1110 self.switch_to_block(after_block);
1115 let res = self.gcc_sub(lhs, rhs);
1116 let comparison = self.gcc_icmp(IntPredicate::IntULE, res, lhs);
1117 let value = self.gcc_neg(self.gcc_int_cast(comparison, result_type));
1118 self.gcc_and(res, value)
1123 fn try_intrinsic<'gcc, 'tcx>(bx: &mut Builder<'_, 'gcc, 'tcx>, try_func: RValue<'gcc>, data: RValue<'gcc>, _catch_func: RValue<'gcc>, dest: RValue<'gcc>) {
1124 // NOTE: the `|| true` here is to use the panic=abort strategy with panic=unwind too
1125 if bx.sess().panic_strategy() == PanicStrategy::Abort || true {
1126 // TODO(bjorn3): Properly implement unwinding and remove the `|| true` once this is done.
1127 bx.call(bx.type_void(), None, try_func, &[data], None);
1128 // Return 0 unconditionally from the intrinsic call;
1129 // we can never unwind.
1130 let ret_align = bx.tcx.data_layout.i32_align.abi;
1131 bx.store(bx.const_i32(0), dest, ret_align);
1133 else if wants_msvc_seh(bx.sess()) {