Indirectly dispatch all backtracking jumps through the same block.

Indirectly dispatch all backtracking jumps through the same block.

BUG=

[zerny-google, 2014-11-13 14:52:08]

The previous CL [1] to use only one dispatch table does not work. We cannot
always jump to the "final" join when backtracking (the register allocator might
place moves between the intermediate target and the final one).

This CL replaces all of the inlined backtracking code by jumps to a single
dispatch block. This causes an indirection but eliminates all duplication both
in the flow-graph and in code-gen. I have not been able to see any regressions
yet on X64. I'll get numbers on other platforms soon. PTAL.

[1]: https://codereview.chromium.org/716163003/

[zerny-google, 2014-11-13 16:25:21]

zerny@google.com changed reviewers:
+ fschneider@google.com, iposva@google.com, vegorov@google.com

[zerny-google, 2014-11-13 16:25:48]

+reviewers

[Vyacheslav Egorov (Google), 2014-11-13 18:30:05]

LGTMwC

https://codereview.chromium.org/722243002/diff/20001/runtime/vm/intermediate_...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/722243002/diff/20001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.cc:2541: Instruction* instr = target;
use target->last_instruction() instead of the loop?

https://codereview.chromium.org/722243002/diff/20001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.cc:2555: intptr_t offset =
when can the ientry be unreachable?

if it is "unreachable" then why is it connected to the IndirectGotoInstr in the
first place?

https://codereview.chromium.org/722243002/diff/20001/runtime/vm/regexp_assemb...
File runtime/vm/regexp_assembler.h (right):

https://codereview.chromium.org/722243002/diff/20001/runtime/vm/regexp_assemb...
runtime/vm/regexp_assembler.h:567: // TODO(zerny): Implement IR support for
"computed gotos" and replace all uses
igoto is a computed goto - so this comment seems a bit strange. 

implement a "different IR support" might work, but overall I think you can just
drop it :)

[zerny-google, 2014-11-14 13:29:29]

Thanks for the review! Comments addressed in latest patch set.

https://codereview.chromium.org/722243002/diff/20001/runtime/vm/intermediate_...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/722243002/diff/20001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.cc:2541: Instruction* instr = target;
On 2014/11/13 18:30:04, Vyacheslav Egorov (Google) wrote:
> use target->last_instruction() instead of the loop?

No can do, since it is not set if the target is unreachable :-(

https://codereview.chromium.org/722243002/diff/20001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.cc:2555: intptr_t offset =
On 2014/11/13 18:30:04, Vyacheslav Egorov (Google) wrote:
> when can the ientry be unreachable?
> 
> if it is "unreachable" then why is it connected to the IndirectGotoInstr in
the
> first place?

It is possible that we never emit a backtracking point despite the regexp
containing branches (also after this CL since here the backtrack block is
unconditionally created). I've added an early escape to this method to avoid
computing tables for an unreachable dispatch instruction.

https://codereview.chromium.org/722243002/diff/20001/runtime/vm/regexp_assemb...
File runtime/vm/regexp_assembler.h (right):

https://codereview.chromium.org/722243002/diff/20001/runtime/vm/regexp_assemb...
runtime/vm/regexp_assembler.h:567: // TODO(zerny): Implement IR support for
"computed gotos" and replace all uses
On 2014/11/13 18:30:04, Vyacheslav Egorov (Google) wrote:
> igoto is a computed goto - so this comment seems a bit strange. 
> 
> implement a "different IR support" might work, but overall I think you can
just
> drop it :)

Yes. I'll drop it from here and add a TODO to the IR declaration about avoiding
the "embedded" gotos.

[zerny-google, 2014-11-14 14:37:03]

FYI, the number of indirect jumps and targets and the collective size of the
resulting tables (sum of jump*target) listed below. The count indicates the
number of compiled regexp matchers. For the regexp benchmark that will include
duplicates from successive runs.

For the RegExp benchmark (collected from some "top 50" websites):

  count = 434

  jump_sum = 866
  jump_max = 12
  jump_min = 0
  jump_avg = 1.995392

  target_sum = 1880
  target_max = 210
  target_min = 0
  target_avg = 4.331797

  table_sum = 7461
  table_max = 2310
  table_min = 0
  table_avg = 17.191244

For all the tests in corelib/regexp:

  count = 1922

  jump_sum = 5151
  jump_max = 299
  jump_min = 0
  jump_avg = 2.680021

  target_sum = 9352
  target_max = 1002
  target_min = 0
  target_avg = 4.865765

  table_sum = 432210
  table_max = 170131
  table_min = 0
  table_avg = 224.875130

So the offsets table can indeed take up considerable space as seen in the case
of the tests which favors using a single dispatch block+table.

[zerny-google, 2014-11-18 06:25:02]

FYI, the performance results of introducing the indirect jump block for the
RegExp benchmark are approx:

- 25% on ia32 (core 2/i5)
+  2% on x64 (core i5)
+ 40% on x64 (core 2)

We do not currently track the RegExp benchmark on other platforms. Should we
have it added to any of the other platforms?

[zerny-google, 2014-11-24 13:08:58]

Merged into: https://codereview.chromium.org/744853003/