Bug 192664

Summary: [BigInt] Add ValueBitLShift into DFG
Product: WebKit Reporter: Caio Lima <ticaiolima>
Component: JavaScriptCoreAssignee: Caio Lima <ticaiolima>
Status: RESOLVED FIXED    
Severity: Normal CC: cdumez, commit-queue, ews, keith_miller, mark.lam, msaboff, rniwa, sbarati, tzagallo, webkit-bug-importer, ysuzuki
Priority: P2 Keywords: InRadar
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on: 192966    
Bug Blocks: 186173    
Attachments:
Description Flags
WIP - Patch
none
Benchmarks
none
Patch
none
Benchmarks
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Benchmarks
none
Patch none

Description Caio Lima 2018-12-13 04:35:32 PST
...
Comment 1 Caio Lima 2018-12-30 07:41:33 PST
Created attachment 358148 [details]
WIP - Patch
Comment 2 Caio Lima 2018-12-30 07:44:00 PST
Created attachment 358149 [details]
Benchmarks

This change is perf neutral on x86_64 macOS build.
Comment 3 Yusuke Suzuki 2018-12-30 11:44:59 PST
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.
Comment 4 Caio Lima 2018-12-30 14:54:48 PST
(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.
Comment 5 Caio Lima 2019-01-16 09:30:18 PST
Created attachment 359271 [details]
Patch
Comment 6 Caio Lima 2019-01-16 09:32:32 PST
Created attachment 359272 [details]
Benchmarks

These changes seems to be perf neutral on macOS x86_ 64
Comment 7 Caio Lima 2019-01-19 06:17:28 PST
Created attachment 359605 [details]
Patch
Comment 8 Saam Barati 2019-01-20 14:46:58 PST
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.
Comment 9 Caio Lima 2019-01-23 17:34:00 PST
Created attachment 359976 [details]
Patch
Comment 10 Caio Lima 2019-01-24 06:34:10 PST
Created attachment 360009 [details]
Patch
Comment 11 Caio Lima 2019-02-01 18:05:30 PST
Created attachment 360941 [details]
Patch
Comment 12 Caio Lima 2019-02-17 15:02:32 PST
Created attachment 362256 [details]
Patch
Comment 13 Caio Lima 2019-03-17 18:52:48 PDT
Created attachment 364993 [details]
Patch
Comment 14 Caio Lima 2019-06-16 17:52:04 PDT
Created attachment 372229 [details]
Patch
Comment 15 Build Bot 2019-06-16 19:55:43 PDT
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
Comment 16 Caio Lima 2019-06-17 04:26:12 PDT
Created attachment 372240 [details]
Patch
Comment 17 Caio Lima 2019-06-25 11:09:19 PDT
Ping Review
Comment 18 Caio Lima 2019-06-27 12:43:42 PDT
Ping Review.
Comment 19 Keith Miller 2019-06-28 11:32:29 PDT
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?
Comment 20 Caio Lima 2019-06-28 13:15:15 PDT
(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.
Comment 21 Caio Lima 2019-07-02 13:54:24 PDT
Ping
Comment 22 Saam Barati 2019-07-09 09:51:25 PDT
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?
Comment 23 Caio Lima 2019-07-09 11:11:54 PDT
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.
Comment 24 Caio Lima 2019-07-09 12:14:51 PDT
Created attachment 373741 [details]
Patch
Comment 25 Caio Lima 2019-07-09 12:16:20 PDT
(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.
Comment 26 Saam Barati 2019-07-09 16:34:37 PDT
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())
Comment 27 Caio Lima 2019-07-10 09:28:17 PDT
Created attachment 373840 [details]
Patch
Comment 28 Caio Lima 2019-07-10 09:30:46 PDT
Created attachment 373841 [details]
Benchmarks

Benchmark results for the new version of the Patch. Perf looks neutral.
Comment 29 Caio Lima 2019-07-10 13:20:20 PDT
(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.
Comment 30 Saam Barati 2019-07-11 12:20:29 PDT
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
Comment 31 Caio Lima 2019-07-12 06:03:45 PDT
Created attachment 374006 [details]
Patch
Comment 32 WebKit Commit Bot 2019-07-12 07:47:43 PDT
Comment on attachment 374006 [details]
Patch

Clearing flags on attachment: 374006

Committed r247387: <https://trac.webkit.org/changeset/247387>
Comment 33 WebKit Commit Bot 2019-07-12 07:47:45 PDT
All reviewed patches have been landed.  Closing bug.
Comment 34 Radar WebKit Bug Importer 2019-07-12 07:48:27 PDT
<rdar://problem/53008172>
Comment 35 Caio Lima 2019-07-12 07:49:00 PDT
(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!