Skip to content

V
V8
Switch branch/tag
  1. 08 Aug, 2019 1 commit
  3. 31 Jul, 2019 1 commit
    • Seth Brenith's avatar
      Reland "[regexp] Better quick checks on loop entry nodes" · bea0ffd0
      Seth Brenith authored 
      This is a reland of 4b15b984

Updates since original: fix an arithmetic overflow bug, remove an invalid
DCHECK, add a unit test that would trigger that DCHECK.

Original change's description:
> [regexp] Better quick checks on loop entry nodes
>
> Like the predecessor change https://crrev.com/c/v8/v8/+/1702125 , this
> change is inspired by attempting to exit earlier from generated RegExp
> code, when no further matches are possible because any match would be
> too long. The motivating example this time is the following expression,
> which tests whether a string of Unicode playing cards has five of the
> same suit in a row:
>
> /([🂡-🂮]{5})|([🂱-🂾]{5})|([🃁-🃎]{5})|([🃑-🃞]{5})/u
>
> A human reading this expression can readily see that any match requires
> at least 10 characters (5 surrogate pairs), but the LoopChoiceNode for
> each repeated option reports its minimum distance to the end of a match
> as zero. This is correct, because the LoopChoiceNode's behavior depends
> on additional state (the loop counter). However, the preceding node, a
> SET_REGISTER action that initializes the loop counter, could confidently
> state that it consumes at least 10 characters. Furthermore, when we try
> to emit a quick check for that action, we could follow only paths from
> the LoopChoiceNode that are possible based on the minimum iteration
> count. This change implements both of those "could"s.
>
> I expect this improvement to apply pretty broadly to expressions that
> use minimum repetition counts and that don't meet the criteria for
> unrolling. In this particular case, I get about 12% improvement on the
> overall UniPoker test, due to reducing the execution time of this
> expression by 85% and the execution time of another similar expression
> that checks for n-of-a-kind by 20%.
>
> Bug: v8:9305
>
> Change-Id: I319e381743967bdf83324be75bae943fbb5dd496
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1704941
> Commit-Queue: Seth Brenith <seth.brenith@microsoft.com>
> Reviewed-by: Jakob Gruber <jgruber@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#62963}

Bug: v8:9305
Change-Id: I992070d383009013881bf778242254c27134b650
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1726674Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
Commit-Queue: Seth Brenith <seth.brenith@microsoft.com>
Cr-Commit-Position: refs/heads/master@{#63009}
      bea0ffd0
  5. 30 Jul, 2019 1 commit
    • Leszek Swirski's avatar
      Revert "[regexp] Better quick checks on loop entry nodes" · 51afbd1a
      Leszek Swirski authored 
      This reverts commit 4b15b984.

Reason for revert: UBSan failure (https://logs.chromium.org/logs/v8/buildbucket/cr-buildbucket.appspot.com/8906578530303352544/+/steps/Check/0/logs/regress-126412/0).

Original change's description:
> [regexp] Better quick checks on loop entry nodes
> 
> Like the predecessor change https://crrev.com/c/v8/v8/+/1702125 , this
> change is inspired by attempting to exit earlier from generated RegExp
> code, when no further matches are possible because any match would be
> too long. The motivating example this time is the following expression,
> which tests whether a string of Unicode playing cards has five of the
> same suit in a row:
> 
> /([🂡-🂮]{5})|([🂱-🂾]{5})|([🃁-🃎]{5})|([🃑-🃞]{5})/u
> 
> A human reading this expression can readily see that any match requires
> at least 10 characters (5 surrogate pairs), but the LoopChoiceNode for
> each repeated option reports its minimum distance to the end of a match
> as zero. This is correct, because the LoopChoiceNode's behavior depends
> on additional state (the loop counter). However, the preceding node, a
> SET_REGISTER action that initializes the loop counter, could confidently
> state that it consumes at least 10 characters. Furthermore, when we try
> to emit a quick check for that action, we could follow only paths from
> the LoopChoiceNode that are possible based on the minimum iteration
> count. This change implements both of those "could"s.
> 
> I expect this improvement to apply pretty broadly to expressions that
> use minimum repetition counts and that don't meet the criteria for
> unrolling. In this particular case, I get about 12% improvement on the
> overall UniPoker test, due to reducing the execution time of this
> expression by 85% and the execution time of another similar expression
> that checks for n-of-a-kind by 20%.
> 
> Bug: v8:9305
> 
> Change-Id: I319e381743967bdf83324be75bae943fbb5dd496
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1704941
> Commit-Queue: Seth Brenith <seth.brenith@microsoft.com>
> Reviewed-by: Jakob Gruber <jgruber@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#62963}

TBR=jgruber@chromium.org,seth.brenith@microsoft.com

Change-Id: Iac085b75e054fdf0d218987cfe449be1f1630545
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: v8:9305
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1725621Reviewed-by: 's avatarLeszek Swirski <leszeks@chromium.org>
Commit-Queue: Leszek Swirski <leszeks@chromium.org>
Cr-Commit-Position: refs/heads/master@{#62977}
      51afbd1a
  7. 29 Jul, 2019 2 commits
    • Seth Brenith's avatar
      [regexp] Better quick checks on loop entry nodes · 4b15b984
      Seth Brenith authored 
      Like the predecessor change https://crrev.com/c/v8/v8/+/1702125 , this
change is inspired by attempting to exit earlier from generated RegExp
code, when no further matches are possible because any match would be
too long. The motivating example this time is the following expression,
which tests whether a string of Unicode playing cards has five of the
same suit in a row:

/([🂡-🂮]{5})|([🂱-🂾]{5})|([🃁-🃎]{5})|([🃑-🃞]{5})/u

A human reading this expression can readily see that any match requires
at least 10 characters (5 surrogate pairs), but the LoopChoiceNode for
each repeated option reports its minimum distance to the end of a match
as zero. This is correct, because the LoopChoiceNode's behavior depends
on additional state (the loop counter). However, the preceding node, a
SET_REGISTER action that initializes the loop counter, could confidently
state that it consumes at least 10 characters. Furthermore, when we try
to emit a quick check for that action, we could follow only paths from
the LoopChoiceNode that are possible based on the minimum iteration
count. This change implements both of those "could"s.

I expect this improvement to apply pretty broadly to expressions that
use minimum repetition counts and that don't meet the criteria for
unrolling. In this particular case, I get about 12% improvement on the
overall UniPoker test, due to reducing the execution time of this
expression by 85% and the execution time of another similar expression
that checks for n-of-a-kind by 20%.

Bug: v8:9305

Change-Id: I319e381743967bdf83324be75bae943fbb5dd496
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1704941
Commit-Queue: Seth Brenith <seth.brenith@microsoft.com>
Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#62963}
      4b15b984
    • Jakob Gruber's avatar
      [regexp] Restructure fast path check logic · c6b1ef0e
      Jakob Gruber authored 
      Prior to this CL, the regexp fast path check is stricter than it
needs to be. For example, adding any arbitrary property on the regexp
prototype would move the execution of all regexp builtins in the same
context onto the slow path. This actually happens in the real world:
popular web frameworks commonly monkey-patch builtin prototypes to add
functionality.

The intent of this CL is to widen the fast path for regexp builtins s.t.
modifications of the prototype that do not conflict with our
requirements stay on the fast path.

This is done by extending the current fast path check with an
additional step. If checking the prototype map identity or
relevant prototype property constness fails, we now compare the actual
value of all relevant properties against the expected value. If these
match, the prototype can be considered fast.

The new step as described in the previous paragraph is part of the
permissive fast path check (BranchIfFastRegExp_Permissive). The strict
variant (BranchIfFastRegExp_Strict) is also still required by a few
spots. We should refactor these to also allow the permissive check in
follow-up work.

Bug: v8:5577,chromium:977382
Change-Id: I69b2244e68ccfbd00edf17fc326aa4b5f5d089fa
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1706056
Commit-Queue: Jakob Gruber <jgruber@chromium.org>
Reviewed-by: 's avatarClemens Hammacher <clemensh@chromium.org>
Reviewed-by: 's avatarBenedikt Meurer <bmeurer@chromium.org>
Reviewed-by: 's avatarPeter Marshall <petermarshall@chromium.org>
Cr-Commit-Position: refs/heads/master@{#62948}
      c6b1ef0e
  9. 26 Jul, 2019 1 commit
  11. 25 Jul, 2019 1 commit
    • Seth Brenith's avatar
      [regexp] Use stricter bounds check to avoid additional iteration · f42b1a5d
      Seth Brenith authored 
      The motivating example is JetStream 2's UniPoker test, which tests
whether a sorted string of Unicode playing cards contains a five-card
straight using a regular expression. In the top-level generated loop for
this RegExp, we see this loop exit condition:

00000350000C2067    27  83fffe         cmpl rdi,0xfe
00000350000C206A    2a  0f8da8e40000   jge 00000350000D0518  <+0xe4d8>

Meaning if the current position is pointing at the very last (16-bit)
character, then we exit the loop. Otherwise we go on and try to find
various matches starting at the current position. However, we can see
in the original expression that any possible match is at least 10
characters (5 astral-plane Unicode values), so we're wasting a lot of
time attempting to find matches in cases where we're too close to the
end of the string for any match to succeed.

This example might be a bit contrived, but I expect that an improvement
in this bounds check would help a larger family of regular expressions,
where the minimum match length is large relative to the string being
matched and we don't meet the other necessary criteria for fast Boyer-
Moore lookahead.

To get the desired bounds check in this case, this patch does the
following:
1. Compute accurate EatsAtLeast values for every node during the
   analysis phase. This could end up doing more work than the current
   implementation, but analysis already has to touch every node, so it
   seems like a cache-friendly time to compute these values. In some
   cases, this might be less total work than the current implementation,
   because the current implementation might recompute the same node
   multiple times.
2. When emitting a quick check, use the EatsAtLeast value from the
   predecessor ChoiceNode for the bounds check.

This improves the UniPoker score on my machine by about 4%, because it
cuts the time spent checking for straights roughly in half, and checking
for straights originally accounted for about 8% of the total time.

Bug: v8:9305
Change-Id: I110b190c2578f73b2263259d5aa5750e921b01be
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1702125
Commit-Queue: Seth Brenith <seth.brenith@microsoft.com>
Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#62919}
      f42b1a5d
  13. 24 Jul, 2019 1 commit
  15. 19 Jul, 2019 1 commit
    • Sathya Gunasekaran's avatar
      Revert "Reland "[regexp] Call the regexp interpreter without CEntry overhead"" · aa478cac
      Sathya Gunasekaran authored 
      This reverts commit c2ee4a79.

Reason for revert: webgl_conformance_tests deqp/data/gles2/shaders/conversions.html crashes on Android FYI Release (Nexus 9)
See https://bugs.chromium.org/p/chromium/issues/detail?id=985624

Original change's description:
> Reland "[regexp] Call the regexp interpreter without CEntry overhead"
>
> This is a reland of d4d28b73
>
> Original change's description:
> > [regexp] Call the regexp interpreter without CEntry overhead
> >
> > Previously all RegExp calls went through Runtime_RegExpExec when --regexp-interpret-all was set.
> >
> > This CL avoids the runtime overhead by calling into the interpreter directly from the RegExpExec Builtin when the regular expression subject was already compiled to ByteCode (i.e. after the first call).
> >
> > Bug: v8:8954
> > Change-Id: Iae9dfcef3370b772a05b2942305335d592f6f15a
> > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1698391
> > Commit-Queue: Patrick Thier <pthier@google.com>
> > Reviewed-by: Jakob Gruber <jgruber@chromium.org>
> > Reviewed-by: Peter Marshall <petermarshall@chromium.org>
> > Cr-Commit-Position: refs/heads/master@{#62753}
>
> Bug: v8:8954
> Change-Id: I1f0b6de9c6da65bcb582ddb41a37419116a5c510
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1706053
> Reviewed-by: Jakob Gruber <jgruber@chromium.org>
> Commit-Queue: Patrick Thier <pthier@google.com>
> Cr-Commit-Position: refs/heads/master@{#62794}

TBR=jgruber@chromium.org,petermarshall@chromium.org,pthier@google.com

# Not skipping CQ checks because original CL landed > 1 day ago.

Bug: v8:8954, chromium:985624
Change-Id: I5bc2c397a09979f42f28670f80a5366f2a33d80f
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1709411
Commit-Queue: Sathya Gunasekaran <gsathya@chromium.org>
Reviewed-by: 's avatarSathya Gunasekaran <gsathya@chromium.org>
Cr-Commit-Position: refs/heads/master@{#62824}
      aa478cac
  17. 18 Jul, 2019 1 commit
    • Patrick Thier's avatar
      Reland "[regexp] Call the regexp interpreter without CEntry overhead" · c2ee4a79
      Patrick Thier authored 
      This is a reland of d4d28b73

Original change's description:
> [regexp] Call the regexp interpreter without CEntry overhead
> 
> Previously all RegExp calls went through Runtime_RegExpExec when --regexp-interpret-all was set.
> 
> This CL avoids the runtime overhead by calling into the interpreter directly from the RegExpExec Builtin when the regular expression subject was already compiled to ByteCode (i.e. after the first call).
> 
> Bug: v8:8954
> Change-Id: Iae9dfcef3370b772a05b2942305335d592f6f15a
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1698391
> Commit-Queue: Patrick Thier <pthier@google.com>
> Reviewed-by: Jakob Gruber <jgruber@chromium.org>
> Reviewed-by: Peter Marshall <petermarshall@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#62753}

Bug: v8:8954
Change-Id: I1f0b6de9c6da65bcb582ddb41a37419116a5c510
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1706053Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
Commit-Queue: Patrick Thier <pthier@google.com>
Cr-Commit-Position: refs/heads/master@{#62794}
      c2ee4a79
  19. 17 Jul, 2019 2 commits
  21. 11 Jul, 2019 2 commits
  23. 10 Jul, 2019 1 commit
  25. 09 Jul, 2019 1 commit
  27. 03 Jul, 2019 1 commit
  29. 02 Jul, 2019 1 commit
  31. 01 Jul, 2019 3 commits
    • Maya Lekova's avatar
      Revert "Speed up CharacterRange::AddCaseEquivalents" · 569e5d23
      Maya Lekova authored 
      This reverts commit f23f644f.

Reason for revert: Breaks arm debug builder - https://ci.chromium.org/p/v8/builders/ci/V8%20Arm%20-%20debug%20builder/22390 - missing file?

Original change's description:
> Speed up CharacterRange::AddCaseEquivalents
> 
> By using the lexCss("color:") to measure the performance
> The change make the lexCss("color:")
>   x21 - x40 times faster than trunk.
>   x2.3 - x4.6 times faster than m74.
> 
> Design Doc: http://shorturl.at/adfO5
> 
> Measured by out/x64.release/d8 reg977003.js
> see reg977003.js attached to chromium:977003
> 
> Also see another cl of benchmark in
> https://chromium-review.googlesource.com/c/v8/v8/+/1679651/
> 
> 
> Bug: chromium:977003
> Change-Id: Ie8518493d2c33df1594be1b4576bda715087b421
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1674851
> Commit-Queue: Frank Tang <ftang@chromium.org>
> Reviewed-by: Yang Guo <yangguo@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#62471}

TBR=adamk@chromium.org,jkummerow@chromium.org,yangguo@chromium.org,jshin@chromium.org,gsathya@chromium.org,ftang@chromium.org

Change-Id: I780fac2cf5f4bae6846f8d5c8765cabd76637545
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: chromium:977003
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1684073Reviewed-by: 's avatarMaya Lekova <mslekova@chromium.org>
Commit-Queue: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#62472}
      569e5d23
    • Frank Tang's avatar
      Speed up CharacterRange::AddCaseEquivalents · f23f644f
      Frank Tang authored 
      By using the lexCss("color:") to measure the performance
The change make the lexCss("color:")
  x21 - x40 times faster than trunk.
  x2.3 - x4.6 times faster than m74.

Design Doc: http://shorturl.at/adfO5

Measured by out/x64.release/d8 reg977003.js
see reg977003.js attached to chromium:977003

Also see another cl of benchmark in
https://chromium-review.googlesource.com/c/v8/v8/+/1679651/


Bug: chromium:977003
Change-Id: Ie8518493d2c33df1594be1b4576bda715087b421
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1674851
Commit-Queue: Frank Tang <ftang@chromium.org>
Reviewed-by: 's avatarYang Guo <yangguo@chromium.org>
Cr-Commit-Position: refs/heads/master@{#62471}
      f23f644f
    • Jakob Gruber's avatar
      [regexp] Fix BoyerMooreLookahead behavior at submatches · bc4cbe92
      Jakob Gruber authored 
      Since https://codereview.chromium.org/2777583003, the Boyer-Moore
lookahead (used by the irregexp engine) also looks inside submatches
to narrow down its range of accepted characters at specific offsets.

But the end of a submatch, designated by a PositiveSubmatchSuccess
action node, was not handled correctly. When a submatch terminates,
we have no knowledge of what may follow, and thus must accept any
character at following positions. This is done by the SetRest call
added in this CL.

An example, since this is fairly obscure:

/^.*?Y(((?=B?).)*)Y$/s

The initial non-greedy loop, together with the s flag,
will trigger an attempted Boyer-Moore lookahead. After this follows
an unconditional Y, a *-quantified loop matching any char and
containing a lookahead that matches either 1 B or 0 B's, and an
unconditional trailing Y.

When the BM lookahead scans the subject string for the beginning of
this pattern after the non-greedy loop, it should look for: a Y at
offset 0, and either a B, a Y, or '.' (-> any character) at offset 1.

Prior to this CL this was not the case:

- The lookaround is internally generated as a submatch.
- The optional 'B?' is unrolled into 'either B followed by submatch
  end' or 'submatch end'.
- Filling in BM infos terminates when encountering a submatch end.
  Thus in the former case we added B to the set of accepted characters
  and terminated, while in the latter case we simply terminated.o

This CL ensures that BM will accept any character at any offset at or
exceeding the first encountered submatch end.

Bug: v8:8770
Change-Id: Iff998ba307cd9669203846a9182798b8cf6a85dc
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1679506
Commit-Queue: Jakob Gruber <jgruber@chromium.org>
Reviewed-by: 's avatarErik Corry <erikcorry@chromium.org>
Reviewed-by: 's avatarYang Guo <yangguo@chromium.org>
Auto-Submit: Jakob Gruber <jgruber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#62460}
      bc4cbe92
  33. 27 Jun, 2019 1 commit
    • Jakob Gruber's avatar
      [regexp] Refactor BoyerMoorePositionInfo uses · ad68a376
      Jakob Gruber authored 
      BoyerMoorePositionInfo is a simple wrapper around a bitset and an
associated ContainedInLattice field. This CL refactors bitset-related
operations that used to be implemented naively (e.g.: loop over all
bits to find a single set bit, or to generate a union of two bitsets).

Instead, use more suitable methods from base::bits and std::bitset.

Drive-by: Remove dead class members.
Drive-by: Zero the ByteArray with memset.

Bug: v8:9359
Change-Id: I33923c7d216320f4e3d7e4a6df2967f4aa86ab05
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1667407
Commit-Queue: Jakob Gruber <jgruber@chromium.org>
Reviewed-by: 's avatarLeszek Swirski <leszeks@chromium.org>
Cr-Commit-Position: refs/heads/master@{#62419}
      ad68a376
  35. 19 Jun, 2019 2 commits
  37. 18 Jun, 2019 4 commits
  39. 17 Jun, 2019 4 commits
  41. 13 Jun, 2019 3 commits
  43. 12 Jun, 2019 3 commits
  45. 07 Jun, 2019 1 commit
  47. 06 Jun, 2019 1 commit