Add shift operators, remove shiftLeft, shiftRight builtins by dneto0 · Pull Request #2989 · gpuweb/gpuweb

dneto0 · 2022-05-31T23:04:49Z

Part 1:

Revert "Remove shift tokens and add shift built-in functions (#2713)"
This reverts commit 48efd97.

Part 2:

Since the removal of shift operators, the shiftLeft and shiftRight
builtins added the ability to take operands that were AbstractInt
or vectors of AbstractInt.

We already have a rule that creation-time expressions must not
overflow. For shift-left, that can only be determined if both its
operands are abstract. So split the description of shift-left
into all-concrete operands, and all-abstract operands.

Additionally, spell out the overflow condition for the all-abstract
form of shift-left.

Fixes: #2092

Part 1: Revert "Remove shift tokens and add shift built-in functions (gpuweb#2713)" This reverts commit 48efd97. Part 2: Since the removal of shift operators, the shiftLeft and shiftRight builtins added the ability to take operands that were AbstractInt or vectors of AbstractInt. We already have a rule that creation-time expressions must not overflow. For shift-left, that can only be determined if both its operands are abstract. So split the description of shift-left into all-concrete operands, and all-abstract operands. Additionally, spell out the overflow condition for the all-abstract form of shift-left. Fixes: gpuweb#2092

dneto0 · 2022-05-31T23:08:06Z

This ended up being more exciting because of the interaction with AbstractInt.

This actually constrains both operands of left-shift to be concrete or both non-concrete. I think it was already problematic to have shiftLeft(AbstractInt, dynamic and concrete) because then the compiler can't tell if there will be overflow. So force the first operand to be concrete as well.

dneto0 · 2022-05-31T23:09:00Z

cc: @ben-clayton

dneto0 · 2022-05-31T23:11:37Z

FYI. The grammar analysis dump expands to this now:
wgsl.lalr.txt

It's still LALR(1).

github-actions · 2022-05-31T23:12:38Z

Previews, as seen when this build job started (dc56da9):
WebGPU | IDL
WGSL
Explainer

dj2 · 2022-06-01T13:41:23Z

+        [=Component-wise=] when |T| is a vector.
+
+        It is a [=shader-creation error=] if the calculation would overflow the AbstractInt type.
+        Overflow occurs when both 0 and 1 bits would be discarded,


Why does this specify 0 and 1 bits specifically? How can you shift off the 0 bit without shifting off the 1 bit?

Those are the values of the bits, not their position.
So, bits with value 0 and bits with value 1.

I'll clarify.

dj2 · 2022-06-01T13:43:23Z

+        It is a [=shader-creation error=] if the calculation would overflow the AbstractInt type.
+        Overflow occurs when both 0 and 1 bits would be discarded,
+        or when the most significant bit of |e1| would differ from the most
+        significant bit of the result.


I don't understand this restriction if I have bits 0100 and I << 1 I'll get 1000 and now the most significant bit of |e1| differs from the result. Is this overflow?

So the essence of the example is you have x = 1 << 62, or 0100 followed by 60 zeroes. So it's a 64bit number, which is the minimum required for AbstractInt.

If I compute (x << 1) then it's 1 followed by 63 zeroes. That 1 bit in the most significant position is the sign bit, because numbers are twos complement. So now the author expects ( x << 1 ) to have value 1 << 63. But (x << 1) is negative. So I call that overflow.

Overflow does not occur if and only if: all the discarded bits are the same value, and are the same as the resulting sign bit. That is, when shifting by y bits, overflow does not occur if the most-significant y+1 bits are the same.

I described the overflow case instead of the not-overflow case, and I wasn't certain which would read better.

Maybe would be easier to describe as a sign change or the size of e2 is too large (e.g. 64).

Chatted offline and saying the top e2+1 bits must be the same makes things a bit clearer. so 1100 << 1 is valid because the top 2 bits are 1 but << 2 would be invalid as the top 3 bits differ.

dj2 · 2022-06-01T13:46:44Z

+    |e2|: |TS|<br>
+    [ALLINTEGRALDECL]<br>
+    |TS| is vec|N|&lt;AbstractInt&gt; or vec|N|&lt;u32&gt; when |T| is vec|N|&lt;S&gt;,
+    otherwise |TS| is AbstractInt or u32


Can we write this like shift left?

|TS| is AbstractInt or u32 when |T| is |S|, otherwise |TS| is vec|N|&lt: AbstractInt> or vec|N|<u32>

Yes. I wondered if that was too much indirection. :-)

Oh, I remember: I did it this way to make sure that the same N value is used.

The N always has to be the same, it can't vary within a precondition (a lot of our builtins are written with that assumption I think)

I didn't want to leave that potential ambiguity.
But I can change it; I do agree it reads better to have the simpler expression first

dj2 · 2022-06-01T13:52:39Z

+
+        [=Component-wise=] when |T| is a vector.
+
+        It is a [=shader-creation error=] if the calculation would overflow the AbstractInt type.


By, if the calculation do you mean if the number of bits shifted is larger then the bit-width of an AbstractInt? If so, could we just say that e2 is modulo the bit-width of an abstract int?

We're trying to allow a future where AbstractInt has more than 64 bits. That's why we don't allow overflow.

So we don't want to have a calculation depend on "the" bit width of AbstractInt.

Are you implying that an abstract int, in the future, could have multiple bit widths? Otherwise there is aways a bit-width for an abstract int so saying the bit-width of abstract int should always be correct regardless if abstract int is int8_t, int64_t or int256_t, no?

You would only have one width of abstract int per translation unit.

So, imagine "abstractInt256" feature which updates only one sentence, to say basically

The AbstractInt type is the set of integers i, with -2255 ≤ i < 2255.

And nothing else. And any pre-existing shader that was valid before will still be valid with this feature, and it would mean the same thing as before.

I see, and a shader which previous did 1 << 65 and ended up doing a 1<<1 will now actually 1 << 65

dj2 · 2022-06-01T13:53:44Z

+        and discarding the least significant bits.
+
+        The number of bits to shift is the value of |e2|.
+        If |e1| has a [=concrete=] type, the shift value is modulo the bit width of |e1|.<br>


if e1 is abstract, do we modulo the bit-width of an abstract int? Otherwise, what if I do 1 >> 65?

No. We don't want to rely on AbstractInt having a specific bit width.

If you do 1 >> 65 then you get zero.
If you do 1 << 65 you get shader creation error.
If someone makes an extension where AbstractInt has 128 bits, then 1 << 64 can become meaningful, and strictly more programs become valid. But old programs that are valid still have the same meaning.

Right and the need to specify this for concrete numbers is because they could happen in the shader where it may modulo. But an abstract number happens compile time and we can make it 0.

dj2 · 2022-06-01T14:00:44Z

+    | [=syntax/shift_expression=]

-    | [=syntax/additive_expression=] [=syntax/greater_than=] [=syntax/additive_expression=]
+    | [=syntax/shift_expression=] [=syntax/less_than=] [=syntax/shift_expression=]


Why did the ordering of >, <=, etc change?

Artifact. I started with a plain revert of the previous removal.

dj2 · 2022-06-01T14:03:39Z

+<div class='syntax' noexport='true'>
+  <dfn for=syntax>shift_right</dfn> :
+
+    | `'>>'`


Missing codepoint?

dj2 · 2022-06-01T14:06:01Z

+<div class='syntax' noexport='true'>
+  <dfn for=syntax>shift_right_equal</dfn> :
+
+    | `'>>='` (Code points: `U+005E` `U+005E` `U+003D`)


This should be 003e not 005e

github-actions · 2022-06-01T17:33:09Z

Previews, as seen when this build job started (4ed102d):
WebGPU | IDL
WGSL
Explainer

github-actions · 2022-06-01T17:59:49Z

Previews, as seen when this build job started (c664ee1):
WebGPU | IDL
WGSL
Explainer

@dneto0

SHA: 5419dce Reason: push, by @dneto0 Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>

@dneto0

SHA: 5419dce Reason: push, by @dneto0 Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>

@dneto0

SHA: 5419dce Reason: push, by @dneto0 Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>

* Add shift operators, remove shiftLeft, shiftRight builtins Part 1: Revert "Remove shift tokens and add shift built-in functions (gpuweb#2713)" This reverts commit 48efd97. Part 2: Since the removal of shift operators, the shiftLeft and shiftRight builtins added the ability to take operands that were AbstractInt or vectors of AbstractInt. We already have a rule that creation-time expressions must not overflow. For shift-left, that can only be determined if both its operands are abstract. So split the description of shift-left into all-concrete operands, and all-abstract operands. Additionally, spell out the overflow condition for the all-abstract form of shift-left. Fixes: gpuweb#2092 * Apply review feedback * Split right-shift into concrete and abstract forms

dneto0 added wgsl WebGPU Shading Language Issues wgsl resolved Resolved - waiting for a change to the WGSL specification labels May 31, 2022

dneto0 added this to the V1.0 milestone May 31, 2022

dneto0 requested review from alan-baker, kdashg and litherum May 31, 2022 23:04

dj2 reviewed Jun 1, 2022

View reviewed changes

dneto0 mentioned this pull request Jun 1, 2022

wgsl: expression overloads, and builtin overloads must have all concrete operands or all abstract operands #2993

Closed

Apply review feedback

4ed102d

dj2 approved these changes Jun 1, 2022

View reviewed changes

Split right-shift into concrete and abstract forms

c664ee1

dneto0 requested a review from dj2 June 1, 2022 17:51

dj2 approved these changes Jun 1, 2022

View reviewed changes

dneto0 merged commit 5419dce into gpuweb:main Jun 1, 2022

dneto0 mentioned this pull request Jun 1, 2022

Reintroduce bitshift operators and remove builtins (revert #2713) #2986

Closed

github-actions Bot added a commit that referenced this pull request Jun 1, 2022

Add shift operators, remove shiftLeft, shiftRight builtins (#2989)

fdf883e

SHA: 5419dce Reason: push, by @dneto0 Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>

github-actions Bot added a commit that referenced this pull request Jun 1, 2022

Add shift operators, remove shiftLeft, shiftRight builtins (#2989)

0878d69

SHA: 5419dce Reason: push, by @dneto0 Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>

github-actions Bot added a commit that referenced this pull request Jun 1, 2022

Add shift operators, remove shiftLeft, shiftRight builtins (#2989)

721960c

SHA: 5419dce Reason: push, by @dneto0 Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>

dneto0 mentioned this pull request Sep 20, 2022

wgsl: somehow we lost arithmetic right shift #3461

Closed


		[=Component-wise=] when \|T\| is a vector.

		It is a [=shader-creation error=] if the calculation would overflow the AbstractInt type.

Conversation

dneto0 commented May 31, 2022

Uh oh!

dneto0 commented May 31, 2022

Uh oh!

dneto0 commented May 31, 2022

Uh oh!

dneto0 commented May 31, 2022

Uh oh!

github-actions Bot commented May 31, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

github-actions Bot commented Jun 1, 2022

Uh oh!

github-actions Bot commented Jun 1, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants