[ir][spirv-writer] Polyfill first*Bit builtins
Add config options to polyfill firstLeadingBit and firstTrailingBit to
the generic BuiltinPolyfill transform.
Bug: tint:1906
Change-Id: I366eb8900cf79487beef7a701686e2b9f23a93d3
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/144981
Kokoro: Kokoro <noreply+kokoro@google.com>
Reviewed-by: Ben Clayton <bclayton@google.com>
Auto-Submit: James Price <jrprice@google.com>
diff --git a/src/tint/lang/core/ir/transform/builtin_polyfill.cc b/src/tint/lang/core/ir/transform/builtin_polyfill.cc
index db6563f..8d96925 100644
--- a/src/tint/lang/core/ir/transform/builtin_polyfill.cc
+++ b/src/tint/lang/core/ir/transform/builtin_polyfill.cc
@@ -54,6 +54,16 @@
}
if (auto* builtin = inst->As<ir::CoreBuiltinCall>()) {
switch (builtin->Func()) {
+ case core::Function::kFirstLeadingBit:
+ if (config.first_leading_bit) {
+ worklist.Push(builtin);
+ }
+ break;
+ case core::Function::kFirstTrailingBit:
+ if (config.first_trailing_bit) {
+ worklist.Push(builtin);
+ }
+ break;
case core::Function::kSaturate:
if (config.saturate) {
worklist.Push(builtin);
@@ -69,6 +79,12 @@
for (auto* builtin : worklist) {
ir::Value* replacement = nullptr;
switch (builtin->Func()) {
+ case core::Function::kFirstLeadingBit:
+ replacement = FirstLeadingBit(builtin);
+ break;
+ case core::Function::kFirstTrailingBit:
+ replacement = FirstTrailingBit(builtin);
+ break;
case core::Function::kSaturate:
replacement = Saturate(builtin);
break;
@@ -86,6 +102,154 @@
}
}
+ /// Return a type with element type @p type that has the same number of vector components as
+ /// @p match. If @p match is scalar just return @p type.
+ /// @param el_ty the type to extend
+ /// @param match the type to match the component count of
+ /// @returns a type with the same number of vector components as @p match
+ const type::Type* MatchWidth(const type::Type* el_ty, const type::Type* match) {
+ if (auto* vec = match->As<type::Vector>()) {
+ return ty.vec(el_ty, vec->Width());
+ }
+ return el_ty;
+ }
+
+ /// Return a constant that has the same number of vector components as @p match, each with the
+ /// value @p element. If @p match is scalar just return @p element.
+ /// @param element the value to extend
+ /// @param match the type to match the component count of
+ /// @returns a value with the same number of vector components as @p match
+ ir::Constant* MatchWidth(ir::Constant* element, const type::Type* match) {
+ if (auto* vec = match->As<type::Vector>()) {
+ return b.Splat(MatchWidth(element->Type(), match), element, vec->Width());
+ }
+ return element;
+ }
+
+ /// Polyfill a `firstLeadingBit()` builtin call.
+ /// @param call the builtin call instruction
+ /// @returns the replacement value
+ ir::Value* FirstLeadingBit(ir::CoreBuiltinCall* call) {
+ auto* input = call->Args()[0];
+ auto* result_ty = input->Type();
+ auto* uint_ty = MatchWidth(ty.u32(), result_ty);
+ auto* bool_ty = MatchWidth(ty.bool_(), result_ty);
+
+ // Make an u32 constant with the same component count as result_ty.
+ auto V = [&](uint32_t u) { return MatchWidth(b.Constant(u32(u)), result_ty); };
+
+ Value* result = nullptr;
+ b.InsertBefore(call, [&] {
+ // %x = %input;
+ // if (%x is signed) {
+ // %x = select(u32(%x), ~u32(%x), x > 0x80000000);
+ // }
+ // %b16 = select(16, 0, (%x & 0xffff0000) == 0);
+ // %x >>= %b16;
+ // %b8 = select(8, 0, (%x & 0x0000ff00) == 0);
+ // %x >>= %b8;
+ // %b4 = select(4, 0, (%x & 0x000000f0) == 0);
+ // %x >>= %b4;
+ // %b2 = select(2, 0, (%x & 0x0000000c) == 0);
+ // %x >>= %b2;
+ // %b1 = select(1, 0, (%x & 0x00000002) == 0);
+ // %result = %b16 | %b8 | %b4 | %b2 | %b1;
+ // %result = select(%result, 0xffffffff, %x == 0);
+
+ auto* x = input;
+ if (result_ty->is_signed_integer_scalar_or_vector()) {
+ x = b.Bitcast(uint_ty, x)->Result();
+ auto* inverted = b.Complement(uint_ty, x);
+ x = b.Call(uint_ty, core::Function::kSelect, inverted, x,
+ b.LessThan(bool_ty, x, V(0x80000000)))
+ ->Result();
+ }
+ auto* b16 = b.Call(uint_ty, core::Function::kSelect, V(16), V(0),
+ b.Equal(bool_ty, b.And(uint_ty, x, V(0xffff0000)), V(0)));
+ x = b.ShiftRight(uint_ty, x, b16)->Result();
+ auto* b8 = b.Call(uint_ty, core::Function::kSelect, V(8), V(0),
+ b.Equal(bool_ty, b.And(uint_ty, x, V(0x0000ff00)), V(0)));
+ x = b.ShiftRight(uint_ty, x, b8)->Result();
+ auto* b4 = b.Call(uint_ty, core::Function::kSelect, V(4), V(0),
+ b.Equal(bool_ty, b.And(uint_ty, x, V(0x000000f0)), V(0)));
+ x = b.ShiftRight(uint_ty, x, b4)->Result();
+ auto* b2 = b.Call(uint_ty, core::Function::kSelect, V(2), V(0),
+ b.Equal(bool_ty, b.And(uint_ty, x, V(0x0000000c)), V(0)));
+ x = b.ShiftRight(uint_ty, x, b2)->Result();
+ auto* b1 = b.Call(uint_ty, core::Function::kSelect, V(1), V(0),
+ b.Equal(bool_ty, b.And(uint_ty, x, V(0x00000002)), V(0)));
+ result = b.Or(uint_ty, b16, b.Or(uint_ty, b8, b.Or(uint_ty, b4, b.Or(uint_ty, b2, b1))))
+ ->Result();
+ result = b.Call(uint_ty, core::Function::kSelect, result, V(0xffffffff),
+ b.Equal(bool_ty, x, V(0)))
+ ->Result();
+ if (result_ty->is_signed_integer_scalar_or_vector()) {
+ result = b.Bitcast(result_ty, result)->Result();
+ }
+ });
+ return result;
+ }
+
+ /// Polyfill a `firstTrailingBit()` builtin call.
+ /// @param call the builtin call instruction
+ /// @returns the replacement value
+ ir::Value* FirstTrailingBit(ir::CoreBuiltinCall* call) {
+ auto* input = call->Args()[0];
+ auto* result_ty = input->Type();
+ auto* uint_ty = MatchWidth(ty.u32(), result_ty);
+ auto* bool_ty = MatchWidth(ty.bool_(), result_ty);
+
+ // Make an u32 constant with the same component count as result_ty.
+ auto V = [&](uint32_t u) { return MatchWidth(b.Constant(u32(u)), result_ty); };
+
+ Value* result = nullptr;
+ b.InsertBefore(call, [&] {
+ // %x = %input;
+ // if (%x is signed) {
+ // %x = bitcast<u32>(%x)
+ // }
+ // %b16 = select(0, 16, (%x & 0x0000ffff) == 0);
+ // %x >>= %b16;
+ // %b8 = select(0, 8, (%x & 0x000000ff) == 0);
+ // %x >>= %b8;
+ // %b4 = select(0, 4, (%x & 0x0000000f) == 0);
+ // %x >>= %b4;
+ // %b2 = select(0, 2, (%x & 0x00000003) == 0);
+ // %x >>= %b2;
+ // %b1 = select(0, 1, (%x & 0x00000001) == 0);
+ // %result = %b16 | %b8 | %b4 | %b2 | %b1;
+ // %result = select(%result, 0xffffffff, %x == 0);
+
+ auto* x = input;
+ if (result_ty->is_signed_integer_scalar_or_vector()) {
+ x = b.Bitcast(uint_ty, x)->Result();
+ }
+ auto* b16 = b.Call(uint_ty, core::Function::kSelect, V(0), V(16),
+ b.Equal(bool_ty, b.And(uint_ty, x, V(0x0000ffff)), V(0)));
+ x = b.ShiftRight(uint_ty, x, b16)->Result();
+ auto* b8 = b.Call(uint_ty, core::Function::kSelect, V(0), V(8),
+ b.Equal(bool_ty, b.And(uint_ty, x, V(0x000000ff)), V(0)));
+ x = b.ShiftRight(uint_ty, x, b8)->Result();
+ auto* b4 = b.Call(uint_ty, core::Function::kSelect, V(0), V(4),
+ b.Equal(bool_ty, b.And(uint_ty, x, V(0x0000000f)), V(0)));
+ x = b.ShiftRight(uint_ty, x, b4)->Result();
+ auto* b2 = b.Call(uint_ty, core::Function::kSelect, V(0), V(2),
+ b.Equal(bool_ty, b.And(uint_ty, x, V(0x00000003)), V(0)));
+ x = b.ShiftRight(uint_ty, x, b2)->Result();
+ auto* b1 = b.Call(uint_ty, core::Function::kSelect, V(0), V(1),
+ b.Equal(bool_ty, b.And(uint_ty, x, V(0x00000001)), V(0)));
+ result = b.Or(uint_ty, b16, b.Or(uint_ty, b8, b.Or(uint_ty, b4, b.Or(uint_ty, b2, b1))))
+ ->Result();
+ result = b.Call(uint_ty, core::Function::kSelect, result, V(0xffffffff),
+ b.Equal(bool_ty, x, V(0)))
+ ->Result();
+ if (result_ty->is_signed_integer_scalar_or_vector()) {
+ result = b.Bitcast(result_ty, result)->Result();
+ }
+ });
+ return result;
+ }
+
/// Polyfill a `saturate()` builtin call.
/// @param call the builtin call instruction
/// @returns the replacement value
@@ -95,16 +259,11 @@
ir::Constant* zero = nullptr;
ir::Constant* one = nullptr;
if (type->DeepestElement()->Is<type::F32>()) {
- zero = b.Constant(0_f);
- one = b.Constant(1_f);
+ zero = MatchWidth(b.Constant(0_f), type);
+ one = MatchWidth(b.Constant(1_f), type);
} else if (type->DeepestElement()->Is<type::F16>()) {
- zero = b.Constant(0_h);
- one = b.Constant(1_h);
- }
- if (auto* vec = type->As<type::Vector>()) {
- // Splat the zero and one arguments to vectors.
- zero = b.Splat(vec, zero, vec->Width());
- one = b.Splat(vec, one, vec->Width());
+ zero = MatchWidth(b.Constant(0_h), type);
+ one = MatchWidth(b.Constant(1_h), type);
}
auto* clamp = b.Call(type, core::Function::kClamp, Vector{call->Args()[0], zero, one});
clamp->InsertBefore(call);
diff --git a/src/tint/lang/core/ir/transform/builtin_polyfill.h b/src/tint/lang/core/ir/transform/builtin_polyfill.h
index 948b946..1ec91a8 100644
--- a/src/tint/lang/core/ir/transform/builtin_polyfill.h
+++ b/src/tint/lang/core/ir/transform/builtin_polyfill.h
@@ -28,6 +28,10 @@
/// The set of polyfills that should be applied.
struct BuiltinPolyfillConfig {
+ /// Should `firstLeadingBit()` be polyfilled?
+ bool first_leading_bit = false;
+ /// Should `firstTrailingBit()` be polyfilled?
+ bool first_trailing_bit = false;
/// Should `saturate()` be polyfilled?
bool saturate = false;
};
diff --git a/src/tint/lang/core/ir/transform/builtin_polyfill_test.cc b/src/tint/lang/core/ir/transform/builtin_polyfill_test.cc
index 62bdb1f..000ddf2 100644
--- a/src/tint/lang/core/ir/transform/builtin_polyfill_test.cc
+++ b/src/tint/lang/core/ir/transform/builtin_polyfill_test.cc
@@ -174,5 +174,467 @@
EXPECT_EQ(expect, str());
}
+TEST_F(IR_BuiltinPolyfillTest, FirstLeadingBit_NoPolyfill) {
+ Build(core::Function::kFirstLeadingBit, ty.u32(), Vector{ty.u32()});
+ auto* src = R"(
+%foo = func(%arg:u32):u32 -> %b1 {
+ %b1 = block {
+ %result:u32 = firstLeadingBit %arg
+ ret %result
+ }
+}
+)";
+ auto* expect = src;
+
+ EXPECT_EQ(src, str());
+
+ BuiltinPolyfillConfig config;
+ config.first_leading_bit = false;
+ Run(BuiltinPolyfill, config);
+ EXPECT_EQ(expect, str());
+}
+
+TEST_F(IR_BuiltinPolyfillTest, FirstLeadingBit_U32) {
+ Build(core::Function::kFirstLeadingBit, ty.u32(), Vector{ty.u32()});
+ auto* src = R"(
+%foo = func(%arg:u32):u32 -> %b1 {
+ %b1 = block {
+ %result:u32 = firstLeadingBit %arg
+ ret %result
+ }
+}
+)";
+ auto* expect = R"(
+%foo = func(%arg:u32):u32 -> %b1 {
+ %b1 = block {
+ %3:u32 = and %arg, 4294901760u
+ %4:bool = eq %3, 0u
+ %5:u32 = select 16u, 0u, %4
+ %6:u32 = shiftr %arg, %5
+ %7:u32 = and %6, 65280u
+ %8:bool = eq %7, 0u
+ %9:u32 = select 8u, 0u, %8
+ %10:u32 = shiftr %6, %9
+ %11:u32 = and %10, 240u
+ %12:bool = eq %11, 0u
+ %13:u32 = select 4u, 0u, %12
+ %14:u32 = shiftr %10, %13
+ %15:u32 = and %14, 12u
+ %16:bool = eq %15, 0u
+ %17:u32 = select 2u, 0u, %16
+ %18:u32 = shiftr %14, %17
+ %19:u32 = and %18, 2u
+ %20:bool = eq %19, 0u
+ %21:u32 = select 1u, 0u, %20
+ %22:u32 = or %17, %21
+ %23:u32 = or %13, %22
+ %24:u32 = or %9, %23
+ %25:u32 = or %5, %24
+ %26:bool = eq %18, 0u
+ %result:u32 = select %25, 4294967295u, %26
+ ret %result
+ }
+}
+)";
+
+ EXPECT_EQ(src, str());
+
+ BuiltinPolyfillConfig config;
+ config.first_leading_bit = true;
+ Run(BuiltinPolyfill, config);
+ EXPECT_EQ(expect, str());
+}
+
+TEST_F(IR_BuiltinPolyfillTest, FirstLeadingBit_I32) {
+ Build(core::Function::kFirstLeadingBit, ty.i32(), Vector{ty.i32()});
+ auto* src = R"(
+%foo = func(%arg:i32):i32 -> %b1 {
+ %b1 = block {
+ %result:i32 = firstLeadingBit %arg
+ ret %result
+ }
+}
+)";
+ auto* expect = R"(
+%foo = func(%arg:i32):i32 -> %b1 {
+ %b1 = block {
+ %3:u32 = bitcast %arg
+ %4:u32 = complement %3
+ %5:bool = lt %3, 2147483648u
+ %6:u32 = select %4, %3, %5
+ %7:u32 = and %6, 4294901760u
+ %8:bool = eq %7, 0u
+ %9:u32 = select 16u, 0u, %8
+ %10:u32 = shiftr %6, %9
+ %11:u32 = and %10, 65280u
+ %12:bool = eq %11, 0u
+ %13:u32 = select 8u, 0u, %12
+ %14:u32 = shiftr %10, %13
+ %15:u32 = and %14, 240u
+ %16:bool = eq %15, 0u
+ %17:u32 = select 4u, 0u, %16
+ %18:u32 = shiftr %14, %17
+ %19:u32 = and %18, 12u
+ %20:bool = eq %19, 0u
+ %21:u32 = select 2u, 0u, %20
+ %22:u32 = shiftr %18, %21
+ %23:u32 = and %22, 2u
+ %24:bool = eq %23, 0u
+ %25:u32 = select 1u, 0u, %24
+ %26:u32 = or %21, %25
+ %27:u32 = or %17, %26
+ %28:u32 = or %13, %27
+ %29:u32 = or %9, %28
+ %30:bool = eq %22, 0u
+ %31:u32 = select %29, 4294967295u, %30
+ %result:i32 = bitcast %31
+ ret %result
+ }
+}
+)";
+
+ EXPECT_EQ(src, str());
+
+ BuiltinPolyfillConfig config;
+ config.first_leading_bit = true;
+ Run(BuiltinPolyfill, config);
+ EXPECT_EQ(expect, str());
+}
+
+TEST_F(IR_BuiltinPolyfillTest, FirstLeadingBit_Vec2U32) {
+ Build(core::Function::kFirstLeadingBit, ty.vec2<u32>(), Vector{ty.vec2<u32>()});
+ auto* src = R"(
+%foo = func(%arg:vec2<u32>):vec2<u32> -> %b1 {
+ %b1 = block {
+ %result:vec2<u32> = firstLeadingBit %arg
+ ret %result
+ }
+}
+)";
+ auto* expect = R"(
+%foo = func(%arg:vec2<u32>):vec2<u32> -> %b1 {
+ %b1 = block {
+ %3:vec2<u32> = and %arg, vec2<u32>(4294901760u)
+ %4:vec2<bool> = eq %3, vec2<u32>(0u)
+ %5:vec2<u32> = select vec2<u32>(16u), vec2<u32>(0u), %4
+ %6:vec2<u32> = shiftr %arg, %5
+ %7:vec2<u32> = and %6, vec2<u32>(65280u)
+ %8:vec2<bool> = eq %7, vec2<u32>(0u)
+ %9:vec2<u32> = select vec2<u32>(8u), vec2<u32>(0u), %8
+ %10:vec2<u32> = shiftr %6, %9
+ %11:vec2<u32> = and %10, vec2<u32>(240u)
+ %12:vec2<bool> = eq %11, vec2<u32>(0u)
+ %13:vec2<u32> = select vec2<u32>(4u), vec2<u32>(0u), %12
+ %14:vec2<u32> = shiftr %10, %13
+ %15:vec2<u32> = and %14, vec2<u32>(12u)
+ %16:vec2<bool> = eq %15, vec2<u32>(0u)
+ %17:vec2<u32> = select vec2<u32>(2u), vec2<u32>(0u), %16
+ %18:vec2<u32> = shiftr %14, %17
+ %19:vec2<u32> = and %18, vec2<u32>(2u)
+ %20:vec2<bool> = eq %19, vec2<u32>(0u)
+ %21:vec2<u32> = select vec2<u32>(1u), vec2<u32>(0u), %20
+ %22:vec2<u32> = or %17, %21
+ %23:vec2<u32> = or %13, %22
+ %24:vec2<u32> = or %9, %23
+ %25:vec2<u32> = or %5, %24
+ %26:vec2<bool> = eq %18, vec2<u32>(0u)
+ %result:vec2<u32> = select %25, vec2<u32>(4294967295u), %26
+ ret %result
+ }
+}
+)";
+
+ EXPECT_EQ(src, str());
+
+ BuiltinPolyfillConfig config;
+ config.first_leading_bit = true;
+ Run(BuiltinPolyfill, config);
+ EXPECT_EQ(expect, str());
+}
+
+TEST_F(IR_BuiltinPolyfillTest, FirstLeadingBit_Vec4I32) {
+ Build(core::Function::kFirstLeadingBit, ty.vec4<i32>(), Vector{ty.vec4<i32>()});
+ auto* src = R"(
+%foo = func(%arg:vec4<i32>):vec4<i32> -> %b1 {
+ %b1 = block {
+ %result:vec4<i32> = firstLeadingBit %arg
+ ret %result
+ }
+}
+)";
+ auto* expect = R"(
+%foo = func(%arg:vec4<i32>):vec4<i32> -> %b1 {
+ %b1 = block {
+ %3:vec4<u32> = bitcast %arg
+ %4:vec4<u32> = complement %3
+ %5:vec4<bool> = lt %3, vec4<u32>(2147483648u)
+ %6:vec4<u32> = select %4, %3, %5
+ %7:vec4<u32> = and %6, vec4<u32>(4294901760u)
+ %8:vec4<bool> = eq %7, vec4<u32>(0u)
+ %9:vec4<u32> = select vec4<u32>(16u), vec4<u32>(0u), %8
+ %10:vec4<u32> = shiftr %6, %9
+ %11:vec4<u32> = and %10, vec4<u32>(65280u)
+ %12:vec4<bool> = eq %11, vec4<u32>(0u)
+ %13:vec4<u32> = select vec4<u32>(8u), vec4<u32>(0u), %12
+ %14:vec4<u32> = shiftr %10, %13
+ %15:vec4<u32> = and %14, vec4<u32>(240u)
+ %16:vec4<bool> = eq %15, vec4<u32>(0u)
+ %17:vec4<u32> = select vec4<u32>(4u), vec4<u32>(0u), %16
+ %18:vec4<u32> = shiftr %14, %17
+ %19:vec4<u32> = and %18, vec4<u32>(12u)
+ %20:vec4<bool> = eq %19, vec4<u32>(0u)
+ %21:vec4<u32> = select vec4<u32>(2u), vec4<u32>(0u), %20
+ %22:vec4<u32> = shiftr %18, %21
+ %23:vec4<u32> = and %22, vec4<u32>(2u)
+ %24:vec4<bool> = eq %23, vec4<u32>(0u)
+ %25:vec4<u32> = select vec4<u32>(1u), vec4<u32>(0u), %24
+ %26:vec4<u32> = or %21, %25
+ %27:vec4<u32> = or %17, %26
+ %28:vec4<u32> = or %13, %27
+ %29:vec4<u32> = or %9, %28
+ %30:vec4<bool> = eq %22, vec4<u32>(0u)
+ %31:vec4<u32> = select %29, vec4<u32>(4294967295u), %30
+ %result:vec4<i32> = bitcast %31
+ ret %result
+ }
+}
+)";
+
+ EXPECT_EQ(src, str());
+
+ BuiltinPolyfillConfig config;
+ config.first_leading_bit = true;
+ Run(BuiltinPolyfill, config);
+ EXPECT_EQ(expect, str());
+}
+
+TEST_F(IR_BuiltinPolyfillTest, FirstTrailingBit_NoPolyfill) {
+ Build(core::Function::kFirstTrailingBit, ty.u32(), Vector{ty.u32()});
+ auto* src = R"(
+%foo = func(%arg:u32):u32 -> %b1 {
+ %b1 = block {
+ %result:u32 = firstTrailingBit %arg
+ ret %result
+ }
+}
+)";
+ auto* expect = src;
+
+ EXPECT_EQ(src, str());
+
+ BuiltinPolyfillConfig config;
+ config.first_trailing_bit = false;
+ Run(BuiltinPolyfill, config);
+ EXPECT_EQ(expect, str());
+}
+
+TEST_F(IR_BuiltinPolyfillTest, FirstTrailingBit_U32) {
+ Build(core::Function::kFirstTrailingBit, ty.u32(), Vector{ty.u32()});
+ auto* src = R"(
+%foo = func(%arg:u32):u32 -> %b1 {
+ %b1 = block {
+ %result:u32 = firstTrailingBit %arg
+ ret %result
+ }
+}
+)";
+ auto* expect = R"(
+%foo = func(%arg:u32):u32 -> %b1 {
+ %b1 = block {
+ %3:u32 = and %arg, 65535u
+ %4:bool = eq %3, 0u
+ %5:u32 = select 0u, 16u, %4
+ %6:u32 = shiftr %arg, %5
+ %7:u32 = and %6, 255u
+ %8:bool = eq %7, 0u
+ %9:u32 = select 0u, 8u, %8
+ %10:u32 = shiftr %6, %9
+ %11:u32 = and %10, 15u
+ %12:bool = eq %11, 0u
+ %13:u32 = select 0u, 4u, %12
+ %14:u32 = shiftr %10, %13
+ %15:u32 = and %14, 3u
+ %16:bool = eq %15, 0u
+ %17:u32 = select 0u, 2u, %16
+ %18:u32 = shiftr %14, %17
+ %19:u32 = and %18, 1u
+ %20:bool = eq %19, 0u
+ %21:u32 = select 0u, 1u, %20
+ %22:u32 = or %17, %21
+ %23:u32 = or %13, %22
+ %24:u32 = or %9, %23
+ %25:u32 = or %5, %24
+ %26:bool = eq %18, 0u
+ %result:u32 = select %25, 4294967295u, %26
+ ret %result
+ }
+}
+)";
+
+ EXPECT_EQ(src, str());
+
+ BuiltinPolyfillConfig config;
+ config.first_trailing_bit = true;
+ Run(BuiltinPolyfill, config);
+ EXPECT_EQ(expect, str());
+}
+
+TEST_F(IR_BuiltinPolyfillTest, FirstTrailingBit_I32) {
+ Build(core::Function::kFirstTrailingBit, ty.i32(), Vector{ty.i32()});
+ auto* src = R"(
+%foo = func(%arg:i32):i32 -> %b1 {
+ %b1 = block {
+ %result:i32 = firstTrailingBit %arg
+ ret %result
+ }
+}
+)";
+ auto* expect = R"(
+%foo = func(%arg:i32):i32 -> %b1 {
+ %b1 = block {
+ %3:u32 = bitcast %arg
+ %4:u32 = and %3, 65535u
+ %5:bool = eq %4, 0u
+ %6:u32 = select 0u, 16u, %5
+ %7:u32 = shiftr %3, %6
+ %8:u32 = and %7, 255u
+ %9:bool = eq %8, 0u
+ %10:u32 = select 0u, 8u, %9
+ %11:u32 = shiftr %7, %10
+ %12:u32 = and %11, 15u
+ %13:bool = eq %12, 0u
+ %14:u32 = select 0u, 4u, %13
+ %15:u32 = shiftr %11, %14
+ %16:u32 = and %15, 3u
+ %17:bool = eq %16, 0u
+ %18:u32 = select 0u, 2u, %17
+ %19:u32 = shiftr %15, %18
+ %20:u32 = and %19, 1u
+ %21:bool = eq %20, 0u
+ %22:u32 = select 0u, 1u, %21
+ %23:u32 = or %18, %22
+ %24:u32 = or %14, %23
+ %25:u32 = or %10, %24
+ %26:u32 = or %6, %25
+ %27:bool = eq %19, 0u
+ %28:u32 = select %26, 4294967295u, %27
+ %result:i32 = bitcast %28
+ ret %result
+ }
+}
+)";
+
+ EXPECT_EQ(src, str());
+
+ BuiltinPolyfillConfig config;
+ config.first_trailing_bit = true;
+ Run(BuiltinPolyfill, config);
+ EXPECT_EQ(expect, str());
+}
+
+TEST_F(IR_BuiltinPolyfillTest, FirstTrailingBit_Vec2U32) {
+ Build(core::Function::kFirstTrailingBit, ty.vec2<u32>(), Vector{ty.vec2<u32>()});
+ auto* src = R"(
+%foo = func(%arg:vec2<u32>):vec2<u32> -> %b1 {
+ %b1 = block {
+ %result:vec2<u32> = firstTrailingBit %arg
+ ret %result
+ }
+}
+)";
+ auto* expect = R"(
+%foo = func(%arg:vec2<u32>):vec2<u32> -> %b1 {
+ %b1 = block {
+ %3:vec2<u32> = and %arg, vec2<u32>(65535u)
+ %4:vec2<bool> = eq %3, vec2<u32>(0u)
+ %5:vec2<u32> = select vec2<u32>(0u), vec2<u32>(16u), %4
+ %6:vec2<u32> = shiftr %arg, %5
+ %7:vec2<u32> = and %6, vec2<u32>(255u)
+ %8:vec2<bool> = eq %7, vec2<u32>(0u)
+ %9:vec2<u32> = select vec2<u32>(0u), vec2<u32>(8u), %8
+ %10:vec2<u32> = shiftr %6, %9
+ %11:vec2<u32> = and %10, vec2<u32>(15u)
+ %12:vec2<bool> = eq %11, vec2<u32>(0u)
+ %13:vec2<u32> = select vec2<u32>(0u), vec2<u32>(4u), %12
+ %14:vec2<u32> = shiftr %10, %13
+ %15:vec2<u32> = and %14, vec2<u32>(3u)
+ %16:vec2<bool> = eq %15, vec2<u32>(0u)
+ %17:vec2<u32> = select vec2<u32>(0u), vec2<u32>(2u), %16
+ %18:vec2<u32> = shiftr %14, %17
+ %19:vec2<u32> = and %18, vec2<u32>(1u)
+ %20:vec2<bool> = eq %19, vec2<u32>(0u)
+ %21:vec2<u32> = select vec2<u32>(0u), vec2<u32>(1u), %20
+ %22:vec2<u32> = or %17, %21
+ %23:vec2<u32> = or %13, %22
+ %24:vec2<u32> = or %9, %23
+ %25:vec2<u32> = or %5, %24
+ %26:vec2<bool> = eq %18, vec2<u32>(0u)
+ %result:vec2<u32> = select %25, vec2<u32>(4294967295u), %26
+ ret %result
+ }
+}
+)";
+
+ EXPECT_EQ(src, str());
+
+ BuiltinPolyfillConfig config;
+ config.first_trailing_bit = true;
+ Run(BuiltinPolyfill, config);
+ EXPECT_EQ(expect, str());
+}
+
+TEST_F(IR_BuiltinPolyfillTest, FirstTrailingBit_Vec4I32) {
+ Build(core::Function::kFirstTrailingBit, ty.vec4<i32>(), Vector{ty.vec4<i32>()});
+ auto* src = R"(
+%foo = func(%arg:vec4<i32>):vec4<i32> -> %b1 {
+ %b1 = block {
+ %result:vec4<i32> = firstTrailingBit %arg
+ ret %result
+ }
+}
+)";
+ auto* expect = R"(
+%foo = func(%arg:vec4<i32>):vec4<i32> -> %b1 {
+ %b1 = block {
+ %3:vec4<u32> = bitcast %arg
+ %4:vec4<u32> = and %3, vec4<u32>(65535u)
+ %5:vec4<bool> = eq %4, vec4<u32>(0u)
+ %6:vec4<u32> = select vec4<u32>(0u), vec4<u32>(16u), %5
+ %7:vec4<u32> = shiftr %3, %6
+ %8:vec4<u32> = and %7, vec4<u32>(255u)
+ %9:vec4<bool> = eq %8, vec4<u32>(0u)
+ %10:vec4<u32> = select vec4<u32>(0u), vec4<u32>(8u), %9
+ %11:vec4<u32> = shiftr %7, %10
+ %12:vec4<u32> = and %11, vec4<u32>(15u)
+ %13:vec4<bool> = eq %12, vec4<u32>(0u)
+ %14:vec4<u32> = select vec4<u32>(0u), vec4<u32>(4u), %13
+ %15:vec4<u32> = shiftr %11, %14
+ %16:vec4<u32> = and %15, vec4<u32>(3u)
+ %17:vec4<bool> = eq %16, vec4<u32>(0u)
+ %18:vec4<u32> = select vec4<u32>(0u), vec4<u32>(2u), %17
+ %19:vec4<u32> = shiftr %15, %18
+ %20:vec4<u32> = and %19, vec4<u32>(1u)
+ %21:vec4<bool> = eq %20, vec4<u32>(0u)
+ %22:vec4<u32> = select vec4<u32>(0u), vec4<u32>(1u), %21
+ %23:vec4<u32> = or %18, %22
+ %24:vec4<u32> = or %14, %23
+ %25:vec4<u32> = or %10, %24
+ %26:vec4<u32> = or %6, %25
+ %27:vec4<bool> = eq %19, vec4<u32>(0u)
+ %28:vec4<u32> = select %26, vec4<u32>(4294967295u), %27
+ %result:vec4<i32> = bitcast %28
+ ret %result
+ }
+}
+)";
+
+ EXPECT_EQ(src, str());
+
+ BuiltinPolyfillConfig config;
+ config.first_trailing_bit = true;
+ Run(BuiltinPolyfill, config);
+ EXPECT_EQ(expect, str());
+}
+
} // namespace
} // namespace tint::ir::transform
diff --git a/src/tint/lang/spirv/writer/builtin_test.cc b/src/tint/lang/spirv/writer/builtin_test.cc
index d180b56..2ba7054 100644
--- a/src/tint/lang/spirv/writer/builtin_test.cc
+++ b/src/tint/lang/spirv/writer/builtin_test.cc
@@ -598,6 +598,275 @@
EXPECT_INST("%result = OpExtInst %v4float %9 UnpackUnorm4x8 %arg");
}
+TEST_F(SpirvWriterTest, Builtin_FirstLeadingBit_U32) {
+ auto* arg = b.FunctionParam("arg", ty.u32());
+ auto* func = b.Function("foo", ty.u32());
+ func->SetParams({arg});
+ b.Append(func->Block(), [&] {
+ auto* result = b.Call(ty.u32(), core::Function::kFirstLeadingBit, arg);
+ b.Return(func, result);
+ mod.SetName(result, "result");
+ });
+
+ ASSERT_TRUE(Generate()) << Error() << output_;
+ EXPECT_INST(R"(
+ %6 = OpBitwiseAnd %uint %arg %uint_4294901760
+ %8 = OpIEqual %bool %6 %uint_0
+ %11 = OpSelect %uint %8 %uint_0 %uint_16
+ %13 = OpShiftRightLogical %uint %arg %11
+ %14 = OpBitwiseAnd %uint %13 %uint_65280
+ %16 = OpIEqual %bool %14 %uint_0
+ %17 = OpSelect %uint %16 %uint_0 %uint_8
+ %19 = OpShiftRightLogical %uint %13 %17
+ %20 = OpBitwiseAnd %uint %19 %uint_240
+ %22 = OpIEqual %bool %20 %uint_0
+ %23 = OpSelect %uint %22 %uint_0 %uint_4
+ %25 = OpShiftRightLogical %uint %19 %23
+ %26 = OpBitwiseAnd %uint %25 %uint_12
+ %28 = OpIEqual %bool %26 %uint_0
+ %29 = OpSelect %uint %28 %uint_0 %uint_2
+ %31 = OpShiftRightLogical %uint %25 %29
+ %32 = OpBitwiseAnd %uint %31 %uint_2
+ %33 = OpIEqual %bool %32 %uint_0
+ %34 = OpSelect %uint %33 %uint_0 %uint_1
+ %36 = OpBitwiseOr %uint %29 %34
+ %37 = OpBitwiseOr %uint %23 %36
+ %38 = OpBitwiseOr %uint %17 %37
+ %39 = OpBitwiseOr %uint %11 %38
+ %40 = OpIEqual %bool %31 %uint_0
+ %result = OpSelect %uint %40 %uint_4294967295 %39
+)");
+}
+
+TEST_F(SpirvWriterTest, Builtin_FirstLeadingBit_I32) {
+ auto* arg = b.FunctionParam("arg", ty.i32());
+ auto* func = b.Function("foo", ty.i32());
+ func->SetParams({arg});
+ b.Append(func->Block(), [&] {
+ auto* result = b.Call(ty.i32(), core::Function::kFirstLeadingBit, arg);
+ b.Return(func, result);
+ mod.SetName(result, "result");
+ });
+
+ ASSERT_TRUE(Generate()) << Error() << output_;
+ EXPECT_INST(R"(
+ %7 = OpBitcast %uint %arg
+ %8 = OpNot %uint %7
+ %9 = OpULessThan %bool %7 %uint_2147483648
+ %12 = OpSelect %uint %9 %7 %8
+ %13 = OpBitwiseAnd %uint %12 %uint_4294901760
+ %15 = OpIEqual %bool %13 %uint_0
+ %17 = OpSelect %uint %15 %uint_0 %uint_16
+ %19 = OpShiftRightLogical %uint %12 %17
+ %20 = OpBitwiseAnd %uint %19 %uint_65280
+ %22 = OpIEqual %bool %20 %uint_0
+ %23 = OpSelect %uint %22 %uint_0 %uint_8
+ %25 = OpShiftRightLogical %uint %19 %23
+ %26 = OpBitwiseAnd %uint %25 %uint_240
+ %28 = OpIEqual %bool %26 %uint_0
+ %29 = OpSelect %uint %28 %uint_0 %uint_4
+ %31 = OpShiftRightLogical %uint %25 %29
+ %32 = OpBitwiseAnd %uint %31 %uint_12
+ %34 = OpIEqual %bool %32 %uint_0
+ %35 = OpSelect %uint %34 %uint_0 %uint_2
+ %37 = OpShiftRightLogical %uint %31 %35
+ %38 = OpBitwiseAnd %uint %37 %uint_2
+ %39 = OpIEqual %bool %38 %uint_0
+ %40 = OpSelect %uint %39 %uint_0 %uint_1
+ %42 = OpBitwiseOr %uint %35 %40
+ %43 = OpBitwiseOr %uint %29 %42
+ %44 = OpBitwiseOr %uint %23 %43
+ %45 = OpBitwiseOr %uint %17 %44
+ %46 = OpIEqual %bool %37 %uint_0
+ %47 = OpSelect %uint %46 %uint_4294967295 %45
+ %result = OpBitcast %int %47
+)");
+}
+
+TEST_F(SpirvWriterTest, Builtin_FirstLeadingBit_Vec2U32) {
+ auto* arg = b.FunctionParam("arg", ty.vec2<u32>());
+ auto* func = b.Function("foo", ty.vec2<u32>());
+ func->SetParams({arg});
+ b.Append(func->Block(), [&] {
+ auto* result = b.Call(ty.vec2<u32>(), core::Function::kFirstLeadingBit, arg);
+ b.Return(func, result);
+ mod.SetName(result, "result");
+ });
+
+ ASSERT_TRUE(Generate()) << Error() << output_;
+ EXPECT_INST("%8 = OpConstantComposite %v2uint %uint_4294901760 %uint_4294901760");
+ EXPECT_INST("%11 = OpConstantComposite %v2uint %uint_0 %uint_0");
+ EXPECT_INST("%16 = OpConstantComposite %v2uint %uint_16 %uint_16");
+ EXPECT_INST("%20 = OpConstantComposite %v2uint %uint_65280 %uint_65280");
+ EXPECT_INST("%24 = OpConstantComposite %v2uint %uint_8 %uint_8");
+ EXPECT_INST("%28 = OpConstantComposite %v2uint %uint_240 %uint_240");
+ EXPECT_INST("%32 = OpConstantComposite %v2uint %uint_4 %uint_4");
+ EXPECT_INST("%36 = OpConstantComposite %v2uint %uint_12 %uint_12");
+ EXPECT_INST("%40 = OpConstantComposite %v2uint %uint_2 %uint_2");
+ EXPECT_INST("%46 = OpConstantComposite %v2uint %uint_1 %uint_1");
+ EXPECT_INST("%54 = OpConstantComposite %v2uint %uint_4294967295 %uint_4294967295");
+ EXPECT_INST(R"(
+ %7 = OpBitwiseAnd %v2uint %arg %8
+ %10 = OpIEqual %v2bool %7 %11
+ %15 = OpSelect %v2uint %10 %11 %16
+ %18 = OpShiftRightLogical %v2uint %arg %15
+ %19 = OpBitwiseAnd %v2uint %18 %20
+ %22 = OpIEqual %v2bool %19 %11
+ %23 = OpSelect %v2uint %22 %11 %24
+ %26 = OpShiftRightLogical %v2uint %18 %23
+ %27 = OpBitwiseAnd %v2uint %26 %28
+ %30 = OpIEqual %v2bool %27 %11
+ %31 = OpSelect %v2uint %30 %11 %32
+ %34 = OpShiftRightLogical %v2uint %26 %31
+ %35 = OpBitwiseAnd %v2uint %34 %36
+ %38 = OpIEqual %v2bool %35 %11
+ %39 = OpSelect %v2uint %38 %11 %40
+ %42 = OpShiftRightLogical %v2uint %34 %39
+ %43 = OpBitwiseAnd %v2uint %42 %40
+ %44 = OpIEqual %v2bool %43 %11
+ %45 = OpSelect %v2uint %44 %11 %46
+ %48 = OpBitwiseOr %v2uint %39 %45
+ %49 = OpBitwiseOr %v2uint %31 %48
+ %50 = OpBitwiseOr %v2uint %23 %49
+ %51 = OpBitwiseOr %v2uint %15 %50
+ %52 = OpIEqual %v2bool %42 %11
+ %result = OpSelect %v2uint %52 %54 %51
+)");
+}
+
+TEST_F(SpirvWriterTest, Builtin_FirstTrailingBit_U32) {
+ auto* arg = b.FunctionParam("arg", ty.u32());
+ auto* func = b.Function("foo", ty.u32());
+ func->SetParams({arg});
+ b.Append(func->Block(), [&] {
+ auto* result = b.Call(ty.u32(), core::Function::kFirstTrailingBit, arg);
+ b.Return(func, result);
+ mod.SetName(result, "result");
+ });
+
+ ASSERT_TRUE(Generate()) << Error() << output_;
+ EXPECT_INST(R"(
+ %6 = OpBitwiseAnd %uint %arg %uint_65535
+ %8 = OpIEqual %bool %6 %uint_0
+ %11 = OpSelect %uint %8 %uint_16 %uint_0
+ %13 = OpShiftRightLogical %uint %arg %11
+ %14 = OpBitwiseAnd %uint %13 %uint_255
+ %16 = OpIEqual %bool %14 %uint_0
+ %17 = OpSelect %uint %16 %uint_8 %uint_0
+ %19 = OpShiftRightLogical %uint %13 %17
+ %20 = OpBitwiseAnd %uint %19 %uint_15
+ %22 = OpIEqual %bool %20 %uint_0
+ %23 = OpSelect %uint %22 %uint_4 %uint_0
+ %25 = OpShiftRightLogical %uint %19 %23
+ %26 = OpBitwiseAnd %uint %25 %uint_3
+ %28 = OpIEqual %bool %26 %uint_0
+ %29 = OpSelect %uint %28 %uint_2 %uint_0
+ %31 = OpShiftRightLogical %uint %25 %29
+ %32 = OpBitwiseAnd %uint %31 %uint_1
+ %34 = OpIEqual %bool %32 %uint_0
+ %35 = OpSelect %uint %34 %uint_1 %uint_0
+ %36 = OpBitwiseOr %uint %29 %35
+ %37 = OpBitwiseOr %uint %23 %36
+ %38 = OpBitwiseOr %uint %17 %37
+ %39 = OpBitwiseOr %uint %11 %38
+ %40 = OpIEqual %bool %31 %uint_0
+ %result = OpSelect %uint %40 %uint_4294967295 %39
+)");
+}
+
+TEST_F(SpirvWriterTest, Builtin_FirstTrailingBit_I32) {
+ auto* arg = b.FunctionParam("arg", ty.i32());
+ auto* func = b.Function("foo", ty.i32());
+ func->SetParams({arg});
+ b.Append(func->Block(), [&] {
+ auto* result = b.Call(ty.i32(), core::Function::kFirstTrailingBit, arg);
+ b.Return(func, result);
+ mod.SetName(result, "result");
+ });
+
+ ASSERT_TRUE(Generate()) << Error() << output_;
+ EXPECT_INST(R"(
+ %7 = OpBitcast %uint %arg
+ %8 = OpBitwiseAnd %uint %7 %uint_65535
+ %10 = OpIEqual %bool %8 %uint_0
+ %13 = OpSelect %uint %10 %uint_16 %uint_0
+ %15 = OpShiftRightLogical %uint %7 %13
+ %16 = OpBitwiseAnd %uint %15 %uint_255
+ %18 = OpIEqual %bool %16 %uint_0
+ %19 = OpSelect %uint %18 %uint_8 %uint_0
+ %21 = OpShiftRightLogical %uint %15 %19
+ %22 = OpBitwiseAnd %uint %21 %uint_15
+ %24 = OpIEqual %bool %22 %uint_0
+ %25 = OpSelect %uint %24 %uint_4 %uint_0
+ %27 = OpShiftRightLogical %uint %21 %25
+ %28 = OpBitwiseAnd %uint %27 %uint_3
+ %30 = OpIEqual %bool %28 %uint_0
+ %31 = OpSelect %uint %30 %uint_2 %uint_0
+ %33 = OpShiftRightLogical %uint %27 %31
+ %34 = OpBitwiseAnd %uint %33 %uint_1
+ %36 = OpIEqual %bool %34 %uint_0
+ %37 = OpSelect %uint %36 %uint_1 %uint_0
+ %38 = OpBitwiseOr %uint %31 %37
+ %39 = OpBitwiseOr %uint %25 %38
+ %40 = OpBitwiseOr %uint %19 %39
+ %41 = OpBitwiseOr %uint %13 %40
+ %42 = OpIEqual %bool %33 %uint_0
+ %43 = OpSelect %uint %42 %uint_4294967295 %41
+ %result = OpBitcast %int %43
+)");
+}
+
+TEST_F(SpirvWriterTest, Builtin_FirstTrailingBit_Vec2U32) {
+ auto* arg = b.FunctionParam("arg", ty.vec2<u32>());
+ auto* func = b.Function("foo", ty.vec2<u32>());
+ func->SetParams({arg});
+ b.Append(func->Block(), [&] {
+ auto* result = b.Call(ty.vec2<u32>(), core::Function::kFirstTrailingBit, arg);
+ b.Return(func, result);
+ mod.SetName(result, "result");
+ });
+
+ ASSERT_TRUE(Generate()) << Error() << output_;
+ EXPECT_INST("%8 = OpConstantComposite %v2uint %uint_65535 %uint_65535");
+ EXPECT_INST("%11 = OpConstantComposite %v2uint %uint_0 %uint_0");
+ EXPECT_INST("%16 = OpConstantComposite %v2uint %uint_16 %uint_16");
+ EXPECT_INST("%20 = OpConstantComposite %v2uint %uint_255 %uint_255");
+ EXPECT_INST("%24 = OpConstantComposite %v2uint %uint_8 %uint_8");
+ EXPECT_INST("%28 = OpConstantComposite %v2uint %uint_15 %uint_15");
+ EXPECT_INST("%32 = OpConstantComposite %v2uint %uint_4 %uint_4");
+ EXPECT_INST("%36 = OpConstantComposite %v2uint %uint_3 %uint_3");
+ EXPECT_INST("%40 = OpConstantComposite %v2uint %uint_2 %uint_2");
+ EXPECT_INST("%44 = OpConstantComposite %v2uint %uint_1 %uint_1");
+ EXPECT_INST("%54 = OpConstantComposite %v2uint %uint_4294967295 %uint_4294967295");
+ EXPECT_INST(R"(
+ %7 = OpBitwiseAnd %v2uint %arg %8
+ %10 = OpIEqual %v2bool %7 %11
+ %15 = OpSelect %v2uint %10 %16 %11
+ %18 = OpShiftRightLogical %v2uint %arg %15
+ %19 = OpBitwiseAnd %v2uint %18 %20
+ %22 = OpIEqual %v2bool %19 %11
+ %23 = OpSelect %v2uint %22 %24 %11
+ %26 = OpShiftRightLogical %v2uint %18 %23
+ %27 = OpBitwiseAnd %v2uint %26 %28
+ %30 = OpIEqual %v2bool %27 %11
+ %31 = OpSelect %v2uint %30 %32 %11
+ %34 = OpShiftRightLogical %v2uint %26 %31
+ %35 = OpBitwiseAnd %v2uint %34 %36
+ %38 = OpIEqual %v2bool %35 %11
+ %39 = OpSelect %v2uint %38 %40 %11
+ %42 = OpShiftRightLogical %v2uint %34 %39
+ %43 = OpBitwiseAnd %v2uint %42 %44
+ %46 = OpIEqual %v2bool %43 %11
+ %47 = OpSelect %v2uint %46 %44 %11
+ %48 = OpBitwiseOr %v2uint %39 %47
+ %49 = OpBitwiseOr %v2uint %31 %48
+ %50 = OpBitwiseOr %v2uint %23 %49
+ %51 = OpBitwiseOr %v2uint %15 %50
+ %52 = OpIEqual %v2bool %42 %11
+ %result = OpSelect %v2uint %52 %54 %51
+)");
+}
+
TEST_F(SpirvWriterTest, Builtin_Saturate_F32) {
auto* arg = b.FunctionParam("arg", ty.f32());
auto* func = b.Function("foo", ty.f32());
diff --git a/src/tint/lang/spirv/writer/raise/raise.cc b/src/tint/lang/spirv/writer/raise/raise.cc
index 52ca457..ab7ff42 100644
--- a/src/tint/lang/spirv/writer/raise/raise.cc
+++ b/src/tint/lang/spirv/writer/raise/raise.cc
@@ -40,6 +40,8 @@
} while (false)
ir::transform::BuiltinPolyfillConfig core_polyfills;
+ core_polyfills.first_leading_bit = true;
+ core_polyfills.first_trailing_bit = true;
core_polyfills.saturate = true;
RUN_TRANSFORM(ir::transform::BuiltinPolyfill, module, core_polyfills);
