Clean up regexp code gen a little

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 2419 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,
+                                Trace* bounds_check_trace,
                                 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, trace->at_start() == Trace::FALSE_VALUE);
   if (details->cannot_match()) return false;
   if (!details->Rationalize(compiler->one_byte())) return false;
   DCHECK(details->characters() == 1 ||
          compiler->macro_assembler()->CanReadUnaligned());
   uint32_t mask = details->mask();
   uint32_t value = details->value();
 
   RegExpMacroAssembler* assembler = compiler->macro_assembler();
 
   if (trace->characters_preloaded() != details->characters()) {
+    DCHECK(trace->cp_offset() == bounds_check_trace->cp_offset());
+    // We are attempting to preload the minimum number of characters
+    // any choice would eat, so if the bounds check fails, then none of the
+    // choices can succeed, so we can just immediately backtrack, rather
+    // than go to the next choice.
     assembler->LoadCurrentCharacter(trace->cp_offset(),
-                                    trace->backtrack(),
+                                    bounds_check_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 1378 matching lines @@
  *             |
  *             R
  *             |
  * backtrack   V
  * <----------Q4
  *   \    F    |
  *    \        |S
  *     \   F   V
  *      \-----S4
  *
- * For greedy loops we reverse our expectation and expect to match rather
- * than fail. Therefore we want the loop code to look like this (U is the
- * unwind code that steps back in the greedy loop).  The following alternatives
- * look the same as above.
+ * For greedy loops we push the current position, then generate the code that
+ * eats the input specially in EmitGreedyLoop.  The other choice (the
+ * continuation) is generated by the normal code in EmitChoices, and steps back
+ * in the input to the starting position when it fails to match.  The loop code
+ * looks like this (U is the unwind code that steps back in the greedy loop).
+ *
  *              _____
  *             /     \
  *             V     |
  * ----------> S1    |
  *            /|     |
  *           / |S    |
  *         F/  \_____/
  *         /
- *        |<-----------
- *        |            \
- *        V             \
- *        Q2 ---> S2     \
- *        |  S   /       |
- *       F|     /        |
- *        |   F/         |
- *        |   /          |
- *        |  R           |
- *        | /            |
- *   F    VL             |
- * <------U              |
- * back   |S             |
- *        \______________/
+ *        |<-----
+ *        |      \
+ *        V       |S
+ *        Q2 ---> U----->backtrack
+ *        |  F   /
+ *       S|     /
+ *        V  F /
+ *        S2--/
  */
 
 GreedyLoopState::GreedyLoopState(bool not_at_start) {
   counter_backtrack_trace_.set_backtrack(&label_);
   if (not_at_start) counter_backtrack_trace_.set_at_start(false);
 }
 
 
 void ChoiceNode::AssertGuardsMentionRegisters(Trace* trace) {
 #ifdef DEBUG
@@ skipping 65 matching lines @@
     // match the traces produced pre-cleanup.
     Label second_choice;
     compiler->macro_assembler()->Bind(&second_choice);
 
     preload.eats_at_least_ = EmitOptimizedUnanchoredSearch(compiler, trace);
 
     EmitChoices(compiler,
                 &alt_gens,
                 0,
                 trace,
-                false,  // Not greedy loop.
                 &preload);
   }
 
   // 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.
   int new_flush_budget = trace->flush_budget() / choice_count;
-  for (int i = 0; i < choice_count - 1; i++) {
+  for (int i = 0; i < choice_count; i++) {
     AlternativeGeneration* alt_gen = alt_gens.at(i);
     Trace new_trace(*trace);
     // If there are actions to be flushed we have to limit how many times
     // they are flushed.  Take the budget of the parent trace and distribute
     // it fairly amongst the children.
     if (new_trace.actions() != NULL) {
       new_trace.set_flush_budget(new_flush_budget);
     }
+    bool next_expects_preload =
+        i == choice_count - 1 ? false : alt_gens.at(i + 1)->expects_preload;
     EmitOutOfLineContinuation(compiler,
                               &new_trace,
                               alternatives_->at(i),
                               alt_gen,
                               preload.preload_characters_,
-                              alt_gens.at(i + 1)->expects_preload);
+                              next_expects_preload);
   }
 }
 
 
 Trace* ChoiceNode::EmitGreedyLoop(RegExpCompiler* compiler,
                                   Trace* trace,
                                   AlternativeGenerationList* alt_gens,
                                   PreloadState* preload,
                                   GreedyLoopState* greedy_loop_state,
                                   int text_length) {
@@ skipping 20 matching lines @@
 
   Label second_choice;  // For use in greedy matches.
   macro_assembler->Bind(&second_choice);
 
   Trace* new_trace = greedy_loop_state->counter_backtrack_trace();
 
   EmitChoices(compiler,
               alt_gens,
               1,
               new_trace,
-              true,  // Is greedy loop.
               preload);
 
   macro_assembler->Bind(greedy_loop_state->label());
   // If we have unwound to the bottom then 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);
   return new_trace;
 }
@@ skipping 46 matching lines @@
     bm->EmitSkipInstructions(macro_assembler);
   }
   return eats_at_least;
 }
 
 
 void ChoiceNode::EmitChoices(RegExpCompiler* compiler,
                              AlternativeGenerationList* alt_gens,
                              int first_choice,
                              Trace* trace,
-                             bool is_greedy_loop,
                              PreloadState* preload) {
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   SetUpPreLoad(compiler, trace, preload);
 
   // 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.
   int choice_count = alternatives_->length();
 
   int new_flush_budget = trace->flush_budget() / choice_count;
 
   for (int i = first_choice; i < choice_count; i++) {
     bool is_last = i == choice_count - 1;
+    bool fall_through_on_failure = !is_last;
     GuardedAlternative alternative = alternatives_->at(i);
     AlternativeGeneration* alt_gen = alt_gens->at(i);
     alt_gen->quick_check_details.set_characters(preload->preload_characters_);
     ZoneList<Guard*>* guards = alternative.guards();
     int guard_count = (guards == NULL) ? 0 : guards->length();
     Trace new_trace(*trace);
     new_trace.set_characters_preloaded(preload->preload_is_current_ ?
                                          preload->preload_characters_ :
                                          0);
     if (preload->preload_has_checked_bounds_) {
       new_trace.set_bound_checked_up_to(preload->preload_characters_);
     }
     new_trace.quick_check_performed()->Clear();
     if (not_at_start_) new_trace.set_at_start(Trace::FALSE_VALUE);
+    if (!is_last) {
+      new_trace.set_backtrack(&alt_gen->after);
+    }
     alt_gen->expects_preload = preload->preload_is_current_;
     bool generate_full_check_inline = false;
     if (FLAG_regexp_optimization &&
         try_to_emit_quick_check_for_alternative(i == 0) &&
         alternative.node()->EmitQuickCheck(compiler,
+                                           trace,
                                            &new_trace,
                                            preload->preload_has_checked_bounds_,
                                            &alt_gen->possible_success,
                                            &alt_gen->quick_check_details,
-                                           !is_last)) {
+                                           fall_through_on_failure)) {
       // Quick check was generated for this choice.
       preload->preload_is_current_ = true;
       preload->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 (is_last) {
+      // If we generated the quick check to fall through on possible success,
+      // we now need to generate the full check inline.
+      if (!fall_through_on_failure) {
         macro_assembler->Bind(&alt_gen->possible_success);
         new_trace.set_quick_check_performed(&alt_gen->quick_check_details);
         new_trace.set_characters_preloaded(preload->preload_characters_);
         new_trace.set_bound_checked_up_to(preload->preload_characters_);
         generate_full_check_inline = true;
       }
     } else if (alt_gen->quick_check_details.cannot_match()) {
-      if (is_last && !is_greedy_loop) {
+      if (!fall_through_on_failure) {
         macro_assembler->GoTo(trace->backtrack());
-      }  // Else just fall through to the next test.
+      }
       continue;
     } 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_choice) {
         alt_gen->expects_preload = false;
         new_trace.InvalidateCurrentCharacter();
       }
-      if (!is_last) {
-        new_trace.set_backtrack(&alt_gen->after);
-      }
       generate_full_check_inline = true;
     }
     if (generate_full_check_inline) {
       if (new_trace.actions() != NULL) {
         new_trace.set_flush_budget(new_flush_budget);
       }
       for (int j = 0; j < guard_count; j++) {
         GenerateGuard(macro_assembler, guards->at(j), &new_trace);
       }
       alternative.node()->Emit(compiler, &new_trace);
@@ skipping 1974 matching lines @@
   }
 
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal