Some irregexp optimizations around keeping track of when the current characte...

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 1405 matching lines @@
 // 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();
 
   ASSERT(actions_ != NULL ||
          cp_offset_ != 0 ||
          backtrack() != NULL ||
          characters_preloaded_ != 0 ||
-         quick_check_performed_.characters() != 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;
     return successor->Emit(compiler, &new_state);
   }
@@ skipping 203 matching lines @@
       macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check);
       checked = check;
     }
     macro_assembler->CheckNotCharacter(c, on_failure);
   }
   return checked;
 }
 
 
 static bool ShortCutEmitCharacterPair(RegExpMacroAssembler* macro_assembler,
+                                      bool ascii,
                                       uc16 c1,
                                       uc16 c2,
                                       Label* on_failure) {
+  uc16 char_mask;
+  if (ascii) {
+    char_mask = String::kMaxAsciiCharCode;
+  } else {
+    char_mask = String::kMaxUC16CharCode;
+  }
   uc16 exor = c1 ^ c2;
   // Check whether exor has only one bit set.
   if (((exor - 1) & exor) == 0) {
     // If c1 and c2 differ only by one bit.
     // Ecma262UnCanonicalize always gives the highest number last.
     ASSERT(c2 > c1);
-    uc16 mask = String::kMaxUC16CharCode ^ exor;
+    uc16 mask = char_mask ^ exor;
     macro_assembler->CheckNotCharacterAfterAnd(c1, mask, on_failure);
     return true;
   }
   ASSERT(c2 > c1);
   uc16 diff = c2 - c1;
   if (((diff - 1) & diff) == 0 && c1 >= diff) {
     // If the characters differ by 2^n but don't differ by one bit then
     // subtract the difference from the found character, then do the or
     // trick.  We avoid the theoretical case where negative numbers are
     // involved in order to simplify code generation.
-    uc16 mask = String::kMaxUC16CharCode ^ diff;
+    uc16 mask = char_mask ^ diff;
     macro_assembler->CheckNotCharacterAfterMinusAnd(c1 - diff,
                                                     diff,
                                                     mask,
                                                     on_failure);
     return true;
   }
   return false;
 }
 
 
 // Only emits letters (things that have case).  Only used for case independent
 // matches.
 static inline bool EmitAtomLetter(
     RegExpMacroAssembler* macro_assembler,
+    bool ascii,
     uc16 c,
     Label* on_failure,
     int cp_offset,
     bool check,
     bool preloaded) {
   unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
   int length = uncanonicalize.get(c, '\0', chars);
   if (length <= 1) return false;
   // We may not need to check against the end of the input string
   // if this character lies before a character that matched.
   if (!preloaded) {
     macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check);
   }
   Label ok;
   ASSERT(unibrow::Ecma262UnCanonicalize::kMaxWidth == 4);
   switch (length) {
     case 2: {
       if (ShortCutEmitCharacterPair(macro_assembler,
+                                    ascii,
                                     chars[0],
                                     chars[1],
                                     on_failure)) {
       } else {
         macro_assembler->CheckCharacter(chars[0], &ok);
         macro_assembler->CheckNotCharacter(chars[1], on_failure);
         macro_assembler->Bind(&ok);
       }
       break;
     }
@@ skipping 287 matching lines @@
   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.
     uint32_t char_mask;
     if (compiler->ascii()) {
       char_mask = String::kMaxAsciiCharCode;
     } else {
       char_mask = String::kMaxUC16CharCode;
     }
     if ((mask & char_mask) == char_mask) need_mask = false;
+    mask &= char_mask;
   } else {
     // For 2-character preloads in ASCII mode we also use a 16 bit load with
     // zero extend.
     if (details->characters() == 2 && compiler->ascii()) {
       if ((mask & 0xffff) == 0xffff) need_mask = false;
     } else {
       if (mask == 0xffffffff) need_mask = false;
     }
   }
 
@@ skipping 296 matching lines @@
                 assembler->LoadCurrentCharacter(cp_offset + j,
                                                 backtrack,
                                                 *checked_up_to < cp_offset + j);
               }
               assembler->CheckNotCharacter(quarks[j], backtrack);
             }
           } else {
             ASSERT_EQ(pass, CASE_CHARACTER_MATCH);
             ASSERT(compiler->ignore_case());
             bound_checked = EmitAtomLetter(assembler,
+                                           compiler->ascii(),
                                            quarks[j],
                                            backtrack,
                                            cp_offset + j,
                                            *checked_up_to < cp_offset + j,
                                            preloaded);
           }
           if (pass != NON_ASCII_MATCH && bound_checked) {
             if (cp_offset + j > *checked_up_to) {
               *checked_up_to = cp_offset + j;
             }
@@ skipping 60 matching lines @@
     return true;
   }
 
   if (compiler->ascii()) {
     int dummy = 0;
     TextEmitPass(compiler, NON_ASCII_MATCH, false, variant, false, &dummy);
   }
 
   bool first_elt_done = false;
   int bound_checked_to = variant->cp_offset() - 1;
-  QuickCheckDetails* quick_check = variant->quick_check_performed();
-  bound_checked_to += Max(quick_check->characters(),
-                          variant->characters_preloaded());
+  bound_checked_to += variant->bound_checked_up_to();
 
   // If a character is preloaded into the current character register then
   // check that now.
   if (variant->characters_preloaded() == 1) {
     TextEmitPass(compiler,
                  CHARACTER_MATCH,
                  true,
                  variant,
                  false,
                  &bound_checked_to);
@@ skipping 46 matching lines @@
   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;
+  bound_checked_up_to_ = Max(0, bound_checked_up_to_ - by);
 }
 
 
 void TextNode::MakeCaseIndependent() {
   int element_count = elms_->length();
   for (int i = 0; i < element_count; i++) {
     TextElement elm = elms_->at(i);
     if (elm.type == TextElement::CHAR_CLASS) {
       RegExpCharacterClass* cc = elm.data.u_char_class;
       ZoneList<CharacterRange>* ranges = cc->ranges();
@@ skipping 287 matching lines @@
       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 = false;
-  bool preload_has_checked_bounds = false;
+  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));
     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);
+    }
     new_variant.quick_check_performed()->Clear();
     alt_gen->expects_preload = preload_is_current;
     bool generate_full_check_inline = false;
     if (alternative.node()->EmitQuickCheck(compiler,
                                            &new_variant,
                                            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);
         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);
+      }
       if (i < choice_count - 1) {
         new_variant.set_backtrack(&alt_gen->after);
       }
       generate_full_check_inline = true;
     }
     if (generate_full_check_inline) {
-      if (preload_is_current) {
-        new_variant.set_characters_preloaded(preload_characters);
-      }
       for (int j = 0; j < guard_count; j++) {
         GenerateGuard(macro_assembler, guards->at(j), &new_variant);
       }
       if (!alternative.node()->Emit(compiler, &new_variant)) {
         greedy_loop_label.Unuse();
         return false;
       }
       preload_is_current = false;
     }
     macro_assembler->Bind(&alt_gen->after);
@@ skipping 1453 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal