Experimental: merge from bleeding_edge. Merge up to and including...

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 163 matching lines @@
 //     space.
 //   * The current state is virtualized.
 //     This is used to defer expensive operations until it is clear that they
 //     are needed and to generate code for a node more than once, allowing
 //     specialized an efficient versions of the code to be created. This is
 //     explained in the section below.
 //
 // Execution state virtualization.
 //
 //   Instead of emitting code, nodes that manipulate the state can record their
-//   manipulation in an object called the GenerationVariant.  The
-//   GenerationVariant object can record a current position offset, an
-//   optional backtrack code location on the top of the virtualized backtrack
-//   stack and some register changes.  When a node is to be emitted it can flush
-//   the GenerationVariant or update it.  Flushing the GenerationVariant
+//   manipulation in an object called the Trace.  The Trace object can record a
+//   current position offset, an optional backtrack code location on the top of
+//   the virtualized backtrack stack and some register changes.  When a node is
+//   to be emitted it can flush the Trace or update it.  Flushing the Trace
 //   will emit code to bring the actual state into line with the virtual state.
 //   Avoiding flushing the state can postpone some work (eg updates of capture
 //   registers).  Postponing work can save time when executing the regular
 //   expression since it may be found that the work never has to be done as a
 //   failure to match can occur.  In addition it is much faster to jump to a
 //   known backtrack code location than it is to pop an unknown backtrack
 //   location from the stack and jump there.
 //
-//   The virtual state found in the GenerationVariant affects code generation.
-//   For example the virtual state contains the difference between the actual
-//   current position and the virtual current position, and matching code needs
-//   to use this offset to attempt a match in the correct location of the input
-//   string.  Therefore code generated for a non-trivial GenerationVariant is
-//   specialized to that GenerationVariant.  The code generator therefore
-//   has the ability to generate code for each node several times.  In order to
-//   limit the size of the generated code there is an arbitrary limit on how
-//   many specialized sets of code may be generated for a given node.  If the
-//   limit is reached, the GenerationVariant is flushed and a generic version of
-//   the code for a node is emitted.  This is subsequently used for that node.
-//   The code emitted for non-generic GenerationVariants is not recorded in the
-//   node and so it cannot currently be reused in the event that code generation
-//   is requested for an identical GenerationVariant.
+//   The virtual state found in the Trace affects code generation.  For example
+//   the virtual state contains the difference between the actual current
+//   position and the virtual current position, and matching code needs to use
+//   this offset to attempt a match in the correct location of the input
+//   string.  Therefore code generated for a non-trivial trace is specialized
+//   to that trace.  The code generator therefore has the ability to generate
+//   code for each node several times.  In order to limit the size of the
+//   generated code there is an arbitrary limit on how many specialized sets of
+//   code may be generated for a given node.  If the limit is reached, the
+//   trace is flushed and a generic version of the code for a node is emitted.
+//   This is subsequently used for that node.  The code emitted for non-generic
+//   trace is not recorded in the node and so it cannot currently be reused in
+//   the event that code generation is requested for an identical trace.
 
 
 void RegExpTree::AppendToText(RegExpText* text) {
   UNREACHABLE();
 }
 
 
 void RegExpAtom::AppendToText(RegExpText* text) {
   text->AddElement(TextElement::Atom(this));
 }
@@ skipping 66 matching lines @@
   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_--; }
 
   inline bool ignore_case() { return ignore_case_; }
   inline bool ascii() { return ascii_; }
 
+  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 ascii_;
 };
 
@@ skipping 29 matching lines @@
 #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);
-  GenerationVariant generic_variant;
-  if (!start->Emit(this, &generic_variant)) {
+  Trace new_trace;
+  if (!start->Emit(this, &new_trace)) {
     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)) {
+    if (!work_list.RemoveLast()->Emit(this, &new_trace)) {
       return Handle<FixedArray>::null();
     }
   }
   Handle<FixedArray> array =
       Factory::NewFixedArray(RegExpImpl::kIrregexpDataLength);
   array->set(RegExpImpl::kIrregexpImplementationIndex,
              Smi::FromInt(macro_assembler_->Implementation()));
   array->set(RegExpImpl::kIrregexpNumberOfRegistersIndex,
              Smi::FromInt(next_register_));
   array->set(RegExpImpl::kIrregexpNumberOfCapturesIndex,
              Smi::FromInt(capture_count));
   Handle<Object> code = macro_assembler_->GetCode(pattern);
   array->set(RegExpImpl::kIrregexpCodeIndex, *code);
   work_list_ = NULL;
 #ifdef DEBUG
   if (FLAG_trace_regexp_assembler) {
     delete macro_assembler_;
   }
 #endif
   return array;
 }
 
+bool Trace::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) {
+
+bool Trace::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;
 }
 
 
-int GenerationVariant::FindAffectedRegisters(OutSet* affected_registers) {
-  int max_register = -1;
+bool Trace::GetStoredPosition(int reg, int* cp_offset) {
+  ASSERT_EQ(0, *cp_offset);
   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->Mentions(reg)) {
+      if (action->type() == ActionNode::STORE_POSITION) {
+        *cp_offset = static_cast<DeferredCapture*>(action)->cp_offset();
+        return true;
+      } else {
+        return false;
+      }
+    }
+  }
+  return false;
+}
+
+
+int Trace::FindAffectedRegisters(OutSet* affected_registers) {
+  int max_register = RegExpCompiler::kNoRegister;
+  for (DeferredAction* action = actions_;
+       action != NULL;
+       action = action->next()) {
+    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) {
-  for (int reg = 0; reg <= max_register; reg++) {
-    if (affected_registers.Get(reg)) assembler->PushRegister(reg);
+void Trace::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);
+    }
   }
 }
 
 
-void GenerationVariant::RestoreAffectedRegisters(
-    RegExpMacroAssembler* assembler,
-    int max_register,
-    OutSet& affected_registers) {
+void Trace::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);
   }
 }
 
 
-void GenerationVariant::PerformDeferredActions(RegExpMacroAssembler* assembler,
-                                               int max_register,
-                                               OutSet& affected_registers) {
+void Trace::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);
+            Trace::DeferredSetRegister* psr =
+                static_cast<Trace::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: {
-            GenerationVariant::DeferredCapture* pc =
-                static_cast<GenerationVariant::DeferredCapture*>(action);
-            if (store_position == -1) {
+            Trace::DeferredCapture* pc =
+                static_cast<Trace::DeferredCapture*>(action);
+            if (!clear && store_position == -1) {
               store_position = pc->cp_offset();
             }
             ASSERT(!absolute);
             ASSERT_EQ(value, 0);
             break;
           }
+          case ActionNode::CLEAR_CAPTURES: {
+            // Since we're scanning in reverse order, if we've already
+            // set the position we have to ignore historically earlier
+            // clearing operations.
+            if (store_position == -1)
+              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) {
+bool Trace::Flush(RegExpCompiler* compiler, RegExpNode* successor) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
 
   ASSERT(actions_ != NULL ||
          cp_offset_ != 0 ||
          backtrack() != NULL ||
          characters_preloaded_ != 0 ||
          quick_check_performed_.characters() != 0 ||
          bound_checked_up_to_ != 0);
 
   if (actions_ == NULL && backtrack() == NULL) {
     // Here we just have some deferred cp advances to fix and we are back to
     // a normal situation.  We may also have to forget some information gained
     // through a quick check that was already performed.
     if (cp_offset_ != 0) assembler->AdvanceCurrentPosition(cp_offset_);
     // Create a new trivial state and generate the node with that.
-    GenerationVariant new_state;
+    Trace new_state;
     return successor->Emit(compiler, &new_state);
   }
 
   // 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();
   }
   if (cp_offset_ != 0) {
     assembler->AdvanceCurrentPosition(cp_offset_);
   }
 
   // Create a new trivial state and generate the node with that.
   Label undo;
   assembler->PushBacktrack(&undo);
-  GenerationVariant new_state;
+  Trace 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);
   if (backtrack() == NULL) {
     assembler->Backtrack();
   } else {
     assembler->GoTo(backtrack());
   }
 
   return true;
 }
 
 
-void EndNode::EmitInfoChecks(RegExpMacroAssembler* assembler,
-                             GenerationVariant* variant) {
+void EndNode::EmitInfoChecks(RegExpMacroAssembler* assembler, Trace* trace) {
   if (info()->at_end) {
     Label succeed;
     // LoadCurrentCharacter will go to the label if we are at the end of the
     // input string.
     assembler->LoadCurrentCharacter(0, &succeed);
-    assembler->GoTo(variant->backtrack());
+    assembler->GoTo(trace->backtrack());
     assembler->Bind(&succeed);
   }
 }
 
 
-bool NegativeSubmatchSuccess::Emit(RegExpCompiler* compiler,
-                                   GenerationVariant* variant) {
-  if (!variant->is_trivial()) {
-    return variant->Flush(compiler, this);
+bool NegativeSubmatchSuccess::Emit(RegExpCompiler* compiler, Trace* trace) {
+  if (!trace->is_trivial()) {
+    return trace->Flush(compiler, this);
   }
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   if (!label()->is_bound()) {
     assembler->Bind(label());
   }
-  EmitInfoChecks(assembler, variant);
+  EmitInfoChecks(assembler, trace);
   assembler->ReadCurrentPositionFromRegister(current_position_register_);
   assembler->ReadStackPointerFromRegister(stack_pointer_register_);
   // Now that we have unwound the stack we find at the top of the stack the
   // backtrack that the BeginSubmatch node got.
   assembler->Backtrack();
   return true;
 }
 
 
-bool EndNode::Emit(RegExpCompiler* compiler, GenerationVariant* variant) {
-  if (!variant->is_trivial()) {
-    return variant->Flush(compiler, this);
+bool EndNode::Emit(RegExpCompiler* compiler, Trace* trace) {
+  if (!trace->is_trivial()) {
+    return trace->Flush(compiler, this);
   }
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   if (!label()->is_bound()) {
     assembler->Bind(label());
   }
   switch (action_) {
     case ACCEPT:
-      EmitInfoChecks(assembler, variant);
+      EmitInfoChecks(assembler, trace);
       assembler->Succeed();
       return true;
     case BACKTRACK:
       ASSERT(!info()->at_end);
-      assembler->GoTo(variant->backtrack());
+      assembler->GoTo(trace->backtrack());
       return true;
     case NEGATIVE_SUBMATCH_SUCCESS:
       // This case is handled in a different virtual method.
       UNREACHABLE();
   }
   UNIMPLEMENTED();
   return false;
 }
 
 
@@ skipping 21 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;
 }
 
 
 ActionNode* ActionNode::PositiveSubmatchSuccess(int stack_reg,
                                                 int position_reg,
                                                 RegExpNode* on_success) {
   ActionNode* result = new ActionNode(POSITIVE_SUBMATCH_SUCCESS, on_success);
   result->data_.u_submatch.stack_pointer_register = stack_reg;
   result->data_.u_submatch.current_position_register = position_reg;
   return result;
 }
 
 
+ActionNode* ActionNode::EmptyMatchCheck(int start_register,
+                                        int repetition_register,
+                                        int repetition_limit,
+                                        RegExpNode* on_success) {
+  ActionNode* result = new ActionNode(EMPTY_MATCH_CHECK, on_success);
+  result->data_.u_empty_match_check.start_register = start_register;
+  result->data_.u_empty_match_check.repetition_register = repetition_register;
+  result->data_.u_empty_match_check.repetition_limit = repetition_limit;
+  return result;
+}
+
+
 #define DEFINE_ACCEPT(Type)                                          \
   void Type##Node::Accept(NodeVisitor* visitor) {                    \
     visitor->Visit##Type(this);                                      \
   }
 FOR_EACH_NODE_TYPE(DEFINE_ACCEPT)
 #undef DEFINE_ACCEPT
 
 
 void LoopChoiceNode::Accept(NodeVisitor* visitor) {
   visitor->VisitLoopChoice(this);
 }
 
 
 // -------------------------------------------------------------------
 // Emit code.
 
 
 void ChoiceNode::GenerateGuard(RegExpMacroAssembler* macro_assembler,
                                Guard* guard,
-                               GenerationVariant* variant) {
+                               Trace* trace) {
   switch (guard->op()) {
     case Guard::LT:
-      ASSERT(!variant->mentions_reg(guard->reg()));
+      ASSERT(!trace->mentions_reg(guard->reg()));
       macro_assembler->IfRegisterGE(guard->reg(),
                                     guard->value(),
-                                    variant->backtrack());
+                                    trace->backtrack());
       break;
     case Guard::GEQ:
-      ASSERT(!variant->mentions_reg(guard->reg()));
+      ASSERT(!trace->mentions_reg(guard->reg()));
       macro_assembler->IfRegisterLT(guard->reg(),
                                     guard->value(),
-                                    variant->backtrack());
+                                    trace->backtrack());
       break;
   }
 }
 
 
 static unibrow::Mapping<unibrow::Ecma262UnCanonicalize> uncanonicalize;
 static unibrow::Mapping<unibrow::CanonicalizationRange> canonrange;
 
 
 // Only emits non-letters (things that don't have case).  Only used for case
@@ skipping 232 matching lines @@
   }
   macro_assembler->Bind(&success);
 }
 
 
 RegExpNode::~RegExpNode() {
 }
 
 
 RegExpNode::LimitResult RegExpNode::LimitVersions(RegExpCompiler* compiler,
-                                                  GenerationVariant* variant) {
+                                                  Trace* trace) {
   // TODO(erikcorry): Implement support.
   if (info_.follows_word_interest ||
       info_.follows_newline_interest ||
       info_.follows_start_interest) {
     return FAIL;
   }
 
   // If we are generating a greedy loop then don't stop and don't reuse code.
-  if (variant->stop_node() != NULL) {
+  if (trace->stop_node() != NULL) {
     return CONTINUE;
   }
 
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
-  if (variant->is_trivial()) {
+  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.
       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.
       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.
-  variants_generated_++;
-  if (variants_generated_ < kMaxVariantsGenerated &&
+  trace_count_++;
+  if (trace_count_ < kMaxCopiesCodeGenerated &&
       compiler->recursion_depth() <= RegExpCompiler::kMaxRecursion) {
     return CONTINUE;
   }
 
-  // If we get here there have been too many variants generated or recursion
-  // is too deep.  Time to switch to a generic version.  The code for
+  // 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 ok = variant->Flush(compiler, this);
+  bool ok = trace->Flush(compiler, this);
   return ok ? DONE : FAIL;
 }
 
 
 int ActionNode::EatsAtLeast(int recursion_depth) {
   if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
   if (type_ == POSITIVE_SUBMATCH_SUCCESS) return 0;  // Rewinds input!
   return on_success()->EatsAtLeast(recursion_depth + 1);
 }
 
@@ skipping 60 matching lines @@
     }
     mask_ |= (pos->mask & char_mask) << char_shift;
     value_ |= (pos->value & char_mask) << char_shift;
     char_shift += asc ? 8 : 16;
   }
   return found_useful_op;
 }
 
 
 bool RegExpNode::EmitQuickCheck(RegExpCompiler* compiler,
-                                GenerationVariant* variant,
+                                Trace* trace,
                                 bool preload_has_checked_bounds,
                                 Label* on_possible_success,
                                 QuickCheckDetails* details,
                                 bool fall_through_on_failure) {
   if (details->characters() == 0) return false;
   GetQuickCheckDetails(details, compiler, 0);
   if (!details->Rationalize(compiler->ascii())) return false;
   uint32_t mask = details->mask();
   uint32_t value = details->value();
 
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
 
-  if (variant->characters_preloaded() != details->characters()) {
-    assembler->LoadCurrentCharacter(variant->cp_offset(),
-                                    variant->backtrack(),
+  if (trace->characters_preloaded() != details->characters()) {
+    assembler->LoadCurrentCharacter(trace->cp_offset(),
+                                    trace->backtrack(),
                                     !preload_has_checked_bounds,
                                     details->characters());
   }
 
 
   bool need_mask = true;
 
   if (details->characters() == 1) {
     // If number of characters preloaded is 1 then we used a byte or 16 bit
     // load so the value is already masked down.
@@ skipping 16 matching lines @@
   }
 
   if (fall_through_on_failure) {
     if (need_mask) {
       assembler->CheckCharacterAfterAnd(value, mask, on_possible_success);
     } else {
       assembler->CheckCharacter(value, on_possible_success);
     }
   } else {
     if (need_mask) {
-      assembler->CheckNotCharacterAfterAnd(value, mask, variant->backtrack());
+      assembler->CheckNotCharacterAfterAnd(value, mask, trace->backtrack());
     } else {
-      assembler->CheckNotCharacter(value, variant->backtrack());
+      assembler->CheckNotCharacter(value, trace->backtrack());
     }
   }
   return true;
 }
 
 
 // Here is the meat of GetQuickCheckDetails (see also the comment on the
 // super-class in the .h file).
 //
 // We iterate along the text object, building up for each character a
@@ skipping 165 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:
+  explicit 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 25 matching lines @@
 // end-of-input when loading the putative 'r'.
 //
 // A slight complication involves the fact that the first character may already
 // be fetched into a register by the previous node.  In this case we want to
 // do the test for that character first.  We do this in separate passes.  The
 // 'preloaded' argument indicates that we are doing such a 'pass'.  If such a
 // pass has been performed then subsequent passes will have true in
 // first_element_checked to indicate that that character does not need to be
 // checked again.
 //
-// In addition to all this we are passed a GenerationVariant, which can
+// In addition to all this we are passed a Trace, which can
 // contain an AlternativeGeneration object.  In this AlternativeGeneration
 // object we can see details of any quick check that was already passed in
 // order to get to the code we are now generating.  The quick check can involve
 // loading characters, which means we do not need to recheck the bounds
 // up to the limit the quick check already checked.  In addition the quick
 // check can have involved a mask and compare operation which may simplify
 // or obviate the need for further checks at some character positions.
 void TextNode::TextEmitPass(RegExpCompiler* compiler,
                             TextEmitPassType pass,
                             bool preloaded,
-                            GenerationVariant* variant,
+                            Trace* trace,
                             bool first_element_checked,
                             int* checked_up_to) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
   bool ascii = compiler->ascii();
-  Label* backtrack = variant->backtrack();
-  QuickCheckDetails* quick_check = variant->quick_check_performed();
+  Label* backtrack = trace->backtrack();
+  QuickCheckDetails* quick_check = trace->quick_check_performed();
   int element_count = elms_->length();
   for (int i = preloaded ? 0 : element_count - 1; i >= 0; i--) {
     TextElement elm = elms_->at(i);
-    int cp_offset = variant->cp_offset() + elm.cp_offset;
+    int cp_offset = trace->cp_offset() + elm.cp_offset;
     if (elm.type == TextElement::ATOM) {
       if (pass == NON_ASCII_MATCH ||
           pass == CHARACTER_MATCH ||
           pass == CASE_CHARACTER_MATCH) {
         Vector<const uc16> quarks = elm.data.u_atom->data();
         for (int j = preloaded ? 0 : quarks.length() - 1; j >= 0; j--) {
           bool bound_checked = true;  // Most ops will check their bounds.
           if (first_element_checked && i == 0 && j == 0) continue;
           if (quick_check != NULL &&
               elm.cp_offset + j < quick_check->characters() &&
@@ skipping 76 matching lines @@
   }
 }
 
 
 // This generates the code to match a text node.  A text node can contain
 // straight character sequences (possibly to be matched in a case-independent
 // way) and character classes.  For efficiency we do not do this in a single
 // pass from left to right.  Instead we pass over the text node several times,
 // emitting code for some character positions every time.  See the comment on
 // TextEmitPass for details.
-bool TextNode::Emit(RegExpCompiler* compiler, GenerationVariant* variant) {
-  LimitResult limit_result = LimitVersions(compiler, variant);
+bool TextNode::Emit(RegExpCompiler* compiler, Trace* trace) {
+  LimitResult limit_result = LimitVersions(compiler, trace);
   if (limit_result == FAIL) return false;
   if (limit_result == DONE) return true;
   ASSERT(limit_result == CONTINUE);
 
   if (info()->follows_word_interest ||
       info()->follows_newline_interest ||
       info()->follows_start_interest) {
     return false;
   }
 
   if (info()->at_end) {
-    compiler->macro_assembler()->GoTo(variant->backtrack());
+    compiler->macro_assembler()->GoTo(trace->backtrack());
     return true;
   }
 
   if (compiler->ascii()) {
     int dummy = 0;
-    TextEmitPass(compiler, NON_ASCII_MATCH, false, variant, false, &dummy);
+    TextEmitPass(compiler, NON_ASCII_MATCH, false, trace, false, &dummy);
   }
 
   bool first_elt_done = false;
-  int bound_checked_to = variant->cp_offset() - 1;
-  bound_checked_to += variant->bound_checked_up_to();
+  int bound_checked_to = trace->cp_offset() - 1;
+  bound_checked_to += trace->bound_checked_up_to();
 
   // If a character is preloaded into the current character register then
   // check that now.
-  if (variant->characters_preloaded() == 1) {
+  if (trace->characters_preloaded() == 1) {
     TextEmitPass(compiler,
                  CHARACTER_MATCH,
                  true,
-                 variant,
+                 trace,
                  false,
                  &bound_checked_to);
     if (compiler->ignore_case()) {
       TextEmitPass(compiler,
                    CASE_CHARACTER_MATCH,
                    true,
-                   variant,
+                   trace,
                    false,
                    &bound_checked_to);
     }
     TextEmitPass(compiler,
                  CHARACTER_CLASS_MATCH,
                  true,
-                 variant,
+                 trace,
                  false,
                  &bound_checked_to);
     first_elt_done = true;
   }
 
   TextEmitPass(compiler,
                CHARACTER_MATCH,
                false,
-               variant,
+               trace,
                first_elt_done,
                &bound_checked_to);
   if (compiler->ignore_case()) {
     TextEmitPass(compiler,
                  CASE_CHARACTER_MATCH,
                  false,
-                 variant,
+                 trace,
                  first_elt_done,
                  &bound_checked_to);
   }
   TextEmitPass(compiler,
                CHARACTER_CLASS_MATCH,
                false,
-               variant,
+               trace,
                first_elt_done,
                &bound_checked_to);
 
-  GenerationVariant successor_variant(*variant);
-  successor_variant.AdvanceVariant(Length(), compiler->ascii());
+  Trace successor_trace(*trace);
+  successor_trace.AdvanceCurrentPositionInTrace(Length(), compiler->ascii());
   RecursionCheck rc(compiler);
-  return on_success()->Emit(compiler, &successor_variant);
+  return on_success()->Emit(compiler, &successor_trace);
 }
 
 
-void GenerationVariant::AdvanceVariant(int by, bool ascii) {
+void Trace::AdvanceCurrentPositionInTrace(int by, bool ascii) {
   ASSERT(by > 0);
   // We don't have an instruction for shifting the current character register
   // down or for using a shifted value for anything so lets just forget that
   // we preloaded any characters into it.
   characters_preloaded_ = 0;
   // Adjust the offsets of the quick check performed information.  This
   // information is used to find out what we already determined about the
   // characters by means of mask and compare.
   quick_check_performed_.Advance(by, ascii);
   cp_offset_ += by;
@@ skipping 66 matching lines @@
 }
 
 
 void LoopChoiceNode::AddContinueAlternative(GuardedAlternative alt) {
   ASSERT_EQ(continue_node_, NULL);
   AddAlternative(alt);
   continue_node_ = alt.node();
 }
 
 
-bool LoopChoiceNode::Emit(RegExpCompiler* compiler,
-                          GenerationVariant* variant) {
+bool LoopChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
-  if (variant->stop_node() == this) {
+  if (trace->stop_node() == this) {
     int text_length = GreedyLoopTextLength(&(alternatives_->at(0)));
     ASSERT(text_length != kNodeIsTooComplexForGreedyLoops);
     // Update the counter-based backtracking info on the stack.  This is an
     // optimization for greedy loops (see below).
-    ASSERT(variant->cp_offset() == text_length);
+    ASSERT(trace->cp_offset() == text_length);
     macro_assembler->AdvanceCurrentPosition(text_length);
-    macro_assembler->GoTo(variant->loop_label());
+    macro_assembler->GoTo(trace->loop_label());
     return true;
   }
-  ASSERT(variant->stop_node() == NULL);
-  if (!variant->is_trivial()) {
-    return variant->Flush(compiler, this);
+  ASSERT(trace->stop_node() == NULL);
+  if (!trace->is_trivial()) {
+    return trace->Flush(compiler, this);
   }
-  return ChoiceNode::Emit(compiler, variant);
+  return ChoiceNode::Emit(compiler, trace);
 }
 
 
 int ChoiceNode::CalculatePreloadCharacters(RegExpCompiler* compiler) {
   int preload_characters = EatsAtLeast(0);
 #ifdef CAN_READ_UNALIGNED
   bool ascii = compiler->ascii();
   if (ascii) {
     if (preload_characters > 4) preload_characters = 4;
     // We can't preload 3 characters because there is no machine instruction
@@ skipping 132 matching lines @@
  *        |   /          |
  *        |  R           |
  *        | /            |
  *   F    VL             |
  * <------U              |
  * back   |S             |
  *        \______________/
  */
 
 
-bool ChoiceNode::Emit(RegExpCompiler* compiler, GenerationVariant* variant) {
+bool ChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   int choice_count = alternatives_->length();
 #ifdef DEBUG
   for (int i = 0; i < choice_count - 1; i++) {
     GuardedAlternative alternative = alternatives_->at(i);
     ZoneList<Guard*>* guards = alternative.guards();
     int guard_count = (guards == NULL) ? 0 : guards->length();
     for (int j = 0; j < guard_count; j++) {
-      ASSERT(!variant->mentions_reg(guards->at(j)->reg()));
+      ASSERT(!trace->mentions_reg(guards->at(j)->reg()));
     }
   }
 #endif
 
-  LimitResult limit_result = LimitVersions(compiler, variant);
+  LimitResult limit_result = LimitVersions(compiler, trace);
   if (limit_result == DONE) return true;
   if (limit_result == FAIL) return false;
   ASSERT(limit_result == CONTINUE);
 
   RecursionCheck rc(compiler);
 
-  GenerationVariant* current_variant = variant;
+  Trace* current_trace = trace;
 
   int text_length = GreedyLoopTextLength(&(alternatives_->at(0)));
   bool greedy_loop = false;
   Label greedy_loop_label;
-  GenerationVariant counter_backtrack_variant;
-  counter_backtrack_variant.set_backtrack(&greedy_loop_label);
+  Trace counter_backtrack_trace;
+  counter_backtrack_trace.set_backtrack(&greedy_loop_label);
   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);
+    ASSERT(trace->stop_node() == NULL);
     macro_assembler->PushCurrentPosition();
-    current_variant = &counter_backtrack_variant;
+    current_trace = &counter_backtrack_trace;
     Label greedy_match_failed;
-    GenerationVariant greedy_match_variant;
-    greedy_match_variant.set_backtrack(&greedy_match_failed);
+    Trace greedy_match_trace;
+    greedy_match_trace.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);
+    greedy_match_trace.set_stop_node(this);
+    greedy_match_trace.set_loop_label(&loop_label);
     bool ok = alternatives_->at(0).node()->Emit(compiler,
-                                                &greedy_match_variant);
+                                                &greedy_match_trace);
     macro_assembler->Bind(&greedy_match_failed);
     if (!ok) {
       greedy_loop_label.Unuse();
       return false;
     }
   }
 
   Label second_choice;  // For use in greedy matches.
   macro_assembler->Bind(&second_choice);
 
   int first_normal_choice = greedy_loop ? 1 : 0;
 
   int preload_characters = CalculatePreloadCharacters(compiler);
   bool preload_is_current =
-      (current_variant->characters_preloaded() == preload_characters);
+      (current_trace->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 ?
+    Trace new_trace(*current_trace);
+    new_trace.set_characters_preloaded(preload_is_current ?
                                          preload_characters :
                                          0);
     if (preload_has_checked_bounds) {
-      new_variant.set_bound_checked_up_to(preload_characters);
+      new_trace.set_bound_checked_up_to(preload_characters);
     }
-    new_variant.quick_check_performed()->Clear();
+    new_trace.quick_check_performed()->Clear();
     alt_gen->expects_preload = preload_is_current;
     bool generate_full_check_inline = false;
     if (alternative.node()->EmitQuickCheck(compiler,
-                                           &new_variant,
+                                           &new_trace,
                                            preload_has_checked_bounds,
                                            &alt_gen->possible_success,
                                            &alt_gen->quick_check_details,
                                            i < choice_count - 1)) {
       // Quick check was generated for this choice.
       preload_is_current = true;
       preload_has_checked_bounds = true;
       // On the last choice in the ChoiceNode we generated the quick
       // check to fall through on possible success.  So now we need to
       // generate the full check inline.
       if (i == choice_count - 1) {
         macro_assembler->Bind(&alt_gen->possible_success);
-        new_variant.set_quick_check_performed(&alt_gen->quick_check_details);
-        new_variant.set_characters_preloaded(preload_characters);
-        new_variant.set_bound_checked_up_to(preload_characters);
+        new_trace.set_quick_check_performed(&alt_gen->quick_check_details);
+        new_trace.set_characters_preloaded(preload_characters);
+        new_trace.set_bound_checked_up_to(preload_characters);
         generate_full_check_inline = true;
       }
     } else {
       // No quick check was generated.  Put the full code here.
       // If this is not the first choice then there could be slow checks from
       // previous cases that go here when they fail.  There's no reason to
       // insist that they preload characters since the slow check we are about
       // to generate probably can't use it.
       if (i != first_normal_choice) {
         alt_gen->expects_preload = false;
-        new_variant.set_characters_preloaded(0);
+        new_trace.set_characters_preloaded(0);
       }
       if (i < choice_count - 1) {
-        new_variant.set_backtrack(&alt_gen->after);
+        new_trace.set_backtrack(&alt_gen->after);
       }
       generate_full_check_inline = true;
     }
     if (generate_full_check_inline) {
       for (int j = 0; j < guard_count; j++) {
-        GenerateGuard(macro_assembler, guards->at(j), &new_variant);
+        GenerateGuard(macro_assembler, guards->at(j), &new_trace);
       }
-      if (!alternative.node()->Emit(compiler, &new_variant)) {
+      if (!alternative.node()->Emit(compiler, &new_trace)) {
         greedy_loop_label.Unuse();
         return false;
       }
       preload_is_current = false;
     }
     macro_assembler->Bind(&alt_gen->after);
   }
   if (greedy_loop) {
     macro_assembler->Bind(&greedy_loop_label);
     // If we have unwound to the bottom then backtrack.
-    macro_assembler->CheckGreedyLoop(variant->backtrack());
+    macro_assembler->CheckGreedyLoop(trace->backtrack());
     // Otherwise try the second priority at an earlier position.
     macro_assembler->AdvanceCurrentPosition(-text_length);
     macro_assembler->GoTo(&second_choice);
   }
   // At this point we need to generate slow checks for the alternatives where
   // the quick check was inlined.  We can recognize these because the associated
   // label was bound.
   for (int i = first_normal_choice; i < choice_count - 1; i++) {
     AlternativeGeneration* alt_gen = alt_gens.at(i);
     if (!EmitOutOfLineContinuation(compiler,
-                                   current_variant,
+                                   current_trace,
                                    alternatives_->at(i),
                                    alt_gen,
                                    preload_characters,
                                    alt_gens.at(i + 1)->expects_preload)) {
       return false;
     }
   }
   return true;
 }
 
 
 bool ChoiceNode::EmitOutOfLineContinuation(RegExpCompiler* compiler,
-                                           GenerationVariant* variant,
+                                           Trace* trace,
                                            GuardedAlternative alternative,
                                            AlternativeGeneration* alt_gen,
                                            int preload_characters,
                                            bool next_expects_preload) {
   if (!alt_gen->possible_success.is_linked()) return true;
 
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   macro_assembler->Bind(&alt_gen->possible_success);
-  GenerationVariant out_of_line_variant(*variant);
-  out_of_line_variant.set_characters_preloaded(preload_characters);
-  out_of_line_variant.set_quick_check_performed(&alt_gen->quick_check_details);
+  Trace out_of_line_trace(*trace);
+  out_of_line_trace.set_characters_preloaded(preload_characters);
+  out_of_line_trace.set_quick_check_performed(&alt_gen->quick_check_details);
   ZoneList<Guard*>* guards = alternative.guards();
   int guard_count = (guards == NULL) ? 0 : guards->length();
   if (next_expects_preload) {
     Label reload_current_char;
-    out_of_line_variant.set_backtrack(&reload_current_char);
+    out_of_line_trace.set_backtrack(&reload_current_char);
     for (int j = 0; j < guard_count; j++) {
-      GenerateGuard(macro_assembler, guards->at(j), &out_of_line_variant);
+      GenerateGuard(macro_assembler, guards->at(j), &out_of_line_trace);
     }
-    bool ok = alternative.node()->Emit(compiler, &out_of_line_variant);
+    bool ok = alternative.node()->Emit(compiler, &out_of_line_trace);
     macro_assembler->Bind(&reload_current_char);
     // Reload the current character, since the next quick check expects that.
     // We don't need to check bounds here because we only get into this
     // code through a quick check which already did the checked load.
-    macro_assembler->LoadCurrentCharacter(variant->cp_offset(),
+    macro_assembler->LoadCurrentCharacter(trace->cp_offset(),
                                           NULL,
                                           false,
                                           preload_characters);
     macro_assembler->GoTo(&(alt_gen->after));
     return ok;
   } else {
-    out_of_line_variant.set_backtrack(&(alt_gen->after));
+    out_of_line_trace.set_backtrack(&(alt_gen->after));
     for (int j = 0; j < guard_count; j++) {
-      GenerateGuard(macro_assembler, guards->at(j), &out_of_line_variant);
+      GenerateGuard(macro_assembler, guards->at(j), &out_of_line_trace);
     }
-    return alternative.node()->Emit(compiler, &out_of_line_variant);
+    return alternative.node()->Emit(compiler, &out_of_line_trace);
   }
 }
 
 
-bool ActionNode::Emit(RegExpCompiler* compiler, GenerationVariant* variant) {
+bool ActionNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
-  LimitResult limit_result = LimitVersions(compiler, variant);
+  LimitResult limit_result = LimitVersions(compiler, trace);
   if (limit_result == DONE) return true;
   if (limit_result == FAIL) return false;
   ASSERT(limit_result == CONTINUE);
 
   RecursionCheck rc(compiler);
 
   switch (type_) {
     case STORE_POSITION: {
-      GenerationVariant::DeferredCapture
-          new_capture(data_.u_position_register.reg, variant);
-      GenerationVariant new_variant = *variant;
-      new_variant.add_action(&new_capture);
-      return on_success()->Emit(compiler, &new_variant);
+      Trace::DeferredCapture
+          new_capture(data_.u_position_register.reg, trace);
+      Trace new_trace = *trace;
+      new_trace.add_action(&new_capture);
+      return on_success()->Emit(compiler, &new_trace);
     }
     case INCREMENT_REGISTER: {
-      GenerationVariant::DeferredIncrementRegister
+      Trace::DeferredIncrementRegister
           new_increment(data_.u_increment_register.reg);
-      GenerationVariant new_variant = *variant;
-      new_variant.add_action(&new_increment);
-      return on_success()->Emit(compiler, &new_variant);
+      Trace new_trace = *trace;
+      new_trace.add_action(&new_increment);
+      return on_success()->Emit(compiler, &new_trace);
     }
     case SET_REGISTER: {
-      GenerationVariant::DeferredSetRegister
+      Trace::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);
+      Trace new_trace = *trace;
+      new_trace.add_action(&new_set);
+      return on_success()->Emit(compiler, &new_trace);
+    }
+    case CLEAR_CAPTURES: {
+      Trace::DeferredClearCaptures
+        new_capture(Interval(data_.u_clear_captures.range_from,
+                             data_.u_clear_captures.range_to));
+      Trace new_trace = *trace;
+      new_trace.add_action(&new_capture);
+      return on_success()->Emit(compiler, &new_trace);
     }
     case BEGIN_SUBMATCH:
-      if (!variant->is_trivial()) return variant->Flush(compiler, this);
+      if (!trace->is_trivial()) return trace->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);
+      return on_success()->Emit(compiler, trace);
+    case EMPTY_MATCH_CHECK: {
+      int start_pos_reg = data_.u_empty_match_check.start_register;
+      int stored_pos = 0;
+      int rep_reg = data_.u_empty_match_check.repetition_register;
+      bool has_minimum = (rep_reg != RegExpCompiler::kNoRegister);
+      bool know_dist = trace->GetStoredPosition(start_pos_reg, &stored_pos);
+      if (know_dist && !has_minimum && stored_pos == trace->cp_offset()) {
+        // If we know we haven't advanced and there is no minimum we
+        // can just backtrack immediately.
+        assembler->GoTo(trace->backtrack());
+        return true;
+      } else if (know_dist && stored_pos < trace->cp_offset()) {
+        // If we know we've advanced we can generate the continuation
+        // immediately.
+        return on_success()->Emit(compiler, trace);
+      }
+      if (!trace->is_trivial()) return trace->Flush(compiler, this);
+      Label skip_empty_check;
+      // If we have a minimum number of repetitions we check the current
+      // number first and skip the empty check if it's not enough.
+      if (has_minimum) {
+        int limit = data_.u_empty_match_check.repetition_limit;
+        assembler->IfRegisterLT(rep_reg, limit, &skip_empty_check);
+      }
+      // If the match is empty we bail out, otherwise we fall through
+      // to the on-success continuation.
+      assembler->IfRegisterEqPos(data_.u_empty_match_check.start_register,
+                                 trace->backtrack());
+      assembler->Bind(&skip_empty_check);
+      return on_success()->Emit(compiler, trace);
+    }
     case POSITIVE_SUBMATCH_SUCCESS:
-      if (!variant->is_trivial()) return variant->Flush(compiler, this);
+      if (!trace->is_trivial()) return trace->Flush(compiler, this);
       // TODO(erikcorry): Implement support.
       if (info()->follows_word_interest ||
           info()->follows_newline_interest ||
           info()->follows_start_interest) {
         return false;
       }
       if (info()->at_end) {
         Label at_end;
         // Load current character jumps to the label if we are beyond the string
         // end.
         assembler->LoadCurrentCharacter(0, &at_end);
-        assembler->GoTo(variant->backtrack());
+        assembler->GoTo(trace->backtrack());
         assembler->Bind(&at_end);
       }
       assembler->ReadCurrentPositionFromRegister(
           data_.u_submatch.current_position_register);
       assembler->ReadStackPointerFromRegister(
           data_.u_submatch.stack_pointer_register);
-      return on_success()->Emit(compiler, variant);
+      return on_success()->Emit(compiler, trace);
     default:
       UNREACHABLE();
       return false;
   }
 }
 
 
-bool BackReferenceNode::Emit(RegExpCompiler* compiler,
-                             GenerationVariant* variant) {
+bool BackReferenceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
-  if (!variant->is_trivial()) {
-    return variant->Flush(compiler, this);
+  if (!trace->is_trivial()) {
+    return trace->Flush(compiler, this);
   }
 
-  LimitResult limit_result = LimitVersions(compiler, variant);
+  LimitResult limit_result = LimitVersions(compiler, trace);
   if (limit_result == DONE) return true;
   if (limit_result == FAIL) return false;
   ASSERT(limit_result == CONTINUE);
 
   RecursionCheck rc(compiler);
 
   ASSERT_EQ(start_reg_ + 1, end_reg_);
   if (info()->at_end) {
     // If we are constrained to match at the end of the input then succeed
     // iff the back reference is empty.
     assembler->CheckNotRegistersEqual(start_reg_,
                                       end_reg_,
-                                      variant->backtrack());
+                                      trace->backtrack());
   } else {
     if (compiler->ignore_case()) {
       assembler->CheckNotBackReferenceIgnoreCase(start_reg_,
-                                                 variant->backtrack());
+                                                 trace->backtrack());
     } else {
-      assembler->CheckNotBackReference(start_reg_, variant->backtrack());
+      assembler->CheckNotBackReference(start_reg_, trace->backtrack());
     }
   }
-  return on_success()->Emit(compiler, variant);
+  return on_success()->Emit(compiler, trace);
 }
 
 
 // -------------------------------------------------------------------
 // Dot/dotty output
 
 
 #ifdef DEBUG
 
 
@@ skipping 241 matching lines @@
       stream()->Add("label=\"$%i:=$pos\", shape=octagon",
                     that->data_.u_position_register.reg);
       break;
     case ActionNode::BEGIN_SUBMATCH:
       stream()->Add("label=\"$%i:=$pos,begin\", shape=septagon",
                     that->data_.u_submatch.current_position_register);
       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 205 matching lines @@
   // where max_match is zero the parser has removed the quantifier if min was
   // > 0 and removed the atom if min was 0.  See AddQuantifierToAtom.
 
   // 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.
-  if (body->min_match() > 0) {
+  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 if (!needs_capture_clearing) {
+    // 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 16 matching lines @@
                                                                       answer)));
         }
         answer = alternation;
       }
       return answer;
     }
   }
   bool has_min = min > 0;
   bool has_max = max < RegExpTree::kInfinity;
   bool needs_counter = has_min || has_max;
-  int reg_ctr = needs_counter ? compiler->AllocateRegister() : -1;
+  int reg_ctr = needs_counter
+      ? compiler->AllocateRegister()
+      : RegExpCompiler::kNoRegister;
   LoopChoiceNode* center = new LoopChoiceNode(body->min_match() == 0);
   RegExpNode* loop_return = needs_counter
       ? static_cast<RegExpNode*>(ActionNode::IncrementRegister(reg_ctr, center))
       : static_cast<RegExpNode*>(center);
+  if (body_can_be_empty) {
+    // If the body can be empty we need to check if it was and then
+    // backtrack.
+    loop_return = ActionNode::EmptyMatchCheck(body_start_reg,
+                                              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