Bug 132319 – CSS JIT: optimize direct / indirect adjacent's traversal backtracking

• Component: CSS
• Status: RESOLVED FIXED

[Yusuke Suzuki]

Since adjacent backtracking stack reference is pre-allocated
in prologue in http://trac.webkit.org/changeset/166834,
clearing stack phase is not needed. So we can drop
JumpToClearAdjacentTail from backtracking action and simplify
backtracking handling.

[Yusuke Suzuki]

Created attachment 230353 [details]
Patch

rev1 patch

[Yusuke Suzuki]

Created attachment 230473 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 230473 [details]
Patch

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

Added comments to the patch.

> Source/WebCore/cssjit/SelectorCompiler.cpp:68
> +    JumpToDirectAdjacentTail

Drop JumpToClearAdjacentTail since there's no need to decrease stack height.

> Source/WebCore/cssjit/SelectorCompiler.cpp:613
> +        return BacktrackingAction::NoBacktracking;

When there's no descendant relation on the right, traversal failure becomes global failure.

> Source/WebCore/cssjit/SelectorCompiler.cpp:615
> +    if (fragment.tagNameMatchedBacktrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))

When `tagNameMatchedBacktrackingStartHeightFromDescendant` == `heightFromDescendant` + 1, the descendant backtracking starts with the parent of the current element. So we can use the current element and the backtracking action is JumpToDescendantTreeWalkerEntryPoint.

> Source/WebCore/cssjit/SelectorCompiler.cpp:618
> +    return BacktrackingAction::JumpToDescendantTail;

Otherwise, currently we take the conservative approach, JumpToDescendantTail.
We can optimize it more aggressively, but it will be done in the next patches.

> Source/WebCore/cssjit/SelectorCompiler.cpp:651
> +            fragment.matchingPostTagNameBacktrackingAction = fragment.traversalBacktrackingAction;

When `hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain` is false and `hasDescendantRelationOnTheRight` is true, we should backtrack with the closest descendant fragment. So we can take the same action as the traversal action.

> Source/WebCore/cssjit/SelectorCompiler.cpp:657
> +        fragment.traversalBacktrackingAction = solveTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);

In the indirect fragment, we can take the same traversal action in the direct fragment's traversal action.

[Yusuke Suzuki]

Comment on attachment 230473 [details]
Patch

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

Add aditional notes

>> Source/WebCore/cssjit/SelectorCompiler.cpp:615
>> +    if (fragment.tagNameMatchedBacktrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
> 
> When `tagNameMatchedBacktrackingStartHeightFromDescendant` == `heightFromDescendant` + 1, the descendant backtracking starts with the parent of the current element. So we can use the current element and the backtracking action is JumpToDescendantTreeWalkerEntryPoint.

NOTE:
If `hasDescendantRelationOnTheRight` is true and there's no child fragment on the right, the backtracking element register is not effective. So we should ensure that fragment doesn't use the backtracking element register.

Such a fragment fulfills the following conditions.
1. tagNameMatchedBacktrackingStartHeightFromDescendant is always 1 (tagNames.size(), that contains only descendant fragment)
2. heightFromDescendant is always 0
(-- See computeBacktrackingHeightFromDescendant implementation)

Therefore such a fragment's action always becomes JumpToDescendantTreeWalkerEntryPoint.
So we can ensure that the backtracking element register is not used.

[Benjamin Poulain]

Comment on attachment 230473 [details]
Patch

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

The patch looks great.

The comments you have added on bugzilla are very useful. You should put those explanation in the changelog too.

r- because I think the test needs to be extended. The patch looks correct to me otherwise.

> Source/WebCore/cssjit/SelectorCompiler.cpp:610
> +static inline BacktrackingAction solveTraversalBacktrackingAction(const SelectorFragment& fragment, bool hasDescendantRelationOnTheRight)

This is only for adjacent backtracking action, let's name this solveAdjacentTraversalBacktrackingAction() for clarity.

> LayoutTests/fast/selectors/backtracking-adjacent.html:6
> +/* default */

You can remove this comment.

> LayoutTests/fast/selectors/backtracking-adjacent.html:113
> +description('The backtracking direct adjacent combinator with descendant tail cases');

Hum, I am confused here, none of the cases tested needs a descendant tail.

I think what would make a good test here is cases of adjacent chain inside a descendant chain where a descendant tail would have been needed before your backtracking optimizations.

[Yusuke Suzuki]

Created attachment 230686 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 230473 [details]
Patch

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

I've uploaded the revised patch. And add comments on bugzilla to ChangeLog.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:610
>> +static inline BacktrackingAction solveTraversalBacktrackingAction(const SelectorFragment& fragment, bool hasDescendantRelationOnTheRight)
> 
> This is only for adjacent backtracking action, let's name this solveAdjacentTraversalBacktrackingAction() for clarity.

That's reasonable. I've renamed it.

>> LayoutTests/fast/selectors/backtracking-adjacent.html:113
>> +description('The backtracking direct adjacent combinator with descendant tail cases');
> 
> Hum, I am confused here, none of the cases tested needs a descendant tail.
> 
> I think what would make a good test here is cases of adjacent chain inside a descendant chain where a descendant tail would have been needed before your backtracking optimizations.

Right. I've changed this with 'The backtracking from adjacent combinators'.

And added test cases using backtracking tails.

[Yusuke Suzuki]

Created attachment 230693 [details]
Patch

[Benjamin Poulain]

Comment on attachment 230693 [details]
Patch

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

Great patch and great test!

I'll update the LayoutTest's ChangeLog and commit manually.

> LayoutTests/ChangeLog:10
> +        Since adjacent backtracking stack reference is pre-allocated
> +        in prologue in http://trac.webkit.org/changeset/166834,
> +        clearing stack phase is not needed. So we can drop

You don't need to repeat the text in this changelog. In the layout test changelog, you can add any comment you have on your tests.

[Benjamin Poulain]

Committed r168236: <http://trac.webkit.org/changeset/168236>

[Yusuke Suzuki]

Thank you!