Lattice-based representation inference, powered by left/right specific type feedback for BinaryOps …

src/ic.cc

Index: src/ic.cc
diff --git a/src/ic.cc b/src/ic.cc
index dd0bb10e1057ad61f3f162727d1c1a66144178e7..1206e28b8539ede3815460d7c28713458d7d5e1d 100644
--- a/src/ic.cc
+++ b/src/ic.cc
@@ -414,11 +414,13 @@ void KeyedStoreIC::Clear(Address address, Code* target) {
 
 
 void CompareIC::Clear(Address address, Code* target) {
-  // Only clear ICCompareStubs, we currently cannot clear generic CompareStubs.
-  if (target->major_key() != CodeStub::CompareIC) return;
+  ASSERT(target->major_key() == CodeStub::CompareIC);
+  CompareIC::State handler_state;
+  Token::Value op;
+  ICCompareStub::DecodeMinorKey(target->stub_info(), NULL, NULL,
+                                &handler_state, &op);
   // Only clear CompareICs that can retain objects.
-  if (target->compare_state() != KNOWN_OBJECTS) return;
-  Token::Value op = CompareIC::ComputeOperation(target);
+  if (handler_state != KNOWN_OBJECTS) return;
   SetTargetAtAddress(address, GetRawUninitialized(op));
   PatchInlinedSmiCode(address, DISABLE_INLINED_SMI_CHECK);
 }
@@ -2307,11 +2309,10 @@ const char* BinaryOpIC::GetName(TypeInfo type_info) {
   switch (type_info) {
     case UNINITIALIZED: return "Uninitialized";
     case SMI: return "SMI";
-    case INT32: return "Int32s";
-    case HEAP_NUMBER: return "HeapNumbers";
+    case INT32: return "Int32";
+    case HEAP_NUMBER: return "HeapNumber";
     case ODDBALL: return "Oddball";
-    case BOTH_STRING: return "BothStrings";
-    case STRING: return "Strings";
+    case STRING: return "String";
     case GENERIC: return "Generic";
     default: return "Invalid";
   }
@@ -2326,7 +2327,6 @@ BinaryOpIC::State BinaryOpIC::ToState(TypeInfo type_info) {
     case INT32:
     case HEAP_NUMBER:
     case ODDBALL:
-    case BOTH_STRING:
     case STRING:
       return MONOMORPHIC;
     case GENERIC:
@@ -2337,58 +2337,6 @@ BinaryOpIC::State BinaryOpIC::ToState(TypeInfo type_info) {
 }
 
 
-BinaryOpIC::TypeInfo BinaryOpIC::JoinTypes(BinaryOpIC::TypeInfo x,
-                                           BinaryOpIC::TypeInfo y) {
-  if (x == UNINITIALIZED) return y;
-  if (y == UNINITIALIZED) return x;
-  if (x == y) return x;
-  if (x == BOTH_STRING && y == STRING) return STRING;
-  if (x == STRING && y == BOTH_STRING) return STRING;
-  if (x == STRING || x == BOTH_STRING || y == STRING || y == BOTH_STRING) {
-    return GENERIC;
-  }
-  if (x > y) return x;
-  return y;
-}
-
-
-BinaryOpIC::TypeInfo BinaryOpIC::GetTypeInfo(Handle<Object> left,
-                                             Handle<Object> right) {
-  ::v8::internal::TypeInfo left_type =
-      ::v8::internal::TypeInfo::TypeFromValue(left);
-  ::v8::internal::TypeInfo right_type =
-      ::v8::internal::TypeInfo::TypeFromValue(right);
-
-  if (left_type.IsSmi() && right_type.IsSmi()) {
-    return SMI;
-  }
-
-  if (left_type.IsInteger32() && right_type.IsInteger32()) {
-    // Platforms with 32-bit Smis have no distinct INT32 type.
-    if (kSmiValueSize == 32) return SMI;
-    return INT32;
-  }
-
-  if (left_type.IsNumber() && right_type.IsNumber()) {
-    return HEAP_NUMBER;
-  }
-
-  // Patching for fast string ADD makes sense even if only one of the
-  // arguments is a string.
-  if (left_type.IsString())  {
-    return right_type.IsString() ? BOTH_STRING : STRING;
-  } else if (right_type.IsString()) {
-    return STRING;
-  }
-
-  // Check for oddball objects.
-  if (left->IsUndefined() && right->IsNumber()) return ODDBALL;
-  if (left->IsNumber() && right->IsUndefined()) return ODDBALL;
-
-  return GENERIC;
-}
-
-
 RUNTIME_FUNCTION(MaybeObject*, UnaryOp_Patch) {
   ASSERT(args.length() == 4);
 
@@ -2440,25 +2388,63 @@ RUNTIME_FUNCTION(MaybeObject*, UnaryOp_Patch) {
   return *result;
 }
 
+
+static BinaryOpIC::TypeInfo TypeInfoFromValue(Handle<Object> value,
+                                              Token::Value op) {
+  ::v8::internal::TypeInfo type =
+      ::v8::internal::TypeInfo::TypeFromValue(value);
+  if (type.IsSmi()) return BinaryOpIC::SMI;
+  if (type.IsInteger32()) {
+    if (kSmiValueSize == 32) return BinaryOpIC::SMI;
+    return BinaryOpIC::INT32;
+  }
+  if (type.IsNumber()) return BinaryOpIC::HEAP_NUMBER;
+  if (type.IsString()) return BinaryOpIC::STRING;
+  if (value->IsUndefined()) {
+    if (op == Token::BIT_AND ||
+        op == Token::BIT_OR ||
+        op == Token::BIT_XOR ||
+        op == Token::SAR ||
+        op == Token::SHL ||
+        op == Token::SHR) {
+      if (kSmiValueSize == 32) return BinaryOpIC::SMI;
+      return BinaryOpIC::INT32;
+    }
+    return BinaryOpIC::ODDBALL;
+  }
+  return BinaryOpIC::GENERIC;
+}
+
+
 RUNTIME_FUNCTION(MaybeObject*, BinaryOp_Patch) {
-  ASSERT(args.length() == 5);
+  ASSERT(args.length() == 3);
 
   HandleScope scope(isolate);
   Handle<Object> left = args.at<Object>(0);
   Handle<Object> right = args.at<Object>(1);
   int key = args.smi_at(2);
-  Token::Value op = static_cast<Token::Value>(args.smi_at(3));
-  BinaryOpIC::TypeInfo previous_type =
-      static_cast<BinaryOpIC::TypeInfo>(args.smi_at(4));
-
-  BinaryOpIC::TypeInfo type = BinaryOpIC::GetTypeInfo(left, right);
-  type = BinaryOpIC::JoinTypes(type, previous_type);
+  Token::Value op = BinaryOpStub::decode_op_from_minor_key(key);
+  BinaryOpIC::TypeInfo previous_left, previous_right, unused_previous_result;
+  BinaryOpStub::decode_types_from_minor_key(
+      key, &previous_left, &previous_right, &unused_previous_result);
+
+  BinaryOpIC::TypeInfo new_left = TypeInfoFromValue(left, op);
+  BinaryOpIC::TypeInfo new_right = TypeInfoFromValue(right, op);
+  // Transition to more general type of {new, previous}.
+  new_left = Max(new_left, previous_left);
+  new_right = Max(new_right, previous_right);
   BinaryOpIC::TypeInfo result_type = BinaryOpIC::UNINITIALIZED;
-  if ((type == BinaryOpIC::STRING || type == BinaryOpIC::BOTH_STRING) &&
+
+  // STRING is only used for ADD operations.
+  if ((new_left == BinaryOpIC::STRING || new_right == BinaryOpIC::STRING) &&
       op != Token::ADD) {
-    type = BinaryOpIC::GENERIC;
+    new_left = new_right = BinaryOpIC::GENERIC;
   }
-  if (type == BinaryOpIC::SMI && previous_type == BinaryOpIC::SMI) {
+
+  BinaryOpIC::TypeInfo new_overall = Max(new_left, new_right);
+  BinaryOpIC::TypeInfo previous_overall = Max(previous_left, previous_right);
+
+  if (new_overall == BinaryOpIC::SMI && previous_overall == BinaryOpIC::SMI) {
     if (op == Token::DIV ||
         op == Token::MUL ||
         op == Token::SHR ||
@@ -2473,26 +2459,37 @@ RUNTIME_FUNCTION(MaybeObject*, BinaryOp_Patch) {
       result_type = BinaryOpIC::INT32;
     }
   }
-  if (type == BinaryOpIC::INT32 && previous_type == BinaryOpIC::INT32) {
-    // We must be here because an operation on two INT32 types overflowed.
-    result_type = BinaryOpIC::HEAP_NUMBER;
+  if (new_overall == BinaryOpIC::INT32 &&
+      previous_overall == BinaryOpIC::INT32) {
+    if (new_left == previous_left &&
+        new_right == previous_right) {
+      result_type = BinaryOpIC::HEAP_NUMBER;
+    } else {
+      result_type = BinaryOpIC::INT32;
+    }
   }
 
-  BinaryOpStub stub(key, type, result_type);
+  BinaryOpStub stub(key, new_left, new_right, result_type);
   Handle<Code> code = stub.GetCode();
   if (!code.is_null()) {
+#ifdef DEBUG
     if (FLAG_trace_ic) {
-      PrintF("[BinaryOpIC (%s->(%s->%s))#%s]\n",
-             BinaryOpIC::GetName(previous_type),
-             BinaryOpIC::GetName(type),
+      PrintF("[BinaryOpIC in ");
+      JavaScriptFrame::PrintTop(stdout, false, true);
+      PrintF(" ((%s+%s)->((%s+%s)->%s))#%s]\n",
+             BinaryOpIC::GetName(previous_left),
+             BinaryOpIC::GetName(previous_right),
+             BinaryOpIC::GetName(new_left),
+             BinaryOpIC::GetName(new_right),
              BinaryOpIC::GetName(result_type),
              Token::Name(op));
     }
+#endif
     BinaryOpIC ic(isolate);
     ic.patch(*code);
 
     // Activate inlined smi code.
-    if (previous_type == BinaryOpIC::UNINITIALIZED) {
+    if (previous_overall == BinaryOpIC::UNINITIALIZED) {
       PatchInlinedSmiCode(ic.address(), ENABLE_INLINED_SMI_CHECK);
     }
   }
@@ -2555,7 +2552,7 @@ RUNTIME_FUNCTION(MaybeObject*, BinaryOp_Patch) {
 
 
 Code* CompareIC::GetRawUninitialized(Token::Value op) {
-  ICCompareStub stub(op, UNINITIALIZED);
+  ICCompareStub stub(op, UNINITIALIZED, UNINITIALIZED, UNINITIALIZED);
   Code* code = NULL;
   CHECK(stub.FindCodeInCache(&code));
   return code;
@@ -2563,35 +2560,20 @@ Code* CompareIC::GetRawUninitialized(Token::Value op) {
 
 
 Handle<Code> CompareIC::GetUninitialized(Token::Value op) {
-  ICCompareStub stub(op, UNINITIALIZED);
+  ICCompareStub stub(op, UNINITIALIZED, UNINITIALIZED, UNINITIALIZED);
   return stub.GetCode();
 }
 
 
-CompareIC::State CompareIC::ComputeState(Code* target) {
-  int key = target->major_key();
-  if (key == CodeStub::Compare) return GENERIC;
-  ASSERT(key == CodeStub::CompareIC);
-  return static_cast<State>(target->compare_state());
-}
-
-
-Token::Value CompareIC::ComputeOperation(Code* target) {
-  ASSERT(target->major_key() == CodeStub::CompareIC);
-  return static_cast<Token::Value>(
-      target->compare_operation() + Token::EQ);
-}
-
-
 const char* CompareIC::GetStateName(State state) {
   switch (state) {
     case UNINITIALIZED: return "UNINITIALIZED";
-    case SMIS: return "SMIS";
-    case HEAP_NUMBERS: return "HEAP_NUMBERS";
-    case OBJECTS: return "OBJECTS";
+    case SMI: return "SMI";
+    case HEAP_NUMBER: return "HEAP_NUMBER";
+    case OBJECT: return "OBJECTS";
     case KNOWN_OBJECTS: return "KNOWN_OBJECTS";
-    case SYMBOLS: return "SYMBOLS";
-    case STRINGS: return "STRINGS";
+    case SYMBOL: return "SYMBOL";
+    case STRING: return "STRING";
     case GENERIC: return "GENERIC";
     default:
       UNREACHABLE();
@@ -2600,28 +2582,67 @@ const char* CompareIC::GetStateName(State state) {
 }
 
 
-CompareIC::State CompareIC::TargetState(State state,
+static CompareIC::State InputState(CompareIC::State old_state,
+                                   Handle<Object> value) {
+  switch (old_state) {
+    case CompareIC::UNINITIALIZED:
+      if (value->IsSmi()) return CompareIC::SMI;
+      if (value->IsHeapNumber()) return CompareIC::HEAP_NUMBER;
+      if (value->IsSymbol()) return CompareIC::SYMBOL;
+      if (value->IsString()) return CompareIC::STRING;
+      if (value->IsJSObject()) return CompareIC::OBJECT;
+      break;
+    case CompareIC::SMI:
+      if (value->IsSmi()) return CompareIC::SMI;
+      if (value->IsHeapNumber()) return CompareIC::HEAP_NUMBER;
+      break;
+    case CompareIC::HEAP_NUMBER:
+      if (value->IsNumber()) return CompareIC::HEAP_NUMBER;
+      break;
+    case CompareIC::SYMBOL:
+      if (value->IsSymbol()) return CompareIC::SYMBOL;
+      if (value->IsString()) return CompareIC::STRING;
+      break;
+    case CompareIC::STRING:
+      if (value->IsSymbol() || value->IsString()) return CompareIC::STRING;
+      break;
+    case CompareIC::OBJECT:
+      if (value->IsJSObject()) return CompareIC::OBJECT;
+      break;
+    case CompareIC::GENERIC:
+      break;
+    case CompareIC::KNOWN_OBJECTS:
+      UNREACHABLE();
+      break;
+  }
+  return CompareIC::GENERIC;
+}
+
+
+CompareIC::State CompareIC::TargetState(State old_state,
+                                        State old_left,
+                                        State old_right,
                                         bool has_inlined_smi_code,
                                         Handle<Object> x,
                                         Handle<Object> y) {
-  switch (state) {
+  switch (old_state) {
     case UNINITIALIZED:
-      if (x->IsSmi() && y->IsSmi()) return SMIS;
-      if (x->IsNumber() && y->IsNumber()) return HEAP_NUMBERS;
+      if (x->IsSmi() && y->IsSmi()) return SMI;
+      if (x->IsNumber() && y->IsNumber()) return HEAP_NUMBER;
       if (Token::IsOrderedRelationalCompareOp(op_)) {
         // Ordered comparisons treat undefined as NaN, so the
         // HEAP_NUMBER stub will do the right thing.
         if ((x->IsNumber() && y->IsUndefined()) ||
             (y->IsNumber() && x->IsUndefined())) {
-          return HEAP_NUMBERS;
+          return HEAP_NUMBER;
         }
       }
       if (x->IsSymbol() && y->IsSymbol()) {
         // We compare symbols as strings if we need to determine
         // the order in a non-equality compare.
-        return Token::IsEqualityOp(op_) ? SYMBOLS : STRINGS;
+        return Token::IsEqualityOp(op_) ? SYMBOL : STRING;
       }
-      if (x->IsString() && y->IsString()) return STRINGS;
+      if (x->IsString() && y->IsString()) return STRING;
       if (!Token::IsEqualityOp(op_)) return GENERIC;
       if (x->IsJSObject() && y->IsJSObject()) {
         if (Handle<JSObject>::cast(x)->map() ==
@@ -2629,30 +2650,63 @@ CompareIC::State CompareIC::TargetState(State state,
             Token::IsEqualityOp(op_)) {
           return KNOWN_OBJECTS;
         } else {
-          return OBJECTS;
+          return OBJECT;
         }
       }
       return GENERIC;
-    case SMIS:
+    case SMI:
       return has_inlined_smi_code && x->IsNumber() && y->IsNumber()
-          ? HEAP_NUMBERS
+          ? HEAP_NUMBER
           : GENERIC;
-    case SYMBOLS:
+    case SYMBOL:
       ASSERT(Token::IsEqualityOp(op_));
-      return x->IsString() && y->IsString() ? STRINGS : GENERIC;
-    case HEAP_NUMBERS:
-    case STRINGS:
-    case OBJECTS:
+      return x->IsString() && y->IsString() ? STRING : GENERIC;
+    case HEAP_NUMBER:
+      if (old_left == SMI && x->IsHeapNumber()) return HEAP_NUMBER;
+      if (old_right == SMI && y->IsHeapNumber()) return HEAP_NUMBER;
+    case STRING:
+    case OBJECT:
     case KNOWN_OBJECTS:
     case GENERIC:
       return GENERIC;
   }
   UNREACHABLE();
-  return GENERIC;
+  return GENERIC;  // Make the compiler happy.
+}
+
+
+void CompareIC::UpdateCaches(Handle<Object> x, Handle<Object> y) {
+  HandleScope scope;
+  State previous_left, previous_right, previous_state;
+  ICCompareStub::DecodeMinorKey(target()->stub_info(), &previous_left,
+                                &previous_right, &previous_state, NULL);
+  State new_left = InputState(previous_left, x);
+  State new_right = InputState(previous_right, y);
+  State state = TargetState(previous_state, previous_left, previous_right,
+                            HasInlinedSmiCode(address()), x, y);
+  ICCompareStub stub(op_, new_left, new_right, state);
+  if (state == KNOWN_OBJECTS) {
+    stub.set_known_map(Handle<Map>(Handle<JSObject>::cast(x)->map()));
+  }
+  set_target(*stub.GetCode());
+
+#ifdef DEBUG
+  if (FLAG_trace_ic) {
+    PrintF("[CompareIC (%s->%s)#%s]\n",
+           GetStateName(previous_state),
+           GetStateName(state),
+           Token::Name(op_));
+  }
+#endif
+
+  // Activate inlined smi code.
+  if (previous_state == UNINITIALIZED) {
+    PatchInlinedSmiCode(address(), ENABLE_INLINED_SMI_CHECK);
+  }
 }
 
 
-// Used from ic_<arch>.cc.
+// Used from ICCompareStub::GenerateMiss in code-stubs-<arch>.cc.
 RUNTIME_FUNCTION(Code*, CompareIC_Miss) {
   NoHandleAllocation na;
   ASSERT(args.length() == 3);