Reduce regexp compiler stack size when not optimizing regexps

src/jsregexp.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/v8.h"
 
 #include "src/ast.h"
 #include "src/base/platform/platform.h"
 #include "src/compilation-cache.h"
 #include "src/compiler.h"
@@ skipping 968 matching lines @@
       return next_register_;
     }
     return next_register_++;
   }
 
   RegExpEngine::CompilationResult Assemble(RegExpMacroAssembler* assembler,
                                            RegExpNode* start,
                                            int capture_count,
                                            Handle<String> pattern);
 
-  inline void AddWork(RegExpNode* node) { work_list_->Add(node); }
+  inline void AddWork(RegExpNode* node) {
+    if (!node->on_work_list() && !node->label()->is_bound()) {
+      node->set_on_work_list(true);
+      work_list_->Add(node);
+    }
+  }
 
   static const int kImplementationOffset = 0;
   static const int kNumberOfRegistersOffset = 0;
   static const int kCodeOffset = 1;
 
   RegExpMacroAssembler* macro_assembler() { return macro_assembler_; }
   EndNode* accept() { return accept_; }
 
   static const int kMaxRecursion = 100;
   inline int recursion_depth() { return recursion_depth_; }
   inline void IncrementRecursionDepth() { recursion_depth_++; }
   inline void DecrementRecursionDepth() { recursion_depth_--; }
 
   void SetRegExpTooBig() { reg_exp_too_big_ = true; }
 
   inline bool ignore_case() { return ignore_case_; }
   inline bool one_byte() { return one_byte_; }
   inline bool optimize() { return optimize_; }
   inline void set_optimize(bool value) { optimize_ = value; }
+  inline bool limiting_recursion() { return limiting_recursion_; }
+  inline void set_limiting_recursion(bool value) {
+    limiting_recursion_ = value;
+  }
   FrequencyCollator* frequency_collator() { return &frequency_collator_; }
 
   int current_expansion_factor() { return current_expansion_factor_; }
   void set_current_expansion_factor(int value) {
     current_expansion_factor_ = value;
   }
 
   Isolate* isolate() const { return isolate_; }
   Zone* zone() const { return zone_; }
 
   static const int kNoRegister = -1;
 
  private:
   EndNode* accept_;
   int next_register_;
   List<RegExpNode*>* work_list_;
   int recursion_depth_;
   RegExpMacroAssembler* macro_assembler_;
   bool ignore_case_;
   bool one_byte_;
   bool reg_exp_too_big_;
+  bool limiting_recursion_;
   bool optimize_;
   int current_expansion_factor_;
   FrequencyCollator frequency_collator_;
   Isolate* isolate_;
   Zone* zone_;
 };
 
 
 class RecursionCheck {
  public:
@@ skipping 14 matching lines @@
 // Attempts to compile the regexp using an Irregexp code generator.  Returns
 // a fixed array or a null handle depending on whether it succeeded.
 RegExpCompiler::RegExpCompiler(Isolate* isolate, Zone* zone, int capture_count,
                                bool ignore_case, bool one_byte)
     : next_register_(2 * (capture_count + 1)),
       work_list_(NULL),
       recursion_depth_(0),
       ignore_case_(ignore_case),
       one_byte_(one_byte),
       reg_exp_too_big_(false),
+      limiting_recursion_(false),
       optimize_(FLAG_regexp_optimization),
       current_expansion_factor_(1),
       frequency_collator_(),
       isolate_(isolate),
       zone_(zone) {
   accept_ = new(zone) EndNode(EndNode::ACCEPT, zone);
   DCHECK(next_register_ - 1 <= RegExpMacroAssembler::kMaxRegister);
 }
 
 
@@ skipping 14 matching lines @@
 
   List <RegExpNode*> work_list(0);
   work_list_ = &work_list;
   Label fail;
   macro_assembler_->PushBacktrack(&fail);
   Trace new_trace;
   start->Emit(this, &new_trace);
   macro_assembler_->Bind(&fail);
   macro_assembler_->Fail();
   while (!work_list.is_empty()) {
-    work_list.RemoveLast()->Emit(this, &new_trace);
+    RegExpNode* node = work_list.RemoveLast();
+    node->set_on_work_list(false);
+    if (!node->label()->is_bound()) node->Emit(this, &new_trace);
   }
   if (reg_exp_too_big_) return IrregexpRegExpTooBig(isolate_);
 
   Handle<HeapObject> code = macro_assembler_->GetCode(pattern);
   heap->IncreaseTotalRegexpCodeGenerated(code->Size());
   work_list_ = NULL;
 #ifdef ENABLE_DISASSEMBLER
   if (FLAG_print_code) {
     CodeTracer::Scope trace_scope(heap->isolate()->GetCodeTracer());
     OFStream os(trace_scope.file());
@@ skipping 255 matching lines @@
                          &registers_to_pop,
                          &registers_to_clear,
                          compiler->zone());
   if (cp_offset_ != 0) {
     assembler->AdvanceCurrentPosition(cp_offset_);
   }
 
   // Create a new trivial state and generate the node with that.
   Label undo;
   assembler->PushBacktrack(&undo);
-  Trace new_state;
-  successor->Emit(compiler, &new_state);
+  if (successor->KeepRecursing(compiler)) {
+    Trace new_state;
+    successor->Emit(compiler, &new_state);
+  } else {
+    compiler->AddWork(successor);
+    assembler->GoTo(successor->label());
+  }
 
   // On backtrack we need to restore state.
   assembler->Bind(&undo);
   RestoreAffectedRegisters(assembler,
                            max_register,
                            registers_to_pop,
                            registers_to_clear);
   if (backtrack() == NULL) {
     assembler->Backtrack();
   } else {
@@ skipping 820 matching lines @@
 
 RegExpNode::LimitResult RegExpNode::LimitVersions(RegExpCompiler* compiler,
                                                   Trace* trace) {
   // If we are generating a greedy loop then don't stop and don't reuse code.
   if (trace->stop_node() != NULL) {
     return CONTINUE;
   }
 
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   if (trace->is_trivial()) {
-    if (label_.is_bound()) {
-      // We are being asked to generate a generic version, but that's already
-      // been done so just go to it.
+    if (label_.is_bound() || on_work_list() || !KeepRecursing(compiler)) {
+      // If a generic version is already scheduled to be generated or we have
+      // recursed too deeply then just generate a jump to that code.
       macro_assembler->GoTo(&label_);
-      return DONE;
-    }
-    if (compiler->recursion_depth() >= RegExpCompiler::kMaxRecursion) {
-      // To avoid too deep recursion we push the node to the work queue and just
-      // generate a goto here.
+      // This will queue it up for generation of a generic version if it hasn't
+      // already been queued.
       compiler->AddWork(this);
-      macro_assembler->GoTo(&label_);
       return DONE;
     }
     // Generate generic version of the node and bind the label for later use.
     macro_assembler->Bind(&label_);
     return CONTINUE;
   }
 
   // We are being asked to make a non-generic version.  Keep track of how many
   // non-generic versions we generate so as not to overdo it.
   trace_count_++;
-  if (compiler->optimize() && trace_count_ < kMaxCopiesCodeGenerated &&
-      compiler->recursion_depth() <= RegExpCompiler::kMaxRecursion) {
+  if (KeepRecursing(compiler) && compiler->optimize() &&
+      trace_count_ < kMaxCopiesCodeGenerated) {
     return CONTINUE;
   }
 
   // If we get here code has been generated for this node too many times or
   // recursion is too deep.  Time to switch to a generic version.  The code for
   // generic versions above can handle deep recursion properly.
+  bool was_limiting = compiler->limiting_recursion();
+  compiler->set_limiting_recursion(true);
   trace->Flush(compiler, this);
+  compiler->set_limiting_recursion(was_limiting);
   return DONE;
 }
 
 
+bool RegExpNode::KeepRecursing(RegExpCompiler* compiler) {
+  return !compiler->limiting_recursion() &&
+         compiler->recursion_depth() <= RegExpCompiler::kMaxRecursion;
+}
+
+
 int ActionNode::EatsAtLeast(int still_to_find,
                             int budget,
                             bool not_at_start) {
   if (budget <= 0) return 0;
   if (action_type_ == POSITIVE_SUBMATCH_SUCCESS) return 0;  // Rewinds input!
   return on_success()->EatsAtLeast(still_to_find,
                                    budget - 1,
                                    not_at_start);
 }
 
@@ skipping 3758 matching lines @@
 RegExpEngine::CompilationResult RegExpEngine::Compile(
     Isolate* isolate, Zone* zone, RegExpCompileData* data, bool ignore_case,
     bool is_global, bool is_multiline, bool is_sticky, Handle<String> pattern,
     Handle<String> sample_subject, bool is_one_byte) {
   if ((data->capture_count + 1) * 2 - 1 > RegExpMacroAssembler::kMaxRegister) {
     return IrregexpRegExpTooBig(isolate);
   }
   RegExpCompiler compiler(isolate, zone, data->capture_count, ignore_case,
                           is_one_byte);
 
-  compiler.set_optimize(!TooMuchRegExpCode(pattern));
+  if (compiler.optimize()) compiler.set_optimize(!TooMuchRegExpCode(pattern));
 
   // Sample some characters from the middle of the string.
   static const int kSampleSize = 128;
 
   sample_subject = String::Flatten(sample_subject);
   int chars_sampled = 0;
   int half_way = (sample_subject->length() - kSampleSize) / 2;
   for (int i = Max(0, half_way);
        i < sample_subject->length() && chars_sampled < kSampleSize;
        i++, chars_sampled++) {
@@ skipping 122 matching lines @@
   Heap* heap = pattern->GetHeap();
   bool too_much = pattern->length() > RegExpImpl::kRegExpTooLargeToOptimize;
   if (heap->total_regexp_code_generated() > RegExpImpl::kRegExpCompiledLimit &&
       heap->isolate()->memory_allocator()->SizeExecutable() >
           RegExpImpl::kRegExpExecutableMemoryLimit) {
     too_much = true;
   }
   return too_much;
 }
 }}  // namespace v8::internal