From: Mohamed Ali <[email protected]>
This commit introduces the `ctlz` and `ctlz_nonzero` intrinsics for counting
leading zeros
in integer types.
The implementation includes handlers for both intrinsics, which validate input
types and utilize
GCC built-ins for the actual computation.
Addresses: Rust-GCC#658
gcc/rust/ChangeLog:
* backend/rust-compile-intrinsic.cc: Register ctlz and ctlz_nonzero
intrinsics.
* backend/rust-intrinsic-handlers.cc (ctlz_handler): Implement
ctlz_handler.
(ctlz_nonzero_handler): Implement ctlz_nonzero_handler.
* backend/rust-intrinsic-handlers.h (ctlz_handler): Add decl for
ctlz_handler.
(ctlz_nonzero_handler): Add decl for ctlz_nonzero_handler.
* util/rust-intrinsic-values.h: map ctlz_nonzero to its name.
gcc/testsuite/ChangeLog:
* rust/compile/ctlz.rs: New test.
* rust/compile/ctlz_nonzero.rs: New test.
* rust/execute/torture/ctlz.rs: New test.
* rust/execute/torture/ctlz_nonzero.rs: New test.
Signed-off-by: Mohamed Ali <[email protected]>
---
gcc/rust/backend/rust-compile-intrinsic.cc | 4 +-
gcc/rust/backend/rust-intrinsic-handlers.cc | 157 ++++++++++++++++++
gcc/rust/backend/rust-intrinsic-handlers.h | 2 +
gcc/rust/util/rust-intrinsic-values.h | 1 +
gcc/testsuite/rust/compile/ctlz.rs | 17 ++
gcc/testsuite/rust/compile/ctlz_nonzero.rs | 19 +++
gcc/testsuite/rust/execute/torture/ctlz.rs | 56 +++++++
.../rust/execute/torture/ctlz_nonzero.rs | 46 +++++
8 files changed, 301 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/rust/compile/ctlz.rs
create mode 100644 gcc/testsuite/rust/compile/ctlz_nonzero.rs
create mode 100644 gcc/testsuite/rust/execute/torture/ctlz.rs
create mode 100644 gcc/testsuite/rust/execute/torture/ctlz_nonzero.rs
diff --git a/gcc/rust/backend/rust-compile-intrinsic.cc
b/gcc/rust/backend/rust-compile-intrinsic.cc
index a4924542da3..9263883e9a5 100644
--- a/gcc/rust/backend/rust-compile-intrinsic.cc
+++ b/gcc/rust/backend/rust-compile-intrinsic.cc
@@ -68,7 +68,9 @@ static const std::map<std::string, handlers::HandlerBuilder>
generic_intrinsics
{IValue::CATCH_UNWIND, handlers::try_handler (true)},
{IValue::DISCRIMINANT_VALUE, handlers::discriminant_value},
{IValue::VARIANT_COUNT, handlers::variant_count},
- {IValue::BSWAP, handlers::bswap_handler}};
+ {IValue::BSWAP, handlers::bswap_handler},
+ {IValue::CTLZ, handlers::ctlz_handler},
+ {IValue::CTLZ_NONZERO, handlers::ctlz_nonzero_handler}};
Intrinsics::Intrinsics (Context *ctx) : ctx (ctx) {}
diff --git a/gcc/rust/backend/rust-intrinsic-handlers.cc
b/gcc/rust/backend/rust-intrinsic-handlers.cc
index 5c7854ce8de..eb86c8ad959 100644
--- a/gcc/rust/backend/rust-intrinsic-handlers.cc
+++ b/gcc/rust/backend/rust-intrinsic-handlers.cc
@@ -748,6 +748,151 @@ atomic_load (Context *ctx, TyTy::FnType *fntype, int
ordering)
return fndecl;
}
+// Shared inner implementation for ctlz and ctlz_nonzero.
+//
+// nonzero=false → ctlz: ctlz(0) is well-defined in Rust and must return
+// bit_size, but __builtin_clz*(0) is undefined behaviour in C, so an
+// explicit arg==0 guard is emitted.
+//
+// nonzero=true → ctlz_nonzero: the caller guarantees arg != 0 (passing 0
+// is immediate UB in Rust), so the zero guard is omitted entirely.
+static tree
+ctlz_handler (Context *ctx, TyTy::FnType *fntype, bool nonzero)
+{
+ rust_assert (fntype->get_params ().size () == 1);
+
+ tree lookup = NULL_TREE;
+ if (check_for_cached_intrinsic (ctx, fntype, &lookup))
+ return lookup;
+
+ auto fndecl = compile_intrinsic_function (ctx, fntype);
+
+ std::vector<Bvariable *> param_vars;
+ compile_fn_params (ctx, fntype, fndecl, ¶m_vars);
+
+ auto arg_param = param_vars.at (0);
+ if (!Backend::function_set_parameters (fndecl, param_vars))
+ return error_mark_node;
+
+ rust_assert (fntype->get_num_substitutions () == 1);
+ auto *monomorphized_type
+ = fntype->get_substs ().at (0).get_param_ty ()->resolve ();
+ if (!check_for_basic_integer_type ("ctlz", fntype->get_locus (),
+ monomorphized_type))
+ return error_mark_node;
+
+ enter_intrinsic_block (ctx, fndecl);
+
+ // BUILTIN ctlz FN BODY BEGIN
+ auto locus = fntype->get_locus ();
+ auto arg_expr = Backend::var_expression (arg_param, locus);
+ tree arg_type = TREE_TYPE (arg_expr);
+ unsigned bit_size = TYPE_PRECISION (arg_type);
+
+ // Convert signed types to their same-width unsigned equivalent before
+ // widening. Without this, widening a signed type sign-extends it.
+ // For example, i8(-1) = 0xFF widened to u32 gives 0xFFFFFFFF, so
+ // __builtin_clz(0xFFFFFFFF) = 0, then 0 - diff(24) = -24.
+ // Converting to u8 first gives 0xFF → 0x000000FF (zero-extended), so
+ // __builtin_clz(0x000000FF) = 24, then 24 - 24 = 0.
+ tree unsigned_type
+ = !TYPE_UNSIGNED (arg_type) ? unsigned_type_for (arg_type) : arg_type;
+ tree unsigned_arg = fold_convert (unsigned_type, arg_expr);
+
+ // Pick the narrowest GCC clz builtin whose operand type is wide enough to
+ // hold bit_size bits. diff records how many extra leading zeros the builtin
+ // will count due to the width difference and is subtracted from the result.
+ //
+ // Example: ctlz(1u8) bit_size=8, int_prec=32, diff=24.
+ // __builtin_clz(1u) returns 31 (counts from bit 31 down to bit 0).
+ // 31 - 24 = 7, which is the correct answer for an 8-bit value.
+ //
+ // TODO: 128-bit integers are not yet handled.
+ unsigned int_prec = TYPE_PRECISION (unsigned_type_node);
+ unsigned long_prec = TYPE_PRECISION (long_unsigned_type_node);
+ unsigned longlong_prec = TYPE_PRECISION (long_long_unsigned_type_node);
+
+ const char *builtin_name = nullptr;
+ tree cast_type = NULL_TREE;
+ int diff = 0;
+
+ if (bit_size <= int_prec)
+ {
+ // Fits in unsigned int: covers 8/16/32-bit integers on most targets.
+ builtin_name = "__builtin_clz";
+ cast_type = unsigned_type_node;
+ diff = static_cast<int> (int_prec - bit_size);
+ }
+ else if (bit_size <= long_prec)
+ {
+ // Fits in unsigned long but not unsigned int.
+ builtin_name = "__builtin_clzl";
+ cast_type = long_unsigned_type_node;
+ diff = static_cast<int> (long_prec - bit_size);
+ }
+ else if (bit_size <= longlong_prec)
+ {
+ // Fits in unsigned long long but not unsigned long.
+ builtin_name = "__builtin_clzll";
+ cast_type = long_long_unsigned_type_node;
+ diff = static_cast<int> (longlong_prec - bit_size);
+ }
+ else
+ {
+ rust_sorry_at (locus, "ctlz for %u-bit integers is not yet implemented",
+ bit_size);
+ return error_mark_node;
+ }
+
+ // Widen the unsigned arg to the chosen builtin's operand type, call it,
+ // then subtract the padding bits. diff == 0 means the Rust type exactly
+ // matches the builtin's operand width, so the subtraction is skipped.
+ tree call_arg = fold_convert (cast_type, unsigned_arg);
+
+ tree builtin_decl = error_mark_node;
+ BuiltinsContext::get ().lookup_simple_builtin (builtin_name, &builtin_decl);
+ rust_assert (builtin_decl != error_mark_node);
+
+ tree builtin_fn = build_fold_addr_expr_loc (locus, builtin_decl);
+ tree clz_expr
+ = Backend::call_expression (builtin_fn, {call_arg}, nullptr, locus);
+
+ if (diff > 0)
+ {
+ tree diff_cst = build_int_cst (integer_type_node, diff);
+ clz_expr
+ = fold_build2 (MINUS_EXPR, integer_type_node, clz_expr, diff_cst);
+ }
+
+ clz_expr = fold_convert (uint32_type_node, clz_expr);
+
+ tree final_expr;
+ if (!nonzero)
+ {
+ // ctlz(0) must return bit_size per the Rust reference.
+ // We cannot pass 0 to __builtin_clz* (UB), so emit:
+ // arg == 0 ? bit_size : clz_expr
+ tree zero = build_int_cst (arg_type, 0);
+ tree cmp = fold_build2 (EQ_EXPR, boolean_type_node, arg_expr, zero);
+ tree width_cst = build_int_cst (uint32_type_node, bit_size);
+ final_expr
+ = fold_build3 (COND_EXPR, uint32_type_node, cmp, width_cst, clz_expr);
+ }
+ else
+ {
+ // ctlz_nonzero: arg != 0 is guaranteed by the caller, no guard needed.
+ final_expr = clz_expr;
+ }
+
+ tree result = fold_convert (TREE_TYPE (DECL_RESULT (fndecl)), final_expr);
+ auto return_stmt = Backend::return_statement (fndecl, result, locus);
+ ctx->add_statement (return_stmt);
+ // BUILTIN ctlz FN BODY END
+
+ finalize_intrinsic_block (ctx, fndecl);
+ return fndecl;
+}
+
} // namespace inner
const HandlerBuilder
@@ -1530,6 +1675,18 @@ bswap_handler (Context *ctx, TyTy::FnType *fntype)
return fndecl;
}
+tree
+ctlz_handler (Context *ctx, TyTy::FnType *fntype)
+{
+ return inner::ctlz_handler (ctx, fntype, false);
+}
+
+tree
+ctlz_nonzero_handler (Context *ctx, TyTy::FnType *fntype)
+{
+ return inner::ctlz_handler (ctx, fntype, true);
+}
+
} // namespace handlers
} // namespace Compile
} // namespace Rust
diff --git a/gcc/rust/backend/rust-intrinsic-handlers.h
b/gcc/rust/backend/rust-intrinsic-handlers.h
index 06174a53574..52462407f82 100644
--- a/gcc/rust/backend/rust-intrinsic-handlers.h
+++ b/gcc/rust/backend/rust-intrinsic-handlers.h
@@ -65,6 +65,8 @@ tree assume (Context *ctx, TyTy::FnType *fntype);
tree discriminant_value (Context *ctx, TyTy::FnType *fntype);
tree variant_count (Context *ctx, TyTy::FnType *fntype);
tree bswap_handler (Context *ctx, TyTy::FnType *fntype);
+tree ctlz_handler (Context *ctx, TyTy::FnType *fntype);
+tree ctlz_nonzero_handler (Context *ctx, TyTy::FnType *fntype);
tree prefetch_data (Context *ctx, TyTy::FnType *fntype, Prefetch kind);
diff --git a/gcc/rust/util/rust-intrinsic-values.h
b/gcc/rust/util/rust-intrinsic-values.h
index 6754392a063..1b2d968b908 100644
--- a/gcc/rust/util/rust-intrinsic-values.h
+++ b/gcc/rust/util/rust-intrinsic-values.h
@@ -81,6 +81,7 @@ public:
static constexpr auto &CALLER_LOCATION = "caller_location";
static constexpr auto &CTPOP = "ctpop";
static constexpr auto &CTLZ = "ctlz";
+ static constexpr auto &CTLZ_NONZERO = "ctlz_nonzero";
static constexpr auto &CTTZ = "cttz";
static constexpr auto &BSWAP = "bswap";
static constexpr auto &BITREVERSE = "bitreverse";
diff --git a/gcc/testsuite/rust/compile/ctlz.rs
b/gcc/testsuite/rust/compile/ctlz.rs
new file mode 100644
index 00000000000..b886be774ea
--- /dev/null
+++ b/gcc/testsuite/rust/compile/ctlz.rs
@@ -0,0 +1,17 @@
+// { dg-do compile }
+#![feature(intrinsics, lang_items, no_core)]
+#![no_core]
+
+#[lang = "sized"]
+pub trait Sized {}
+
+#[lang = "copy"]
+pub trait Copy {}
+
+extern "rust-intrinsic" {
+ pub fn ctlz<T>(x: T) -> u32; // { dg-error "ctlz intrinsics can only be
used with basic integer types .got 'bool'." }
+}
+
+fn main() {
+ let _ = ctlz(true);
+}
diff --git a/gcc/testsuite/rust/compile/ctlz_nonzero.rs
b/gcc/testsuite/rust/compile/ctlz_nonzero.rs
new file mode 100644
index 00000000000..bf12728d215
--- /dev/null
+++ b/gcc/testsuite/rust/compile/ctlz_nonzero.rs
@@ -0,0 +1,19 @@
+// { dg-do compile }
+#![feature(intrinsics, lang_items, no_core)]
+#![no_core]
+
+#[lang = "sized"]
+pub trait Sized {}
+
+#[lang = "copy"]
+pub trait Copy {}
+
+extern "rust-intrinsic" {
+ pub fn ctlz_nonzero<T>(x: T) -> u32; // { dg-error "ctlz intrinsics can
only be used with basic integer types .got 'bool'." }
+}
+
+fn main() {
+ unsafe {
+ let _ = ctlz_nonzero(true);
+ }
+}
diff --git a/gcc/testsuite/rust/execute/torture/ctlz.rs
b/gcc/testsuite/rust/execute/torture/ctlz.rs
new file mode 100644
index 00000000000..bd8afba223f
--- /dev/null
+++ b/gcc/testsuite/rust/execute/torture/ctlz.rs
@@ -0,0 +1,56 @@
+#![feature(no_core)]
+#![no_core]
+#![feature(intrinsics)]
+#![feature(lang_items)]
+
+#[lang = "sized"]
+pub trait Sized {}
+
+extern "rust-intrinsic" {
+ pub fn ctlz<T>(x: T) -> u32;
+ pub fn abort() -> !;
+}
+
+fn main() -> i32 {
+ if ctlz(0u8) != 8 {
+ abort();
+ }
+ if ctlz(1u8) != 7 {
+ abort();
+ }
+ if ctlz(255u8) != 0 {
+ abort();
+ }
+
+ if ctlz(0u16) != 16 {
+ abort();
+ }
+ if ctlz(1u16) != 15 {
+ abort();
+ }
+ if ctlz(0xFFFFu16) != 0 {
+ abort();
+ }
+
+ if ctlz(0u32) != 32 {
+ abort();
+ }
+ if ctlz(1u32) != 31 {
+ abort();
+ }
+ if ctlz(0xFFFFFFFFu32) != 0 {
+ abort();
+ }
+
+ if ctlz(0u64) != 64 {
+ abort();
+ }
+ if ctlz(1u64) != 63 {
+ abort();
+ }
+ if ctlz(!0u64) != 0 {
+ abort();
+ }
+
+ 0
+}
diff --git a/gcc/testsuite/rust/execute/torture/ctlz_nonzero.rs
b/gcc/testsuite/rust/execute/torture/ctlz_nonzero.rs
new file mode 100644
index 00000000000..3476ab2b9a6
--- /dev/null
+++ b/gcc/testsuite/rust/execute/torture/ctlz_nonzero.rs
@@ -0,0 +1,46 @@
+#![feature(no_core)]
+#![no_core]
+#![feature(intrinsics)]
+#![feature(lang_items)]
+
+#[lang = "sized"]
+pub trait Sized {}
+
+extern "rust-intrinsic" {
+ pub fn ctlz_nonzero<T>(x: T) -> u32;
+ pub fn abort() -> !;
+}
+
+fn main() -> i32 {
+ unsafe {
+ if ctlz_nonzero(1u8) != 7 {
+ abort();
+ }
+ if ctlz_nonzero(255u8) != 0 {
+ abort();
+ }
+
+ if ctlz_nonzero(1u16) != 15 {
+ abort();
+ }
+ if ctlz_nonzero(0xFFFFu16) != 0 {
+ abort();
+ }
+
+ if ctlz_nonzero(1u32) != 31 {
+ abort();
+ }
+ if ctlz_nonzero(0xFFFFFFFFu32) != 0 {
+ abort();
+ }
+
+ if ctlz_nonzero(1u64) != 63 {
+ abort();
+ }
+ if ctlz_nonzero(!0u64) != 0 {
+ abort();
+ }
+ }
+
+ 0
+}
--
2.50.1
