Use a typed array for the irregexp stack.

runtime/vm/regexp_assembler.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.h"
 
 #include "vm/bit_vector.h"
 #include "vm/compiler.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 18 matching lines @@
 
 #define PRINT(arg) if (FLAG_trace_irregexp) { Print(arg); }
 
 namespace dart {
 
 DEFINE_FLAG(bool, trace_irregexp, false, "Trace irregexps");
 
 
 static const intptr_t kInvalidTryIndex = CatchClauseNode::kInvalidTryIndex;
 static const intptr_t kNoSourcePos = Scanner::kNoSourcePos;
+static const intptr_t kMinStackSize = 512;
 
 
 void PrintUtf16(uint16_t c) {
   const char* format = (0x20 <= c && c <= 0x7F) ?
         "%c" : (c <= 0xff) ? "\\x%02x" : "\\u%04x";
   OS::Print(format, c);
 }
 
 
 /*
@@ skipping 34 matching lines @@
     intptr_t capture_count,
     const ParsedFunction* parsed_function,
     const ZoneGrowableArray<const ICData*>& ic_data_array,
     Isolate* isolate)
     : RegExpMacroAssembler(isolate),
       specialization_cid_(specialization_cid),
       parsed_function_(parsed_function),
       ic_data_array_(ic_data_array),
       current_instruction_(NULL),
       stack_(NULL),
+      stack_tip_(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_(GrowableObjectArray::ZoneHandle(
-          isolate, GrowableObjectArray::New(16, Heap::kOld))),
+      stack_array_cell_(Array::ZoneHandle(isolate, Array::New(1, Heap::kOld))),
       // The registers array is allocated at a fixed size after assembly.
       registers_array_(TypedData::ZoneHandle(isolate, TypedData::null())) {
   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(isolate,
+    TypedData::New(kTypedDataInt32ArrayCid, kMinStackSize / 4, Heap::kOld)));
+
   // Create and generate all preset blocks.
   entry_block_ =
       new(isolate) GraphEntryInstr(
         parsed_function_,
         new(isolate) TargetEntryInstr(block_id_.Alloc(), kInvalidTryIndex),
         Isolate::kNoDeoptId);
   start_block_ =
       new(isolate) JoinEntryInstr(block_id_.Alloc(), kInvalidTryIndex);
   success_block_ =
       new(isolate) JoinEntryInstr(block_id_.Alloc(), kInvalidTryIndex);
@@ skipping 21 matching lines @@
 IRRegExpMacroAssembler::~IRRegExpMacroAssembler() { }
 
 
 void IRRegExpMacroAssembler::InitializeLocals() {
   // All generated functions are expected to have a current-context variable.
   // This variable is unused in irregexp functions.
   parsed_function_->current_context_var()->set_index(GetNextLocalIndex());
 
   // Create local variables and parameters.
   stack_ = Local(Symbols::stack());
+  stack_tip_ = Local(Symbols::stack_tip());

[Vyacheslav Egorov (Google), 2015/01/20 16:26:24]

Any reason for not calling it stack_pointer_ or stack_top_?

(there are functions like ReadStackPointerFromRegister)

[zerny-google, 2015/01/21 12:03:11]

Done.

   registers_ = Local(Symbols::position_registers());
   current_character_ = Local(Symbols::current_character());
   current_position_ = Local(Symbols::current_position());
   string_param_length_ = Local(Symbols::string_param_length());
   capture_length_ = Local(Symbols::capture_length());
   match_start_index_ = Local(Symbols::match_start_index());
   capture_start_index_ = Local(Symbols::capture_start_index());
   match_end_index_ = Local(Symbols::match_end_index());
   char_in_capture_ = Local(Symbols::char_in_capture());
   char_in_match_ = Local(Symbols::char_in_match());
@@ skipping 25 matching lines @@
   PushArgumentInstr* length_push = PushLocal(string_param_length_);
 
   StoreLocal(current_position_, Bind(Sub(start_index_push, length_push)));
 
   // Generate a local list variable to represent "registers" and
   // initialize capture registers (others remain garbage).
   StoreLocal(registers_, Bind(new(I) ConstantInstr(registers_array_)));
   ClearRegisters(0, saved_registers_count_ - 1);
 
   // Generate a local list variable to represent the backtracking stack.
-  StoreLocal(stack_, Bind(new(I) ConstantInstr(stack_array_)));
-  PushArgumentInstr* stack_push = PushLocal(stack_);
-  PushArgumentInstr* zero_push = PushArgument(Bind(Uint64Constant(0)));
-  Do(InstanceCall(InstanceCallDescriptor(
-      Library::PrivateCoreLibName(Symbols::_setLength())),
-      stack_push,
-      zero_push));
+  PushArgumentInstr* stack_cell_push =
+      PushArgument(Bind(new(I) ConstantInstr(stack_array_cell_)));
+  StoreLocal(stack_, Bind(InstanceCall(
+      InstanceCallDescriptor::FromToken(Token::kINDEX),
+      stack_cell_push,
+      PushArgument(Bind(Uint64Constant(0))))));
+  StoreLocal(stack_tip_, Bind(Int64Constant(-1)));
 
   // Jump to the start block.
   current_instruction_->Goto(start_block_);
 }
 
 
 void IRRegExpMacroAssembler::GenerateBacktrackBlock() {
   set_current_instruction(backtrack_block_);
   TAG();
   CheckPreemption();
 
   const intptr_t entries_count = entry_block_->indirect_entries().length();
 
   TypedData& offsets = TypedData::ZoneHandle(I,
       TypedData::New(kTypedDataInt32ArrayCid, entries_count, Heap::kOld));
 
   PushArgumentInstr* block_offsets_push =
       PushArgument(Bind(new(I) ConstantInstr(offsets)));
-  PushArgumentInstr* block_id_push = PushArgument(PopStack());
+  PushArgumentInstr* block_id_push = PushArgument(Bind(PopStack()));
 
   Value* offset_value =
       Bind(InstanceCall(InstanceCallDescriptor::FromToken(Token::kINDEX),
                         block_offsets_push,
                         block_id_push));
 
   backtrack_goto_ = new(I) IndirectGotoInstr(&offsets, offset_value);
   CloseBlockWith(backtrack_goto_);
 
   // Add an edge from the "indirect" goto to each of the targets.
@@ skipping 654 matching lines @@
                                Uint64Constant(limit)),
                     on_less);
 }
 
 
 void IRRegExpMacroAssembler::CheckGreedyLoop(BlockLabel* on_equal) {
   TAG();
 
   BlockLabel fallthrough;
 
-  PushArgumentInstr* stack_push = PushLocal(stack_);
-  Definition* stack_tip_def = InstanceCall(
-        InstanceCallDescriptor(String::ZoneHandle(
-                                 I, Field::GetterSymbol(Symbols::last()))),
-        stack_push);
+  Definition* stack_tip_def = PeekStack();

[Vyacheslav Egorov (Google), 2015/01/20 16:26:24]

Definition* peeked_def 

stack_tip_def is confusing because I thought it contains stack_tip clone but it
actually contains a value at stack[stack_tip]

[zerny-google, 2015/01/21 12:03:11]

Yes. It this is caused by trying to match the names of return types. These
should be binding to a value but the Comparison signature wants definitions :-/

Renamed to simply 'head'.

   Definition* cur_pos_def = LoadLocal(current_position_);
-
   BranchOrBacktrack(Comparison(kNE, stack_tip_def, cur_pos_def),
                     &fallthrough);
 
   // Pop, throwing away the value.
-  stack_push = PushLocal(stack_);
-  Do(InstanceCall(InstanceCallDescriptor(Symbols::removeLast()),
-                  stack_push));
+  Do(PopStack());
 
   BranchOrBacktrack(NULL, on_equal);
 
   BindBlock(&fallthrough);
 }
 
 
 void IRRegExpMacroAssembler::CheckNotBackReferenceIgnoreCase(
     intptr_t start_reg,
     BlockLabel* on_no_match) {
@@ skipping 596 matching lines @@
   ASSERT(cp_offset < (1<<30));  // Be sane! (And ensure negation works)
   if (check_bounds) {
     CheckPosition(cp_offset + characters - 1, on_end_of_input);
   }
   LoadCurrentCharacterUnchecked(cp_offset, characters);
 }
 
 
 void IRRegExpMacroAssembler::PopCurrentPosition() {
   TAG();
-  StoreLocal(current_position_, PopStack());
+  StoreLocal(current_position_, Bind(PopStack()));
 }
 
 
 void IRRegExpMacroAssembler::PopRegister(intptr_t reg) {
   TAG();
   ASSERT(reg < registers_count_);
   PushArgumentInstr* registers_push = PushLocal(registers_);
   PushArgumentInstr* index_push = PushRegisterIndex(reg);
-  PushArgumentInstr* pop_push = PushArgument(PopStack());
+  PushArgumentInstr* pop_push = PushArgument(Bind(PopStack()));
   StoreRegister(registers_push, index_push, pop_push);
 }
 
 
 void IRRegExpMacroAssembler::PushStack(Definition *definition) {
   PushArgumentInstr* stack_push = PushLocal(stack_);
+  PushArgumentInstr* stack_tip_push = PushLocal(stack_tip_);
+  StoreLocal(stack_tip_,
+             Bind(Add(stack_tip_push,
+                      PushArgument(Bind(Uint64Constant(1))))));
+  stack_tip_push = PushLocal(stack_tip_);
+  // TODO(zerny): bind value and push could break stack discipline.
   PushArgumentInstr* value_push = PushArgument(Bind(definition));
-  Do(InstanceCall(InstanceCallDescriptor(Symbols::add()),
+  Do(InstanceCall(InstanceCallDescriptor::FromToken(Token::kASSIGN_INDEX),
                   stack_push,
+                  stack_tip_push,
                   value_push));
 }
 
 
-Value* IRRegExpMacroAssembler::PopStack() {
+Definition* IRRegExpMacroAssembler::PopStack() {
   PushArgumentInstr* stack_push = PushLocal(stack_);
-  return Bind(InstanceCall(InstanceCallDescriptor(Symbols::removeLast()),
-                           stack_push));
+  PushArgumentInstr* stack_tip_push1 = PushLocal(stack_tip_);
+  PushArgumentInstr* stack_tip_push2 = PushLocal(stack_tip_);
+  StoreLocal(stack_tip_,
+             Bind(Sub(stack_tip_push2, PushArgument(Bind(Uint64Constant(1))))));
+  return InstanceCall(InstanceCallDescriptor::FromToken(Token::kINDEX),
+                      stack_push,
+                      stack_tip_push1);
 }
 
 
+Definition* IRRegExpMacroAssembler::PeekStack() {
+  PushArgumentInstr* stack_push = PushLocal(stack_);
+  PushArgumentInstr* stack_tip_push = PushLocal(stack_tip_);
+  return InstanceCall(InstanceCallDescriptor::FromToken(Token::kINDEX),
+                      stack_push,
+                      stack_tip_push);
+}
+
+
 // Pushes the location corresponding to label to the backtracking stack.
 void IRRegExpMacroAssembler::PushBacktrack(BlockLabel* label) {
   TAG();
 
   // Ensure that targets of indirect jumps are never accessed through a
   // normal control flow instructions by creating a new block for each backtrack
   // target.
   IndirectEntryInstr* indirect_target = IndirectWithJoinGoto(label->block());
 
   // Add a fake edge from the graph entry for data flow analysis.
   entry_block_->AddIndirectEntry(indirect_target);
 
   ConstantInstr* offset = Uint64Constant(indirect_target->indirect_id());
   PushStack(offset);
+  CheckStackLimit();
 }
 
 
 void IRRegExpMacroAssembler::PushCurrentPosition() {
   TAG();
   PushStack(LoadLocal(current_position_));
 }
 
 
 void IRRegExpMacroAssembler::PushRegister(intptr_t reg) {
   TAG();
+  // TODO(zerny): Refactor PushStack so it can be reused here.
   PushArgumentInstr* stack_push = PushLocal(stack_);
+  PushArgumentInstr* stack_tip_push = PushLocal(stack_tip_);
+  StoreLocal(stack_tip_,
+             Bind(Add(stack_tip_push,
+                      PushArgument(Bind(Uint64Constant(1))))));
+  stack_tip_push = PushLocal(stack_tip_);
+  // TODO(zerny): bind value and push could break stack discipline.
   PushArgumentInstr* value_push = PushArgument(LoadRegister(reg));
-  Do(InstanceCall(InstanceCallDescriptor(Symbols::add()),
+  Do(InstanceCall(InstanceCallDescriptor::FromToken(Token::kASSIGN_INDEX),
                   stack_push,
+                  stack_tip_push,
                   value_push));
+  CheckStackLimit();
 }
 
 
+// Checks that (stack.capacity - stack_limit_slack) > stack_tip.
+// This ensures that up to stack_limit_slack stack pushes can be
+// done without exhausting the stack space. If the check fails the
+// stack will be grown.
+void IRRegExpMacroAssembler::CheckStackLimit() {
+  TAG();
+  PushArgumentInstr* stack_push = PushLocal(stack_);
+  PushArgumentInstr* length_push = PushArgument(Bind(InstanceCall(
+      InstanceCallDescriptor(
+          String::ZoneHandle(Field::GetterSymbol(Symbols::Length()))),
+      stack_push)));
+  PushArgumentInstr* capacity_push = PushArgument(Bind(Sub(
+      length_push,
+      PushArgument(Bind(Uint64Constant(stack_limit_slack()))))));
+  PushArgumentInstr* stack_tip_push = PushLocal(stack_tip_);
+  BranchInstr* branch = new(I) BranchInstr(
+      Comparison(kGT, capacity_push, stack_tip_push));
+  CloseBlockWith(branch);
+
+  BlockLabel grow_stack;
+  BlockLabel fallthrough;
+  *branch->true_successor_address() =
+      TargetWithJoinGoto(fallthrough.block());
+  *branch->false_successor_address() =
+      TargetWithJoinGoto(grow_stack.block());
+
+  BindBlock(&grow_stack);
+  GrowStack();
+
+  BindBlock(&fallthrough);
+}
+
+
+void IRRegExpMacroAssembler::GrowStack() {
+  TAG();
+  Value* stack_val = Bind(LoadLocal(stack_));
+  StoreLocal(stack_, Bind(new(I) GrowTypedDataInstr(stack_val)));

[Vyacheslav Egorov (Google), 2015/01/20 16:26:24]

Consider passing stack_cell into GrowTypedDataInstr and let static call update
it instead of building IR for this.

[zerny-google, 2015/01/21 12:03:11]

Done.

+
+  // Cache the newly allocated backing for subsequent matches.
+  PushArgumentInstr* stack_cell_push =
+      PushArgument(Bind(new(I) ConstantInstr(stack_array_cell_)));
+  PushArgumentInstr* zero_index = PushArgument(Bind(Uint64Constant(0)));
+  PushArgumentInstr* stack_push = PushLocal(stack_);
+  Do(InstanceCall(InstanceCallDescriptor::FromToken(Token::kASSIGN_INDEX),
+                  stack_cell_push,
+                  zero_index,
+                  stack_push));
+}
+
+
 void IRRegExpMacroAssembler::ReadCurrentPositionFromRegister(intptr_t reg) {
   TAG();
   StoreLocal(current_position_, LoadRegister(reg));
 }
 
-// Resets the size of the stack to the value stored in reg.
+// Resets the tip of the stack to the value stored in reg.
 void IRRegExpMacroAssembler::ReadStackPointerFromRegister(intptr_t reg) {
   TAG();
   ASSERT(reg < registers_count_);
-
-  PushArgumentInstr* stack_push = PushLocal(stack_);
-  PushArgumentInstr* length_push = PushArgument(LoadRegister(reg));
-
-  Do(InstanceCall(
-      InstanceCallDescriptor(
-          String::ZoneHandle(I, Field::SetterSymbol(Symbols::Length()))),
-      stack_push,
-      length_push));
+  StoreLocal(stack_tip_, LoadRegister(reg));
 }
 
 void IRRegExpMacroAssembler::SetCurrentPositionFromEnd(intptr_t by)  {
   TAG();
 
   BlockLabel after_position;
 
   Definition* cur_pos_def = LoadLocal(current_position_);
   Definition* by_value_def = Int64Constant(-by);
 
@@ skipping 61 matching lines @@
     StoreRegister(registers_push, index_push, value_push);
   }
 }
 
 
 void IRRegExpMacroAssembler::WriteStackPointerToRegister(intptr_t reg) {
   TAG();
 
   PushArgumentInstr* registers_push = PushLocal(registers_);
   PushArgumentInstr* index_push = PushRegisterIndex(reg);
-  PushArgumentInstr* stack_push = PushLocal(stack_);
-  PushArgumentInstr* length_push =
-      PushArgument(Bind(InstanceCall(InstanceCallDescriptor(
-          String::ZoneHandle(I, Field::GetterSymbol(Symbols::Length()))),
-                                     stack_push)));
-  StoreRegister(registers_push, index_push, length_push);
+  PushArgumentInstr* tip_push = PushLocal(stack_tip_);
+  StoreRegister(registers_push, index_push, tip_push);
 }
 
 
 // Private methods:
 
 
 void IRRegExpMacroAssembler::CheckPosition(intptr_t cp_offset,
                                            BlockLabel* on_outside_input) {
   TAG();
   Definition* curpos_def = LoadLocal(current_position_);
@@ skipping 157 matching lines @@
       index_val,
       characters,
       specialization_cid_,
       Scanner::kNoSourcePos));
 }
 
 
 #undef __
 
 }  // namespace dart