Integrate the Irregexp Regular Expression Engine.

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(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 23 matching lines @@
   M(Constant)                                                                  \
   M(UnboxedConstant)                                                           \
   M(CheckEitherNonSmi)                                                         \
   M(BinaryDoubleOp)                                                            \
   M(MathUnary)                                                                 \
   M(MathMinMax)                                                                \
   M(Box)                                                                       \
   M(Unbox)                                                                     \
   M(BoxInt64)                                                                  \
   M(UnboxInt64)                                                                \
+  M(CaseInsensitiveCompareUC16)                                                \
   M(BinaryMintOp)                                                              \
   M(ShiftMintOp)                                                               \
   M(UnaryMintOp)                                                               \
   M(CheckArrayBound)                                                           \
   M(Constraint)                                                                \
   M(StringToCharCode)                                                          \
   M(StringFromCharCode)                                                        \
   M(StringInterpolate)                                                         \
   M(InvokeMathCFunction)                                                       \
   M(MergedMath)                                                                \
@@ skipping 644 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)
       : Instruction(Isolate::Current()->GetNextDeoptId()),
         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) {

[Ivan Posva, 2014/11/10 08:16:23]

It is very unclear what these entries are used for and why they should be on the
GraphEntry instruction.

[zerny-google, 2014/11/10 09:10:42]

As far as I understand, the graph entry is the main entry of any graph (and the
only entry we know exists for any graph). The indirect (join) entries are needed
to represent the possible backtracking points in a way that satisfies the flow
graph assumptions. We add the entries to a known place (ie, the graph entry) so
we can finalize the construction by linking up the jumps with the joins after
graph construction.

+    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 678 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

[Ivan Posva, 2014/11/10 08:16:23]

This comment is unclear. What is "final" in this context? The last indirect
entry from the offset/successors array?

[zerny-google, 2014/11/10 09:10:42]

I'll update the comment to be more clear.

What this comment is trying to say is that an "indirect" goto represents a
dynamically computed goto. In order to represent the CFG of this goto we must
link it to each of the possible targets it might jump to without breaking the
assumptions of the flow graph representation. Thus the dynamic jump is
represented as an "IndirectGotoInstr" that for each possible target contains a
successor "GotoInstr" that jumps to the actual target "IndirectEntryInstr".

+// 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. The desired offset is looked up while the generated code is executing,
+// and passed to IndirectGoto as an input.
+class IndirectGotoInstr : public TemplateInstruction<1, NoThrow> {
+ 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;
+
+  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_;

[Ivan Posva, 2014/11/10 08:16:23]

How many of these successors and corresponding offsets do we get for each
IndirectGotoInstr?

[zerny-google, 2014/11/10 09:10:42]

One for each possible target. The number of targets depends on how many
backtracking points exist in the generated code for a particular regexp matching
function.

+  GrowableObjectArray& offsets_;
+};
+
+
 class ComparisonInstr : public TemplateDefinition<2, NoThrow, Pure> {
  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 1449 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(zerny): Add support for loading into UnboxedInt32x4.
+class LoadCodeUnitsInstr : public TemplateDefinition<2, NoThrow> {
+ public:
+  LoadCodeUnitsInstr(Value* 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, str);
+    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 EffectSet Effects() const { return EffectSet::None(); }
+
+ 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, NoThrow, Pure> {
  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 1155 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(zerny): Remove this once (if) functions inherited from unibrow
+// are moved to dart code.
+class CaseInsensitiveCompareUC16Instr
+    : public TemplateDefinition<4, NoThrow, Pure> {
+ 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 AttributesEqual(Instruction* other) const {
+    return other->AsCaseInsensitiveCompareUC16()->cid_ == cid_;
+  }
+
+ private:
+  const intptr_t cid_;
+
+  DISALLOW_COPY_AND_ASSIGN(CaseInsensitiveCompareUC16Instr);
+};
+
+
 // Represents Math's static min and max functions.
 class MathMinMaxInstr : public TemplateDefinition<2, NoThrow, Pure> {
  public:
   MathMinMaxInstr(MethodRecognizer::Kind op_kind,
                   Value* left_value,
                   Value* right_value,
                   intptr_t deopt_id,
                   intptr_t result_cid)
       : TemplateDefinition(deopt_id),
         op_kind_(op_kind),
@@ skipping 2968 matching lines @@
       Isolate* isolate, bool opt) const {                                     \
     UNIMPLEMENTED();                                                          \
     return NULL;                                                              \
   }                                                                           \
   void Name::EmitNativeCode(FlowGraphCompiler* compiler) { UNIMPLEMENTED(); }
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_