Use a typed array for the irregexp stack.

Use a typed array for the irregexp stack.

BUG=
R=vegorov@google.com

Committed: https://code.google.com/p/dart/source/detail?r=43039

[zerny-google, 2015-01-20 13:10:57]

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

[zerny-google, 2015-01-20 13:16:39]

This CL replaces the RegExp backtracking stack with a typed-data array with
explicit stack-bounds checks. The "stack slack" assumptions are now the same as
in V8 and in order grow the stack we add an instruction to "grow" a typed-data
array.

This CL shows up to 10-15% improvement on the RegExp and RegExpDna benchmarks.

PTAL

[Vyacheslav Egorov (Google), 2015-01-20 16:26:24]

lgtm

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/code_generato...
File runtime/vm/code_generator.cc (right):

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/code_generato...
runtime/vm/code_generator.cc:1665: DEFINE_RUNTIME_ENTRY(GrowTypedData, 1) {
The name is a bit confusing: but I can't come up with a better one.

Grow implies in-place grow which is not the case.

Maybe ReallocTypedData (parallel with realloc())?

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

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/regexp_assemb...
runtime/vm/regexp_assembler.cc:162: stack_tip_ = Local(Symbols::stack_tip());
Any reason for not calling it stack_pointer_ or stack_top_?

(there are functions like ReadStackPointerFromRegister)

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/regexp_assemb...
runtime/vm/regexp_assembler.cc:908: Definition* stack_tip_def = PeekStack();
Definition* peeked_def 

stack_tip_def is confusing because I thought it contains stack_tip clone but it
actually contains a value at stack[stack_tip]

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/regexp_assemb...
runtime/vm/regexp_assembler.cc:1661: StoreLocal(stack_, Bind(new(I)
GrowTypedDataInstr(stack_val)));
Consider passing stack_cell into GrowTypedDataInstr and let static call update
it instead of building IR for this.

[zerny-google, 2015-01-21 12:03:11]

thanks for the review.

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/code_generato...
File runtime/vm/code_generator.cc (right):

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/code_generato...
runtime/vm/code_generator.cc:1665: DEFINE_RUNTIME_ENTRY(GrowTypedData, 1) {
On 2015/01/20 16:26:24, Vyacheslav Egorov (Google) wrote:
> The name is a bit confusing: but I can't come up with a better one.
> 
> Grow implies in-place grow which is not the case.
> 
> Maybe ReallocTypedData (parallel with realloc())?

Since I've changed the call to take a typed-data cell, as per your suggestion,
the Grow prefix is more fitting now. However, I'm fine with renaming to Realloc
if you like.

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

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/regexp_assemb...
runtime/vm/regexp_assembler.cc:162: stack_tip_ = Local(Symbols::stack_tip());
On 2015/01/20 16:26:24, Vyacheslav Egorov (Google) wrote:
> Any reason for not calling it stack_pointer_ or stack_top_?
> 
> (there are functions like ReadStackPointerFromRegister)

Done.

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/regexp_assemb...
runtime/vm/regexp_assembler.cc:908: Definition* stack_tip_def = PeekStack();
On 2015/01/20 16:26:24, Vyacheslav Egorov (Google) wrote:
> Definition* peeked_def 
> 
> stack_tip_def is confusing because I thought it contains stack_tip clone but
it
> actually contains a value at stack[stack_tip]

Yes. It this is caused by trying to match the names of return types. These
should be binding to a value but the Comparison signature wants definitions :-/

Renamed to simply 'head'.

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/regexp_assemb...
runtime/vm/regexp_assembler.cc:1661: StoreLocal(stack_, Bind(new(I)
GrowTypedDataInstr(stack_val)));
On 2015/01/20 16:26:24, Vyacheslav Egorov (Google) wrote:
> Consider passing stack_cell into GrowTypedDataInstr and let static call update
> it instead of building IR for this.
> 

Done.

[Vyacheslav Egorov (Google), 2015-01-21 12:10:00]

lgtm!

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/code_generato...
File runtime/vm/code_generator.cc (right):

https://codereview.chromium.org/800433004/diff/20001/runtime/vm/code_generato...
runtime/vm/code_generator.cc:1665: DEFINE_RUNTIME_ENTRY(GrowTypedData, 1) {
On 2015/01/21 12:03:11, zerny-google wrote:
> On 2015/01/20 16:26:24, Vyacheslav Egorov (Google) wrote:
> > The name is a bit confusing: but I can't come up with a better one.
> > 
> > Grow implies in-place grow which is not the case.
> > 
> > Maybe ReallocTypedData (parallel with realloc())?
> 
> Since I've changed the call to take a typed-data cell, as per your suggestion,
> the Grow prefix is more fitting now. However, I'm fine with renaming to
Realloc
> if you like.

Agreed. Maybe GrowRegExpStack then?

[zerny-google, 2015-01-21 13:25:43]

> Agreed. Maybe GrowRegExpStack then?

Done.

[zerny-google, 2015-01-21 15:11:58]

Committed patchset #4 (id:60001) manually as 43039 (presubmit successful).