Port and integrate the irregexp engine from V8

runtime/vm/flow_graph_optimizer.cc

 // 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.
 
 #include "vm/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
 #include "vm/exceptions.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
 #include "vm/flow_graph_range_analysis.h"
 #include "vm/hash_map.h"
 #include "vm/il_printer.h"
 #include "vm/intermediate_language.h"
 #include "vm/object_store.h"
 #include "vm/parser.h"
+#include "vm/regexp_assembler.h"
 #include "vm/resolver.h"
 #include "vm/scopes.h"
 #include "vm/stack_frame.h"
 #include "vm/symbols.h"
 
 namespace dart {
 
 DEFINE_FLAG(int, getter_setter_ratio, 13,
     "Ratio of getter/setter usage used for double field unboxing heuristics");
 DEFINE_FLAG(bool, load_cse, true, "Use redundant load elimination.");
@@ skipping 1594 matching lines @@
       if (!ShouldInlineSimd()) {
         return false;
       }
       return InlineByteArrayViewStore(target, call, receiver, receiver_cid,
                                       kTypedDataInt32x4ArrayCid,
                                       ic_data, entry, last);
     case MethodRecognizer::kStringBaseCodeUnitAt:
       return InlineStringCodeUnitAt(call, receiver_cid, entry, last);
     case MethodRecognizer::kStringBaseCharAt:
       return InlineStringBaseCharAt(call, receiver_cid, entry, last);
+    case MethodRecognizer::kOneByteString_oneCodeUnitAt:
+    case MethodRecognizer::kTwoByteString_oneCodeUnitAt:
+      return InlineStringCodeUnitsAt(call, receiver_cid, 1, entry, last);
+    case MethodRecognizer::kOneByteString_twoCodeUnitsAt:
+    case MethodRecognizer::kTwoByteString_twoCodeUnitsAt:
+      return InlineStringCodeUnitsAt(call, receiver_cid, 2, entry, last);
+    case MethodRecognizer::kOneByteString_fourCodeUnitsAt:
+      return InlineStringCodeUnitsAt(call, receiver_cid, 4, entry, last);
     case MethodRecognizer::kDoubleAdd:
       return InlineDoubleOp(Token::kADD, call, entry, last);
     case MethodRecognizer::kDoubleSub:
       return InlineDoubleOp(Token::kSUB, call, entry, last);
     case MethodRecognizer::kDoubleMul:
       return InlineDoubleOp(Token::kMUL, call, entry, last);
     case MethodRecognizer::kDoubleDiv:
       return InlineDoubleOp(Token::kDIV, call, entry, last);
     default:
       return false;
@@ skipping 1189 matching lines @@
   *entry = new(I) TargetEntryInstr(flow_graph()->allocate_block_id(),
                                    call->GetBlock()->try_index());
   (*entry)->InheritDeoptTarget(I, call);
 
   *last = PrepareInlineStringIndexOp(call, cid, str, index, *entry);
 
   return true;
 }
 
 
+Definition* FlowGraphOptimizer::PrepareInlineStringIndexOpUnchecked(
+    Instruction* call,
+    intptr_t cid,
+    intptr_t count,
+    Definition* str,
+    Definition* index,
+    Instruction* cursor) {
+  LoadCodeUnitsInstr* load = new(I) LoadCodeUnitsInstr(

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

[ignore this comment]

This is *a*whole*lot* of code (and also "dead" stuff like that TargetEntryInstr
down there) to produce a single instruction.

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

I agree, the reason behind this was that LoadIndexedInstr was not expected in
unoptimized code and we wanted to optimize *codeUnitsAt 'properly'.

+      new(I) Value(str),
+      new(I) Value(index),
+      Instance::ElementSizeFor(cid),
+      count,
+      cid,
+      Isolate::kNoDeoptId,
+      call->token_pos());
+
+  cursor = flow_graph()->AppendTo(cursor,
+                                  load,
+                                  NULL,
+                                  FlowGraph::kValue);
+  ASSERT(cursor == load);
+  return load;
+}
+
+
+bool FlowGraphOptimizer::InlineStringCodeUnitsAt(
+    Instruction* call,
+    intptr_t cid,
+    intptr_t count,
+    TargetEntryInstr** entry,
+    Definition** last) {
+  // TODO(johnmccutchan): Handle external strings in PrepareInlineStringIndexOp.
+  if (RawObject::IsExternalStringClassId(cid)) {
+    return false;
+  }
+
+  Definition* str = call->ArgumentAt(0);
+  Definition* index = call->ArgumentAt(1);
+
+  *entry = new(I) TargetEntryInstr(flow_graph()->allocate_block_id(),
+                                   call->GetBlock()->try_index());
+  (*entry)->InheritDeoptTarget(I, call);
+
+  *last = PrepareInlineStringIndexOpUnchecked(
+        call, cid, count, str, index, *entry);
+
+  return true;
+}
+
+
 bool FlowGraphOptimizer::InlineStringBaseCharAt(
     Instruction* call,
     intptr_t cid,
     TargetEntryInstr** entry,
     Definition** last) {
   // TODO(johnmccutchan): Handle external strings in PrepareInlineStringIndexOp.
   if (RawObject::IsExternalStringClassId(cid) || cid != kOneByteStringCid) {
     return false;
   }
   Definition* str = call->ArgumentAt(0);
@@ skipping 172 matching lines @@
         Bigint::neg_offset(),
         new(I) Value(bigint),
         new(I) Value(value),
         kEmitStoreBarrier,
         call->token_pos());
     ReplaceCall(call, store);
     return true;
   }
 
   if (((recognized_kind == MethodRecognizer::kStringBaseCodeUnitAt) ||
-       (recognized_kind == MethodRecognizer::kStringBaseCharAt)) &&
+       (recognized_kind == MethodRecognizer::kStringBaseCharAt) ||
+       (recognized_kind == MethodRecognizer::kOneByteString_oneCodeUnitAt) ||
+       (recognized_kind == MethodRecognizer::kOneByteString_twoCodeUnitsAt) ||
+       (recognized_kind == MethodRecognizer::kOneByteString_fourCodeUnitsAt) ||
+       (recognized_kind == MethodRecognizer::kTwoByteString_oneCodeUnitAt) ||
+       (recognized_kind == MethodRecognizer::kTwoByteString_twoCodeUnitsAt)) &&
       (ic_data.NumberOfChecks() == 1) &&
       ((class_ids[0] == kOneByteStringCid) ||
        (class_ids[0] == kTwoByteStringCid))) {
     return TryReplaceInstanceCallWithInline(call);
   }
 
   if ((class_ids[0] == kOneByteStringCid) && (ic_data.NumberOfChecks() == 1)) {
     if (recognized_kind == MethodRecognizer::kOneByteStringSetAt) {
       // This is an internal method, no need to check argument types nor
       // range.
@@ skipping 4634 matching lines @@
 }
 
 
 void ConstantPropagator::VisitTargetEntry(TargetEntryInstr* block) {
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     it.Current()->Accept(this);
   }
 }
 
 
+void ConstantPropagator::VisitIndirectEntry(IndirectEntryInstr* block) {
+  for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+    it.Current()->Accept(this);
+  }
+}
+
+
 void ConstantPropagator::VisitCatchBlockEntry(CatchBlockEntryInstr* block) {
   const GrowableArray<Definition*>& defs = *block->initial_definitions();
   for (intptr_t i = 0; i < defs.length(); ++i) {
     defs[i]->Accept(this);
   }
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     it.Current()->Accept(this);
   }
 }
 
@@ skipping 27 matching lines @@
   SetReachable(instr->successor());
 
   // Phi value depends on the reachability of a predecessor. We have
   // to revisit phis every time a predecessor becomes reachable.
   for (PhiIterator it(instr->successor()); !it.Done(); it.Advance()) {
     it.Current()->Accept(this);
   }
 }
 
 
+void ConstantPropagator::VisitIndirectGoto(IndirectGotoInstr* instr) {
+  for (intptr_t i = 0; i < instr->SuccessorCount(); i++) {
+    SetReachable(instr->SuccessorAt(i));
+  }
+}
+
+
 void ConstantPropagator::VisitBranch(BranchInstr* instr) {
   instr->comparison()->Accept(this);
 
   // The successors may be reachable, but only if this instruction is.  (We
   // might be analyzing it because the constant value of one of its inputs
   // has changed.)
   if (reachable_->Contains(instr->GetBlock()->preorder_number())) {
     if (instr->constant_target() != NULL) {
       ASSERT((instr->constant_target() == instr->true_successor()) ||
              (instr->constant_target() == instr->false_successor()));
@@ skipping 391 matching lines @@
           SetValue(instr, result);
           return;
         }
       }
     }
     SetValue(instr, non_constant_);
   }
 }
 
 
+void ConstantPropagator::VisitLoadCodeUnits(LoadCodeUnitsInstr* instr) {
+  // TODO(jgruber): Implement constant propagation.
+  SetValue(instr, non_constant_);
+}
+
+
 void ConstantPropagator::VisitStoreIndexed(StoreIndexedInstr* instr) {
   SetValue(instr, instr->value()->definition()->constant_value());
 }
 
 
 void ConstantPropagator::VisitStoreInstanceField(
     StoreInstanceFieldInstr* instr) {
   SetValue(instr, instr->value()->definition()->constant_value());
 }
 
@@ skipping 622 matching lines @@
   const Object& right = instr->right()->definition()->constant_value();
   if (IsNonConstant(left) || IsNonConstant(right)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(left) && IsConstant(right)) {
     // TODO(srdjan): Handle min and max.
     SetValue(instr, non_constant_);
   }
 }
 
 
+void ConstantPropagator::VisitCaseInsensitiveCompareUC16(
+    CaseInsensitiveCompareUC16Instr *instr) {

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

Not sure if it's actually worth supporting: do you see cases where all inputs
are constants?

Maybe just simplify the code and say

SetValue(instr, non_constant_);

instead.

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

Done.

+  const Object& str = instr->str()->definition()->constant_value();
+  const Object& lhs_index = instr->lhs_index()->definition()->constant_value();
+  const Object& rhs_index = instr->rhs_index()->definition()->constant_value();
+  const Object& length = instr->length()->definition()->constant_value();
+
+  if (IsConstant(str) && str.IsString() &&
+      IsConstant(lhs_index) && lhs_index.IsSmi() &&
+      IsConstant(rhs_index) && rhs_index.IsSmi() &&
+      IsConstant(length) && length.IsSmi()) {
+    const Bool& result =
+        Bool::Handle(isolate(),
+                     IRRegExpMacroAssembler::CaseInsensitiveCompareUC16(
+                       String::Cast(str).raw(),
+                       Smi::Cast(lhs_index).raw(),
+                       Smi::Cast(rhs_index).raw(),
+                       Smi::Cast(length).raw()));
+    SetValue(instr, result);
+  } else {
+    SetValue(instr, non_constant_);
+  }
+}
+
+
 void ConstantPropagator::VisitUnboxDouble(UnboxDoubleInstr* instr) {
   const Object& value = instr->value()->definition()->constant_value();
   if (IsNonConstant(value)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(value)) {
     // TODO(kmillikin): Handle conversion.
     SetValue(instr, non_constant_);
   }
 }
 
@@ skipping 129 matching lines @@
     } else {
       BlockEntryInstr* block = block_worklist_.RemoveLast();
       block->Accept(this);
     }
   }
 }
 
 
 static bool IsEmptyBlock(BlockEntryInstr* block) {
   return block->next()->IsGoto() &&
-      (!block->IsJoinEntry() || (block->AsJoinEntry()->phis() == NULL));
+      (!block->IsJoinEntry() || (block->AsJoinEntry()->phis() == NULL)) &&
+      !block->IsIndirectEntry();
 }
 
 
 // Traverses a chain of empty blocks and returns the first reachable non-empty
 // block that is not dominated by the start block. The empty blocks are added
 // to the supplied bit vector.
 static BlockEntryInstr* FindFirstNonEmptySuccessor(
     TargetEntryInstr* block,
     BitVector* empty_blocks) {
   BlockEntryInstr* current = block;
@@ skipping 1170 matching lines @@
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits_collector_.exits().length(); i++) {
     CreateMaterializationAt(
         exits_collector_.exits()[i], alloc, alloc->cls(), *slots);
   }
 }
 
 
 }  // namespace dart