zig Add `@depositBits` and `@extractBits` builtins

This PR implements the @depositBits and @extractBits builtins, which correspond to the pdep and pext instructions in the x86 BMI2 extension (see #14995). On architectures where these instructions are unavailable, their behaviour is emulated, as it is for integers larger than their otherwise supported sizes.

This implementation functions correctly, to my observations. Each backend will need to implement an emulation for the two builtins, and optionally leverage dedicated instructions where available.

This is my first contribution to the compiler itself, so my code may well be non-idiomatic, or completely terrible just in general, so please be careful to fully analyse what my code is actually doing :) Particularly, my big.int probably needs plenty of critique and modification. Additionally, I'm not actually quite confident about my additions in Liveness.zig.

I'll rebase this code onto master and clean up my commits once it is ready to merge.

To-do

[ ] Look at tidying up and possibly optimising the bigint algorithms.
[ ] Use llvm.ppc.pdepd and pextd when available.
[ ] Consider how the available 64-bit pext/pdep instructions could be used to compute values for larger integers (u128, etc).
[x] Avoid mutating the mask in the bigint representation, so that we can avoid allocating a buffer and copying into it
[ ] Improve documentation
- [x] Allowed types
[x] Review general code quality, this is my first compiler contribution after all.
[ ] Implement in the other (non-LLVM) backends (could be done after this PR is merged).
[ ] Improve test coverage, testing against random numbers.
[x] Replace use of std.mem.set with @memset.

Closes #14995

Apr 14 '23 15:04 ominitay

zig fmt issue I think in llvm.zig:

2023-04-14T21:15:45.4950062Z + stage3-release/bin/zig fmt --check .. --exclude ../test/cases/ --exclude ../build-release
2023-04-14T21:15:45.4950642Z ../src/codegen/llvm.zig
2023-04-14T21:15:45.5071189Z ##[error]Process completed with exit code 1.

Apr 14 '23 21:04 matu3ba

Huh, suprised Emacs didn't automatically fix that.

Apr 14 '23 22:04 ominitay

New commit removes limbs_buffer requirement from big.int functions. It gets the job done, but I don't particularly like it. Would appreciate advice on cleaning that up.

Apr 17 '23 20:04 ominitay

After further thinking about how signed ints are handled, there is probably an accidental sign extension if passing a signed int parameter with fewer bits than the other parameter -- the signed int will coerce up, causing a sign-extension accidentally. Will test this later, add a behaviour test, and change the Sema code to effectively do an implicit bitcast to unsigned arguments before coercing them.

Apr 18 '23 09:04 ominitay

I see two choices here. The two builtins can do an implicit bitcast to get the semantics we want, or we can leave the bitcast to the caller. I personally think the conversion from signed -> unsigned should be handled by the builtins, as there's no intuitive reason why passing i64 for example shouldn't work.

Apr 18 '23 10:04 ominitay

Not sure why macos-debug tests failed there too.

Apr 18 '23 10:04 ominitay

Looks like linking libc and not linking libc for ReleaseFast are racing at writing the cache manifest against each other, as both fail with the very exact error message:

2023-04-18T08:30:11.3938460Z Install the project...
2023-04-18T08:30:11.4063650Z -- Install configuration: "Debug"
2023-04-18T08:57:06.4523620Z ++ pwd
2023-04-18T08:57:06.4799110Z + stage3/bin/zig build test docs --zig-lib-dir /Users/runner/work/zig/zig/build/../lib -Denable-macos-sdk -Dstatic-llvm -Dskip-non-native --search-prefix /Users/runner/zig+llvm+lld+clang-x86_64-macos-none-0.11.0-dev.2441+eb19f73af
2023-04-18T09:23:00.6724990Z zig test ReleaseFast native: error: thread 183881 panic: reached unreachable code
2023-04-18T09:23:00.6854820Z /Users/runner/work/zig/zig/lib/std/os.zig:962:23: 0x100e24071 in ftruncate (zig)
2023-04-18T09:23:00.6969080Z             .INVAL => unreachable, // Handle not open for writing
2023-04-18T09:23:00.7074050Z                       ^
2023-04-18T09:23:00.7194090Z /Users/runner/work/zig/zig/lib/std/fs/file.zig:254:30: 0x100c90736 in setEndPos (zig)
2023-04-18T09:23:00.7302450Z         try os.ftruncate(self.handle, length);
2023-04-18T09:23:00.7403820Z                              ^
2023-04-18T09:23:00.7916250Z /Users/runner/work/zig/zig/lib/std/Build/Cache.zig:870:55: 0x100c903c3 in writeManifest (zig)
2023-04-18T09:23:00.8029440Z             try manifest_file.setEndPos(contents.items.len);
2023-04-18T09:23:00.8029780Z                                                       ^
2023-04-18T09:23:00.8030070Z /Users/runner/work/zig/zig/src/Compilation.zig:2122:26: 0x100cff3d0 in update (zig)
2023-04-18T09:23:00.8030380Z         man.writeManifest() catch |err| {
2023-04-18T09:23:00.8030600Z                          ^
2023-04-18T09:23:00.8031030Z /Users/runner/work/zig/zig/src/main.zig:3384:36: 0x100d2f1c6 in serve (zig)
2023-04-18T09:23:00.8031350Z                     try comp.update(main_progress_node);
2023-04-18T09:23:00.8031600Z                                    ^
2023-04-18T09:23:00.8031880Z /Users/runner/work/zig/zig/src/main.zig:3202:31: 0x100b98d1e in buildOutputType (zig)
2023-04-18T09:23:00.8032790Z                 test_exec_args.items,
2023-04-18T09:23:00.8033040Z                               ^
2023-04-18T09:23:00.8038770Z /Users/runner/work/zig/zig/src/main.zig:273:31: 0x100b6b62f in mainArgs (zig)
2023-04-18T09:23:00.8039320Z         return buildOutputType(gpa, arena, args, .zig_test);
2023-04-18T09:23:00.8039580Z                               ^
2023-04-18T09:23:00.8039840Z /Users/runner/work/zig/zig/src/main.zig:211:20: 0x100b6a887 in main (zig)
2023-04-18T09:23:00.8060930Z     return mainArgs(gpa, arena, args);
2023-04-18T09:23:00.8061200Z                    ^
2023-04-18T09:23:00.8061470Z /Users/runner/work/zig/zig/lib/std/start.zig:609:37: 0x100b6d0b3 in main (zig)
2023-04-18T09:23:00.8061760Z             const result = root.main() catch |err| {
2023-04-18T09:23:00.8061990Z                                     ^
2023-04-18T09:23:00.8062190Z ???:?:?: 0x7fff203e7f3c in ??? (???)
2023-04-18T09:23:00.8062590Z ???:?:?: 0x12 in ??? (???)
2023-04-18T09:23:00.8062770Z 
2023-04-18T09:23:00.8062960Z zig test ReleaseFast native: error: the following command terminated unexpectedly:
2023-04-18T09:23:26.2318440Z /Users/runner/work/zig/zig/build/stage3/bin/zig test /Users/runner/work/zig/zig/test/behavior.zig -OReleaseFast --cache-dir /Users/runner/work/zig/zig/build/zig-local-cache --global-cache-dir /Users/runner/work/zig/zig/build/zig-global-cache --name test -I /Users/runner/work/zig/zig/test -L /Users/runner/zig+llvm+lld+clang-x86_64-macos-none-0.11.0-dev.2441+eb19f73af/lib -I /Users/runner/zig+llvm+lld+clang-x86_64-macos-none-0.11.0-dev.2441+eb19f73af/include --zig-lib-dir /Users/runner/work/zig/zig/lib --listen=- 
2023-04-18T09:23:26.2319480Z zig test ReleaseFast native: error: thread 183882 panic: reached unreachable code
2023-04-18T09:23:26.2424740Z /Users/runner/work/zig/zig/lib/std/os.zig:962:23: 0x107649071 in ftruncate (zig)
2023-04-18T09:23:26.2526060Z             .INVAL => unreachable, // Handle not open for writing
2023-04-18T09:23:26.2640040Z                       ^
2023-04-18T09:23:26.2743480Z /Users/runner/work/zig/zig/lib/std/fs/file.zig:254:30: 0x1074b5736 in setEndPos (zig)
2023-04-18T09:23:26.2852980Z         try os.ftruncate(self.handle, length);
2023-04-18T09:23:26.2964870Z                              ^
2023-04-18T09:23:26.3068300Z /Users/runner/work/zig/zig/lib/std/Build/Cache.zig:870:55: 0x1074b53c3 in writeManifest (zig)
2023-04-18T09:23:26.3177990Z             try manifest_file.setEndPos(contents.items.len);
2023-04-18T09:23:26.3279350Z                                                       ^
2023-04-18T09:23:26.3381060Z /Users/runner/work/zig/zig/src/Compilation.zig:2122:26: 0x1075243d0 in update (zig)
2023-04-18T09:23:26.3482580Z         man.writeManifest() catch |err| {
2023-04-18T09:23:26.3583880Z                          ^
2023-04-18T09:23:26.3685600Z /Users/runner/work/zig/zig/src/main.zig:3384:36: 0x1075541c6 in serve (zig)
2023-04-18T09:23:26.3787030Z                     try comp.update(main_progress_node);
2023-04-18T09:23:26.3889390Z                                    ^
2023-04-18T09:23:26.3990850Z /Users/runner/work/zig/zig/src/main.zig:3202:31: 0x1073bdd1e in buildOutputType (zig)
2023-04-18T09:23:26.4042130Z                 test_exec_args.items,
2023-04-18T09:23:26.4042810Z                               ^
2023-04-18T09:23:26.4043350Z /Users/runner/work/zig/zig/src/main.zig:273:31: 0x10739062f in mainArgs (zig)
2023-04-18T09:23:26.4043910Z         return buildOutputType(gpa, arena, args, .zig_test);
2023-04-18T09:23:26.4044370Z                               ^
2023-04-18T09:23:26.4044840Z /Users/runner/work/zig/zig/src/main.zig:211:20: 0x10738f887 in main (zig)
2023-04-18T09:23:26.4045340Z     return mainArgs(gpa, arena, args);
2023-04-18T09:23:26.4045760Z                    ^
2023-04-18T09:23:26.4046240Z /Users/runner/work/zig/zig/lib/std/start.zig:609:37: 0x1073920b3 in main (zig)
2023-04-18T09:23:26.4046760Z             const result = root.main() catch |err| {
2023-04-18T09:23:26.4047210Z                                     ^
2023-04-18T09:23:26.4047650Z ???:?:?: 0x7fff203e7f3c in ??? (???)
2023-04-18T09:23:26.4048070Z ???:?:?: 0x13 in ??? (???)
2023-04-18T09:23:26.4048390Z 
2023-04-18T09:23:26.4050030Z zig test ReleaseFast native: error: the following command terminated unexpectedly:
2023-04-18T09:23:26.4053880Z /Users/runner/work/zig/zig/build/stage3/bin/zig test /Users/runner/work/zig/zig/test/behavior.zig -lc -OReleaseFast --cache-dir /Users/runner/work/zig/zig/build/zig-local-cache --global-cache-dir /Users/runner/work/zig/zig/build/zig-global-cache --name test -I /Users/runner/work/zig/zig/test -L /Users/runner/zig+llvm+lld+clang-x86_64-macos-none-0.11.0-dev.2441+eb19f73af/lib -I /Users/runner/zig+llvm+lld+clang-x86_64-macos-none-0.11.0-dev.2441+eb19f73af/include --zig-lib-dir /Users/runner/work/zig/zig/lib --listen=-

This is weird, because the access at the same time should be handled by the file lock and also the comment above man.WriteManifest tells us // Failure here only means an unnecessary cache miss. and the first line in Cache.zig writeManifest(self: *Manifest) is also an assertion assert(self.have_exclusive_lock);.

More speculative, this looks like the cache manifest has not been written yet, so both processes try to create it and it never gets written in the first place, so both processes fail with INVAL. But this is just guessing without evidence.

I do see a few places, where this could be wrong, but further investigation is needed, ideally with some tracing:

1. logic to handle locking is incorrect
1. Memory synchronization is broken such that one thread has an invalid view on the return value of the locking state
1. Kernel bug, where internal data is not synchronized yet
1. msync is not included (in the correct order) such that memory is flushed into the Kernel before execution resumes (or the return value is ignored somehow leading to inconsistent state at the file descriptors that need special handling).
1. Some other process might write that very file after the 2 processes and succeeds causing these 2 processes to return INVAL.
1. No process succeeds writing the cache manifest and the cause for the error happened some time before.

Potentially related #14815 #14978.

Apr 18 '23 14:04 matu3ba

Decided to disallow using signed integers at all with these builtins. This simplifies the implementation greatly (makes me less likely to break things, and probably makes it faster), and just makes more sense; we're dealing with raw bits after all.

Apr 18 '23 17:04 ominitay

Looks like linking libc and not linking libc for ReleaseFast are racing at writing the cache manifest against each other, as both fail with the very exact error message:

fixed by #15351

Apr 18 '23 21:04 andrewrk

Forgot to enable the behaviour tests >_<

Apr 19 '23 10:04 ominitay

Starting to come back to this now. One possible thought is that the compiler itself currently doesn't actually utilise these builtins, when it could use them for a subset of types at comptime. Obviously not a priority, but could perhaps be worthwhile to consider in the future?

Jun 17 '23 18:06 ominitay

It looks like this PR never reached "ready for review & merge" status. It's now bitrotted, so if you wish to continue this effort, please open a new PR against master branch.

Oct 19 '23 01:10 andrewrk

Will do! Have had a lot of commitments irl, but I'll try to find the time in a month-ish.

Oct 19 '23 18:10 ominitay

No pressure. Happy to take a look when you decide it is ready :+1:

Oct 19 '23 18:10 andrewrk

zig zig copied to clipboard

Add `@depositBits` and `@extractBits` builtins

To-do

zig
zig copied to clipboard