Bug 182216 – [ESNext][BigInt] Implement "~" unary operation

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Caio Lima]

...

[Caio Lima]

*** Bug 190798 has been marked as a duplicate of this bug. ***

[Caio Lima]

Created attachment 356382 [details]
WIP - Patch

[Caitlin Potter (:caitp)]

Comment on attachment 356382 [details]
WIP - Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=356382&action=review

I've given this a quick look --- I don't feel too good reviewing DFG/FTL stuff as it's been a while and I don't have it fresh in my mind, so the style nit is all I got there.

The runtime looks good and matches the v8 implementation --- unfortunately I'm not super familiar with the spec and will have a hard time vetting the tests, maybe Robin could take a look at those?

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:387
> +        if (node->op() == ValueBitNot) {

do we really need to fall through ValueBitNot into this? the amount of shared code is pretty small

[EWS Watchlist]

Comment on attachment 356382 [details]
WIP - Patch

Attachment 356382 [details] did not pass jsc-ews (mac):
Output: https://webkit-queues.webkit.org/results/10250201

New failing tests:
exceptionFuzz.yaml/exceptionFuzz/earley-boyer.js.exception-fuzz
apiTests

[Caio Lima]

Created attachment 356489 [details]
WIP - Patch

[EWS Watchlist]

Comment on attachment 356489 [details]
WIP - Patch

Attachment 356489 [details] did not pass mac-ews (mac):
Output: https://webkit-queues.webkit.org/results/10264412

Number of test failures exceeded the failure limit.

[EWS Watchlist]

Created attachment 356498 [details]
Archive of layout-test-results from ews101 for mac-sierra

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews101  Port: mac-sierra  Platform: Mac OS X 10.12.6

[Caio Lima]

Created attachment 357224 [details]
Patch

[Caio Lima]

Created attachment 357227 [details]
Patch

[Saam Barati]

Comment on attachment 357227 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=357227&action=review

Mostly LGTM, but I’m worried about how you lower to ArithBitNot vs ValueBitNot

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:383
> +            setConstant(node, JSValue(~a));

I think you need a didFoldClobber here

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:4929
> +            if (isInt32Speculation(getPrediction()))

This reasoning is wrong. You’re saying you’ll produce an ArithBitNot if you produce an int32, but you’ll always produce an Int32 I believe if you’re not a big int. This logic should consider the operands, not the result. I think this kind of logic is best done in Fixup. If you kept this code this way, I believe you’re introducing an OSR exit loop every time you have some object type as an input

> Source/JavaScriptCore/dfg/DFGOperations.cpp:368
> +        RETURN_IF_EXCEPTION(scope, encodedJSValue());

No need for this extra branch. I think you can just RELEASE_AND_RETURN the above operation

[Caio Lima]

Thank you for the review.

(In reply to Saam Barati from comment #10)
> Comment on attachment 357227 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=357227&action=review
> 
> Mostly LGTM, but I’m worried about how you lower to ArithBitNot vs
> ValueBitNot
> 
> > Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:383
> > +            setConstant(node, JSValue(~a));
> 
> I think you need a didFoldClobber here
> 
> > Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:4929
> > +            if (isInt32Speculation(getPrediction()))
> 
> This reasoning is wrong. You’re saying you’ll produce an ArithBitNot if you
> produce an int32, but you’ll always produce an Int32 I believe if you’re not
> a big int. This logic should consider the operands, not the result. I think
> this kind of logic is best done in Fixup. If you kept this code this way, I
> believe you’re introducing an OSR exit loop every time you have some object
> type as an input

Maybe I'm missing some edge case here, but I don't understand why such situation would be possible. Isn't this the same situation as the test `JSTests/stress/bitwise-not-fixup-rules.js` is stressing?
Even when we emit ArithBitNot we are fixing this for ValueBitNot into fixup phase when operand should be Untyped. BTW, this is the same approach we are following in all other bitwise operations.

> > Source/JavaScriptCore/dfg/DFGOperations.cpp:368
> > +        RETURN_IF_EXCEPTION(scope, encodedJSValue());
> 
> No need for this extra branch. I think you can just RELEASE_AND_RETURN the
> above operation

[Saam Barati]

(In reply to Caio Lima from comment #11)
> Thank you for the review.
> 
> (In reply to Saam Barati from comment #10)
> > Comment on attachment 357227 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=357227&action=review
> > 
> > Mostly LGTM, but I’m worried about how you lower to ArithBitNot vs
> > ValueBitNot
> > 
> > > Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:383
> > > +            setConstant(node, JSValue(~a));
> > 
> > I think you need a didFoldClobber here
> > 
> > > Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:4929
> > > +            if (isInt32Speculation(getPrediction()))
> > 
> > This reasoning is wrong. You’re saying you’ll produce an ArithBitNot if you
> > produce an int32, but you’ll always produce an Int32 I believe if you’re not
> > a big int. This logic should consider the operands, not the result. I think
> > this kind of logic is best done in Fixup. If you kept this code this way, I
> > believe you’re introducing an OSR exit loop every time you have some object
> > type as an input
> 
> Maybe I'm missing some edge case here, but I don't understand why such
> situation would be possible. Isn't this the same situation as the test
> `JSTests/stress/bitwise-not-fixup-rules.js` is stressing?
> Even when we emit ArithBitNot we are fixing this for ValueBitNot into fixup
> phase when operand should be Untyped. BTW, this is the same approach we are
> following in all other bitwise operations.
You’re correct. I missed the code in Fixup that does this. I guess it’s weird to first start with ArithBitNot and then move to ValueBitNot. This probably doesn’t have an effect in practice, but it’s subtly wrong if we ever move some analyses before Fixup. As a general rule of thumb, you can change a node from performing effects to not performing effects. However, taking a node that doesn’t perform effects and converting it to a node that does effects is wrong. It may not matter this early in the compiler pipeline, but I think we should follow this rule. E.g, we use clobberize rules in BytecodeParser to report if it’s valid to exit at a subsequent node.

We should start by lowering to ValueBitNot, then in if possible, in Fixup convert to ArithBitNot and clear the must generate flags
> 
> > > Source/JavaScriptCore/dfg/DFGOperations.cpp:368
> > > +        RETURN_IF_EXCEPTION(scope, encodedJSValue());
> > 
> > No need for this extra branch. I think you can just RELEASE_AND_RETURN the
> > above operation

[Caio Lima]

(In reply to Saam Barati from comment #12)
> You’re correct. I missed the code in Fixup that does this. I guess it’s
> weird to first start with ArithBitNot and then move to ValueBitNot. This
> probably doesn’t have an effect in practice, but it’s subtly wrong if we
> ever move some analyses before Fixup. As a general rule of thumb, you can
> change a node from performing effects to not performing effects. However,
> taking a node that doesn’t perform effects and converting it to a node that
> does effects is wrong. It may not matter this early in the compiler
> pipeline, but I think we should follow this rule. E.g, we use clobberize
> rules in BytecodeParser to report if it’s valid to exit at a subsequent node.

After your comment I started to think about it and agree that this reasoning is wrong. I decided to fix other Nodes into https://bugs.webkit.org/show_bug.cgi?id=192966.

[Caio Lima]

Created attachment 358064 [details]
Patch

[EWS Watchlist]

Attachment 358064 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:286:  When wrapping a line, only indent 4 spaces.  [whitespace/indent] [3]
Total errors found: 1 in 29 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Robin Templeton]

Comment on attachment 358064 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=358064&action=review

looks good for the parts i can review, some small issues and nits below

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:398
> +    case ArithBitNot: {;

nit: extra semicolon

> Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:292
> +            

nit: trailing whitespace

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:2891
> +            

nit: trailing whitespace

> Source/JavaScriptCore/runtime/JSBigInt.cpp:540
> +    return result->rightTrim(vm);

this should check for errors from absoluteSubOne/absoluteAddOne before trimming (also both of those functions appear to trim their results, so calling rightTrim may not be strictly necessary here)

> JSTests/stress/big-int-bitwise-not-wrapped-value.js:21
> +testBitNot(o, -2n, "ToPrimitive: @@toPrimitive");

this could also check that toPrimitive/valueOf/toString are prioritized correctly by defining the unused methods and throwing errors from them: valueOf and toString in this test, and toString in the next one

test262 checks for this in https://github.com/tc39/test262/blob/master/test/language/expressions/bitwise-not/bigint-non-primitive.js

> JSTests/stress/bitwise-not-fixup-rules.js:1
> +//@ runBigIntEnabled

might need '//@ skip if not $jitTests' -- numberOfDFGCompiles will return a large number if the jit is not enabled

[Caio Lima]

Created attachment 359198 [details]
Patch

[Caio Lima]

Created attachment 359235 [details]
Benchmarks

This patch seems perf neutral when running on macOS x86_64.

[Caio Lima]

Created attachment 359236 [details]
Patch

[Saam Barati]

Comment on attachment 359236 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=359236&action=review

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:383
> +            didFoldClobberWorld();

I think you only want to call this if you're UntypedUse.

> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:242
> +            if (operandEdge.node()->shouldSpeculateBigInt())
> +                fixEdge<BigIntUse>(operandEdge);

I think you can clear mustGenerate here too, right? This isn't observable IIRC

[Robin Templeton]

Comment on attachment 359236 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=359236&action=review

tests and runtime code lgtm

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:4938
> +                set(bytecode.dst, addToGraph(ArithBitNot, op1));

nit: bytecode.dst -> bytecode.m_dst in master (from bug 193467?)

> Source/JavaScriptCore/runtime/CommonSlowPaths.cpp:725
> +    auto operandNumeric = GET_C(bytecode.operand).jsValue().toBigIntOrInt32(exec);

and bytecode.operand -> bytecode.m_operand

[Caio Lima]

Created attachment 359885 [details]
Patch

[Caio Lima]

Created attachment 359890 [details]
Benchmarks

It seems perf neutral.

[EWS Watchlist]

Comment on attachment 359885 [details]
Patch

Attachment 359885 [details] did not pass mac-wk2-ews (mac-wk2):
Output: https://webkit-queues.webkit.org/results/10859239

New failing tests:
imported/w3c/web-platform-tests/css/css-grid/abspos/orthogonal-positioned-grid-descendants-013.html

[EWS Watchlist]

Created attachment 359898 [details]
Archive of layout-test-results from ews104 for mac-highsierra-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews104  Port: mac-highsierra-wk2  Platform: Mac OS X 10.13.6

[Caio Lima]

Created attachment 360006 [details]
Patch

[Caio Lima]

Created attachment 360007 [details]
Benchmarks

Changes are perf neutral

[Caio Lima]

Ping review.

[Caio Lima]

Created attachment 360931 [details]
Patch

[Caio Lima]

Pong Review

[Caio Lima]

Created attachment 362250 [details]
Patch

[Caio Lima]

Created attachment 363089 [details]
Patch

[Caio Lima]

Ping review

[Caio Lima]

Ping Review

[Keith Miller]

Comment on attachment 363089 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=363089&action=review

r=me with some comments.

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:384
> +            if (node->child1().useKind() == UntypedUse)
> +                didFoldClobberWorld();

Why do you need this check? It doesn't seem like you should need it because even if Fixup thinks this should have been a BigInt, AI has proven it's an int32.

> Source/JavaScriptCore/dfg/DFGOperations.cpp:216
> +template<typename BigIntOperation, typename Int32Operation>
> +static ALWAYS_INLINE EncodedJSValue bitwiseBinaryOp(ExecState* exec, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2, BigIntOperation&& bigIntOp, Int32Operation&& int32Op, const char* errorMessage)

Nice!

> JSTests/stress/big-int-bit-not-general.js:4
> +// Copyright (C) 2017 Josh Wolfe. All rights reserved.
> +// This code is governed by the BSD license found in the LICENSE file.

Does this file exist? If not please paste the contents of the original BSD license here.

[Caio Lima]

Comment on attachment 363089 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=363089&action=review

Thx a lot for the review!

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:384
>> +                didFoldClobberWorld();
> 
> Why do you need this check? It doesn't seem like you should need it because even if Fixup thinks this should have been a BigInt, AI has proven it's an int32.

I agree with you. I can't think in a case where it is reproducible, but  we are getting the useKind of `node->child1()` and it can be anything. AFICT, there is no way this happen, but to be robust against future changes, instead of removing the condition, I added an ASSERT(node->child1().useKind() == UntypedUse).

>> JSTests/stress/big-int-bit-not-general.js:4
>> +// This code is governed by the BSD license found in the LICENSE file.
> 
> Does this file exist? If not please paste the contents of the original BSD license here.

Done.

[Caio Lima]

Created attachment 363878 [details]
Patch

[Keith Miller]

(In reply to Caio Lima from comment #36)
> Comment on attachment 363089 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=363089&action=review
> 
> Thx a lot for the review!
> 
> >> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:384
> >> +                didFoldClobberWorld();
> > 
> > Why do you need this check? It doesn't seem like you should need it because even if Fixup thinks this should have been a BigInt, AI has proven it's an int32.
> 
> I agree with you. I can't think in a case where it is reproducible, but  we
> are getting the useKind of `node->child1()` and it can be anything. AFICT,
> there is no way this happen, but to be robust against future changes,
> instead of removing the condition, I added an
> ASSERT(node->child1().useKind() == UntypedUse).

That’s definitely not a valid assertion. Prediction the value profile coming into the not can say anything it wants. This includes intentionally lying, which we sometimes do for testing. It’s basically a guess. Thus, it’s perfectly valid for Fixup to decide to check for a JSBigInt. However AI will only say a value is an int32 if it’s 100% true. So it’s completely possible for us to have a JSBigInt use kind and have AI prove it’s an int32.

> 
> >> JSTests/stress/big-int-bit-not-general.js:4
> >> +// This code is governed by the BSD license found in the LICENSE file.
> > 
> > Does this file exist? If not please paste the contents of the original BSD license here.
> 
> Done.

[Keith Miller]

(In reply to Keith Miller from comment #38)
> (In reply to Caio Lima from comment #36)
> > Comment on attachment 363089 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=363089&action=review
> > 
> > Thx a lot for the review!
> > 
> > >> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:384
> > >> +                didFoldClobberWorld();
> > > 
> > > Why do you need this check? It doesn't seem like you should need it because even if Fixup thinks this should have been a BigInt, AI has proven it's an int32.
> > 
> > I agree with you. I can't think in a case where it is reproducible, but  we
> > are getting the useKind of `node->child1()` and it can be anything. AFICT,
> > there is no way this happen, but to be robust against future changes,
> > instead of removing the condition, I added an
> > ASSERT(node->child1().useKind() == UntypedUse).
> 
> That’s definitely not a valid assertion. Prediction the value profile coming
> into the not can say anything it wants. This includes intentionally lying,
> which we sometimes do for testing. It’s basically a guess. Thus, it’s
> perfectly valid for Fixup to decide to check for a JSBigInt. However AI will
> only say a value is an int32 if it’s 100% true. So it’s completely possible
> for us to have a JSBigInt use kind and have AI prove it’s an int32.
> 

Can you please remove that assertion?

> > 
> > >> JSTests/stress/big-int-bit-not-general.js:4
> > >> +// This code is governed by the BSD license found in the LICENSE file.
> > > 
> > > Does this file exist? If not please paste the contents of the original BSD license here.
> > 
> > Done.

[Caio Lima]

(In reply to Keith Miller from comment #39)
> (In reply to Keith Miller from comment #38)
> > 
> > That’s definitely not a valid assertion. Prediction the value profile coming
> > into the not can say anything it wants. This includes intentionally lying,
> > which we sometimes do for testing. It’s basically a guess. Thus, it’s
> > perfectly valid for Fixup to decide to check for a JSBigInt. However AI will
> > only say a value is an int32 if it’s 100% true. So it’s completely possible
> > for us to have a JSBigInt use kind and have AI prove it’s an int32.
> > 
> 
> Can you please remove that assertion?

Sure. Sorry for the delay on reply, but I was thinking in a way to add a test for this case before upload the patch. My major confusion here is because I'm asserting on ```node->child1.useKind``` and this is definitely not guaranteed. When AI executes ```ValueBitNot``` edges and its UseKind is ```BigIntUse``` means that AI can't prove it is a Int32 anymore, which makes sense. So the following code wouldn't propagate a constant:

...
1: @ArithOp(Int32)
2: @ValueBit(Check:BigInt:@1)
3: @return(Check:Untyped:@2)
...

So, in the case of ValueBitNot, only ```UntypedUse``` is possible to allow AI prove it is Int32 ant that's why we don't need the check/assertion. Did I get it right?

The problem of getting a test case for this is because Fixup will change ValueBitNot by ArithBitNot when its operand is AnyInt or Number.

[Caio Lima]

Created attachment 364004 [details]
Patch

[Caio Lima]

(In reply to Caio Lima from comment #40) 
> Sure. Sorry for the delay on reply, but I was thinking in a way to add a
> test for this case before upload the patch. My major confusion here is
> because I'm asserting on ```node->child1.useKind``` and this is definitely
> not guaranteed. When AI executes ```ValueBitNot``` edges and its UseKind is
> ```BigIntUse``` means that AI can't prove it is a Int32 anymore, which makes
> sense. So the following code wouldn't propagate a constant:
> 
> ...
> 1: @ArithOp(Int32)
> 2: @ValueBit(Check:BigInt:@1)
> 3: @return(Check:Untyped:@2)
> ...
> 
> So, in the case of ValueBitNot, only ```UntypedUse``` is possible to allow
> AI prove it is Int32 ant that's why we don't need the check/assertion. Did I
> get it right?
> 
> The problem of getting a test case for this is because Fixup will change
> ValueBitNot by ArithBitNot when its operand is AnyInt or Number.

I get it now. `didFoldClobberWorld` needs to align with clobberize rules, and as I explained before, BigIntUse on ValueBitNot won't allow AI proves an Int32 constant. The assertion is indeed not needed and is wrong because it is not related with child's use kind. I think we are good to commit current Patch, right?

[Keith Miller]

(In reply to Caio Lima from comment #42)
> (In reply to Caio Lima from comment #40) 
> > Sure. Sorry for the delay on reply, but I was thinking in a way to add a
> > test for this case before upload the patch. My major confusion here is
> > because I'm asserting on ```node->child1.useKind``` and this is definitely
> > not guaranteed. When AI executes ```ValueBitNot``` edges and its UseKind is
> > ```BigIntUse``` means that AI can't prove it is a Int32 anymore, which makes
> > sense. So the following code wouldn't propagate a constant:
> > 
> > ...
> > 1: @ArithOp(Int32)
> > 2: @ValueBit(Check:BigInt:@1)
> > 3: @return(Check:Untyped:@2)
> > ...
> > 
> > So, in the case of ValueBitNot, only ```UntypedUse``` is possible to allow
> > AI prove it is Int32 ant that's why we don't need the check/assertion. Did I
> > get it right?
> > 
> > The problem of getting a test case for this is because Fixup will change
> > ValueBitNot by ArithBitNot when its operand is AnyInt or Number.
> 
> I get it now. `didFoldClobberWorld` needs to align with clobberize rules,
> and as I explained before, BigIntUse on ValueBitNot won't allow AI proves an
> Int32 constant. The assertion is indeed not needed and is wrong because it
> is not related with child's use kind. I think we are good to commit current
> Patch, right?

Whoops, thought I commented before... I was actually wrong and the original patch was fine. As you said, there's no way for AI to prove int32 with BitIntUse because it will reach a contradiction. I'm OK with either version of this patch.

[Caio Lima]

Thx again for the review!

[WebKit Commit Bot]

Comment on attachment 364004 [details]
Patch

Clearing flags on attachment: 364004

Committed r242715: <https://trac.webkit.org/changeset/242715>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/48771508>