Capture register clearing on loop iteration

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 1286 matching lines @@
   array->set(RegExpImpl::kIrregexpCodeIndex, *code);
   work_list_ = NULL;
 #ifdef DEBUG
   if (FLAG_trace_regexp_assembler) {
     delete macro_assembler_;
   }
 #endif
   return array;
 }
 
+bool GenerationVariant::DeferredAction::Mentions(int that) {
+  if (type() == ActionNode::CLEAR_CAPTURES) {
+    Interval range = static_cast<DeferredClearCaptures*>(this)->range();
+    return range.Contains(that);
+  } else {
+    return reg() == that;
+  }
+}
+
 
 bool GenerationVariant::mentions_reg(int reg) {
   for (DeferredAction* action = actions_;
        action != NULL;
        action = action->next()) {
-    if (reg == action->reg()) return true;
+    if (action->Mentions(reg))
+      return true;
   }
   return false;
 }
 
 
 bool GenerationVariant::GetStoredPosition(int reg, int* cp_offset) {
   ASSERT_EQ(0, *cp_offset);
   for (DeferredAction* action = actions_;
        action != NULL;
        action = action->next()) {
-    if (reg == action->reg()) {
+    if (action->Mentions(reg)) {
       if (action->type() == ActionNode::STORE_POSITION) {
         *cp_offset = static_cast<DeferredCapture*>(action)->cp_offset();
         return true;
       } else {
         return false;
       }
     }
   }
   return false;
 }
 
 
 int GenerationVariant::FindAffectedRegisters(OutSet* affected_registers) {
   int max_register = RegExpCompiler::kNoRegister;
   for (DeferredAction* action = actions_;
        action != NULL;
        action = action->next()) {
-    affected_registers->Set(action->reg());
-    if (action->reg() > max_register) max_register = action->reg();
+    if (action->type() == ActionNode::CLEAR_CAPTURES) {
+      Interval range = static_cast<DeferredClearCaptures*>(action)->range();
+      for (int i = range.from(); i < range.to(); i++)
+        affected_registers->Set(i);
+      if (range.to() > max_register) max_register = range.to();
+    } else {
+      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) {
   // Stay safe and check every half times the limit.
   // (Round up in case the limit is 1).
   int push_limit = (assembler->stack_limit_slack() + 1) / 2;
   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);

[Erik Corry, 2009/01/14 09:24:31]

It's a waste to push...

[Christian Plesner Hansen, 2009/01/14 11:31:35]

I'd like to defer that optimization.

     }
   }
 }
 
 
 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);

[Erik Corry, 2009/01/14 09:24:31]

... and pop registers if they are just affected by a WritePosition.  We could
just clear them instead of popping them.

[Erik Corry, 2009/01/14 09:30:13]

In fact for register 0 there's no need to clear it either.  Either it will be
overwritten later or the regexp doesn't match in which case it doesn't matter
what is in it.

   }
 }
 
 
 void GenerationVariant::PerformDeferredActions(RegExpMacroAssembler* assembler,
                                                int max_register,
                                                OutSet& affected_registers) {
   for (int reg = 0; reg <= max_register; reg++) {
     if (!affected_registers.Get(reg)) {
       continue;
     }
     int value = 0;
     bool absolute = false;
+    bool clear = false;
     int store_position = -1;
     // This is a little tricky because we are scanning the actions in reverse
     // historical order (newest first).
     for (DeferredAction* action = actions_;
          action != NULL;
          action = action->next()) {
-      if (action->reg() == reg) {
+      if (action->Mentions(reg)) {
         switch (action->type()) {
           case ActionNode::SET_REGISTER: {
             GenerationVariant::DeferredSetRegister* psr =
                 static_cast<GenerationVariant::DeferredSetRegister*>(action);
             value += psr->value();
             absolute = true;
             ASSERT_EQ(store_position, -1);
+            ASSERT(!clear);
             break;
           }
           case ActionNode::INCREMENT_REGISTER:
             if (!absolute) {
               value++;
             }
             ASSERT_EQ(store_position, -1);
+            ASSERT(!clear);
             break;
           case ActionNode::STORE_POSITION: {

[Erik Corry, 2009/01/14 09:24:31]

We should be ignoring a store position that we find after we found a clear...

[Christian Plesner Hansen, 2009/01/14 11:31:35]

Fixed

             GenerationVariant::DeferredCapture* pc =
                 static_cast<GenerationVariant::DeferredCapture*>(action);
             if (store_position == -1) {
               store_position = pc->cp_offset();
             }
             ASSERT(!absolute);
             ASSERT_EQ(value, 0);
             break;
           }
+          case ActionNode::CLEAR_CAPTURES: {

[Erik Corry, 2009/01/14 09:24:31]

...and we should be ignoring a clear that we find after a store position.

[Christian Plesner Hansen, 2009/01/14 11:31:35]

Fixed

+            clear = true;
+            ASSERT(!absolute);
+            ASSERT_EQ(value, 0);
+            break;
+          }
           default:
             UNREACHABLE();
             break;
         }
       }
     }
     if (store_position != -1) {
       assembler->WriteCurrentPositionToRegister(reg, store_position);
-    } else {
-      if (absolute) {
-        assembler->SetRegister(reg, value);
-      } else {
-        if (value != 0) {
-          assembler->AdvanceRegister(reg, value);
-        }
-      }
+    } else if (clear) {
+      assembler->ClearRegister(reg);
+    } else if (absolute) {
+      assembler->SetRegister(reg, value);
+    } else if (value != 0) {
+      assembler->AdvanceRegister(reg, value);
     }
   }
 }
 
 
 // This is called as we come into a loop choice node and some other tricky
 // nodes.  It normalises the state of the code generator to ensure we can
 // generate generic code.
 bool GenerationVariant::Flush(RegExpCompiler* compiler, RegExpNode* successor) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
@@ skipping 135 matching lines @@
 }
 
 
 ActionNode* ActionNode::StorePosition(int reg, RegExpNode* on_success) {
   ActionNode* result = new ActionNode(STORE_POSITION, on_success);
   result->data_.u_position_register.reg = reg;
   return result;
 }
 
 
+ActionNode* ActionNode::ClearCaptures(Interval range,
+                                      RegExpNode* on_success) {
+  ActionNode* result = new ActionNode(CLEAR_CAPTURES, on_success);
+  result->data_.u_clear_captures.range_from = range.from();
+  result->data_.u_clear_captures.range_to = range.to();
+  return result;
+}
+
+
 ActionNode* ActionNode::BeginSubmatch(int stack_reg,
                                       int position_reg,
                                       RegExpNode* on_success) {
   ActionNode* result = new ActionNode(BEGIN_SUBMATCH, on_success);
   result->data_.u_submatch.stack_pointer_register = stack_reg;
   result->data_.u_submatch.current_position_register = position_reg;
   return result;
 }
 
 
@@ skipping 661 matching lines @@
     pos->mask &= other_pos->mask;
     pos->value &= pos->mask;
     other_pos->value &= pos->mask;
     uc16 differing_bits = (pos->value ^ other_pos->value);
     pos->mask &= ~differing_bits;
     pos->value &= pos->mask;
   }
 }
 
 
+class VisitMarker {
+ public:
+  VisitMarker(NodeInfo* info) : info_(info) {
+    ASSERT(!info->visited);
+    info->visited = true;
+  }
+  ~VisitMarker() {
+    info_->visited = false;
+  }
+ private:
+  NodeInfo* info_;
+};
+
+
 void LoopChoiceNode::GetQuickCheckDetails(QuickCheckDetails* details,
                                           RegExpCompiler* compiler,
                                           int characters_filled_in) {
-  if (body_can_be_zero_length_) return;
+  if (body_can_be_zero_length_ || info()->visited) return;
+  VisitMarker marker(info());
   return ChoiceNode::GetQuickCheckDetails(details,
                                           compiler,
                                           characters_filled_in);
 }
 
 
 void ChoiceNode::GetQuickCheckDetails(QuickCheckDetails* details,
                                       RegExpCompiler* compiler,
                                       int characters_filled_in) {
   int choice_count = alternatives_->length();
@@ skipping 552 matching lines @@
   bool preload_is_current =
       (current_variant->characters_preloaded() == preload_characters);
   bool preload_has_checked_bounds = preload_is_current;
 
   AlternativeGenerationList alt_gens(choice_count);
 
   // For now we just call all choices one after the other.  The idea ultimately
   // is to use the Dispatch table to try only the relevant ones.
   for (int i = first_normal_choice; i < choice_count; i++) {
     GuardedAlternative alternative = alternatives_->at(i);
-    AlternativeGeneration* alt_gen(alt_gens.at(i));
+    AlternativeGeneration* alt_gen = alt_gens.at(i);
     alt_gen->quick_check_details.set_characters(preload_characters);
     ZoneList<Guard*>* guards = alternative.guards();
     int guard_count = (guards == NULL) ? 0 : guards->length();
     GenerationVariant new_variant(*current_variant);
     new_variant.set_characters_preloaded(preload_is_current ?
                                          preload_characters :
                                          0);
     if (preload_has_checked_bounds) {
       new_variant.set_bound_checked_up_to(preload_characters);
     }
@@ skipping 138 matching lines @@
       new_variant.add_action(&new_increment);
       return on_success()->Emit(compiler, &new_variant);
     }
     case SET_REGISTER: {
       GenerationVariant::DeferredSetRegister
           new_set(data_.u_store_register.reg, data_.u_store_register.value);
       GenerationVariant new_variant = *variant;
       new_variant.add_action(&new_set);
       return on_success()->Emit(compiler, &new_variant);
     }
+    case CLEAR_CAPTURES: {
+      GenerationVariant::DeferredClearCaptures
+        new_capture(Interval(data_.u_clear_captures.range_from,
+                             data_.u_clear_captures.range_to));
+      GenerationVariant new_variant = *variant;
+      new_variant.add_action(&new_capture);
+      return on_success()->Emit(compiler, &new_variant);
+    }
     case BEGIN_SUBMATCH:
       if (!variant->is_trivial()) return variant->Flush(compiler, this);
       assembler->WriteCurrentPositionToRegister(
           data_.u_submatch.current_position_register, 0);
       assembler->WriteStackPointerToRegister(
           data_.u_submatch.stack_pointer_register);
       return on_success()->Emit(compiler, variant);
     case EMPTY_MATCH_CHECK: {
       int start_pos_reg = data_.u_empty_match_check.start_register;
       int stored_pos = 0;
@@ skipping 343 matching lines @@
       break;
     case ActionNode::POSITIVE_SUBMATCH_SUCCESS:
       stream()->Add("label=\"escape\", shape=septagon");
       break;
     case ActionNode::EMPTY_MATCH_CHECK:
       stream()->Add("label=\"$%i=$pos?,$%i<%i?\", shape=septagon",
                     that->data_.u_empty_match_check.start_register,
                     that->data_.u_empty_match_check.repetition_register,
                     that->data_.u_empty_match_check.repetition_limit);
       break;
+    case ActionNode::CLEAR_CAPTURES: {
+      stream()->Add("label=\"clear $%i to $%i\", shape=septagon",
+                    that->data_.u_clear_captures.range_from,
+                    that->data_.u_clear_captures.range_to);
+      break;
+    }
   }
   stream()->Add("];\n");
   PrintAttributes(that);
   RegExpNode* successor = that->on_success();
   stream()->Add("  n%p -> n%p;\n", that, successor);
   Visit(successor);
 }
 
 
 class DispatchTableDumper {
@@ skipping 207 matching lines @@
 
   // If we know that we cannot match zero length then things are a little
   // simpler since we don't need to make the special zero length match check
   // from step 2.1.  If the min and max are small we can unroll a little in
   // this case.
   static const int kMaxUnrolledMinMatches = 3;  // Unroll (foo)+ and (foo){3,}
   static const int kMaxUnrolledMaxMatches = 3;  // Unroll (foo)? and (foo){x,3}
   if (max == 0) return on_success;  // This can happen due to recursion.
   bool body_can_be_empty = (body->min_match() == 0);
   int body_start_reg = RegExpCompiler::kNoRegister;
+  Interval capture_registers = body->CaptureRegisters();
+  bool needs_capture_clearing = !capture_registers.is_empty();
   if (body_can_be_empty) {
     body_start_reg = compiler->AllocateRegister();
-  } else {
+  } else if (!needs_capture_clearing) {

[Erik Corry, 2009/01/14 09:24:31]

Surely it's OK to unroll and no need to clear captures if max is 1?

+    // Only unroll if there are no captures and the body can't be
+    // empty.
     if (min > 0 && min <= kMaxUnrolledMinMatches) {
       int new_max = (max == kInfinity) ? max : max - min;
       // Recurse once to get the loop or optional matches after the fixed ones.
       RegExpNode* answer =
           ToNode(0, new_max, is_greedy, body, compiler, on_success);
       // Unroll the forced matches from 0 to min.  This can cause chains of
       // TextNodes (which the parser does not generate).  These should be
       // combined if it turns out they hinder good code generation.
       for (int i = 0; i < min; i++) {
         answer = body->ToNode(compiler, answer);
@@ skipping 37 matching lines @@
                                               reg_ctr,
                                               min,
                                               loop_return);
   }
   RegExpNode* body_node = body->ToNode(compiler, loop_return);
   if (body_can_be_empty) {
     // If the body can be empty we need to store the start position
     // so we can bail out if it was empty.
     body_node = ActionNode::StorePosition(body_start_reg, body_node);
   }
+  if (needs_capture_clearing) {
+    // Before entering the body of this loop we need to clear captures.
+    body_node = ActionNode::ClearCaptures(capture_registers, body_node);
+  }
   GuardedAlternative body_alt(body_node);
   if (has_max) {
     Guard* body_guard = new Guard(reg_ctr, Guard::LT, max);
     body_alt.AddGuard(body_guard);
   }
   GuardedAlternative rest_alt(on_success);
   if (has_min) {
     Guard* rest_guard = new Guard(reg_ctr, Guard::GEQ, min);
     rest_alt.AddGuard(rest_guard);
   }
@@ skipping 820 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal