compiler/rustc_codegen_gcc/src/intrinsic/mod.rs

   1 pub mod llvm;
   2 mod simd;
   3
   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;
  18
  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;
  26
  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",
  34         sym::sinf64 => "sin",
  35         sym::cosf32 => "cosf",
  36         sym::cosf64 => "cos",
  37         sym::powf32 => "powf",
  38         sym::powf64 => "pow",
  39         sym::expf32 => "expf",
  40         sym::expf64 => "exp",
  41         sym::exp2f32 => "exp2f",
  42         sym::exp2f64 => "exp2",
  43         sym::logf32 => "logf",
  44         sym::logf64 => "log",
  45         sym::log10f32 => "log10f",
  46         sym::log10f64 => "log10",
  47         sym::log2f32 => "log2f",
  48         sym::log2f64 => "log2",
  49         sym::fmaf32 => "fmaf",
  50         sym::fmaf64 => "fma",
  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",
  72         _ => return None,
  73     };
  74     Some(cx.context.get_builtin_function(&gcc_name))
  75 }
  76
  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) {
  79         let tcx = self.tcx;
  80         let callee_ty = instance.ty(tcx, ty::ParamEnv::reveal_all());
  81
  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),
  85         };
  86
  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();
  93
  94         let llret_ty = self.layout_of(ret_ty).gcc_type(self, true);
  95         let result = PlaceRef::new_sized(llresult, fn_abi.ret.layout);
  96
  97         let simple = get_simple_intrinsic(self, name);
  98         let llval =
  99             match 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)
 104                 },
 105                 sym::likely => {
 106                     self.expect(args[0].immediate(), true)
 107                 }
 108                 sym::unlikely => {
 109                     self.expect(args[0].immediate(), false)
 110                 }
 111                 kw::Try => {
 112                     try_intrinsic(
 113                         self,
 114                         args[0].immediate(),
 115                         args[1].immediate(),
 116                         args[2].immediate(),
 117                         llresult,
 118                     );
 119                     return;
 120                 }
 121                 sym::breakpoint => {
 122                     unimplemented!();
 123                 }
 124                 sym::va_copy => {
 125                     unimplemented!();
 126                 }
 127                 sym::va_arg => {
 128                     unimplemented!();
 129                 }
 130
 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)));
 136                     }
 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))
 140                 }
 141                 sym::volatile_store => {
 142                     let dst = args[0].deref(self.cx());
 143                     args[1].val.volatile_store(self, dst);
 144                     return;
 145                 }
 146                 sym::unaligned_volatile_store => {
 147                     let dst = args[0].deref(self.cx());
 148                     args[1].val.unaligned_volatile_store(self, dst);
 149                     return;
 150                 }
 151                 sym::prefetch_read_data
 152                     | sym::prefetch_write_data
 153                     | sym::prefetch_read_instruction
 154                     | sym::prefetch_write_instruction => {
 155                         unimplemented!();
 156                     }
 157                 sym::ctlz
 158                     | sym::ctlz_nonzero
 159                     | sym::cttz
 160                     | sym::cttz_nonzero
 161                     | sym::ctpop
 162                     | sym::bswap
 163                     | sym::bitreverse
 164                     | sym::rotate_left
 165                     | sym::rotate_right
 166                     | sym::saturating_add
 167                     | sym::saturating_sub => {
 168                         let ty = arg_tys[0];
 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");
 176
 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);
 182
 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);
 186
 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);
 191
 192                                     let zeros =
 193                                         match name {
 194                                             sym::ctlz => self.count_leading_zeroes(width, arg),
 195                                             sym::cttz => self.count_trailing_zeroes(width, arg),
 196                                             _ => unreachable!(),
 197                                         };
 198                                     self.llbb().add_assignment(None, result, zeros);
 199                                     self.llbb().end_with_jump(None, after_block);
 200
 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);
 204
 205                                     result.to_rvalue()
 206                                 }
 207                                 sym::ctlz_nonzero => {
 208                                     self.count_leading_zeroes(width, args[0].immediate())
 209                                 },
 210                                 sym::cttz_nonzero => {
 211                                     self.count_trailing_zeroes(width, args[0].immediate())
 212                                 }
 213                                 sym::ctpop => self.pop_count(args[0].immediate()),
 214                                 sym::bswap => {
 215                                     if width == 8 {
 216                                         args[0].immediate() // byte swap a u8/i8 is just a no-op
 217                                     }
 218                                     else {
 219                                         self.gcc_bswap(args[0].immediate(), width)
 220                                     }
 221                                 },
 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();
 230                                     if is_left {
 231                                         self.rotate_left(val, raw_shift, width)
 232                                     }
 233                                     else {
 234                                         self.rotate_right(val, raw_shift, width)
 235                                     }
 236                                 },
 237                                 sym::saturating_add => {
 238                                     self.saturating_add(args[0].immediate(), args[1].immediate(), signed, width)
 239                                 },
 240                                 sym::saturating_sub => {
 241                                     self.saturating_sub(args[0].immediate(), args[1].immediate(), signed, width)
 242                                 },
 243                                 _ => bug!(),
 244                             },
 245                             None => {
 246                                 tcx.sess.emit_err(InvalidMonomorphizationBasicInteger { span, name, ty });
 247                                 return;
 248                             }
 249                         }
 250                     }
 251
 252                 sym::raw_eq => {
 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
 264                         }
 265                     };
 266
 267                     let a = args[0].immediate();
 268                     let b = args[1].immediate();
 269                     if layout.size().bytes() == 0 {
 270                         self.const_bool(true)
 271                     }
 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)
 280                     }*/
 281                     else {
 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))
 289                     }
 290                 }
 291
 292                 sym::black_box => {
 293                     args[0].val.store(self, result);
 294
 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);
 300
 301                     // We have copied the value to `result` already.
 302                     return;
 303                 }
 304
 305                 sym::ptr_mask => {
 306                     let usize_type = self.context.new_type::<usize>();
 307                     let void_ptr_type = self.context.new_type::<*const ()>();
 308
 309                     let ptr = args[0].immediate();
 310                     let mask = args[1].immediate();
 311
 312                     let addr = self.bitcast(ptr, usize_type);
 313                     let masked = self.and(addr, mask);
 314                     self.bitcast(masked, void_ptr_type)
 315                 },
 316
 317                 _ if name_str.starts_with("simd_") => {
 318                     match generic_simd_intrinsic(self, name, callee_ty, args, ret_ty, llret_ty, span) {
 319                         Ok(llval) => llval,
 320                         Err(()) => return,
 321                     }
 322                 }
 323
 324                 _ => bug!("unknown intrinsic '{}'", name),
 325             };
 326
 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);
 332             }
 333             else {
 334                 OperandRef::from_immediate_or_packed_pair(self, llval, result.layout)
 335                     .val
 336                     .store(self, result);
 337             }
 338         }
 339     }
 340
 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);
 345     }
 346
 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);
 352     }
 353
 354     fn expect(&mut self, cond: Self::Value, _expected: bool) -> Self::Value {
 355         // TODO(antoyo)
 356         cond
 357     }
 358
 359     fn type_test(&mut self, _pointer: Self::Value, _typeid: Self::Value) -> Self::Value {
 360         // Unsupported.
 361         self.context.new_rvalue_from_int(self.int_type, 0)
 362     }
 363
 364     fn type_checked_load(
 365         &mut self,
 366         _llvtable: Self::Value,
 367         _vtable_byte_offset: u64,
 368         _typeid: Self::Value,
 369     ) -> Self::Value {
 370         // Unsupported.
 371         self.context.new_rvalue_from_int(self.int_type, 0)
 372     }
 373
 374     fn va_start(&mut self, _va_list: RValue<'gcc>) -> RValue<'gcc> {
 375         unimplemented!();
 376     }
 377
 378     fn va_end(&mut self, _va_list: RValue<'gcc>) -> RValue<'gcc> {
 379         unimplemented!();
 380     }
 381 }
 382
 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)
 386     }
 387
 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)
 390     }
 391
 392     fn arg_memory_ty(&self, arg_abi: &ArgAbi<'tcx, Ty<'tcx>>) -> Type<'gcc> {
 393         arg_abi.memory_ty(self)
 394     }
 395 }
 396
 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>>);
 401 }
 402
 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)
 408     }
 409
 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() {
 416             return;
 417         }
 418         if self.is_sized_indirect() {
 419             OperandValue::Ref(val, None, self.layout.align.abi).store(bx, dst)
 420         }
 421         else if self.is_unsized_indirect() {
 422             bug!("unsized `ArgAbi` must be handled through `store_fn_arg`");
 423         }
 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);
 432             }
 433             else {
 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.
 439                 //
 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.
 447
 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);
 453
 454                 // ... where we first store the value...
 455                 bx.store(val, llscratch, scratch_align);
 456
 457                 // ... and then memcpy it to the intended destination.
 458                 bx.memcpy(
 459                     dst.llval,
 460                     self.layout.align.abi,
 461                     llscratch,
 462                     scratch_align,
 463                     bx.const_usize(self.layout.size.bytes()),
 464                     MemFlags::empty(),
 465                 );
 466
 467                 bx.lifetime_end(llscratch, scratch_size);
 468             }
 469         }
 470         else {
 471             OperandValue::Immediate(val).store(bx, dst);
 472         }
 473     }
 474
 475     fn store_fn_arg<'a>(&self, bx: &mut Builder<'a, 'gcc, 'tcx>, idx: &mut usize, dst: PlaceRef<'tcx, RValue<'gcc>>) {
 476         let mut next = || {
 477             let val = bx.current_func().get_param(*idx as i32);
 478             *idx += 1;
 479             val.to_rvalue()
 480         };
 481         match self.mode {
 482             PassMode::Ignore => {},
 483             PassMode::Pair(..) => {
 484                 OperandValue::Pair(next(), next()).store(bx, dst);
 485             },
 486             PassMode::Indirect { extra_attrs: Some(_), .. } => {
 487                 OperandValue::Ref(next(), Some(next()), self.layout.align.abi).store(bx, dst);
 488             },
 489             PassMode::Direct(_) | PassMode::Indirect { extra_attrs: None, .. } | PassMode::Cast(..) => {
 490                 let next_arg = next();
 491                 self.store(bx, next_arg, dst);
 492             },
 493         }
 494     }
 495 }
 496
 497 fn int_type_width_signed<'gcc, 'tcx>(ty: Ty<'tcx>, cx: &CodegenCx<'gcc, 'tcx>) -> Option<(u64, bool)> {
 498     match ty.kind() {
 499         ty::Int(t) => Some((
 500             match t {
 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,
 507             },
 508             true,
 509         )),
 510         ty::Uint(t) => Some((
 511             match t {
 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,
 518             },
 519             false,
 520         )),
 521         _ => None,
 522     }
 523 }
 524
 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);
 529
 530         let value =
 531             if result_type.is_signed(self.cx) {
 532                 self.gcc_int_cast(value, typ)
 533             }
 534             else {
 535                 value
 536             };
 537
 538         let context = &self.cx.context;
 539         let result =
 540             match width {
 541                 8 => {
 542                     // First step.
 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);
 548
 549                     // Second step.
 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);
 555
 556                     // Third step.
 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);
 562
 563                     step3
 564                 },
 565                 16 => {
 566                     // First step.
 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);
 572
 573                     // Second step.
 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);
 579
 580                     // Third step.
 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);
 586
 587                     // Fourth step.
 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);
 593
 594                     step4
 595                 },
 596                 32 => {
 597                     // TODO(antoyo): Refactor with other implementations.
 598                     // First step.
 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);
 604
 605                     // Second step.
 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);
 611
 612                     // Third step.
 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);
 618
 619                     // Fourth step.
 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);
 625
 626                     // Fifth step.
 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);
 632
 633                     step5
 634                 },
 635                 64 => {
 636                     // First step.
 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);
 640
 641                     // Second step.
 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);
 647
 648                     // Third step.
 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));
 652
 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);
 656
 657                     // Fourth step.
 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));
 661
 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);
 665
 666                     // Fifth step.
 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));
 670
 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);
 674
 675                     step5
 676                 },
 677                 128 => {
 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);
 683
 684                     let reversed_high = self.bit_reverse(64, high);
 685                     let reversed_low = self.bit_reverse(64, low);
 686
 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);
 689
 690                     self.gcc_or(new_low, new_high)
 691                 },
 692                 _ => {
 693                     panic!("cannot bit reverse with width = {}", width);
 694                 },
 695             };
 696
 697         self.gcc_int_cast(result, result_type)
 698     }
 699
 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) {
 707                 "__builtin_clz"
 708             }
 709             else if arg_type.is_ulong(&self.cx) {
 710                 "__builtin_clzl"
 711             }
 712             else if arg_type.is_ulonglong(&self.cx) {
 713                 "__builtin_clzll"
 714             }
 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");
 720
 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);
 725
 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);
 729
 730                 let clzll = self.context.get_builtin_function("__builtin_clzll");
 731
 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);
 734                 self.llbb()
 735                     .add_assignment(None, first_elem, first_value);
 736
 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);
 740                 self.llbb()
 741                     .add_assignment(None, second_elem, second_value);
 742
 743                 let third_elem = self.context.new_array_access(None, result, two);
 744                 let third_value = self.const_uint(arg_type, 128);
 745                 self.llbb()
 746                     .add_assignment(None, third_elem, third_value);
 747
 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
 753                 // gcc.
 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);
 757
 758                 let res = self.context.new_array_access(None, result, index);
 759
 760                 return self.gcc_int_cast(res.to_rvalue(), arg_type);
 761             }
 762             else {
 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);
 769             };
 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)
 773     }
 774
 775     fn count_trailing_zeroes(&mut self, _width: u64, arg: RValue<'gcc>) -> RValue<'gcc> {
 776         let result_type = arg.get_type();
 777         let arg =
 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)
 781             }
 782             else {
 783                 arg
 784             };
 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)
 792             }
 793             else if arg_type.is_ulong(&self.cx) {
 794                 ("__builtin_ctzl", self.cx.ulong_type)
 795             }
 796             else if arg_type.is_ulonglong(&self.cx) {
 797                 ("__builtin_ctzll", self.cx.ulonglong_type)
 798             }
 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");
 804
 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);
 809
 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);
 813
 814                 let ctzll = self.context.get_builtin_function("__builtin_ctzll");
 815
 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);
 818                 self.llbb()
 819                     .add_assignment(None, first_elem, first_value);
 820
 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);
 823                 self.llbb()
 824                     .add_assignment(None, second_elem, second_value);
 825
 826                 let third_elem = self.context.new_array_access(None, result, two);
 827                 let third_value = self.gcc_int(arg_type, 128);
 828                 self.llbb()
 829                     .add_assignment(None, third_elem, third_value);
 830
 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
 836                 // gcc.
 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);
 840
 841                 let res = self.context.new_array_access(None, result, index);
 842
 843                 return self.gcc_int_cast(res.to_rvalue(), result_type);
 844             }
 845             else {
 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);
 857             };
 858         let count_trailing_zeroes = self.context.get_builtin_function(count_trailing_zeroes);
 859         let arg =
 860             if arg_type != expected_type {
 861                 self.context.new_cast(None, arg, expected_type)
 862             }
 863             else {
 864                 arg
 865             };
 866         let res = self.context.new_call(None, count_trailing_zeroes, &[arg]);
 867         self.context.new_cast(None, res, result_type)
 868     }
 869
 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);
 874
 875         let value =
 876             if result_type.is_signed(self.cx) {
 877                 self.gcc_int_cast(value, value_type)
 878             }
 879             else {
 880                 value
 881             };
 882
 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);
 895         }
 896
 897         // First step.
 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;
 903
 904         // Second step.
 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;
 910
 911         // Third step.
 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;
 917
 918         if value_type.is_u8(&self.cx) {
 919             return self.context.new_cast(None, value, result_type);
 920         }
 921
 922         // Fourth step.
 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;
 928
 929         if value_type.is_u16(&self.cx) {
 930             return self.context.new_cast(None, value, result_type);
 931         }
 932
 933         // Fifth step.
 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;
 939
 940         if value_type.is_u32(&self.cx) {
 941             return self.context.new_cast(None, value, result_type);
 942         }
 943
 944         // Sixth step.
 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;
 950
 951         self.context.new_cast(None, value, result_type)
 952     }
 953
 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);
 960         let result_and =
 961             self.and(
 962                 result_neg,
 963                 self.const_uint(shift.get_type(), width - 1),
 964             );
 965         let rhs = self.lshr(value, result_and);
 966         self.or(lhs, rhs)
 967     }
 968
 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);
 975         let result_and =
 976             self.and(
 977                 result_neg,
 978                 self.const_uint(shift.get_type(), width - 1),
 979             );
 980         let rhs = self.shl(value, result_and);
 981         self.or(lhs, rhs)
 982     }
 983
 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();
 986         if signed {
 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);
 991             let overflow =
 992                 if supports_native_type {
 993                     let func_name =
 994                         match width {
 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!(),
1001                         };
1002                     let overflow_func = self.context.get_builtin_function(func_name);
1003                     self.overflow_call(overflow_func, &[lhs, rhs, res.get_address(None)], None)
1004                 }
1005                 else {
1006                     let func_name =
1007                         match width {
1008                             128 => "__rust_i128_addo",
1009                             _ => unreachable!(),
1010                         };
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);
1021                     overflow
1022                 };
1023
1024             let then_block = func.new_block("then");
1025             let after_block = func.new_block("after");
1026
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);
1035
1036             self.llbb().end_with_conditional(None, overflow, then_block, after_block);
1037
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);
1041
1042             res.to_rvalue()
1043         }
1044         else {
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)
1050         }
1051     }
1052
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();
1056         if signed {
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);
1061             let overflow =
1062                 if supports_native_type {
1063                     let func_name =
1064                         match width {
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!(),
1071                         };
1072                     let overflow_func = self.context.get_builtin_function(func_name);
1073                     self.overflow_call(overflow_func, &[lhs, rhs, res.get_address(None)], None)
1074                 }
1075                 else {
1076                     let func_name =
1077                         match width {
1078                             128 => "__rust_i128_subo",
1079                             _ => unreachable!(),
1080                         };
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);
1091                     overflow
1092                 };
1093
1094             let then_block = func.new_block("then");
1095             let after_block = func.new_block("after");
1096
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);
1105
1106             self.llbb().end_with_conditional(None, overflow, then_block, after_block);
1107
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);
1111
1112             res.to_rvalue()
1113         }
1114         else {
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)
1119         }
1120     }
1121 }
1122
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);
1132     }
1133     else if wants_msvc_seh(bx.sess()) {
1134         unimplemented!();
1135     }
1136     else {
1137         unimplemented!();
1138     }
1139 }