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

src/jsregexp.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 22 matching lines @@
 #include "jsregexp-inl.h"
 #include "platform.h"
 #include "runtime.h"
 #include "top.h"
 #include "compilation-cache.h"
 #include "string-stream.h"
 #include "parser.h"
 #include "regexp-macro-assembler.h"
 #include "regexp-macro-assembler-tracer.h"
 #include "regexp-macro-assembler-irregexp.h"
+#include "regexp-stack.h"
 
 #ifdef ARM
 #include "regexp-macro-assembler-arm.h"
 #else  // IA32
 #include "macro-assembler-ia32.h"
 #include "regexp-macro-assembler-ia32.h"
 #endif
 
 #include "interpreter-irregexp.h"
 
@@ skipping 853 matching lines @@
         const byte* address;
         if (is_ascii) {
           ExternalAsciiString* ext = ExternalAsciiString::cast(*subject);
           address = reinterpret_cast<const byte*>(ext->resource()->data());
         } else {
           ExternalTwoByteString* ext = ExternalTwoByteString::cast(*subject);
           address = reinterpret_cast<const byte*>(ext->resource()->data());
         }
         res = RegExpMacroAssemblerIA32::Execute(
             *code,
-            &address,
+            const_cast<Address*>(&address),
             start_offset << char_size_shift,
             end_offset << char_size_shift,
             offsets_vector,
             previous_index == 0);
       } else {  // Sequential string
         Address char_address =
             is_ascii ? SeqAsciiString::cast(*subject)->GetCharsAddress()
                      : SeqTwoByteString::cast(*subject)->GetCharsAddress();
         int byte_offset = char_address - reinterpret_cast<Address>(*subject);
         res = RegExpMacroAssemblerIA32::Execute(
             *code,
-            subject.location(),
+            reinterpret_cast<Address*>(subject.location()),
             byte_offset + (start_offset << char_size_shift),
             byte_offset + (end_offset << char_size_shift),
             offsets_vector,
             previous_index == 0);
       }
 
       if (res == RegExpMacroAssemblerIA32::EXCEPTION) {
         ASSERT(Top::has_pending_exception());
         return Handle<Object>::null();
       }
@@ skipping 325 matching lines @@
     Handle<String> pattern) {
 #ifdef DEBUG
   if (FLAG_trace_regexp_assembler)
     macro_assembler_ = new RegExpMacroAssemblerTracer(macro_assembler);
   else
 #endif
     macro_assembler_ = macro_assembler;
   List <RegExpNode*> work_list(0);
   work_list_ = &work_list;
   Label fail;
-  macro_assembler->PushBacktrack(&fail);
+  macro_assembler->PushBacktrack(&fail,
+                                 RegExpMacroAssembler::kNoStackLimitCheck);
   GenerationVariant generic_variant;
   if (!start->Emit(this, &generic_variant)) {
     fail.Unuse();
     return Handle<FixedArray>::null();
   }
   macro_assembler_->Bind(&fail);
   macro_assembler_->Fail();
   while (!work_list.is_empty()) {
     if (!work_list.RemoveLast()->Emit(this, &generic_variant)) {
       return Handle<FixedArray>::null();
@@ skipping 55 matching lines @@
     affected_registers->Set(action->reg());
     if (action->reg() > max_register) max_register = action->reg();
   }
   return max_register;
 }
 
 
 void GenerationVariant::PushAffectedRegisters(RegExpMacroAssembler* assembler,
                                               int max_register,
                                               OutSet& affected_registers) {
-  for (int reg = 0; reg <= max_register; reg++) {
-    if (affected_registers.Get(reg)) assembler->PushRegister(reg);
+  // Stay safe and check every half times the limit.
+  int push_limit = (assembler->stack_limit() + 1) / 2;

[Erik Corry, 2009/01/12 11:50:13]

Why plus 1?

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

Rounding up in case the value is one (which it happens to be for
macro-assembler-irregexp).
Comment added.

+  for (int reg = 0, pushes = 0; reg <= max_register; reg++) {
+    if (affected_registers.Get(reg)) {
+      pushes++;
+      RegExpMacroAssembler::StackCheckFlag check_stack_limit =
+          (pushes % push_limit) == 0 ?
+                RegExpMacroAssembler::kCheckStackLimit :
+                RegExpMacroAssembler::kNoStackLimitCheck;
+      assembler->PushRegister(reg, check_stack_limit);
+    }
   }
 }
 
 
 void GenerationVariant::RestoreAffectedRegisters(
     RegExpMacroAssembler* assembler,
     int max_register,
     OutSet& affected_registers) {
   for (int reg = max_register; reg >= 0; reg--) {
     if (affected_registers.Get(reg)) assembler->PopRegister(reg);
@@ skipping 88 matching lines @@
 
   // Generate deferred actions here along with code to undo them again.
   OutSet affected_registers;
   int max_register = FindAffectedRegisters(&affected_registers);
   PushAffectedRegisters(assembler, max_register, affected_registers);
   PerformDeferredActions(assembler, max_register, affected_registers);
   if (backtrack() != NULL) {
     // Here we have a concrete backtrack location.  These are set up by choice
     // nodes and so they indicate that we have a deferred save of the current
     // position which we may need to emit here.
-    assembler->PushCurrentPosition();
+    assembler->PushCurrentPosition(RegExpMacroAssembler::kNoStackLimitCheck);

[Erik Corry, 2009/01/12 11:50:13]

We never emit this with stack limit check so the extra boolean is just noise.

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

What's wrong with needless generality now?!?
Ok, removed.

   }
   if (cp_offset_ != 0) {
     assembler->AdvanceCurrentPosition(cp_offset_);
   }
 
   // Create a new trivial state and generate the node with that.
   Label undo;
-  assembler->PushBacktrack(&undo);
+  assembler->PushBacktrack(&undo, RegExpMacroAssembler::kCheckStackLimit);

[Erik Corry, 2009/01/12 11:50:13]

We should always emit this with stack limit check so the extra boolean is just
noise.

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

Removed too

   GenerationVariant new_state;
   bool ok = successor->Emit(compiler, &new_state);
 
   // On backtrack we need to restore state.
   assembler->Bind(&undo);
   if (!ok) return false;
   if (backtrack() != NULL) {
     assembler->PopCurrentPosition();
   }
   RestoreAffectedRegisters(assembler, max_register, affected_registers);
@@ skipping 1312 matching lines @@
   if (choice_count > 1 && text_length != kNodeIsTooComplexForGreedyLoops) {
     // Here we have special handling for greedy loops containing only text nodes
     // and other simple nodes.  These are handled by pushing the current
     // position on the stack and then incrementing the current position each
     // time around the switch.  On backtrack we decrement the current position
     // and check it against the pushed value.  This avoids pushing backtrack
     // information for each iteration of the loop, which could take up a lot of
     // space.
     greedy_loop = true;
     ASSERT(variant->stop_node() == NULL);
-    macro_assembler->PushCurrentPosition();
+    macro_assembler->PushCurrentPosition(
+        RegExpMacroAssembler::kCheckStackLimit);

[Erik Corry, 2009/01/12 11:50:13]

We don't need to check here.  Greedy loops cannot contain other stack operations
(or they would not work) and are not nested.

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

PushCurrentPosition never checks now. 
We shouldn't need more than one of those between other types of pushes anyway.

     current_variant = &counter_backtrack_variant;
     Label greedy_match_failed;
     GenerationVariant greedy_match_variant;
     greedy_match_variant.set_backtrack(&greedy_match_failed);
     Label loop_label;
     macro_assembler->Bind(&loop_label);
     greedy_match_variant.set_stop_node(this);
     greedy_match_variant.set_loop_label(&loop_label);
     bool ok = alternatives_->at(0).node()->Emit(compiler,
                                                 &greedy_match_variant);
@@ skipping 1662 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal