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.
* ensures that IR generated by IRRegExpMacroAssembler is OSR compatible:
  * GraphEntryInstr has correct osr_id;
  * GraphEntry and normal entry have different block ids (B0 and B1 - instead of B0 and B0);
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell and :stack
    are always in sync, because :stack can come from OSR or deoptimization why stack_array_cell
    is a constant associated with a particular Code object.
* refactors the way the RegExp stack was growing: instead of having a special instruction
  just emit a call to a Dart function;
* refactors the way block pruning for OSR is done by consolidating duplicated code
  in a single function.

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).

CL history
----------

This relands commit d87cc52c3ee791e4dff9136c5c80353deb0f36a3.

Original code review: https://codereview.chromium.org/2950783003/

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

R=erikcorry@google.com

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

[Vyacheslav Egorov (Google), 2017-06-21 20:22: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...
==========

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.
* ensures that IR generated by IRRegExpMacroAssembler is OSR compatible:
  * GraphEntryInstr has correct osr_id;
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR
entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell
and :stack are always in sync, because :stack can come from OSR or
deoptimization why stack_array_cell is a constant associated with a particular
Code object.
* refactored the way the RegExp stack was growing: instead of having a special
instruction just emit a call to a Dart function. 
  
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...
==========

[Vyacheslav Egorov (Google), 2017-06-21 20:24:03]

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.
* ensures that IR generated by IRRegExpMacroAssembler is OSR compatible:
  * GraphEntryInstr has correct osr_id;
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR
entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell
and :stack are always in sync, because :stack can come from OSR or
deoptimization why stack_array_cell is a constant associated with a particular
Code object.
* refactored the way the RegExp stack was growing: instead of having a special
instruction just emit a call to a Dart function. 
  
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...
==========

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.
* ensures that IR generated by IRRegExpMacroAssembler is OSR compatible:
  * GraphEntryInstr has correct osr_id;
  * GraphEntry and normal entry have different block ids (B0 and B1 - instead of
B0 and B0);
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR
entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell
and :stack are always in sync, because :stack can come from OSR or
deoptimization why stack_array_cell is a constant associated with a particular
Code object.
* refactored the way the RegExp stack was growing: instead of having a special
instruction just emit a call to a Dart function. 
  
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...
==========

[Vyacheslav Egorov (Google), 2017-06-21 20:26: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.
* ensures that IR generated by IRRegExpMacroAssembler is OSR compatible:
  * GraphEntryInstr has correct osr_id;
  * GraphEntry and normal entry have different block ids (B0 and B1 - instead of
B0 and B0);
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR
entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell
and :stack are always in sync, because :stack can come from OSR or
deoptimization why stack_array_cell is a constant associated with a particular
Code object.
* refactored the way the RegExp stack was growing: instead of having a special
instruction just emit a call to a Dart function. 
  
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...
==========

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.
* ensures that IR generated by IRRegExpMacroAssembler is OSR compatible:
  * GraphEntryInstr has correct osr_id;
  * GraphEntry and normal entry have different block ids (B0 and B1 - instead of
B0 and B0);
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR
entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell
and :stack are always in sync, because :stack can come from OSR or
deoptimization why stack_array_cell is a constant associated with a particular
Code object.
* refactored the way the RegExp stack was growing: instead of having a special
instruction just emit a call to a Dart function. 
  
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).

CL history
----------

This relands commit d87cc52c3ee791e4dff9136c5c80353deb0f36a3.

Original code review: https://codereview.chromium.org/2950783003/

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

[Vyacheslav Egorov (Google), 2017-06-21 20:26:05]

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

[Vyacheslav Egorov (Google), 2017-06-21 20:28:41]

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.
* ensures that IR generated by IRRegExpMacroAssembler is OSR compatible:
  * GraphEntryInstr has correct osr_id;
  * GraphEntry and normal entry have different block ids (B0 and B1 - instead of
B0 and B0);
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR
entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell
and :stack are always in sync, because :stack can come from OSR or
deoptimization why stack_array_cell is a constant associated with a particular
Code object.
* refactored the way the RegExp stack was growing: instead of having a special
instruction just emit a call to a Dart function. 
  
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).

CL history
----------

This relands commit d87cc52c3ee791e4dff9136c5c80353deb0f36a3.

Original code review: https://codereview.chromium.org/2950783003/

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

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.
* ensures that IR generated by IRRegExpMacroAssembler is OSR compatible:
  * GraphEntryInstr has correct osr_id;
  * GraphEntry and normal entry have different block ids (B0 and B1 - instead of
B0 and B0);
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR
entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell
and :stack 
    are always in sync, because :stack can come from OSR or deoptimization why
stack_array_cell
    is a constant associated with a particular Code object.
* refactors the way the RegExp stack was growing: instead of having a special
instruction 
  just emit a call to a Dart function;
* refactors the way block pruning for OSR is done by consolidating duplicated
code
  in a single function.
  
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).

CL history
----------

This relands commit d87cc52c3ee791e4dff9136c5c80353deb0f36a3.

Original code review: https://codereview.chromium.org/2950783003/

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

[Vyacheslav Egorov (Google), 2017-06-21 20:33:45]

Hi Erik,

Please take a look. 

The changes from the previous CL: 

1) Fixed compilation error in the intermediate_language.cc on some compilers;

2) Fixed issues with OSR caused by IRRegExpMacroAssembler generating OSR
incompatible code or not doing all necessary things to IR during OSR:
  * GraphEntry and normal entry must have different block ids (B0 and B1 -
instead of B0 and B0);
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR
entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell
and :stack 
    are always in sync, because :stack can come from OSR or deoptimization why
stack_array_cell
    is a constant associated with a particular Code object.
* refactors the way the RegExp stack was growing: instead of having a special
instruction 
  just emit a call to a Dart function;
* refactors the way block pruning for OSR is done by consolidating duplicated
code
  in a single function.

[erikcorry, 2017-06-22 13:08:06]

LGTM

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/compiler.cc#...
runtime/vm/compiler.cc:179: // When compiling for OSR, use a depth first search
to prune instructions
Actually "use a depth first search to find the entry point.  Later, the
instructions not reachable from the entry point will be pruned by
DiscoverBlocks.

Is this the right understanding.  I think this method should be called "Attach
OSR Entry Point" since it doesn't actually prune anything, if I've understood it
right.

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/intermediate...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/intermediate...
runtime/vm/intermediate_language.h:1300: // entry point.
Perform a depth first search to find the OSR entry point. Later we will prune
code not findable from this point.

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/regexp_assem...
File runtime/vm/regexp_assembler.h (right):

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/regexp_assem...
runtime/vm/regexp_assembler.h:156: // Checks for pre-emption and serves as an
OSR entry.
preemption with no hypen

[Vyacheslav Egorov (Google), 2017-06-22 14:58:48]

Thanks for the review. Landing.

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/compiler.cc#...
runtime/vm/compiler.cc:179: // When compiling for OSR, use a depth first search
to prune instructions
On 2017/06/22 13:08:06, erikcorry wrote:
> Actually "use a depth first search to find the entry point.  Later, the
> instructions not reachable from the entry point will be pruned by
> DiscoverBlocks.
> 
> Is this the right understanding.  I think this method should be called "Attach
> OSR Entry Point" since it doesn't actually prune anything, if I've understood
it
> right.


Renamed to RelinkToOsrEntry()

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/intermediate...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/intermediate...
runtime/vm/intermediate_language.h:1300: // entry point.
On 2017/06/22 13:08:06, erikcorry wrote:
> Perform a depth first search to find the OSR entry point. Later we will prune
> code not findable from this point.

Done.

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/regexp_assem...
File runtime/vm/regexp_assembler.h (right):

https://codereview.chromium.org/2951053003/diff/40001/runtime/vm/regexp_assem...
runtime/vm/regexp_assembler.h:156: // Checks for pre-emption and serves as an
OSR entry.
On 2017/06/22 13:08:06, erikcorry wrote:
> preemption with no hypen

Done.

[Vyacheslav Egorov (Google), 2017-06-23 10:51:57]

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.
* ensures that IR generated by IRRegExpMacroAssembler is OSR compatible:
  * GraphEntryInstr has correct osr_id;
  * GraphEntry and normal entry have different block ids (B0 and B1 - instead of
B0 and B0);
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR
entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell
and :stack 
    are always in sync, because :stack can come from OSR or deoptimization why
stack_array_cell
    is a constant associated with a particular Code object.
* refactors the way the RegExp stack was growing: instead of having a special
instruction 
  just emit a call to a Dart function;
* refactors the way block pruning for OSR is done by consolidating duplicated
code
  in a single function.
  
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).

CL history
----------

This relands commit d87cc52c3ee791e4dff9136c5c80353deb0f36a3.

Original code review: https://codereview.chromium.org/2950783003/

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

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.
* ensures that IR generated by IRRegExpMacroAssembler is OSR compatible:
  * GraphEntryInstr has correct osr_id;
  * GraphEntry and normal entry have different block ids (B0 and B1 - instead of
B0 and B0);
  * unreachable blocks are pruned and GraphEntry is rewired to point to OSR
entry;
  * IRRegExpMacroAssembler::GrowStack should not assume that  stack_array_cell
and :stack
    are always in sync, because :stack can come from OSR or deoptimization why
stack_array_cell
    is a constant associated with a particular Code object.
* refactors the way the RegExp stack was growing: instead of having a special
instruction
  just emit a call to a Dart function;
* refactors the way block pruning for OSR is done by consolidating duplicated
code
  in a single function.

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).

CL history
----------

This relands commit d87cc52c3ee791e4dff9136c5c80353deb0f36a3.

Original code review: https://codereview.chromium.org/2950783003/

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

R=erikcorry@google.com

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

[Vyacheslav Egorov (Google), 2017-06-23 10:51:58]

Committed patchset #3 (id:40001) manually as
7887c34a29b015fcf7411bafc27ace0d4a1e73e7 (presubmit successful).