commit 7887c34a29b015fcf7411bafc27ace0d4a1e73e7
author Vyacheslav Egorov <vegorov@google.com> Fri Jun 23 12:51:52 2017 +0200
committer Vyacheslav Egorov <vegorov@google.com> Fri Jun 23 12:51:53 2017 +0200
tree a3f025f38ae43069aa59925849edb8e57d3d150b
parent 23083fdee191d473b79f44e8bdf48db302e92c32

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

Review-Url: https://codereview.chromium.org/2951053003 .