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

src/ic.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 396 matching lines @@
 void KeyedStoreIC::Clear(Address address, Code* target) {
   if (target->ic_state() == UNINITIALIZED) return;
   SetTargetAtAddress(address,
       (Code::GetStrictMode(target->extra_ic_state()) == kStrictMode)
         ? initialize_stub_strict()
         : initialize_stub());
 }
 
 
 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);
 }
 
 
 static bool HasInterceptorGetter(JSObject* object) {
   return !object->GetNamedInterceptor()->getter()->IsUndefined();
 }
 
 
@@ skipping 1874 matching lines @@
 
 void BinaryOpIC::patch(Code* code) {
   set_target(code);
 }
 
 
 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";
   }
 }
 
 
 BinaryOpIC::State BinaryOpIC::ToState(TypeInfo type_info) {
   switch (type_info) {
     case UNINITIALIZED:
       return ::v8::internal::UNINITIALIZED;
     case SMI:
     case INT32:
     case HEAP_NUMBER:
     case ODDBALL:
-    case BOTH_STRING:
     case STRING:
       return MONOMORPHIC;
     case GENERIC:
       return MEGAMORPHIC;
   }
   UNREACHABLE();
   return ::v8::internal::UNINITIALIZED;
 }
 
 
-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);
 
   HandleScope scope(isolate);
   Handle<Object> operand = args.at<Object>(0);
   Token::Value op = static_cast<Token::Value>(args.smi_at(1));
   UnaryOverwriteMode mode = static_cast<UnaryOverwriteMode>(args.smi_at(2));
   UnaryOpIC::TypeInfo previous_type =
       static_cast<UnaryOpIC::TypeInfo>(args.smi_at(3));
 
@@ skipping 31 matching lines @@
 
   bool caught_exception;
   Handle<Object> result = Execution::Call(builtin_function, operand, 0, NULL,
                                           &caught_exception);
   if (caught_exception) {
     return Failure::Exception();
   }
   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;
+}
+
+
+static BinaryOpIC::TypeInfo InputState(BinaryOpIC::TypeInfo old_type,
+                                       Handle<Object> value,
+                                       Token::Value op) {
+  BinaryOpIC::TypeInfo new_type = TypeInfoFromValue(value, op);
+  if (old_type == BinaryOpIC::UNINITIALIZED) return new_type;

[danno, 2012/11/14 10:38:22]

remove above?

[Jakob Kummerow, 2012/11/14 15:53:23]

Done.

+  if (old_type == BinaryOpIC::STRING) {
+    if (new_type == BinaryOpIC::STRING) return new_type;
+    return BinaryOpIC::GENERIC;
+  }
+  return Max(old_type, new_type);
+}
+
+
 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));
+  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 type = BinaryOpIC::GetTypeInfo(left, right);
-  type = BinaryOpIC::JoinTypes(type, previous_type);
+  BinaryOpIC::TypeInfo new_left = InputState(previous_left, left, op);
+  BinaryOpIC::TypeInfo new_right = InputState(previous_right, right, op);
   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 ||
         kSmiValueSize == 32) {
       // Arithmetic on two Smi inputs has yielded a heap number.
       // That is the only way to get here from the Smi stub.
       // With 32-bit Smis, all overflows give heap numbers, but with
       // 31-bit Smis, most operations overflow to int32 results.
       result_type = BinaryOpIC::HEAP_NUMBER;
     } else {
       // Other operations on SMIs that overflow yield int32s.
       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;
+    }
   }
 
-  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 @ %p]\n",
+             BinaryOpIC::GetName(previous_left),
+             BinaryOpIC::GetName(previous_right),
+             BinaryOpIC::GetName(new_left),
+             BinaryOpIC::GetName(new_right),
              BinaryOpIC::GetName(result_type),
-             Token::Name(op));
+             Token::Name(op),
+             static_cast<void*>(*code));
     }
+#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);
     }
   }
 
   Handle<JSBuiltinsObject> builtins = Handle<JSBuiltinsObject>(
       isolate->thread_local_top()->context_->builtins(), isolate);
   Object* builtin = NULL;  // Initialization calms down the compiler.
   switch (op) {
     case Token::ADD:
       builtin = builtins->javascript_builtin(Builtins::ADD);
@@ skipping 42 matching lines @@
                                           builtin_args,
                                           &caught_exception);
   if (caught_exception) {
     return Failure::Exception();
   }
   return *result;
 }
 
 
 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;
 }
 
 
 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();
       return NULL;
   }
 }
 
 
-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() ==
             Handle<JSObject>::cast(y)->map() &&
             Token::IsEqualityOp(op_)) {
           return KNOWN_OBJECTS;
         } else {
-          return OBJECTS;
+          return OBJECT;
         }
       }
       return GENERIC;
-    case SMIS:
-      return has_inlined_smi_code && x->IsNumber() && y->IsNumber()
-          ? HEAP_NUMBERS
+    case SMI:
+      return x->IsNumber() && y->IsNumber()
+          ? 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.
 }
 
 
-// Used from ic_<arch>.cc.
+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 in ");
+    JavaScriptFrame::PrintTop(stdout, false, true);
+    PrintF(" ((%s+%s=%s)->(%s+%s=%s))#%s @ %p]\n",
+           GetStateName(previous_left),
+           GetStateName(previous_right),
+           GetStateName(previous_state),
+           GetStateName(new_left),
+           GetStateName(new_right),
+           GetStateName(state),
+           Token::Name(op_),
+           static_cast<void*>(*stub.GetCode()));
+  }
+#endif
+
+  // Activate inlined smi code.
+  if (previous_state == UNINITIALIZED) {
+    PatchInlinedSmiCode(address(), ENABLE_INLINED_SMI_CHECK);
+  }
+}
+
+
+// Used from ICCompareStub::GenerateMiss in code-stubs-<arch>.cc.
 RUNTIME_FUNCTION(Code*, CompareIC_Miss) {
   NoHandleAllocation na;
   ASSERT(args.length() == 3);
   CompareIC ic(isolate, static_cast<Token::Value>(args.smi_at(2)));
   ic.UpdateCaches(args.at<Object>(0), args.at<Object>(1));
   return ic.target();
 }
 
 
 RUNTIME_FUNCTION(MaybeObject*, ToBoolean_Patch) {
@@ skipping 28 matching lines @@
 #undef ADDR
 };
 
 
 Address IC::AddressFromUtilityId(IC::UtilityId id) {
   return IC_utilities[id];
 }
 
 
 } }  // namespace v8::internal