* Move irregexp backtrack stack to external memory area, instead of the system stack.

Separately growing stack for irregexp ia32 backtrack stack.

[Lasse Reichstein, 2009-01-08 14:09:33]

The approach of moving the backtrack stack to another memory area was easier
than expected.
Erik will chat with Ivan when possible to see what further concerns there are at
the conceptual level.

[iposva, 2009-01-09 05:44:13]

I have not looked in detail at the register reshuffling due to the use of ecx as
backtrack stack pointer.

Set of comments below after which it should look good to me.

http://codereview.chromium.org/17416/diff/28/232
File src/regexp-macro-assembler-ia32.cc (left):

http://codereview.chromium.org/17416/diff/28/232#oldcode144
Line 144: __ mov(eax, current_character());
Thanks!

http://codereview.chromium.org/17416/diff/28/232
File src/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/17416/diff/28/232#newcode259
Line 259: // Store current state before reusing the registers.
Should we add a comment like this? (Not sure if I mentioned all the right
registers.)
// After these pushes the registers eax, ebx, ecx, edx and edi are available in
the code below.

http://codereview.chromium.org/17416/diff/28/232#newcode309
Line 309: // Store registers before calling C function.
Store registers -> Save registers

http://codereview.chromium.org/17416/diff/28/232#newcode627
Line 627: __ mov(ecx, Operand(ebp, kStackHighEnd));
How about using backtrack_stackpointer() instead of ecx here?

http://codereview.chromium.org/17416/diff/28/232#newcode708
Line 708: __ bind(&stack_overflow);
Can you please comment why it is still possible to reach here to distinguish
from the stack overflow handling below?

If I am not mistaken the preemption check does verify that the native stack is
sane when popping backtracking information, so if too much things were pushed on
the native stack you would jump to the preemption label and the code determines
that this was not really a preemption but a native stack overflow => return with
an exception. Correct?

http://codereview.chromium.org/17416/diff/28/232#newcode738
Line 738: __ bind(&grow_failed);
You could consolidate this label with the stack_overflow label from above and
name it exit_with_exception.

http://codereview.chromium.org/17416/diff/28/232#newcode987
Line 987: Register RegExpMacroAssemblerIA32::backtrack_stackpointer() {
How about defining this function straight in the header file. As well as other
accessor like functions such as PushCurrentPosition, ...

http://codereview.chromium.org/17416/diff/28/232#newcode1043
Line 1043: Operand(backtrack_stackpointer(), -kPointerSize));
Why not simplify and always use this pattern regardless of the register being
pushed?

http://codereview.chromium.org/17416/diff/28/232#newcode1057
Line 1057: __ mov(Operand(backtrack_stackpointer(), 0), value);
If you do decide to only use one pattern above, you might want to turn this one
around for consistency.

http://codereview.chromium.org/17416/diff/28/236
File src/regexp-stack.cc (right):

http://codereview.chromium.org/17416/diff/28/236#newcode35
Line 35: ExecutionAccess lock;
Please see comment about ExecutionAccess in the header file. I believe it
applies here too.

http://codereview.chromium.org/17416/diff/28/236#newcode46
Line 46: ExecutionAccess lock;
ditto

http://codereview.chromium.org/17416/diff/28/236#newcode54
Line 54: ExecutionAccess lock;
ditto

http://codereview.chromium.org/17416/diff/28/236#newcode63
Line 63: ExecutionAccess lock;
ditto

http://codereview.chromium.org/17416/diff/28/237
File src/regexp-stack.h (right):

http://codereview.chromium.org/17416/diff/28/237#newcode44
Line 44: // Gives the top of the memory used as stack.
Please use empty line between last piece of code and comment for next function
declaration to add structure for the reader's eye.

http://codereview.chromium.org/17416/diff/28/237#newcode46
Line 46: ExecutionAccess lock;
I don't think you need to own the ExecutionAccess here since you are not calling
StackGuard methods. And the external preemption thread is not going to mess with
this thread_local_ data. Ask Erik Corry to be safe though.

http://codereview.chromium.org/17416/diff/28/237#newcode52
Line 52: ExecutionAccess lock;
ditto

http://codereview.chromium.org/17416/diff/28/237#newcode60
Line 60: ExecutionAccess lock;
ditto

[Lasse Reichstein, 2009-01-09 09:59:04]

Addressed review comments

http://codereview.chromium.org/17416/diff/28/232
File src/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/17416/diff/28/232#newcode627
Line 627: __ mov(ecx, Operand(ebp, kStackHighEnd));
On 2009/01/09 05:44:13, iposva wrote:
> How about using backtrack_stackpointer() instead of ecx here?

Done. Good catch!

http://codereview.chromium.org/17416/diff/28/232#newcode708
Line 708: __ bind(&stack_overflow);
Yes, this is correct.
It's unlikely, but perhaps possible in some pathological case, for the system
stack to overflow while we are working on a regexp. We will notice this when we
check the StackGuard.
It's much more likely that we trigger the stack guard due to preemption or
debugging.

http://codereview.chromium.org/17416/diff/28/232#newcode738
Line 738: __ bind(&grow_failed);
On 2009/01/09 05:44:13, iposva wrote:
> You could consolidate this label with the stack_overflow label from above and
> name it exit_with_exception.

Done.

http://codereview.chromium.org/17416/diff/28/232#newcode987
Line 987: Register RegExpMacroAssemblerIA32::backtrack_stackpointer() {
I concur on the accessors, but I prefer to keep all the code-generating
functions in the .cc-file, even if they are small.

http://codereview.chromium.org/17416/diff/28/232#newcode1043
Line 1043: Operand(backtrack_stackpointer(), -kPointerSize));
I'm assuming the version below to be slightly more efficient (and four bytes
shorter), since it doesn't need a displacement on the mov-operation.
I don't actually push the backtrack-stackpointer, so this isn't (currently)
necessary. I'll just make it not work for the backtrack stackpointer instead, to
reduce complexity.
Also, it doesn't matter whether we affect flags, so I might as well use add and
sub instead of lea.

http://codereview.chromium.org/17416/diff/28/237
File src/regexp-stack.h (right):

http://codereview.chromium.org/17416/diff/28/237#newcode44
Line 44: // Gives the top of the memory used as stack.
On 2009/01/09 05:44:13, iposva wrote:
> Please use empty line between last piece of code and comment for next
function
> declaration to add structure for the reader's eye.

Done.

http://codereview.chromium.org/17416/diff/28/237#newcode46
Line 46: ExecutionAccess lock;
Erik concurs. All code using these functions are guaranteed to have the global
V8 lock at the time.

[Erik Corry, 2009-01-09 10:34:58]

LGTM

http://codereview.chromium.org/17416/diff/245/250
File src/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/17416/diff/245/250#newcode244
Line 244: #ifdef DEBUG
This will not do.   We can't generate different code in DEBUG mode than in
release mode.   That leads to undebuggable code generation bugs.

http://codereview.chromium.org/17416/diff/245/250#newcode694
Line 694: // If returned value is non-zero, the stack guard reports the actual
Surely this can't happen any more?

http://codereview.chromium.org/17416/diff/245/251
File src/regexp-macro-assembler-ia32.h (right):

http://codereview.chromium.org/17416/diff/245/251#newcode142
Line 142: // Adds code that loads the character at the given offset from the
That loads n characters...
Actually the other comments don't have the 'Add code that...' prefix.  Should
probably be made consistent.

http://codereview.chromium.org/17416/diff/245/251#newcode151
Line 151: void CheckStackLimit();
At some point we may want to combine CheckStackLimit and CheckPreemption for
efficiency.

http://codereview.chromium.org/17416/diff/245/251#newcode226
Line 226: // Which mode to generate code for (ASCII or UTF16).
UC16, not UTF16

http://codereview.chromium.org/17416/diff/245/254
File src/regexp-stack.cc (right):

http://codereview.chromium.org/17416/diff/245/254#newcode40
Line 40: return to + size;
Whoever introduced this way of archiving thread local data was an idiot :-)

http://codereview.chromium.org/17416/diff/245/254#newcode63
Line 63: size = RoundUpToPowerOf2(size);
I see no need to round up.  On the contrary if we ever move to a growth factor
that is not 2 then it could cause confusion, esp one that is less than 2.

http://codereview.chromium.org/17416/diff/245/255
File src/regexp-stack.h (right):

http://codereview.chromium.org/17416/diff/245/255#newcode90
Line 90: limit_(reinterpret_cast<Address>(kMemoryTop)) {}
You wouldn't have to cast this if it had the right type to start with.  Of
course, then you'd have to cast it in the initializer, but that seems marginally
nicer to me.

http://codereview.chromium.org/17416/diff/245/257
File test/cctest/test-regexp.cc (right):

http://codereview.chromium.org/17416/diff/245/257#newcode680
Line 680: reinterpret_cast<void*>(const_cast<T**>(input))),
A reinterpret_cast in a reinterpret_cast?

[iposva, 2009-01-10 07:31:38]

LGTM.

http://codereview.chromium.org/17416/diff/245/250
File src/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/17416/diff/245/250#newcode695
Line 695: // stack limit being hit and an exception have already been raised.
"an exception has already"

http://codereview.chromium.org/17416/diff/245/254
File src/regexp-stack.cc (right):

http://codereview.chromium.org/17416/diff/245/254#newcode63
Line 63: size = RoundUpToPowerOf2(size);
On 2009/01/09 10:34:58, Erik Corry wrote:
> I see no need to round up.  On the contrary if we ever move to a growth factor
> that is not 2 then it could cause confusion, esp one that is less than 2.

Erik has a point here. The sizes do not have to be a power of two as there is no
assumption in the code about alignment of this block.

[Lasse Reichstein, 2009-01-12 10:34:12]

Erik: As discussed, added explicit request for check of the backtrack stack
limit to Push operations.
Enforces check often enough to avoid undetected overflows.
Could you check just this change?

http://codereview.chromium.org/17416/diff/245/250
File src/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/17416/diff/245/250#newcode694
Line 694: // If returned value is non-zero, the stack guard reports the actual
Since we never push more than a few registers and then call a C function, which
will need to do its own checking if it does anything complex, no.
We should, however, check after allocating space for the registers. If there are
many registers, it could potentially cause a stack overflow, but that's only
necessary to do once.

http://codereview.chromium.org/17416/diff/245/251
File src/regexp-macro-assembler-ia32.h (right):

http://codereview.chromium.org/17416/diff/245/251#newcode142
Line 142: // Adds code that loads the character at the given offset from the
On 2009/01/09 10:34:58, Erik Corry wrote:
> That loads n characters...
> Actually the other comments don't have the 'Add code that...' prefix.  Should
> probably be made consistent.

Done.

http://codereview.chromium.org/17416/diff/245/254
File src/regexp-stack.cc (right):

http://codereview.chromium.org/17416/diff/245/254#newcode63
Line 63: size = RoundUpToPowerOf2(size);
On 2009/01/09 10:34:58, Erik Corry wrote:
> I see no need to round up.  On the contrary if we ever move to a growth
factor
> that is not 2 then it could cause confusion, esp one that is less than 2.

Done.

http://codereview.chromium.org/17416/diff/245/255
File src/regexp-stack.h (right):

http://codereview.chromium.org/17416/diff/245/255#newcode90
Line 90: limit_(reinterpret_cast<Address>(kMemoryTop)) {}
Sadly, I was not allowed to initialize a constant to a pointer type.

http://codereview.chromium.org/17416/diff/245/257
File test/cctest/test-regexp.cc (right):

http://codereview.chromium.org/17416/diff/245/257#newcode680
Line 680: reinterpret_cast<void*>(const_cast<T**>(input))),
I wasn't allowed to cast directly from one pointer-to-pointer type to another.
Which makes me think: Should I really be using static_cast instead?

[Erik Corry, 2009-01-12 11:50:12]

LGTM

http://codereview.chromium.org/17416/diff/262/404
File src/jsregexp.cc (right):

http://codereview.chromium.org/17416/diff/262/404#newcode1353
Line 1353: int push_limit = (assembler->stack_limit() + 1) / 2;
Why plus 1?

http://codereview.chromium.org/17416/diff/262/404#newcode1471
Line 1471:
assembler->PushCurrentPosition(RegExpMacroAssembler::kNoStackLimitCheck);
We never emit this with stack limit check so the extra boolean is just noise.

http://codereview.chromium.org/17416/diff/262/404#newcode1479
Line 1479: assembler->PushBacktrack(&undo,
RegExpMacroAssembler::kCheckStackLimit);
We should always emit this with stack limit check so the extra boolean is just
noise.

http://codereview.chromium.org/17416/diff/262/404#newcode2813
Line 2813: RegExpMacroAssembler::kCheckStackLimit);
We don't need to check here.  Greedy loops cannot contain other stack operations
(or they would not work) and are not nested.

http://codereview.chromium.org/17416/diff/262/405
File src/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/17416/diff/262/405#newcode665
Line 665: __ mov(ecx, -1);  // Word offset of register 0 relative to ebp.
I can't make out what this comment above means.

http://codereview.chromium.org/17416/diff/262/405#newcode671
Line 671: __ dec(ecx);
Please avoid dec due to partial flags update performance hit.

http://codereview.chromium.org/17416/diff/262/405#newcode680
Line 680: i < num_registers_; i += kRegistersPerPage) {
for(...;...;...) should be either all on one line or on 3 lines.

http://codereview.chromium.org/17416/diff/262/405#newcode681
Line 681: __ mov(register_location(i), eax);  // One write every page.
Please add a test that executes this line if there isn't one already.

http://codereview.chromium.org/17416/diff/262/405#newcode876
Line 876: if (check_stack_limit) CheckStackLimit();
Checking twice just to be sure? :-)

http://codereview.chromium.org/17416/diff/262/412
File src/regexp-macro-assembler.h (right):

http://codereview.chromium.org/17416/diff/262/412#newcode57
Line 57: // often is allowed (and encouraged)
Missing full stop, and I see no need to encourage inefficiency.  Also the name
is not descriptive.  Something including the word 'slack' seems more
appropriate.

http://codereview.chromium.org/17416/diff/262/414
File src/regexp-stack.h (right):

http://codereview.chromium.org/17416/diff/262/414#newcode64
Line 64: return &(thread_local_.limit_);
This looks like it would all fit on one line.

[Lasse Reichstein, 2009-01-12 13:03:59]

Addressed review comments.

http://codereview.chromium.org/17416/diff/245/250
File src/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/17416/diff/245/250#newcode695
Line 695: // stack limit being hit and an exception have already been raised.
On 2009/01/10 07:31:39, iposva wrote:
> "an exception has already"

Done.

http://codereview.chromium.org/17416/diff/262/404
File src/jsregexp.cc (right):

http://codereview.chromium.org/17416/diff/262/404#newcode1353
Line 1353: int push_limit = (assembler->stack_limit() + 1) / 2;
Rounding up in case the value is one (which it happens to be for
macro-assembler-irregexp).
Comment added.

http://codereview.chromium.org/17416/diff/262/404#newcode1471
Line 1471:
assembler->PushCurrentPosition(RegExpMacroAssembler::kNoStackLimitCheck);
What's wrong with needless generality now?!?
Ok, removed.

http://codereview.chromium.org/17416/diff/262/404#newcode1479
Line 1479: assembler->PushBacktrack(&undo,
RegExpMacroAssembler::kCheckStackLimit);
Removed too

http://codereview.chromium.org/17416/diff/262/404#newcode2813
Line 2813: RegExpMacroAssembler::kCheckStackLimit);
PushCurrentPosition never checks now. 
We shouldn't need more than one of those between other types of pushes anyway.

http://codereview.chromium.org/17416/diff/262/405
File src/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/17416/diff/262/405#newcode680
Line 680: i < num_registers_; i += kRegistersPerPage) {
On 2009/01/12 11:50:13, Erik Corry wrote:
> for(...;...;...) should be either all on one line or on 3 lines.

Done.

http://codereview.chromium.org/17416/diff/262/405#newcode681
Line 681: __ mov(register_location(i), eax);  // One write every page.
On 2009/01/12 11:50:13, Erik Corry wrote:
> Please add a test that executes this line if there isn't one already.

Done.

http://codereview.chromium.org/17416/diff/262/405#newcode876
Line 876: if (check_stack_limit) CheckStackLimit();
Better safe and safe than sorry and sorry.
Fixed.

http://codereview.chromium.org/17416/diff/262/412
File src/regexp-macro-assembler.h (right):

http://codereview.chromium.org/17416/diff/262/412#newcode57
Line 57: // often is allowed (and encouraged)
On 2009/01/12 11:50:13, Erik Corry wrote:
> Missing full stop, and I see no need to encourage inefficiency.  Also the
name
> is not descriptive.  Something including the word 'slack' seems more
> appropriate.

Done.

http://codereview.chromium.org/17416/diff/262/414
File src/regexp-stack.h (right):

http://codereview.chromium.org/17416/diff/262/414#newcode64
Line 64: return &(thread_local_.limit_);
On 2009/01/12 11:50:13, Erik Corry wrote:
> This looks like it would all fit on one line.

Done.