Bug 181535 – [DFG][FTL] Introduce PhantomNewRegexp and RegExpExecNonGlobalOrSticky

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Yusuke Suzuki]

Our goal is dropping unnecessary RegExp object creation when executing the code like `string.match(/regexp/)`.
To do so, we first start optimizing very simple case: if /regexp/ is neither global nor sticky, we do not need to touch RegExpObject.
Then, we can simply make it PhantomNewRegexp.

[Yusuke Suzuki]

(In reply to Yusuke Suzuki from comment #0)
> Our goal is dropping unnecessary RegExp object creation when executing the
> code like `string.match(/regexp/)`.
> To do so, we first start optimizing very simple case: if /regexp/ is neither
> global nor sticky, we do not need to touch RegExpObject.
> Then, we can simply make it PhantomNewRegexp.

We can extend it later for global case. But in this patch, we should focus on the simple case at first.

[Yusuke Suzuki]

Created attachment 331054 [details]
Patch

[EWS Watchlist]

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


ERROR: Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1962:  One line control clauses should not use braces.  [whitespace/braces] [4]
Total errors found: 1 in 28 files


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

[Yusuke Suzuki]

Created attachment 331181 [details]
Patch

[Yusuke Suzuki]

Created attachment 331187 [details]
Patch

[Yusuke Suzuki]

Created attachment 331318 [details]
Patch

[Yusuke Suzuki]

Ping?

[Saam Barati]

Comment on attachment 331318 [details]
Patch

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

Some initial feedback

> Source/JavaScriptCore/ChangeLog:15
> +        if we carefully model SetRegExpLastIndex and GetRegExpLastIndex in OAS phase.

These node names are wrong:
SetRegExpLastIndex => SetRegExpObjectLastIndex
etc

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1972
> +    case RegExpExecNonGlobalOrSticky:
> +        if (JSValue globalObjectValue = forNode(node->child1()).m_value) {
> +            if (JSGlobalObject* globalObject = jsDynamicCast<JSGlobalObject*>(m_vm, globalObjectValue)) {
> +                if (!globalObject->isHavingABadTime()) {
> +                    m_graph.watchpoints().addLazily(globalObject->havingABadTimeWatchpoint());
> +                    RegisteredStructureSet structureSet;
> +                    structureSet.add(m_graph.registerStructure(globalObject->regExpMatchesArrayStructure()));
> +                    structureSet.add(m_graph.registerStructure(globalObject->regExpMatchesArrayWithGroupsStructure()));
> +                    forNode(node).set(m_graph, structureSet);
> +                    forNode(node).merge(SpecOther);
> +                    break;
> +                }
> +            }
> +        }

This is duplicate code. It's probably worth factoring it out.

> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:1102
> +        case RegExpExecNonGlobalOrSticky: {
> +            fixEdge<KnownCellUse>(node->child1());
> +            fixEdge<KnownCellUse>(node->child2());
> +            break;
> +        }

How is this code reachable here? Seems like it should be moved to the area where we crash if we see it. We only convert to this node in strength reduction

> Source/JavaScriptCore/dfg/DFGNode.cpp:250
> +    children.child1() = Edge(children.child1().node(), KnownCellUse);
> +    children.child2() = Edge(children.child3().node(), KnownCellUse);

What's the old child2?

> Source/JavaScriptCore/dfg/DFGNode.h:659
> +        ASSERT(m_op == NewRegexp || m_op == MaterializeNewRegexp);

When will this ever actually be MaterializeNewRegexp. Seems wrong.

> Source/JavaScriptCore/dfg/DFGNode.h:661
> +        m_flags |= NodeMustGenerate;

why not default flags?

> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1555
> +            return m_graph.addNode(
> +                allocation.identifier()->prediction(), MaterializeNewRegexp,
> +                where->origin.withSemantic(
> +                    allocation.identifier()->origin.semantic),
> +                OpInfo(regExp));

Why have this node at all? Why not just materialize using this IR pattern:
```
a: NewRegExp
b: SetRegExpObjectLastIndex(@a, @index)
```
And perhaps have a variant of SetRegExpObjectLastIndex that asserts it can never exit via some OpInfo flag.

[Saam Barati]

Comment on attachment 331318 [details]
Patch

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

>> Source/JavaScriptCore/dfg/DFGNode.cpp:250
>> +    children.child2() = Edge(children.child3().node(), KnownCellUse);
> 
> What's the old child2?

No need to answer this. It's the old regex.

[Yusuke Suzuki]

Comment on attachment 331318 [details]
Patch

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

>> Source/JavaScriptCore/ChangeLog:15
>> +        if we carefully model SetRegExpLastIndex and GetRegExpLastIndex in OAS phase.
> 
> These node names are wrong:
> SetRegExpLastIndex => SetRegExpObjectLastIndex
> etc

Yeah, it's good time to rename this! Fixed.

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1972
>> +        }
> 
> This is duplicate code. It's probably worth factoring it out.

OK, fixed.

>> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:1102
>> +        }
> 
> How is this code reachable here? Seems like it should be moved to the area where we crash if we see it. We only convert to this node in strength reduction

Yeah, removed.

>> Source/JavaScriptCore/dfg/DFGNode.h:659
>> +        ASSERT(m_op == NewRegexp || m_op == MaterializeNewRegexp);
> 
> When will this ever actually be MaterializeNewRegexp. Seems wrong.

OK, removed.

>> Source/JavaScriptCore/dfg/DFGNode.h:661
>> +        m_flags |= NodeMustGenerate;
> 
> why not default flags?

Using default flags seems ok. Fixed.

>> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1555
>> +                OpInfo(regExp));
> 
> Why have this node at all? Why not just materialize using this IR pattern:
> ```
> a: NewRegExp
> b: SetRegExpObjectLastIndex(@a, @index)
> ```
> And perhaps have a variant of SetRegExpObjectLastIndex that asserts it can never exit via some OpInfo flag.

This is just for simplicity. Currently, createMaterialization assumes that materialization is done by one node producing the value.
I think we can do
```
a: NewRegExp
b: SetRegExpObjectLastIndex(@a, @index)
```
But I think `MaterializeNewRegExp` is very simple approach to do what we want.
MaterializeNewRegexp is aligned to MaterializeNewObject, MaterializeCreateActivation etc.

[Yusuke Suzuki]

Comment on attachment 331318 [details]
Patch

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

>>> Source/JavaScriptCore/ChangeLog:15
>>> +        if we carefully model SetRegExpLastIndex and GetRegExpLastIndex in OAS phase.
>> 
>> These node names are wrong:
>> SetRegExpLastIndex => SetRegExpObjectLastIndex
>> etc
> 
> Yeah, it's good time to rename this! Fixed.

Ah, no. It's typo. Fixed.

[Yusuke Suzuki]

Created attachment 331458 [details]
Patch

[Saam Barati]

Comment on attachment 331318 [details]
Patch

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

>>> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1555
>>> +                OpInfo(regExp));
>> 
>> Why have this node at all? Why not just materialize using this IR pattern:
>> ```
>> a: NewRegExp
>> b: SetRegExpObjectLastIndex(@a, @index)
>> ```
>> And perhaps have a variant of SetRegExpObjectLastIndex that asserts it can never exit via some OpInfo flag.
> 
> This is just for simplicity. Currently, createMaterialization assumes that materialization is done by one node producing the value.
> I think we can do
> ```
> a: NewRegExp
> b: SetRegExpObjectLastIndex(@a, @index)
> ```
> But I think `MaterializeNewRegExp` is very simple approach to do what we want.
> MaterializeNewRegexp is aligned to MaterializeNewObject, MaterializeCreateActivation etc.

I see. I agree your approach is simple. But I think it'd be even simpler just to reuse NewRegExp. Or at least come up with a way to share code in the FTL backend. You could even change NewRegexp to just take the last index as a child node. If you did that, you'd maintain the invariant that the allocating node is a single node. Or you can keep them separate, but try to share more of the code. Right now, there is a lot of duplication.

[Yusuke Suzuki]

Comment on attachment 331318 [details]
Patch

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

>>>> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1555
>>>> +                OpInfo(regExp));
>>> 
>>> Why have this node at all? Why not just materialize using this IR pattern:
>>> ```
>>> a: NewRegExp
>>> b: SetRegExpObjectLastIndex(@a, @index)
>>> ```
>>> And perhaps have a variant of SetRegExpObjectLastIndex that asserts it can never exit via some OpInfo flag.
>> 
>> This is just for simplicity. Currently, createMaterialization assumes that materialization is done by one node producing the value.
>> I think we can do
>> ```
>> a: NewRegExp
>> b: SetRegExpObjectLastIndex(@a, @index)
>> ```
>> But I think `MaterializeNewRegExp` is very simple approach to do what we want.
>> MaterializeNewRegexp is aligned to MaterializeNewObject, MaterializeCreateActivation etc.
> 
> I see. I agree your approach is simple. But I think it'd be even simpler just to reuse NewRegExp. Or at least come up with a way to share code in the FTL backend. You could even change NewRegexp to just take the last index as a child node. If you did that, you'd maintain the invariant that the allocating node is a single node. Or you can keep them separate, but try to share more of the code. Right now, there is a lot of duplication.

OK, so I think we can have one `NewRegexp(Untyped:lastIndex)`, which would be simpler :).

[Yusuke Suzuki]

Created attachment 331470 [details]
Patch

[EWS Watchlist]

Comment on attachment 331470 [details]
Patch

Attachment 331470 [details] did not pass ios-sim-ews (ios-simulator-wk2):
Output: http://webkit-queues.webkit.org/results/6103415

New failing tests:
http/tests/misc/resource-timing-resolution.html

[EWS Watchlist]

Created attachment 331473 [details]
Archive of layout-test-results from ews124 for ios-simulator-wk2

The attached test failures were seen while running run-webkit-tests on the ios-sim-ews.
Bot: ews124  Port: ios-simulator-wk2  Platform: Mac OS X 10.12.6

[Saam Barati]

Comment on attachment 331470 [details]
Patch

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

r=me

> Source/JavaScriptCore/ChangeLog:13
> +        phase. We should do this analysis in OAS phase since we would like to extend it further by tracking `lastIndex` modification

"we would like to extend it further by tracking ..." => "we track modifications to `lastIndex` in the OAS phase."

> Source/JavaScriptCore/ChangeLog:15
> +        if we carefully model SetRegExpObjectLastIndex and GetRegExpObjectLastIndex in OAS phase.

"if we" => "because we"

> Source/JavaScriptCore/ChangeLog:19
> +        non-global and non-sticky one. We can later extend this optimization for RegExp with global flag. But this is not included
> +        in this patch.

Is there a bug open for this? Is it worth doing?

> Source/JavaScriptCore/ChangeLog:37
> +        This patch does not change Octane/RegExp so much since it heavily uses String.prototype.replace, which is not handled in
> +        this patch right now. We should support StringReplace node in subsequent patches.

Any idea if this improves Web Tooling Bench? I know many of its tests heavily use RegExps.

> Source/JavaScriptCore/dfg/DFGOperations.cpp:1045
> +        scope.release();

Why scope.release() here? The below line isn't going to throw? Maybe:
ASSERT(!scope.exception())

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:10628
> +    GPRReg argumentGPR = argument.gpr();

This is inconsistent with what you do in the FTL. The FTL does lowString(). My vote would be for this node to have a StringUse for its second operand instead of KnownCellUse. AI will already prove this check isn't needed.

> JSTests/stress/materialize-regexp-at-osr-exit.js:1
> +function shouldBe(actual, expected)

You should add some tests where lastIndex and another object allocation form a cycle in various ways. And make sure things work if it gets escaped, does not get escaped, etc.

[Yusuke Suzuki]

Comment on attachment 331470 [details]
Patch

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

>> Source/JavaScriptCore/ChangeLog:13
>> +        phase. We should do this analysis in OAS phase since we would like to extend it further by tracking `lastIndex` modification
> 
> "we would like to extend it further by tracking ..." => "we track modifications to `lastIndex` in the OAS phase."

Fixed.

>> Source/JavaScriptCore/ChangeLog:15
>> +        if we carefully model SetRegExpObjectLastIndex and GetRegExpObjectLastIndex in OAS phase.
> 
> "if we" => "because we"

Fixed.

>> Source/JavaScriptCore/ChangeLog:19
>> +        in this patch.
> 
> Is there a bug open for this? Is it worth doing?

For `sticky` case, I don't think it is worth doing since `sticky` is inherently focusing on RegExp object.
But `global` case, we should do that since we may see the code like `string.match(/pattern/g)`.
Fortunately, extending this to `global` case is not so difficult I think.

>> Source/JavaScriptCore/ChangeLog:37
>> +        this patch right now. We should support StringReplace node in subsequent patches.
> 
> Any idea if this improves Web Tooling Bench? I know many of its tests heavily use RegExps.

Not looking into Web Tooling Bench yet. But it's worth doing. I believe that we have bunch of chance of optimization for RegExp right now, in terms of both Yarr runtime and RegExp handling in JSC.
This "removing unnecessary RegExp object allocation" is categorized into the latter one and I think we could exploit a chance to optimize Web Tooling Bench with such optimization. (I'll look into it!)
And I think we can optimize our Yarr further. E.g. introducing more sophisticated searching of fixed chars into Yarr. I remember that V8 IrregExp construct pattern to perform Boyer-Moore searching.
We could optimize Yarr by adopting SSE: Currently, our fixed char's matching utilizes 64bit reg to perform 8 char match at at time. But we can do further by using XMM regs.
And we could use SSE 4.2 string searching operations to further optimize Yarr.

And I also found that StringReplace DFG node always inserts several TryGetById and CheckCell nodes in DFG fixup phase. Since it is ad-hocly inserted in fixup phase, it is never converted to constant / nop.
So we need to always do several TryGetById ICs and CheckCell. While we emit these nodes in DFG, in FTL, we should have feedback information from ICs emitted and executed in DFG. So we should have a way to make them constant and watchpoints.

>> Source/JavaScriptCore/dfg/DFGOperations.cpp:1045
>> +        scope.release();
> 
> Why scope.release() here? The below line isn't going to throw? Maybe:
> ASSERT(!scope.exception())

OK, fixed.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:10628
>> +    GPRReg argumentGPR = argument.gpr();
> 
> This is inconsistent with what you do in the FTL. The FTL does lowString(). My vote would be for this node to have a StringUse for its second operand instead of KnownCellUse. AI will already prove this check isn't needed.

OK, changed.

>> JSTests/stress/materialize-regexp-at-osr-exit.js:1
>> +function shouldBe(actual, expected)
> 
> You should add some tests where lastIndex and another object allocation form a cycle in various ways. And make sure things work if it gets escaped, does not get escaped, etc.

OK, added.

[Yusuke Suzuki]

Created attachment 331487 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 331487 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGMayExit.cpp:128
> +    case SetRegExpObjectLastIndex:
> +        if (node->ignoreLastIndexIsWritable())
> +            break;
> +        return Exits;

Make `ignoreLastIndexIsWritable = true` case exitless.

> Source/JavaScriptCore/dfg/DFGNode.h:2692
> +    }

Added to make SetRegExpObjectLastIndex Exitless if ignoreLastIndexIsWritable is specified.

> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:2213
> +            if (m_sinkCandidates.contains(value))
> +                node->child1() = Edge(m_bottom);
> +            else
> +                node->child1() = Edge(value);

It would be possible that `lastIndex` one is also phantom (and later it is populated).

> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:2329
> +            break;

Add recovery case. We use OpInfo(1) for this to make this SetRegExpObjectLastIndex Exitless.

> Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h:122
> +        case RegExpObjectLastIndexPLoc:

Extend it for RegExpObjectLastIndexPLoc.

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:10425
> +    if (!node->ignoreLastIndexIsWritable()) {

Add this mode for recovery use.

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:10415
> +        if (!m_node->ignoreLastIndexIsWritable()) {

Ditto.

[EWS Watchlist]

Comment on attachment 331487 [details]
Patch

Attachment 331487 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.webkit.org/results/6107719

New failing tests:
imported/w3c/web-platform-tests/media-source/mediasource-config-change-mp4-a-bitrate.html

[EWS Watchlist]

Created attachment 331520 [details]
Archive of layout-test-results from ews103 for mac-sierra

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

[Saam Barati]

Comment on attachment 331487 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:4503
> +            set(VirtualRegister(currentInstruction[1].u.operand), addToGraph(NewRegexp, OpInfo(frozen), jsConstant(jsNumber(0))));

this needs to be reverted

[Saam Barati]

Comment on attachment 331487 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:2212
> +            if (m_sinkCandidates.contains(value))
> +                node->child1() = Edge(m_bottom);
> +            else

Why do any of this since you no longer need this as input to NewRegexp node

[Yusuke Suzuki]

Comment on attachment 331487 [details]
Patch

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

Thank you.

>> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:4503
>> +            set(VirtualRegister(currentInstruction[1].u.operand), addToGraph(NewRegexp, OpInfo(frozen), jsConstant(jsNumber(0))));
> 
> this needs to be reverted

This is necessary since this `NewRegexp` is used for materialization.

>> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:2212
>> +            else
> 
> Why do any of this since you no longer need this as input to NewRegexp node

createRecovery is used for `m_sinkCandidates.contains(value)` case. So if value is not a materialization target, we need to set it here, correct?

[Yusuke Suzuki]

Created attachment 331567 [details]
Patch

[Yusuke Suzuki]

Created attachment 331571 [details]
Patch

[Saam Barati]

Comment on attachment 331571 [details]
Patch

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

Nice!
r=me

> Source/JavaScriptCore/dfg/DFGNode.h:751
> +        m_opInfo = 0;

m_opInfo = false?

> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:2326
> +                OpInfo(1),

OpInfo(true)?

> Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp:717
> +                        OpInfo(0),

OpInfo(false)?

> Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp:854
> +                    OpInfo(0),

OpInfo(false)?

[Yusuke Suzuki]

Comment on attachment 331571 [details]
Patch

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

Thanks!

>> Source/JavaScriptCore/dfg/DFGNode.h:751
>> +        m_opInfo = 0;
> 
> m_opInfo = false?

Fixed.

>> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:2326
>> +                OpInfo(1),
> 
> OpInfo(true)?

Fixed.

>> Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp:717
>> +                        OpInfo(0),
> 
> OpInfo(false)?

Fixed.

>> Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp:854
>> +                    OpInfo(0),
> 
> OpInfo(false)?

Fixed.

[Yusuke Suzuki]

Committed r227107: <https://trac.webkit.org/changeset/227107>

[Radar WebKit Bug Importer]

<rdar://problem/36607504>

[Ryan Haddad]

stress/inserted-recovery-with-set-last-index.js is timing out on Debug JSC bots:

https://build.webkit.org/builders/Apple%20High%20Sierra%20Debug%20JSC%20%28Tests%29/builds/521

[Yusuke Suzuki]

(In reply to Ryan Haddad from comment #33)
> stress/inserted-recovery-with-set-last-index.js is timing out on Debug JSC
> bots:
> 
> https://build.webkit.org/builders/
> Apple%20High%20Sierra%20Debug%20JSC%20%28Tests%29/builds/521

Thanks, I'll reduce the count of the iteration to make it non-timing out in debug JSC.

[Yusuke Suzuki]

Committed r227196: <https://trac.webkit.org/changeset/227196>