Bug 192664 – [BigInt] Add ValueBitLShift into DFG

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Caio Lima]

...

[Caio Lima]

Created attachment 358148 [details]
WIP - Patch

[Caio Lima]

Created attachment 358149 [details]
Benchmarks

This change is perf neutral on x86_64 macOS build.

[Yusuke Suzuki]

Comment on attachment 358148 [details]
WIP - Patch

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

quick review. The direction looks really nice. Please make the code consistent with the existing bit operations :)

> Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp:123
> +        case ValueBitLShift:

Is it correct? If it is correct, why aren't ValueBitOr and ValueBitXor included?

> Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp:223
> +        case ValueBitLShift:

Ditto.

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:3439
>          // We can use a BitLShift here because typed arrays will never have a byteLength

Change this to `ArithBitLShift`.

> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:220
> +            if (Node::shouldSpeculateUntypedForBitOps(node->child1().node(), node->child2().node())) {
> +                fixEdge<UntypedUse>(node->child1());
> +                fixEdge<UntypedUse>(node->child2());
> +                break;
> +            }
> +
> +            node->setOp(ArithBitLShift);
> +            node->clearFlags(NodeMustGenerate);
> +            node->setResult(NodeResultInt32);
> +            fixIntConvertingEdge(node->child1());
> +            fixIntConvertingEdge(node->child2());
> +            break;                     
> +        }

I'm not sure why this is separated from ValueBitXor, ValueBitOr and ValueBitAnd.
This checks shouldSpeculateUntypedForBitOps. But ValueBitXor, ValueBitOr and ValueBitAnd do not.

[Caio Lima]

(In reply to Yusuke Suzuki from comment #3)
> Comment on attachment 358148 [details]
> WIP - Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=358148&action=review
> 
> quick review. The direction looks really nice. Please make the code
> consistent with the existing bit operations :)

Thx for the review! This is the goal. I'm thinking in handle other BitOps into https://bugs.webkit.org/show_bug.cgi?id=192966

> > Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp:123
> > +        case ValueBitLShift:
> 
> Is it correct? If it is correct, why aren't ValueBitOr and ValueBitXor
> included?
> 
> > Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp:223
> > +        case ValueBitLShift:
> 
> Ditto.
> 
> > Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:3439
> >          // We can use a BitLShift here because typed arrays will never have a byteLength
> 
> Change this to `ArithBitLShift`.
> 
> > Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:220
> > +            if (Node::shouldSpeculateUntypedForBitOps(node->child1().node(), node->child2().node())) {
> > +                fixEdge<UntypedUse>(node->child1());
> > +                fixEdge<UntypedUse>(node->child2());
> > +                break;
> > +            }
> > +
> > +            node->setOp(ArithBitLShift);
> > +            node->clearFlags(NodeMustGenerate);
> > +            node->setResult(NodeResultInt32);
> > +            fixIntConvertingEdge(node->child1());
> > +            fixIntConvertingEdge(node->child2());
> > +            break;                     
> > +        }
> 
> I'm not sure why this is separated from ValueBitXor, ValueBitOr and
> ValueBitAnd.
> This checks shouldSpeculateUntypedForBitOps. But ValueBitXor, ValueBitOr and
> ValueBitAnd do not.
 Ditto.

[Caio Lima]

Created attachment 359271 [details]
Patch

[Caio Lima]

Created attachment 359272 [details]
Benchmarks

These changes seems to be perf neutral on macOS x86_ 64

[Caio Lima]

Created attachment 359605 [details]
Patch

[Saam Barati]

Comment on attachment 359605 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGDoesGC.cpp:103
> +    case ValueBitLShift:

same comment as I've written in other bugs. Should return true if BigIntUse.

[Caio Lima]

Created attachment 359976 [details]
Patch

[Caio Lima]

Created attachment 360009 [details]
Patch

[Caio Lima]

Created attachment 360941 [details]
Patch

[Caio Lima]

Created attachment 362256 [details]
Patch

[Caio Lima]

Created attachment 364993 [details]
Patch

[Caio Lima]

Created attachment 372229 [details]
Patch

[EWS Watchlist]

Comment on attachment 372229 [details]
Patch

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

New failing tests:
stress/urshift-int32-overflow.js.ftl-no-cjit-b3o0
stress/urshift-int32-overflow.js.bytecode-cache
stress/urshift-int32-overflow.js.ftl-no-cjit-small-pool
stress/urshift-int32-overflow.js.ftl-no-cjit-no-put-stack-validate
stress/urshift-int32-overflow.js.ftl-eager-no-cjit-b3o1
stress/urshift-int32-overflow.js.ftl-no-cjit-validate-sampling-profiler
stress/urshift-int32-overflow.js.ftl-eager
stress/urshift-int32-overflow.js.ftl-eager-no-cjit
stress/urshift-int32-overflow.js.ftl-no-cjit-no-inline-validate
stress/urshift-int32-overflow.js.default
apiTests

[Caio Lima]

Created attachment 372240 [details]
Patch

[Caio Lima]

Ping Review

[Caio Lima]

Ping Review.

[Keith Miller]

Comment on attachment 372240 [details]
Patch

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

> Source/JavaScriptCore/ChangeLog:15
> +        not using `getHeapPrediction()` during prediction propagation, because
> +        it causes performance regression on Octane's zlib and mandreel.

Why does this cause a regression?

[Caio Lima]

(In reply to Keith Miller from comment #19)
> Comment on attachment 372240 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=372240&action=review
> 
> > Source/JavaScriptCore/ChangeLog:15
> > +        not using `getHeapPrediction()` during prediction propagation, because
> > +        it causes performance regression on Octane's zlib and mandreel.
> 
> Why does this cause a regression?

The problem is when we use getPrediction() to populate “getHeapTopPrediction()” and the instruction was never executed before, we emit a ForceOSRExit. It means that the program will have more OSRExits than desired. Such case seems to be very common for those benchmarks. Another option would be to use getPredictionWithoutOSR(), but in this case we will have Untyped as the prediction for instructions never executed. This means that we will stop the prediction propagation for those instructions and will emit ValueBitLShift in cases where it would totally possible to speculate Int32 or other types. IIRC, the best approach is then use the instruction inputs to propagate the predictions.

[Caio Lima]

Ping

[Saam Barati]

Comment on attachment 372240 [details]
Patch

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

> Source/JavaScriptCore/bytecode/BytecodeList.rb:263
> +        :lshift,

Where are you actually using the value profile?

> Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:182
> +        case ValueBitLShift: {

Did you mean to make this just use the value profile?

> Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:190
> +                else if (isFullNumberOrBooleanSpeculationExpectingDefined(left) && isFullNumberOrBooleanSpeculationExpectingDefined(right))
> +                    changed |= mergePrediction(SpecInt32Only);

shouldn't this just be something like:
if ((!left & SpecBigInt) && !(right & SpecBigInt))

Since this will always return int32 unless the input might be BigInt? Or maybe ValueOf allows you to return BigInt and therefore I'm wrong?

[Caio Lima]

Thx a lot for the feedback.

(In reply to Saam Barati from comment #22)
> Comment on attachment 372240 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=372240&action=review
> 
> > Source/JavaScriptCore/bytecode/BytecodeList.rb:263
> > +        :lshift,
> 
> Where are you actually using the value profile?

IIRC, the idea of keeping ValueProfile on this instruction was to get predictions injected during PredictionInjectionPhase and potentially making `PredictionPropagationPhase` converge in less iterations. However, I think the predictions are never injected for those nodes. Even though, leaving this profiler there don't make much sense anymore and I think we should remove it.

> > Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:182
> > +        case ValueBitLShift: {
> 
> Did you mean to make this just use the value profile?

Since this version gave up on using getHeapTopPrediction(), I don't think we need to have ValueProfile anymore.
 
> > Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:190
> > +                else if (isFullNumberOrBooleanSpeculationExpectingDefined(left) && isFullNumberOrBooleanSpeculationExpectingDefined(right))
> > +                    changed |= mergePrediction(SpecInt32Only);
> 
> shouldn't this just be something like:
> if ((!left & SpecBigInt) && !(right & SpecBigInt))
> 
> Since this will always return int32 unless the input might be BigInt? Or
> maybe ValueOf allows you to return BigInt and therefore I'm wrong?

Yes, `valueOf` can return BigInt and, as you mentioned, `if ((!left & SpecBigInt) && !(right & SpecBigInt))` don't catch those cases.

[Caio Lima]

Created attachment 373741 [details]
Patch

[Caio Lima]

(In reply to Caio Lima from comment #24)
> Created attachment 373741 [details]
> Patch

In this Patch I removed the ValueProfile of ValueBitLShift and also added a test case to cover when BigInt can be a return of a `valueOf` method.

[Saam Barati]

Comment on attachment 373741 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:192
> +                else
> +                    changed |= mergePrediction(SpecBigInt | SpecInt32Only);

btw, this is where the value profile would help you out. You could make this mergePrediction(getHeapPrediction())

[Caio Lima]

Created attachment 373840 [details]
Patch

[Caio Lima]

Created attachment 373841 [details]
Benchmarks

Benchmark results for the new version of the Patch. Perf looks neutral.

[Caio Lima]

(In reply to Saam Barati from comment #26)
> Comment on attachment 373741 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=373741&action=review
> 
> > Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:192
> > +                else
> > +                    changed |= mergePrediction(SpecBigInt | SpecInt32Only);
> 
> btw, this is where the value profile would help you out. You could make this
> mergePrediction(getHeapPrediction())

Thx a lot for this advice! I uploaded a new version using this idea and there is no performance regression on last report.

[Saam Barati]

Comment on attachment 373840 [details]
Patch

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

> Source/JavaScriptCore/ChangeLog:14
> +        not using `getHeapPrediction()` during prediction propagation, because

not true anymore

[Caio Lima]

Created attachment 374006 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 374006 [details]
Patch

Clearing flags on attachment: 374006

Committed r247387: <https://trac.webkit.org/changeset/247387>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/53008172>

[Caio Lima]

(In reply to Saam Barati from comment #30)
> Comment on attachment 373840 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=373840&action=review
> 
> > Source/JavaScriptCore/ChangeLog:14
> > +        not using `getHeapPrediction()` during prediction propagation, because
> 
> not true anymore

Thx a lot for the reviews!