VM(RegExp): Allow OSR optimization of RegExp :matcher functions.

VM(RegExp): Allow OSR optimization of RegExp :matcher functions.

Previously these functions would only contain a single CheckStackOverflowInstr
in a backtracking block and that CheckStackOverflowInstr would have a zero
loop_depth - which means it would not be considered eligable for OSR.

This change:

* adds CheckStackOverflowInstr with non-zero loop_depth in two other places
  (Boyer-Moore lookahead skip loop and greedy loop) where loops arise in the
  generated IL;
* sets non-zero loop depth on the CheckStackOverflowInstr in the backtracking
  block;
* adds a flag on CheckStackOverflowInstr that allows optimizing compiler to
  optimize away those checks that were inserted solely to serve as OSR entries.

We allow the optimizing compiler to remove preemption checks from
non-backtracking loops in the regexp code because those loops
unlike backtracking have guaranteed O(input_length) time
complexity.

Performance Implications
------------------------

This change improves performance of regexps in cases where regexp spends a lot
of time in the first invocation (either due to backtracking or due to long non
matching prefix) by allowing VM to optimize the :matcher while :matcher is
running.

For example on regex-redux[1] benchmark it improves Dart performance by 3x
(from ~18s to ~6s on my Mac Book Pro).

[1] https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&lang=dart&id=2

BUG=
R=erikcorry@google.com

Committed: https://github.com/dart-lang/sdk/commit/d87cc52c3ee791e4dff9136c5c80353deb0f36a3

[Vyacheslav Egorov (Google), 2017-06-20 16:38:06]

Description was changed from

==========
VM(RegExp): Allow OSR optimizing into RegExp :matcher functions.

Previously these functions would only contain a single CheckStackOverflowInstr
in a backtracking block and that CheckStackOverflowInstr would have a zero
loop_depth - which means it would not be considered eligable for OSR.

This change:

* adds CheckStackOverflowInstr with non-zero loop_depth in two other places
  (Boyer-Moore lookahead skip loop and greedy loop) where loops arise in the
  generated IL;
* sets non-zero loop depth on the CheckStackOverflowInstr in the backtracking
  block;
* adds a flag on CheckStackOverflowInstr that allows optimizing compiler to
  optimize away those checks that were inserted solely to serve as OSR entries.

Performance Implications
------------------------

This change improves performance of regexps in cases where regexp spends a lot
of time in the first invocation (either due to backtracking or due to long non
matching prefix) by allowing VM to optimize the :matcher while :matcher is
running.

For example on regex-redux[1] benchmark it improves Dart performance by 3x
(from ~18s to ~6s on my Mac Book Pro).

[1]
https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&lan...

BUG=
==========

to

==========
VM(RegExp): Allow OSR optimization of RegExp :matcher functions.

Previously these functions would only contain a single CheckStackOverflowInstr
in a backtracking block and that CheckStackOverflowInstr would have a zero
loop_depth - which means it would not be considered eligable for OSR.

This change:

* adds CheckStackOverflowInstr with non-zero loop_depth in two other places
  (Boyer-Moore lookahead skip loop and greedy loop) where loops arise in the
  generated IL;
* sets non-zero loop depth on the CheckStackOverflowInstr in the backtracking
  block;
* adds a flag on CheckStackOverflowInstr that allows optimizing compiler to
  optimize away those checks that were inserted solely to serve as OSR entries.

Performance Implications
------------------------

This change improves performance of regexps in cases where regexp spends a lot
of time in the first invocation (either due to backtracking or due to long non
matching prefix) by allowing VM to optimize the :matcher while :matcher is
running.

For example on regex-redux[1] benchmark it improves Dart performance by 3x
(from ~18s to ~6s on my Mac Book Pro).

[1]
https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&lan...

BUG=
==========

[Vyacheslav Egorov (Google), 2017-06-20 16:38:27]

vegorov@google.com changed reviewers:
+ erikcorry@google.com

[Vyacheslav Egorov (Google), 2017-06-20 16:38:29]

Hi Erik,

Please take a look.

[rmacnak, 2017-06-20 17:57:14]

rmacnak@google.com changed reviewers:
+ rmacnak@google.com

[rmacnak, 2017-06-20 17:57:15]

It might be worth keeping the new StackOverflowChecks in the optimized code to
handle interrupt requests (https://github.com/dart-lang/sdk/issues/26041)

[erikcorry, 2017-06-21 07:54:07]

LGTM

The important thing is to have preemption in the backtracking, since that can
run for a long time.

The greedy loops and the Boyer-Moore skipping code, are designed to be very
tight loops and it's important to note they always make progress, so their
running time is limited by the input string length.

For regex-redux I measured Slava's current change, which scans strings at
309Mbytes/s.  If we put the preemption checks in the greedy loops and the
Boyer-Moore loop that falls to 295Mbytes/s, a reduction of about 4.5%.

Since these loops scan linearly without backtracking, you would need a truly
gargantuan input string to see a noticable preemption gap.

https://codereview.chromium.org/2950783003/diff/1/runtime/vm/regexp_assembler...
File runtime/vm/regexp_assembler_ir.cc (right):

https://codereview.chromium.org/2950783003/diff/1/runtime/vm/regexp_assembler...
runtime/vm/regexp_assembler_ir.cc:1774: // Setting non-zero loop_depth turns
this CheckStackOverflow into
This is confusing.  "Turns it into an OSR entry" sounds like it affects the
'kind' flag which can be either kOsrEntry or kFull.  Perhaps:

Perhaps it's clearer to rename kFull to kOsrAndPreemption?  And/or  write:

// We don't have the loop_depth available when compiling regexps, but
// we set loop_depth to a non-zero value because this instruction does
// not emit OSR entry information outside loops.

[Vyacheslav Egorov (Google), 2017-06-21 11:40:47]

Description was changed from

==========
VM(RegExp): Allow OSR optimization of RegExp :matcher functions.

Previously these functions would only contain a single CheckStackOverflowInstr
in a backtracking block and that CheckStackOverflowInstr would have a zero
loop_depth - which means it would not be considered eligable for OSR.

This change:

* adds CheckStackOverflowInstr with non-zero loop_depth in two other places
  (Boyer-Moore lookahead skip loop and greedy loop) where loops arise in the
  generated IL;
* sets non-zero loop depth on the CheckStackOverflowInstr in the backtracking
  block;
* adds a flag on CheckStackOverflowInstr that allows optimizing compiler to
  optimize away those checks that were inserted solely to serve as OSR entries.

Performance Implications
------------------------

This change improves performance of regexps in cases where regexp spends a lot
of time in the first invocation (either due to backtracking or due to long non
matching prefix) by allowing VM to optimize the :matcher while :matcher is
running.

For example on regex-redux[1] benchmark it improves Dart performance by 3x
(from ~18s to ~6s on my Mac Book Pro).

[1]
https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&lan...

BUG=
==========

to

==========
VM(RegExp): Allow OSR optimization of RegExp :matcher functions.

Previously these functions would only contain a single CheckStackOverflowInstr
in a backtracking block and that CheckStackOverflowInstr would have a zero
loop_depth - which means it would not be considered eligable for OSR.

This change:

* adds CheckStackOverflowInstr with non-zero loop_depth in two other places
  (Boyer-Moore lookahead skip loop and greedy loop) where loops arise in the
  generated IL;
* sets non-zero loop depth on the CheckStackOverflowInstr in the backtracking
  block;
* adds a flag on CheckStackOverflowInstr that allows optimizing compiler to
  optimize away those checks that were inserted solely to serve as OSR entries.

We allow the optimizing compiler to remove preemption checks from
non-backtracking loops in the regexp code because those loops unlike
backtracking have guaranteed O(input_length) time complexity.

Performance Implications
------------------------

This change improves performance of regexps in cases where regexp spends a lot
of time in the first invocation (either due to backtracking or due to long non
matching prefix) by allowing VM to optimize the :matcher while :matcher is
running.

For example on regex-redux[1] benchmark it improves Dart performance by 3x
(from ~18s to ~6s on my Mac Book Pro).

[1]
https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&lan...

BUG=
==========

[Vyacheslav Egorov (Google), 2017-06-21 11:41:05]

Description was changed from

==========
VM(RegExp): Allow OSR optimization of RegExp :matcher functions.

Previously these functions would only contain a single CheckStackOverflowInstr
in a backtracking block and that CheckStackOverflowInstr would have a zero
loop_depth - which means it would not be considered eligable for OSR.

This change:

* adds CheckStackOverflowInstr with non-zero loop_depth in two other places
  (Boyer-Moore lookahead skip loop and greedy loop) where loops arise in the
  generated IL;
* sets non-zero loop depth on the CheckStackOverflowInstr in the backtracking
  block;
* adds a flag on CheckStackOverflowInstr that allows optimizing compiler to
  optimize away those checks that were inserted solely to serve as OSR entries.

We allow the optimizing compiler to remove preemption checks from
non-backtracking loops in the regexp code because those loops unlike
backtracking have guaranteed O(input_length) time complexity.

Performance Implications
------------------------

This change improves performance of regexps in cases where regexp spends a lot
of time in the first invocation (either due to backtracking or due to long non
matching prefix) by allowing VM to optimize the :matcher while :matcher is
running.

For example on regex-redux[1] benchmark it improves Dart performance by 3x
(from ~18s to ~6s on my Mac Book Pro).

[1]
https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&lan...

BUG=
==========

to

==========
VM(RegExp): Allow OSR optimization of RegExp :matcher functions.

Previously these functions would only contain a single CheckStackOverflowInstr
in a backtracking block and that CheckStackOverflowInstr would have a zero
loop_depth - which means it would not be considered eligable for OSR.

This change:

* adds CheckStackOverflowInstr with non-zero loop_depth in two other places
  (Boyer-Moore lookahead skip loop and greedy loop) where loops arise in the
  generated IL;
* sets non-zero loop depth on the CheckStackOverflowInstr in the backtracking
  block;
* adds a flag on CheckStackOverflowInstr that allows optimizing compiler to
  optimize away those checks that were inserted solely to serve as OSR entries.

We allow the optimizing compiler to remove preemption checks from
non-backtracking loops in the regexp code because those loops
unlike backtracking have guaranteed O(input_length) time
complexity.

Performance Implications
------------------------

This change improves performance of regexps in cases where regexp spends a lot
of time in the first invocation (either due to backtracking or due to long non
matching prefix) by allowing VM to optimize the :matcher while :matcher is
running.

For example on regex-redux[1] benchmark it improves Dart performance by 3x
(from ~18s to ~6s on my Mac Book Pro).

[1]
https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&lan...

BUG=
==========

[Vyacheslav Egorov (Google), 2017-06-21 11:42:04]

Thanks. 

I updated CL description to include the reasoning for removing those preemption
checks.

https://codereview.chromium.org/2950783003/diff/1/runtime/vm/regexp_assembler...
File runtime/vm/regexp_assembler_ir.cc (right):

https://codereview.chromium.org/2950783003/diff/1/runtime/vm/regexp_assembler...
runtime/vm/regexp_assembler_ir.cc:1774: // Setting non-zero loop_depth turns
this CheckStackOverflow into
On 2017/06/21 07:54:07, erikcorry wrote:
> This is confusing.  "Turns it into an OSR entry" sounds like it affects the
> 'kind' flag which can be either kOsrEntry or kFull.  Perhaps:
> 
> Perhaps it's clearer to rename kFull to kOsrAndPreemption?  And/or  write:
> 
> // We don't have the loop_depth available when compiling regexps, but
> // we set loop_depth to a non-zero value because this instruction does
> // not emit OSR entry information outside loops.

Done.

[Vyacheslav Egorov (Google), 2017-06-21 11:46:51]

Description was changed from

==========
VM(RegExp): Allow OSR optimization of RegExp :matcher functions.

Previously these functions would only contain a single CheckStackOverflowInstr
in a backtracking block and that CheckStackOverflowInstr would have a zero
loop_depth - which means it would not be considered eligable for OSR.

This change:

* adds CheckStackOverflowInstr with non-zero loop_depth in two other places
  (Boyer-Moore lookahead skip loop and greedy loop) where loops arise in the
  generated IL;
* sets non-zero loop depth on the CheckStackOverflowInstr in the backtracking
  block;
* adds a flag on CheckStackOverflowInstr that allows optimizing compiler to
  optimize away those checks that were inserted solely to serve as OSR entries.

We allow the optimizing compiler to remove preemption checks from
non-backtracking loops in the regexp code because those loops
unlike backtracking have guaranteed O(input_length) time
complexity.

Performance Implications
------------------------

This change improves performance of regexps in cases where regexp spends a lot
of time in the first invocation (either due to backtracking or due to long non
matching prefix) by allowing VM to optimize the :matcher while :matcher is
running.

For example on regex-redux[1] benchmark it improves Dart performance by 3x
(from ~18s to ~6s on my Mac Book Pro).

[1]
https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&lan...

BUG=
==========

to

==========
VM(RegExp): Allow OSR optimization of RegExp :matcher functions.

Previously these functions would only contain a single CheckStackOverflowInstr
in a backtracking block and that CheckStackOverflowInstr would have a zero
loop_depth - which means it would not be considered eligable for OSR.

This change:

* adds CheckStackOverflowInstr with non-zero loop_depth in two other places
  (Boyer-Moore lookahead skip loop and greedy loop) where loops arise in the
  generated IL;
* sets non-zero loop depth on the CheckStackOverflowInstr in the backtracking
  block;
* adds a flag on CheckStackOverflowInstr that allows optimizing compiler to
  optimize away those checks that were inserted solely to serve as OSR entries.

We allow the optimizing compiler to remove preemption checks from
non-backtracking loops in the regexp code because those loops
unlike backtracking have guaranteed O(input_length) time
complexity.

Performance Implications
------------------------

This change improves performance of regexps in cases where regexp spends a lot
of time in the first invocation (either due to backtracking or due to long non
matching prefix) by allowing VM to optimize the :matcher while :matcher is
running.

For example on regex-redux[1] benchmark it improves Dart performance by 3x
(from ~18s to ~6s on my Mac Book Pro).

[1]
https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&lan...

BUG=
R=erikcorry@google.com

Committed:
https://github.com/dart-lang/sdk/commit/d87cc52c3ee791e4dff9136c5c80353deb0f36a3
==========

[Vyacheslav Egorov (Google), 2017-06-21 11:46:52]

Committed patchset #1 (id:1) manually as
d87cc52c3ee791e4dff9136c5c80353deb0f36a3 (presubmit successful).