Port and integrate the irregexp engine from V8

runtime/vm/intermediate_language.h

Index: runtime/vm/intermediate_language.h
diff --git a/runtime/vm/intermediate_language.h b/runtime/vm/intermediate_language.h
index e7933fcb63c2cf75952bee0dfd8a3d0db7d4bc2c..731894ea8b563c479e56fddb184fe381d994beeb 100644
--- a/runtime/vm/intermediate_language.h
+++ b/runtime/vm/intermediate_language.h
@@ -423,6 +423,7 @@ class EmbeddedArray<T, 0> {
   M(GraphEntry)                                                                \
   M(JoinEntry)                                                                 \
   M(TargetEntry)                                                               \
+  M(IndirectEntry)                                                             \
   M(CatchBlockEntry)                                                           \
   M(Phi)                                                                       \
   M(Redefinition)                                                              \
@@ -433,6 +434,7 @@ class EmbeddedArray<T, 0> {
   M(Throw)                                                                     \
   M(ReThrow)                                                                   \
   M(Goto)                                                                      \
+  M(IndirectGoto)                                                              \
   M(Branch)                                                                    \
   M(AssertAssignable)                                                          \
   M(AssertBoolean)                                                             \
@@ -452,6 +454,7 @@ class EmbeddedArray<T, 0> {
   M(NativeCall)                                                                \
   M(DebugStepCheck)                                                            \
   M(LoadIndexed)                                                               \
+  M(LoadCodeUnits)                                                             \
   M(StoreIndexed)                                                              \
   M(StoreInstanceField)                                                        \
   M(InitStaticField)                                                           \
@@ -491,6 +494,7 @@ class EmbeddedArray<T, 0> {
   M(BinaryDoubleOp)                                                            \
   M(MathUnary)                                                                 \
   M(MathMinMax)                                                                \
+  M(CaseInsensitiveCompareUC16)                                                \
   M(UnboxDouble)                                                               \
   M(BoxDouble)                                                                 \
   M(BoxFloat32x4)                                                              \
@@ -886,6 +890,7 @@ FOR_EACH_ABSTRACT_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
   friend class UnaryDoubleOpInstr;
   friend class MathUnaryInstr;
   friend class MathMinMaxInstr;
+  friend class CaseInsensitiveCompareUC16Instr;
   friend class CheckClassInstr;
   friend class CheckClassIdInstr;
   friend class GuardFieldInstr;
@@ -901,10 +906,12 @@ FOR_EACH_ABSTRACT_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
   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;
   friend class JoinEntryInstr;
   friend class InstanceOfInstr;
   friend class PolymorphicInstanceCallInstr;
@@ -1187,6 +1194,9 @@ class BlockEntryInstr : public Instruction {
 
   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();
@@ -1202,6 +1212,7 @@ class BlockEntryInstr : public Instruction {
         dominator_(NULL),
         dominated_blocks_(1),
         last_instruction_(NULL),
+        offset_(-1),
         parallel_move_(NULL),
         loop_info_(NULL) { }
 
@@ -1226,6 +1237,9 @@ class BlockEntryInstr : public Instruction {
   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_;
@@ -1306,6 +1320,12 @@ class GraphEntryInstr : public BlockEntryInstr {
 
   CatchBlockEntryInstr* GetCatchEntry(intptr_t index);
 
+  void AddIndirectEntry(IndirectEntryInstr* entry) {
+    indirect_entries_.Add(entry);
+  }
+
+  JoinEntryInstr* GetIndirectTargetEntry(intptr_t index);
+
   GrowableArray<Definition*>* initial_definitions() {
     return &initial_definitions_;
   }
@@ -1340,6 +1360,10 @@ class GraphEntryInstr : public BlockEntryInstr {
     return catch_entries_;
   }
 
+  const GrowableArray<IndirectEntryInstr*>& indirect_entries() const {
+    return indirect_entries_;
+  }
+
   virtual void PrintTo(BufferFormatter* f) const;
 
  private:
@@ -1349,6 +1373,8 @@ class GraphEntryInstr : public BlockEntryInstr {
   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_;
@@ -1394,6 +1420,7 @@ class JoinEntryInstr : public BlockEntryInstr {
   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;
@@ -1473,6 +1500,17 @@ class TargetEntryInstr : public BlockEntryInstr {
 };
 
 
+class IndirectEntryInstr : public JoinEntryInstr {
+ public:
+  IndirectEntryInstr(intptr_t block_id, intptr_t try_index)
+      : JoinEntryInstr(block_id, try_index) { }
+
+  DECLARE_INSTRUCTION(IndirectEntry)
+
+  virtual void PrintTo(BufferFormatter* f) const;
+};
+
+
 class CatchBlockEntryInstr : public BlockEntryInstr {
  public:
   CatchBlockEntryInstr(intptr_t block_id,
@@ -2141,6 +2179,67 @@ class GotoInstr : public TemplateInstruction<0> {
 };
 
 
+// Targets of indirect gotos are never entered through any other means.
+class IndirectGotoInstr : public TemplateInstruction<1> {
+ public:
+  explicit IndirectGotoInstr(GrowableObjectArray* offsets,
+                             Value* offset_from_start)

[srdjan, 2014/09/22 22:34:07]

remove explicit

[jgruber1, 2014/09/23 10:58:47]

Done.

+    : offset_from_start_(offset_from_start),
+      edge_weight_(0.0),
+      offsets_(*offsets) {
+    inputs_[0] = offset_from_start_;
+    offset_from_start_->set_instruction(this);
+    offset_from_start_->set_use_index(0);
+  }
+
+  DECLARE_INSTRUCTION(IndirectGoto)
+
+  virtual intptr_t ArgumentCount() const { return 0; }
+
+  double edge_weight() const { return edge_weight_; }
+  void set_edge_weight(double weight) { edge_weight_ = weight; }
+  void adjust_edge_weight(double scale_factor) { edge_weight_ *= scale_factor; }

[srdjan, 2014/09/22 22:34:07]

s/adjust_edge_weight/scale_edge_weight/ to make it more readable at call site?

[jgruber1, 2014/09/23 10:58:47]

edge_weight_ was left over from duplicating GotoInstr, removed it & associated
functions.

+
+  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 SetOffsetAt(Isolate* isolate, intptr_t index, intptr_t offset) {
+    intptr_t minimal_length = index + 1;
+    if (offsets_.Length() < minimal_length) {
+      offsets_.Grow(minimal_length, Heap::kOld);
+      offsets_.SetLength(minimal_length);
+    }
+    offsets_.SetAt(index, Smi::ZoneHandle(isolate, Smi::New(offset)));
+  }
+
+ private:
+  Value* offset_from_start_;
+  double edge_weight_;
+
+  GrowableArray<TargetEntryInstr*> successors_;
+  GrowableObjectArray& offsets_;
+};
+
+
 class ComparisonInstr : public TemplateDefinition<2> {
  public:
   Value* left() const { return inputs_[0]; }
@@ -3767,6 +3866,64 @@ class LoadIndexedInstr : public TemplateDefinition<2> {
 };
 
 
+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;
+  }
+
+  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) {
@@ -4995,6 +5152,69 @@ class MathUnaryInstr : public TemplateDefinition<1> {
 };
 
 
+// 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;
+  }
+
+  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;
+  }
+
+  virtual intptr_t DeoptimizationTarget() const {
+    // Direct access since this instruction cannot deoptimize, and the deopt-id
+    // was inherited from another instruction that could deoptimize.
+    return deopt_id_;
+  }
+
+  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: