Optimize one byte string comparisons.

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/dart_entry.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 1463 matching lines @@
   last->LinkTo(call);
   // Remove through the iterator.
   ASSERT(current_iterator()->Current() == call);
   current_iterator()->RemoveCurrentFromGraph();
   call->set_previous(NULL);
   call->set_next(NULL);
   return true;
 }
 
 
+static bool IsStringFromCharCode(Definition* d) {
+  return (d->IsStringCharCode() &&
+      (d->AsStringCharCode()->kind() == StringCharCodeInstr::kFromCharCode));
+}
+
+
+// Return true if d is a string of length one (a constant or result from
+// from string-from-char-code instruction.
+static bool IsLengthOneString(Definition* d) {
+  if (d->IsConstant()) {
+    const Object& obj = d->AsConstant()->value();
+    if (obj.IsString()) {
+      return String::Cast(obj).Length() == 1;
+    } else {
+      return false;
+    }
+  } else {
+    return IsStringFromCharCode(d);
+  }
+}
+
+
+// Returns true if the string comparison was converted into char-code
+// comparison. Conversion is only possible for strings of length one.
+// E.g., detect str[x] == "x"; and use an integer comparison of char-codes.
+// TODO(srdjan): Expand for two-byte and external strings.
+bool FlowGraphOptimizer::TryStringLengthOneEquality(InstanceCallInstr* call,
+                                                    Token::Kind op_kind) {
+  ASSERT(HasOnlyTwoOf(*call->ic_data(), kOneByteStringCid));
+  // Check that left and right are length one strings (either string constants
+  // or results of string-from-char-code.
+  Definition* left = call->ArgumentAt(0);
+  Definition* right = call->ArgumentAt(1);
+  Value* left_val = NULL;
+  Definition* to_remove_left = NULL;
+  if (IsLengthOneString(right)) {
+    // Swap, since we know that both arguments are strings
+    Definition* temp = left;
+    left = right;
+    right = temp;
+  }
+  if (IsLengthOneString(left)) {
+    // Optimize if left is a string with length one (either constant or
+    // result of string-from-char-code.
+    if (left->IsConstant()) {
+      ConstantInstr* left_const = left->AsConstant();
+      const String& str = String::Cast(left_const->value());
+      ASSERT(str.Length() == 1);
+      ConstantInstr* char_code_left =
+          new ConstantInstr(Smi::ZoneHandle(Smi::New(str.CharAt(0))));

[Florian Schneider, 2013/12/20 09:29:12]

Use flow_graph()->GetConstant(Smi::Handle(Smi::New(str.CharAt(0)))) instead.

[srdjan, 2013/12/20 19:48:03]

Done, and using ZoneHandle since the handle escapes this scope. Also removed
InsertBefore below, as I do not need to add constants in the list, and it does
not work for shared constant instructions.

+      InsertBefore(call, char_code_left, NULL, Definition::kValue);
+      left_val = new Value(char_code_left);
+    } else if (IsStringFromCharCode(left)) {
+      // Use input of string-from-charcode as left value.
+      StringCharCodeInstr* instr = left->AsStringCharCode();
+      left_val = new Value(instr->char_code()->definition());
+      to_remove_left = instr;
+    } else {
+      // IsLengthOneString(left) should have been false.
+      UNREACHABLE();
+    }
+
+    Definition* to_remove_right = NULL;
+    Value* right_val = NULL;
+    if (IsStringFromCharCode(right)) {
+      // Skip string-from-char-code, and use its input as right value.
+      StringCharCodeInstr* right_instr = right->AsStringCharCode();
+      right_val = new Value(right_instr->char_code()->definition());
+      to_remove_right = right_instr;
+    } else {
+      const ICData& unary_checks_1 =
+          ICData::ZoneHandle(call->ic_data()->AsUnaryClassChecksForArgNr(1));
+      AddCheckClass(right,
+                    unary_checks_1,
+                    call->deopt_id(),
+                    call->env(),
+                    call);
+      // String-to-char-code instructions returns -1 (illegal charcode) if
+      // string is not of length one.
+      StringCharCodeInstr* char_code_right = new StringCharCodeInstr(
+          new Value(right),
+          kOneByteStringCid,
+          StringCharCodeInstr::kToCharCode);
+      InsertBefore(call, char_code_right, call->env(), Definition::kValue);
+      right_val = new Value(char_code_right);
+    }
+
+    // Comparing char-codes instead of strings.
+    EqualityCompareInstr* comp =
+        new EqualityCompareInstr(call->token_pos(),
+                                 op_kind,
+                                 left_val,
+                                 right_val,
+                                 kSmiCid,
+                                 call->deopt_id());
+    ReplaceCall(call, comp);
+
+    // Remove dead instructions.
+    if ((to_remove_left != NULL) &&
+        (to_remove_left->input_use_list() == NULL)) {
+      ConstantInstr* null = new ConstantInstr(Instance::ZoneHandle());

[Florian Schneider, 2013/12/20 09:29:12]

Use flow_grah()->constant_null().

[srdjan, 2013/12/20 19:48:03]

Done.

+      to_remove_left->ReplaceUsesWith(null);
+      to_remove_left->RemoveFromGraph();
+    }
+    if ((to_remove_right != NULL) &&
+        (to_remove_right->input_use_list() == NULL)) {
+      ConstantInstr* null = new ConstantInstr(Instance::ZoneHandle());

[Florian Schneider, 2013/12/20 09:29:12]

Use flow_grah()->constant_null().

[srdjan, 2013/12/20 19:48:03]

Done.

+      to_remove_right->ReplaceUsesWith(null);
+      to_remove_right->RemoveFromGraph();
+    }
+    return true;
+  }
+  return false;
+}
+
+
 static bool SmiFitsInDouble() { return kSmiBits < 53; }
 
 bool FlowGraphOptimizer::TryReplaceWithEqualityOp(InstanceCallInstr* call,
                                                   Token::Kind op_kind) {
   const ICData& ic_data = *call->ic_data();
   ASSERT(ic_data.num_args_tested() == 2);
 
   ASSERT(call->ArgumentCount() == 2);
   Definition* left = call->ArgumentAt(0);
   Definition* right = call->ArgumentAt(1);
 
   intptr_t cid = kIllegalCid;
-  if (HasOnlyTwoOf(ic_data, kSmiCid)) {
+  if (HasOnlyTwoOf(ic_data, kOneByteStringCid)) {
+    if (TryStringLengthOneEquality(call, op_kind)) {
+      return true;
+    } else {
+      return false;
+    }
+  } else if (HasOnlyTwoOf(ic_data, kSmiCid)) {
     InsertBefore(call,
                  new CheckSmiInstr(new Value(left), call->deopt_id()),
                  call->env(),
                  Definition::kEffect);
     InsertBefore(call,
                  new CheckSmiInstr(new Value(right), call->deopt_id()),
                  call->env(),
                  Definition::kEffect);
     cid = kSmiCid;
   } else if (HasTwoMintOrSmi(ic_data) &&
@@ skipping 841 matching lines @@
     LoadIndexedInstr* instr = BuildStringCodeUnitAt(call, class_ids[0]);
     ReplaceCall(call, instr);
     return true;
   }
   if ((class_ids[0] == kOneByteStringCid) && (ic_data.NumberOfChecks() == 1)) {
     if (recognized_kind == MethodRecognizer::kStringBaseCharAt) {
       // TODO(fschneider): Handle TwoByteString.
       LoadIndexedInstr* load_char_code =
           BuildStringCodeUnitAt(call, class_ids[0]);
       InsertBefore(call, load_char_code, NULL, Definition::kValue);
-      StringFromCharCodeInstr* char_at =
-          new StringFromCharCodeInstr(new Value(load_char_code),
-                                      kOneByteStringCid);
+      StringCharCodeInstr* char_at =
+          new StringCharCodeInstr(new Value(load_char_code),
+                                  kOneByteStringCid,
+                                  StringCharCodeInstr::kFromCharCode);
       ReplaceCall(call, char_at);
       return true;
     }
     if (recognized_kind == MethodRecognizer::kOneByteStringSetAt) {
       // This is an internal method, no need to check argument types nor
       // range.
       Definition* str = call->ArgumentAt(0);
       Definition* index = call->ArgumentAt(1);
       Definition* value = call->ArgumentAt(2);
       StoreIndexedInstr* store_op = new StoreIndexedInstr(
@@ skipping 4283 matching lines @@
     }
   }
 }
 
 
 void ConstantPropagator::VisitNativeCall(NativeCallInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
-void ConstantPropagator::VisitStringFromCharCode(
-    StringFromCharCodeInstr* instr) {
-  SetValue(instr, non_constant_);
+void ConstantPropagator::VisitStringCharCode(StringCharCodeInstr* instr) {
+  if (instr->kind() == StringCharCodeInstr::kFromCharCode) {
+    const Object& o = instr->char_code()->definition()->constant_value();
+    if (IsNonConstant(o)) {
+      SetValue(instr, non_constant_);
+    } else if (IsConstant(o)) {
+      const intptr_t ch_code = Smi::Cast(o).Value();
+      ASSERT(ch_code >= 0);
+      if (ch_code < Symbols::kMaxOneCharCodeSymbol) {
+        RawString** table = Symbols::PredefinedAddress();
+        SetValue(instr, String::ZoneHandle(table[ch_code]));
+      } else {
+        SetValue(instr, non_constant_);
+      }
+    }
+  } else {
+    ASSERT(instr->kind() == StringCharCodeInstr::kToCharCode);
+    const Object& o = instr->str()->definition()->constant_value();
+    if (IsNonConstant(o)) {
+      SetValue(instr, non_constant_);
+    } else if (IsConstant(o)) {
+      const String& str = String::Cast(o);
+      const intptr_t result = (str.Length() == 1) ? str.CharAt(0) : -1;

[Florian Schneider, 2013/12/20 09:29:12]

Can the case of Length() > 1 occur at all?

[srdjan, 2013/12/20 19:48:03]

Yes, length 0 as well. StringToCharCode has as its input any string and returns
-1 if the string is not of length one, thus it will not match/equal to a string
of length 1.

+      SetValue(instr, Smi::ZoneHandle(Smi::New(result)));
+    }
+  }
 }
 
 
 void ConstantPropagator::VisitStringInterpolate(StringInterpolateInstr* instr) {
   SetValue(instr, non_constant_);
   return;
 }
 
 
 void ConstantPropagator::VisitLoadIndexed(LoadIndexedInstr* instr) {
@@ skipping 1469 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *fields);
   }
 }
 
 
 }  // namespace dart