Large integer polyfills

[Firestar99]

We should have polyfills to downlevel u64 and u128 to many u32 instructions, enabling the use of these types without concern for hardware capabilities on eg. mobile ARM platforms. Also consider polyfill for u8 and u16, which could enable things like using enum Ordering from std, see #147.

libm only handles float math, no integer downlevel.

Discussed in #301

^{Originally posted by nazar-pc June 27, 2025}
I faced a small challenge: my CPU code I'm trying to run on a GPU naturally maps onto u64 and u128, but even u64 apparently requires OpCapability Int64, let alone u128.

Now writing polyfills that work around that feels like a job that compiler should do for me, though I appreciate that it at least tells me that there isn't a native way to run that and I should think about what to do with it.

I'm wondering it it'd be possible to either have a compilation flag that automatically inserts polyfills for such types. It will be an explicit opt-in feature, but otherwise require the least amount of effort for those who do need it. I believe LLVM is capable of this.

I'm really not looking forward to writing polyfills for u128 using a bunch of u32s.

[Firestar99]

Implementation Notes

For anyone investigating this, I can at least paste these relevant code locations:

• where all basic math functions are implemented
  

  rust-gpu/crates/rustc_codegen_spirv/src/builder/builder_methods.rs

  Lines 1538 to 1588 in 2f915a0

  	simple_op! {
  	add, i_add,
  	fold_const {
  	int(a, b) => a.wrapping_add(b)
  	}
  	}
  	// FIXME(eddyb) try to annotate the SPIR-V for `fast` and `algebraic`.
  	simple_op! {fadd, f_add}
  	simple_op! {fadd_fast, f_add} // fast=normal
  	simple_op! {fadd_algebraic, f_add} // algebraic=normal
  	simple_op! {sub, i_sub}
  	simple_op! {fsub, f_sub}
  	simple_op! {fsub_fast, f_sub} // fast=normal
  	simple_op! {fsub_algebraic, f_sub} // algebraic=normal
  	simple_op! {
  	mul, i_mul,
  	// HACK(eddyb) `rustc_codegen_ssa` relies on `Builder` methods doing
  	// on-the-fly constant-folding, for e.g. intrinsics that copy memory.
  	fold_const {
  	int(a, b) => a.wrapping_mul(b)
  	}
  	}
  	simple_op! {fmul, f_mul}
  	simple_op! {fmul_fast, f_mul} // fast=normal
  	simple_op! {fmul_algebraic, f_mul} // algebraic=normal
  	simple_op! {udiv, u_div}
  	// Note: exactudiv is UB when there's a remainder, so it's valid to implement as a normal div.
  	// TODO: Can we take advantage of the UB and emit something else?
  	simple_op! {exactudiv, u_div}
  	simple_op! {sdiv, s_div}
  	// Same note and TODO as exactudiv
  	simple_op! {exactsdiv, s_div}
  	simple_op! {fdiv, f_div}
  	simple_op! {fdiv_fast, f_div} // fast=normal
  	simple_op! {fdiv_algebraic, f_div} // algebraic=normal
  	simple_op! {urem, u_mod}
  	simple_op! {srem, s_rem}
  	simple_op! {frem, f_rem}
  	simple_op! {frem_fast, f_rem} // fast=normal
  	simple_op! {frem_algebraic, f_rem} // algebraic=normal
  	simple_op_unchecked_type! {shl, shift_left_logical}
  	simple_op_unchecked_type! {lshr, shift_right_logical}
  	simple_op_unchecked_type! {ashr, shift_right_arithmetic}
  	simple_op! {unchecked_sadd, i_add} // already unchecked by default
  	simple_op! {unchecked_uadd, i_add} // already unchecked by default
  	simple_op! {unchecked_ssub, i_sub} // already unchecked by default
  	simple_op! {unchecked_usub, i_sub} // already unchecked by default
  	simple_op! {unchecked_smul, i_mul} // already unchecked by default
  	simple_op! {unchecked_umul, i_mul} // already unchecked by default
  	simple_uni_op! {neg, s_negate}
  	simple_uni_op! {fneg, f_negate}

• with this proc macro just emitting the correct instruction plus some const eval, nothing wrt emulation to be found
  

  rust-gpu/crates/rustc_codegen_spirv/src/builder/builder_methods.rs

  Lines 79 to 82 in 2f915a0

  	self.emit()
  	.$inst_name(result_type, None, lhs.def(self), rhs.def(self))
  	.unwrap()
  	.with_type(result_type)

• I already made some downlevels for count_ones, bit_reverse, count_trailing_zeros and count_leading_zeros here, since spirv requires these instructions to be u32 exclusive.
  

  rust-gpu/crates/rustc_codegen_spirv/src/builder/intrinsics.rs

  Lines 361 to 592 in 2f915a0

  	impl Builder<'_, '_> {
  	pub fn count_ones(&self, arg: SpirvValue) -> SpirvValue {
  	let ty = arg.ty;
  	match self.cx.lookup_type(ty) {
  	SpirvType::Integer(bits, false) => {
  	let u32 = SpirvType::Integer(32, false).def(self.span(), self);
  	match bits {
  	8 | 16 => {
  	let arg = arg.def(self);
  	let arg = self.emit().u_convert(u32, None, arg).unwrap();
  	self.emit().bit_count(u32, None, arg).unwrap()
  	}
  	32 => self.emit().bit_count(u32, None, arg.def(self)).unwrap(),
  	64 => {
  	let u32_32 = self.constant_u32(self.span(), 32).def(self);
  	let arg = arg.def(self);
  	let lower = self.emit().u_convert(u32, None, arg).unwrap();
  	let higher = self
  	.emit()
  	.shift_right_logical(ty, None, arg, u32_32)
  	.unwrap();
  	let higher = self.emit().u_convert(u32, None, higher).unwrap();
  	let lower_bits = self.emit().bit_count(u32, None, lower).unwrap();
  	let higher_bits = self.emit().bit_count(u32, None, higher).unwrap();
  	self.emit()
  	.i_add(u32, None, lower_bits, higher_bits)
  	.unwrap()
  	}
  	_ => {
  	return self.undef_zombie(
  	ty,
  	&format!("count_ones() on unsupported {ty:?} bit integer type"),
  	);
  	}
  	}
  	.with_type(u32)
  	}
  	_ => self.fatal(format!(
  	"count_ones() expected an unsigned integer type, got {:?}",
  	self.cx.lookup_type(ty)
  	)),
  	}
  	}
  	pub fn bit_reverse(&self, arg: SpirvValue) -> SpirvValue {
  	let ty = arg.ty;
  	match self.cx.lookup_type(ty) {
  	SpirvType::Integer(bits, false) => {
  	let u32 = SpirvType::Integer(32, false).def(self.span(), self);
  	let uint = SpirvType::Integer(bits, false).def(self.span(), self);
  	match bits {
  	8 | 16 => {
  	let arg = arg.def(self);
  	let arg = self.emit().u_convert(u32, None, arg).unwrap();
  	let reverse = self.emit().bit_reverse(u32, None, arg).unwrap();
  	let shift = self.constant_u32(self.span(), 32 - bits).def(self);
  	let reverse = self
  	.emit()
  	.shift_right_logical(u32, None, reverse, shift)
  	.unwrap();
  	self.emit().u_convert(uint, None, reverse).unwrap()
  	}
  	32 => self.emit().bit_reverse(u32, None, arg.def(self)).unwrap(),
  	64 => {
  	let u32_32 = self.constant_u32(self.span(), 32).def(self);
  	let arg = arg.def(self);
  	let lower = self.emit().u_convert(u32, None, arg).unwrap();
  	let higher = self
  	.emit()
  	.shift_right_logical(ty, None, arg, u32_32)
  	.unwrap();
  	let higher = self.emit().u_convert(u32, None, higher).unwrap();
  	// note that higher and lower have swapped
  	let higher_bits = self.emit().bit_reverse(u32, None, lower).unwrap();
  	let lower_bits = self.emit().bit_reverse(u32, None, higher).unwrap();
  	let higher_bits = self.emit().u_convert(uint, None, higher_bits).unwrap();
  	let higher_bits = self
  	.emit()
  	.shift_left_logical(uint, None, higher_bits, u32_32)
  	.unwrap();
  	let lower_bits = self.emit().u_convert(uint, None, lower_bits).unwrap();
  	self.emit()
  	.bitwise_or(ty, None, lower_bits, higher_bits)
  	.unwrap()
  	}
  	_ => {
  	return self.undef_zombie(
  	ty,
  	&format!("bit_reverse() on unsupported {ty:?} bit integer type"),
  	);
  	}
  	}
  	.with_type(ty)
  	}
  	_ => self.fatal(format!(
  	"bit_reverse() expected an unsigned integer type, got {:?}",
  	self.cx.lookup_type(ty)
  	)),
  	}
  	}
  	pub fn count_leading_trailing_zeros(
  	&self,
  	arg: SpirvValue,
  	trailing: bool,
  	non_zero: bool,
  	) -> SpirvValue {
  	let ty = arg.ty;
  	match self.cx.lookup_type(ty) {
  	SpirvType::Integer(bits, false) => {
  	let bool = SpirvType::Bool.def(self.span(), self);
  	let u32 = SpirvType::Integer(32, false).def(self.span(), self);
  	let glsl = self.ext_inst.borrow_mut().import_glsl(self);
  	let find_xsb = |arg, offset: i32| {
  	if trailing {
  	let lsb = self
  	.emit()
  	.ext_inst(u32, None, glsl, GLOp::FindILsb as u32, [Operand::IdRef(
  	arg,
  	)])
  	.unwrap();
  	if offset == 0 {
  	lsb
  	} else {
  	let const_offset = self.constant_i32(self.span(), offset).def(self);
  	self.emit().i_add(u32, None, const_offset, lsb).unwrap()
  	}
  	} else {
  	// rust is always unsigned, so FindUMsb
  	let msb_bit = self
  	.emit()
  	.ext_inst(u32, None, glsl, GLOp::FindUMsb as u32, [Operand::IdRef(
  	arg,
  	)])
  	.unwrap();
  	// the glsl op returns the Msb bit, not the amount of leading zeros of this u32
  	// leading zeros = 31 - Msb bit
  	let const_offset = self.constant_i32(self.span(), 31 - offset).def(self);
  	self.emit().i_sub(u32, None, const_offset, msb_bit).unwrap()
  	}
  	};
  	let converted = match bits {
  	8 | 16 => {
  	let arg = self.emit().u_convert(u32, None, arg.def(self)).unwrap();
  	if trailing {
  	find_xsb(arg, 0)
  	} else {
  	find_xsb(arg, bits as i32 - 32)
  	}
  	}
  	32 => find_xsb(arg.def(self), 0),
  	64 => {
  	let u32_0 = self.constant_int(u32, 0).def(self);
  	let u32_32 = self.constant_u32(self.span(), 32).def(self);
  	let arg = arg.def(self);
  	let lower = self.emit().u_convert(u32, None, arg).unwrap();
  	let higher = self
  	.emit()
  	.shift_right_logical(ty, None, arg, u32_32)
  	.unwrap();
  	let higher = self.emit().u_convert(u32, None, higher).unwrap();
  	if trailing {
  	let use_lower = self.emit().i_equal(bool, None, higher, u32_0).unwrap();
  	let lower_bits = find_xsb(lower, 32);
  	let higher_bits = find_xsb(higher, 0);
  	self.emit()
  	.select(u32, None, use_lower, lower_bits, higher_bits)
  	.unwrap()
  	} else {
  	let use_higher = self.emit().i_equal(bool, None, lower, u32_0).unwrap();
  	let lower_bits = find_xsb(lower, 0);
  	let higher_bits = find_xsb(higher, 32);
  	self.emit()
  	.select(u32, None, use_higher, higher_bits, lower_bits)
  	.unwrap()
  	}
  	}
  	_ => {
  	return self.undef_zombie(ty, &format!(
  	"count_leading_trailing_zeros() on unsupported {ty:?} bit integer type"
  	));
  	}
  	};
  	if non_zero {
  	converted
  	} else {
  	let int_0 = self.constant_int(ty, 0).def(self);
  	let int_bits = self.constant_int(u32, bits as u128).def(self);
  	let is_0 = self
  	.emit()
  	.i_equal(bool, None, arg.def(self), int_0)
  	.unwrap();
  	self.emit()
  	.select(u32, None, is_0, int_bits, converted)
  	.unwrap()
  	}
  	.with_type(u32)
  	}
  	SpirvType::Integer(bits, true) => {
  	// rustc wants `[i8,i16,i32,i64]::leading_zeros()` with `non_zero: true` for some reason. I do not know
  	// how these are reachable, marking them as zombies makes none of our compiletests fail.
  	let unsigned = SpirvType::Integer(bits, false).def(self.span(), self);
  	let arg = self
  	.emit()
  	.bitcast(unsigned, None, arg.def(self))
  	.unwrap()
  	.with_type(unsigned);
  	let result = self.count_leading_trailing_zeros(arg, trailing, non_zero);
  	self.emit()
  	.bitcast(ty, None, result.def(self))
  	.unwrap()
  	.with_type(ty)
  	}
  	e => {
  	self.fatal(format!(
  	"count_leading_trailing_zeros(trailing: {trailing}, non_zero: {non_zero}) expected an integer type, got {e:?}",
  	));
  	}
  	}
  	}

[Firestar99]

I wonder if polyfills should be linker steps instead. Generate all code with all the u8/u16/u64 as is, then have the linker downlevel it to u32 for you. With multimodule, you could control polyfill for each entry point, allowing you to have a u64-supported and a u64-polyfill entry point right next to each other. And your runtime can decide which one to pick depending on device features.

[nazar-pc]

Hm... that is an interesting proposal. I already have two builds: for GPUs that support Int64 and those that do not. If I can compile it once and have post-processing step to add polyfills, it might be cheaper overall. I wouldn't want multiple single-module files though.

Also since I'm using u128s as bit containers, having polyfills on Rust side might be beneficial in case I don't actually use 128 bits, but something like 80, in which case the overall number of, let's say, bit shifts, can potentially be reduced by eliminating dead code by the compiler, which I imagine will not be possible at a later stage, at least not as easily.

Or sometimes bit shift might be known at compile time to be something like 35, in which case some of the words can be ignored completely since they'll be shifted away completely.

So overall, my preference would be to implement it on earlier stage for better performance.