Port and integrate the irregexp engine from V8

runtime/vm/intermediate_language.h

 // Copyright (c) 2013, 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.
 
 #ifndef VM_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
@@ skipping 406 matching lines @@
 
 // Instructions.
 
 // M is a single argument macro.  It is applied to each concrete instruction
 // type name.  The concrete instruction classes are the name with Instr
 // concatenated.
 #define FOR_EACH_INSTRUCTION(M)                                                \
   M(GraphEntry)                                                                \
   M(JoinEntry)                                                                 \
   M(TargetEntry)                                                               \
+  M(IndirectEntry)                                                             \
   M(CatchBlockEntry)                                                           \
   M(Phi)                                                                       \
   M(Redefinition)                                                              \
   M(Parameter)                                                                 \
   M(ParallelMove)                                                              \
   M(PushArgument)                                                              \
   M(Return)                                                                    \
   M(Throw)                                                                     \
   M(ReThrow)                                                                   \
   M(Goto)                                                                      \
+  M(IndirectGoto)                                                              \
   M(Branch)                                                                    \
   M(AssertAssignable)                                                          \
   M(AssertBoolean)                                                             \
   M(CurrentContext)                                                            \
   M(StoreContext)                                                              \
   M(ClosureCall)                                                               \
   M(InstanceCall)                                                              \
   M(PolymorphicInstanceCall)                                                   \
   M(StaticCall)                                                                \
   M(LoadLocal)                                                                 \
   M(PushTemp)                                                                  \
   M(DropTemps)                                                                 \
   M(StoreLocal)                                                                \
   M(StrictCompare)                                                             \
   M(EqualityCompare)                                                           \
   M(RelationalOp)                                                              \
   M(NativeCall)                                                                \
   M(DebugStepCheck)                                                            \
   M(LoadIndexed)                                                               \
+  M(LoadCodeUnits)                                                             \
   M(StoreIndexed)                                                              \
   M(StoreInstanceField)                                                        \
   M(InitStaticField)                                                           \
   M(LoadStaticField)                                                           \
   M(StoreStaticField)                                                          \
   M(BooleanNegate)                                                             \
   M(InstanceOf)                                                                \
   M(CreateArray)                                                               \
   M(AllocateObject)                                                            \
   M(LoadField)                                                                 \
@@ skipping 19 matching lines @@
   M(FloatToDouble)                                                             \
   M(CheckClass)                                                                \
   M(CheckClassId)                                                              \
   M(CheckSmi)                                                                  \
   M(Constant)                                                                  \
   M(UnboxedConstant)                                                           \
   M(CheckEitherNonSmi)                                                         \
   M(BinaryDoubleOp)                                                            \
   M(MathUnary)                                                                 \
   M(MathMinMax)                                                                \
+  M(CaseInsensitiveCompareUC16)                                                \
   M(UnboxDouble)                                                               \
   M(BoxDouble)                                                                 \
   M(BoxFloat32x4)                                                              \
   M(UnboxFloat32x4)                                                            \
   M(BoxInt32x4)                                                                \
   M(UnboxInt32x4)                                                              \
   M(UnboxInteger)                                                              \
   M(BoxInteger)                                                                \
   M(BinaryMintOp)                                                              \
   M(ShiftMintOp)                                                               \
@@ skipping 696 matching lines @@
     return const_cast<BlockEntryInstr*>(this);
   }
 
   // Helper to mutate the graph during inlining. This block should be
   // replaced with new_block as a predecessor of all of this block's
   // successors.
   void ReplaceAsPredecessorWith(BlockEntryInstr* new_block);
 
   void set_block_id(intptr_t block_id) { block_id_ = block_id; }
 
+  intptr_t offset() const { return offset_; }
+  void set_offset(intptr_t offset) { offset_ = offset; }
+
   // For all instruction in this block: Remove all inputs (including in the
   // environment) from their definition's use lists for all instructions.
   void ClearAllInstructions();
 
   DEFINE_INSTRUCTION_TYPE_CHECK(BlockEntry)
 
  protected:
   BlockEntryInstr(intptr_t block_id, intptr_t try_index)
       : block_id_(block_id),
         try_index_(try_index),
         preorder_number_(-1),
         postorder_number_(-1),
         dominator_(NULL),
         dominated_blocks_(1),
         last_instruction_(NULL),
+        offset_(-1),
         parallel_move_(NULL),
         loop_info_(NULL) {
     deopt_id_ = Isolate::Current()->GetNextDeoptId();
   }
 
  private:
   virtual void RawSetInputAt(intptr_t i, Value* value) { UNREACHABLE(); }
 
   virtual void ClearPredecessors() = 0;
   virtual void AddPredecessor(BlockEntryInstr* predecessor) = 0;
 
   void set_dominator(BlockEntryInstr* instr) { dominator_ = instr; }
 
   intptr_t block_id_;
   const intptr_t try_index_;
   intptr_t preorder_number_;
   intptr_t postorder_number_;
   // Starting and ending lifetime positions for this block.  Used by
   // the linear scan register allocator.
   intptr_t start_pos_;
   intptr_t end_pos_;
   BlockEntryInstr* dominator_;  // Immediate dominator, NULL for graph entry.
   // TODO(fschneider): Optimize the case of one child to save space.
   GrowableArray<BlockEntryInstr*> dominated_blocks_;
   Instruction* last_instruction_;
 
+  // Offset of this block from the start of the emitted code.
+  intptr_t offset_;
+
   // Parallel move that will be used by linear scan register allocator to
   // connect live ranges at the start of the block.
   ParallelMoveInstr* parallel_move_;
 
   // Bit vector containg loop blocks for a loop header indexed by block
   // preorder number.
   BitVector* loop_info_;
 
   DISALLOW_COPY_AND_ASSIGN(BlockEntryInstr);
 };
@@ skipping 60 matching lines @@
     UNREACHABLE();
     return NULL;
   }
   virtual intptr_t SuccessorCount() const;
   virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
 
   void AddCatchEntry(CatchBlockEntryInstr* entry) { catch_entries_.Add(entry); }
 
   CatchBlockEntryInstr* GetCatchEntry(intptr_t index);
 
+  void AddIndirectEntry(IndirectEntryInstr* entry) {
+    indirect_entries_.Add(entry);
+  }
+
   GrowableArray<Definition*>* initial_definitions() {
     return &initial_definitions_;
   }
   ConstantInstr* constant_null();
 
   bool IsCompiledForOsr() const { return osr_id_ != Isolate::kNoDeoptId; }
 
   intptr_t entry_count() const { return entry_count_; }
   void set_entry_count(intptr_t count) { entry_count_ = count; }
 
@@ skipping 14 matching lines @@
   TargetEntryInstr* normal_entry() const { return normal_entry_; }
 
   const ParsedFunction& parsed_function() const {
     return *parsed_function_;
   }
 
   const GrowableArray<CatchBlockEntryInstr*>& catch_entries() const {
     return catch_entries_;
   }
 
+  const GrowableArray<IndirectEntryInstr*>& indirect_entries() const {
+    return indirect_entries_;
+  }
+
   virtual void PrintTo(BufferFormatter* f) const;
 
  private:
   virtual void ClearPredecessors() {}
   virtual void AddPredecessor(BlockEntryInstr* predecessor) { UNREACHABLE(); }
 
   const ParsedFunction* parsed_function_;
   TargetEntryInstr* normal_entry_;
   GrowableArray<CatchBlockEntryInstr*> catch_entries_;
+  // Indirect targets are blocks reachable only through indirect gotos.
+  GrowableArray<IndirectEntryInstr*> indirect_entries_;
   GrowableArray<Definition*> initial_definitions_;
   const intptr_t osr_id_;
   intptr_t entry_count_;
   intptr_t spill_slot_count_;
   intptr_t fixed_slot_count_;  // For try-catch in optimized code.
 
   DISALLOW_COPY_AND_ASSIGN(GraphEntryInstr);
 };
 
 
@@ skipping 25 matching lines @@
   virtual void PrintTo(BufferFormatter* f) const;
 
   virtual EffectSet Effects() const { return EffectSet::None(); }
   virtual EffectSet Dependencies() const { return EffectSet::None(); }
 
  private:
   // Classes that have access to predecessors_ when inlining.
   friend class BlockEntryInstr;
   friend class InlineExitCollector;
   friend class PolymorphicInliner;
+  friend class IndirectEntryInstr;  // Access in il_printer.cc.
 
   // Direct access to phis_ in order to resize it due to phi elimination.
   friend class ConstantPropagator;
   friend class DeadCodeElimination;
 
   virtual void ClearPredecessors() { predecessors_.Clear(); }
   virtual void AddPredecessor(BlockEntryInstr* predecessor);
 
   GrowableArray<BlockEntryInstr*> predecessors_;
   ZoneGrowableArray<PhiInstr*>* phis_;
@@ skipping 58 matching lines @@
     predecessor_ = predecessor;
   }
 
   BlockEntryInstr* predecessor_;
   double edge_weight_;
 
   DISALLOW_COPY_AND_ASSIGN(TargetEntryInstr);
 };
 
 
+class IndirectEntryInstr : public JoinEntryInstr {
+ public:
+  IndirectEntryInstr(intptr_t block_id,
+                     intptr_t indirect_id,
+                     intptr_t try_index)
+      : JoinEntryInstr(block_id, try_index),
+        indirect_id_(indirect_id) { }
+
+  DECLARE_INSTRUCTION(IndirectEntry)
+
+  virtual void PrintTo(BufferFormatter* f) const;
+
+  intptr_t indirect_id() const { return indirect_id_; }
+
+ private:
+  const intptr_t indirect_id_;
+};
+
+
 class CatchBlockEntryInstr : public BlockEntryInstr {
  public:
   CatchBlockEntryInstr(intptr_t block_id,
                        intptr_t try_index,
                        const Array& handler_types,
                        intptr_t catch_try_index,
                        const LocalVariable& exception_var,
                        const LocalVariable& stacktrace_var,
                        bool needs_stacktrace)
       : BlockEntryInstr(block_id, try_index),
@@ skipping 654 matching lines @@
  private:
   JoinEntryInstr* successor_;
   double edge_weight_;
 
   // Parallel move that will be used by linear scan register allocator to
   // connect live ranges at the end of the block and resolve phis.
   ParallelMoveInstr* parallel_move_;
 };
 
 
+// As a high level description, an indirect goto takes the indirect_id of an
+// indirect entry as a parameter, and jumps to that location.
+//
+// In more detail: in order to preserve split-edge form, an intermediate target
+// entry consisting of a goto to the final indirect entry is inserted on
+// each possible indirect goto -> indirect entry edge. These target entries are
+// accessible through successors_.
+//
+// Byte offsets of all possible indirect targets are stored in the offsets_
+// array and are looked up at runtime.

[Ivan Posva, 2014/10/09 09:54:15]

It is not clear what runtime means here. While executing the regular expression?

[jgruber1, 2014/10/09 13:36:16]

Yes. Clarified the comment.

+class IndirectGotoInstr : public TemplateInstruction<1> {
+ public:
+  IndirectGotoInstr(GrowableObjectArray* offsets,
+                    Value* offset_from_start)
+    : offsets_(*offsets) {
+    SetInputAt(0, offset_from_start);
+  }
+
+  DECLARE_INSTRUCTION(IndirectGoto)
+
+  virtual intptr_t ArgumentCount() const { return 0; }
+
+  void AddSuccessor(TargetEntryInstr* successor) {
+    ASSERT(successor->next()->IsGoto());
+    ASSERT(successor->next()->AsGoto()->successor()->IsIndirectEntry());
+    successors_.Add(successor);
+  }
+
+  virtual intptr_t SuccessorCount() const { return successors_.length(); }
+  virtual TargetEntryInstr* SuccessorAt(intptr_t index) const {
+    ASSERT(index < SuccessorCount());
+    return successors_[index];
+  }
+
+  virtual bool CanDeoptimize() const { return false; }
+  virtual bool CanBecomeDeoptimizationTarget() const { return false; }
+
+  virtual EffectSet Effects() const { return EffectSet::None(); }
+
+  virtual void PrintTo(BufferFormatter* f) const;
+
+  virtual bool MayThrow() const { return false; }
+
+  const GrowableObjectArray& offsets() const { return offsets_; }
+  void SetOffsetCount(Isolate* isolate, intptr_t count) {
+    if (offsets_.Capacity() < count) {
+      offsets_.Grow(count, Heap::kOld);
+    }
+    if (offsets_.Length() < count) {
+      offsets_.SetLength(count);
+    }
+  }
+  void SetOffsetAt(Isolate* isolate, intptr_t index, intptr_t offset) {
+    offsets_.SetAt(index, Smi::ZoneHandle(isolate, Smi::New(offset)));
+  }
+
+ private:
+  GrowableArray<TargetEntryInstr*> successors_;
+  GrowableObjectArray& offsets_;
+};
+
+
 class ComparisonInstr : public TemplateDefinition<2> {
  public:
   Value* left() const { return inputs_[0]; }
   Value* right() const { return inputs_[1]; }
 
   virtual intptr_t token_pos() const { return token_pos_; }
   Token::Kind kind() const { return kind_; }
 
   virtual ComparisonInstr* CopyWithNewOperands(Value* left, Value* right) = 0;
 
@@ skipping 1618 matching lines @@
 
  private:
   const intptr_t index_scale_;
   const intptr_t class_id_;
   const intptr_t token_pos_;
 
   DISALLOW_COPY_AND_ASSIGN(LoadIndexedInstr);
 };
 
 
+// Loads the specified number of code units from the given string, packing
+// multiple code units into a single datatype. In essence, this is a specialized
+// version of LoadIndexedInstr which accepts only string targets and can load
+// multiple elements at once. The result datatype differs depending on the
+// string type, element count, and architecture; if possible, the result is
+// packed into a Smi, falling back to a Mint otherwise.
+// TODO(jgruber): Add support for loading into UnboxedInt32x4.
+class LoadCodeUnitsInstr : public TemplateDefinition<2> {
+ public:
+  LoadCodeUnitsInstr(Value* array,

[Ivan Posva, 2014/10/09 09:54:15]

Why do we need a special instruction here? Can't this be "just" a static call to
a corresponding recognized method?
Why is one of the values being passed an array? Shouldn't that be the string?

[jgruber1, 2014/10/09 13:36:16]

The instruction is needed because the corresponding recognized method optimizes
to it. It's different from LoadIndexed in that it may load more than one 'array
element' (in this case, code unit from a string) at once and pack them into a
single return value.

It's one of the hottest functions in irregexp execution, so optimizing down to a
single mov (plus a SmiTag and possibly a SmiUntag) makes a big difference.

The 'array' name was left over from LoadIndexedInstr, I've changed it to 'str'.

+                     Value* index,
+                     intptr_t element_count,
+                     intptr_t class_id,
+                     intptr_t token_pos)
+      : class_id_(class_id),
+        token_pos_(token_pos),
+        element_count_(element_count) {
+    ASSERT(element_count == 1 || element_count == 2 || element_count == 4);
+    ASSERT(class_id == kOneByteStringCid || class_id == kTwoByteStringCid);
+    SetInputAt(0, array);
+    SetInputAt(1, index);
+  }
+
+  intptr_t token_pos() const { return token_pos_; }
+
+  DECLARE_INSTRUCTION(LoadCodeUnits)
+  virtual CompileType ComputeType() const;
+
+  bool IsExternal() const {
+    return array()->definition()->representation() == kUntagged;
+  }
+
+  Value* array() const { return inputs_[0]; }
+  Value* index() const { return inputs_[1]; }
+  intptr_t index_scale() const { return Instance::ElementSizeFor(class_id_); }
+  intptr_t class_id() const { return class_id_; }
+  intptr_t element_count() const { return element_count_; }
+
+  bool can_pack_into_smi() const {
+    return element_count() <= kSmiBits / (index_scale() * kBitsPerByte);
+  }
+
+  virtual bool CanDeoptimize() const { return false; }
+
+  virtual Representation representation() const;
+  virtual void InferRange(RangeAnalysis* analysis, Range* range);
+
+  virtual bool AllowsCSE() const { return false; }
+  virtual EffectSet Effects() const { return EffectSet::None(); }
+  virtual EffectSet Dependencies() const { return EffectSet::All(); }
+  virtual bool AttributesEqual(Instruction* other) const;
+
+  virtual bool MayThrow() const { return false; }
+
+ private:
+  const intptr_t class_id_;
+  const intptr_t token_pos_;
+  const intptr_t element_count_;
+
+  DISALLOW_COPY_AND_ASSIGN(LoadCodeUnitsInstr);
+};
+
+
 class StringFromCharCodeInstr : public TemplateDefinition<1> {
  public:
   StringFromCharCodeInstr(Value* char_code, intptr_t cid) : cid_(cid) {
     ASSERT(char_code != NULL);
     ASSERT(char_code->definition()->IsLoadIndexed());
     ASSERT(char_code->definition()->AsLoadIndexed()->class_id() ==
            kOneByteStringCid);
     SetInputAt(0, char_code);
   }
 
@@ skipping 1214 matching lines @@
 
   static const char* KindToCString(MathUnaryKind kind);
 
  private:
   const MathUnaryKind kind_;
 
   DISALLOW_COPY_AND_ASSIGN(MathUnaryInstr);
 };
 
 
+// Calls into the runtime and performs a case-insensitive comparison of the
+// UTF16 strings (i.e. TwoByteString or ExternalTwoByteString) located at
+// str[lhs_index:lhs_index + length] and str[rhs_index:rhs_index + length].
+//
+// TODO(jgruber): Remove this once (if) functions inherited from unibrow
+// are moved to dart code.
+class CaseInsensitiveCompareUC16Instr : public TemplateDefinition<4> {
+ public:
+  CaseInsensitiveCompareUC16Instr(
+      Value* str,
+      Value* lhs_index,
+      Value* rhs_index,
+      Value* length,
+      intptr_t cid)
+    : cid_(cid) {
+    ASSERT(cid == kTwoByteStringCid || cid == kExternalTwoByteStringCid);
+    ASSERT(index_scale() == 2);
+    SetInputAt(0, str);
+    SetInputAt(1, lhs_index);
+    SetInputAt(2, rhs_index);
+    SetInputAt(3, length);
+  }
+
+  Value* str() const { return inputs_[0]; }
+  Value* lhs_index() const { return inputs_[1]; }
+  Value* rhs_index() const { return inputs_[2]; }
+  Value* length() const { return inputs_[3]; }
+
+  const RuntimeEntry& TargetFunction() const;
+  bool IsExternal() const { return cid_ == kExternalTwoByteStringCid; }
+  intptr_t class_id() const { return cid_; }
+  intptr_t index_scale() const { return Instance::ElementSizeFor(cid_); }
+
+  virtual bool CanDeoptimize() const { return false; }
+
+  virtual Representation representation() const {
+    return kTagged;
+  }
+
+  DECLARE_INSTRUCTION(CaseInsensitiveCompareUC16)
+  virtual CompileType ComputeType() const;
+
+  virtual bool AllowsCSE() const { return true; }
+  virtual EffectSet Effects() const { return EffectSet::None(); }
+  virtual EffectSet Dependencies() const { return EffectSet::None(); }
+
+  virtual bool MayThrow() const { return false; }
+
+ private:
+  const intptr_t cid_;
+
+  DISALLOW_COPY_AND_ASSIGN(CaseInsensitiveCompareUC16Instr);
+};
+
+
 // Represents Math's static min and max functions.
 class MathMinMaxInstr : public TemplateDefinition<2> {
  public:
   MathMinMaxInstr(MethodRecognizer::Kind op_kind,
                   Value* left_value,
                   Value* right_value,
                   intptr_t deopt_id,
                   intptr_t result_cid)
       : op_kind_(op_kind), result_cid_(result_cid) {
     ASSERT((result_cid == kSmiCid) || (result_cid == kDoubleCid));
@@ skipping 3355 matching lines @@
       Isolate* isolate, bool opt) const {                                     \
     UNIMPLEMENTED();                                                          \
     return NULL;                                                              \
   }                                                                           \
   void Name::EmitNativeCode(FlowGraphCompiler* compiler) { UNIMPLEMENTED(); }
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_