commit | 7887c34a29b015fcf7411bafc27ace0d4a1e73e7 | [log] [tgz] |
---|---|---|
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 [diff] |
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 .
Dart is an open-source, scalable programming language, with robust libraries and runtimes, for building web, server, and mobile apps.
Visit the dartlang.org to learn more about the language, tools, getting started, and more.
Browse pub.dartlang.org for more packages and libraries contributed by the community and the Dart team.
If you want to build Dart yourself, here is a guide to getting the source, preparing your machine to build the SDK, and building.
There are more documents on our wiki.
The easiest way to contribute to Dart is to file issues.
You can also contribute patches, as described in Contributing.