Skip to content

V
V8
Switch branch/tag
  1. 29 Aug, 2019 2 commits
    • Jakob Gruber's avatar
      [regexp] Add an offset argument CheckAtStart · 2e0bc516
      Jakob Gruber authored 
      Similar to CheckNotAtStart, one can now apply an offset to the
CheckAtStart operation. Due to a recent change, all callsites of
CheckNotAtStart now need to pass an offset, whereas previously the
offset was just assumed to be zero.

Bug: chromium:996391
Change-Id: Ia59a584e93e5384479f05abddef7859b420b023a
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1773272
Commit-Queue: Jakob Gruber <jgruber@chromium.org>
Auto-Submit: Jakob Gruber <jgruber@chromium.org>
Reviewed-by: 's avatarPeter Marshall <petermarshall@chromium.org>
Cr-Commit-Position: refs/heads/master@{#63444}
      2e0bc516
    • Jakob Gruber's avatar
      [regexp] Add dedicated flags for printing regexp code and bytecode · eebb18d3
      Jakob Gruber authored 
      Printing regexp code used to behind the generic --print-code flag, but
there was no way to distinguish between irregexp-generated code; and
printing regexp bytecode was not supported at all (the
--trace-regexp-bytecodes flag *did* exist, but prints the execution
trace at runtime and not the generated bytecode sequence).

This CL adds two new flags:

--print-regexp-code
--print-regexp-bytecode

Regexp code is no longer printed as part of --print-code.

Example output for --print-regexp-bytecode:

generated bytecode for regexp pattern: .(?<!^.)
0x1ddcc614cbd0     0  PUSH_BT, 02, 00, 00, 00, c0, 00, 00, 00 .......
0x1ddcc614cbd8     8  LOAD_CURRENT_CHAR, 11, 00, 00, 00, b0, 00, 00, 00 .......
0x1ddcc614cbe0    10  CHECK_CHAR, 18, 0a, 00, 00, b0, 00, 00, 00 .......
0x1ddcc614cbe8    18  CHECK_CHAR, 18, 0d, 00, 00, b0, 00, 00, 00 .......
0x1ddcc614cbf0    20  PUSH_CP, 01, 00, 00, 00 ...

Bug: chromium:996391
Change-Id: I731defbd7cf9ed29753a39bb1d7205dc136ca950
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1773249
Commit-Queue: Jakob Gruber <jgruber@chromium.org>
Auto-Submit: Jakob Gruber <jgruber@chromium.org>
Reviewed-by: 's avatarPeter Marshall <petermarshall@chromium.org>
Cr-Commit-Position: refs/heads/master@{#63442}
      eebb18d3
  3. 28 Aug, 2019 1 commit
    • Jakob Gruber's avatar
      [regexp] Dont attempt to match '^' before the start of the string · 1990b1e1
      Jakob Gruber authored 
      This fixes an invalid assumption when emitting code for matching '^'
(start of line) in multiline regexps and '\b', '\B' in general.

What we used to do: if the current trace's cp_offset (the offset from
the current position) was non-zero, we assumed that we were looking at
subject string index 1 or greater (i.e.: not at the start of the string
or before).

This is no longer valid since cp_offsets can now be negative.

This CL changes the logic to omit start- and bounds-checks only for
strictly positive cp_offsets, where the above assumption still holds.

Bug: chromium:996391
Change-Id: I79be4fc295c6f0b63e41c13d1e91fdd00f2f2b42
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1771794
Commit-Queue: Erik Corry <erikcorry@chromium.org>
Auto-Submit: Jakob Gruber <jgruber@chromium.org>
Reviewed-by: 's avatarErik Corry <erikcorry@chromium.org>
Cr-Commit-Position: refs/heads/master@{#63424}
      1990b1e1
  5. 23 Aug, 2019 1 commit
  7. 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
  9. 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
  11. 29 Jul, 2019 1 commit
    • 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
  13. 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
  15. 01 Jul, 2019 1 commit
    • 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
  17. 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
  19. 19 Jun, 2019 2 commits
  21. 18 Jun, 2019 3 commits
  23. 17 Jun, 2019 3 commits
  25. 13 Jun, 2019 3 commits
  27. 12 Jun, 2019 3 commits
  29. 07 Jun, 2019 1 commit
  31. 23 May, 2019 2 commits
  33. 22 May, 2019 1 commit
  35. 21 May, 2019 2 commits
  37. 20 May, 2019 1 commit
  39. 10 May, 2019 1 commit
  41. 06 May, 2019 1 commit
  43. 29 Apr, 2019 1 commit
    • Clemens Hammacher's avatar
      [cleanup] Use Vector::begin instead of Vector::start · 4b0f9c85
      Clemens Hammacher authored 
      Our {Vector} template provides both {start} and {begin} methods. They
return exactly the same value. Since the {begin} method is needed for
iteration, and is also what standard containers provide, this CL
switches all uses of the {start} method to use {begin} instead.

Patchset 1 was auto-generated by using this clang AST matcher:
    callExpr(
        callee(
          cxxMethodDecl(
            hasName("start"),
            ofClass(hasName("v8::internal::Vector")))
        ),
        argumentCountIs(0))

Patchset 2 was created by running clang-format. Patchset 3 then
removes the now unused {Vector::start} method.

R=jkummerow@chromium.org
TBR=mstarzinger@chromium.org,yangguo@chromium.org,verwaest@chromium.org

Bug: v8:9183
Change-Id: Id9f01c92870872556e2bb3f6d5667463b0e3e5c6
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1587381Reviewed-by: 's avatarJakob Kummerow <jkummerow@chromium.org>
Commit-Queue: Clemens Hammacher <clemensh@chromium.org>
Cr-Commit-Position: refs/heads/master@{#61081}
      4b0f9c85
  45. 03 Apr, 2019 2 commits
  47. 12 Mar, 2019 2 commits
  49. 11 Mar, 2019 2 commits