sat-arithmetic: add operator support #9679

travisstaloch · 2021-09-02T20:57:36Z

implements accepted syntax from Saturating arithmetic #1284
adds initial support for the operators +|, -|, *|, <<|, +|=, -|=, *|=, <<|=
uses operators in addition to builtins in behavior test
adds binOpExt() and assignBinOpExt() to AstGen.zig. these need to be audited

travisstaloch · 2021-09-02T20:59:09Z

TODOS

audit AstGen.zig binOpExt() and assignBinOpExt()
update langref
c backend support
zig fmt support - currently deleting '|' from '<<|='
zls support

I'm not sure what needs to be done yet for 3, 4, and 5. Any advice appreciated.

andrewrk · 2021-09-07T19:48:01Z

Here's some advice to get you going-

c backend support

You can add any functions you need to src/link/C/zig.h, and then in codegen/c.zig you can emit calls to them. This part is pretty fun! I recommend to play with godbolt to test out your saturating arithmetic implementations and see how optimizable they are (the goal would be that most C compilers would be able to optimize them into machine code instructions when available).

zig fmt support - currently deleting '|' from '<<|='

Double check your edits to tokenizer.zig. Perhaps try adding some test cases at the bottom of tokenizer.zig (there are a few examples already there you can look at). Something to keep in mind is that tokenizer.zig and tokenizer.cpp are intentionally nearly identical implementations, so your edits to each file should look almost the same.

zls support

Not needed for this PR to be merged :)

travisstaloch · 2021-09-08T23:23:27Z

src/Sema.zig

+// TODO: audit - not sure if its a good idea to reuse this, adding `opt_extended` param
+// FIXME: somehow, rhs of <<| is required to be Log2T. this should accept T
 fn analyzeArithmetic(
    sema: *Sema,
    block: *Scope.Block,


I'm reusing analyzeArithmetic() by adding an opt_extended param here. Is this a bad idea?

Also, I can't figure out where the check that rhs of <<| is a Log2T happens (and how to disable it). It needs to accept T, but currently doesn't.

I would have expected this to be in zirShl, but I did not find it either. You should be able to disable this in stage1, which ensures one does not use too big types for shifting left. I may be wrong, but bigint_shl might be the function in stage1.

However this sounds to me inconsistent to the behavior of normal shift left and could hide a logical bug.
For prototyping using const/var shlcount = @intcast(Log2Int(@bitSizeOf(var1)), var2) (Log2Int is from math.zig) also does the job.

Why do you think requiring an @intcast for the left-shift is a bad idea?

Why do you think requiring an @intcast for the left-shift is a bad idea?

@matu3ba I was just trying to match the behavior of @shlWithSaturation which doesn't require Log2T, but accepts T.

also, this is how the llvm intrinsics are defined

travisstaloch · 2021-09-09T04:41:18Z

This part is pretty fun! I recommend to play with godbolt to test out your saturating arithmetic implementations and see how optimizable they are (the goal would be that most C compilers would be able to optimize them into machine code instructions when available).

I looked at them on godbolt with clang and gcc, both with -O1. They were all branchless using cmovs except for the gcc signed 64 bit operations have one jump instruction. I'm not super confident in the signed shl impl.

Double check your edits to tokenizer.zig. Perhaps try adding some test cases at the bottom of tokenizer.zig

This worked well. I was updating the result instead of the state when in the << transition.

Thank you for the guildance! Please let me know if you get a chance to look at this again. I've left some TODOs and FIXMEs.

matu3ba

Some tests ~~and simplification with using maxInt from math.zig~~.

Changing the behavior to allowing types on right hand side that are not Log2(left hand side) sounds to me inconsistent to the other << operations and (from my perspective) can hide logical bugs without crashing/overflowing in tests if one is not cautious.

lib/std/zig/tokenizer.zig

matu3ba · 2021-09-09T19:42:19Z

src/Sema.zig

+// TODO: audit - not sure if its a good idea to reuse this, adding `opt_extended` param
+// FIXME: somehow, rhs of <<| is required to be Log2T. this should accept T
 fn analyzeArithmetic(
    sema: *Sema,
    block: *Scope.Block,


I would have expected this to be in zirShl, but I did not find it either. You should be able to disable this in stage1, which ensures one does not use too big types for shifting left. I may be wrong, but bigint_shl might be the function in stage1.

However this sounds to me inconsistent to the behavior of normal shift left and could hide a logical bug.
For prototyping using const/var shlcount = @intcast(Log2Int(@bitSizeOf(var1)), var2) (Log2Int is from math.zig) also does the job.

Why do you think requiring an @intcast for the left-shift is a bad idea?

src/codegen/c.zig

travisstaloch · 2021-09-09T21:39:33Z

Changing the behavior to allowing types on right hand side that are not Log2(left hand side) sounds to me inconsistent to the other << operations and (from my perspective) can hide logical bugs without crashing/overflowing in tests if one is not cautious.

This is how @shlWithSaturation is defined:

Unlike other @shl builtins, shift_amt doesn't need to be a Log2T as saturated overshifting is well defined.

andrewrk

I have not fully looked at the review but I am about to go do something else so I wanted to give you something to work with in the meantime-

src/Sema.zig

src/AstGen.zig

test/behavior/saturating_arithmetic.zig

travisstaloch · 2021-09-15T07:08:42Z

CI failure

del : Cannot remove item D:\a\1\s\sfx.exe: The process cannot access the file 'D:\a\1\s\sfx.exe' because it is being used by another process.

I'm confident this was just a glitch. Last few commits have passed CI

- adds initial support for the operators +|, -|, *|, <<|, +|=, -|=, *|=, <<|= - uses operators in addition to builtins in behavior test - adds binOpExt() and assignBinOpExt() to AstGen.zig. these need to be audited

- modify AstGen binOpExt()/assignBinOpExt() to accept generic extended payload T - rework Sema zirSatArithmetic() to use existing sema.analyzeArithmetic() by adding an `opt_extended` parameter. - add airSatOp() to codegen/c.zig - add saturating functions to src/link/C/zig.h

- set state rather than result.tag in tokenizer.zig - add test to tokenizer.zig for <<, <<|, <<|=

- similar to Sema.analyzeArithmetic but uses accepts Zir.Inst.Extended.InstData - missing support for Pointer types and comptime arithmetic

- not necessary as we are testing the operators

* Remove the builtins `@addWithSaturation`, `@subWithSaturation`, `@mulWithSaturation`, and `@shlWithSaturation` now that we have first-class syntax for saturating arithmetic. * langref: Clarify the behavior of `@shlExact`. * Ast: rename `bit_shift_left` to `shl` and `bit_shift_right` to `shr` for consistency. * Air: rename to include underscore separator with consistency with the rest of the ops. * Air: add shl_exact instruction * Use non-extended tags for saturating arithmetic, to keep it simple so that all the arithmetic operations can be done the same way. - Sema: unify analyzeArithmetic with analyzeSatArithmetic - implement comptime `+|`, `-|`, and `*|` - allow float operands to saturating arithmetic * `<<|` allows any integer type for the RHS. * C backend: fix rebase conflicts * LLVM backend: reduce the amount of branching for arithmetic ops * zig.h: fix magic number not matching actual size of C integer types

travisstaloch force-pushed the sat-arith-operators branch from bf14b88 to 1659b97 Compare September 8, 2021 23:11

travisstaloch commented Sep 8, 2021

View reviewed changes

travisstaloch force-pushed the sat-arith-operators branch 2 times, most recently from ee220a8 to c98f767 Compare September 9, 2021 00:05

matu3ba reviewed Sep 9, 2021

View reviewed changes

travisstaloch force-pushed the sat-arith-operators branch 2 times, most recently from 4a8f2c5 to c7c5487 Compare September 11, 2021 03:33

andrewrk requested changes Sep 13, 2021

View reviewed changes

src/Sema.zig Outdated Show resolved Hide resolved

src/AstGen.zig Outdated Show resolved Hide resolved

test/behavior/saturating_arithmetic.zig Outdated Show resolved Hide resolved

travisstaloch requested a review from andrewrk September 15, 2021 02:00

travisstaloch force-pushed the sat-arith-operators branch 3 times, most recently from 1439d02 to 6785552 Compare September 28, 2021 20:07

travisstaloch added 13 commits September 28, 2021 17:02

sat-arithmetic: add operator support

29f4189

- adds initial support for the operators +|, -|, *|, <<|, +|=, -|=, *|=, <<|= - uses operators in addition to builtins in behavior test - adds binOpExt() and assignBinOpExt() to AstGen.zig. these need to be audited

sat-arithmetic: correctly tokenize <<|, <<|=

dcbc52e

- set state rather than result.tag in tokenizer.zig - add test to tokenizer.zig for <<, <<|, <<|=

sat-arithmetic: fixups zig fmt / astcheck

bdb90a0

sat-arithmetic: fix docgen

6ba9f74

sat-arithmetic: update langref

0f24625

sat-arithmetic: langref - remove syntax disclaimer

1d86eae

sat-arithmetic: add additional tokenizer tests

4870595

sat-arithmetic: langref - use <th> tags

fd83835

sat-arithmetic: minor formatting changes

6805085

sat-arithmetic: fix shl methods in cbe

cd8d8ad

sat-arithmetic: create Sema.analyzeSatArithmetic

baaec94

- similar to Sema.analyzeArithmetic but uses accepts Zir.Inst.Extended.InstData - missing support for Pointer types and comptime arithmetic

sat-arithmetic: don't test builtins in behavior tests

38703dc

- not necessary as we are testing the operators

travisstaloch and others added 4 commits September 28, 2021 17:04

get build passing again after rebase

51673bc

add missing zig fmt test for saturating arithmetic

6cb7906

AstGen: delete dead code

71da169

andrewrk force-pushed the sat-arith-operators branch from 9761f93 to 5467582 Compare September 29, 2021 02:20

andrewrk merged commit cf90cb7 into ziglang:master Sep 29, 2021

andrewrk mentioned this pull request Sep 29, 2021

Saturating arithmetic #1284

Closed

travisstaloch deleted the sat-arith-operators branch September 29, 2021 03:14

travisstaloch mentioned this pull request Sep 29, 2021

support new ast token changes and saturating operators zigtools/zls#399

Merged

gwenzek mentioned this pull request May 19, 2022

Upgrade to LLVM 14 #11274

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

sat-arithmetic: add operator support #9679

sat-arithmetic: add operator support #9679

travisstaloch commented Sep 2, 2021 •

edited

travisstaloch commented Sep 2, 2021 •

edited

andrewrk commented Sep 7, 2021

travisstaloch Sep 8, 2021 •

edited

matu3ba Sep 9, 2021 •

edited

travisstaloch Sep 9, 2021

travisstaloch Sep 9, 2021

travisstaloch commented Sep 9, 2021 •

edited

matu3ba left a comment •

edited

matu3ba Sep 9, 2021 •

edited

travisstaloch commented Sep 9, 2021

andrewrk left a comment

travisstaloch commented Sep 15, 2021

sat-arithmetic: add operator support #9679

sat-arithmetic: add operator support #9679

Conversation

travisstaloch commented Sep 2, 2021 • edited

travisstaloch commented Sep 2, 2021 • edited

andrewrk commented Sep 7, 2021

travisstaloch Sep 8, 2021 • edited

Choose a reason for hiding this comment

matu3ba Sep 9, 2021 • edited

Choose a reason for hiding this comment

travisstaloch Sep 9, 2021

Choose a reason for hiding this comment

travisstaloch Sep 9, 2021

Choose a reason for hiding this comment

travisstaloch commented Sep 9, 2021 • edited

matu3ba left a comment • edited

Choose a reason for hiding this comment

matu3ba Sep 9, 2021 • edited

Choose a reason for hiding this comment

travisstaloch commented Sep 9, 2021

andrewrk left a comment

Choose a reason for hiding this comment

travisstaloch commented Sep 15, 2021

travisstaloch commented Sep 2, 2021 •

edited

travisstaloch commented Sep 2, 2021 •

edited

travisstaloch Sep 8, 2021 •

edited

matu3ba Sep 9, 2021 •

edited

travisstaloch commented Sep 9, 2021 •

edited

matu3ba left a comment •

edited

matu3ba Sep 9, 2021 •

edited