| Issue |
76810
|
| Summary |
Basic checks against count-leading/trailing zeroes should be optimized
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
Validark
|
Here are some basic transformations applicable on architectures lacking fast clz/ctz instructions: [Godbolt link](https://zig.godbolt.org/z/re4bfMGnc)
```zig
const T = u64;
export fn isCountLeadingZeroesEven1(x: T) bool {
return 1 == @clz(x) & 1;
}
export fn isCountLeadingZeroesEven2(x: T) bool {
const odd_bits: @TypeOf(x) =
@bitCast(@as(@Vector(@divExact(@bitSizeOf(@TypeOf(x)), 8), u8), @splat(0xaa)));
return (x & ~odd_bits) > (x & odd_bits);
}
```
The previous code [[1](https://github.com/ziglang/zig/blob/9a56228c2b90d94d01bb76784c77fdec5710cf0a/lib/std/priority_dequeue.zig#L72), [2](https://github.com/google/guava/blob/3a86a13223b899b848a7f95556601d49d2faf426/guava/src/com/google/common/collect/MinMaxPriorityQueue.java#L502)] is actually useful for Atkinson et al.'s 1986 [Min-Max Heap](https://www.researchgate.net/profile/M-Atkinson/publication/220424085_Min-Max_Heaps_and_Generalized_Priority_Queues/links/00b49514bc2c945127000000/Min-Max-Heaps-and-Generalized-Priority-Queues.pdf) for telling whether a layer is a min layer or max layer. Here is an analogous transformation for count-trailing zeroes:
```zig
const T = u64;
export fn isCountTrailingZeroesEven1(x: u64) bool {
return 1 == @ctz(x) & 1;
}
export fn isCountTrailingZeroesEven2(x: u64) bool {
const odd_bits: @TypeOf(x) =
@bitCast(@as(@Vector(@divExact(@bitSizeOf(@TypeOf(x)), 8), u8), @splat(0xaa)));
return ((x & (~x +% 1)) & odd_bits) != 0;
}
```
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
