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 405 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 375 matching lines @@
   friend class Int32x4BoolConstructorInstr;
   friend class Int32x4GetFlagInstr;
   friend class Int32x4SetFlagInstr;
   friend class Int32x4SelectInstr;
   friend class Int32x4ToFloat32x4Instr;
   friend class BinaryInt32x4OpInstr;
   friend class BinaryFloat64x2OpInstr;
   friend class UnaryDoubleOpInstr;
   friend class MathUnaryInstr;
   friend class MathMinMaxInstr;
+  friend class CaseInsensitiveCompareUC16Instr;

[Florian Schneider, 2014/10/01 17:04:13]

Not needed?

[jgruber1, 2014/10/03 18:59:51]

Done, unneeded now that deopt_id_ is not accessed in CICUC16Instr.

   friend class CheckClassInstr;
   friend class CheckClassIdInstr;
   friend class GuardFieldInstr;
   friend class CheckSmiInstr;
   friend class CheckArrayBoundInstr;
   friend class CheckEitherNonSmiInstr;
   friend class LICM;
   friend class DoubleToSmiInstr;
   friend class DoubleToDoubleInstr;
   friend class DoubleToFloatInstr;
   friend class FloatToDoubleInstr;
   friend class InvokeMathCFunctionInstr;
   friend class MergedMathInstr;
   friend class FlowGraphOptimizer;
   friend class LoadIndexedInstr;
+  friend class LoadCodeUnitsInstr;
   friend class StoreIndexedInstr;
   friend class StoreInstanceFieldInstr;
   friend class ComparisonInstr;
   friend class TargetEntryInstr;
+  friend class IndirectEntryInstr;

[Florian Schneider, 2014/10/01 17:04:13]

Not needed?

[jgruber1, 2014/10/03 18:59:51]

Done.

   friend class JoinEntryInstr;
   friend class InstanceOfInstr;
   friend class PolymorphicInstanceCallInstr;
   friend class SmiToDoubleInstr;
   friend class MintToDoubleInstr;
   friend class DoubleToIntegerInstr;
   friend class BranchSimplifier;
   friend class BlockEntryInstr;
   friend class RelationalOpInstr;
   friend class EqualityCompareInstr;
@@ skipping 262 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) { }
 
  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 59 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 648 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.
+class IndirectGotoInstr : public TemplateInstruction<1> {
+ public:
+  IndirectGotoInstr(GrowableObjectArray* offsets,

[Florian Schneider, 2014/10/01 17:04:13]

Can this be NULL? If not, just pass a const GrowableObjectArray& instead.

[jgruber1, 2014/10/03 18:59:51]

No, but it is modified in SetOffsetCount() and SetOffsetAt(), and lint does not
like non-const reference parameters.

+                    Value* offset_from_start)
+    : offset_from_start_(offset_from_start),
+      offsets_(*offsets) {
+    inputs_[0] = offset_from_start_;

[Vyacheslav Egorov (Google), 2014/10/01 20:13:21]

please add a comment explaining why you can't SetInputAt(0, ...) here.

[jgruber1, 2014/10/03 18:59:51]

Done, changed to SetInputAt().

+    offset_from_start_->set_instruction(this);
+    offset_from_start_->set_use_index(0);
+  }
+
+  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:
+  Value* offset_from_start_;

[Florian Schneider, 2014/10/02 11:58:12]

Remove this member. SetInputAt(0,...) already stores it.

[jgruber1, 2014/10/03 18:59:51]

Done.

+
+  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 1606 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 may 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,
+                     Value* index,
+                     intptr_t index_scale,
+                     intptr_t element_count,
+                     intptr_t class_id,
+                     intptr_t deopt_id,
+                     intptr_t token_pos)
+      : index_scale_(index_scale),
+        class_id_(class_id),
+        token_pos_(token_pos),
+        element_count_(element_count) {
+    ASSERT(class_id == kOneByteStringCid || class_id == kTwoByteStringCid);
+    SetInputAt(0, array);
+    SetInputAt(1, index);
+    deopt_id_ = deopt_id;

[Vyacheslav Egorov (Google), 2014/10/01 20:13:21]

I don't think it can deoptimize.

[jgruber1, 2014/10/03 18:59:51]

Done.

+  }
+
+  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 index_scale_; }
+  intptr_t class_id() const { return class_id_; }
+  intptr_t element_count() const { return element_count_; }
+
+  virtual bool CanDeoptimize() const {
+    return deopt_id_ != Isolate::kNoDeoptId;
+  }
+
+  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 index_scale_;
+  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 1208 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,
+      intptr_t deopt_id)
+    : 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);
+    deopt_id_ = deopt_id;

[Florian Schneider, 2014/10/01 17:04:13]

Not needed, since it can't deoptimize and also can't become deoptimization
target.

[jgruber1, 2014/10/03 18:59:51]

Done.

+  }
+
+  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 void PrintOperandsTo(BufferFormatter* f) const;
+
+  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; }
+
+  Definition* Canonicalize(FlowGraph* flow_graph);
+
+ 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 3354 matching lines @@
       Isolate* isolate, bool opt) const {                                     \
     UNIMPLEMENTED();                                                          \
     return NULL;                                                              \
   }                                                                           \
   void Name::EmitNativeCode(FlowGraphCompiler* compiler) { UNIMPLEMENTED(); }
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_