VM(RegExp): Allow OSR optimization of RegExp :matcher functions.

runtime/vm/regexp_assembler_ir.cc

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/regexp_assembler_ir.h"
 
 #include "vm/bit_vector.h"
 #include "vm/compiler.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 60 matching lines @@
  * indices of -1 denote non-matched groups. Note that we store these indices
  * as a negative offset from the end of the string in registers_array_
  * during processing, and convert them to standard indexes when copying them
  * to matches_param_ on successful match.
  */
 IRRegExpMacroAssembler::IRRegExpMacroAssembler(
     intptr_t specialization_cid,
     intptr_t capture_count,
     const ParsedFunction* parsed_function,
     const ZoneGrowableArray<const ICData*>& ic_data_array,
+    intptr_t osr_id,
     Zone* zone)
     : RegExpMacroAssembler(zone),
       thread_(Thread::Current()),
       specialization_cid_(specialization_cid),
       parsed_function_(parsed_function),
       ic_data_array_(ic_data_array),
       current_instruction_(NULL),
       stack_(NULL),
       stack_pointer_(NULL),
       current_character_(NULL),
       current_position_(NULL),
       string_param_(NULL),
       string_param_length_(NULL),
       start_index_param_(NULL),
       registers_count_(0),
       saved_registers_count_((capture_count + 1) * 2),
       stack_array_cell_(Array::ZoneHandle(zone, Array::New(1, Heap::kOld))),
       // The registers array is allocated at a fixed size after assembly.
-      registers_array_(TypedData::ZoneHandle(zone, TypedData::null())) {
+      registers_array_(TypedData::ZoneHandle(zone, TypedData::null())),
+      // B0 is taken by GraphEntry thus block ids must start at 1.
+      block_id_(1) {
   switch (specialization_cid) {
     case kOneByteStringCid:
     case kExternalOneByteStringCid:
       mode_ = ASCII;
       break;
     case kTwoByteStringCid:
     case kExternalTwoByteStringCid:
       mode_ = UC16;
       break;
     default:
       UNREACHABLE();
   }
 
   InitializeLocals();
 
   // Allocate an initial stack backing of the minimum stack size. The stack
   // backing is indirectly referred to so we can reuse it on subsequent matches
   // even in the case where the backing has been enlarged and thus reallocated.
   stack_array_cell_.SetAt(
       0,
       TypedData::Handle(zone, TypedData::New(kTypedDataInt32ArrayCid,
                                              kMinStackSize / 4, Heap::kOld)));
 
   // Create and generate all preset blocks.
   entry_block_ = new (zone) GraphEntryInstr(
       *parsed_function_,
       new (zone) TargetEntryInstr(block_id_.Alloc(), kInvalidTryIndex,
                                   GetNextDeoptId()),
-      Compiler::kNoOSRDeoptId);
+      osr_id);
   start_block_ = new (zone)
       JoinEntryInstr(block_id_.Alloc(), kInvalidTryIndex, GetNextDeoptId());
   success_block_ = new (zone)
       JoinEntryInstr(block_id_.Alloc(), kInvalidTryIndex, GetNextDeoptId());
   backtrack_block_ = new (zone)
       JoinEntryInstr(block_id_.Alloc(), kInvalidTryIndex, GetNextDeoptId());
   exit_block_ = new (zone)
       JoinEntryInstr(block_id_.Alloc(), kInvalidTryIndex, GetNextDeoptId());
 
   GenerateEntryBlock();
@@ skipping 77 matching lines @@
   StoreLocal(stack_pointer_, Bind(Int64Constant(-1)));
 
   // Jump to the start block.
   current_instruction_->Goto(start_block_);
 }
 
 
 void IRRegExpMacroAssembler::GenerateBacktrackBlock() {
   set_current_instruction(backtrack_block_);
   TAG();
-  CheckPreemption();
+  CheckPreemption(/*is_backtrack=*/true);
 
   const intptr_t entries_count = entry_block_->indirect_entries().length();
 
   TypedData& offsets = TypedData::ZoneHandle(
       Z, TypedData::New(kTypedDataInt32ArrayCid, entries_count, Heap::kOld));
 
   PushArgumentInstr* block_offsets_push =
       PushArgument(Bind(new (Z) ConstantInstr(offsets)));
   PushArgumentInstr* block_id_push = PushArgument(Bind(PopStack()));
 
@@ skipping 1350 matching lines @@
 
   BindBlock(&grow_stack);
   GrowStack();
 
   BindBlock(&fallthrough);
 }
 
 
 void IRRegExpMacroAssembler::GrowStack() {
   TAG();
-  Value* cell = Bind(new (Z) ConstantInstr(stack_array_cell_));
-  StoreLocal(stack_, Bind(new (Z) GrowRegExpStackInstr(cell)));
+  const Library& lib = Library::Handle(Library::InternalLibrary());
+  const Function& grow_function = Function::ZoneHandle(
+      Z, lib.LookupFunctionAllowPrivate(Symbols::GrowRegExpStack()));
+  StoreLocal(stack_, Bind(StaticCall(grow_function, PushLocal(stack_))));
+
+  // Note: :stack and stack_array_cell content might diverge because each
+  // instance of :matcher code has its own stack_array_cell embedded into it
+  // as a constant but :stack is a local variable and its value might be
+  // comming from OSR or deoptimization. This means we should never use
+  // stack_array_cell in the body of the :matcher to reload the :stack.
+  PushArgumentInstr* stack_cell_push =
+      PushArgument(Bind(new (Z) ConstantInstr(stack_array_cell_)));
+  PushArgumentInstr* index_push = PushArgument(Bind(Uint64Constant(0)));
+  PushArgumentInstr* stack_push = PushLocal(stack_);
+  Do(InstanceCall(InstanceCallDescriptor::FromToken(Token::kASSIGN_INDEX),
+                  stack_cell_push, index_push, stack_push));
 }
 
 
 void IRRegExpMacroAssembler::ReadCurrentPositionFromRegister(intptr_t reg) {
   TAG();
   StoreLocal(current_position_, LoadRegister(reg));
 }
 
 // Resets the tip of the stack to the value stored in reg.
 void IRRegExpMacroAssembler::ReadStackPointerFromRegister(intptr_t reg) {
@@ skipping 151 matching lines @@
       new (Z) IndirectEntryInstr(block_id_.Alloc(), indirect_id_.Alloc(),
                                  kInvalidTryIndex, GetNextDeoptId());
   blocks_.Add(target);
 
   target->AppendInstruction(new (Z) GotoInstr(dst, GetNextDeoptId()));
 
   return target;
 }
 
 
-void IRRegExpMacroAssembler::CheckPreemption() {
+void IRRegExpMacroAssembler::CheckPreemption(bool is_backtrack) {
   TAG();
-  AppendInstruction(new (Z) CheckStackOverflowInstr(TokenPosition::kNoSource, 0,
-                                                    GetNextDeoptId()));
+
+  // We don't have the loop_depth available when compiling regexps, but
+  // we set loop_depth to a non-zero value because this instruction does
+  // not act as an OSR entry outside loops.
+  AppendInstruction(new (Z) CheckStackOverflowInstr(
+      TokenPosition::kNoSource,
+      /*loop_depth=*/1, GetNextDeoptId(),
+      is_backtrack ? CheckStackOverflowInstr::kOsrAndPreemption
+                   : CheckStackOverflowInstr::kOsrOnly));
 }
 
 
 Definition* IRRegExpMacroAssembler::Add(PushArgumentInstr* lhs,
                                         PushArgumentInstr* rhs) {
   return InstanceCall(InstanceCallDescriptor::FromToken(Token::kADD), lhs, rhs);
 }
 
 
 Definition* IRRegExpMacroAssembler::Sub(PushArgumentInstr* lhs,
@@ skipping 68 matching lines @@
 
   return Bind(new (Z) LoadCodeUnitsInstr(pattern_val, index_val, characters,
                                          specialization_cid_,
                                          TokenPosition::kNoSource));
 }
 
 
 #undef __
 
 }  // namespace dart