Port and integrate the irregexp engine from V8

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc
index f5333546f2ed98d51cc45fded39181aab427b875..2ccf0d9798f22590906b2419911d8e6c1c10a2f9 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -17,6 +17,7 @@
 #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"
@@ -1631,6 +1632,14 @@ bool FlowGraphOptimizer::TryInlineRecognizedMethod(intptr_t receiver_cid,
       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:
@@ -2840,6 +2849,56 @@ bool FlowGraphOptimizer::InlineStringCodeUnitAt(
 }
 
 
+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,
@@ -3032,7 +3091,12 @@ bool FlowGraphOptimizer::TryInlineInstanceMethod(InstanceCallInstr* call) {
   }
 
   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))) {
@@ -7687,6 +7751,13 @@ void ConstantPropagator::VisitTargetEntry(TargetEntryInstr* block) {
 }
 
 
+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) {
@@ -7734,6 +7805,13 @@ void ConstantPropagator::VisitGoto(GotoInstr* instr) {
 }
 
 
+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);
 
@@ -8145,6 +8223,12 @@ void ConstantPropagator::VisitLoadIndexed(LoadIndexedInstr* instr) {
 }
 
 
+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());
 }
@@ -8787,6 +8871,31 @@ void ConstantPropagator::VisitMathMinMax(MathMinMaxInstr* instr) {
 }
 
 
+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)) {
@@ -8936,7 +9045,8 @@ void ConstantPropagator::Analyze() {
 
 static bool IsEmptyBlock(BlockEntryInstr* block) {
   return block->next()->IsGoto() &&
-      (!block->IsJoinEntry() || (block->AsJoinEntry()->phis() == NULL));
+      (!block->IsJoinEntry() || (block->AsJoinEntry()->phis() == NULL)) &&
+      !block->IsIndirectEntry();
 }